數(shù)據(jù)結(jié)構(gòu)講義完整版

1、第一章 緒論p學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義p基本概念和術(shù)語(yǔ)p算法的描述和分析1.1 什么是數(shù)據(jù)結(jié)構(gòu)p圖書(shū)的基本信息登記號(hào)，書(shū)名，作者，分類(lèi)編號(hào)，出版單位，出版時(shí)間登記號(hào)，書(shū)名，作者，分類(lèi)編號(hào)，出版單位，出版時(shí)間作者簡(jiǎn)介，內(nèi)容簡(jiǎn)介，等等。作者簡(jiǎn)介，內(nèi)容簡(jiǎn)介，等等。p操作檢索，排序，等等檢索，排序，等等p數(shù)據(jù)之間的關(guān)系線性關(guān)系線性關(guān)系p數(shù)據(jù)表示和算法操作的設(shè)計(jì)與需求有關(guān)與需求有關(guān)p數(shù)據(jù)的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，算法操作n邏輯結(jié)構(gòu)是客觀事物特性的一種抽象邏輯結(jié)構(gòu)是客觀事物特性的一種抽象n存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的計(jì)算機(jī)實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的計(jì)算機(jī)實(shí)現(xiàn)n算法操作是基于存儲(chǔ)結(jié)構(gòu)的操作，反映客觀事物的變化算法操作是基于存儲(chǔ)

2、結(jié)構(gòu)的操作，反映客觀事物的變化p如何表示一個(gè)棋局p數(shù)據(jù)之間的邏輯結(jié)構(gòu)表示棋局之間的演化關(guān)系 樹(shù)型結(jié)構(gòu)p算法如何設(shè)計(jì)基于數(shù)據(jù)表示的基礎(chǔ)上算法設(shè)計(jì)邏輯結(jié)構(gòu)：圖狀結(jié)構(gòu)p研究和解決非數(shù)值數(shù)據(jù)的組織和處理研究和解決非數(shù)值數(shù)據(jù)的組織和處理n描述非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型，不再是數(shù)學(xué)方程n例如：前述的三個(gè)例子：數(shù)據(jù)的線性結(jié)構(gòu)，樹(shù)型結(jié)構(gòu)，圖p算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)=程序程序n算法和數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系n軟件系統(tǒng)的框架應(yīng)當(dāng)建立在數(shù)據(jù)之上，而不是建立在操作之上p數(shù)據(jù)結(jié)構(gòu)的作用范疇數(shù)據(jù)結(jié)構(gòu)的作用范疇n抽象數(shù)據(jù)對(duì)象的數(shù)學(xué)模型（邏輯結(jié)構(gòu)）例：圖狀結(jié)構(gòu)n明確操作（運(yùn)算的定義） 例：查找、插入、n在存儲(chǔ)結(jié)構(gòu)上映射數(shù)據(jù)（存儲(chǔ)

3、結(jié)構(gòu)） 例：順序存儲(chǔ)n實(shí)現(xiàn)操作 p1968年斯坦福的Knuth教授開(kāi)創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，在他所著的計(jì)算機(jī)程序設(shè)計(jì)技巧第一卷基本算法中第一次較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作。 Donald Ervin Knuth The Art of Computer Programming Art Evansp數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中是一門(mén)綜合性的專(zhuān)業(yè)基礎(chǔ)課，也是計(jì)算機(jī)專(zhuān)業(yè)的必修課，是其它許多課程的先修課程，是設(shè)計(jì)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)等系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。1.2 基本概念和術(shù)語(yǔ)p數(shù)據(jù)數(shù)據(jù) 被計(jì)算機(jī)加工處理的對(duì)象。p數(shù)據(jù)元素?cái)?shù)據(jù)元素（記錄記錄、表目表目） 數(shù)據(jù)的基本單位，

4、是數(shù)據(jù)集合中的一個(gè)有意義的個(gè)體。p數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) 一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)組成。 組合項(xiàng)組合項(xiàng)年 月 日學(xué) 號(hào)姓 名班 號(hào)性別出生日期入學(xué)成績(jī)?cè)禹?xiàng)原子項(xiàng)p數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。 學(xué)號(hào) 姓名 班號(hào) 性別 出生日期 入學(xué)成績(jī) 001 劉影 01 女 19840417 623 002 李恒 01 男 19831211 679 003 陳誠(chéng) 02 男 19840910 638 p數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。它包括數(shù)據(jù)元素的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)和相適應(yīng)的運(yùn)算。數(shù)據(jù)元素 數(shù)據(jù)元素之間的邏輯關(guān)系，與計(jì)算機(jī)無(wú)關(guān)。 可用一個(gè)二元組

5、表示：Data_Structure = (D,R) D：數(shù)據(jù)元素的有窮集合，R：集合D上關(guān)系的有窮集合。 例例 設(shè)有數(shù)據(jù)結(jié)構(gòu) B = (D,R) ， 其中 D= d1, d2, d3, d4, d5, d6， R=r， r=, , , , ， 試畫(huà)出其邏輯結(jié)構(gòu)圖。 d1d2 d3 d4d5 d6（以班級(jí)學(xué)生關(guān)系為例）(1)集合結(jié)構(gòu)集合結(jié)構(gòu) 數(shù)據(jù)元素除了“屬于同一集合”的聯(lián)系之外，沒(méi)有其它的關(guān)系。(2)線性結(jié)構(gòu)線性結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。(3)樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu) 數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。(4)圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。成員關(guān)系長(zhǎng)幼關(guān)系管理關(guān)

6、系朋友關(guān)系存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中如何表示。p數(shù)據(jù)元素的映象數(shù)據(jù)元素的映象 用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素。 每個(gè)數(shù)據(jù)元素的映象稱(chēng)為每個(gè)數(shù)據(jù)元素的映象稱(chēng)為結(jié)點(diǎn)結(jié)點(diǎn) 每個(gè)數(shù)據(jù)項(xiàng)的映象稱(chēng)為每個(gè)數(shù)據(jù)項(xiàng)的映象稱(chēng)為數(shù)據(jù)域數(shù)據(jù)域p關(guān)系的映象關(guān)系的映象兩種基本方法及其組合使用。兩種基本方法及其組合使用。n順序映象順序映象：以相對(duì)的存儲(chǔ)位置表示關(guān)系以相對(duì)的存儲(chǔ)位置表示關(guān)系n鏈?zhǔn)接诚箧準(zhǔn)接诚螅阂愿郊有畔ⅲ阂愿郊有畔? (指針指針) )表示關(guān)系表示關(guān)系在不同的編程環(huán)境下，存儲(chǔ)結(jié)構(gòu)有不同的描述方式。用高級(jí)程序語(yǔ)言編程時(shí)，直接用其提供的數(shù)據(jù)類(lèi)型描述。(1)順序存儲(chǔ)順序存儲(chǔ)：數(shù)據(jù)元素依次放在連

7、續(xù)的存儲(chǔ)單元中。 a1 a2 . ai . an (2)鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)：在存儲(chǔ)結(jié)點(diǎn)中增加若干指針域，記錄后繼或者相關(guān)結(jié)點(diǎn)的地址（指針）。 a1 1220 . a3 1342 . a21072 .1000 1004 1000 1004 1072 1076 1220 1224指針結(jié)點(diǎn)結(jié)點(diǎn)運(yùn)算運(yùn)算（操作操作）：在數(shù)據(jù)邏輯結(jié)構(gòu)上定義的一組數(shù)據(jù)被使用的方式，其具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。幾種常用的運(yùn)算有： (1)建立數(shù)據(jù)結(jié)構(gòu) (6)檢索* (2)清除數(shù)據(jù)結(jié)構(gòu) (7)更新 (3)插入數(shù)據(jù)元素 (8)判空和判滿* (4)刪除數(shù)據(jù)元素 (9)求長(zhǎng)* (5)排序 *操作為引用型操作引用型操作，即數(shù)據(jù)值不發(fā)生變

8、化； 其它為加工型操作加工型操作。抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型 ADT（ Abstract Data Type Abstract Data Type ）： 數(shù)據(jù)類(lèi)型概念的引伸。指一個(gè)數(shù)學(xué)模型數(shù)學(xué)模型以及在其上定義的操作集操作集合合，與計(jì)算機(jī)無(wú)關(guān)。 數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型：一組值的集合和定義在其上的一組操作的總稱(chēng)。ADT的特點(diǎn)的特點(diǎn)：將它的使用和實(shí)現(xiàn)分離，提高軟件復(fù)用程度。 原子類(lèi)型 固定聚合類(lèi)型：值由確定數(shù)目的成分構(gòu)成 結(jié)構(gòu)類(lèi)型 可變聚合類(lèi)型：值的成分?jǐn)?shù)目不確定 數(shù)據(jù)的邏輯結(jié)構(gòu)+運(yùn)算的定義-面向用戶，需求分析 （抽象數(shù)據(jù)類(lèi)型） 概念層 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)+運(yùn)算的實(shí)現(xiàn)-面向計(jì)算機(jī) 實(shí)現(xiàn)層 其中基本操作的定義格

9、式為:ADT 抽象數(shù)據(jù)類(lèi)型名抽象數(shù)據(jù)類(lèi)型名 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象的定義 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的定義 基本操作：基本操作：基本操作的定義 ADT 抽象數(shù)據(jù)類(lèi)型名基本操作名基本操作名（參數(shù)表） 初始條件：初始條件：初始條件描述 操作結(jié)果操作結(jié)果：操作結(jié)果描述p參數(shù)參數(shù)n賦值參數(shù) 只為操作提供輸入值。只為操作提供輸入值。n引用參數(shù) 除可提供輸入值外，還將返回該參數(shù)值在操作后的變化結(jié)除可提供輸入值外，還將返回該參數(shù)值在操作后的變化結(jié)果果p初始條件初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。p操作結(jié)果操作結(jié)果 說(shuō)明了操作正常完成之后，

10、數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。1.3 抽象數(shù)據(jù)類(lèi)型的表示與實(shí)現(xiàn)1.4 算法和算法分析算法的概念算法的概念 建立在數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上的、求解問(wèn)題的一系列確切的步驟。一個(gè)算法必須滿足以下一個(gè)算法必須滿足以下五五個(gè)重要特性個(gè)重要特性p有窮性：對(duì)任何合法輸入執(zhí)行有窮步后能結(jié)束。p確定性：每條指令必須有確切的含義。p可行性：算法的每一條指令均能執(zhí)行。p輸入：有零個(gè)或多個(gè)輸入。p輸出：有一個(gè)或多個(gè)輸出。p正確性(Correctness)n算法應(yīng)滿足具體問(wèn)題的需求算法應(yīng)滿足具體問(wèn)題的需求n對(duì)于典型的、苛刻而帶有刁難性的一組有效輸入得到正確的對(duì)于典型的、苛刻而帶有刁難性的一組有效輸入得到正確的結(jié)果結(jié)果p可讀性

11、(Readability)n算法應(yīng)該好讀。以有利于閱讀者對(duì)程序的理解。算法應(yīng)該好讀。以有利于閱讀者對(duì)程序的理解。p健壯性(Robustness) n算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙或隨機(jī)的輸出結(jié)果。反應(yīng)，而不是產(chǎn)生莫名其妙或隨機(jī)的輸出結(jié)果。p高效性(Efficiency)算法效率的度量算法效率的度量n時(shí)間復(fù)雜度時(shí)間復(fù)雜度n空間復(fù)雜度空間復(fù)雜度算法效率的度量時(shí)間復(fù)雜度空間復(fù)雜度p事后統(tǒng)計(jì)的方法n先運(yùn)行依據(jù)算法的程序先運(yùn)行依據(jù)算法的程序n所得時(shí)間的統(tǒng)計(jì)量依賴(lài)于計(jì)算機(jī)的硬件、軟件等環(huán)境所得時(shí)間的統(tǒng)計(jì)量依賴(lài)

12、于計(jì)算機(jī)的硬件、軟件等環(huán)境因素因素n收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料p事前分析估算的方法n求出該算法的一個(gè)時(shí)間界限函數(shù)；求出該算法的一個(gè)時(shí)間界限函數(shù)；pnn問(wèn)題規(guī)模，一般為數(shù)據(jù)的輸入量問(wèn)題規(guī)模，一般為數(shù)據(jù)的輸入量pf(n)n算法中基本操作重復(fù)執(zhí)行的次數(shù)算法中基本操作重復(fù)執(zhí)行的次數(shù)頻度頻度n是問(wèn)題規(guī)模是問(wèn)題規(guī)模n n的某個(gè)函數(shù)的某個(gè)函數(shù)p算法的算法的時(shí)間量度、時(shí)間復(fù)雜度時(shí)間復(fù)雜度n算法中各語(yǔ)句的頻度之和算法中各語(yǔ)句的頻度之和T(n)nT(n)=O( f(n) )n隨問(wèn)題規(guī)模的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和隨問(wèn)題規(guī)模的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率

13、和f(n)的增長(zhǎng)率相同的增長(zhǎng)率相同pO的含義n 存在正的常數(shù)存在正的常數(shù)c和和n0，使得，使得當(dāng)當(dāng)n n0時(shí)，時(shí)， 0 T(n) c* f(n) 例1： x+; s = 0;將x+看成是基本操作，語(yǔ)句頻度為T(mén)(n)=2算法的時(shí)間復(fù)雜度：O(1)-常量階例2: for (i = 0; in; i+) /執(zhí)行n+1次 x+; /語(yǔ)句頻度為：n s += x; /語(yǔ)句頻度為：n T(n)=2n+n+1=3n+1算法的時(shí)間復(fù)雜度為：O(n)-線性階例3: 矩陣相乘C=AxB for (i =0; i n; i+)/n+1 for (j = 0; j n; j+) /n*(n+1) cij = 0;/n2 for (k = 0; k n; k+) /n2 *(n+1) cij += aik * bkj; /n3 T(n)= 2n3 +3n2+2n+1算法的時(shí)間復(fù)雜度：O(n3)p在難以精確計(jì)算基本操作執(zhí)行次數(shù)的情況下，只求出關(guān)于n的增長(zhǎng)率即可。例4: for (i = 2; i = n; +i) for (j = 2; j =0 & Ai!=K ) (3) i=i-1;(4) RETURN(i);最好情況的時(shí)間復(fù)雜度 T(n)=O(1) 最壞情況的時(shí)間復(fù)雜度 T(n)=O(n) 平均時(shí)間復(fù)雜度：所有可能的輸入實(shí)例以等概率出現(xiàn)的情況 T(