數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版復(fù)習(xí)重點(diǎn)

1、數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)復(fù)習(xí)重點(diǎn)重點(diǎn)在二、三、六、七、九、十章，考試內(nèi)容兩大類：概念，算法 第1章、緒論1. 數(shù)據(jù)：是對(duì)客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。2. 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。3. 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。其4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)4. 邏輯結(jié)構(gòu)：是數(shù)據(jù)元素之間的邏輯關(guān)系的描述。5. 物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）：是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像）。其4種存儲(chǔ)結(jié)構(gòu)：順序存數(shù)結(jié)構(gòu)、鏈?zhǔn)酱鏀?shù)結(jié)構(gòu)、索引存數(shù)結(jié)構(gòu)、散列存數(shù)結(jié)構(gòu)6

2、. 算法：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。其5個(gè)重要特性：有窮性、確定性、可行性、輸入、輸出7. 時(shí)間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n),算法的時(shí)間度量記作，t(n)=o(f(n) ；他表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱做算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。例如： (a) +x;s=0;(b) for(i=1;i<=n;+i)+x;s += x;(c) for(j=1;j<=n;+j)for(k=1;k<=n;+k)+x;s += x;含基本操作“x增1

3、”的語(yǔ)句的頻度分別為1、n和n²，則這3個(gè)程序段的時(shí)間復(fù)雜度分別為o(1)、o(n)和o(n²)，分別稱為常量階、線性階和平方階。還可呈現(xiàn)對(duì)數(shù)階o(log n)、指數(shù)階o(2的n次方)等。8. 空間復(fù)雜度：算法所需存儲(chǔ)空間的度量記作，s(n)=o(f(n)。 第2章、線性表1. 線性表：是最常用最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)，一個(gè)線性表是n個(gè)數(shù)據(jù)元素的有限序列。2. 線性表的順序存儲(chǔ)結(jié)構(gòu)：是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。其特點(diǎn)為邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也相鄰，可以隨機(jī)存取表中任一元素。存儲(chǔ)位置計(jì)算：假設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，并以所占的第一

4、個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置，線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為loc(ai)=loc(a1)+(i-1)*l 式中l(wèi)oc(a1)是線性表第一個(gè)元素a1的存儲(chǔ)位置，通常稱做線性表的起始位置或基地址。3. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的)。數(shù)據(jù)元素ai的存儲(chǔ)映像稱為結(jié)點(diǎn)，包括2個(gè)域：存數(shù)據(jù)的數(shù)據(jù)域、存后繼存儲(chǔ)位置的指針域。1) 線性鏈表(單鏈表)特點(diǎn)：每個(gè)結(jié)點(diǎn)只包含1個(gè)指針域。在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)。假設(shè)l是linklist型變量，則l為單鏈表的頭指針，它指向表中第一個(gè)結(jié)點(diǎn)；

5、l->next為第一個(gè)結(jié)點(diǎn)地址，l->next=null為空表。生成結(jié)點(diǎn)：p=(linklist)malloc(sizeof(lnode)回收結(jié)點(diǎn)：free(q)2) 循環(huán)鏈表特點(diǎn)：表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。循環(huán)鏈表的操作與線性鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空，而是它們是否等于頭指針。3) 雙向鏈表特點(diǎn)：有2個(gè)指針域，其一指向直接后繼，另一指向直接前趨。第3章、棧和隊(duì)列1. 棧：是限定僅在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱為棧頂，表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為后進(jìn)先出的線性表。2.

6、隊(duì)列：是一種先進(jìn)先出的線性表，它只允許在表的一端進(jìn)行插入，而另一端刪除元素。允許插入的一端叫做隊(duì)尾，允許刪除的一端則稱為隊(duì)頭。1) 鏈隊(duì)列：用鏈表示的隊(duì)列。一個(gè)隊(duì)列需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針（分別成為頭指針和尾指針）才能確定唯一。和單鏈表一樣，也給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，并令頭指針指向頭結(jié)點(diǎn)。2) 循環(huán)隊(duì)列：與順序棧類似，除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素及隊(duì)列尾元素的位置。初始化建空隊(duì)列時(shí)，令front = rear = 0，每當(dāng)插入新的隊(duì)列尾元素時(shí)，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時(shí)，“頭指針增1”。

7、第4章、串1. 串：是由零個(gè)或多個(gè)字符組成的有限序列。第5章、數(shù)組和廣義表1. 數(shù)組特點(diǎn)：與線性表一樣，所有數(shù)據(jù)元素都必須屬于同一數(shù)據(jù)類型。2. 數(shù)組的順序存儲(chǔ)結(jié)構(gòu)：由于數(shù)組一般不作插入或刪除操作，一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)據(jù)元素個(gè)數(shù)和元素之間的關(guān)系就不會(huì)發(fā)生變動(dòng)，因此采用順序存儲(chǔ)結(jié)構(gòu)表示數(shù)組。存儲(chǔ)位置計(jì)算：假設(shè)每個(gè)數(shù)據(jù)元素需占用l個(gè)存儲(chǔ)單元，則二維數(shù)組a中任一元素aij的存儲(chǔ)位置可由下式確定以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)：loc(i,j)=loc(0,0)+(b2*i+j)*l以列序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)：loc(i,j)=loc(0,0)+(b2*j+i)*l式中l(wèi)oc(i,j)是aij的存儲(chǔ)位置；l

8、oc(0,0)是a00的存儲(chǔ)位置，即二維數(shù)組a的起始存儲(chǔ)位置，也稱基地址或基址；b2在以行序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)時(shí)為每行存儲(chǔ)元素的個(gè)數(shù)(列數(shù))，在以列序?yàn)橹餍虻拇鎯?chǔ)結(jié)構(gòu)時(shí)為每列存儲(chǔ)元素的個(gè)數(shù)(行數(shù))。3. 廣義表：是線性表的推廣，也有人稱其為列表（lists，用復(fù)數(shù)形式以示與統(tǒng)稱的表list的區(qū)別）。記作ls=(a1,a2,an) ，其中l(wèi)s是廣義表(a1,a2,an)的名稱，n是它的長(zhǎng)度。在線性表的定義中，ai(1in)只限于是單個(gè)元素。而在廣義表的定義中，ai可以是單個(gè)元素，也可以是廣義表，分別稱為廣義表ls的原子和子表。例如：第6章、樹(shù)和二叉樹(shù)1. 二叉樹(shù)：是一種樹(shù)型的結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)

9、點(diǎn)至多只有兩棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。2. 二叉樹(shù)的性質(zhì)：1) 性質(zhì)1：在二叉樹(shù)的第i層上至多有2的i減1次方個(gè)結(jié)點(diǎn)(i1)。2) 性質(zhì)2：深度為k的二叉樹(shù)至多有2的k次方減1個(gè)結(jié)點(diǎn)(k1)。深度為k的二叉樹(shù)至少有k個(gè)結(jié)點(diǎn)(k1)。深度為k的完全二叉樹(shù)至少有2的k次方減2的k減1次方個(gè)結(jié)點(diǎn)(k1)。3) 性質(zhì)3：對(duì)任何一棵二叉樹(shù)t，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。4) 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。5) 性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為log2n+1）的

10、結(jié)點(diǎn)按層序編號(hào)（從第1層到第log2n+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i（1in）有：a) 如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親parent(i)是結(jié)點(diǎn)i/2。b) 如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子lchild(i)是結(jié)點(diǎn)2i。c) 如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子rchild(i)是結(jié)點(diǎn)2i+1。3. 滿二叉樹(shù)：一顆深度為k且有 2的k次方減1個(gè)結(jié)點(diǎn)的二叉樹(shù)。4. 完全二叉樹(shù)：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。5. 遍歷二叉樹(shù)：

11、1) 根據(jù)二叉樹(shù)寫遍歷結(jié)果：a) 先序遍歷（先根遍歷）：dlr- + a * b - c d / e fb) 中序遍歷（中根遍歷）：ldra + b * c - d - e / fc) 后序遍歷（后根遍歷）：lrda b c d - * + e f / -2) 根據(jù)遍歷結(jié)果畫二叉樹(shù)：一棵二叉樹(shù)的先序、中序和后序序列分別如下，其中有部分未給出，試求出空格處的結(jié)點(diǎn)字符，并畫出該二叉樹(shù)。先序：_b_ehi_fg_k中序：d_heia_cjg_后序：_h_ebf_kg_a解題思路：a) 由先序或后序確定根結(jié)點(diǎn)；如本題后序最后一個(gè)為a，根結(jié)點(diǎn)為a，所以先序第一個(gè)空就為a。b) 在中序找出根結(jié)點(diǎn)，根結(jié)點(diǎn)左

12、側(cè)為左子樹(shù)，右側(cè)為右子樹(shù)；如本題d_hei為左子樹(shù)，_cjg_為右子樹(shù)。c) 由先序確定緊跟在根結(jié)點(diǎn)后的左子樹(shù)根；如本題緊跟在a后的是b，b為左子樹(shù)根，中序根結(jié)點(diǎn)的左子樹(shù)只有一個(gè)空，所以為b。d) 繼續(xù)由中序確定左子樹(shù)根的左右子樹(shù)，左側(cè)為左子樹(shù)，右側(cè)為右子樹(shù)；如本題b的左子樹(shù)為d，右子樹(shù)為hei，所以先序第二個(gè)空為d。e) 重復(fù)c)、d)步驟確定整棵左子樹(shù)；如本題先序中緊跟在d后的是e，e為b的右子樹(shù)，由中序中看出e左子樹(shù)為h，右子樹(shù)為i，補(bǔ)充后序填空，前兩空分別為d和i。f) 由后序確定右子樹(shù)根的左子樹(shù)，再由中序確定右子樹(shù)根；如本題緊跟在b后的是f，f為右子樹(shù)根的左子樹(shù)，已知中序_cjg_為

13、右子樹(shù)，f只可能第一個(gè)空，那第二個(gè)空為k，補(bǔ)全先序、中序、后序填空并可畫出二叉樹(shù)。6. 森林與二叉樹(shù)的轉(zhuǎn)換：1) 樹(shù)轉(zhuǎn)換成二叉樹(shù)：連兄弟，留長(zhǎng)子，刪孩子。a) 連線，連接所有兄弟結(jié)點(diǎn)。b) 刪線，僅保留雙親與長(zhǎng)子結(jié)點(diǎn)的連線，刪除與其他孩子結(jié)點(diǎn)之間的連線。c) 整理，原有的長(zhǎng)子結(jié)點(diǎn)為左子樹(shù)，從兄弟轉(zhuǎn)換為孩子的結(jié)點(diǎn)為右子樹(shù)。d) 注意，由于樹(shù)根沒(méi)有兄弟結(jié)點(diǎn)，固樹(shù)轉(zhuǎn)換為二叉樹(shù)后，二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)必為空。2) 森林轉(zhuǎn)換成二叉樹(shù)：連樹(shù)根及兄弟，留長(zhǎng)子，刪孩子。a) 連線，連接每棵樹(shù)的根結(jié)點(diǎn)及所有兄弟結(jié)點(diǎn)。b) 刪線，僅保留雙親與長(zhǎng)子結(jié)點(diǎn)的連線，刪除與其他孩子結(jié)點(diǎn)之間的連線。c) 整理，第一棵樹(shù)根結(jié)點(diǎn)

14、為二叉樹(shù)根結(jié)點(diǎn)，原有的長(zhǎng)子結(jié)點(diǎn)為左子樹(shù)，從兄弟轉(zhuǎn)換為孩子的結(jié)點(diǎn)為右子樹(shù)。3) 二叉樹(shù)轉(zhuǎn)換成樹(shù)：連左孩子的右孩子及其右孩子，刪原樹(shù)右孩子。a) 連線，若某結(jié)點(diǎn)x存在左孩子xl，則將這個(gè)左孩子的右孩子結(jié)點(diǎn)xlr、左孩子的右孩子的右孩子結(jié)點(diǎn)xlrr、左孩子的右孩子的右孩子的右孩子結(jié)點(diǎn)xlrrr都與x結(jié)點(diǎn)連線。b) 刪線，刪除原二叉樹(shù)的所有雙親與右孩子結(jié)點(diǎn)的連線。c) 整理，原二叉樹(shù)根結(jié)點(diǎn)為樹(shù)根結(jié)點(diǎn)。4) 二叉樹(shù)轉(zhuǎn)換成森林：連左孩子的右孩子及其右孩子，刪原樹(shù)右孩子。a) 連線，若某結(jié)點(diǎn)x存在左孩子xl，則將這個(gè)左孩子的右孩子結(jié)點(diǎn)xlr、左孩子的右孩子的右孩子結(jié)點(diǎn)xlrr、左孩子的右孩子的右孩子的右孩子

15、結(jié)點(diǎn)xlrrr都與x結(jié)點(diǎn)連線。b) 刪線，刪除原二叉樹(shù)的所有雙親與右孩子結(jié)點(diǎn)的連線。c) 整理，調(diào)整為多棵樹(shù)的森林。7. 赫夫曼樹(shù)：又稱最優(yōu)樹(shù)，是一類帶權(quán)路徑長(zhǎng)度最短的樹(shù)。a) 兩個(gè)最小數(shù)值組成一對(duì)，小的在前，大的在后；如上圖中2與4最小，2在前，4在后。b) 將兩個(gè)最小數(shù)值的和算作一個(gè)數(shù)，再與其他數(shù)重復(fù)a)步驟；如上圖中2與4的和為6，5與6最小，5在前，6在后。c) 最后計(jì)算wpl，它等于每個(gè)數(shù)值乘以從根結(jié)點(diǎn)到這個(gè)數(shù)值的連線個(gè)數(shù)的積之和；如上圖中wpl=2*3+4*3+5*2+7*1=35。8. 赫夫曼編碼：a) 在赫夫曼樹(shù)上，左分支代表0，右分支代表1。b) 由根結(jié)點(diǎn)到指定結(jié)點(diǎn)的路徑(從

16、上到下把0、1連起來(lái))，就是該結(jié)點(diǎn)的赫夫曼編碼；如上圖(d)中a為0，b為10，c為110，d為111。第7章、圖1. 圖：多個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個(gè)數(shù)據(jù)元素之間都有可能相關(guān)。2. 無(wú)向完全圖：有n(n-1)/2條邊的無(wú)向圖。3. 有向完全圖：有n(n-1)條邊的有向圖。4. 入度：以頂點(diǎn)v為頭的弧的數(shù)目稱為v的入度。5. 出度：以v為尾的弧的數(shù)目稱為v的出度。6. 連通圖：在無(wú)向圖中，任意兩個(gè)頂點(diǎn)之間都有路徑。7. 連通分量：在無(wú)向圖中的極大連通子圖。8. 鄰接矩陣：無(wú)向圖的鄰接矩陣關(guān)于主對(duì)角線對(duì)稱，在整個(gè)矩陣中非零元素的個(gè)數(shù)等于邊個(gè)數(shù)的2倍，第i行和第i列中非零元素

17、的個(gè)數(shù)等于該結(jié)點(diǎn)的度。9. 鄰接表：無(wú)向圖的鄰接矩陣關(guān)于主對(duì)角線對(duì)稱，在整個(gè)矩陣中非零元素的個(gè)數(shù)等于邊個(gè)數(shù)的2倍，第i行和第i列中非零元素的個(gè)數(shù)等于該結(jié)點(diǎn)的度。10. 深度優(yōu)先遍歷：從圖中某個(gè)頂點(diǎn)出發(fā)，搜索與之相關(guān)聯(lián)的頂點(diǎn)，選擇一個(gè)訪問(wèn)（從左到右，從上到下）；再?gòu)脑擁旤c(diǎn)出發(fā)，搜索與之相關(guān)聯(lián)且未訪問(wèn)過(guò)的頂點(diǎn)，選擇一個(gè)訪問(wèn)；重復(fù)上步驟，直到?jīng)]有相關(guān)聯(lián)且未訪問(wèn)過(guò)的頂點(diǎn)；后退一個(gè)頂點(diǎn)繼續(xù)搜索訪問(wèn)，直到所有頂點(diǎn)都被訪問(wèn)過(guò)。a) 從v0出發(fā)，先找到v0的關(guān)聯(lián)頂點(diǎn)v3。b) 由v3出發(fā)，找到v1；由v1出發(fā)，沒(méi)有關(guān)聯(lián)的頂點(diǎn)。c) 回到v3，從v3出發(fā)，找到v2；由v2出發(fā)，沒(méi)有關(guān)聯(lián)的頂點(diǎn)。d) 回到v3，再

18、回到v0，由v0出發(fā)，找到v4。e) 從v4出發(fā)，找到v1，因?yàn)関1已經(jīng)被訪問(wèn)過(guò)了，所以不訪問(wèn)。所以最后順序是v0, v3, v1, v2, v4。11. 廣度優(yōu)先遍歷：從圖中某個(gè)頂點(diǎn)出發(fā)，搜索與之相關(guān)聯(lián)的頂點(diǎn)，逐個(gè)訪問(wèn)（從左到右，從上到下）；再?gòu)倪@些頂點(diǎn)出發(fā)，搜索與之相關(guān)聯(lián)且未訪問(wèn)過(guò)的頂點(diǎn)，逐個(gè)訪問(wèn)；重復(fù)上步驟，直到所有頂點(diǎn)都被訪問(wèn)過(guò)。a) 從v0出發(fā)，先找到v0的關(guān)聯(lián)頂點(diǎn)v3、v4。b) 由v3出發(fā)，找到v1、v2；由v4出發(fā)，找到v1，因?yàn)関1已經(jīng)被訪問(wèn)過(guò)了，所以不訪問(wèn)。c) 由v1出發(fā)，沒(méi)有關(guān)聯(lián)的頂點(diǎn)；由v2出發(fā)，沒(méi)有關(guān)聯(lián)的頂點(diǎn)。所以最后順序是v0, v3, v4, v1, v2。12

19、. 最小生成樹(shù)：1) 普里姆算法：連相鄰權(quán)值最小的。2) 克魯斯卡爾算法：先連權(quán)值最小的，再依次連。13. 拓?fù)渑判颍河赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序的操作。14. 關(guān)鍵路徑：路徑長(zhǎng)度最長(zhǎng)的路徑。1) 如圖，先求各事件的最早發(fā)生時(shí)間（順序?yàn)関1v9）v1的最早發(fā)生時(shí)間為0，v2的最早發(fā)生時(shí)間為6，v3的最早發(fā)生時(shí)間為4，v4的最早發(fā)生時(shí)間為5。對(duì)于v5，需要v2，v3均發(fā)生，v2發(fā)生且完成的時(shí)間為6+1=7；v3發(fā)生且完成的時(shí)間為4+1=5，因而v5的最早發(fā)生時(shí)間為7。同理可求出各頂點(diǎn)的最早發(fā)生時(shí)間：v1v2v3v4v5v6v7v8v9e(i)0645771614182) 求各事件

20、的最晚發(fā)生時(shí)間（順序?yàn)関9v1）v9的最晚時(shí)間為18，v8的最晚時(shí)間為18-a11=14，v7的最晚時(shí)間為18-a10=16，v6的最晚時(shí)間為14-a9=10，v5的最晚時(shí)間為v7的最晚時(shí)間減去a7和v8的最晚時(shí)間減去a8兩者較小的，則v5的最晚時(shí)間為7，同理可得其他頂點(diǎn)的最晚發(fā)生時(shí)間：v1v2v3v4v5v6v7v8v9l(i) 0668710161418則li與ei相等的事件即為關(guān)鍵事件即：v1，v2，v5，v7，v8，v9可得關(guān)鍵路徑：v1，v2，v5，v7，v9或v1，v2，v5，v8，v93) 求各活動(dòng)的最早發(fā)生時(shí)間a1a2a3a4a5a6a7a8a9a10a11e(i)000645

21、77716144) 求各活動(dòng)的最晚發(fā)生時(shí)間a1a2a3a4a5a6a7a8a9a10a11l(i)6-6=06-4=28-5=37-1=67-1=610-2=816-9=714-7=714-4=1018-2=1618-4=14則li與ei相等的活動(dòng)即為關(guān)鍵活動(dòng)即：a1，a4，a7，a8，a10，a11可得關(guān)鍵路徑：v1，v2，v5，v7，v9或v1，v2，v5，v8，v915. 最短路徑：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過(guò)的路徑中，各邊上權(quán)值之和最小的一條路徑。1) 迪杰斯特拉算法：2) 弗洛伊德算法：方法：兩條線，從左上角開(kāi)始計(jì)算一直到右下角 如下所示：給出矩陣，其中矩陣a是鄰接矩陣，

22、而矩陣path記錄u,v兩點(diǎn)之間最短路徑所必須經(jīng)過(guò)的點(diǎn)。最后a3即為所求結(jié)果。第9章、查找1. 查找表：是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。2. 關(guān)鍵字：是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。3. 靜態(tài)查找表：查詢某個(gè)特定的數(shù)據(jù)元素是否在查找表中，檢索某個(gè)特定的數(shù)據(jù)元素的各種屬性。1) 順序查找法：從表中最后一個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之若直至第一個(gè)記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒(méi)有所查記錄，查找不成功。其存儲(chǔ)結(jié)構(gòu)要求：以順序表或線性鏈表表示的

23、靜態(tài)查找表。其平均查找長(zhǎng)度：假設(shè)每個(gè)記錄的查找概率相等，即pi=1/n，則在等概率情況下順序查找的平均查找長(zhǎng)度為，asl=(n+1)/2。2) 折半查找法（二分查找法）：先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。其存儲(chǔ)結(jié)構(gòu)要求：以有序表表示的靜態(tài)查找表。其平均查找長(zhǎng)度：假設(shè)表中每個(gè)記錄的查找概率相等（pi=1/n），則查找成功時(shí)折半查找的平均查找長(zhǎng)度為，asl=(n+1)/n*log2(n+1)-1。3) 索引順序表查找法（分塊查找法）：先確定待查記錄所在的塊（子表），然后在塊中順序查找。其存儲(chǔ)結(jié)構(gòu)要求：以索引順序表表示的靜態(tài)查找表。其平均查找長(zhǎng)度：將長(zhǎng)度為

24、n的表均勻地分成b塊，每塊含有s個(gè)記錄，即b=n/s；又假設(shè)表中每個(gè)記錄的查找概率相等，則每塊查找概率為1/b，塊中每個(gè)記錄的查找概率為1/s，若用順序查找確定所在塊，則分塊查找的平均查找長(zhǎng)度為，asl=(n/s+s)/2+1；若用折半查找確定所在塊，則分塊查找的平均查找長(zhǎng)度為，asllog2(n/s+1)+s/2。4. 動(dòng)態(tài)查找表：在查找過(guò)程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素。1) 二叉排序樹(shù)：或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)：1、若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；2、若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于

25、它的根結(jié)點(diǎn)的值；3、它的左、右子樹(shù)也分別為二叉排序樹(shù)。2) 平衡二叉樹(shù)（avl樹(shù)）：它或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)：它的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和右子樹(shù)的深度之差的絕對(duì)值不超過(guò)1。若將二叉樹(shù)上結(jié)點(diǎn)的平衡因子bf定義為該結(jié)點(diǎn)的左子樹(shù)的深度減去它的右子樹(shù)的深度，則平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是 -1、0和1。只要二叉樹(shù)上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹(shù)就是不平衡的。下面即四種情況分別為：左左、右右、左右、右左，每種情況又有兩個(gè)圖、，是該情況的最簡(jiǎn)單的圖形，是該情況的一般的圖形。設(shè)x為最小不平衡子樹(shù)的根結(jié)點(diǎn)，y為剛插入的點(diǎn)左左：即在x的左孩子a的左孩

26、子c上插入一個(gè)結(jié)點(diǎn)y（該結(jié)點(diǎn)也可以是c,如圖），即y可以是c，也可以是c的左孩子（如圖），也可以是c的右孩子（不在畫出）。圖就不用說(shuō)了，結(jié)點(diǎn)x和結(jié)點(diǎn)a變換，則樹(shù)平衡了；那么圖就是樹(shù)中的一般情況了a結(jié)點(diǎn)有右孩子d，那要進(jìn)行x和a變換，那么a的右孩子放哪啊？很簡(jiǎn)單，如圖放在x的左孩子上；分析：x>d,d>a,所以d可作為x的左孩子，且可作為a的右孩子中的孩子。下邊這樣的類似情況不再一一分析，自己分析分析實(shí)現(xiàn)：找到根結(jié)點(diǎn)x，與它的左孩子a進(jìn)行交換即可使二叉樹(shù)樹(shù)再次平衡；右右：即在x的右孩子a的右孩子c上插入一個(gè)結(jié)點(diǎn)y（該結(jié)點(diǎn)也可以是c,如圖），即y可以是c，也可以是c的右孩子（如圖），也

27、可以是c的左孩子（不在畫出）。實(shí)現(xiàn)：找到根結(jié)點(diǎn)x，與它的右孩子a進(jìn)行交換即可使二叉樹(shù)樹(shù)再次平衡；左右：即在x的左孩子a的右孩子c上插入一個(gè)結(jié)點(diǎn)y（該結(jié)點(diǎn)也可以是c,如圖），即y可以是c，也可以是c的右孩子（如圖），也可以是c的左孩子（不在畫出）。這個(gè)左右和下邊的右左，稍微復(fù)雜了點(diǎn)，需要進(jìn)行兩次交換，才能達(dá)到平衡，注意這時(shí)y是c的右孩子，最終y作為x的左孩子；若y是c的左孩子，最終y作為a的右孩子，畫圖分析一下下邊類似，不再敖述。實(shí)現(xiàn)：找到根結(jié)點(diǎn)x，讓x的左孩子a與x的左孩子a的右孩子c進(jìn)行交換，然后再讓x與x此時(shí)的左孩子c進(jìn)行交換，最終達(dá)到平衡；右左：即在x的右孩子a的左孩子c上插入一個(gè)結(jié)點(diǎn)y

28、（該結(jié)點(diǎn)也可以是c,如圖），即y可以是c，也可以是c的右孩子（如圖），也可以是c的左孩子（不在畫出）。實(shí)現(xiàn)：找到根結(jié)點(diǎn)x，讓x的右孩子a與x的右孩子a的左孩子c進(jìn)行交換，然后再讓x與x此時(shí)的右孩子c進(jìn)行交換，最終達(dá)到平衡； 上邊的四種情況包含了所有插入時(shí)導(dǎo)致不平衡的情況，上面給出的僅僅是一棵大樹(shù)中的最小不平衡子樹(shù)，一定要想清楚，別迷了！另外一定要注意這個(gè)交換操作，比如a與b交換（a在上，b在下），b一定要占據(jù)a的位置！什么意思？就是b要放在（覆蓋）儲(chǔ)存a的那塊內(nèi)存上，再通俗點(diǎn)說(shuō)，若a是x的左孩子，則交換后b要做x的左孩子；這就是所謂的b占據(jù)a的位置！5. 哈希表：1) 構(gòu)造方法：a) 直接定址

29、法：取關(guān)鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為散列地址。即h(key)=key或h(key) = a·key + b，其中a和b為常數(shù)（這種散列函數(shù)叫做自身函數(shù)）。若其中h(key）中已經(jīng)有值了，就往下一個(gè)找，直到h(key）中沒(méi)有值了，就放進(jìn)去。b) 數(shù)字分析法：分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時(shí)我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會(huì)很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來(lái)構(gòu)成散列地址，則沖突的幾率會(huì)明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來(lái)構(gòu)造沖突幾率較低的散列地址。c) 平方取中法

30、：當(dāng)無(wú)法確定關(guān)鍵字中哪幾位分布較均勻時(shí)，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。d) 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對(duì)齊，然后相加；間界疊加是從一端向另一端沿分割界來(lái)回折疊，然后對(duì)齊相加。e) 除留余數(shù)法：取關(guān)鍵字被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址。即 h(key) = key mod p,p<=m。不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。對(duì)p的選擇很重要，一般取素?cái)?shù)或m，若p選的不好，容易產(chǎn)生同義詞。2) 處理沖突方法：a) 開(kāi)放定址法：hi=(h(key) + di) mod m,i=1,2，k(k<