數(shù)據(jù)結(jié)構(gòu)知識點全面總結(jié)

1、第1章 緒論內(nèi)容提要： 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容。針對非數(shù)值計算的程序設(shè)計問題，研究計算機的 操作對象 以及它們之間的 關(guān)系和操作 。 數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容： 基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型。 數(shù)據(jù) 所有能被計算機識別、存儲和處理的符號的集合。數(shù)據(jù)元素 是數(shù)據(jù)的基本單位，具有完整確定的實際意義。數(shù)據(jù)對象 具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，表示為：Data_Structure= （ D, R）數(shù)據(jù)類型 是一個值的集合和定義在該值上的一組操作的總稱。抽象數(shù)據(jù)類型 由用戶定義的一個數(shù)學(xué)模型與定義在

2、該模型上的一組操作， 它由基本的數(shù)據(jù)類型構(gòu)成。 算法的定義及五個特征。算法 是對特定問題求解步驟的一種描述， 它是指令的有限序列， 是一系列輸入轉(zhuǎn)換為輸 出的計算步驟。算法的基本特性 ：輸入、輸出、有窮性、確定性、可行性 算法設(shè)計要求。 正確性、可讀性、健壯性、效率與低存儲量需求 算法分析。 時間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性 學(xué)習(xí)重點： 數(shù)據(jù)結(jié)構(gòu)的“三要素” ：邏輯結(jié)構(gòu) 、物理（存儲）結(jié)構(gòu) 及在 這種結(jié)構(gòu)上所定義的操作（運 算） 。 用計算語句頻度來估算算法的時間復(fù)雜度。第二章 線性表內(nèi)容提要： 線性表的邏輯結(jié)構(gòu)定義，對線性表定義的操作。線性表的定義：用數(shù)據(jù)元素的有限序列表示 線性表的存儲結(jié)構(gòu)：

3、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。不一順序存儲定義：把邏輯上 相鄰 的數(shù)據(jù)元素存儲在物理上 相鄰 的存儲單元中的存儲結(jié)構(gòu)。 鏈?zhǔn)酱鎯Y(jié)構(gòu) : 其結(jié)點在存儲器中的位置是隨意的， 即邏輯上 相鄰 的數(shù)據(jù)元素在物理上 定相鄰。通過 指針 來實現(xiàn)！ 線性表的操作在兩種存儲結(jié)構(gòu)中的實現(xiàn)。 數(shù)據(jù)結(jié)構(gòu)的基本運算： 修改、插入、刪除、查找、排序1) 修改通過數(shù)組的下標(biāo)便可訪問某個特定元素并修改之。 核心語句 : Vi=x;順序表修改操作的時間效率是 O(1)2) 插入在線性表的第 i 個位置前插入一個元素 實現(xiàn)步驟： 將第 n 至第 i 位的元素向后移動一個位置； 將要插入的元素寫到第 i 個位置；表長加 1。注意

4、：事先應(yīng)判斷 : 插入位置 i 是否合法表是否已滿 應(yīng)當(dāng)符合條件： 1in+1 或 i=1, n+1 核心語句：for (j=n; j=i; j-) aj+1=a j ;a i =x;n+;插入時的平均移動次數(shù)為： n(n+1)/ 2( n+1) n/2 O(n)3) 刪除刪除線性表的第 i 個位置上的元素 實現(xiàn)步驟：將第 i+1 至第 n 位的元素向前移動一個位置； 表長減 1。 注意：事先需要判斷，刪除位置 i 是否合法 應(yīng)當(dāng)符合條件： 1in 或 i=1, n核心語句：for ( j=i+1; j=n; j+ )aj-1=aj;n-;順序表刪除一元素的時間效率為 :T（ n）=（n-1）

5、/ 2 O（n）順序表插入、刪除算法的平均空間復(fù)雜度為 O（1）單鏈表：1）a，b， c， z） ,請寫出 C語言程序。用單鏈表結(jié)構(gòu)來存放 26 個英文字母組成的線性表（ #include #include typedef struct nodechar data; struct node *next; node;node*p,*q,*head;d1, c2.d2 ，則行優(yōu)先存儲時的地址公式為：二維數(shù)組列優(yōu)先存儲的通式為： 稀疏矩陣（含特殊矩陣）的存儲及運算。稀疏矩陣：矩陣中非零元素的個數(shù)較少（一般小于5%）學(xué)習(xí)重點： 線性表的邏輯結(jié)構(gòu)，指線性表的數(shù)據(jù)元素間存在著 線性關(guān)系 。在順序存儲結(jié)構(gòu)中

6、，元素 存儲的 先后位置 反映出這種線性關(guān)系，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，是靠 指針 來反映這種關(guān)系的。 順序存儲結(jié)構(gòu)用一維數(shù)組表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于 隨機存取 的存儲結(jié) 構(gòu)。 鏈表操作中應(yīng)注意不要使鏈意外“斷開” 。因此，若在某結(jié)點前插入一個元素，或刪除 某元素，必須知道該元素的 前驅(qū)結(jié)點的指針 。 掌握通過畫出結(jié)點圖來進(jìn)行鏈表（單鏈表、循環(huán)鏈表等）的 生成、插入、刪除、遍歷 等 操作。 數(shù)組（主要是二維）在以 行序 / 列序 為主的存儲中的地址計算方法。 稀疏矩陣的三元組表存儲結(jié)構(gòu)。 稀疏矩陣的十字鏈表存儲方法。 補充重點：1. 每個存儲結(jié)點都包含兩部分： 數(shù)據(jù)域和指針域 （ 鏈域

7、 ）2. 在單鏈表中，除了首元結(jié)點外， 任一結(jié)點的存儲位置由 其直接前驅(qū)結(jié)點的鏈域的值 指示。3. 在鏈表中設(shè)置頭結(jié)點有什么好處頭結(jié)點即在鏈表的首元結(jié)點之前附設(shè)的一個結(jié)點，該結(jié)點的 數(shù)據(jù)域可以為空，也可存 放表長度 等附加信息， 其作用是為了對鏈表進(jìn)行操作時， 可以對 空表、 非空表 的情況以及對 首元結(jié)點 進(jìn)行統(tǒng)一處理，編程更方便。4. 如何表示空表 （1）無頭結(jié)點時，當(dāng)頭指針的值為空時表示空表； （2）有頭結(jié)點時，當(dāng)頭結(jié)點的指針域為空時表示空表。5. 鏈表的數(shù)據(jù)元素有兩個域，不再是簡單數(shù)據(jù)類型，編程時該如何表示 因每個結(jié)點至少有兩個分量，且數(shù)據(jù)類型通常不一致，所以要采用結(jié)構(gòu)數(shù)據(jù)類型。（x）

8、 計算變量 x 的長度（字節(jié)數(shù)） ；malloc（m） 開辟 m 字節(jié)長度的地址空間，并返回這段空間的首地址； free（p） 釋放指針 p 所指變量的存儲空間，即徹底刪除一個變量。7. 鏈表的運算效率分析：（1）查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度為O（n）。（2） 插入和刪除 因線性鏈表不需要移動元素，只要修改指針，一般情況下時間復(fù)雜度為O（1）。但是，如果要在單鏈表中進(jìn)行前插或刪除操作，因為要從頭查找前驅(qū)結(jié)點，所耗時間復(fù)雜 度將是 O（n）。例：在 n 個結(jié)點的單鏈表中要刪除已知結(jié)點 *P ，需找到它的 前驅(qū)結(jié)點的地址 ，其時間復(fù)雜 度為 O（ n）8

9、. 順序存儲和鏈?zhǔn)酱鎯Φ膮^(qū)別和優(yōu)缺點 順序存儲時，邏輯上相鄰的數(shù)據(jù)元素，其物理存放地址也相鄰。 順序存儲的優(yōu)點是存 儲密度大，存儲空間利用率高；缺點是插入或刪除元素時不方便。鏈?zhǔn)酱鎯r， 相鄰數(shù)據(jù)元素可隨意存放， 但所占存儲空間分兩部分， 一部分存放結(jié)點值， 另一部分存放表示結(jié)點間關(guān)系的指針。 鏈?zhǔn)酱鎯Φ膬?yōu)點是插入或刪除元素時很方便，使用 靈活。缺點是存儲密度小，存儲空間利用率低。 順序表適宜于做查找這樣的靜態(tài)操作； 鏈表宜于做插入、刪除這樣的動態(tài)操作。 若線性表的長度變化不大，且其主要操作是查找，則采用順序表； 若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。9. 判斷：“

10、數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡單” ，對嗎 答：對的。因為 數(shù)組中各元素具有 統(tǒng)一的類型； 數(shù)組元素的下標(biāo)一般具有 固定的上界和下界 ，即數(shù)組一旦被定義，它的維數(shù)和維界就不 再改變。 數(shù)組的 基本操作比較簡 單，除了結(jié)構(gòu)的初始化和銷毀之外， 只有存取元素和修改元素值的 操作。10. 三元素組表中的每個結(jié)點對應(yīng)于稀疏矩陣的一個非零元素，它包含有三個數(shù)據(jù)項，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。11. 寫出右圖所示稀疏矩陣的壓縮存儲形式。法 2：用十字鏈表表示用途：方便稀疏矩陣的加減運算方法：每個非 0 元素占用 5 個域法 1：用線性表表示：( 1,2,12) ，(1,3,9)，

11、(3,1,-3)， (3,5,14)，(4,3,24) ， (5,2,18) ， (6,1,15)， (6,4,-7)解：介紹 3 種存儲形式。法 3：用三元組矩陣表示：稀疏矩陣壓縮存儲的缺點：將失去隨機存取功能 代碼：a， b，c， z），寫出在順序結(jié)構(gòu)上生成1. 用數(shù)組 V來存放 26 個英文字母組成的線性表（ 和顯示該表的 C 語言程序。char V30;void build()base=(QElemType *)malloc(sizeof(QElemType )QUEUE_MAXSIZE;base=(QElemType *)malloc(sizeof(QElemType)* QUEUE

12、_MAXSIZE）; rear + 1 ） % QUEUE_MAXSIZE; = e; 什么要設(shè)計隊列它有什么獨特用途 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU 芯片中的指令譯碼隊列） 操作系統(tǒng)中的作業(yè)調(diào)度（一個 CPU 執(zhí)行多個作業(yè)） ； 簡化程序設(shè)計。3. 什么叫“假溢出” 如何解決 答：在順序隊中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界， 不能再有入隊操作， 但其實數(shù)組中還有空 位置，這就叫“假溢出” 。解決假溢出的途徑采用循環(huán)隊列。4. 在一個循環(huán)隊列中， 若約定隊首指針指向隊首元素的前一個位置。那么， 從循環(huán)隊列中刪除一個元素時，其操作是先 移動隊首位置 ，后 取出元素 。5. 線性

13、表、棧、隊的異同點：相同點：邏輯結(jié)構(gòu)相同， 都是線性的；都可以用順序存儲或鏈表存儲； 棧和隊列是兩種特殊 的線性表，即受限的線性表（只是對插入、刪除運算加以限制） 。不同點： 運算規(guī)則不同： 線性表為隨機存?。?而棧是只允許在一端進(jìn)行插入和刪除運算，因而是后進(jìn)先出表LIFO；隊列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運算，因而是先進(jìn)先出表FIFO。 用途不同，線性表比較通用；堆棧用于函數(shù)調(diào)用、遞歸和簡化設(shè)計等；隊列用于離散事 件模擬、 OS作業(yè)調(diào)度和簡化設(shè)計等。第四章 串 內(nèi)容提要： 串是數(shù)據(jù)元素為字符的線性表，串的定義及操作。 串即字符串，是由零個或多個字符組成的有限序列，是數(shù)據(jù)元素為單個字

14、符的特殊線性表。 串比較： int strcmp(char *s1,char *s2);求串長： int strlen(char *s);串連接： char strcat(char *to,char *from)子串 T 定位： char strchr(char *s,char *c); 串的存儲結(jié)構(gòu)，因串是數(shù)據(jù)元素為字符的線性表，所以存在“結(jié)點大小”的問題。 模式匹配算法。串有三種機內(nèi)表示方法：模式匹配算法： 算法目的：確定主串中所含子串第一次出現(xiàn)的位置(定位) 定位問題稱為串的模式匹配，典型函數(shù)為 Index(S,T,pos)BF算法的實現(xiàn)即編寫 Index(S, T, pos)函數(shù)BF算

15、法設(shè)計思想：將主串 S的第 pos個字符和模式 T的第 1 個字符比較， 若相等，繼續(xù)逐個比較后續(xù)字符；若不等，從主串 S 的下一字符( pos+1)起，重新與 T 第一個字符比較。 直到主串 S的一個連續(xù)子串字符序列與模式T 相等。返回值為 S中與 T匹配的子序列第一個字符的序號，即匹配成功。否則，匹配失敗，返回值 0。Int Index_BP(SString S, SString T, int pos) 串和空白串有無區(qū)別 答：有區(qū)別?？沾?(Null String)是指長度為零的串；而空白串 (Blank String),是指包含一個或多個空白字符 (空格鍵 )的字符串 .2. “空串是

16、任意串的子串；任意串S 都是 S本身的子串，除 S本身外， S 的其他子串稱為 S的真子串?！钡诹?樹和二叉樹內(nèi)容提要： 樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。樹：由一個或多個 (n 0)結(jié)點組成的有限集合 T，有且僅有一個結(jié)點稱為根( root )，當(dāng) n1 時，其余的結(jié)點分為 m(m 0)個互不相交的有限集合 T1,T2， Tm。每個集合本身又是棵 樹，被稱作這個根的子樹 。二叉樹：是 n( n 0)個結(jié)點的有限集合，由一個根結(jié)點以及兩棵互不相交的、分別稱為左 子樹和右子樹的二叉樹組成。術(shù)語： P88 二叉樹的性質(zhì)，存儲結(jié)構(gòu)。性質(zhì) 1: 在二叉樹的第 i 層上至

17、多有 2i-1 個結(jié)點（ i0）。性質(zhì) 2: 深度為 k 的二叉樹至多有 2k-1 個結(jié)點（ k0）。性質(zhì) 3: 對于任何一棵二叉樹，若 2 度的結(jié)點數(shù)有 n2 個，則葉子數(shù)（ n0）必定為 n2 1 性質(zhì) 4: 具有 n 個結(jié)點的完全二叉樹的深度必為性質(zhì) 5: 對完全二叉樹，若從上至下、從左至右編號，則編號為 i 的結(jié)點，其左孩子編號必 為 2i，其右孩子編號為 2i1；其雙親的編號必為 i/2（ i1 時為根 ,除外）。 二叉樹的存儲結(jié)構(gòu)： 一、順序存儲結(jié)構(gòu) 按二叉樹的結(jié)點“自上而下、從左至右”編號，用一組連續(xù)的存儲單元存儲。若是完全 / 滿二叉樹則可以做到唯一復(fù)原。 不是完全二叉樹：一律

18、轉(zhuǎn)為完全二叉樹！ 方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結(jié)點” ，其內(nèi)容為空。 缺點：浪費空間；插入、刪除不便二、鏈?zhǔn)酱鎯Y(jié)構(gòu) 用二叉鏈表即可方便表示。一般從根結(jié)點開始存儲。優(yōu)點：不浪費空間；插入、刪除方便 二叉樹的遍歷。 指按照某種次序訪問二叉樹的所有結(jié)點，并且每個結(jié)點僅訪問一次，得到一個線性序列。 遍歷規(guī)則二叉樹由根、左子樹、右子樹構(gòu)成，定義為D、 L、 R若限定先左后右，則有三種實現(xiàn)方案：DLRLDRLRD先序遍歷中序遍歷后序遍歷 樹的存儲結(jié)構(gòu)，樹、森林的遍歷及和二叉樹的相互轉(zhuǎn)換?；仡?2：二叉樹怎樣還原為樹 要點：逆操作，把所有右孩子變?yōu)樾值埽?討論 1 ：森林如何轉(zhuǎn)為二叉樹 法一： 各

19、森林先各自轉(zhuǎn)為二叉樹； 依次連到前一個二叉樹的右子樹上。法二：森林直接變兄弟，再轉(zhuǎn)為二叉樹討論 2：二叉樹如何還原為森林 要點：把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值?樹和森林的存儲方式： 樹有三種常用存儲方式： 雙親表示法 孩子表示法 孩子兄弟表示法 問：樹二叉樹的“連線抹線旋轉(zhuǎn)” 如何由計算機自動實現(xiàn) 答：用“左孩子右兄弟”表示法來存儲即可。 存儲的過程就是樹轉(zhuǎn)換為二叉樹的過程！樹、森林的遍歷： 先根遍歷：訪問根結(jié)點；依次先根遍歷根結(jié)點的每棵子樹。 后根遍歷：依次后根遍歷根結(jié)點的每棵子樹；訪問根結(jié)點。 討論：樹若采用“先轉(zhuǎn)換，后遍歷”方式，結(jié)果是否一樣1. 樹的先根遍歷與二叉樹的先序遍

20、歷相同；2. 樹的后根遍歷相當(dāng)于二叉樹的中序遍歷；3. 樹沒有中序遍歷，因為子樹無左右之分。 先序遍歷若森林為空，返回； 訪問森林中第一棵樹的根結(jié)點； 先根遍歷第一棵樹的根結(jié)點的子樹森林； 先根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 中序遍歷 若森林為空，返回； 中根遍歷森林中第一棵樹的根結(jié)點的子樹森林； 訪問第一棵樹的根結(jié)點； 中根遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。 二叉樹的應(yīng)用：哈夫曼樹和哈夫曼編碼。Huffman 樹：最優(yōu)二叉樹（帶權(quán)路徑長度最短的樹）Huffman 編碼：不等長編碼。樹的帶權(quán)路徑長度： （樹中所有葉子結(jié)點的帶權(quán)路徑長度之和）構(gòu)造 Huffman 樹的基本思想：權(quán)

21、值大的結(jié)點用短路徑，權(quán)值小的結(jié)點用長路徑。 構(gòu)造 Huffman 樹的步驟（即 Huffman 算法）：（1）由給定的 n 個權(quán)值 w1, w2, , wn 構(gòu)成 n棵二叉樹的集合 F = T1, T2, , Tn （即森 林） ，其中每棵二叉樹 Ti 中只有一個帶權(quán)為 wi 的根結(jié)點，其左右子樹均空。(2) 在 F 中選取兩棵根結(jié)點權(quán)值最小的樹 做為左右子樹構(gòu)造一棵新的二叉樹，且讓新二叉 樹根結(jié)點的權(quán)值等于其左右子樹的根結(jié)點權(quán)值之和。(3) 在 F 中刪去這兩棵樹，同時將新得到的二叉樹加入F 中。(4) 重復(fù)(2) 和(3) , 直到 F 只含一棵樹為止。這棵樹便是 Huffman 樹。 具

22、體操作步驟：學(xué)習(xí)重點：(本章內(nèi)容是本課程的重點) 二叉樹性質(zhì)及證明方法，并能把這種方法推廣到K 叉樹。 二叉樹遍歷，遍歷是基礎(chǔ)，由此導(dǎo)出許多實用的算法，如求二叉樹的高度、各結(jié)點的層 次數(shù)、度為 0、1、 2 的結(jié)點數(shù)。由前序和 由二叉樹遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹。 后序序列不能唯一確定一棵二叉樹。 完全二叉樹的性質(zhì)。 樹、森林和二叉樹間的相互轉(zhuǎn)換。 哈夫曼樹的定義、構(gòu)造及求哈夫曼編碼。補充：1. 滿二叉樹和完全二叉樹有什么區(qū)別k-1 層是滿的，但最底層卻允許答：滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前 在右邊缺少連續(xù)若干個結(jié)點。滿二叉樹是完全二叉樹的一個

23、特例。2. Huffman 樹有什么用最小冗余編碼、信息高效傳輸?shù)谄哒?圖內(nèi)容提要： 圖的定義，概念、術(shù)語及基本操作。 圖：記為 G( V, E ) 其中： V 是 G 的頂點集合，是有窮非空集；E 是G 的邊集合，是有窮集。 術(shù)語：見課件 圖的存儲結(jié)構(gòu)。1. 鄰接矩陣 （數(shù)組 ）表示法 建立一個頂點表和一個鄰接矩陣 設(shè)圖 A = （V, E） 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 nn 。 注：在有向圖的鄰接矩陣中，第 i 行含義：以結(jié)點 vi 為尾的弧 （即出度邊）；第 i 列含義：以結(jié)點 vi 為頭的弧 （即入度邊）。 鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點

24、之間是否有邊（?。?找頂點的鄰接點等等。鄰接矩陣法缺點： n 個頂點需要 n*n 個單元存儲邊 （?。?空間效率為 O（n2）。2. 鄰接表 （鏈?zhǔn)?）表示法 對每個頂點 vi 建立一個單鏈表，把與 vi 有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來， 表中每個結(jié)點都設(shè)為 3 個域 : 每個單鏈表還應(yīng)當(dāng)附設(shè)一個頭結(jié)點（設(shè)為2 個域），存 vi 信息； 每個單鏈表的頭結(jié)點另外用順序存儲結(jié)構(gòu)存儲。 鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點； 鄰接表的缺點： 判斷兩頂點間是否有邊或弧， 需搜索兩結(jié)點對應(yīng)的單鏈表， 沒有鄰接矩陣方 便。 圖的遍歷。 遍歷定義：從已給的連通圖中某一頂點出發(fā)，沿著一些邊

25、，訪遍圖中所有的頂點，且 使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。 圖常用的遍歷：一、深度優(yōu)先搜索；二、廣度優(yōu)先搜索 深度優(yōu)先搜索（遍歷）步驟： 訪問起始點 v; 若 v 的第 1 個鄰接點沒訪問過，深度遍歷此鄰接點； 若當(dāng)前鄰接點已訪問過，再找 v 的第 2 個鄰接點重新遍歷。 基本思想：仿樹的先序遍歷過程。廣度優(yōu)先搜索（遍歷）步驟： 在訪問了起始點 v 之后，依次訪問 v 的鄰接點； 然后再依次（順序）訪問這些點（下一層）中未被訪問過的鄰接點； 直到所有頂點都被訪問過為止。 圖的應(yīng)用（最小生成樹，最短路經(jīng)）最小生成樹（ MST）的性質(zhì)如下：若 U 集是 V 的一個非空子集

26、，若 （u0, v0）是一條最小權(quán) 值的邊，其中 u0U， v0V-U；則： （u0, v0）必在最小生成樹上。求 MST 最常用的是以下兩種： Kruskal（克魯斯卡爾）算法、 Prim （普里姆）算法Kruskal 算法特點：將邊歸并，適于求稀疏網(wǎng)的最小生成樹。Prime 算法特點 : 將頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。在帶權(quán)有向圖中 A 點（源點）到達(dá) B 點（終點）的多條路徑中，尋找一條各邊權(quán)值之和最 小的路徑，即最短路徑。兩種常見的最短路徑問題：一、 單源最短路徑用 Dijkstra（迪杰斯特拉）算法 二、所有頂點間的最短路徑用Floyd（弗洛伊德）算法一、單源最短路徑 （Dij

27、kstra 算法 ）一頂點到其余各頂點（ v0j）目的： 設(shè)一有向圖 G=（V, E），已知各邊的權(quán)值，以某指定點 v0 為源點，求從 v0到圖 的其余各點的最短路徑。限定各邊上的權(quán)值大于或等于0。二、所有頂點之間的最短路徑可以通過調(diào)用 n 次 Dijkstra 算法來完成，還有更簡單的一個算法： Floyd 算法（自學(xué)） 。學(xué)習(xí)重點： 圖是應(yīng)用最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，本章也是這門課程的重點。 基本概念中，連通分量，生成樹，鄰接點是重點。 連通圖： 在無向圖中 , 若從頂點 v1 到頂點 v2 有路徑 , 則稱頂點 v1 與 v2 是連通的。 如果圖中任意一對頂點都是連通的 , 則稱此圖是連通圖

28、。 非連通圖的極大連通子圖叫做 連通分量。 生成樹： 是一個極小連通子圖，它含有圖中全部n 個頂點，但只有 n-1 條邊。 鄰接點： 若 （u, v） 是 E（G） 中的一條邊，則稱 u 與 v 互為鄰接頂點。 圖是復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，也有順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)：數(shù)組表示法（重點是鄰接距陣） 和鄰接表。這兩種存儲結(jié)構(gòu)對有向圖和無向圖均適用 圖的遍歷是圖的各種算法的基礎(chǔ)，應(yīng)熟練掌握圖的深度、廣度優(yōu)先遍歷。應(yīng)熟練掌 連通圖的最小生成樹不是唯一的，但最小生成樹邊上的權(quán)值之和是唯一的。握 prim 和 kruscal 算法，特別是手工分步模擬生成樹的生成過程。 從單源點到其他頂點，以及各個頂點間的最短路徑

29、問題，掌握熟練手工模擬。補充：1. 問：當(dāng)有向圖中僅 1 個頂點的入度為 0,其余頂點的入度均為 1，此時是何形狀 答：是樹！而且是一棵有向樹！2. 討論：鄰接表與鄰接矩陣有什么異同之處1. 聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行， 鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2. 區(qū)別： 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致） ， 但鄰接表不唯一（鏈接次序與頂點編號無關(guān)） 。3. 用途： 鄰接矩陣多用于稠密圖的存儲 而鄰接表多用于稀疏圖的存儲3. 若對連通圖進(jìn)行遍歷，得到的是生成樹 若對非連通圖進(jìn)行遍歷，得到的是生成森林。第八章 查找內(nèi)容提要： 查找表是稱為集合的數(shù)

30、據(jù)結(jié)構(gòu)。是元素間約束力最差的數(shù)據(jù)結(jié)構(gòu)：元素間的關(guān)系是 僅共在同一個集合中。 （同一類型的數(shù)據(jù)元素構(gòu)成的集合） 查找表的操作：查找，插入，刪除。 靜態(tài)查找表：順序表，有序表等。針對靜態(tài)查找表的查找算法主要有一、順序查找（線性查找） 技巧：把待查關(guān)鍵字 int Search_Seq（ SSTable ST , KeyType 0.key =key;for（ i=; i .key!=key; - - i ）;return i;:順序查找、折半查找、分塊查找key 存入表頭或表尾（俗稱“哨兵”key ），這樣可以加快執(zhí)行速度。PL s p PR fm1 j 1ASL j 2j 1nj1n1nlog 2

31、(n 1) 1log2n找的過程是怎樣的給定一個值 K，在含有 n 個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于K 的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。2.對查找表常用的操作有哪些查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。3. 哪些查找方法 查找方法取決于表中數(shù)據(jù)的排列方式 ;4. 如何評估查找方法的優(yōu)劣 用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度ASL。ASL= Pi. Ci5. 使用折半查找算法時，要求被查文件：采用順序存貯結(jié)構(gòu)、記錄按關(guān)鍵字遞增有序6. 將線性表構(gòu)造成二叉排序樹的優(yōu)點： 查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高； 中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列（即實現(xiàn)了排序運算） ； 如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點上，而且插入或刪除 時只需修改指針而不需移動元素。第九章 內(nèi)部排序內(nèi)容提要： 排序的定義，排序可以看作是線性表的一種操作排序:將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次