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

1、第1頁(yè)第2頁(yè) 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)及相關(guān)專業(yè)中一門重要的專業(yè)基礎(chǔ)課程。本課程的任務(wù)： 在基礎(chǔ)方面，要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法；在技能方面，通過系統(tǒng)學(xué)習(xí)能夠在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算，并對(duì)算法設(shè)計(jì)的方式和技巧有所體會(huì)。學(xué)業(yè)基礎(chǔ)： 本課程的先修課程為離散數(shù)學(xué)和高級(jí)語言程序設(shè)計(jì)。學(xué)習(xí)本課程必須具備高級(jí)語言程序設(shè)計(jì)(C語言)的基礎(chǔ)知識(shí)與基本技能。它的后續(xù)課程有操作系統(tǒng)和數(shù)據(jù)庫(kù)原理等。第3頁(yè)2022年6月17日教學(xué)內(nèi)容： (1)數(shù)據(jù)結(jié)構(gòu)的概念 (2)抽象數(shù)據(jù)類型 (3)算法和算法分析 (4)遞歸 教學(xué)目的： (1)領(lǐng)會(huì)數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間關(guān)系 (2)清楚數(shù)據(jù)結(jié)

2、構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別 (3)理解抽象數(shù)據(jù)類型的概念 (4)掌握進(jìn)行簡(jiǎn)單算法分析的方法 (5)理解遞歸的特點(diǎn)，會(huì)分析什么樣的問題適合用遞歸解決；領(lǐng)會(huì)遞歸調(diào)用的執(zhí)行過程； 了解遞歸的優(yōu)缺點(diǎn)第1章 數(shù)據(jù)結(jié)構(gòu)與算法第4頁(yè)2022年6月17日教學(xué)重點(diǎn)： 數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)的概念 邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別 抽象數(shù)據(jù)類型和數(shù)據(jù)抽象 評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)及方法 (5) 什么樣的問題可以用遞歸解決、遞歸實(shí)現(xiàn)的方法 、遞歸方法的時(shí)空效率教學(xué)難點(diǎn)： 區(qū)別算法與程序 邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別 抽象數(shù)據(jù)類型與數(shù)據(jù)抽象 算法的時(shí)間復(fù)雜度分析 (5)遞歸的執(zhí)行過程；遞歸轉(zhuǎn)換為非

3、遞歸第5頁(yè)2022年6月17日1.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大和軟、硬件的發(fā)展，非數(shù)值計(jì)算問題越來越顯得重要。這類問題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學(xué)方程式加以描述。解決這類問題的關(guān)鍵是要設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問題。1.1 引言第6頁(yè)2022年6月17日 【例1-1】成績(jī)檢索系統(tǒng)。要求成績(jī)檢索系統(tǒng)提供自動(dòng)查詢的功能，如查找某個(gè)學(xué)生的單科成績(jī)或平均成績(jī)，查詢某門課程的最高分等等。學(xué)號(hào)姓名 考 試 成 績(jī) 平均成績(jī)高等數(shù)學(xué)C語言英語20071801吳承志9095859020071802李淑芳8876918520071803劉 麗9

4、278828420071804張會(huì)友8178727720071805石寶國(guó)7682797920071806何文穎8690918920071807趙勝利7678807820071808崔文靖8293868720071809劉 麗80858182圖 1-1 學(xué)生成績(jī)表第7頁(yè) 【例1-2】棋盤布局問題。要求將4個(gè)棋子布在4行4列的棋盤上，使得任兩個(gè)棋子既不在同一行或同一列，也不在同一對(duì)角線上。第8頁(yè)2022年6月17日 【例1-3】教學(xué)計(jì)劃編排問題第9頁(yè)2022年6月17日1、數(shù)據(jù)結(jié)構(gòu)課程的發(fā)展 數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程在國(guó)外是從1968年才開始的，但在此之前其有關(guān)內(nèi)容已散見于編譯原理及操作系統(tǒng)之

5、中。 從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對(duì)獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們?cè)絹碓街匾晹?shù)據(jù)結(jié)構(gòu)。 從70年代中期到80年代，各版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。 1.1.2 數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容第10頁(yè)2022年6月17日數(shù)據(jù)結(jié)構(gòu)的內(nèi)容包括三個(gè)層次的五個(gè)“要素”。2、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容第11頁(yè)2022年6月17日1.2.1 有關(guān)概念和術(shù)語1、數(shù)據(jù)2、數(shù)據(jù)項(xiàng)3、數(shù)據(jù)元素4、數(shù)據(jù)對(duì)象 1.2 數(shù)據(jù)結(jié)構(gòu)的概念第12頁(yè)2022年6月17日 （a）集合結(jié)構(gòu) （b）線性結(jié)構(gòu) （c）樹結(jié)構(gòu) （d）圖結(jié)構(gòu) 四類基本結(jié)構(gòu)的示意圖5、數(shù)據(jù)結(jié)構(gòu) 集合結(jié)構(gòu)。線性結(jié)構(gòu)。樹結(jié)構(gòu)。圖結(jié)構(gòu)。

6、 第13頁(yè)2022年6月17日(1)邏輯層次的數(shù)據(jù)結(jié)構(gòu)有兩個(gè)要素。 一個(gè)是數(shù)據(jù)元素的集合，另一個(gè)是關(guān)系的集合。 形式上，數(shù)據(jù)結(jié)構(gòu)可以采用一個(gè)二元組來表示： Data_Structure （D，R）其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。(2) 應(yīng)用層次的數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)學(xué)模型，它與數(shù)據(jù)的存儲(chǔ)無關(guān)。 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的標(biāo)識(shí)稱為數(shù)據(jù)的物理結(jié)構(gòu)，或稱存儲(chǔ)結(jié)構(gòu)。第14頁(yè)2022年6月17日1.2.2 抽象數(shù)據(jù)類型1、數(shù)據(jù)類型 數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。2、抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型（

7、Abstruct Data Type，簡(jiǎn)稱ADT）是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān)。即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用。第15頁(yè)2022年6月17日1.3.1 算法及其特性 算法（算法（AlgorithmAlgorithm）是對(duì)特定問題求解步驟的一種描述，）是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。是指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。 一個(gè)算法應(yīng)該具有下列特性： 有窮性。有窮性。 確定性。確定性。 可行性?？尚行?/p>

8、。 輸入。輸入。 輸出。輸出。1.3 算法 第16頁(yè)2022年6月17日要設(shè)計(jì)一個(gè)好的算法通常要考慮以下的要求。 正確。正確。 可讀。可讀。 健壯。健壯。 高效。高效。第17頁(yè)2022年6月17日1.3.2 算法描述算法可以使用各種不同的方法來描述。l自然語言自然語言: :l程序流程圖、程序流程圖、N-SN-S圖圖等算法描述工具：l直接使用某種程序設(shè)計(jì)語言某種程序設(shè)計(jì)語言：l用偽碼語言偽碼語言的描述方法：第18頁(yè)2022年6月17日1.3.3 算法的性能分析與度量時(shí)間復(fù)雜度 將一個(gè)算法轉(zhuǎn)換成程序并在計(jì)算機(jī)上執(zhí)行時(shí)，其運(yùn)行所需要的時(shí)間取決于下列因素： 硬件的速度。 書寫程序的語言。 編譯程序所生

9、成目標(biāo)代碼的質(zhì)量。 問題的規(guī)模。第19頁(yè)2022年6月17日 時(shí)間復(fù)雜度時(shí)間復(fù)雜度 ：算法的時(shí)間復(fù)雜度T(n)表示為：其中ti表示語句i執(zhí)行一次的時(shí)間，ci表示語句i的頻度。 假設(shè)每條語句執(zhí)行一次的時(shí)間均為一個(gè)單位時(shí)間，那么算法的時(shí)間耗費(fèi)可簡(jiǎn)單表示為各語句的頻度之和： ii( )tciT n 語句（）i( )ciT n 語句第20頁(yè)2022年6月17日【例1-5】下面的程序段用來求兩個(gè)n階方陣A和B的乘積C。for(i=0;in;i+) /* n+1*/ for(j=0;jn;j+) /* n(n+1) */ Cij=0; /* n2*/ for(k=0;kn;k+) /* n2(n+1) *

10、/Cij+=Aik*Bkj; /* n3*/右邊列出了各語句的頻度，因而算法的時(shí)間復(fù)雜度T(n)為： T (n) (n+1)n(n+1)+ n2+ n2(n+1) + n3 =2n3+3n2+2n+1可見，T(n)是矩陣階數(shù)n的函數(shù)。第21頁(yè)2022年6月17日 而許多時(shí)候要精確地計(jì)算T(n)是困難的，很多算法的時(shí)間復(fù)雜度難以給出解析形式，或者非常復(fù)雜。 因此在實(shí)際應(yīng)用中，往往放棄復(fù)雜的函數(shù)來表示確切的時(shí)間復(fù)雜度，而采用一些簡(jiǎn)單的函數(shù)來近似表示時(shí)間性能，這就是時(shí)間漸進(jìn)復(fù)雜度。 定義（大記號(hào)）：設(shè)T(n)是問題規(guī)模n的函數(shù)f(n)，若存在兩個(gè)正常數(shù)c和n0，使得對(duì)所有的n，nn0，有： T(n)

11、 cf(n)，則記為：T(n) (f(n) 例 如 ， 一 個(gè) 程 序 的 實(shí) 際 執(zhí) 行 時(shí) 間 為 T ( n ) 20n3+25n2+9，則T(n)(n3)。 使用大記號(hào)表示的算法的時(shí)間復(fù)雜度，稱為算法的漸進(jìn)時(shí)間復(fù)雜度（Asymptotic Complexity），簡(jiǎn)稱時(shí)間復(fù)雜度。第22頁(yè)2022年6月17日 通常用(1)表示常數(shù)計(jì)算時(shí)間。常見的漸進(jìn)時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列為： (1)(log2n)(n)(nlog2n) (n2)(n3)(2n) 第23頁(yè)2022年6月17日【例1-6】冒泡排序。void BublleSort(int a , int n) for (i=0; in-1

12、&swap; i+) swap=0; for(j=0; jaj+1) ajaj+1; swap=1; 選擇交換相鄰的兩個(gè)元素“ajaj+1;”作為基本操作。 而n個(gè)元素組成的輸入集可能有n!中排列情況，若各種情況等概率，則冒泡排序的平均時(shí)間復(fù)雜度T(n)=(n2)。 第24頁(yè)2022年6月17日l 空間復(fù)雜度： 一個(gè)算法的空間復(fù)雜度（Space complexity）是指算法運(yùn)行從開始到結(jié)束所需的存儲(chǔ)量。 第25頁(yè)2022年6月17日 算法運(yùn)行所需的存儲(chǔ)空間包括以下兩部分： v固定部分 這部分空間與所處理數(shù)據(jù)的大小和個(gè)數(shù)無關(guān)，或者稱與問題的實(shí)例的特征無關(guān)。主要包括程序代碼、常量、簡(jiǎn)單變

13、量、定長(zhǎng)成分的結(jié)構(gòu)變量所占的空間。v可變部分 這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。例如100個(gè)數(shù)據(jù)元素的排序算法與1000個(gè)數(shù)據(jù)元素的排序算法所需的存儲(chǔ)空間顯然是不同的。 第26頁(yè) 例1：一個(gè)人要搬走10塊石頭，怎么搬呢？ 例2：計(jì)算從1到100的累加和。 例3：計(jì)算2n。 這些定義方式體現(xiàn)了一種邏輯思想，同時(shí)又是一種解決問題的方案。遞歸定義的問題，可以用遞歸的算法來求解。1.4 遞歸1.問題的提出第27頁(yè)n ! =1 n=0 n*(n-1)! n0 Fib( n ) =n n=0,1 Fib(n-1)+ Fib(n-2) n=2 遞歸是一個(gè)過程或函數(shù)直接或間接調(diào)用

14、自身的一種方法，它可以把一個(gè)大型的問題層層轉(zhuǎn)化為一個(gè)與原問題相似、但規(guī)模較小的問題來求解。 數(shù)學(xué)中階乘的定義，n的階乘可以如下表示： 再如，斐波那契（Fibonacci）數(shù)列指的是這樣一個(gè)數(shù)列： 直接或間接調(diào)用自身的程序稱為遞歸程序。 遞歸是一種特殊的嵌套調(diào)用，是某個(gè)函數(shù)調(diào)用自己，而不是另外一個(gè)函數(shù)。這是一種函數(shù)直接或者間接調(diào)用自身編程技術(shù)。1.4.1 遞歸的概念第28頁(yè)1.4.2 遞歸調(diào)用的實(shí)現(xiàn)原理1.遞歸算法的構(gòu)成能夠用遞歸解決的問題應(yīng)該滿足以下三個(gè)條件：需要解決的問題可以化為一個(gè)或多個(gè)子問題來求解，而這些子問題的求解方法與原來的問題完全相同，只是在數(shù)量規(guī)模上不同；遞歸調(diào)用的次數(shù)必須是有限

15、的；必須有結(jié)束遞歸的條件（邊界條件）來終止遞歸。第29頁(yè)遞歸算法的設(shè)計(jì)一般分為兩步:第一步，將規(guī)模較大的原問題分解為一個(gè)或多個(gè)規(guī)模較小的而又類似于原問題特性的子問題，既將較大的問題遞歸地用較小的子問題來描述，解原問題的方法同樣可以用來解決子問題；第二步，是確定一個(gè)或多個(gè)不需要分解、可直接求解的最小子問題。 第30頁(yè)【算法2-1】計(jì)算n！的遞歸方法 public static int fact1 (int n) int temp； if (n= =0|) /遞歸的終結(jié)條件 return 1 ; else temp= n* fact (n-1)； /遞歸調(diào)用 return temp; 【算法2-2

16、】計(jì)算斐波那契（Fibonacci）數(shù)列第n項(xiàng)的遞歸方法 public static int fibonacci1 (int n) if (n= =0|n= =1) /遞歸的終結(jié)條件 return n ; else return(fibonacci (n-2)+ fibonacci (n-1)；/遞歸調(diào)用 第31頁(yè) 2.遞歸調(diào)用的內(nèi)部過程 【算法2-1】中求階乘的問題，假設(shè)程序運(yùn)行時(shí)，n4，那么程序的執(zhí)行過程。第32頁(yè) 從上面可以看出，遞歸調(diào)用的過程分為兩個(gè)階段： 1）遞歸過程：將原始問題不斷轉(zhuǎn)化為規(guī)模小了一級(jí)的新問題，從求4！變成求3！，變成求2！，最終達(dá)到遞歸終結(jié)條件，求1??； 2）回溯過

17、程：從已知條件出發(fā)，沿遞歸的逆過程，逐一求值返回，直至遞歸初始處，完成遞歸調(diào)用。 第33頁(yè)2.遞歸調(diào)用的內(nèi)部過程 在這兩個(gè)階段中，系統(tǒng)會(huì)分別完成一系列的操作。在遞歸調(diào)用之前，系統(tǒng)需完成三件事：為被調(diào)用過程的局部變量分配存儲(chǔ)區(qū)；將所有的實(shí)參、返回地址等信息傳遞給被調(diào)用過程保存；將控制轉(zhuǎn)移到被調(diào)過程的入口。 從被調(diào)用過程返回調(diào)用過程之前，系統(tǒng)也應(yīng)完成三件工作：保存被調(diào)過程的計(jì)算結(jié)果；釋放被調(diào)過程的數(shù)據(jù)區(qū)；依照被調(diào)過程保存的返回地址將控制轉(zhuǎn)移到調(diào)用過程。 在計(jì)算機(jī)中，是通過使用系統(tǒng)棧（后面的章節(jié)會(huì)介紹“?！保﹣硗瓿缮鲜霾僮鞯摹５?4頁(yè)1.4.3 遞歸轉(zhuǎn)換為非遞歸1.1.遞歸轉(zhuǎn)化為遞推遞歸轉(zhuǎn)化為遞推

18、當(dāng)遞歸算法所涉及的數(shù)據(jù)定義形式是遞歸的情況下，通?？梢詫⑦f歸算法轉(zhuǎn)化為遞推算法，用遞歸的邊界條件作為遞推的邊界條件。比如求階乘、斐波那契數(shù)列等。 遞推也是一種從已知條件出發(fā)，用一種具體的算法，一步一步接近未知，一般采用循環(huán)結(jié)構(gòu)，經(jīng)常和枚舉配合使用。遞推算法在求解的過程中，每一個(gè)中間量都是已知，而且沒有重復(fù)計(jì)算，運(yùn)算簡(jiǎn)潔，但是書寫代碼和理解代碼比較難。第35頁(yè)【例1-8】 階乘的遞推算法 public static int fact2 (int n) int s=1; for( i=1; i=n; i+) s=s*i; return s; 【例1-9】斐波那契數(shù)列的遞推算法 public static int fibo 2(int n) int f0=1, f1=1, f;