數(shù)據(jù)結構緒論

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

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

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

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

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

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

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

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

9、成目標代碼的質量。 問題的規(guī)模。第19頁2022年6月17日 時間復雜度時間復雜度 ：算法的時間復雜度T(n)表示為：其中ti表示語句i執(zhí)行一次的時間，ci表示語句i的頻度。 假設每條語句執(zhí)行一次的時間均為一個單位時間，那么算法的時間耗費可簡單表示為各語句的頻度之和： ii( )tciT n 語句（）i( )ciT n 語句第20頁2022年6月17日【例1-5】下面的程序段用來求兩個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*/右邊列出了各語句的頻度，因而算法的時間復雜度T(n)為： T (n) (n+1)n(n+1)+ n2+ n2(n+1) + n3 =2n3+3n2+2n+1可見，T(n)是矩陣階數(shù)n的函數(shù)。第21頁2022年6月17日 而許多時候要精確地計算T(n)是困難的，很多算法的時間復雜度難以給出解析形式，或者非常復雜。 因此在實際應用中，往往放棄復雜的函數(shù)來表示確切的時間復雜度，而采用一些簡單的函數(shù)來近似表示時間性能，這就是時間漸進復雜度。 定義（大記號）：設T(n)是問題規(guī)模n的函數(shù)f(n)，若存在兩個正常數(shù)c和n0，使得對所有的n，nn0，有： T(n)

11、 cf(n)，則記為：T(n) (f(n) 例 如 ， 一 個 程 序 的 實 際 執(zhí) 行 時 間 為 T ( n ) 20n3+25n2+9，則T(n)(n3)。 使用大記號表示的算法的時間復雜度，稱為算法的漸進時間復雜度（Asymptotic Complexity），簡稱時間復雜度。第22頁2022年6月17日 通常用(1)表示常數(shù)計算時間。常見的漸進時間復雜度按數(shù)量級遞增排列為： (1)(log2n)(n)(nlog2n) (n2)(n3)(2n) 第23頁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; 選擇交換相鄰的兩個元素“ajaj+1;”作為基本操作。 而n個元素組成的輸入集可能有n!中排列情況，若各種情況等概率，則冒泡排序的平均時間復雜度T(n)=(n2)。 第24頁2022年6月17日l 空間復雜度： 一個算法的空間復雜度（Space complexity）是指算法運行從開始到結束所需的存儲量。 第25頁2022年6月17日 算法運行所需的存儲空間包括以下兩部分： v固定部分 這部分空間與所處理數(shù)據(jù)的大小和個數(shù)無關，或者稱與問題的實例的特征無關。主要包括程序代碼、常量、簡單變

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

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

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

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

17、程：從已知條件出發(fā)，沿遞歸的逆過程，逐一求值返回，直至遞歸初始處，完成遞歸調用。 第33頁2.遞歸調用的內部過程 在這兩個階段中，系統(tǒng)會分別完成一系列的操作。在遞歸調用之前，系統(tǒng)需完成三件事：為被調用過程的局部變量分配存儲區(qū)；將所有的實參、返回地址等信息傳遞給被調用過程保存；將控制轉移到被調過程的入口。 從被調用過程返回調用過程之前，系統(tǒng)也應完成三件工作：保存被調過程的計算結果；釋放被調過程的數(shù)據(jù)區(qū)；依照被調過程保存的返回地址將控制轉移到調用過程。 在計算機中，是通過使用系統(tǒng)棧（后面的章節(jié)會介紹“棧”）來完成上述操作的。第34頁1.4.3 遞歸轉換為非遞歸1.1.遞歸轉化為遞推遞歸轉化為遞推

18、當遞歸算法所涉及的數(shù)據(jù)定義形式是遞歸的情況下，通?？梢詫⑦f歸算法轉化為遞推算法，用遞歸的邊界條件作為遞推的邊界條件。比如求階乘、斐波那契數(shù)列等。 遞推也是一種從已知條件出發(fā)，用一種具體的算法，一步一步接近未知，一般采用循環(huán)結構，經(jīng)常和枚舉配合使用。遞推算法在求解的過程中，每一個中間量都是已知，而且沒有重復計算，運算簡潔，但是書寫代碼和理解代碼比較難。第35頁【例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;