IT計(jì)算機(jī) 數(shù)據(jù)結(jié)構(gòu)與算法

數(shù)據(jù)結(jié)構(gòu)與算法

F王昭

北京大學(xué)信息學(xué)院軟件研究所

wangzhao@

內(nèi)容提要

?課程簡(jiǎn)介

第一章緒論

2

為什么要學(xué)習(xí)該課程

?學(xué)分

?畢業(yè)

3

學(xué)兄、學(xué)姐的體會(huì)

?學(xué)兄、學(xué)姐的體會(huì)

4

一堂讓人變得更聰明的課

?是需要調(diào)整思維習(xí)慣和方式而非僅僅充實(shí)知識(shí)

庫(kù)。

?要變得聰明一些，就要學(xué)會(huì)選擇適當(dāng)?shù)慕嵌?/p>

?一旦領(lǐng)會(huì)，終生受益。

寸口7

漢字結(jié)構(gòu)

?細(xì)胞結(jié)構(gòu)

?物質(zhì)結(jié)構(gòu)

?地球的內(nèi)部結(jié)構(gòu)

?文章結(jié)構(gòu)

?建筑結(jié)構(gòu)

?結(jié)構(gòu):實(shí)體+關(guān)系，把某些成份按一定的規(guī)律或方式組織在

一起的實(shí)體或某些成分組織在一起的方式

在這里，我們把實(shí)體看作數(shù)據(jù)

?算法

?是對(duì)特定問(wèn)題求解方法和步驟的一種描述。

。最大公因數(shù)的求解算法

O一元二次方程的求解

。圓周長(zhǎng)、圓面積

。立方體的表面積和邊長(zhǎng)

。排序

O分治、貪心、動(dòng)態(tài)規(guī)劃……

7

［數(shù)據(jù)結(jié)構(gòu)+算法=程序］

NikiklausWirth

?程序：為計(jì)算機(jī)解決問(wèn)題編制的指令集，是按照

事先設(shè)計(jì)的功能和性能要求執(zhí)行的指令序列

?從程序設(shè)計(jì)的觀點(diǎn)來(lái)看，

c信息的表示：“數(shù)據(jù)結(jié)構(gòu)”研究的問(wèn)題

。信息的處理：“算法”研究的問(wèn)題

了解計(jì)算機(jī)原理、掌握程序設(shè)計(jì)的必由之路。

8

課程目標(biāo)

?學(xué)會(huì)怎樣組織信息，以便支持高效的數(shù)據(jù)處理

O掌握常用的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用

O學(xué)會(huì)合理組織數(shù)據(jù)、有效地處理數(shù)據(jù)

O基本掌握算法的設(shè)計(jì)與分析方法

O提高程序設(shè)計(jì)能力

9

“數(shù)據(jù)結(jié)構(gòu)與算法”課程與計(jì)算機(jī)專業(yè)其他課程的關(guān)系

人工智能

隊(duì)列.圖、字符、矩廣義表.集合、各圖形圖像

陣、散列、排序、種有向圖、搜索惻隊(duì)列.棧、圖、矩陣、

索引、檢索J空間索引樹(shù).檢索

一小~~工

「操作系統(tǒng)

數(shù)據(jù)庫(kù)概論編譯原理

線性表、多鏈表、隊(duì)列、存儲(chǔ)管理表、

字符申、棧、

排序、B+索引用\排芹、目錄樹(shù)」1

列表、語(yǔ)法樹(shù)

數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)

算法分析與設(shè)計(jì)可看計(jì)算復(fù)「雜二性理論

數(shù)據(jù)結(jié)構(gòu)與算法

程序設(shè)計(jì)實(shí)習(xí)

集合論與國(guó)

概率統(tǒng)計(jì)計(jì)算概論

建議的學(xué)習(xí)方案

?聽(tīng)課，思考，提問(wèn)，討論

。三人行，必我我?guī)熝?/p>

O學(xué)而不思則罔，思而不學(xué)則殆

。不恥下問(wèn)

。獨(dú)學(xué)而無(wú)友則孤陋而寡聞

?上機(jī)

紙上得來(lái)終覺(jué)淺，絕知此事要躬行

聽(tīng)懂很容易，學(xué)會(huì)才是真

11

教學(xué)方式

?課堂講授：3學(xué)時(shí)/周

每周：星期三3~4節(jié)(10:10~12:00)

單周：星期五7~8節(jié)(14:40~16:30)

?上機(jī)實(shí)踐：2學(xué)時(shí)/周，

每周：星期五11~12節(jié)(19:00~21:00)

(從上課起第3周開(kāi)始)

12

課件位置

?課件位置

C北京大學(xué)教學(xué)網(wǎng)

?http:〃course.Q/webapps/login/

Ohttn:〃/~wangzhao/

?開(kāi)設(shè)課程

13

教材和參考書(shū)

?教材：

O算法與數(shù)據(jù)結(jié)構(gòu).C語(yǔ)言描述（第2版），

張乃孝主編，高等教育出版社,2006」

參考書(shū)：

。數(shù)據(jù)結(jié)構(gòu)?C語(yǔ)言版，（有配套習(xí)題集與習(xí)題解

答）嚴(yán)蔚敏等，清華大學(xué)出版社

O數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用C++語(yǔ)言描述，大量的習(xí)

題），網(wǎng)上PDF格式，翻譯教材

14

其他參考教材

?張銘，劉曉丹譯?！稊?shù)據(jù)結(jié)構(gòu)與算法分析》（C++兩版、

Java版）。電子工業(yè)出版社2002年6月C++第二版，2001

年1月Java版，1998年8月C++第一版。譯自：Clifford

A.Shaffer,ApracticalIntroductiontoDataStructures

andAlgorithmAnalysis,PrenticeHallo

殷人昆等,數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語(yǔ)言描述）第2

版,清華大學(xué)出版社,2007年6月。

?廖明宏等，《數(shù)據(jù)結(jié)構(gòu)與算法■（第4版）》，高等教育，

2007年11月。

?耿國(guó)華等，《數(shù)據(jù)結(jié)構(gòu)語(yǔ)言描述》，高等教育出版社

,2006年1月。

?王曉東等，《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》，電子工業(yè)出版社

,2007年7月。15

課程資源

?清華大學(xué)的《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏主講視頻教程

/2004/09/30/0000022031.html

網(wǎng)絡(luò)課堂的ISO

/2004/10/01/0000022112.html

?北大計(jì)算機(jī)系課程資源（包含課程的視頻C++語(yǔ)言）

http:〃/pkuipk/course/siig/

?西北工業(yè)大學(xué)“數(shù)據(jù)結(jié)構(gòu)”（包含課程的視頻）

http:〃ipkc.nwu./datastr/

?“算法+數(shù)據(jù)結(jié)構(gòu)"http:〃algorithm./

16

成績(jī)考核

“學(xué)生成績(jī)二平時(shí)成績(jī)（50%）+期末考試成績(jī)（50%）”

r平時(shí)作業(yè)（一定要按時(shí)交）20%

平時(shí)成績(jī)50%，隨堂測(cè)驗(yàn)+考勤10%（由助教負(fù)責(zé)）

上機(jī)20%

期末考試成績(jī)50%

注重綜合能力的考評(píng)，平時(shí)表現(xiàn)突出、上機(jī)能力較強(qiáng)的

（如完成附加題）可以得到獎(jiǎng)勵(lì)加分，不超過(guò)5分。

“優(yōu)秀率（85分以上）原則上不超過(guò)30%,不及格率（60分

以下）不超過(guò)15%?！?/p>

作業(yè)要求

?書(shū)面作業(yè)

按時(shí)交，杜絕抄襲（一旦發(fā)現(xiàn)，該次作業(yè)成績(jī)0分）

上機(jī)作業(yè)

程序編寫

程序調(diào)試

運(yùn)行結(jié)果

□做什么

輔導(dǎo)教員檢查

□怎么做

上機(jī)報(bào)告

□結(jié)果

□體會(huì)與收獲

18

上機(jī)安排

?上機(jī)時(shí)間

周五11?12節(jié)(19:00-21:00)

?上機(jī)地點(diǎn)：

計(jì)算中心機(jī)房：號(hào)機(jī)房(理科1號(hào)樓2層)

?輔導(dǎo)老師：

孫'聰：suncong.pku@

冀康：jikang1985@

蔣星博：jiangxb1987@

杜龍志：dlz@

19

上機(jī)要求

?上機(jī)環(huán)境

VC++6.0

?要求

c認(rèn)真準(zhǔn)備，有備而來(lái)；

O嚴(yán)禁玩游戲；

O及時(shí)向輔導(dǎo)老師反映問(wèn)題；

。培養(yǎng)獨(dú)立解決問(wèn)題的能力O

20

答疑安排

?平時(shí)有疑問(wèn)請(qǐng)?jiān)谡n下及時(shí)解決，如有問(wèn)題

發(fā)郵件

?考試前安排『2次答疑時(shí)間

?有何意見(jiàn)及建議請(qǐng)及時(shí)反映

21

內(nèi)容提要

?課程簡(jiǎn)介

?第一章緒論

22

第一章緒論

?為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

?數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)

?算法與算法評(píng)價(jià)

?總結(jié)

23

數(shù)值計(jì)算與非數(shù)值計(jì)算

?對(duì)于數(shù)值計(jì)算問(wèn)題，處理的對(duì)象為簡(jiǎn)單的

數(shù)值，數(shù)學(xué)模型為數(shù)學(xué)方程；

對(duì)于非數(shù)值計(jì)算問(wèn)題（如資料查詢、交通

管理等），處理的對(duì)象之間具有一定的邏

輯關(guān)系，其數(shù)學(xué)模型不能簡(jiǎn)單地用數(shù)學(xué)方

程描述，此時(shí)必須根據(jù)對(duì)象之間的邏輯關(guān)

系建立描述問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。

24

非數(shù)值計(jì)算問(wèn)題分析

?信息管理（圖書(shū)、檔案、職工等）

?交通管理（城市交通管理、航線、鐵路、公路等）

關(guān)鍵：

數(shù)據(jù)的表示（數(shù)據(jù)結(jié)構(gòu)問(wèn)題）和數(shù)據(jù)的處理（算

法問(wèn)題）

25

些問(wèn)題

空氣污染嚴(yán)重的城市有：太原、北京、烏魯木齊、

蘭州、重慶、濟(jì)南、石家莊、青島、廣州、沈陽(yáng)。

水污染嚴(yán)重的城市有：臨汾、陽(yáng)泉、大同、石嘴

山、三門峽、金昌、石家莊、重慶、株洲和洛陽(yáng)。

列出空氣污染嚴(yán)重或水污染嚴(yán)重的城市（集合的

并）。

26

西薇巨柏XX么"貢

氏葉松XX公頃

白皮松XXO1頁(yè)

云杉XX公頃

冷杉XX公頃

鐵杉XX公頃

如現(xiàn)國(guó)家要統(tǒng)計(jì)四川金錢松XX公頃

某年我國(guó)的野生銀杉XX公匕頁(yè)

銀杏X(jué)X公匕頁(yè)

植物保護(hù)情況。水杉XX公頃

現(xiàn)有各省市各種云杉XX公匕頁(yè)

冷杉XX公頃

珍稀野生植物的紅杉XX公4頁(yè)

種植面積，要統(tǒng)紅豆杉XX公頃

連香樹(shù)XX公頃

計(jì)各種野生植物湖南銀杉XX公頃

在我國(guó)總的種植水杉XX公L頁(yè)

云杉XX公頃

金錢松XX公頃

伯樂(lè)樹(shù)X2K公H更

連香樹(shù)XX公匕頁(yè)

莢囊蹂XX公頃

27

根據(jù)各城市的GDP值，給出全國(guó)GDP的總排名。

某年南方GDP排名前二十如下:同年北方GDP排名前二十如下

排名城市GDP及增氏排名城市GDP及增長(zhǎng)

01上海10297-12.0%01北京7720+12.0%

02廣州6068+147%02天津4338+11.1%

03深圳5684+15.0%03膏島3207+15.7%

04蘇州4820+15.5%04大連2568^16.1%

05堂慶3486+12.2%05沈陽(yáng)2483+16.5%

06杭州3441+14.3%06煙臺(tái)2402+17.0%

073360+15.0%07唐山2362+11.8%

08佛山29274-19.3%08濟(jì)南2185+15.7%

09寧波2864+13.4%09哈爾濱2091+13.5%

1U南樂(lè)2774+151%10石家莊2061+13.2%

11成都2750+13.8%11鄭州2002+15.7%

12東莞2624+19.1%12;、春1934+11.5%

13武漢2590+14.8%13濰坊1721+16.5%

14泉州1901+15.0%14淄博1645+15.8%

15溫州1834+13.3%15大慶1618~11.1%

16長(zhǎng)沙1791+14.8%16濟(jì)寧1156+16.5%

17南通1758+15.7%17西安1450+12.8%

18紹興1678+13.2%18東營(yíng)1150+17.0%

19福州1660+12.2%19臨沂1105+16.3%

20常州1560+15.0%20威海1369^15.9%

線性表問(wèn)題

每人一個(gè)記錄，多個(gè)數(shù)據(jù)項(xiàng);

什么樣的邏輯關(guān)系？

如何存儲(chǔ)？

什么樣的操作？

（統(tǒng)計(jì)、檢索問(wèn)題）

編號(hào)姓名性別年齡月收入

1李泉男51980

2王怡女47945

3張三男35870

4馬小丁男27840

???????????????

29

找出下歹UDNA片斷是否包含

TTCCTATGGGAGTGGCCCTCAGTCCGTTTCTCCTGGCTCAGTTTACTA序列。

?DNASEQUENCE：

?ATGGGAGGTTCGTCTTCCAAAGCTCGACAA

GGCATGGGGACGAATCTTTCTGTTGCCAAT

CCTCTGGGATTCTTTCCCGATCACCAGTTG

GACCCTGGGTTGGGAGCCAACTCAAACAAT

?CCAGATTGGGACTTGAACCCCAACAAGGAT

CACTGGCCAGAGGCAAATCAGGTAGGAGCG

?GGAGCATTCGGGCCAGGGTTCACCCCACCA

CACGGCGGTCTTTTGGGGTGGACCCCTCAG

GCTCAGGGGATTTTGACAACAGTGCCAGTA

GCACCTCCTCCTGCCTCCAGCAATCGCCAG

?CAGTGGAACTCCACAACATTCCACCAACCT

CTGCCAGACCCCAGAGTGAGGGGCCTATAC30

某生態(tài)系統(tǒng)的食物網(wǎng)如下圖所示。找出對(duì)山獅的生

存有影響的動(dòng)物。

31

用9-5個(gè)出地生態(tài)系收的部分食物網(wǎng)

Google地圖，輸入出發(fā)起始點(diǎn)和到達(dá)終止點(diǎn)，網(wǎng)站即推薦乘

車方式，本源即為最短路徑問(wèn)題。圖中的距離還可根據(jù)交通

擁塞程度加權(quán)。

已保存地址?登錄?都助

駟圖莊逸迅地圖逾壇更多》

Google北京崇文區(qū)天壇二北京海淀區(qū)中關(guān)村北大街116號(hào)北方|行車路鏤-

搜索地圖梗索周邊行車路線

搜索結(jié)果目立金區(qū)電子郵件?顯示本頁(yè)鏈接

———二S

與）旦北京崇文區(qū)天壇Si0i0

a北五環(huán)

翹.

臼駕駛219公里

1進(jìn)入天壇路向東南232米

.025?

2左轉(zhuǎn)掉頭進(jìn)入天壇路向西06公里

西環(huán)

?*.i

3.右轉(zhuǎn)進(jìn)入祈年大街向北1.4公里五

環(huán)

4.左轉(zhuǎn)進(jìn)入前門東大街向西北92公里環(huán)

5靠左進(jìn)入西直門北大街向北29公里?朝陽(yáng)公園

?北京:策

6.右轉(zhuǎn)進(jìn)入藥門橋向東北47米

7右轉(zhuǎn)進(jìn)入北三環(huán)西路輔路向西06公里京「通快速丁跖

8靠左進(jìn)入北三環(huán)西路向西1.9?里

五

2靠右進(jìn)入北三環(huán)西路輔路向西0.6公里

阡

10右轉(zhuǎn)進(jìn)入中關(guān)村大街向北36公里

11左轉(zhuǎn)掉頭進(jìn)入中關(guān)村北大街向南08公里南

金苑

0至北京海淀區(qū)中關(guān)村北大街116號(hào)北克路

大學(xué)修改

本行車路線僅供計(jì)劃N用，M際路況可需不同于地圖顯?世界公園：

示結(jié)果.

32

地圖孫據(jù)^2007MstsabccomI?2007Google-地圖數(shù)據(jù)磔D搏Mapabc.8m-三|'二

@InternetO?、100%

Google地圖,輸入出發(fā)起始點(diǎn)和到照黑工警整堞

車方式，本源即為最短路徑問(wèn)題。圖中的距禺還可根據(jù)父通

擁塞程度加權(quán)。

33

假設(shè)在中國(guó)有30個(gè)城市，城市之間想建公路，假設(shè)公路的建

設(shè)費(fèi)用與公路的長(zhǎng)度成正比，而這12個(gè)城市之間的位置都已

經(jīng)假定，分別用坐標(biāo)表示，如何鏈接公路使得所有的城市都

能鏈接，并且成本最?。?/p>

烏魯木齊長(zhǎng)春

呼和浩？北京

平壤

銀川

濟(jì)南

西寧?蘭州

西安

合肥

武漢杭州

不丹

釣魚(yú)島

臺(tái)北

澳門&香港

非線性問(wèn)題

每個(gè)城市為一個(gè)數(shù)據(jù)單位；

什么樣的邏輯關(guān)系？

如何存儲(chǔ)？

什么樣的操作？（尋找最短路徑等）

北京

1、天津,

659

鄭州徐州

349

651

9

武漢

上海

1

890

101650>

2

廣州福州

35

工廠污水檢測(cè)問(wèn)題：假設(shè)有10000個(gè)工廠，現(xiàn)在從每個(gè)工廠

里面的排水系統(tǒng)獲得樣品，每個(gè)工廠的排水樣品被訪到一個(gè)

標(biāo)號(hào)的試管里面，然后我們的工作就是對(duì)樣品就行污水測(cè)試。

從而線性測(cè)試的成本為O(10000),顯然任務(wù)比較繁重，

而且實(shí)際中有很多工廠還是比較尊守法律，不會(huì)排出污水，

請(qǐng)問(wèn)用什么樣的方法才能簡(jiǎn)化污水的測(cè)試？這里假設(shè)不同工

廠污水之間不發(fā)生化學(xué)反應(yīng)？

36

計(jì)算機(jī)解決問(wèn)題的過(guò)程

?分析階段：弄清所要解決的問(wèn)題是什么，并用一

種語(yǔ)言清楚地描述出來(lái)。

?設(shè)計(jì)階段：建立程序系統(tǒng)的結(jié)構(gòu)，重點(diǎn)是算法的

設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)。

?銅碼階段：采用適當(dāng)?shù)某绦蛟O(shè)計(jì)語(yǔ)言，編寫出可

執(zhí)行的程序。

?測(cè)試和維護(hù)：發(fā)現(xiàn)和排除在前幾個(gè)階段中產(chǎn)生的

錯(cuò)誤，經(jīng)測(cè)試通過(guò)的程序便可投入運(yùn)行，在運(yùn)行

過(guò)程中還可能發(fā)現(xiàn)隱含的錯(cuò)誤和問(wèn)題。

37

多叉路口交通信號(hào)燈的管理：

（一）問(wèn)題分析：首先需要分析一下所有車輛的行駛路線的

沖突問(wèn)題。這個(gè)問(wèn)題可以歸結(jié)為對(duì)車輛的可能行駛方向作某

種分組，對(duì)分組的要求是使任一個(gè)組中各個(gè)方向行駛的車輛

可以同時(shí)安全行駛而不發(fā)生碰撞。

根據(jù)這個(gè)路口的實(shí)際情況可

以確定13個(gè)可能通行方向：

A-B,A-C,A-D,B-A,

B-C,B-D,D-A,D-B,

D-C,E-A,EfB,EfC,

E-D。

圖1.1一個(gè)交叉路口的模型

38

為了敘述方便，我們下面把

A-B簡(jiǎn)寫成AB,并且用一

個(gè)小橢圓把它框起來(lái)，在

不能同時(shí)行駛的路線間畫

一條連線（表示它們互相沖

突），便可以得到圖L2所

圖L1一個(gè)交叉路口的模型示的圖式。

圖1.2交叉路口的圖式模型

這樣做就把要解決的問(wèn)題借助圖的模型變成了另一個(gè)抽象

問(wèn)題：要求將圖1.2中的結(jié)點(diǎn)分組，使有線相連（互相沖突）

的結(jié)點(diǎn)不在同一個(gè)組里。

如果把上圖中的一個(gè)結(jié)點(diǎn)理解為一個(gè)國(guó)家，結(jié)點(diǎn)之間的連

線看作兩國(guó)有共同邊界，上述問(wèn)題就變成著名的“著色問(wèn)

題”：即求出要幾種顏色可將圖中所有國(guó)家著色，使得任

意兩個(gè)相鄰的國(guó)家顏色都不相同。

通過(guò)上面的分析，我們就獲得了該交通管理系統(tǒng)的數(shù)學(xué)模

型：圖

40

圖1.2交叉路口的圖式模型

（二）算法和數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)

?可行解：滿足要求的普通解。

?最優(yōu)解：分組數(shù)最少的解。

?次優(yōu)解：分組數(shù)接近最優(yōu)解的可行解。

?數(shù)據(jù)結(jié)構(gòu)中涉及的算法大致有如下一些：

。窮舉法

。貪心法：如著色問(wèn)題

o分治法：如二分法檢索

?；厮莘ǎ喝缑詫m問(wèn)題

動(dòng)態(tài)規(guī)劃法

41

算法設(shè)計(jì)

算法設(shè)計(jì)

1,對(duì)n個(gè)結(jié)點(diǎn)，逐個(gè)測(cè)試其所有組合；

2.“貪心法”

while有結(jié)點(diǎn)未著色｛

選擇一種新顏色；

在未著色的結(jié)點(diǎn)中，給盡可能多的彼此之間沒(méi)有邊的連

接結(jié)點(diǎn)著色；

42

有些通行方向顯然不能同時(shí)進(jìn)行,相應(yīng)的結(jié)點(diǎn)間畫一條連線。

EC

43

分組結(jié)果

把前述方法應(yīng)用于交叉路口的模型圖，得

到下面的分組：

O綠色：AB,AC,AD,BA,DC,ED

O藍(lán)色：BC,BD,EA

O紅色：DA,DB

O白色：EB,EC

44

（三）編碼

?假設(shè)需要著色的圖是G,集合V1包括圖中所有未被著色的

結(jié)點(diǎn)，著色開(kāi)始時(shí)V1是G所有結(jié)點(diǎn)集合（用G.V表示）。

NEW表示已用新顏色著色的結(jié)點(diǎn)集合。

從V1中找出可用新顏色著色的結(jié)點(diǎn)集的工作可以用下面

的程序框架描述：

置NEW為空集合；

for每個(gè)vGV1do

ifv與NEW中所有結(jié)點(diǎn)間都沒(méi)有邊：

從V1中去掉v;

將v加入NEW;

45

intcolorllp(GraphG)

intcolor=0;

setV1=G.V;/*vi初始化為圖G的結(jié)點(diǎn)集合v*/

setNEW;

while(!isEmpty(V1))

{NEW={}；

while(vGV1.notAdjacentWithSet(NEW,v,G))

add(NEW,v);

remove(V1,v);

++color;

return(color);/*返回使用的顏色數(shù)*/

46

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)要解決的問(wèn)題

?要描述非數(shù)值計(jì)算問(wèn)題，單靠數(shù)學(xué)方程是無(wú)法解決的，它

涉及表、圖、樹(shù)等類的數(shù)據(jù)結(jié)構(gòu)。因此，數(shù)據(jù)結(jié)構(gòu)課是一

門研究小數(shù)值計(jì)算問(wèn)題的程序設(shè)計(jì)中計(jì)算機(jī)的操作對(duì)象以

及它們之間的關(guān)系和運(yùn)算操作等的一門學(xué)科。

?常見(jiàn)的計(jì)算機(jī)語(yǔ)言并不支持圖、樹(shù)、集合等數(shù)據(jù)結(jié)構(gòu)，通

常只提供基本的數(shù)據(jù)類型（整數(shù)、實(shí)數(shù)等）和一些數(shù)據(jù)構(gòu)

造手段（如數(shù)組、結(jié)構(gòu)、指針等）。因此，復(fù)雜數(shù)據(jù)結(jié)構(gòu)

的設(shè)計(jì)以及相應(yīng)的操作必須有用戶自己實(shí)現(xiàn)。

?用計(jì)算機(jī)求解問(wèn)題，首先分析問(wèn)題的需求，抽出抽象模型,

然后設(shè)計(jì)適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和有關(guān)的算法，最后采用計(jì)算機(jī)

編程語(yǔ)言精確地描述所需要的數(shù)據(jù)和算法，實(shí)現(xiàn)程序。

47

第一章緒論

?為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

?數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)《二

?算法與算法評(píng)價(jià)

?總結(jié)

48

基本概念和術(shù)語(yǔ)

?數(shù)據(jù)：指能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息載

體。（數(shù)據(jù)是客觀事物的符號(hào)表示。能輸入到計(jì)算機(jī)中并

被計(jì)算機(jī)程序處理的符號(hào)的總稱。）

?數(shù)據(jù)元素：就是數(shù)據(jù)的基本單位，在某些情況下，數(shù)據(jù)

元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。數(shù)據(jù)元素有時(shí)可

以由若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)

識(shí)單位.

數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素集合，是數(shù)據(jù)的一個(gè)子

編q姓名性別年齡月收入

1李泉男51980

2王怡女47945

3張三男35870

4馬小丁男27840

49

數(shù)據(jù)結(jié)構(gòu)

?沒(méi)有公認(rèn)的定義

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：板照邏輯關(guān)男組織起來(lái)的一

批數(shù)據(jù)，按一定的存儲(chǔ)方避巴它存儲(chǔ)在計(jì)算機(jī)中.并在這些

數(shù)據(jù)上定義了相關(guān)運(yùn)豆的集合.

o一般包括三個(gè)方面的內(nèi)容:數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)

算

「數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的教芨元

素的集合。

”數(shù)據(jù)結(jié)構(gòu)的表示：是指一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)

Wo

數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)：在具體數(shù)據(jù)結(jié)構(gòu)的表示的基礎(chǔ)上各種族

的具體過(guò)程的描述。

50

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)元素之間的邏輯關(guān)系，也稱數(shù)據(jù)的邏輯結(jié)構(gòu)。與數(shù)據(jù)

的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看

作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。

集合線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀或網(wǎng)狀結(jié)構(gòu)

特元素間為松散兀素間為嚴(yán)格元素間為嚴(yán)格的一元素間為多對(duì)多關(guān)系

征的關(guān)系的一封一關(guān)系對(duì)多關(guān)系

示如前面的職工

例一對(duì)多攵祖多對(duì)多

同屬色彩集合表的各元素

?藍(lán)色/北

￡T/合肥一連云港一上海

/\/

攵攵義干

黃色

公路交通網(wǎng)

［集合、線性表、字符串、棧與隊(duì)列、樹(shù)與二叉樹(shù)、字典、圖］51

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

?數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)

的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言

的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語(yǔ)言。

?順序存儲(chǔ)結(jié)構(gòu)、鏈接（鏈狀）存儲(chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、

散列存儲(chǔ)結(jié)構(gòu)。

四種存儲(chǔ)結(jié)構(gòu)既可單獨(dú)使用，又可組合使用

52

順序存儲(chǔ)結(jié)構(gòu)

?順序存儲(chǔ)結(jié)構(gòu)：它是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置

相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接

關(guān)系來(lái)體現(xiàn)。

邏輯地址數(shù)據(jù)元素

鏈接（鏈狀）存儲(chǔ)結(jié)構(gòu)

鏈接（鏈狀）存儲(chǔ)結(jié)構(gòu)：它不要求邏輯上相鄰的結(jié)點(diǎn)在物

理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段

表示的。

存儲(chǔ)地址數(shù)據(jù)域指針域

1Li43

7Qian13

13Sun1

19WangNULL

25Wu37

31Zhao7

37Zheng1954/

43Zhou254

索引存儲(chǔ)結(jié)構(gòu)

?索引存儲(chǔ)結(jié)構(gòu)：除建立

存儲(chǔ)結(jié)點(diǎn)信息外，還建

立附加的索引表來(lái)標(biāo)識(shí)

結(jié)點(diǎn)的地址。

55

散列存儲(chǔ)結(jié)構(gòu)

散列存儲(chǔ)結(jié)構(gòu)：就是根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)

的存儲(chǔ)地址。

假設(shè)以地區(qū)名作關(guān)鍵字，地區(qū)名以漢語(yǔ)拼音的字符表示，

可以取這樣的散列函數(shù)：求關(guān)鍵字的第，個(gè)和最后，個(gè)字

母在字母表中的序號(hào)之利，然后判別這個(gè)值，若比30（表

長(zhǎng)）大，則減去30。

keyB日J(rèn)INTIANJIHEBEISHAXSHANSHANHENASICHU

GN河北NXIGHAIDONGNAN

北京天津山西上海山東河南四川

h2(key)0904172828262203

56

數(shù)據(jù)的運(yùn)算

-數(shù)據(jù)的運(yùn)算

。定義在邏輯結(jié)構(gòu)上的一系列操作以及這些操作在存儲(chǔ)

結(jié)構(gòu)上的實(shí)現(xiàn)；數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，

而具體的實(shí)現(xiàn)是基于存儲(chǔ)結(jié)構(gòu)。

。常用的運(yùn)算：檢索、插入、刪除、定位、修改、排序

等；只是在抽象的數(shù)據(jù)上所施加的一系列抽象的操作。

所謂抽象的操作，是指我們只知道這些操作是“做什

么”，而無(wú)須考慮“如何做”。只有確定了存儲(chǔ)結(jié)構(gòu)之后,

才考慮如何具體實(shí)現(xiàn)這些運(yùn)算。

本課程中討論的各種數(shù)據(jù)結(jié)構(gòu)皆按照三個(gè)方面進(jìn)行：

。邏輯定義（邏輯結(jié)構(gòu)）

。存儲(chǔ)結(jié)構(gòu)及其各種運(yùn)算的實(shí)現(xiàn).

數(shù)據(jù)結(jié)構(gòu)中涉及的主要結(jié)構(gòu)

線性表：線性表中各元素之間是一種簡(jiǎn)單的“線性”關(guān)

系。

順序表和鏈表：是兩種常用的實(shí)現(xiàn)線性表的數(shù)據(jù)結(jié)構(gòu)。

字符串：字符串也是一種特殊的線性結(jié)構(gòu)，它以字符為

元素。

堆棧：堆棧元素的存入和取出按照后進(jìn)先出原則，最先

取出的總是在此之前最后放進(jìn)去的那個(gè)元素；

隊(duì)列：而隊(duì)列實(shí)現(xiàn)先進(jìn)先出的原則，最先到達(dá)的元素也

最先離開(kāi)隊(duì)列。

樹(shù)與二叉樹(shù)：樹(shù)和二叉樹(shù)都屬“樹(shù)形結(jié)構(gòu)”，在邏輯上表

示了結(jié)點(diǎn)的層次關(guān)系。

字典：字典是一種二元組的集合，每個(gè)二元組包含著一個(gè)

關(guān)鍵碼和一個(gè)值。抽象地看，一個(gè)字典就是由關(guān)鍵碼集合

到值集合的一個(gè)映射。按關(guān)鍵碼進(jìn)行檢索是字典中最常用

的操作。

?靜態(tài)字典：有些字典一經(jīng)建立就基本固定不變，主要的操

作就是字典元素的檢索

?動(dòng)態(tài)字典：經(jīng)常需要改動(dòng)的字典稱為“動(dòng)態(tài)字典”

圖：包括一個(gè)結(jié)點(diǎn)集合和一個(gè)邊集合，邊集合中每條邊聯(lián)

系著兩個(gè)結(jié)點(diǎn)。

實(shí)際應(yīng)用：公路網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、不同事物間的聯(lián)系等。59

第一章緒論

?為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

?數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)

?算法與算法評(píng)價(jià)<=

?總結(jié)

60

算法

?算法是對(duì)特定問(wèn)題求解方法和步驟的一種描述，它是指令的

一組有限序列，其中每個(gè)指令表示一個(gè)或多個(gè)操作。

?算法+數(shù)據(jù)結(jié)構(gòu)二程序：揭示了算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系

?算法的五個(gè)重要特性

。輸入：0或多個(gè)外界輸入，初始值

。輸出：一個(gè)或多個(gè)輸出

。有窮性：一個(gè)算法必須總是（對(duì)任何合法輸入值）在執(zhí)

行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成；

。確定性：每條指令有明確的含義，無(wú)二義性，相同的輸

入得到相同結(jié)果

?？尚行裕核惴ū仨毮軋?zhí)行，所有的操作都可以通過(guò)已經(jīng)

實(shí)現(xiàn)了的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。

61

算法的設(shè)計(jì)要求

?解決問(wèn)題：選擇恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)算法，再進(jìn)行

編程實(shí)現(xiàn)。如何設(shè)計(jì)一個(gè)好的算法？

o正確性：經(jīng)得起一切輸入數(shù)據(jù)的考驗(yàn)；能夠正確實(shí)現(xiàn)

預(yù)想的目標(biāo)。

?？勺x性：讓人閱讀得懂，便于交流。注意注釋行的作

用；

健壯性：輸入數(shù)據(jù)錯(cuò)誤時(shí)，進(jìn)行必要的處理。不能得

到莫名其妙的結(jié)果；

。高效率：執(zhí)行時(shí)間盡可能地短，對(duì)存儲(chǔ)要求盡可能地

少，既省時(shí)有節(jié)省空間。

綜合考慮，時(shí)間、空間往往相互抵制，快速往往需要

高存儲(chǔ)要求，低存儲(chǔ)要求往往導(dǎo)致執(zhí)行時(shí)間效率下降。

時(shí)間換空間，空間換時(shí)間…

62