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

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

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

3、 基本操作在計算機上的實現(xiàn)（方法 ）。15、數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念16、數(shù)據(jù)元素的 4 類的基本結(jié)構(gòu) ： 集合； 線性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對一的關(guān)系； 樹形結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對多的關(guān)系； 4 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在多對多 的關(guān)系。17、C語言的優(yōu)點：C語言可以直接操作內(nèi)存。18、每個節(jié)點都由兩部分組成： 數(shù)據(jù)域和指針域 。19、鏈接存儲結(jié)構(gòu)特點：比順序存儲結(jié)構(gòu)的存儲密度小(每個節(jié)點都由數(shù)據(jù)域和指針域組成 )。 邏輯上相鄰的節(jié)點物理上不必相鄰。插入、刪除靈活 (不必移動節(jié)點，只要改變節(jié)點中的指針 )。20、數(shù)據(jù)類型 是一個值的集合和定義在此集合上的一組操作的

4、 總稱。21、ADT 有兩個重要特征 :數(shù)據(jù)抽象 和數(shù)據(jù)封裝 。22、抽象數(shù)據(jù)類型(Abstract Data Type簡稱ADT):是指一個數(shù) 學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。23、抽象數(shù)據(jù)類型有:數(shù)據(jù)對象 數(shù)據(jù)對象的定義 、數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系的定義、 基本操作 基本操作的定義 。24、數(shù)據(jù)類型的定義和含義。 定義:數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組 操作的總稱。含義:將數(shù)據(jù)按一定次序與形式存放的結(jié)構(gòu)。24、算法空間復(fù)雜度 S(n) 算法的存儲量包括: 輸入數(shù)據(jù)所占的空間； 程序本身所占的空間； 輔助變量所占的空間。25、算法具有 有窮性、確定性、可行性、輸入和輸出五大特性

5、。26、抽象數(shù)據(jù)類型具有 數(shù)據(jù)抽象、數(shù)據(jù)封裝 的特點。27、數(shù)據(jù)的儲存結(jié)構(gòu)分為： 順序存儲結(jié)構(gòu) 和 鏈?zhǔn)酱鎯Y(jié)構(gòu) 。 第二章 線性表1、線性結(jié)構(gòu)的特點：在數(shù)據(jù)元素中的非空有限集中。(1) 存在唯一的一個被稱作“第一”的數(shù)據(jù)元素；(2) 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素；(3) 除第一個外，集合中的每一個數(shù)據(jù)元素均只有一個前驅(qū)；(4) 除最后一個外，集合中的每一個數(shù)據(jù)元素均只有一個后繼。2、線性表 (Linear List) ：一個線性表是 n 個數(shù)據(jù)元素的有限序列3、線性表的順序存儲實現(xiàn)：typedef struct ElementType DataMAXSIZE;int Last;

6、 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 && PtrL->Datai!= X )i+;if (i > PtrL->Last) return -1; /* 如果沒找到，返回 -1

7、*/else return i; /* 找到后返回的是存儲位置 */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) /*檢查插入位置的合法性 */ printf( 位置不合法 );return;for ( j = PtrL->Last; j >= i-1; j- )PtrL->Dataj+

8、1 = PtrL->Dataj; /* 將 ai an 倒序向后移動 */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 (不存在第d個元素” ,i ); return ;for ( j = i; j <= PtrL->Last; j+ )PtrL->D

9、ataj-1 = PtrL->Dataj; /* 將 ai+1 an順序向 前移動*/PtrL->Last-; /*Last 仍指向最后元素 */ return;8、求表長int Length ( List *PtrL ) List *p = PtrL;/* p 指向表的第一個結(jié)點 */int j = 0;while ( p ) p = p->Next;j+; /* 當(dāng)前 p 指向的是第 j 個結(jié)點 */return j;9、查找( 1)按序號查找 : FindKth;List *FindKth( int K, List *PtrL ) List *p = PtrL;int

10、i = 1;while (p !=NULL && i < K ) p = p->Next;i+;if ( i = K ) return p;/* 找到第 K 個，返回指針 */else return NULL;/* 否則返回空 */( 2)按值查找 : FindList *Find( ElementType X, List *PtrL )List *p = PtrL;while ( p!=NULL && p->Data != X )p = p->Next;return p;10、插入(在鏈表的第i-1(1w iw n+1)個結(jié)點后插入一個

11、值為 X的新 結(jié)點 )List *Insert( ElementType X, int i, List *PtrL )List *p, *s;if ( i = 1 ) /* 新結(jié)點插入在表頭 */s = (List *)malloc(sizeof(List); /*申請、填裝結(jié)點 */ s->Data = X;s->Next = PtrL;return s; /* 返回新表頭指針 */p = FindKth( i-1, PtrL );/* 查找第 i-1 個結(jié)點 */if ( p = NULL ) /* 第 i-1 個不存在，不能插入 */printf(H 參數(shù) i 錯"

12、)；return NULL;else s = (List *)malloc(sizeof(List); /*申請、填裝結(jié)點*/s->Data = X;s->Next = p->Next; /* 新結(jié)點插入在第 i-1 個結(jié)點的后面 */p->Next = s;return PtrL;11、刪除(刪除鏈表的第i (1<iWn)個位置上的結(jié)點)List *Delete( int i, List *PtrL )List *p, *s;/* 若要刪除的是表的/*s 指向第 1 個結(jié)點/* 從鏈表中刪除 */* 釋放被刪除結(jié)點if ( i = 1 ) 第一個結(jié)點 */s =

13、 PtrL;*/PtrL = PtrL->Next; free(s);*/return PtrL;if ( p = NULL ) NULL; elseNULL; elseprintf（第小個結(jié)點不存在”卜1）;if ( p->Next = NULL )printf（ 第%d個結(jié)點不存在” j）;s = p->Next;returnreturn/*s指向第i個結(jié)點*/p->Next = s->Next;/*從鏈表中刪除*/free(s);/*釋放被刪除結(jié)點*/retur n PtrL;12、鏈表不具備的特點是可隨機訪問任一節(jié)點插入刪除不須要移動元素 不必事先估計存儲

14、空間所需空間與其長度成正比13、帶頭結(jié)點的單鏈表head為空的判定條件是 2 head=NULL head->n ext=head head-> next=NULL head!二NULL14、如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用 存儲方式最節(jié)省時間。單鏈表 雙鏈表 單循環(huán)鏈表 順序表第三章 Chapter 3 棧(stacks)和隊列(queues)1、棧是限定僅能在表尾一端進行 插入、刪除 操作的線性表。2、棧的特點是“后進棧的元素先出棧” (last in, first out),故棧又 稱為后進先出表( LIFO)。3、一個棧是一些元素的線形列表，其中元素的插入和刪

15、除均在表的同一端進行。插入和刪除發(fā)生的一端稱為棧頂(the top of thestack)。4、第一個進棧的元素在棧底，5、最后一個進棧的元素在棧頂， 第一個出棧的元素為棧頂元素， 最后一個出棧的元素為棧底元素。6、連續(xù)棧(Contiguous Stack的類型定義#define MaxStack 50Typedef structdatatype stackMaxStack;int top;Seqstack;Seqstack *s;7、判斷棧是否已滿viod Push(Seqstack *s, datatype x )if (s->top>=MaxStack-1) printf(

16、“ overflow ” ); else s-> top+;s->stacks->top=x;8、判斷棧是否為空datatype pop(Seqstack *s ) if (s->top<0)printf(“underflow”); return(NULL); return(s->stacks->top); s->top-;9、返回棧頂元素的值，棧不發(fā)生變化。datatype top(Seqstack *s ) if (s->top<0)printf(“underflow”); return(NULL); return(s->s

17、tacks->top);10、鏈棧(Linked Stack的類型定義棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧， 它是運算受限的單鏈表， 插入和刪除操作僅限制在表頭位置上進行。 由于只能在鏈表頭部進行操作， 故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧頂指針就是鏈表的頭指針鏈棧的類型說明如下：typedef struct stacknode datatype datastruct stacknode *nextstacknode11、鏈?zhǔn)綏５奶攸c： 鏈?zhǔn)綏o棧滿問題；空間可擴充；插入與刪除僅在棧頂處執(zhí)行； 鏈?zhǔn)綏５臈ｍ斣阪滎^；適合于多棧操作。11、棧是限定僅能在表的一端進行插入、刪除操作的線性表 。12、棧

18、的元素具有后進先出的特點 。13、棧頂元素的位置由棧頂指針的指示 , 進棧、出棧操作要修改棧 頂指針。14、抽象數(shù)據(jù)類型隊列的定義：隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進 行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front),允許插入的一端稱為隊尾 (rear)。15、 隊列亦稱作先進先出(First In First Out的線性表，簡稱FIFO表。16、雙端隊列：就是限定插入和刪除操作在表的兩端進行的線性表。17、鏈隊列結(jié)點定義：typedef struct Qnode QElemType data;struct QNode *n ext; QNode

19、,*QueuPtr;18、隊列的順序存儲結(jié)構(gòu)稱為 順序隊列，在隊列的順序存儲結(jié)構(gòu)中， 除了用一組地址連續(xù)的儲存單元依次存放從隊頭到隊尾的元素 之外，尚需要附設(shè)兩個指針front和rear分別指示隊列頭元素 和隊列尾元素的位置。19、在非空隊列中，頭指針始終指向隊頭元素，而尾指針始終指向 隊尾元素的下一位置。20、棧的特點是先講后出，隊列的特點是先講后出 21、棧和隊列的共同特點是只允許在端點處插入和刪除元素 22、一個棧的進棧序列是a, b, c, d, e,則棧的不可能的輸出序列(A) edcba (B) decba(C) dceab(D) abcde 23、若已知一個棧的進棧序列是p1,

20、p2, p3,，pn。其輸出序列為1, 2, 3,，n，若p3=1，則p1為 C 。(A) 可能是2 (B)定是2 (C)不可能是2 (D)不可能是324、設(shè)有一個空棧，棧頂指針為 1000H (十六進制，下同)，現(xiàn)有輸入序列為 1、2、3、4、5,經(jīng)過 PUSH PUSH POP PUSH POP PUSHPUSH 后，輸出 序列是 3, 棧頂指針是8。 5、4、3、2、12、1 2、33、41002H1004H24、一個隊列的入隊序列是若1, 2 , 3, 4,則隊列的輸出序列是B。(A) 4, 3, 2, 1(B) 1, 2, 3, 4(C) 1, 4, 3, 2(D) 3, 2, 4,

21、 125、若用一個大小為6的一維數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和 front的值分別為0和3。當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別是B。(A) 1 禾口 5(B) 2 和 4(C) 4 和 2( D) 5 和 126、有5個元素，其入棧次序為A、B、C D、E,在各種可能的出棧 次序中，以元素C、D最先出棧（即C第一個且D第二個出棧）的次 序有哪幾個C、D、B、A、EC、D、E、B、AC、D、B、E、A第六章樹和二叉樹1、樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。2、樹的定義：樹是n（n>=0）個結(jié)點的有限集T, T為空時稱為空樹， 否則它滿足如下兩個條件：（

22、1）有且僅有一個特定的稱為根的結(jié)點；（2）當(dāng)n>1時，其余結(jié)點可分為 m（m>0）個互不相交的有限集T1, T2, T3Tm,其中每個子集又是一棵樹，并稱其為根的子樹 。3、基本術(shù)語結(jié)點表示樹中的元素， 包括數(shù)據(jù)項及若干指向其子樹的分支結(jié)點的度(degree)結(jié)點擁有的子樹數(shù)葉子(leaf)度為0的結(jié)點孩子(child)結(jié)點子樹的根稱為該結(jié)點的孩子雙親(parents)孩子結(jié)點的上層結(jié)點叫該結(jié)點的兄弟(sibling)同一雙親的孩子樹的度 一棵樹中最大的結(jié)點度數(shù)結(jié)點的層次(level)從根結(jié)點算起，根為第一層，它的孩子為第二層深度(depth)樹中結(jié)點的最大層次數(shù)森林(forest

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

24、從 第 1 層到第 log2n +1 層，每層從左到右 ) ，則對任一結(jié)點 (i 1<=i<=n)，有：(1) 如果i= 1,則結(jié)點i無雙親，是二叉樹的根；如果i>1, 則其雙親是結(jié)點 i/2 。(2) 如果2i>n,則結(jié)點i為葉子結(jié)點，無左孩子；否則，其左 孩子是結(jié)點 2i。(3) 如果2i+1>n,貝卩結(jié)點i無右孩子；否則，其右孩子是結(jié) 點 2i1 。一棵深度為 k 且有 2k-1 個結(jié)點的二叉樹稱為滿二叉樹。如：5、二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)define MAX-TREE-SIZE 1 00Typedef TelemType SqBiTree MAX-TR

25、EE-SIZE;SqBitree bt;缺點是有可能對存儲空間造成極大的浪費。鏈?zhǔn)酱鎯Y(jié)構(gòu) 二叉鏈?zhǔn)酱鎯Y(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、遍歷二叉樹 二叉樹是由三個基本單元組成：根結(jié)點、左子樹和右子樹。 若限定先左后右，則只有前三種情況，分別稱之為 先(根)序遍歷， 中(根)序遍歷和后(根)序遍

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

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

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

29、 bt->data);/*(3) 訪問結(jié)點的數(shù)據(jù)域 */例題：后序遍歷序列： D B C A( 4)層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層(根結(jié)點)開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問層次遍歷序列 :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é)點的先后次序?qū)⒔Y(jié)點排列起來， 其先 序序列為： -+a*b-cd/ef按中序遍歷，其中序序列為： a+

30、b*c-d-e/f 按后序遍歷，其后序序列為： abcd-*+ef/ -8、( 1 )查詢二叉樹中某個結(jié)點Status Preorder (BiTree T, ElemType x, BiTree &p) / 若二叉樹中存在和 x 相同的元素，則 p 指向該結(jié)點并/ 返回 OK,/ 否則返回 FALSEif (T) if (T->data= =x) p = T; return OK,else if (Preorder(T->lchild, x, p) return OK;else (Preorder(T->rchild, x, p) return OK;/else/i

31、felse return FALSE;(2)計算二叉樹中葉子結(jié)點的個數(shù)int CountLeaf (BiTree T)/ 返回指針 T 所指二叉樹中所有葉子結(jié)點個數(shù)if (!T ) return 0;if (!T->lchild && !T->rchild) return 1;elsem = CountLeaf( T->lchild);n = CountLeaf( T->rchild);return (m+n); /else / CountLeaf3) 求二叉樹的深度 (后序遍歷 )int Depth (BiTree T ) / 返回二叉樹的深度if (

32、 !T ) depthval = 0; else depthLeft = Depth( T->lchild );depthRight= Depth( T->rchild );depthval = 1 + (depthLeft > depthRight ?depthLeft : depthRight);return depthval;4) 按先序遍歷序列建立二叉樹Status CreateBiTree(BiTree &T ) /按先序次序輸入二叉樹中結(jié) 點的值 (一個字符)，空格字符表示空樹， 構(gòu)造二叉鏈表表示的 二叉樹 Tscanf (&ch);if ( ch

33、= ) T=NULL; else if(!T=(BiTNode *)malloc(sizeof(BiTNode) exit (OVERFLOW); T->data=ch; /生成根結(jié)點CreateBiTree(T->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(&

34、quot;%dt",p->data);if (p->rc!=NULL)si+=p->rc;p=p->lc;if ( i > 0) p=s-i;while( i>0 | p!=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 &

35、gt; 0) p=s-i;while( i>0 | p!=NULL); ( 3)后序遍歷二叉樹的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹非遞歸算法 / int s2M,b,i=0; JD *p,*s1M; p=r;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;printf("%dt",p->data);p=p->lc;

36、if ( i > 0) s2i-1=1; p=s1i-1; p=p->rc; while( i>0); 12、線索二叉樹：以二叉鏈表作為存儲結(jié)構(gòu)時，只能找到結(jié)點的左右孩子的信息，而不能在結(jié)點的任一序列的前驅(qū)與后繼信息，這種信息只有在遍歷的動態(tài)過程中才能得到，為了能保存所需的信息，可增加標(biāo)志域lchildLtagdataRtagrchildLtag=O , Ichild域指示結(jié)點的左孩子；Ltag=1, Ichild域指示結(jié) 點的前驅(qū)。Rtag=O, rchild域指示結(jié)點的右孩子；Rtag=1, rchild域指示結(jié)點 的后驅(qū)。以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，

37、叫做線索鏈 表，其中指向結(jié)點前驅(qū)與后繼的指針叫做線索， 加上線索的二叉樹稱 之為線索二叉樹。（1）先序線索二叉樹（2）中序線索二叉樹（3）后序線索二叉樹13、樹的存儲結(jié)構(gòu)雙親表示法#define MAX_TREE_SIZE100typedef struct PTNode /結(jié)點結(jié)構(gòu)ElemType data;int pare nt; /雙親位置域 PTNode;typedef struct / 樹結(jié)構(gòu)PTNode nodesMAX_TREE_SIZE; PTree;孩子表示法（帶雙親的孩子鏈表 孩子兄弟表示法 鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個 兄弟結(jié)點。typedef

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

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

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

41、0，01，11，105、樹和二叉樹的主要差別是（1）樹的結(jié)點個數(shù)至少為 1，而二叉 樹的結(jié)點個數(shù)可以為 0 （2）樹中結(jié)點的最大度數(shù)沒有限制，而二叉 樹結(jié)點的最大度數(shù)為 2 （3）樹的結(jié)點無左、右之分，而二叉樹的結(jié) 點右左、右之分。6、 深度為k的完全二叉樹至少有 個結(jié)點，至多有 個結(jié)點，若按自上而下，從左到右次序給結(jié)點編號（從 1開始），則編 號最小的葉子結(jié)點的編號 。7、一棵二叉樹的第i(i 1)層最多有個結(jié)點；一棵有n(n>0)個結(jié)點的滿二叉樹共有 個葉子結(jié)點和_個非葉子結(jié)點。8已知二叉樹的先序、中序和后序序列分別如下，其中有一些看不清的字母用*表示，請構(gòu)造出一棵符合條件的二叉樹并

42、畫出該二叉樹。先序序列是：*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)排序大致可分為五類：插入排序、交換排序、選擇排序、歸并 排序和分配排序。2、直接插入排序直接插入的算法實現(xiàn)void sort(NODE array,i nt n)/待排序元素用一個

43、數(shù)組array表示，數(shù)組有 n個元素 int i, j;NODE x;/ x為中間結(jié)點變量for ( i=1; i<n; i+)/i表示插入次數(shù)，共進行n-1次插入 x=arrayi; /把待排序元素賦給xj=i-1;while (j>=0)&& (x.key<arrayj.key)arrayj+1=arrayj; j-; / 順序比較和移動 arrayj+1=x; 例如，n=6,數(shù)組R的六個排序碼分別為：17，3, 25,14, 20，9。它的直接插入排序的執(zhí)行過程如圖7-1所示。012345初始直接插入排序的時間復(fù)雜度為14 O( n2»)o9第

44、-直接插入算法的元素移動是順序的，該方法是9穩(wěn)定的。Kt3、第希次插排序(31725 )14209希爾排序的時間復(fù)雜性在 0 (nlog2n)和0 (n2 )之間，大致為第三次插入 (3141725 )209O(n1.3)。F第四次插入(31417 2025 )9由于希爾排序?qū)γ總€子序列單獨比較，在比較時進行元素移動，有可1改變相同排序碼元素的原始順序,20因此希爾排序是不穩(wěn)定的。圖10-1直接插入排序示例例如，n=8,數(shù)組array的八個元素分別為：91，67，35，62，29,72, 46, 57。下面用圖10-2給出希爾排序算法的執(zhí)行過程4、交換排序1) 冒泡排序 冒泡排序的算法實現(xiàn)vo

45、id Bubblesort( NODE array,int n) int i, j, flag; / 當(dāng) flag 為 0 則停止排序NODE temp;for ( i=1; i<n; i+) / i 表示趟數(shù)，最多 n-1 趟 flag=0;/ 開始時元素未交換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的六個排序碼分別為

46、：17, 3, 25,14, 20, 9。下面用圖 10-3 給出冒泡排序算法的執(zhí)行過程。冒泡排序算法的時間復(fù)雜度為 O (n2)。由于其中的元素移動較多， 所以屬于內(nèi)排序中速度較慢的一種。因為冒泡排序算法只進行元素間的順序移動,所以是一個穩(wěn)定的算 法。2) 快速排序 快速排序(Quick Sorting)是迄今為止所有內(nèi)排序算法中速度最快的一種?？焖倥判虻乃惴▽崿F(xiàn)void quicksort(NODE array,int start , int end) int i , j; NODE mid;if (start>=end) return;i=start;j=end;mid=array

47、i;while (i<j) 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-; / 一次劃分得到基準(zhǔn)值的正確位置arrayi=mid;quicksort(array,start,i-1);/ 遞歸調(diào)用左子區(qū)間quicksort(array,i+1,end); /遞歸調(diào)用右子區(qū)間 例如，給定排序碼為： ( 46，55，

48、13，42，94，05，17，70) ，具 體劃分如圖 10-4 所示。快速排序所占用的輔助空間為棧的深度， 故最好的空間復(fù)雜度為O(log2n),最壞的空間復(fù)雜度為 0(n)?？焖倥判蚴且环N不穩(wěn)定的排序方法。5、選擇排序1) 直接選擇排序例如，給定n=8,數(shù)組R中的8個元素的排序碼為：(8, 3, 2, 1,乙 4， 6， 5)，則直接選擇排序過程如圖 7-5 所示。直接選擇排序的時間復(fù)雜度為 0( n2)數(shù)量級2) 樹形選擇排序例如,給定排序碼頭 50, 37, 66, 98, 75, 12, 26, 49,樹形選擇 排序過程見圖 7-7。3) 堆排序例如,給定排序碼 49, 38, 65

49、, 97, 76, 13, 27, 70,建立初始堆 的過程如圖 7-8所示。按層次遍歷完全二叉樹,得到一個由大到小排列的有序序列：97, 76, 70, 65, 49, 38, 27, 13每次篩選運算的時間復(fù)雜度為 O(log2 n),故整個堆排序過程的時間復(fù) 雜度為 0(nlog2n)。5、歸并排序例如,給定排序碼 46, 55, 13, 42, 94, 05, 17, 70,二路歸并排 序過程如圖 7-10所示。二路歸并排序的時間復(fù)雜度為 0(nlog2n)。6、各種內(nèi)排序方法的比較和選擇1)從時間復(fù)雜度比較 從平均時間復(fù)雜度來考慮,直接插入排序、冒泡排序、直接選擇 排序是三種簡單的排

50、序方法，時間復(fù)雜度都為0(n2),而快速排序、 堆排序、二路歸并排序的時間復(fù)雜度都為 O(nl og2 n),希爾排序的復(fù) 雜度介于這兩者之間。 若從最好的時間復(fù)雜度考慮， 則直接插入排序 和冒泡排序的時間復(fù)雜度最好，為0(n),其它的最好情形同平均情形 相同。若從最壞的時間復(fù)雜度考慮，則快速排序的為 0(n2),直接插 入排序、冒泡排序、希爾排序同平均情形相同, 但系數(shù)大約增加一倍, 所以運行速度將降低一半, 最壞情形對直接選擇排序、 堆排序和歸并 排序影響不大。2) 從空間復(fù)雜度比較歸并排序的空間復(fù)雜度最大，為0(n),快速排序的空間復(fù)雜度為O(log2 n),其它排序的空間復(fù)雜度為 0(

51、 1)。3) 從穩(wěn)定性比較直接插入排序、冒泡排序、 歸并排序是穩(wěn)定的排序方法,而直接選擇 排序、希爾排序、快速排序、堆排序是不穩(wěn)定的排序方法。4) 從算法簡單性比較直接插入排序、冒泡排序、 直接選擇排序都是簡單的排序方法,算法 簡單,易于理解,而希爾排序、快速排序、堆排序、歸并排序都是改 進型的排序方法,算法比簡單排序要復(fù)雜得多,也難于理解。8、各種內(nèi)排序方法的選擇1 )從時間復(fù)雜度選擇 對元素個數(shù)較多的排序,可以選快速排序、堆排序、歸并排序, 元素個數(shù)較少時,可以選簡單的排序方法。2)從空間復(fù)雜度選擇盡量選空間復(fù)雜度為 0( 1)的排序方法，其次選空間復(fù)雜度為O(log2n)的快速排序方法，

52、最后才選空間復(fù)雜度為0 (n)二路歸并排 序的排序方法。3) 一般選擇規(guī)則當(dāng)待排序元素的個數(shù) n 較大，排序碼分布是隨機，而對穩(wěn)定性不 做要求時，則采用快速排序為宜。當(dāng)待排序元素的個數(shù) n 大，內(nèi)存空間允許，且要求排序穩(wěn)定時， 則采用二路歸并排序為宜。當(dāng)待排序元素的個數(shù) n 大，排序碼分布可能會出現(xiàn)正序或逆序的 情形，且對穩(wěn)定性不做要求時，則采用堆排序或二路歸并排序為 宜。當(dāng)待排序元素的個數(shù) n 小，元素基本有序或分布較隨機，且要求 穩(wěn)定時，則采用直接插入排序為宜。當(dāng)待排序元素的個數(shù) n 小，對穩(wěn)定性不做要求時，則采用直接選 擇排序為宜，若排序碼不接近逆序，也可以采用直接插入排序。 冒泡排序一

53、般很少采用。第9章查找1、順序表的查找(順序查找)順序查找的缺點是平均查找長度較大， 特別是當(dāng)n很大時，查找效率 低。然而，它有很大的優(yōu)點是：算法簡單且適應(yīng)面廣。2、有序表的查找(折半查找)算法實現(xiàn)：假設(shè)表長為 n， low、high 和 mid 分別指向待查元素所在 區(qū)間的上界、下界和中點， k 為給定值，初始時，令 low=1， high=n， mid= （low+high）/2讓 k 與 mid 指向的記錄比較若 k=rmid.key ，查找成功若 k<rmid.key ，則 high=mid-1若 k>rmid.key ，則 low=mid+1重復(fù)上述操作，直至 low&g

54、t;high 時，查找失敗。例如：已知如下 11 個數(shù)據(jù)元素的有序表（ 05，13，19，21，37，56， 64，75，80，88，92），現(xiàn)要查找關(guān)鍵字為 21和 70 的數(shù)據(jù)元素。 折半查找的效率比順序查找高， 但折半查找只適用于有序表， 且限于 順序存儲結(jié)構(gòu)。3、查找方法的比較4、二叉排序樹的插入例 45，24， 53， 45，12，24，905、二叉排序樹的刪除5、含有 n 個結(jié)點的二叉排序樹的平均查找長度和樹的形態(tài)有關(guān)。第 7章 圖1、圖的定義和術(shù)語 若圖中的邊是頂點的有序?qū)Γ瑒t稱此圖為有向圖。 若圖中的邊是頂點的無序?qū)?，則稱此圖為無向圖。有向邊又稱為弧，通常用尖括號表示一條有向邊

55、，vv, w>表示從頂點v到w頂點的一條弧，v稱為邊的始點（或弧尾），w稱為邊的終點(或弧頭)。有向完全圖：具有n(n-1)條弧的有向圖稱為有向完全圖。無向完全圖：n個頂點的無向圖最大邊數(shù)是 n(n-1)/2,具有n(n-1)/2條邊的無向圖稱為無向完全圖。度的例題：子圖的例題：總的例題：若G中任意兩個頂點都是連通的，則稱 G為連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量在有向圖中，若對于每一對頂點vi和vj，都存在一條從vi到vj和 從vj到vi的路徑，則稱此圖是強連通圖。非強連通圖的極大強連通2、圖的存儲結(jié)構(gòu)無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的數(shù)組表示法(鄰接矩陣)網(wǎng)的鄰接矩陣可為：3、儲存表示1）有向圖的十字鏈表表示法 2）無向圖的鄰接多重表存儲表示4、圖的遍歷通常有兩條遍歷圖的路徑：深度優(yōu)