數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)要點(diǎn)

1、A熟練掌握B理解C了解第一章：緒論1. 基本概念：包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的相關(guān)運(yùn)算。四類數(shù)據(jù)組織結(jié)構(gòu)：集合、線性表、樹形、圖狀結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)方式：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。BCC2.算法和分析算法的特征、時(shí)間復(fù)雜度的分析和常見的時(shí)間復(fù)雜度增長(zhǎng)率排序、空間復(fù)雜度本章重點(diǎn)：分析算法時(shí)間復(fù)雜度例 1. 下面關(guān)于算法說法錯(cuò)誤的是（）A算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)BB. 為解決某問題的算法同為該問題編寫的程序含義是相同的C. 算法的可行性是指指令不能有二義性D.以上幾個(gè)都是錯(cuò)誤的D例 2.A棧以下那一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？（B.哈希表C.線索樹D.）雙向鏈表A例 3. 求下段程序的時(shí)間

2、復(fù)雜度：void mergesort(int i, int j)int m;if(i!=j)m=(i+j)/2;mergesort(i,m);mergesort(m+1,j);merge(i,j,m);其中 mergesort()用于對(duì)數(shù)組 an 歸并排序，調(diào)用方式為mergesort(0,n-1); ， merge()用于兩個(gè)有序子序列的合并，是非遞歸函數(shù)，時(shí)間復(fù)雜度為O(n) 。解：分析得到的時(shí)間復(fù)雜度的遞歸關(guān)系：t( n)O(1)n 12t(n / 2) O(n)n1O(n) 為 merge（）所需的時(shí)間，設(shè)為cn（ c 為常量）。因此t( n)2( n / 2)cn2(2t (n /

3、22 )cn / 2) cn22 t( n / 22 )2cn .2k t(n / 2k )kcn令n1 ，有 klog 2 n2k有 t( n)2log 2 n O (1)cn log 2 nncn log 2 nO (n log 2 n)第二章：線性表1. 性表的基本運(yùn)算： .C2. 性表的 序存 （利用靜 數(shù) 或 內(nèi)存分配）。相 的表示與操作A3. 性表的 式存 。相 的表示與操作。包括循 表、雙向 表。A4. 序存 與 式存 的比 ：基于 的考 -分 適用于靜 的和 的操作：比如靜 找和插入 除） ；基于空 的考 - .B 也適用于后面用兩種方式存 的其他數(shù)據(jù) 構(gòu)。本章重點(diǎn)：很熟悉 序

4、表， 表、雙 表，循 表的基本操作；并學(xué)會(huì)在各種 表上 行一些算法 （與基本操作 似的操作或 合）， 仔 復(fù) 。例 4 假 有兩個(gè)按元素 增次序排列的 性表，均以 表形式存 。 寫算法將 兩個(gè) 表 并 一個(gè)按元素 減次序排列的 表， 并要求利用原來兩個(gè) 表的 點(diǎn)存放 并后的 表。 目分析 因 兩 表已按元素 增次序排列，將其合并 ，均從第一個(gè) 點(diǎn)起 行比 ，將小的 入 表中，同 后移 表工作指 。 要求 果 表按元素 減次序排列。故在合并的同 ，將 表 點(diǎn)逆置。void Union(LinkList la, LinkListlb) la,lb 分 是 點(diǎn)的兩個(gè) 表的 指 ， 表中的元素 按 增

5、序排列，本算法將兩 表合并成一個(gè)按元素 減次序排列的 表。 pa=la-next; pb=lb-next; pa， pb 分 是 表la 和 lb 的工作指 la-next=null; la 作 果 表的 指 ，先將 果 表初始化 空。while(pa!=null & pb!=null)當(dāng)兩 表未 束if(pa-datadata) q=pa-next;將 pa 的后 點(diǎn) 存于 q。 pa-next=la-next; 將 pa 點(diǎn) 于 果表中，同 逆置。 la-next=pa;pa=q;恢復(fù) pa 當(dāng)前待比 點(diǎn)。elseq=pb-next; 將 pb 的后 點(diǎn) 存于 q。 pb-next=la-

6、next; 將 pb 點(diǎn) 于 果表中，同 逆置。 la-next=pb;pb=q; 恢復(fù) pb 當(dāng)前待比 點(diǎn)。while(pa!=null)將 la 表的剩余部分 入 果表，并逆置。q=pa-next; pa-next=la-next; la-next=pa; pa=q; while(pb!=null)q =pb-next; pb-next=la-next; la-next=pb; pb=q; 算法 Union 束。注意 ：（1）此 q 用作 存后 點(diǎn)，操作后pa 或 pb 回原指向位置； 與我 原來不改 或 pb 的指向，增加一個(gè)q=pa 或 pb 作 摘取 點(diǎn) 行添加操作起到的作用一 。（

7、2） 此 要完成逆序插入操作故用 插法（基于 指 la 或 lb），注意尾插法（附 一個(gè)尾指 ，基于 指 插入）的可完成 序插入。（注意：逆序另一種方式也要掌握?。﹑a練習(xí)：練習(xí)題 2編程 1 67.判斷帶頭結(jié)點(diǎn)雙向循環(huán)鏈表L 是否對(duì)稱相等 .8. 設(shè)計(jì)一個(gè)算法判斷單鏈表（帶頭結(jié)點(diǎn)）是否是遞增的（注意比排序算法應(yīng)該簡(jiǎn)單，鏈表排序也要會(huì)實(shí)現(xiàn)）9. 設(shè)計(jì)一個(gè)算法判斷有序表 A 是否是有序表 B 的子集（即表 A 中的元素在 B 中）（。思考：如果遞歸程序怎么寫？ ）第三章：棧與隊(duì)列1.兩種特殊線性表：分別有后進(jìn)先出、先進(jìn)先出的特性。B2.棧的順序表示與實(shí)現(xiàn)（利用靜態(tài)數(shù)組或動(dòng)態(tài)內(nèi)存分配）A注意棧頂指

8、針的初始位置不同，進(jìn)出棧，?？諚M的實(shí)現(xiàn)語句有差別！舉例：若定義typedef struct SElemType*base;SElemType*top;intstacksize;/當(dāng)前棧能使用的最大容量 SqStack;SqStacks;top的初始值指向棧底，即top=base；?？諚l件：s. top =s. base此時(shí)不能出棧棧滿條件： s.top-s.base=s.stacksize進(jìn)棧操作： *s.top+=e;或 *s.top=e; s.top+;退棧操作： e=*-s.top ； 或 s.top-； e=*s.top若定義：typedef struct SElemTypebase

9、MAXSIZE;int top;SqStack;SqStacks;top 的初始值為0 時(shí) :?？諚l件： s. top =0此時(shí)不能出棧棧滿條件： s.top = MAXSIZE進(jìn)棧操作： s.bases.top+=e;退棧操作： e=s.base-s.toptop 的初始值為 -1 時(shí) :棧空條件： s. top = -1此時(shí)不能出棧棧滿條件： s.top = MAXSIZE-1進(jìn)棧操作： s.base+s.top=e;退棧操作： e=s.bases.top-3.棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn)B(對(duì)比順序棧，實(shí)質(zhì)不帶頭結(jié)點(diǎn)的鏈表在頭指針處插入和刪除)4.隊(duì)列的順序表示與實(shí)現(xiàn)循環(huán)隊(duì)列A設(shè)兩個(gè)指針：Q.fr

10、ont指向隊(duì)列頭元素；Q.rear指向隊(duì)列尾元素的下一個(gè)位置注意隊(duì)中若Q.rear 指向隊(duì)列尾元素，進(jìn)出隊(duì)，實(shí)現(xiàn)語句有差別！初始狀態(tài)（空隊(duì)列） ： Q.front = Q.rear=0隊(duì)頭指針進(jìn)1:Q.front = (Q.front + 1)% MAXSIZE隊(duì)尾指針進(jìn)1:Q.rear = (Q.rear + 1)% MAXSIZE;隊(duì)列初始化：Q.front = Q.rear = 0;隊(duì)空條件：Q.front = Q.rear;隊(duì)滿條件： (Q.rear + 1) % MAXSIZE = Q.front隊(duì)列長(zhǎng)度： (Q.rear-Q.front+MAXSIZE)%MAXSIZE6.隊(duì)列的鏈

11、式表示與實(shí)現(xiàn)B本章重點(diǎn) ：順序棧的初始條件、操作，循環(huán)隊(duì)列的初始條件、操作本章難點(diǎn)：棧的設(shè)計(jì)與使用，隊(duì)列的設(shè)計(jì)與使用（主要結(jié)合后面樹和圖中的應(yīng)用復(fù)習(xí)）例 5 鏈棧與順序棧比起來優(yōu)勢(shì)在于。沒有預(yù)設(shè)容量的限制例 6計(jì)算算術(shù)表達(dá)式的值時(shí)，可用兩個(gè)棧作輔助工具。對(duì)于給出的一個(gè)表達(dá)式，從左向右掃描它的字符，并將操作數(shù)放入棧S1 中，運(yùn)算符放入棧 S2 中，但每次掃描到運(yùn)算符時(shí)，要把它同S2 的棧頂運(yùn)算符進(jìn)行優(yōu)先級(jí)比較，當(dāng)掃描到的運(yùn)算符的優(yōu)先級(jí)不高于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，取出棧S1 的棧頂和次棧頂?shù)膬蓚€(gè)元素，以及棧S2 的棧頂運(yùn)算符進(jìn)行運(yùn)算將結(jié)果放入棧 S1 中（得到的結(jié)果依次用T1、T2等表示）。為方便

12、比較，假設(shè)棧S2 的初始棧頂為 ? （ ? 運(yùn)算符的優(yōu)先級(jí)低于加、減、乘、除中任何一種運(yùn)算）?，F(xiàn)假設(shè)要計(jì)算表達(dá)式：A-B*C/D+E/F 。寫出棧 S1 和 S2 的變化過程。步驟棧 S1棧 S2輸入的算術(shù)表達(dá)式（按字符讀入）初始?A-B*C/D+E/F?1A?A-B*C/D+E/F?2A?-B*C/D+E/F?3AB?-B*C/D+E/F?4AB?-*C/D+E/F?5ABC?-*C/D+E/F?6AT1（注： T1=B*C ） ?-/D+E/F?7AT1D?-/D+E/F?8AT2（注： T2=T1/D ） ?-+E/F?T3 （注： T3=A-T2 ） ?+9T3E?+E/F?10T3E

13、?+/F?11T3EF?+/F?12T3T4 （注： T4=E/F ） ?+?T5（注：T5= T3+ T4 ） ?例 7 將兩個(gè)棧存入數(shù)組 V1.m 應(yīng)如何安排最好？這時(shí)?？?、棧滿的條件是什么？，入棧和出棧的操作是什么？分析：為了增加內(nèi)存空間的利用率和減少溢出的可能性， 由兩個(gè)棧共享一片連續(xù)的空間時(shí)，應(yīng)將兩棧的 棧底 分別設(shè)在內(nèi)存空間的兩端， 這樣只有當(dāng) 兩棧頂指針相鄰 （即值之差的絕對(duì)值為 1 時(shí)才產(chǎn)生溢出。設(shè)棧 S1 和棧 S2 共享向量 V1.m ，初始時(shí)，棧S1 的棧頂指針top0=0 ，棧 S2 的棧頂指針top1=m+1 ，當(dāng) top0=0 為棧 S1 空， top1=m+1

14、為棧 S2 空；當(dāng) top0=0 并且 top1=m+1 時(shí)為兩棧全空。當(dāng) top1-top0=1 時(shí)為棧滿。入棧核心操作出棧核心操作S1: V+top0=x1;S1: x1=Vtop0-;S2:S2:V-top1=x2x2=Vtop1+例 8如果用一個(gè)循環(huán)數(shù)組base0.MAX-1表示隊(duì)列時(shí)， 該隊(duì)列只有一個(gè)隊(duì)列頭指針不設(shè)隊(duì)列尾指針rear ，而改置計(jì)數(shù)器count 用以記錄隊(duì)列中結(jié)點(diǎn)的個(gè)數(shù)。front，（ 1）編寫實(shí)現(xiàn)隊(duì)列的三個(gè)基本運(yùn)算：判空、入隊(duì)、出隊(duì)（ 2）隊(duì)列中能容納元素的最多個(gè)數(shù)是多少typedefstruct ElemType baseMAX;intfront,count; /f

15、ront是指向隊(duì)頭元素針，count 是隊(duì)列中元素個(gè)數(shù)。CQueue;/定義類型標(biāo)識(shí)符。(1) 判空： intEmpty(CQueue q)/q是 CQueue類型的變量 if (q.count=0)return (1) ；elsereturn(0); /空隊(duì)列入隊(duì) :intEnQueue(CQueue q， ElemType x) if (q.count=MAX)printf(“隊(duì)滿 n ”) ； exit(0); q.base(q.front+q.count)%MAX=x;/x入隊(duì)q.count+;return(1);/隊(duì)列中元素個(gè)數(shù)增加1, 入隊(duì)成功。出隊(duì) :intDelQueue(CQ

16、ueue q, ElemType &x) if(q.count=0)printf(“隊(duì)空 n ”) ； return(0);x=q.baseq.front;q.front=(q.front+1)%MAX; /計(jì)算新的隊(duì)頭指針q.count-;return(1);(2)隊(duì)列中能容納的元素的個(gè)數(shù)為MAX。第四章：串1.串的基本概念C2.串的順序表示與實(shí)現(xiàn)（兩種存儲(chǔ)方式）A特別的模式匹配算法之KMP算法B本章重點(diǎn)：串的定長(zhǎng)順序存儲(chǔ)和堆分配存儲(chǔ)、掌握一些常規(guī)的串操作（自己會(huì)用和會(huì)編寫）本章難點(diǎn)：串的模式匹配快速算法（KMP ）例 9. 串的定長(zhǎng)順序存儲(chǔ)缺點(diǎn)在于存在情況。截?cái)嗬?10 已知 u= xyx

17、yxyxxyxy ； t= xxy ；ASSIGN （ s， u）；ASSIGN （ v， SUBSTR （ s， INDEX （ s， t）， LEN （ t） +1）；ASSIGN （ m， ww ）求 REPLACE （， m） = _。xyxyxywwy 例 11 14設(shè)字符串 S= aabaabaabaac ， P= aabaac（1）給出 S 和 P 的 next 值和 nextval值；（ 2）若 S作主串， P 作模式串，試給出利用BF算法和 KMP算法的匹配過程。（ 1）（ 1）p 的 next 與 nextval值分別為012123 和 002003。（ 2）利用 BF 算

18、法的匹配過程：第一趟匹配：aabaabaabaacaabaac(i=6,j=6)第二趟匹配：aabaabaabaacaa(i=3,j=2)第三趟匹配：aabaabaabaaca(i=3,j=1)第四趟匹配：aabaabaabaacaabaac(i=9,j=6)第五趟匹配：aabaabaabaacaa(i=6,j=2)第六趟匹配：aabaabaabaaca(i=6,j=1)第七趟匹配：aabaabaabaac利用 KMP算法的匹配過程：第一趟匹配： aabaabaabaacaabaac(i=6,j=6,nextval(j)=3)第二趟匹配： aabaabaabaac(aa)baac (i=9,j

19、=6)第三趟匹配：aabaabaabaac(成功 ) (aa)baac(i=13,j=7)例 12一般串定位函數(shù)Index(S,T,pos),設(shè) S 的串長(zhǎng)為n，T 的串長(zhǎng)為 m,則最壞時(shí)間復(fù)雜度；而改進(jìn)的Index_KMP(S,T,pos)時(shí)間復(fù)雜度為。O(m * n)O( mn)第五章：數(shù)組和廣義表1.數(shù)組的存儲(chǔ)結(jié)構(gòu)：以行為主序、以列為主序的地址映像函數(shù)B2 矩 的 存 ：（1）特殊 ：包括 稱 、三角 、 狀 （利用其特性 存 到一 數(shù) ）B（2）稀疏 利用的是三元 序表來表示B用十字 表表示C（本次考 不做要求）3.廣 表定 與存 表示B （本次考 不做要求）本章重點(diǎn)：地址映像函數(shù)的

20、算（包括數(shù) 和特殊矩 ）例 13已知 n 下三角矩 A（即當(dāng) ij ，有 aij =0），按照 存 的思想，可以將其主 角 以下所有元素 ( 包括主 角 上元素 ) 依次存放于一 數(shù) B 中， 寫出從第一列開始采用列序 主序分配方式 在B 中確定元素aij 的存放位置的公式。答： n 下三角矩 元素Aij （ 1=i,j=j）。第1 列有n 個(gè)元素，第j 列有n-j+1個(gè)元素，第 1 列到第 j-1 列是等腰梯形，元素?cái)?shù) (n+(n-j+2)(j-1)/2 ，而 aij 在第 j 列上的位置是為 i-j+1 。所以 n 下三角矩 A 按列存 ，其元素 aij 在一 數(shù) B 中的存 位置 k 與

21、 i 和j 的關(guān)系 ：k=(n+(n-(j-1)+1)(j-1)/2+(i-j+1)=(2n-j)(j-1)/2+i第六章：二叉樹與樹1.二叉 的定 和性 ：B幾個(gè)特殊的二叉 ： 二叉 、完全二叉 、二叉排序 、平衡二叉 B2.二叉 的 序存 ：C3.二叉 的 式存 ：用二叉 表表示與 A4.二叉 的遍 ：先（中、后）序遍 及 用，相 算法和非 算法A5. 索化二叉 （利用二叉 表n+1 空指 域來存放某遍 下指向 點(diǎn)的直接前 或直接后 ，使得 含更多信息）B6.二叉 的 用：算 表達(dá)式，霍夫曼 （最 二叉 ），判定 B7. 的定 和存 表示： .B8. 和森林和二叉 的 B9. 與森林的遍

22、B本章重點(diǎn)：很熟悉二叉 （在二叉 表表示下）的基本操作的 算法和遍 的非 算法， 仔 復(fù) 。本章 點(diǎn)：二叉 （含排序 、平衡 ）的 算法和非 算法。 索化二叉 及相 操作，重在理解，不考 程！例 14 引入二叉 索 的目的是（）A將非 性序列 化成某種 性序列；加快 找 點(diǎn)的前 或后 的速度B 了能在二叉 中方便的 行插入與 除C 了能方便的找到雙 D使二叉 的遍 果唯一A例 15 二叉 表在 索化后，仍不能有效求解的 是（）。A前（先）序 索二叉 中求前（先）序后 B 中序 索二叉 中求中序后 C中序 索二叉 中求中序前 D 后序 索二叉 中求后序后 D例 16在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造

23、成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A, 并已知A的左孩子的平衡因子為-1 右孩子的平衡因子為0, 則應(yīng)作 ()型調(diào)整以使其平衡。 （平衡因子 =左子樹深度 - 右子樹深度）A. LL（單向右旋）B. LR（先左后右雙向旋轉(zhuǎn)）C. RL（先右后左雙向旋轉(zhuǎn)）D. RR（單向左旋）B例 17 一棵非空的二叉樹其先序序列和后序序列正好相反，畫出這棵二叉樹的形狀。先序序列是“根左右”后序序列是“左右根” ，可見對(duì)任意結(jié)點(diǎn)，若至多只有左子女或至多只有右子女，均可使前序序列與后序序列相反，圖示如下：例 18：已知二叉樹結(jié)點(diǎn)結(jié)構(gòu)如下：用 C 語言表示typedef struct BiNodeElemType d

24、ata;struct BiNode *lchild,*rchild;int val;BiNode,*BiTree;其中 val 域表示該結(jié)點(diǎn)的子孫（含孩子結(jié)點(diǎn)）的個(gè)數(shù)。開始時(shí)，二叉樹根結(jié)點(diǎn)的指針。請(qǐng)寫算法填寫該二叉樹中每個(gè)結(jié)點(diǎn)的valval 域值均為域。0，T為指向某遞歸算法如下：int writeVal(BiNode *root)if(root=NULL)root-val=0;else if(root-lchild=NULL&root-rchild=NULL)root-val=1;elseroot-val=writeVal(root-lchild)+writeVal(root-rchild)

25、;return root-val;例 19編寫一個(gè)算法，將指針S 所指的結(jié)點(diǎn)插入到根結(jié)點(diǎn)指針為存在則不再插入返回0；否則返回1。（遞歸的算法見教材）int Insert_BST( BiTree &T, BiTNode S ) BiTreep, q;/p 指向當(dāng)前訪問的結(jié)點(diǎn)if(!T) T=S;else p=T;while ( p )q = p;/q 指向 p 結(jié)點(diǎn)的雙親結(jié)點(diǎn)T 的二叉排序樹中，若已if (S-data.key data.key)p = p-lchild;else if(S-data.key p-data.key) p = p-rchild;elsep=NULL;if (S-da

26、ta.key = q-data.key)return 0;if (S-data.key data.key)q-lchild = S;else q-rchild = S;return 1;例 20 編寫一個(gè)算法，計(jì)算平衡二叉樹中所有結(jié)點(diǎn)的平衡因子解：計(jì)算一個(gè)結(jié)點(diǎn) bt 的 bf 的值遞歸模型如下：f(bt): bt-bf不存在當(dāng) bt=NULLf(bt): bt-bf=0f(bt): bt-bf=bt當(dāng) bt-lchild=NULL&bt-rchild=NULL的右子樹的高度左子樹的高度其它情況可選用先序的方式統(tǒng)計(jì)出各個(gè)結(jié)點(diǎn)的平衡因子如何求高度呢？遞歸模型如下：f(bt):f(bt):f(bt)

27、:bt不存在當(dāng) bt=NULL當(dāng) bt-lchild=NULL&bt-rchild=NULL的左子樹和右子樹的高度的最大值其它情況int Height(BSTNode *bt)/int max1,max2;if(bt=NULL) return 0;求樹的高度else if(bt-lchild=NULL&bt-rchild=NULL) return 1;elsemax1=Height(bt-lchild);max2=Height(bt-rchild);return max1max2?max1+1:max2+1;void Countbf(BSTNode *&bt) /求所有結(jié)點(diǎn)的bfif(bt!=

28、NULL)if(bt-lchild=NULL&bt-rchild=NULL)bf-bf=0;elseCountbf(bt-lchild);Countbf(bt-rchild);bt-bf= Height(bt-rchild)-Height(bt-lchild);實(shí)質(zhì)上可以將上面求bf 和求高度合二為一。int Countbf1(BSTNode *&bt)/求所有結(jié)點(diǎn)的bf, 返回對(duì)應(yīng)結(jié)點(diǎn)高度值int max1,max2;if(bt=NULL) return 0;if(bt-lchild=NULL&bt-rchild=NULL)bf-bf=0;return1;elsemax1=Height(bt

29、-lchild);max2=Height(bt-rchild);bt-bf= max2-max1;return max1max2?max1+1:max2+1;例 21 設(shè)給出一段報(bào)文：CASTCASTSATATATASA ；字符集合是 C, A, S,T ，各個(gè)字符出現(xiàn)的頻度若給每個(gè)字符以等長(zhǎng)編碼優(yōu)越之處。 (編碼最短 )( 次數(shù) )是 A : 00W 2, 7, 4, 5 T : 10C : 01；試設(shè)計(jì)赫夫曼編碼，畫出赫夫曼樹。S : 11；試說明赫夫曼編碼比此方案的解答見ppt練習(xí)1設(shè)計(jì)一個(gè)算法，刪除該二叉樹，釋放所有結(jié)點(diǎn)2設(shè)計(jì)一算法判斷二叉鏈表存儲(chǔ)的二叉樹是否結(jié)構(gòu)對(duì)稱（左右子樹結(jié)點(diǎn)結(jié)構(gòu)

30、對(duì)稱相同）3試寫出復(fù)制一棵二叉樹的算法。二叉樹采用標(biāo)準(zhǔn)鏈接結(jié)構(gòu)。4習(xí)題六編程（除打星號(hào)的部分）5. 設(shè)計(jì)一個(gè)算法， 尋找二叉樹中滿足特定數(shù)值x 的第一個(gè)結(jié)點(diǎn) (相應(yīng)的變形： 尋找最小值，尋找父結(jié)點(diǎn)，尋找兄弟)6. 設(shè)計(jì)一個(gè)算法，統(tǒng)計(jì)二叉樹中滿足特定數(shù)值x 結(jié)點(diǎn)的個(gè)數(shù)（相應(yīng)的變形：統(tǒng)計(jì)度為0，1， 2 的結(jié)點(diǎn)）第七章圖1.圖的定義、基本概念：B2.圖的存儲(chǔ)方式：鄰接矩陣和鄰接表A3.圖的遍歷深度優(yōu)先和廣度優(yōu)先A4.圖的連通性和生成樹B帶權(quán)圖的最小生成樹及算法B5.圖的最短路徑問題B6.拓?fù)渑判颉?AOE 網(wǎng)中的關(guān)鍵路徑B本章重點(diǎn)：熟悉鄰接矩陣和鄰接表的表示方法，學(xué)會(huì)編寫遍歷算法深度優(yōu)先和廣度優(yōu)先

31、遍歷算法以及一些遍歷算法的應(yīng)用。請(qǐng)仔細(xì)復(fù)習(xí)。本章難點(diǎn)：圖的一些算法（如最小生成樹、最短路徑、關(guān)鍵路徑；這部分重在理解算法思想和設(shè)計(jì)過程）例 22 將鄰接矩陣 g 裝換為鄰接表 G (鄰接表的表示方法 ) void MatToList(MGragh g,ALGLink &G)int i,j, N=g.n;/N表示頂點(diǎn)數(shù)ArcNode *p;G=(ALGraph*)malloc(sizeof(ALGraph);for(i=0;iverticesi.data=g.vexsi;G-verticesi.firstedge=NULL;for(i=0;i=0;j-)/ 對(duì)第 i 個(gè)頂點(diǎn)進(jìn)行建立鏈表（由后向前

32、添加）if(g.edgesij!=0)p=(ArcNode *)malloc(sizeof(ArcNode);/新建結(jié)點(diǎn)p-adjvex=j;p-info=g.edgesij;/存放邊的權(quán)值p-next=G-verticesi.firstedge;/前插G-verticesi.firstedge=p;G-n=N; G-e=g.e;例 23 試?yán)蒙疃葍?yōu)先遍歷DFS 判斷該圖（在鄰接表存儲(chǔ)下）是否是連通的，若是連通的返回，若是不連通的返回圖的連通分量個(gè)數(shù)，空?qǐng)D則返回。(圖的遍歷 )int vistedMAXNUM; /全局?jǐn)?shù)組void DFS (ALGraph* G, int i)/*以 Vi

33、為出發(fā)點(diǎn)對(duì)鄰接表圖進(jìn)行ArcNode *p;printf(visit data:%dn,G-verticesi.data);/訪問頂點(diǎn)Vivisitedi=1;/標(biāo)記 Vi 已訪問，標(biāo)志為p= G-verticesi.firstarc;/ 取 Vi 邊表的頭指針while(p) / 依次搜索Vi 的鄰接點(diǎn)Vj ，if (!visitedp-adjvex) /若 Vj 尚未訪問，則以VjDFS (G,p-adjvex);p=p-next;DFS */為出發(fā)點(diǎn)向縱深搜索/* 判斷無向圖是否連通，若連通返回intConnects(ALGraph*G)int i,flag=1;/flagfor (i=

34、0;ivexnum;i+)visitedi=0 ;1*/為標(biāo)記是否連通/標(biāo)志向量visted 初始化，標(biāo)志為DFS(g,0);for (i=0;ivexnum;i+)if (visitedi=0) / 還有vi 未訪問過，修改標(biāo)記flag量flag=0;break;return flag;例 24 下面是求 通網(wǎng)的最小生成 的prim 算法：集合VT， ET 分 放 點(diǎn)和 ，初始 （ 1），下面步 重復(fù)n-1 次: a ：（ 2）； b：（ 3）；最后：（ 4）。（ 1）A VT， ET 空BVT 所有 點(diǎn)，ET 空C VT 網(wǎng)中任意一點(diǎn)，ET 空DVT 空， ET 網(wǎng)中所有 （ 2）A.選

35、i 屬于 VT，j 不屬于 VT，且（ i ， j ）上的 最小B i 屬于 VT，j 不屬于 VT，且（ i ， j ）上的 最大C i 不屬于 VT， j 不屬于 VT，且（ i ， j ）上的 最小D i 不屬于 VT， j 不屬于 VT，且（ i ， j ）上的 最大（ 3）A 點(diǎn) i 加入 VT，（ i,j）加入 ETB. 點(diǎn) j 加入 VT，（ i,j）加入 ETC. 點(diǎn) j 加入 VT，（i,j）從 ET中 去D 點(diǎn) i,j加入 VT，（ i,j）加入ET（ 4）AET 中 最小生成 BCET中有 n-1 條 生成 ，否 無解不在 ET 中的 構(gòu)成最小生成 D ET中無回路 ，

36、生成 ，否 無解C A B A例 25 P182 算法7.12（思考：用 接矩 存 怎么 ？）練習(xí)1. 假 有向 以 接表存 ， 算Vi 點(diǎn)的出度和入度。2.在有向無 中， 利用深度 先遍 DFS 求出一個(gè)拓?fù)渑判蛐蛄?。提示：由某點(diǎn)出 行深度 先遍 ，退出DFS 函數(shù) 用 此 點(diǎn)序號(hào)，最先退出 DFS 函數(shù)的 點(diǎn)是拓?fù)湫蛄兄械淖詈笠粋€(gè) 點(diǎn)，依次下去 .得到一個(gè)逆向拓?fù)溆行蛐蛄校辉賹⒋?點(diǎn)序號(hào)反向 出即可。3. 一個(gè)深度 先搜索算法，以判斷用 接表方式存 的有向 中是否存在由 點(diǎn)Vi 到 點(diǎn) Vj （ i j ）的路徑。第八章查找基本概念C靜 找表中常用的方法： 序 找、折半 找、分 找（分 適

37、用于一般、有序、分 有序的表）相 算法和性能分析A 找表：二叉排序 的建立、 找、 除；A二叉平衡 哈希表：哈希函數(shù)的構(gòu)造和沖突 理方法本章重點(diǎn)： 找 的建立和 找（含靜 折半 找、 找 ）、哈希函數(shù)和沖突方法本章 點(diǎn)：二叉排序 除；平衡排序 的插入例 26在有序表A1.12依次 _。中，采用二分 找算法 等于A12的元素，所比 的元素下 6,9,11,12例 27 散列表 HT 0.12,和再散列函數(shù)分 ：即表的大小 m=13。 采用雙散列法解決沖突。散列函數(shù)H0(key)=key % 13;注 :%是求余數(shù)運(yùn)算Hi =(Hi-1 +REV(key+1)%11+1) % 13;i=1,2,3,(=mod),m-1其中，函數(shù)REV（x）表示 倒