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

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

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

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

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

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

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

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

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

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

10、數(shù)組的處理比其它復(fù)雜的結(jié)構(gòu)要簡(jiǎn)單” ，對(duì)嗎 答：對(duì)的。因?yàn)?數(shù)組中各元素具有 統(tǒng)一的類型； 數(shù)組元素的下標(biāo)一般具有 固定的上界和下界 ，即數(shù)組一旦被定義，它的維數(shù)和維界就不 再改變。 數(shù)組的 基本操作比較簡(jiǎn) 單，除了結(jié)構(gòu)的初始化和銷毀之外， 只有存取元素和修改元素值的 操作。10. 三元素組表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)于稀疏矩陣的一個(gè)非零元素，它包含有三個(gè)數(shù)據(jù)項(xiàng)，分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。11. 寫(xiě)出右圖所示稀疏矩陣的壓縮存儲(chǔ)形式。法 2：用十字鏈表表示用途：方便稀疏矩陣的加減運(yùn)算方法：每個(gè)非 0 元素占用 5 個(gè)域法 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 種存儲(chǔ)形式。法 3：用三元組矩陣表示：稀疏矩陣壓縮存儲(chǔ)的缺點(diǎn)：將失去隨機(jī)存取功能 代碼：a， b，c， z），寫(xiě)出在順序結(jié)構(gòu)上生成1. 用數(shù)組 V來(lái)存放 26 個(gè)英文字母組成的線性表（ 和顯示該表的 C 語(yǔ)言程序。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è)計(jì)隊(duì)列它有什么獨(dú)特用途 離散事件的模擬（模擬事件發(fā)生的先后順序,例如 CPU 芯片中的指令譯碼隊(duì)列） 操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè) CPU 執(zhí)行多個(gè)作業(yè)） ； 簡(jiǎn)化程序設(shè)計(jì)。3. 什么叫“假溢出” 如何解決 答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界， 不能再有入隊(duì)操作， 但其實(shí)數(shù)組中還有空 位置，這就叫“假溢出” 。解決假溢出的途徑采用循環(huán)隊(duì)列。4. 在一個(gè)循環(huán)隊(duì)列中， 若約定隊(duì)首指針指向隊(duì)首元素的前一個(gè)位置。那么， 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先 移動(dòng)隊(duì)首位置 ，后 取出元素 。5. 線性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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