算法與數(shù)據(jù)結(jié)構(gòu) 期末考試復(fù)習(xí)

《算法與數(shù)據(jù)結(jié)構(gòu) 期末考試復(fù)習(xí)》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法與數(shù)據(jù)結(jié)構(gòu) 期末考試復(fù)習(xí)（61頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)復(fù)習(xí)2013秋季秋季l屬于程序設(shè)計(jì)的一個(gè)重要內(nèi)容，訓(xùn)練如何對(duì)數(shù)據(jù)信息進(jìn)行抽象。屬于程序設(shè)計(jì)的一個(gè)重要內(nèi)容，訓(xùn)練如何對(duì)數(shù)據(jù)信息進(jìn)行抽象。算法與數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容算法與數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容l對(duì)數(shù)據(jù)信息進(jìn)行抽象，從邏輯關(guān)系上，可以得到四大類數(shù)據(jù)結(jié)對(duì)數(shù)據(jù)信息進(jìn)行抽象，從邏輯關(guān)系上，可以得到四大類數(shù)據(jù)結(jié)構(gòu)：構(gòu)： 集合集合 線性結(jié)構(gòu)（線性表、棧、隊(duì)列、串、數(shù)組）線性結(jié)構(gòu)（線性表、棧、隊(duì)列、串、數(shù)組） 樹形結(jié)構(gòu)樹形結(jié)構(gòu) 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)l對(duì)應(yīng)四種邏輯關(guān)系，均可以采用兩種存儲(chǔ)結(jié)構(gòu)進(jìn)行物理存儲(chǔ)：對(duì)應(yīng)四種邏輯關(guān)系，均可以采用兩種存儲(chǔ)結(jié)構(gòu)進(jìn)行物理存儲(chǔ)： 順序存儲(chǔ)結(jié)構(gòu)

2、順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（指針型鏈表、數(shù)組型靜態(tài)鏈表）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（指針型鏈表、數(shù)組型靜態(tài)鏈表）l對(duì)應(yīng)四種邏輯關(guān)系，均可以設(shè)計(jì)出具體的操作方法對(duì)應(yīng)四種邏輯關(guān)系，均可以設(shè)計(jì)出具體的操作方法 結(jié)構(gòu)的初始化、銷毀，數(shù)據(jù)的查找、插入、刪除、比較等結(jié)構(gòu)的初始化、銷毀，數(shù)據(jù)的查找、插入、刪除、比較等l對(duì)四種邏輯關(guān)系的操作方法進(jìn)行了具體的編程實(shí)現(xiàn)，也例舉了對(duì)四種邏輯關(guān)系的操作方法進(jìn)行了具體的編程實(shí)現(xiàn)，也例舉了它們的一些具體應(yīng)用。它們的一些具體應(yīng)用。多項(xiàng)式的表示和操作多項(xiàng)式的表示和操作離散事件系統(tǒng)模擬離散事件系統(tǒng)模擬遞歸程序的實(shí)現(xiàn)遞歸程序的實(shí)現(xiàn)文本編輯系統(tǒng)的設(shè)計(jì)文本編輯系統(tǒng)的設(shè)計(jì)霍夫曼編碼方法霍夫曼編碼方法

3、判定樹的構(gòu)造判定樹的構(gòu)造最短路徑、關(guān)鍵路徑、拓?fù)渑判蜃疃搪窂?、關(guān)鍵路徑、拓?fù)渑判騦對(duì)于集合結(jié)構(gòu)，研究了兩種重要操作，即排序和查找對(duì)于集合結(jié)構(gòu)，研究了兩種重要操作，即排序和查找第一章第一章 緒論緒論1、基本概念和術(shù)語、基本概念和術(shù)語“數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)”課程的研究內(nèi)容及在計(jì)算機(jī)科學(xué)中的地位；課程的研究內(nèi)容及在計(jì)算機(jī)科學(xué)中的地位；數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型；數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型、抽象數(shù)據(jù)類型；邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；邏輯結(jié)構(gòu)和物理結(jié)構(gòu)、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；2、抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)、抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 三

4、元組表示法；三元組表示法； 熟悉類熟悉類c語言的語法；語言的語法； 3、算法和算法分析、算法和算法分析 算法的定義和算法的定義和5個(gè)重要特性；個(gè)重要特性； 算法設(shè)計(jì)的算法設(shè)計(jì)的4個(gè)要求及含義；個(gè)要求及含義； 算法效率的度量算法效率的度量 漸進(jìn)時(shí)間復(fù)雜度的概念；漸進(jìn)時(shí)間復(fù)雜度的概念； 簡單算法的時(shí)間復(fù)雜度的估算；簡單算法的時(shí)間復(fù)雜度的估算；第二章第二章 線性表線性表1、線性表的類型定義、線性表的類型定義 線性結(jié)構(gòu)線性結(jié)構(gòu) 線性表的定義及特性線性表的定義及特性2、線性表的順序表示和實(shí)現(xiàn)、線性表的順序表示和實(shí)現(xiàn) 線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu)線性表的動(dòng)態(tài)分配順序存儲(chǔ)結(jié)構(gòu) 線性表插入、刪除算法，線性表插

5、入、刪除算法，算法算法2.4、2.5 插入、刪除算法的平均時(shí)間復(fù)雜度的估算插入、刪除算法的平均時(shí)間復(fù)雜度的估算3、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 線性鏈表的概念線性鏈表的概念 線性單鏈表的存儲(chǔ)結(jié)構(gòu)和創(chuàng)建、線性單鏈表的存儲(chǔ)結(jié)構(gòu)和創(chuàng)建、插入插入、刪除、合并算法、刪除、合并算法 循環(huán)鏈表的概念、特點(diǎn)循環(huán)鏈表的概念、特點(diǎn) 雙向鏈表的存儲(chǔ)結(jié)構(gòu)和插入刪除算法，雙向鏈表的存儲(chǔ)結(jié)構(gòu)和插入刪除算法，算法算法2.18、2.194、一元多項(xiàng)式的表示與相加算法、一元多項(xiàng)式的表示與相加算法typedef struct PNode float coef；/系數(shù)系數(shù) int expn； /指數(shù)指數(shù) stru

6、ct PNode *next； PNode，PLinkList；相加算法要求讀懂、理解，算法相加算法要求讀懂、理解，算法2.23pabxs例如：在線性鏈表兩個(gè)數(shù)據(jù)元素例如：在線性鏈表兩個(gè)數(shù)據(jù)元素a和和b間插入間插入x, 已知已知p指針指針指向指向a。s-next = p-next;p-next = s;Status ListInsert_L(LinkList &L, int i, ElemType e) /在位置在位置i插入元素插入元素e e；p = L; j = 0;while (p & jnext; +jif (!p | ji-1) return ERROR; /指定的插入

7、位置超界；指定的插入位置超界；s = ( LinkList) malloc ( sizeof (LNode) );s-data = e; s-next = p-next;p-next = s;return OK; nOnT第三章第三章 棧和隊(duì)列棧和隊(duì)列1、棧的表示和實(shí)現(xiàn)、棧的表示和實(shí)現(xiàn)棧的概念、特點(diǎn)、表示和實(shí)現(xiàn)（棧的概念、特點(diǎn)、表示和實(shí)現(xiàn)（順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)）；）；棧的初始化、取棧頂元素、棧的初始化、取棧頂元素、元素的入棧、出棧算法元素的入棧、出棧算法，47頁；頁；2、棧的應(yīng)用、棧的應(yīng)用 數(shù)制轉(zhuǎn)換算法，算法數(shù)制轉(zhuǎn)換算法，算法3.13.1； 求解求解n n階階HanoiHanoi塔問題的遞

8、歸過程和算法，算法塔問題的遞歸過程和算法，算法3.53.5；3、隊(duì)列的定義、特點(diǎn)、隊(duì)列的定義、特點(diǎn)鏈隊(duì)列的表示和實(shí)現(xiàn)、元素的插入鏈隊(duì)列的表示和實(shí)現(xiàn)、元素的插入和和刪除算法刪除算法；循環(huán)隊(duì)列的表示和實(shí)現(xiàn)循環(huán)隊(duì)列的表示和實(shí)現(xiàn)、元素的插入和刪除算法元素的插入和刪除算法；離散事件模擬過程、算法、運(yùn)行結(jié)果，離散事件模擬過程、算法、運(yùn)行結(jié)果，算法算法3.7；順序棧順序棧typedef structSElemType * base;SElemType * top;intstacksize;SqStack; 棧的存儲(chǔ)結(jié)構(gòu)棧的存儲(chǔ)結(jié)構(gòu)Status Push(SqStack &S, SElemType e

9、)Status Push(SqStack &S, SElemType e) if(S.top S.base = S.stacksize) if(S.top S.base = S.stacksize)/棧滿，追加空間；棧滿，追加空間； S.base = (SElemType S.base = (SElemType * *) realloc(S.base,) realloc(S.base, (S.stacksize +STACKINCREMENT) (S.stacksize +STACKINCREMENT) * * sizeof(SElemType) sizeof(SElemType)；

10、if(!S.base) exit (OVERFLOW);if(!S.base) exit (OVERFLOW); S.top = S.base + S.stacksize; S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; S.stacksize += STACKINCREMENT; * * S.top + + =e; S.top + + =e; /先將元素壓入堆棧，后移動(dòng)指針；先將元素壓入堆棧，后移動(dòng)指針； return OK;return OK; Status Pop(SqStack &S, SElemType

11、 &e)Status Pop(SqStack &S, SElemType &e) if(S.top = = S.base)return ERROR; if(S.top = = S.base)return ERROR; /堆棧為空；堆棧為空； e = e = * *- -S.top; - -S.top; /先移動(dòng)指針先移動(dòng)指針, ,再將元素彈出堆棧；再將元素彈出堆棧； return OK;return OK; 棧頂指針棧頂指針top等于等于棧底指棧底指針針base時(shí)，棧是空棧。時(shí)，棧是空棧。top123450進(jìn)棧進(jìn)棧A棧滿棧滿BCDEF 非空棧的非空棧的棧頂指針棧頂指針始

12、終指向棧頂元素始終指向棧頂元素的下一個(gè)位置。的下一個(gè)位置。toptoptoptoptoptop出棧出棧123450ABCDEFtoptoptoptop=base?？諚？誸optoptop=base123450?？諚？誦asetop=base先把元素壓入堆棧，先把元素壓入堆棧，再移動(dòng)指針。再移動(dòng)指針。先移動(dòng)指針，再把先移動(dòng)指針，再把棧頂元素彈出。棧頂元素彈出。n只能在棧頂進(jìn)行數(shù)據(jù)元素的入棧和出棧操只能在棧頂進(jìn)行數(shù)據(jù)元素的入棧和出棧操作。作。 Status EnQueue (LinkQueue &Q, QElemType e) Status EnQueue (LinkQueue &

13、Q, QElemType e) / / 插入元素插入元素e e為為Q Q的新的隊(duì)尾元素的新的隊(duì)尾元素 p = new QNode;p = new QNode; if (!p) exit (OVERFLOW); if (!p) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 p-data = e; p-next = NULL;p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; Q.rear-next = p; Q.rear = p; return OK; return OK; / 結(jié)點(diǎn)類型結(jié)點(diǎn)類型 typedef stru

14、ct QNode QElemType data; struct QNode *next; QNode, * QueuePtr;/ / 鏈隊(duì)列類型鏈隊(duì)列類型typedef struct QueuePtr front; / 隊(duì)頭指針隊(duì)頭指針 QueuePtr rear; / 隊(duì)尾指針隊(duì)尾指針 LinkQueue; Status DeQueue (LinkQueue &Q, QElemType &e) Status DeQueue (LinkQueue &Q, QElemType &e) / / 若隊(duì)列不空，則刪除若隊(duì)列不空，則刪除Q Q的隊(duì)頭元素，的隊(duì)頭元素， /用

15、用 e e 返回其值，并返回返回其值，并返回OKOK；否則返回；否則返回ERRORERROR if (Q.front = Q.rear) return ERROR; if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; p = Q.front-next; e = p-data; Q.front-next = p-next; Q.front-next = p-next; if (Q.rear = = p) Q.rear = Q.front; if (Q.rear = = p) Q.rear = Q.front; /防止

16、隊(duì)尾指針丟失；防止隊(duì)尾指針丟失； delete (p); delete (p); return OK; return OK; #define MAXQSIZE 100 /最大隊(duì)列長度最大隊(duì)列長度typedef struct QElemType *base; / / 動(dòng)態(tài)分配存儲(chǔ)空間動(dòng)態(tài)分配存儲(chǔ)空間 int front; / / 頭指針，若隊(duì)列不空，指向隊(duì)列頭元素頭指針，若隊(duì)列不空，指向隊(duì)列頭元素; ; int rear; / / 尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置; ; SqQueue;0M-11frontrear.Status EnQ

17、ueue (SqQueue &Q, ElemType e) Status EnQueue (SqQueue &Q, ElemType e) / / 插入元素插入元素e e為為Q Q的新的隊(duì)尾元素的新的隊(duì)尾元素; ; if (Q.rear+1) % MAXQSIZE = Q.front) if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; return ERROR; /隊(duì)列滿隊(duì)列滿 Q.baseQ.rear = e;Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; Q.rear =

18、(Q.rear+1) % MAXQSIZE; return OK; return OK; Status DeQueue (SqQueue &Q, ElemType &e) Status DeQueue (SqQueue &Q, ElemType &e) / / 若隊(duì)列不空，則刪除若隊(duì)列不空，則刪除Q Q的隊(duì)頭元素，的隊(duì)頭元素， / / 用用e e返回其值，并返回返回其值，并返回OK;OK;否則返回否則返回ERRORERROR if (Q.front = Q.rear) return ERROR; if (Q.front = Q.rear) return ERRO

19、R; e = Q.baseQ.front; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; Q.front = (Q.front+1) % MAXQSIZE; return OK; return OK;第四章第四章 串串1、串類型的定義、表示和實(shí)現(xiàn)、串類型的定義、表示和實(shí)現(xiàn) 定長順序存儲(chǔ)表示定長順序存儲(chǔ)表示 堆分配存儲(chǔ)表示堆分配存儲(chǔ)表示 串的塊鏈存儲(chǔ)表示串的塊鏈存儲(chǔ)表示 串的抽象數(shù)據(jù)類型定義串的抽象數(shù)據(jù)類型定義 串和串的基本概念串和串的基本概念串串(String)(String)是零個(gè)或多個(gè)字符組成的有限序列。一般是零個(gè)或多個(gè)字符組成的

20、有限序列。一般記作記作S=aS=a1 1 a a2 2 a a3 3 a an n，其中，其中S S是串名，單引號(hào)括是串名，單引號(hào)括起來的字符序列是串值；起來的字符序列是串值；a ai i(1(1i in)n)可以是字母、數(shù)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為串的字或其它字符；串中所包含的字符個(gè)數(shù)稱為串的長度長度。空串空串(Empty String)(Empty String)是長度為零的串，它不包含任何是長度為零的串，它不包含任何字符。字符?？瞻状瞻状?Blank String)(Blank String)是由一個(gè)或多個(gè)空格組成的串。是由一個(gè)或多個(gè)空格組成的串。 注意：空串

21、和空白串不同，例如注意：空串和空白串不同，例如和和分別表分別表示長度為示長度為1 1的空白串和長度為的空白串和長度為0 0的空串。的空串。定長順序存儲(chǔ)表示定長順序存儲(chǔ)表示#define MAXSTRLEN 255 / / 用戶可在用戶可在255255以內(nèi)定義串長以內(nèi)定義串長typedef unsigned char SStringMAXSTRLEN + 1; /0/0號(hào)單元存放串的長度號(hào)單元存放串的長度(PASCAL(PASCAL風(fēng)格風(fēng)格) )堆分配存儲(chǔ)表示堆分配存儲(chǔ)表示typedef struct char *ch; / / 若是非空串，則按串長分配存儲(chǔ)區(qū)，否則若是非空串，則按串長分配存儲(chǔ)區(qū)

22、，否則chch為為NULL;NULL; int length; / / 串長度串長度; ; HString;串的塊鏈存儲(chǔ)表示串的塊鏈存儲(chǔ)表示#define CHUNKSIZE 80 #define CHUNKSIZE 80 / / 可由用戶定義的塊大小可由用戶定義的塊大小; ;typedef struct Chunk typedef struct Chunk / / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu); ; char chCUNKSIZE; char chCUNKSIZE; struct Chunk struct Chunk * *next;next; Chunk; Chunk;typedef struct t

23、ypedef struct / / 串的鏈表結(jié)構(gòu)串的鏈表結(jié)構(gòu); ; Chunk Chunk * *head, head, * *tail; tail; / / 串的頭和尾指針串的頭和尾指針; ; int curlen; int curlen; / / 串的當(dāng)前長度串的當(dāng)前長度; ; LString; LString;第六章第六章 樹和二叉樹樹和二叉樹1 1、樹的定義及基本術(shù)語、樹的定義及基本術(shù)語 樹的抽象數(shù)據(jù)類型表述樹的抽象數(shù)據(jù)類型表述 基本術(shù)語基本術(shù)語2 2、二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)、二叉樹的定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu) 二叉樹的抽象數(shù)據(jù)類型表述二叉樹的抽象數(shù)據(jù)類型表述 二叉樹的性質(zhì)二叉樹的性質(zhì)

24、1、2、3、4 二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）（順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）3 3、二叉樹的遍歷與構(gòu)造、二叉樹的遍歷與構(gòu)造 算法算法6.1、6.2、6.34 4、樹和森林、樹和森林 樹的存儲(chǔ)結(jié)構(gòu)樹的存儲(chǔ)結(jié)構(gòu)（孩子兄弟表示法）（孩子兄弟表示法） 森林和二叉樹的轉(zhuǎn)換森林和二叉樹的轉(zhuǎn)換5 5、赫夫曼樹的定義、赫夫曼樹的定義、構(gòu)造方法構(gòu)造方法及其應(yīng)用（判定樹、赫夫曼編碼）及其應(yīng)用（判定樹、赫夫曼編碼） 算法算法6.12抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型定義ADT Tree 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系

25、R：若若D為空集，則稱為空樹；若為空集，則稱為空樹；若D僅含一個(gè)數(shù)據(jù)元僅含一個(gè)數(shù)據(jù)元素，則素，則R為空集，否則為空集，否則R=H,H是如下二元關(guān)系：是如下二元關(guān)系： (1) 在在D中存在惟一的稱為根的數(shù)據(jù)元素中存在惟一的稱為根的數(shù)據(jù)元素root，它在關(guān)系，它在關(guān)系H下無下無前驅(qū)；前驅(qū)； (2) 若若D-root，則存在，則存在D-root的一個(gè)劃分的一個(gè)劃分D1，D2, , Dm (m0)，對(duì)任意，對(duì)任意jk (1j，km)有有DjDk=，且對(duì)任意的，且對(duì)任意的i(1im)，惟一存在數(shù)據(jù)元素，惟一存在數(shù)據(jù)元素xiDi, 有有H; (3) 對(duì)應(yīng)于對(duì)應(yīng)于D-root的劃分，的劃分，H- , , 有

26、惟一的一個(gè)劃分有惟一的一個(gè)劃分H1,H2, , Hm (m0)，對(duì)任意，對(duì)任意jk (1j，km)有有HjHk=，且對(duì)任意的，且對(duì)任意的i(1im)，Hi是是Di上的上的二元關(guān)系，二元關(guān)系，(Di，Hi)是一顆符合本定義的樹，稱為根是一顆符合本定義的樹，稱為根root的子樹。的子樹。 基本術(shù)語基本術(shù)語(1)結(jié)點(diǎn)結(jié)點(diǎn)(node)表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其表示樹中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支子樹的分支;(2)結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹數(shù)量結(jié)點(diǎn)擁有的子樹數(shù)量;(3)葉子葉子(leaf)度為度為0的結(jié)點(diǎn)；的結(jié)點(diǎn)；(4)孩子孩子(child) 結(jié)點(diǎn)子樹的根稱為

27、該結(jié)點(diǎn)的孩子；結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子；(5)雙親雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親；孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親；(6)兄弟兄弟(sibling)同一雙親的孩子；同一雙親的孩子；(7)樹的度樹的度一棵樹中各結(jié)點(diǎn)的度的最大值；一棵樹中各結(jié)點(diǎn)的度的最大值；(8)結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層為第二層；(9)深度深度(depth)樹中結(jié)點(diǎn)的最大層次數(shù)；樹中結(jié)點(diǎn)的最大層次數(shù)；(10)森林森林(forest)m(m 0)棵互不相交的樹的集合；棵互不相交的樹的集合；二叉樹性質(zhì)二叉樹性質(zhì)證明：用歸納

28、法證明之證明：用歸納法證明之: i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，時(shí)，只有一個(gè)根結(jié)點(diǎn)， ，結(jié)論成立；，結(jié)論成立； 假設(shè)對(duì)所有假設(shè)對(duì)所有j(1 j1，則則其雙親是其雙親是 i/2 ； (2)如果如果2in，則結(jié)點(diǎn)則結(jié)點(diǎn)i無左孩子；如果無左孩子；如果2i n，則其左孩子是則其左孩子是2i； (3)如果如果2i+1n，則結(jié)點(diǎn)則結(jié)點(diǎn)i無右孩子；如果無右孩子；如果2i+1 n，則其右孩則其右孩子是子是2i+1；1log2nn深度為個(gè)結(jié)點(diǎn)的完全二叉樹的具有性質(zhì)性質(zhì)4：證明：設(shè)深度為證明：設(shè)深度為K，根據(jù)性質(zhì)，根據(jù)性質(zhì)2和完全二叉樹的定義：和完全二叉樹的定義： 2k-1-1n2k-1 或者或者 2k-1n2k ；K

29、-12nlchild);Pop(S, p); /完成循環(huán)，最后入棧的是一個(gè)空指針；完成循環(huán)，最后入棧的是一個(gè)空指針；if (!StackEmpty(S) Pop(S, p); if (! Visit(p-data) return ERROR;Push(S, p-rchild);return OK；ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B訪問：訪問：C(4)pABCDEFGiP-A訪問：訪問：C B(5)ABCDEFGiP-AP-D訪問：訪問：C Bp(6)ABCDEFGiP-AP-DP-

30、E訪問：訪問：C Bp(7)ABCDEFGiP-AP-D訪問：訪問：C B Ep(8)ABCDEFGiP-AP-DP-G訪問：訪問：C B EP=NULL(9)ABCDEFGiP-A訪問：訪問：C B E G Dp(11)ABCDEFGiP-AP-F訪問：訪問：C B E G Dp(12)ABCDEFGiP-AP-D訪問：訪問：C B E Gp(10)ABCDEFGiP-A訪問：訪問：C B E G D Fp=NULL(13)ABCDEFGi訪問：訪問：C B E G D F Ap(14)ABCDEFGi訪問：訪問：C B E G D F Ap=NULL(15)森林與二叉樹的轉(zhuǎn)換森林與二叉樹的

31、轉(zhuǎn)換 樹與二叉樹樹與二叉樹可以通過二叉鏈表作為媒介實(shí)現(xiàn)二者間的可以通過二叉鏈表作為媒介實(shí)現(xiàn)二者間的映射關(guān)系。映射關(guān)系。 森林與二叉樹森林與二叉樹同樣可以通過二叉鏈表作為媒介實(shí)現(xiàn)二同樣可以通過二叉鏈表作為媒介實(shí)現(xiàn)二者間的映射關(guān)系。者間的映射關(guān)系。ACBED樹ABCDE二叉樹二叉樹 A B C D E A B C D E A B C D E 對(duì)應(yīng)對(duì)應(yīng)存儲(chǔ)存儲(chǔ)存儲(chǔ)存儲(chǔ)解釋解釋解釋解釋構(gòu)造構(gòu)造HuffmanHuffman樹的方法樹的方法HuffmanHuffman算法算法構(gòu)造構(gòu)造HuffmanHuffman樹的步驟樹的步驟1 1、根據(jù)給定的、根據(jù)給定的n n個(gè)權(quán)值個(gè)權(quán)值w1,w2,w1,w2,wnwn

32、，構(gòu)造構(gòu)造n n棵棵只有根結(jié)點(diǎn)的二叉樹，第只有根結(jié)點(diǎn)的二叉樹，第i i棵樹的棵樹的權(quán)值為權(quán)值為w wi i；形成；形成一個(gè)森林。一個(gè)森林。2 2、在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和, ,并并在森林中刪在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中；除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中；3 3、重復(fù)上述兩步直到只含一棵樹為止，這棵樹即重復(fù)上述兩步直到只含一棵樹為止，這棵樹即赫夫曼樹。赫夫曼樹。例例

33、a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3 1114297823 113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295810011358192342291487152958第七章第七章 圖圖1 1、圖的定義和術(shù)語、圖的定義和術(shù)語2 2、圖的存儲(chǔ)結(jié)構(gòu)、圖的存儲(chǔ)結(jié)構(gòu) 數(shù)組表示法數(shù)組表示法 鄰接表鄰接表 十字鏈表十字鏈表 鄰接多重表

34、鄰接多重表 采用鄰接矩陣表示法，構(gòu)造無向網(wǎng)采用鄰接矩陣表示法，構(gòu)造無向網(wǎng)G，算法算法7.2 采用十字鏈表表示法，構(gòu)造有向圖采用十字鏈表表示法，構(gòu)造有向圖G，算法算法7.33 3、圖的遍歷、圖的遍歷 深度優(yōu)先搜索的過程和算法，深度優(yōu)先搜索的過程和算法，算法算法7.4、 7.5 廣度優(yōu)先搜索的過程和算法，廣度優(yōu)先搜索的過程和算法，算法算法7.64 4、圖的連通性問題、圖的連通性問題 最小生成樹的概念、最小生成樹的概念、普里姆算法普里姆算法、克魯斯卡爾算法思想克魯斯卡爾算法思想 普里姆算法，算法普里姆算法，算法7.95 5、有向無環(huán)圖及其應(yīng)用、有向無環(huán)圖及其應(yīng)用 拓?fù)渑判虻母拍詈退惴?，拓?fù)渑判虻母拍?/p>

35、和算法，算法算法7.12 關(guān)鍵路徑的概念和算法，關(guān)鍵路徑的概念和算法，算法算法7.13、7.14 AOV-網(wǎng)和網(wǎng)和AOE-網(wǎng)的概念網(wǎng)的概念 6 6、最短路徑、最短路徑 最短路徑的概念最短路徑的概念 從某一源點(diǎn)到其余各頂點(diǎn)的最短路徑，從某一源點(diǎn)到其余各頂點(diǎn)的最短路徑，迪杰斯特拉算迪杰斯特拉算 法，算法法，算法7.15 構(gòu)造最小生成樹的方法構(gòu)造最小生成樹的方法方法一：普里姆方法一：普里姆(Prim)算法算法1、算法思想：設(shè)、算法思想：設(shè)N=(V,E)是連通網(wǎng)，是連通網(wǎng)，TE是是N上最小生上最小生成樹中邊的集合；成樹中邊的集合；2、初始令、初始令U=u0,(u0 V), TE= ；3、在所有、在所有

36、u U,v V-U的邊的邊(u,v) E中，找一條代價(jià)最中，找一條代價(jià)最小的邊小的邊(u0,v0)；4、將、將(u0,v0)并入集合并入集合TE，同時(shí)同時(shí)v0并入并入U(xiǎn)；5、重復(fù)上述操作直至、重復(fù)上述操作直至U=V為止，則為止，則T=(V,TE)為為N的的最小生成樹；最小生成樹；例例1654326513566425131163141643142116432142516543214253 方法二：克魯斯卡爾方法二：克魯斯卡爾(Kruskal)算法算法算法思想：算法思想：1、設(shè)連通網(wǎng)、設(shè)連通網(wǎng)N=(V,E)，令最小生成樹的令最小生成樹的初始狀態(tài)為只有初始狀態(tài)為只有n個(gè)頂個(gè)頂點(diǎn)而無邊的非連通圖點(diǎn)而無

37、邊的非連通圖T=(V, )，每個(gè)頂點(diǎn)自成一個(gè)連通分量，每個(gè)頂點(diǎn)自成一個(gè)連通分量;2、在、在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的中不同的連通分量上，則將此邊加入到連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下中；否則，舍去此邊，選取下一條代價(jià)最小的邊一條代價(jià)最小的邊;3、依此類推，直至、依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止中所有頂點(diǎn)都在同一連通分量上為止。例例165432651356642516543212345最短路徑最短路徑如果用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：如果用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)頂

38、點(diǎn)表示城市；表示城市；邊邊表示城市間的交通聯(lián)系；表示城市間的交通聯(lián)系；權(quán)權(quán)表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等；表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等；如何尋找如何尋找最短路徑最短路徑？即？即尋找尋找從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑；點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑；問題的提出問題的提出迪杰斯特拉迪杰斯特拉(Dijkstra)(Dijkstra)算法思想算法思想按路徑長度的遞增順序，依次產(chǎn)生最短路徑按路徑長度的遞增順序，依次產(chǎn)生最短路徑;假設(shè)圖中所示為從源點(diǎn)到其余各點(diǎn)之間的最短路徑

39、，在其中必有假設(shè)圖中所示為從源點(diǎn)到其余各點(diǎn)之間的最短路徑，在其中必有一條相對(duì)最短的路徑；一條相對(duì)最短的路徑；源點(diǎn)源點(diǎn)a 在在相對(duì)最短的相對(duì)最短的路徑上，必定只含一條弧且路徑上，必定只含一條弧且權(quán)值最小。因權(quán)值最小。因此，只此，只要在所有從源點(diǎn)出發(fā)的弧中查找權(quán)值最小者，可得要在所有從源點(diǎn)出發(fā)的弧中查找權(quán)值最小者，可得相對(duì)最短路徑相對(duì)最短路徑; ;長度次短的路徑可能有兩種情況長度次短的路徑可能有兩種情況: : 它可能是從源點(diǎn)直接到該點(diǎn)的路徑它可能是從源點(diǎn)直接到該點(diǎn)的路徑; ; 也可能是，從源點(diǎn)到也可能是，從源點(diǎn)到a, a, 再從再從a a到該點(diǎn)；到該點(diǎn)；其余依次類推，直至求出源點(diǎn)到各頂點(diǎn)的全部最短

40、路徑。其余依次類推，直至求出源點(diǎn)到各頂點(diǎn)的全部最短路徑。 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑假設(shè)假設(shè) Distk 表示當(dāng)前所求得的從源點(diǎn)到表示當(dāng)前所求得的從源點(diǎn)到k的最短路徑，顯然，的最短路徑，顯然， Distk = 或或 = + + ；求最短路徑步驟求最短路徑步驟: :首先，令首先，令S=VS=V0 0 ，T=T=其余頂點(diǎn)其余頂點(diǎn) ，V V0 0到到T T中頂點(diǎn)對(duì)應(yīng)的路徑長度：中頂點(diǎn)對(duì)應(yīng)的路徑長度： 若存在若存在V ，為，為V 弧上的權(quán)值；弧上的權(quán)值； 若不存在若不存在 ，為為 ；其次，從其次，從T T中選取一個(gè)與中選取一個(gè)與V V0 0路徑長度路徑長度最小的頂

41、點(diǎn)最小的頂點(diǎn)j j，加入，加入S S； 對(duì)對(duì)T T中頂點(diǎn)的中頂點(diǎn)的路徑長度路徑長度進(jìn)行修改：若加進(jìn)進(jìn)行修改：若加進(jìn)j j作中間頂點(diǎn)，從作中間頂點(diǎn)，從V V0 0到到V Vi i的路徑長度比不加的路徑長度比不加j j時(shí)時(shí)的路徑短，則修改此路徑長度的路徑短，則修改此路徑長度。重復(fù)上述步驟，直到重復(fù)上述步驟，直到S S中包含所有頂點(diǎn)，即中包含所有頂點(diǎn)，即S=VS=V為止。為止。138 30 32V213-1330 32V1-13302220V3-192220V4終點(diǎn)終點(diǎn) 從從V0到各終點(diǎn)的最短路徑及其長度到各終點(diǎn)的最短路徑及其長度V1V2V3V4V5V6Vj-2120V651643208562301

42、3717329第九章第九章 查找查找概念：關(guān)鍵字概念：關(guān)鍵字1、靜態(tài)查找表、靜態(tài)查找表 順序表的查找，順序表的查找，算法算法9.1 有序表的查找，有序表的查找，算法算法9.2 索引順序表的查找算法思想索引順序表的查找算法思想 上述三種查找方式的平均查找長度上述三種查找方式的平均查找長度 判定樹的概念與結(jié)構(gòu)特點(diǎn)判定樹的概念與結(jié)構(gòu)特點(diǎn)2、動(dòng)態(tài)查找表、動(dòng)態(tài)查找表 二叉排序樹的特性以及查找、插入、刪除算法，二叉排序樹的特性以及查找、插入、刪除算法， 9.5(b)、9.6、9.8 平衡二叉樹的概念平衡二叉樹的概念 B-樹和樹和B+樹的概念樹的概念 B-樹的查找算法，算法樹的查找算法，算法9.133、哈希

43、表、哈希表u哈希表的概念哈希表的概念u哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法直接定址法直接定址法除留余數(shù)法除留余數(shù)法u處理沖突的方法處理沖突的方法開放定址法開放定址法鏈地址法鏈地址法u哈希表的查找過程哈希表的查找過程1B-樹的定義樹的定義B-樹是一種 平衡平衡 的 多路多路 查找查找 樹： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96平衡樹的特性平衡樹的特性 樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上中的同一層次上; 根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹子樹; 其余所有非葉結(jié)點(diǎn)

44、均至少含有其余所有非葉結(jié)點(diǎn)均至少含有 m/2 棵棵子樹，至多含有子樹，至多含有 m 棵子樹棵子樹; ; 在在 m 階的階的B-樹上，每個(gè)非終端結(jié)點(diǎn)可能樹上，每個(gè)非終端結(jié)點(diǎn)可能含有：含有： n 個(gè)個(gè)關(guān)鍵字關(guān)鍵字 Ki（1 in） nm n 個(gè)個(gè)指向記錄的指針指向記錄的指針 Di（1in） n+1 個(gè)個(gè)指向子樹的指針指向子樹的指針 Ai（0in）;多叉樹的特性多叉樹的特性 非葉結(jié)點(diǎn)中的非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字均自小至大多個(gè)關(guān)鍵字均自小至大有有序排列，即：序排列，即：K1 K2 Kn; 且且 Ai-1 所指子樹上所有關(guān)鍵字均小于所指子樹上所有關(guān)鍵字均小于Ki; Ai 所指子樹上所有關(guān)鍵字均大于所指子樹

45、上所有關(guān)鍵字均大于Ki; ; 非終端結(jié)點(diǎn)中包含的信息：非終端結(jié)點(diǎn)中包含的信息： (n,A0,K1,A1,K2,Kn,An)查找樹的特性查找樹的特性一棵一棵4階階B-樹樹t ta ac cd de ef fg g35351 118181 111111 127271 139391 199991 14747535364643 3434378782 2FFFFFFFFFFFFb bh hB+樹的結(jié)構(gòu)特點(diǎn)：樹的結(jié)構(gòu)特點(diǎn)： 每個(gè)中間結(jié)點(diǎn)中含有每個(gè)中間結(jié)點(diǎn)中含有 n 個(gè)關(guān)鍵字和個(gè)關(guān)鍵字和 n 個(gè)指個(gè)指向記錄的指針向記錄的指針；2B+樹樹:是是B-樹的一種變型樹的一種變型 每個(gè)每個(gè)中間結(jié)點(diǎn)中間結(jié)點(diǎn)中的關(guān)鍵字中

46、的關(guān)鍵字 Ki 即為其相應(yīng)即為其相應(yīng)指針指針 Ai 所指子樹中所指子樹中關(guān)鍵字的最大值關(guān)鍵字的最大值；所有葉子結(jié)點(diǎn)都處在所有葉子結(jié)點(diǎn)都處在同一層次上同一層次上，每個(gè)葉子，每個(gè)葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于 m/2 和和 m 之間，之間，包括包括 m/2 和和 m 。并且，所有并且，所有葉子結(jié)點(diǎn)彼此相葉子結(jié)點(diǎn)彼此相鏈接構(gòu)成一個(gè)有序鏈表鏈接構(gòu)成一個(gè)有序鏈表，其頭指針指向含最小，其頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)；關(guān)鍵字的結(jié)點(diǎn)；數(shù)據(jù)庫中的數(shù)據(jù)庫中的非簇索引非簇索引和和簇索引簇索引5757第第10章章 排序排序u排序的概念、穩(wěn)定排序、排序算法的時(shí)間復(fù)雜度排序的概念、穩(wěn)定排序、排序算法的時(shí)間復(fù)雜度極限極限O(nlogn)u各種排序方法的基本思想、過程、性能，給出一各種排序方法的基本思想、過程、性能，給出一個(gè)序列，能夠手工推演出各趟排序結(jié)果。個(gè)序列，能夠手工推演出各趟排序結(jié)果。直接插入排序、表插入排序、希爾排序直接插入排序、表插入排序、希爾排序快速排序快速排序堆排序堆排序歸并排序歸并排序基數(shù)排序基數(shù)排序本文觀看結(jié)束！謝 謝欣 賞！祝各位身體健康！萬事如意！