(完整word版)數(shù)據(jù)結(jié)構(gòu),清華大學(xué)出版社,嚴(yán)蔚敏吳偉民編著

1、第一章 緒論1、數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)中 存儲(chǔ)、組織數(shù)據(jù) 的方式。精心選擇的數(shù)據(jù) 結(jié)構(gòu)可以帶來 最優(yōu)效率 的算法。2、程序設(shè)計(jì) = 算法 +數(shù)據(jù)結(jié)構(gòu)3、解決問題方法的效率：跟數(shù)據(jù)的組織方式有關(guān)跟空間的利用效率有關(guān)跟算法的巧妙程度有關(guān)4、數(shù)據(jù) ：所有能輸入到計(jì)算機(jī)中 ,且被計(jì)算機(jī)處理的符號(hào)的集合， 是計(jì)算機(jī)操作對(duì)象的總稱；是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。5、數(shù)據(jù)元素 ：數(shù)據(jù)中的一個(gè)“個(gè)體” ,數(shù)據(jù)結(jié)構(gòu)中討論的基本單 位。 相當(dāng)于“記錄” ,在計(jì)算機(jī)程序中通常作為一個(gè)整體考 慮和處理。6、數(shù)據(jù)項(xiàng) : 相當(dāng)于記錄的“域”, 是數(shù)據(jù)的不可分割的最小單位 如學(xué)號(hào)。數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。7、數(shù)據(jù)對(duì)

2、象 ：性質(zhì)相同的數(shù)據(jù)元素的集合 .例如 : 所有運(yùn)動(dòng)員的記錄集合8、數(shù)據(jù)結(jié)構(gòu) ：是相互間存在某種關(guān)系的數(shù)據(jù)元素集合。9、數(shù)據(jù)結(jié)構(gòu)是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。10、不同的關(guān)系構(gòu)成不同的結(jié)構(gòu)。11、次序關(guān)系 ：vai,ai+1>|i=1,2,3,4,5,612、對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題：1）數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作；2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)；13、數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)結(jié)構(gòu)的基本操作：指對(duì)數(shù)據(jù)結(jié)構(gòu)的加工處理。14、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）:數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示。數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)：基本操作在計(jì)算機(jī)上的

3、實(shí)現(xiàn)（方法）。15、數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念|線性表上線性結(jié)構(gòu)!棧隊(duì)（仁數(shù)據(jù)的邏輯結(jié)構(gòu)=i數(shù)£結(jié)構(gòu)的三個(gè)方廁B.非彌結(jié)構(gòu)I樹形結(jié)構(gòu) JI圖形結(jié)構(gòu)木數(shù)據(jù)的存儲(chǔ)結(jié)枸I A噸序行儲(chǔ)B 鏈?zhǔn)酱鎯?chǔ)< 3、數(shù)據(jù)的運(yùn)算：檢索.插入.刪除*烽改等16、數(shù)據(jù)元素的 4 類的基本結(jié)構(gòu) ： 集合； 線性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系； 樹形結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系；4 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在多對(duì)多 的關(guān)系。17、C語言的優(yōu)點(diǎn)：C語言可以直接操作內(nèi)存。18、每個(gè)節(jié)點(diǎn)都由兩部分組成： 數(shù)據(jù)域和指針域 。19、鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度?。總€(gè)節(jié)點(diǎn)都

4、由數(shù)據(jù)域和指針域組成 ）。邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。插入、刪除靈活（不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針 ）。20、數(shù)據(jù)類型 是一個(gè)值的集合和定義在此集合上的一組操作的 總稱。21、ADT 有兩個(gè)重要特征 :數(shù)據(jù)抽象和數(shù)據(jù)封裝。22、 抽象數(shù)據(jù)類型（Abstract Data Type簡稱ADT）:是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。23、抽象數(shù)據(jù)類型有： 數(shù)據(jù)對(duì)象 數(shù)據(jù)對(duì)象的定義、數(shù)據(jù)關(guān) 系數(shù)據(jù)關(guān)系的定義、 基本操作 基本操作的定義 。24、數(shù)據(jù)類型的定義和含義。定義：數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組 操作的總稱。含義：將數(shù)據(jù)按一定次序與形式存放的結(jié)構(gòu)24、算

5、法空間復(fù)雜度 S（n）算法的存儲(chǔ)量包括： 輸入數(shù)據(jù)所占的空間； 程序本身所占的空間； 輔助變量所占的空間。25、算法具有 有窮性、確定性、可行性、輸入和輸出五大特性。26、抽象數(shù)據(jù)類型具有 數(shù)據(jù)抽象 、數(shù)據(jù)封裝 的特點(diǎn)。27、數(shù)據(jù)的儲(chǔ)存結(jié)構(gòu)分為： 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。第二章 線性表1、線性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素中的非空有限集中。（1）存在唯一的一個(gè)被稱作“第一”的數(shù)據(jù)元素；（2）存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元素；（3）除第一個(gè)外，集合中的每一個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；（4）除最后一個(gè)外，集合中的每一個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。2、線性表 （Linear List） ：一個(gè)

6、線性表是 n 個(gè)數(shù)據(jù)元素的有限序列3、線性表的順序存儲(chǔ)實(shí)現(xiàn)： typedef struct ElementType DataMAXSIZE;int Last; List;List L, *PtrL;4、初始化(建立空的順序表)List *MakeEmpty( ) List *PtrL;PtrL = (List *)malloc( sizeof(List) );PtrL->Last = -1;return PtrL;5、查找int Find( ElementType X, List *PtrL ) int i = 0;while( i <= PtrL->Last &&a

7、mp; PtrL->Datai!= X )i+;if (i > PtrL->Last) return -1; /* 如果沒找到，返回 -1 */ else return i; /* 找到后返回的是存儲(chǔ)位置 */6、插入算法void Insert( ElementType X, int i, List *PtrL ) int j;if ( PtrL->Last = MAXSIZE-1 )/* 表空間已滿， 不能插入 */ printf( 表滿 );return;if ( i < 1 | i > PtrL->Last+2) /*檢查插入位置的合法性 */

8、printf( 位置不合法 );return;for ( j = PtrL->Last; j >= i-1; j- )PtrL->Dataj+1 = PtrL->Dataj; /* 將 ai an 倒序向后移動(dòng) */PtrL->Datai-1 = X; /* 新元素插入 */PtrL->Last+;/*Last 仍指向最后元素 */return;7、刪除算法void Delete( int i, List *PtrL ) int j;if( i < 1 | i > PtrL->Last+1 ) /*檢查空表及刪除位置的合法性*/printf

9、 （不存在第d個(gè)元素”，i ）;return ;for ( j = i; j <= PtrL->Last; j+ )PtrL->Dataj-1 = PtrL->Dataj; /* 將 ai+1 an順序向前移動(dòng)*/PtrL->Last-;/*Last 仍指向最后元素 */return;8、求表長int Length ( List *PtrL ) List *p = PtrL;/* p 指向表的第一個(gè)結(jié)點(diǎn) */int j = 0;while ( p ) p = p->Next;j+;/* 當(dāng)前 p 指向的是第 j個(gè)結(jié)點(diǎn) */return j;9、查找1) 按序

10、號(hào)查找 : FindKth;List *FindKth( int K, List *PtrL ) List *p = PtrL;int i = 1;while (p !=NULL && i < K ) p = p->Next;i+;if ( i = K ) return p;/* 找到第 K 個(gè)，返回指針 */else return NULL;/* 否則返回空 */2) 按值查找 : FindList *Find( ElementType X, List *PtrL )List *p = PtrL;while ( p!=NULL && p->D

11、ata != X ) p = p->Next;return p;10、插入(在鏈表的第i-1(1w iw n+1)個(gè)結(jié)點(diǎn)后插入一個(gè)值為 X的新結(jié)點(diǎn)）List *Insert( ElementType X, int i, List *PtrL ) List *p, *s;if ( i = 1 ) /* 新結(jié)點(diǎn)插入在表頭 */s = (List *)malloc(sizeof(List); /*申請(qǐng)、填裝結(jié)點(diǎn) */ s->Data = X;s->Next = PtrL;return s;/* 返回新表頭指針 */p = FindKth( i-1, PtrL ); /* 查找第 i

12、-1 個(gè)結(jié)點(diǎn) */if ( p = NULL ) /* 第 i-1 個(gè)不存在，不能插入 */printf( 參數(shù) i 錯(cuò));return NULL;else s = (List *)malloc(sizeof(List); /*申請(qǐng)、填裝結(jié)點(diǎn)*/s->Data = X;s->Next = p->Next; /* 新結(jié)點(diǎn)插入在第 i-1個(gè)結(jié)點(diǎn)的后面 */p->Next = s;return PtrL;11、刪除(刪除鏈表的第i (1<iWn)個(gè)位置上的結(jié)點(diǎn))List *Delete( int i, List *PtrL )List *p, *s;if ( i = 1

13、 ) /* 若要?jiǎng)h除的是表的第一個(gè)結(jié)點(diǎn) */s = PtrL;/*s 指向第 1 個(gè)結(jié)點(diǎn)*/PtrL = PtrL->Next; /* 從鏈表中刪除 */ free(s);/* 釋放被刪除結(jié)點(diǎn)*/return PtrL;p = FindKth( i-1, PtrL );/* 查找第 i-1 個(gè)結(jié)點(diǎn) */if ( p = NULL ) printf(第小個(gè)結(jié)點(diǎn)不存在” ,-1); returnNULL; else if ( p->Next = NULL )printf(第小個(gè)結(jié)點(diǎn)不存在” j);returnNULL; else s = p->Next;/*s指向第i個(gè)結(jié)點(diǎn)*/p

14、->Next = s->Next;/*從鏈表中刪除*/free(s);/*釋放被刪除結(jié)點(diǎn)*/retur n PtrL;12、鏈表不具備的特點(diǎn)是1?？呻S機(jī)訪問任一節(jié)點(diǎn)插入刪除不須要移動(dòng)元素 不必事先估計(jì)存儲(chǔ)空間所需空間與其長度成正比13、 帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是2。 head=NULL head-> next=NULL head-> next=head head!=NULL14、如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用存儲(chǔ)方式最節(jié)省時(shí)間。單鏈表雙鏈表單循環(huán)鏈表順序表第三章 Chapter 3 棧(stacks)和隊(duì)列(queues)1、棧是限定僅能

15、在表尾一端進(jìn)行 插入、刪除操作的線性表。2、棧的特點(diǎn)是“后進(jìn)棧的元素先出?！?(last in, first out)，故棧又稱為后進(jìn)先出表( LIFO)。3、一個(gè)棧是一些元素的線形列表，其中元素的插入和刪除均在表 的同一端進(jìn)行。 插入和刪除發(fā)生的一端稱為棧頂 (the top of the stack)。4、第一個(gè)進(jìn)棧的元素在棧底， 最后一個(gè)進(jìn)棧的元素在棧頂， 第一個(gè)出棧的元素為棧頂元素， 最后一個(gè)出棧的元素為棧底元素。5、連續(xù)棧(Contiguous Stack的類型定義#define MaxStack 50Typedef structdatatype stackMaxStack;int

16、top;Seqstack;Seqstack *s;6、判斷棧是否已滿？viod Push(Seqstack *s, datatype x )if (s->top>=MaxStack-1) printf(“ overflow ” );else s-> top+;s->stacks->top=x;7、判斷棧是否為空？datatype pop(Seqstack *s ) if (s->top<0)printf(“underflow”); return(NULL); return(s->stacks->top); s->top-;8、返回棧頂

17、元素的值，棧不發(fā)生變化。datatype top(Seqstack *s ) if (s->top<0)printf(“underflow”); return(NULL); return(s->stacks->top);9、鏈棧(Linked Stack的類型定義棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧， 它是運(yùn)算受限的單鏈表， 插入和刪除 操作僅限制在表頭位置上進(jìn)行。 由于只能在鏈表頭部進(jìn)行操作， 故鏈 表沒有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針。鏈棧的類型說明如下：typedef struct stacknode datatype datastruct stackn

18、ode *nextstacknode10、鏈?zhǔn)綏５奶攸c(diǎn)：鏈?zhǔn)綏o棧滿問題；空間可擴(kuò)充；插入與刪除僅在棧頂處執(zhí)行； 鏈?zhǔn)綏５臈ｍ斣阪滎^；適合于多棧操作。11、棧是限定僅能在表的一端進(jìn)行插入、刪除操作的線性表 。12、棧的元素具有后進(jìn)先出的特點(diǎn) 。13、棧頂元素的位置由棧頂指針的指示 , 進(jìn)棧、出棧操作要修改棧 頂指針。14、抽象數(shù)據(jù)類型隊(duì)列的定義：隊(duì)列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊(duì)頭(front),允許插入的一端稱為隊(duì)尾 (rear)。15、隊(duì)列亦稱作先進(jìn)先出(First In First Out的線性表，簡稱FIFO

19、表。16、雙端隊(duì)列：就是限定插入和刪除操作在表的兩端進(jìn)行的線性表。17、鏈隊(duì)列結(jié)點(diǎn)定義：typedef struct Qnode QElemType data;struct QNode *next; QNode,*QueuPtr;18、隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為 順序隊(duì)列 ,在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中, 除了用一組地址連續(xù)的儲(chǔ)存單元依次存放從隊(duì)頭到隊(duì)尾的元素 之外,尚需要附設(shè)兩個(gè)指針 front 和 rear 分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置19、在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素，而尾指針始終指向隊(duì)尾元素的下一位置20、 棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)后出21、棧和隊(duì)列的共同特點(diǎn)是只允許

20、在端點(diǎn)處插入和刪除元素22、一個(gè)棧的進(jìn)棧序列是a, b, c, d, e,則棧的不可能的輸出序列(A) edcba (B)decba(C) dceab(D) abcde 23、若已知一個(gè)棧的進(jìn)棧序列是p1, p2, p3,，pn。其輸出序列為1, 2, 3,，n，若p3=1，則pl為 C 。(A) 可能是2 (B) 一定是2 (C)不可能是2 (D)不可能是324、設(shè)有一個(gè)空棧，棧頂指針為 1000H (十六進(jìn)制，下同)，現(xiàn)有輸入序列為 1、2、3、4、5,經(jīng)過 PUSH PUSH POP PUSH POP PUSH8。 5、4、3、2、13、41005H24、一個(gè)隊(duì)列的入隊(duì)序列是若B。(A)

21、 4, 3 , 2 , 1PUSH 后，輸出 序列是 3, 棧頂指針是2、12、31002H1004H1003H1, 2 , 3 , 4,則隊(duì)列的輸出序列是(B) 1, 2 , 3 , 4(C) 1 , 4 , 3 , 2(D) 3 , 2 , 4 , 125、 若用一個(gè)大小為6的一維數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和 front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素 后，rear和front的值分別是B。（A）1 禾口 5（ B）2 禾口 4（C）4禾口 2（ D）5 禾口126、 有5個(gè)元素，其入棧次序?yàn)锳、B、C D、E,在各種可能的出棧 次序中，以元素C、D最先出

22、棧（即C第一個(gè)且D第二個(gè)出棧）的次 序有哪幾個(gè)？C、D、B、A、EC、D、E、B、AC、D、B、E、A第六章 樹和二叉樹1、樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu) 。2、樹的定義：樹是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T, T為空時(shí)稱為空樹， 否則它滿足如下兩個(gè)條件：(1) 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；(2) 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為 m(m>0)個(gè)互不相交的有限集T1, T2, T3Tm,其中每個(gè)子集又是一棵樹，并稱其為根的子樹。3、基本術(shù)語結(jié)點(diǎn) 表示樹中的元素, 包括數(shù)據(jù)項(xiàng)及若干指向其子樹的分支 結(jié)點(diǎn)的度(degree)結(jié)點(diǎn)擁有的子樹數(shù)葉子(leaf)度為0的結(jié)點(diǎn)孩子(child

23、)結(jié)點(diǎn)子樹的根稱為該結(jié)點(diǎn)的孩子雙親(parents)孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的兄弟(sibling)同一雙親的孩子樹的度 一棵樹中最大的結(jié)點(diǎn)度數(shù)結(jié)點(diǎn)的層次(level)從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層深度(depth)樹中結(jié)點(diǎn)的最大層次數(shù)森林(forest)m(m 0)棵互不相交的樹的集合例題:結(jié)點(diǎn)A的度二 結(jié)點(diǎn)B的度; 結(jié)點(diǎn)M的度:3葉子：K, L, F, G, Ms lt J結(jié)點(diǎn)A的層次； 結(jié)點(diǎn)M的層次:I®樹的深度：4樹的度：3結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)F,G為堂兄弟結(jié)點(diǎn)B, C, D為兄弟 結(jié)點(diǎn)K, L為兄弟結(jié)點(diǎn)A是結(jié)點(diǎn)F, G的祖先結(jié)點(diǎn)A的孩子：B,

24、CT D 結(jié)點(diǎn)B的孩了 ： E, F4、二叉樹是由n(n>=0個(gè)結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。性質(zhì)1:在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1)。性質(zhì)2：深度為k的二叉樹至多有2k1個(gè)結(jié)點(diǎn)(k>=1)。性質(zhì)3:對(duì)任何一棵二叉樹T,如果其終端結(jié)點(diǎn)數(shù)為n0,度為2的 結(jié)點(diǎn)數(shù)為n2,則n0= n2 + 1。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為Iog2n + 1。性質(zhì)5:如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)(從 第1層到第Iog2n

25、 +1層，每層從左到右),則對(duì)任一結(jié)點(diǎn)i (1<=i<=n), 有：(1) 如果i= 1,則結(jié)點(diǎn)i無雙親，是二叉樹的根；如果i>1,則其雙親是結(jié)點(diǎn)i/2。(2) 如果2i>n,則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；否則，其左 孩子是結(jié)點(diǎn)2i。(3) 如果2i+1>n,貝卩結(jié)點(diǎn)i無右孩子；否則，其右孩子是結(jié)點(diǎn) 2i+ 1。一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。如:(a)完全二叉樹(b)非完全二叉樹 3)非完全二叉樹5、二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)define MAX-TREE-SIZE100Typedef TelemType SqBiTree MAX-TREE

26、-SIZE;SqBitree bt;缺點(diǎn)是有可能對(duì)存儲(chǔ)空間造成極大的浪費(fèi)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;BiTNode,*BiTree;三叉鏈表typedef struct node datatype data;struct node *lchild, *rchild, *parent;JD;6、遍歷二叉樹 二叉樹是由三個(gè)基本單元組成：根結(jié)點(diǎn)、左子樹和右子樹。 若限定先左后右，則只有前三種情況，分別稱之為 先（根）序遍歷， 中（根）序遍歷和后（根）序遍歷 。（

27、 1）先序遍歷算法 若二叉樹為空樹，則空操作；否則，訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。void PreOrder（BiTree bt）/* 先序遍歷二叉樹 bt*/ if （bt=NULL） return; /* 遞歸調(diào)用的結(jié)束條件 */ Visite（bt->data）;/*（1） 訪問結(jié)點(diǎn)的數(shù)據(jù)域 */PreOrder (bt->lchild) ; /*(2)先序遞歸遍歷 bt的左子樹*/PreOrder (bt->rchild) ;/*(3)先序遞歸遍歷 bt 的右子樹 */void preorder(JD *bt) if(bt!二NULL) prin tf(

28、"%dt",bt->data);preorder(bt->lchild); preorder(bt->rchild);(2)中序遍歷算法若二叉樹為空樹，則空操作；否則,先序遍歷左子樹；訪問根結(jié)點(diǎn)；先序遍歷右子樹。void In Order( BiTree bt /* 先序遍歷二叉樹 bt*/if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/In Order (bt->lchild) ; /*(2)先序遞歸遍歷 bt的左子樹*/Visite ( bt->data) ;/*(1)訪問結(jié)點(diǎn)的數(shù)據(jù)域*/In Order( bt->

29、;rchild);/*(3)先序遞歸遍歷bt的右子樹*/(3)后序遍歷算法A C否則,若二叉樹為空樹，則空操作；先序遍歷左子樹；先序遍歷右子樹； 訪問根結(jié)點(diǎn)。void PostOrder( BiTree bt)/* 后序遍歷二叉樹 bt*/ if (bt=NULL) return; /*遞歸調(diào)用的結(jié)束條件*/ PostOrder( bt->lchild);/*(1)后序遞歸遍歷 bt 的左子樹 */ PostOrder( bt->rchild) ; /*(2)后序遞歸遍歷bt的右子樹 Visite (bt->data) ;/*(3)訪問結(jié)點(diǎn)的數(shù)據(jù)域 */例題：后序遍歷序列：D

30、(4) 層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層(根結(jié)點(diǎn))開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問層次遍歷序列:12 3 4 5 67、例題:1、先序序列：A B C D E F G H K中序序列：B D C A E H G K F后序序列：D C B H K G F E K層次序列：A B E C F D G H K2、若先序遍歷此二叉樹，按訪問結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來，其先序序列為：-+a*b-cd/ef按中序遍歷，其中序序列為：a+b*c-d-e/f按后序遍歷，其后序序列為：abcd-*+ef/ -8 (1)查詢二叉樹中某個(gè)結(jié)點(diǎn)Status P

31、reorder (BiTree T, ElemType x, BiTree &p) /若二叉樹中存在和x相同的元素，則p指向該結(jié)點(diǎn)并/返回0K,/否則返回FALSEif (T) if (T->data= =x) p = T; return OK,else else (Preorder(T->rchild, x, p) return OK;/else/ifelse return FALSE;2)計(jì)算二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)int CountLeaf (BiTree T)/ 返回指針 T 所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù) if (!T ) return 0;if (!T->lc

32、hild && !T->rchild) return 1;elsem = CountLeaf( T->lchild); n = CountLeaf( T->rchild);return (m+n); /else / CountLeaf3) 求二叉樹的深度 (后序遍歷 )int Depth (BiTree T ) / 返回二叉樹的深度 if ( !T )depthval = 0; else depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild ); depthval = 1 + (de

33、pthLeft > depthRight ?depthLeft : depthRight); return depthval;( 4)按先序遍歷序列建立二叉樹Status CreateBiTree(BiTree &T ) / 按先序次序輸入二叉樹中結(jié) 點(diǎn)的值 (一個(gè)字符)，空格字符表示空樹， 構(gòu)造二叉鏈表表示的 二叉樹 Tscanf (&ch);if ( ch= ) T=NULL; else if(!T=(BiTNode *)malloc(sizeof(BiTNode) exit (OVERFLOW);T->data=ch; /生成根結(jié)點(diǎn)CreateBiTree(T

34、->lchild);/構(gòu)造左子樹 CreateBiTree(T->rchild);/構(gòu)造右子樹Return OK; /CreateBiTree9、遍歷二叉樹的非遞歸算法(1)先序遍歷二叉樹的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹非遞歸算法 / int i=0;JD *p,*sM;p=r;do while(p!=NULL) printf("%dt",p->data);if (p->rc!=NULL)si+=p->rc;p=p->lc; if ( i > 0) p=s-i;while( i>0 | p!

35、=NULL); 2)中序遍歷二叉樹的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹非遞歸算法 / int i=0; JD *p,*sM; p=r;do while(p!=NULL) si+=p; p=p->lc; if (i>0) p=s-i;printf("%dt",p->data); p=p->lc; if ( i > 0) p=s-i;while( i>0 | p!=NULL); 3) 后序遍歷二叉樹的非遞歸算法p=r;void inorder(JD *r)/ 先序遍歷二叉樹非遞歸算法 / int s2M,b,i

36、=0; JD *p,*s1M;do while(p!二NULL)s1i-1=p;s2i+=0;p=p->lc;while (i>0 && (s2i-1=1)p=s1-i; printf( “%dt” ,p->data ); if (i>0)p=s-i;prin tf("%dt",p->data);p=p->lc;if ( i > 0) s2i-1=1; p=s1i-1; p=p->rc; while( i>0);11、線索二叉樹：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左右孩子的信息，而不能在結(jié)點(diǎn)的任一序

37、列的前驅(qū)與后繼信息， 這種信息只有在遍歷的動(dòng)態(tài)過程中才能得到，為了能保存所需 的信息，可增加標(biāo)志域；lchildLtagdataRtagrchildLtag=0，lchild域指示結(jié)點(diǎn)的左孩子；Ltag=1, lchild域指示結(jié)點(diǎn)的前驅(qū)。Rtag=0, rchild域指示結(jié)點(diǎn)的右孩子；Rtag=1, rchild域指示結(jié)點(diǎn)的后驅(qū)以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)， 叫做線索鏈 表，其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線索， 加上線索的二叉樹稱 之為線索二叉樹。先序線索二叉樹* 中序序列：BCAED中序線索二叉樹(3)后序線索二叉樹12、樹的存儲(chǔ)結(jié)構(gòu)雙親表示法SIZE100a0b1c1d

38、2e2f3g5h55data parent2467S9typedef struct PTNode /結(jié)點(diǎn)結(jié)構(gòu)ElemType data;intpare nt;/雙親位置域 PTNode;typedef struct / 樹結(jié)構(gòu)PTNode nodesMAX_TREE_SIZE;int r, n; /根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;孩子表示法9（帶雙親的孩子鏈表12anbtc1d2Ae2r34g5Ah5*715A79data jiMrent $(2464k+ 7 孩子兄弟表示法鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)typedef struct node datat

39、ype data;struct node *fch, *n sib;JD;13、樹和森林與二叉樹的轉(zhuǎn)換-SCM加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系,oAe)BEF卜:HAEFBFA-* -FJ.L)旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn) 4513、將二叉樹轉(zhuǎn)換成樹加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與 p的雙親用線連起來.抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)14、森林轉(zhuǎn)換二叉樹(1)將各棵樹分別轉(zhuǎn)換成二叉樹(2)將每棵樹的根結(jié)點(diǎn)用線相連(3) 以第一

40、棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)14、二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線， 及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成15、樹和森林的遍歷樹的遍歷兩種次序遍歷樹的方法：一種是先根(次序)遍歷樹，即先訪問樹的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹；一種是后根（次序）遍歷，即先依次后根遍歷每棵子樹，然后訪問根 結(jié)點(diǎn)。森林的遍歷先序遍歷：A B C D E F G H I J先根序列：A B C D E 后根序列：B D C E A中序遍歷：B C D A F E H J I G16、赫夫曼樹及其應(yīng)

41、用例題： w=5, 29, 7, 8, 14, 23, 3, 1150 110291 0711108111114110230 030 111110 10習(xí)題:1、由于二叉樹中每個(gè)結(jié)點(diǎn)的度最大為 2,所以二叉樹是一種特殊的 樹，這種說法_B_。（A）正確（B）錯(cuò)誤2、某二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹一定是D_。（A）空或只有一個(gè)結(jié)點(diǎn)（B）完全二叉樹（C）二叉排序樹（D）高度等于其節(jié)點(diǎn)數(shù)3、深度為5的二叉樹至多有C個(gè)結(jié)點(diǎn)。（A）16( B)32（C）31（D）104、根據(jù)使用頻率為5個(gè)字符設(shè)計(jì)的赫夫曼編碼不可能是 C（A）111，110，10，01，00（B）000，001

42、，010，011，1(C) 100，11，10，1，0(D) 001, 000, 01, 11, 10 5、 樹和二叉樹的主要差別是(1) 樹的結(jié)點(diǎn)個(gè)數(shù)至少為 1,而二叉 樹的結(jié)點(diǎn)個(gè)數(shù)可以為 0 (2)樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉 樹結(jié)點(diǎn)的最大度數(shù)為 2 (3)樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié) 點(diǎn)右左、右之分。6、 深度為k的完全二叉樹至少有 個(gè)結(jié)點(diǎn)，至多有 個(gè)結(jié)點(diǎn)，若按自上而下，從左到右次序給結(jié)點(diǎn)編號(hào)(從 1開始)，則編 號(hào)最小的葉子結(jié)點(diǎn)的編號(hào) 。7、一棵二叉樹的第i(i 1)層最多有個(gè)結(jié)點(diǎn)；一棵有n(n>0)個(gè)結(jié)點(diǎn)的滿二叉樹共有 個(gè)葉子結(jié)點(diǎn)和_個(gè)非葉子結(jié)點(diǎn)。8已知二叉樹的先序

43、、中序和后序序列分別如下，其中有一些看不 清的字母用*表示，請(qǐng)構(gòu)造出一棵符合條件的二叉樹并畫出該二叉樹。先序序列是：*BC*FG中序序列是：CB*EAG*后序序列是：*EDB*FA9、將右圖所示的樹轉(zhuǎn)化為一叉樹，并與出先序遍歷，中序遍歷和后序遍歷的結(jié)果先序：ABEFGCDHI中序：EFGBCHIDA后序：GFEIHDCBA10、設(shè)給定權(quán)集w=2, 3，4，7，8，9，試構(gòu)造關(guān)于w的一棵赫夫曼樹，并求其加權(quán)路徑長度WPL。WPL=(9+7+8)*2+4*3+(2+3)*4=80第十章內(nèi)部排序1、內(nèi)排序大致可分為五類：插入排序、交換排序、選擇排序、歸并排序和分配排序。（插入排序（直插排序、二分排序

44、、希爾排序）交換排序（昌泡排序、快速排序）排序選擇排序（直選排序.樹型排序.堆排序）歸并排序（二路歸井排序、多路歸并排序）分配排序（多關(guān)鍵字排序.基數(shù)排序）2、直接插入排序直接插入的算法實(shí)現(xiàn)void sort(NODE array,i nt n)/待排序元素用一個(gè)數(shù)組array表示，數(shù)組有n個(gè)元素 int i, j;NODE x;/ x為中間結(jié)點(diǎn)變量for ( i=1; i<n; i+)/i表示插入次數(shù)，共進(jìn)行n-1次插入 x=arrayi;/把待排序元素賦給xj=i-1;while (j>=0)&& (x.key<arrayj.key)arrayj+1=ar

45、rayj; j-; / 順序比較和移動(dòng)arrayj+1=x; 例如，n=6,數(shù)組R的六個(gè)排序碼分別為：17, 3, 25,14, 20, 9它的直接插入排序的執(zhí)行過程如圖7-1所示。012345初始狀態(tài)(17 )3J2514209t第一次插入(317 )2514209第二次插入(317T25 )14|209第三次插入(3141725 )2019t第四次插入(314172025 )9第五次插入 (3914172025)圖10-1直接插入排序示例直接插入排序的時(shí)間復(fù)雜度為 O (n2)。直接插入算法的元素移動(dòng)是順序的，該方法是穩(wěn)定的。3、希爾排序希爾排序的時(shí)間復(fù)雜性在 O (nlog2n)和O (

46、n2 )之間，大致為O( n 1.3)。由于希爾排序?qū)γ總€(gè)子序列單獨(dú)比較，在比較時(shí)進(jìn)行元素移動(dòng)， 有可能改變相同排序碼元素的原始順序，因此希爾排序是不穩(wěn)定的。例如，n=8,數(shù)組array的八個(gè)元素分別為：91, 67, 35, 62, 29, 72, 46, 57。下面用圖10-2給出希爾排序算法的執(zhí)行過程。初始狀態(tài)，setp=49167 35 62 29 72 46 57第一趟結(jié)果,step=229673557917246624、交換排序1) 冒泡排序 冒泡排序的算法實(shí)現(xiàn)void Bubblesort( NODE array,int n) int i, j, flag;/ 當(dāng) flag 為

47、0 則停止排序NODE temp;for ( i=1; i<n; i+) / i 表示趟數(shù)，最多 n-1 趟 flag=0; / 開始時(shí)元素未交換for ( j=n-1; j>=i; j-)if (arrayj.key<arrayj-1.key) / 發(fā)生逆序 temp=arrayj;arrayj=arrayj-1;arrayj-1=temp; flag=1; / 交換，并標(biāo)記發(fā)生了交換if(flag=0) break; 例如，n=6,數(shù)組R的六個(gè)排序碼分別為：17, 3, 25,14, 20, 9 下面用圖10-3給出冒泡排序算法的執(zhí)行過程。012345初始狀態(tài)(173J2

48、514209)+第一趟排序3f廠第二趟排序39(171412520)1*第三趟排序3914(172025)第四趟排序3914172025圖10-3冒泡排序示例冒泡排序算法的時(shí)間復(fù)雜度為 O (n2)。由于其中的元素移動(dòng)較多, 所以屬于內(nèi)排序中速度較慢的一種。因?yàn)槊芭菖判蛩惴ㄖ贿M(jìn)行元素間的順序移動(dòng)，所以是一個(gè)穩(wěn)定的算 法。2) 快速排序快速排序(Quick Sorting)是迄今為止所有內(nèi)排序算法中速度最快的 一種。快速排序的算法實(shí)現(xiàn)void quicksort(NODE array,int start , int end) int i , j; NODE mid;if

49、 (start>=e nd) return;i=start;j=e nd;mid二arrayi;while (ivj) while (i<j && arrayj.key>mid.key) j-;if (i<j) arrayi=arrayj; i+;while (i<j && arrayi.key<二mid.key)i+;if (i<j) arrayj=arrayi; j-; II 一次劃分得到基準(zhǔn)值的正確位置arrayi=mid;quicksort(array,start,i-1);II 遞歸調(diào)用左子區(qū)間quicksort(array,i+1,e nd); / 遞歸調(diào)用右子區(qū)間例如，給定排序碼為：(46, 55, 13, 42, 94, 05，17, 70),具 體劃分如圖10-4所示。46i55134294051770 j46i551342940517 j70 175571342940546j70 174613429405 j5570 170513i429446 j5570 1705T1342i94146 j5570 17051342i94146j5570 17051342 46945570 廿j圖 10-4快速排序的一次劃分快速排序所占用的輔助