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

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

F王昭

北京大學信息學院軟件研究所

wangzhao@

內(nèi)容提要

?課程簡介

第一章緒論

2

為什么要學習該課程

?學分

?畢業(yè)

3

學兄、學姐的體會

?學兄、學姐的體會

4

一堂讓人變得更聰明的課

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

庫。

?要變得聰明一些，就要學會選擇適當?shù)慕嵌?/p>

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

寸口7

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

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

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

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

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

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

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

一起的實體或某些成分組織在一起的方式

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

?算法

?是對特定問題求解方法和步驟的一種描述。

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

O一元二次方程的求解

。圓周長、圓面積

。立方體的表面積和邊長

。排序

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

7

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

NikiklausWirth

?程序：為計算機解決問題編制的指令集，是按照

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

?從程序設(shè)計的觀點來看，

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

。信息的處理：“算法”研究的問題

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

8

課程目標

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

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

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

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

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

9

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

人工智能

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

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

索引、檢索J空間索引樹.檢索

一小~~工

「操作系統(tǒng)

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

線性表、多鏈表、隊列、存儲管理表、

字符申、棧、

排序、B+索引用\排芹、目錄樹」1

列表、語法樹

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

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

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

程序設(shè)計實習

集合論與國

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

建議的學習方案

?聽課，思考，提問，討論

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

O學而不思則罔，思而不學則殆

。不恥下問

。獨學而無友則孤陋而寡聞

?上機

紙上得來終覺淺，絕知此事要躬行

聽懂很容易，學會才是真

11

教學方式

?課堂講授：3學時/周

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

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

?上機實踐：2學時/周，

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

(從上課起第3周開始)

12

課件位置

?課件位置

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

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

Ohttn:〃/~wangzhao/

?開設(shè)課程

13

教材和參考書

?教材：

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

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

參考書：

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

答）嚴蔚敏等，清華大學出版社

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

題），網(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++語言描述）第2

版,清華大學出版社,2007年6月。

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

2007年11月。

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

,2006年1月。

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

,2007年7月。15

課程資源

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

/2004/09/30/0000022031.html

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

/2004/10/01/0000022112.html

?北大計算機系課程資源（包含課程的視頻C++語言）

http:〃/pkuipk/course/siig/

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

http:〃ipkc.nwu./datastr/

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

16

成績考核

“學生成績二平時成績（50%）+期末考試成績（50%）”

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

平時成績50%，隨堂測驗+考勤10%（由助教負責）

上機20%

期末考試成績50%

注重綜合能力的考評，平時表現(xiàn)突出、上機能力較強的

（如完成附加題）可以得到獎勵加分，不超過5分。

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

以下）不超過15%?！?/p>

作業(yè)要求

?書面作業(yè)

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

上機作業(yè)

程序編寫

程序調(diào)試

運行結(jié)果

□做什么

輔導(dǎo)教員檢查

□怎么做

上機報告

□結(jié)果

□體會與收獲

18

上機安排

?上機時間

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

?上機地點：

計算中心機房：號機房(理科1號樓2層)

?輔導(dǎo)老師：

孫'聰：suncong.pku@

冀康：jikang1985@

蔣星博：jiangxb1987@

杜龍志：dlz@

19

上機要求

?上機環(huán)境

VC++6.0

?要求

c認真準備，有備而來；

O嚴禁玩游戲；

O及時向輔導(dǎo)老師反映問題；

。培養(yǎng)獨立解決問題的能力O

20

答疑安排

?平時有疑問請在課下及時解決，如有問題

發(fā)郵件

?考試前安排『2次答疑時間

?有何意見及建議請及時反映

21

內(nèi)容提要

?課程簡介

?第一章緒論

22

第一章緒論

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

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

?算法與算法評價

?總結(jié)

23

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

?對于數(shù)值計算問題，處理的對象為簡單的

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

對于非數(shù)值計算問題（如資料查詢、交通

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

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

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

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

24

非數(shù)值計算問題分析

?信息管理（圖書、檔案、職工等）

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

關(guān)鍵：

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

法問題）

25

些問題

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

蘭州、重慶、濟南、石家莊、青島、廣州、沈陽。

水污染嚴重的城市有：臨汾、陽泉、大同、石嘴

山、三門峽、金昌、石家莊、重慶、株洲和洛陽。

列出空氣污染嚴重或水污染嚴重的城市（集合的

并）。

26

西薇巨柏XX么"貢

氏葉松XX公頃

白皮松XXO1頁

云杉XX公頃

冷杉XX公頃

鐵杉XX公頃

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

某年我國的野生銀杉XX公匕頁

銀杏XX公匕頁

植物保護情況。水杉XX公頃

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

冷杉XX公頃

珍稀野生植物的紅杉XX公4頁

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

連香樹XX公頃

計各種野生植物湖南銀杉XX公頃

在我國總的種植水杉XX公L頁

云杉XX公頃

金錢松XX公頃

伯樂樹X2K公H更

連香樹XX公匕頁

莢囊蹂XX公頃

27

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

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

排名城市GDP及增氏排名城市GDP及增長

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沈陽2483+16.5%

06杭州3441+14.3%06煙臺2402+17.0%

073360+15.0%07唐山2362+11.8%

08佛山29274-19.3%08濟南2185+15.7%

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

1U南樂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長沙1791+14.8%16濟寧1156+16.5%

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

18紹興1678+13.2%18東營1150+17.0%

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

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

線性表問題

每人一個記錄，多個數(shù)據(jù)項;

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

如何存儲？

什么樣的操作？

（統(tǒng)計、檢索問題）

編號姓名性別年齡月收入

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)如下圖所示。找出對山獅的生

存有影響的動物。

31

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

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

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

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

已保存地址?登錄?都助

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

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

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

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

———二S

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

a北五環(huán)

翹.

臼駕駛219公里

1進入天壇路向東南232米

.025?

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

西環(huán)

?*.i

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

環(huán)

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

5靠左進入西直門北大街向北29公里?朝陽公園

?北京:策

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

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

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

五

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

阡

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

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

金苑

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

大學修改

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

示結(jié)果.

32

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

@InternetO?、100%

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

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

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

33

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

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

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

能鏈接，并且成本最??？

烏魯木齊長春

呼和浩？北京

平壤

銀川

濟南

西寧?蘭州

西安

合肥

武漢杭州

不丹

釣魚島

臺北

澳門&香港

非線性問題

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

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

如何存儲？

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

北京

1、天津,

659

鄭州徐州

349

651

9

武漢

上海

1

890

101650>

2

廣州福州

35

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

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

標號的試管里面，然后我們的工作就是對樣品就行污水測試。

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

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

請問用什么樣的方法才能簡化污水的測試？這里假設(shè)不同工

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

36

計算機解決問題的過程

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

種語言清楚地描述出來。

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

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

?銅碼階段：采用適當?shù)某绦蛟O(shè)計語言，編寫出可

執(zhí)行的程序。

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

錯誤，經(jīng)測試通過的程序便可投入運行，在運行

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

37

多叉路口交通信號燈的管理：

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

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

種分組，對分組的要求是使任一個組中各個方向行駛的車輛

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

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

以確定13個可能通行方向：

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一個交叉路口的模型

38

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

A-B簡寫成AB,并且用一

個小橢圓把它框起來，在

不能同時行駛的路線間畫

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

突），便可以得到圖L2所

圖L1一個交叉路口的模型示的圖式。

圖1.2交叉路口的圖式模型

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

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

的結(jié)點不在同一個組里。

如果把上圖中的一個結(jié)點理解為一個國家，結(jié)點之間的連

線看作兩國有共同邊界，上述問題就變成著名的“著色問

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

意兩個相鄰的國家顏色都不相同。

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

型：圖

40

圖1.2交叉路口的圖式模型

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

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

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

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

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

。窮舉法

。貪心法：如著色問題

o分治法：如二分法檢索

?；厮莘ǎ喝缑詫m問題

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

41

算法設(shè)計

算法設(shè)計

1,對n個結(jié)點，逐個測試其所有組合；

2.“貪心法”

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

選擇一種新顏色；

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

接結(jié)點著色；

42

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

EC

43

分組結(jié)果

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

到下面的分組：

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

O藍色：BC,BD,EA

O紅色：DA,DB

O白色：EB,EC

44

（三）編碼

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

結(jié)點，著色開始時V1是G所有結(jié)點集合（用G.V表示）。

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

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

的程序框架描述：

置NEW為空集合；

for每個vGV1do

ifv與NEW中所有結(jié)點間都沒有邊：

從V1中去掉v;

將v加入NEW;

45

intcolorllp(GraphG)

intcolor=0;

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

setNEW;

while(!isEmpty(V1))

{NEW={}；

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

add(NEW,v);

remove(V1,v);

++color;

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

46

學習數(shù)據(jù)結(jié)構(gòu)要解決的問題

?要描述非數(shù)值計算問題，單靠數(shù)學方程是無法解決的，它

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

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

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

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

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

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

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

?用計算機求解問題，首先分析問題的需求，抽出抽象模型,

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

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

47

第一章緒論

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

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

?算法與算法評價

?總結(jié)

48

基本概念和術(shù)語

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

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

被計算機程序處理的符號的總稱。）

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

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

以由若干數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標

識單位.

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

編q姓名性別年齡月收入

1李泉男51980

2王怡女47945

3張三男35870

4馬小丁男27840

49

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

?沒有公認的定義

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

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

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

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

算

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

素的集合。

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

Wo

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

的具體過程的描述。

50

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

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

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

作是從具體問題抽象出來的數(shù)學模型。

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

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

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

示如前面的職工

例一對多攵祖多對多

同屬色彩集合表的各元素

?藍色/北

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

/\/

攵攵義干

黃色

公路交通網(wǎng)

［集合、線性表、字符串、棧與隊列、樹與二叉樹、字典、圖］51

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

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

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

的實現(xiàn)，它依賴于計算機語言。

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

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

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

52

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

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

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

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

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

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

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

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

表示的。

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

1Li43

7Qian13

13Sun1

19WangNULL

25Wu37

31Zhao7

37Zheng1954/

43Zhou254

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

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

存儲結(jié)點信息外，還建

立附加的索引表來標識

結(jié)點的地址。

55

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

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

的存儲地址。

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

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

母在字母表中的序號之利，然后判別這個值，若比30（表

長）大，則減去30。

keyB日JINTIANJIHEBEISHAXSHANSHANHENASICHU

GN河北NXIGHAIDONGNAN

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

h2(key)0904172828262203

56

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

系。

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

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

元素。

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

取出的總是在此之前最后放進去的那個元素；

隊列：而隊列實現(xiàn)先進先出的原則，最先到達的元素也

最先離開隊列。

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

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

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

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

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

的操作。

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

作就是字典元素的檢索

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

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

系著兩個結(jié)點。

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

第一章緒論

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

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

?算法與算法評價<=

?總結(jié)

60

算法

?算法是對特定問題求解方法和步驟的一種描述，它是指令的

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

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

?算法的五個重要特性

。輸入：0或多個外界輸入，初始值

。輸出：一個或多個輸出

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

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

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

入得到相同結(jié)果

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

實現(xiàn)了的基本運算執(zhí)行有限次來實現(xiàn)。

61

算法的設(shè)計要求

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

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

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

預(yù)想的目標。

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

用；

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

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

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

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

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

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

時間換空間，空間換時間…

62