1、單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式第二級第二級第三級第三級第四級第四級第五級第五級1Computer Software Technology計算機(jī)軟件技術(shù)基礎(chǔ)計算機(jī)軟件技術(shù)基礎(chǔ)馮花平馮花平北京工業(yè)大學(xué)耿丹學(xué)院信息工程系北京工業(yè)大學(xué)耿丹學(xué)院信息工程系單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級2Computer Software Technology第第1 1章章 數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)結(jié)構(gòu)基本概念1.1 1.1 什么是數(shù)據(jù)結(jié)構(gòu)

2、什么是數(shù)據(jù)結(jié)構(gòu) 1.2 1.2 基本概念和術(shù)語基本概念和術(shù)語1.3 1.3 算法及其分析算法及其分析單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級3Computer Software Technology3下面文字的含義： 漆黑的頭發(fā)沒有麻子腳不大周正 l演繹 漆黑的頭發(fā)，沒有麻子，腳不大，周正。l結(jié)論：描述一個古代美人！ l演繹 漆黑的頭發(fā)沒有，麻子，腳不大周正。l結(jié)論：描述了一個古代丑女人，還是個瘸子。l結(jié)論 兩個不同的演繹表現(xiàn)為不同的結(jié)果，一個是古代美人，一個確實(shí)古代丑女人，原因只

3、是文字的不同組合造成！l也就是說：相同的文字（數(shù)據(jù)）經(jīng)過不同的組合（結(jié)構(gòu)）會得到也就是說：相同的文字（數(shù)據(jù)）經(jīng)過不同的組合（結(jié)構(gòu)）會得到不同的結(jié)果，這就是我們要介紹的數(shù)據(jù)結(jié)構(gòu)：不同的結(jié)果，這就是我們要介紹的數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)及其之間的關(guān)數(shù)據(jù)及其之間的關(guān)系（結(jié)構(gòu)）。系（結(jié)構(gòu)）。單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級4Computer Software Technology1.1 什么是什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)計算機(jī)解決問題的步驟？計算機(jī)解決問題的步驟？&數(shù)值計算數(shù)值計算解決問題的

4、一般步驟：解決問題的一般步驟： 數(shù)學(xué)模型數(shù)學(xué)模型選擇計算機(jī)語言選擇計算機(jī)語言編出程序編出程序測試測試最終解最終解答。答。 數(shù)值計算的關(guān)鍵是：如何得出數(shù)值計算的關(guān)鍵是：如何得出數(shù)學(xué)模型數(shù)學(xué)模型（方程）？（方程）？ 程序設(shè)計人員比較關(guān)注程序設(shè)計的技巧。程序設(shè)計人員比較關(guān)注程序設(shè)計的技巧。&非數(shù)值計算非數(shù)值計算問題：問題： 數(shù)據(jù)元素之間的相互關(guān)系一般數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程無法用數(shù)學(xué)方程加以描述加以描述諸如表、樹、圖之類的數(shù)據(jù)結(jié)構(gòu)單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級

5、第五級5Computer Software Technology例例1：問題：圖書管理，完成書目的檢索（線性關(guān)系）問題：圖書管理，完成書目的檢索（線性關(guān)系）數(shù)據(jù)：數(shù)據(jù)：各類書籍，更確切地說是每本書的信息，即書名、各類書籍，更確切地說是每本書的信息，即書名、作者、出版社、出版日期、書號、價格、內(nèi)容提要等。作者、出版社、出版日期、書號、價格、內(nèi)容提要等。操作：操作：書目入庫、查詢、借書、還書書目入庫、查詢、借書、還書非數(shù)值計算問題非數(shù)值計算問題3個引例個引例書目自動檢索系統(tǒng)的數(shù)學(xué)模型書目自動檢索系統(tǒng)的數(shù)學(xué)模型001高等數(shù)學(xué)樊映川S01002理論力學(xué)羅遠(yuǎn)祥L01003高等數(shù)學(xué)華羅庚S01004線性代

6、數(shù)欒汝書S02書目文件按書名按作者名按分類號高等數(shù)學(xué)001，003理論力學(xué)002，.線性代數(shù)004，.L002,S001,003,索引表線性表例例2：人機(jī)對奕問題的數(shù)學(xué)模型（樹結(jié)構(gòu)）：人機(jī)對奕問題的數(shù)學(xué)模型（樹結(jié)構(gòu)）樹樹.問題：問題：人機(jī)對弈，即人與計算機(jī)下棋人機(jī)對弈，即人與計算機(jī)下棋數(shù)據(jù)：數(shù)據(jù)：各種棋局狀態(tài)，確切地說是描述棋盤格局各種棋局狀態(tài)，確切地說是描述棋盤格局的信息。的信息。操作：操作：走棋，即選擇一種策略使棋局狀態(tài)發(fā)生變走棋，即選擇一種策略使棋局狀態(tài)發(fā)生變化（由一個格局派生出另一個格局）化（由一個格局派生出另一個格局）單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版

7、文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級7Computer Software TechnologyCEDABABACADBABCBDDADBDCEAEBECED圖例例3：多叉路口的交通燈管理問題的數(shù)學(xué)模型：多叉路口的交通燈管理問題的數(shù)學(xué)模型問題：問題：多叉路口的交通燈管理，即在多叉路程口多叉路口的交通燈管理，即在多叉路程口設(shè)置幾種顏色的交通燈，以保證交通暢通。設(shè)置幾種顏色的交通燈，以保證交通暢通。數(shù)據(jù)：數(shù)據(jù)：路口各條路的信息。路口各條路的信息。操作：操作：設(shè)置信號燈（求出各個可同時通行的路的設(shè)置信號燈（求出各個可同時通行的路的集合。集合。單擊此處

8、編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級8Computer Software Technology&求求解非數(shù)值計算的問題：解非數(shù)值計算的問題： 主要考慮的是設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相主要考慮的是設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。應(yīng)的算法。 即：首先要考慮即：首先要考慮對相關(guān)的各種信息如何表對相關(guān)的各種信息如何表示、組織和存儲？示、組織和存儲？ 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作計問題中計算機(jī)的操作對象對象以及它們之間以及它們

9、之間的的關(guān)系關(guān)系和和操作操作的學(xué)科。的學(xué)科。單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級9Computer Software Technology 程序設(shè)計：程序設(shè)計：為計算機(jī)處理問題編制一組為計算機(jī)處理問題編制一組指令集。指令集。 算法：算法：處理問題的策略。處理問題的策略。 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：問題的數(shù)學(xué)模型。問題的數(shù)學(xué)模型。Niklaus Wirth1.1 什么是什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)Algorithm+DataStructures=Programs算法算法+ +數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)

10、= =程序程序單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級10Computer Software Technology基本概念和術(shù)語基本概念和術(shù)語1.2.1基本概念基本概念數(shù)據(jù)（數(shù)據(jù)（data）：）： 數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機(jī)中并及所有能輸入到計算機(jī)中并被計算機(jī)程序識別和處理被計算機(jī)程序識別和處理的符號的集合的符號的集合, , 是計算機(jī)程序加工的是計算機(jī)程序加工的”原料原料”。 分類：分類： 數(shù)值性

11、數(shù)據(jù)數(shù)值性數(shù)據(jù) 非數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級11Computer Software Technology2、數(shù)據(jù)元素（、數(shù)據(jù)元素（data element）數(shù)據(jù)的數(shù)據(jù)的基本單位。基本單位。在計算機(jī)程序在計算機(jī)程序中常作為一個整體進(jìn)行考慮和處中常作為一個整體進(jìn)行考慮和處理。有時理。有時一個數(shù)據(jù)元素可以由若一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項干數(shù)據(jù)項(Data Item)(Data Item)組成。組成。數(shù)據(jù)項數(shù)據(jù)項是數(shù)據(jù)不可分割的最小標(biāo)是數(shù)據(jù)不可分割的最小

12、標(biāo)識單位。識單位。數(shù)據(jù)元素數(shù)據(jù)元素又稱為又稱為元素元素、結(jié)點(diǎn)結(jié)點(diǎn)、頂頂點(diǎn)點(diǎn)、記錄。記錄。學(xué)號學(xué)號姓名姓名成績成績001LiLy89002Yang98003Zhao78單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級12Computer Software Technology數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項的區(qū)別：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項的區(qū)別：數(shù)據(jù)數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)項實(shí)數(shù)集實(shí)數(shù)集單個實(shí)數(shù)單個實(shí)數(shù)單個實(shí)數(shù)（不可再分）單個實(shí)數(shù)（不可再分）復(fù)數(shù)集復(fù)數(shù)集單個復(fù)數(shù)單個復(fù)數(shù)實(shí)部，虛部實(shí)部，虛部職工信息

13、職工信息 單個職工記錄單個職工記錄 多個數(shù)據(jù)項（姓名、年多個數(shù)據(jù)項（姓名、年齡、齡、）單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級13Computer Software Technology3、數(shù)據(jù)對象（、數(shù)據(jù)對象（data object）l數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。u整數(shù)數(shù)據(jù)對象整數(shù)數(shù)據(jù)對象 N = 0, 1, 2, u字母字符數(shù)據(jù)對象字母字符數(shù)據(jù)對象 C=A，B，Zu學(xué)生成績數(shù)據(jù)對象學(xué)生成績數(shù)據(jù)對象Cj=（101，jane，80

14、），）， （ 102，jack，90 ），）， （ 103，jerry，75 ）單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級14Computer Software Technology4、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)(data structure) 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。的數(shù)據(jù)元素的集合。 在任何問題中，數(shù)據(jù)元素都不是孤立存在的，在任何問題中，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關(guān)系，這種數(shù)據(jù)元而是在它們之

15、間存在著某種關(guān)系，這種數(shù)據(jù)元素相互之間的素相互之間的關(guān)系關(guān)系稱為稱為結(jié)構(gòu)結(jié)構(gòu)(Structure)。 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間是一堆數(shù)據(jù)元素和這些數(shù)據(jù)元素之間的關(guān)系的總和。的關(guān)系的總和。單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級15Computer Software Technology 按數(shù)據(jù)元素之間關(guān)系的不同特性，通常有按數(shù)據(jù)元素之間關(guān)系的不同特性，通常有4類類基本結(jié)構(gòu)基本結(jié)構(gòu)（1）集合）集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個集同屬于一

16、個集合合”外，別無其它關(guān)系。外，別無其它關(guān)系。（2）線性結(jié)構(gòu)）線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。的關(guān)系。（3）樹型結(jié)構(gòu)）樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。的關(guān)系。（4）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)）圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。存在多對多的關(guān)系。14131211234567891031587101199874566231311152436單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級

17、第四級 第五級第五級16Computer Software Technology數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)的形式定義用一個二元組表示，記為：用一個二元組表示，記為： Data_Structure = （D, S） 其中，其中，D 是數(shù)據(jù)元素的有限集（即一個數(shù)據(jù)是數(shù)據(jù)元素的有限集（即一個數(shù)據(jù) 對象），對象），S 是該對象中所有數(shù)據(jù)成員之間的關(guān)是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。系的有限集合。在計算機(jī)科學(xué)中，對復(fù)數(shù)的定義：復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)在計算機(jī)科學(xué)中，對復(fù)數(shù)的定義：復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)Complex=(C,R)其中：其中：C是包含兩個實(shí)數(shù)的集合是包含兩個實(shí)數(shù)的集合 C1, C2 ,R=P

18、,P是定義在是定義在C上的一種關(guān)系上的一種關(guān)系 。單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級17Computer Software Technology5、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從從邏輯關(guān)系邏輯關(guān)系上描述數(shù)據(jù)，可以上描述數(shù)據(jù)，可以看作是從具體問題抽象出來的看作是從具體問題抽象出來的數(shù)據(jù)模型數(shù)據(jù)模型，與數(shù)，與數(shù)據(jù)的存儲無關(guān)，也與數(shù)據(jù)元素本身的形式、內(nèi)據(jù)的存儲無關(guān)，也與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置無關(guān)；容、相對位置無關(guān)； 數(shù)據(jù)的邏輯結(jié)構(gòu)分類數(shù)據(jù)

19、的邏輯結(jié)構(gòu)分類：線性結(jié)構(gòu)線性結(jié)構(gòu) 線性表、棧、隊列線性表、棧、隊列 、串、串非線性結(jié)構(gòu)非線性結(jié)構(gòu) 樹樹 、圖（或網(wǎng)絡(luò)）、圖（或網(wǎng)絡(luò)）單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級18Computer Software Technology6、數(shù)據(jù)的存儲結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示計算機(jī)中的表示( (或稱映象）或稱映象）稱為稱為數(shù)據(jù)的存儲結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。它包括它包括數(shù)數(shù)據(jù)元素的表示據(jù)元素的表示和和關(guān)系的表示關(guān)系的表示。（1）

20、數(shù)據(jù)元素的表示：位、字長、元素、結(jié)點(diǎn)、數(shù)）數(shù)據(jù)元素的表示：位、字長、元素、結(jié)點(diǎn)、數(shù)據(jù)域據(jù)域（2）關(guān)系的表示）關(guān)系的表示兩種基本的存儲方法：兩種基本的存儲方法：順序映像（順序存儲結(jié)構(gòu)）順序映像（順序存儲結(jié)構(gòu)）非順序映像（鏈?zhǔn)酱鎯Y(jié)構(gòu)）非順序映像（鏈?zhǔn)酱鎯Y(jié)構(gòu)） 算法設(shè)計算法設(shè)計邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)算法實(shí)現(xiàn)算法實(shí)現(xiàn)存儲結(jié)構(gòu)存儲結(jié)構(gòu)單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級19Computer Software Technology19 借助數(shù)據(jù)元素在存儲器中的相對位置來表示借助數(shù)據(jù)元素在存儲

21、器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)元素之間的邏輯關(guān)系。 所有元素存放在一片所有元素存放在一片連續(xù)的存貯單元連續(xù)的存貯單元中，中，邏邏輯上相鄰的元素存放到計算機(jī)內(nèi)仍然相鄰。輯上相鄰的元素存放到計算機(jī)內(nèi)仍然相鄰。 把必要的數(shù)據(jù)元素存儲在存儲單元中后，通過把必要的數(shù)據(jù)元素存儲在存儲單元中后，通過對存儲單元的對存儲單元的地址進(jìn)行一個固定的計算地址進(jìn)行一個固定的計算就能直接就能直接表達(dá)數(shù)據(jù)元素之間邏輯上的關(guān)系的物理結(jié)構(gòu)。表達(dá)數(shù)據(jù)元素之間邏輯上的關(guān)系的物理結(jié)構(gòu)。 順序存儲結(jié)構(gòu)（順序存儲結(jié)構(gòu)（sequential storage structure）單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題

22、樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級20Computer Software Technology20元素n.元素i.元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Lo(元素i)=Lo+（i-1)*m 例如例如: : 順序存儲順序存儲設(shè)一個元素占設(shè)一個元素占m個字節(jié)，則個字節(jié)，則n 個元個元素順序存儲在內(nèi)素順序存儲在內(nèi)存中的映象如右存中的映象如右圖。圖。如果知道了第如果知道了第1個個元素的首地址，元素的首地址，則可直接則可直接計算計算出出第第i個元素的地址個元素的地址。單擊此處編輯母版標(biāo)題

23、樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級21Computer Software Technology21鏈?zhǔn)酱鎯Y(jié)構(gòu)（鏈?zhǔn)酱鎯Y(jié)構(gòu)（linked storage structure） 把數(shù)據(jù)元素存儲在把數(shù)據(jù)元素存儲在附設(shè)了指針域的存儲單元附設(shè)了指針域的存儲單元中，通過中，通過指針域的值指針域的值來表達(dá)數(shù)據(jù)元素之間邏輯上來表達(dá)數(shù)據(jù)元素之間邏輯上的關(guān)系的物理結(jié)構(gòu)。的關(guān)系的物理結(jié)構(gòu)。 所有元素存放在可以所有元素存放在可以不連續(xù)的存貯單元不連續(xù)的存貯單元中，中，但元素之間的關(guān)系可以通過但元素之間的關(guān)系可以通過

24、地址（指針）地址（指針）確定，確定，邏輯上相鄰的元素存放到計算機(jī)內(nèi)存后不一定是邏輯上相鄰的元素存放到計算機(jī)內(nèi)存后不一定是相鄰的。相鄰的。單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級22Computer Software Technology221536元素21400元素11346元素3 元素41345存儲地址存儲地址 存儲內(nèi)容存儲內(nèi)容 指針指針 1345 1345 元素元素1 1 1400 1400 1346 1346 元素元素4 4 . . . . . 1400 1400 元素元素2

25、 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 例如例如: : 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?h單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級23Computer Software Technology23 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲順序存儲 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表棧棧隊隊樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)單擊此處編輯母版標(biāo)題樣式單擊此處編輯母

26、版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級24Computer Software Technology 算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系非常密切，在算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系非常密切，在算法設(shè)計算法設(shè)計時先要時先要確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)確定相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，而，而在討論在討論某一種數(shù)據(jù)結(jié)構(gòu)某一種數(shù)據(jù)結(jié)構(gòu)時時也必然會涉及相也必然會涉及相應(yīng)的算法。應(yīng)的算法。 算法的特性與設(shè)計要求算法的特性與設(shè)計要求 算法效率的度量算法效率的度量 1.3 算法和算法分析算法和算法分析單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編

27、輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級25Computer Software Technology1.3 算法和算法分析算法和算法分析 算法的定義：是對算法的定義：是對特定問題求解步驟特定問題求解步驟的一種描的一種描述述, ,是一個是一個有窮的指令集有窮的指令集，這些指令表示一個，這些指令表示一個或多個操作。或多個操作。 算法的特性算法的特性( (要素要素) )：有窮性有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束算法應(yīng)在執(zhí)行有窮步后結(jié)束, ,且每一步都在有窮時間且每一步都在有窮時間內(nèi)完成內(nèi)完成確定性確定性 每步定義都是確切、無歧義的每步定義都是確切、無歧義的可行性可行性 算

28、法中描述的操作應(yīng)能通過執(zhí)行有限次已經(jīng)實(shí)現(xiàn)的算法中描述的操作應(yīng)能通過執(zhí)行有限次已經(jīng)實(shí)現(xiàn)的基本運(yùn)算而實(shí)現(xiàn)基本運(yùn)算而實(shí)現(xiàn)輸入輸入 有有0 0個或多個輸入個或多個輸入輸出輸出 有一個或多個輸出有一個或多個輸出( (處理結(jié)果處理結(jié)果) )。單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級26Computer Software Technology算法設(shè)計的要求算法設(shè)計的要求 正確性：正確性：不含有語法錯誤；對于各種合法的輸不含有語法錯誤；對于各種合法的輸入數(shù)據(jù)能夠得到滿足規(guī)格說明要求的結(jié)果。入數(shù)據(jù)能

29、夠得到滿足規(guī)格說明要求的結(jié)果。 可讀性：可讀性：要求程序有較好的人機(jī)交互性要求程序有較好的人機(jī)交互性,有助有助于人們對算法的理解。于人們對算法的理解。 健壯性：健壯性：對輸入的非法數(shù)據(jù)能作出適當(dāng)?shù)捻憫?yīng)對輸入的非法數(shù)據(jù)能作出適當(dāng)?shù)捻憫?yīng)或處理。或處理。 效率與低存儲需求：效率與低存儲需求：主要指算法的執(zhí)行時間和主要指算法的執(zhí)行時間和所需的最大存儲空間，這兩方面主要和問題的所需的最大存儲空間，這兩方面主要和問題的規(guī)模有關(guān)。規(guī)模有關(guān)。單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級27Comput

30、er Software Technology27 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 順序存儲順序存儲 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表棧棧隊隊樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個方面：數(shù)據(jù)結(jié)構(gòu)的三個方面：單擊此處編輯母版標(biāo)題樣式單擊此處編輯母版標(biāo)題樣式 單擊此處編輯母版文本樣式單擊此處編輯母版文本樣式 第二級第二級 第三級第三級 第四級第四級 第五級第五級28Computer Software Technology本章小結(jié)本章小結(jié) 與數(shù)據(jù)結(jié)構(gòu)相關(guān)的幾個名詞概念與數(shù)據(jù)結(jié)構(gòu)相關(guān)的幾個名詞概念 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容： 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)）數(shù)據(jù)的物理結(jié)構(gòu)（存儲結(jié)構(gòu)） 在數(shù)據(jù)結(jié)構(gòu)上的操作在數(shù)據(jù)結(jié)構(gòu)上的操作 了解算法分析