數(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)可以帶來(lái) 最優(yōu)效率 的算法。2、程序設(shè)計(jì) = 算法 +數(shù)據(jù)結(jié)構(gòu)3、解決問(wèn)題方法的效率：跟數(shù)據(jù)的組織方式有關(guān)跟空間的利用效率有關(guān)跟算法的巧妙程度有關(guān)4、數(shù)據(jù) ：所有能輸入到計(jì)算機(jī)中 ,且被計(jì)算機(jī)處理的符號(hào)的集合， 是計(jì)算機(jī)操作對(duì)象的總稱(chēng)；是計(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)系 ：<ai,ai+1>|i=1,2,3,4,5,612、對(duì)每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問(wèn)題：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)：

3、 基本操作在計(jì)算機(jī)上的實(shí)現(xiàn)（方法 ）。15、數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念16、數(shù)據(jù)元素的 4 類(lèi)的基本結(jié)構(gòu) ： 集合； 線(xiàn)性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系； 樹(shù)形結(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ǔ)言的優(yōu)點(diǎn)：C語(yǔ)言可以直接操作內(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)都由數(shù)據(jù)域和指針域組成 )。 邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。插入、刪除靈活 (不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針 )。20、數(shù)據(jù)類(lèi)型 是一個(gè)值的集合和定義在此集合上的一組操作的

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

5、。26、抽象數(shù)據(jù)類(lèi)型具有 數(shù)據(jù)抽象、數(shù)據(jù)封裝 的特點(diǎn)。27、數(shù)據(jù)的儲(chǔ)存結(jié)構(gòu)分為： 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 。 第二章 線(xiàn)性表1、線(xiàn)性結(jié)構(gòu)的特點(diǎn)：在數(shù)據(jù)元素中的非空有限集中。(1) 存在唯一的一個(gè)被稱(chēng)作“第一”的數(shù)據(jù)元素；(2) 存在唯一的一個(gè)被稱(chēng)作“最后一個(gè)”的數(shù)據(jù)元素；(3) 除第一個(gè)外，集合中的每一個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)；(4) 除最后一個(gè)外，集合中的每一個(gè)數(shù)據(jù)元素均只有一個(gè)后繼。2、線(xiàn)性表 (Linear List) ：一個(gè)線(xiàn)性表是 n 個(gè)數(shù)據(jù)元素的有限序列3、線(xiàn)性表的順序存儲(chǔ)實(shí)現(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; /* 如果沒(méi)找到，返回 -1

7、*/else return i; /* 找到后返回的是存儲(chǔ)位置 */6、插入算法void Insert( ElementType X, int i, List *PtrL ) int j;if ( PtrL->Last = MAXSIZE-1 )/* 表空間已滿(mǎn)， 不能插入 */ printf( 表滿(mǎn) );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 倒序向后移動(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 (不存在第d個(gè)元素” ,i ); return ;for ( j = i; j <= PtrL->Last; j+ )PtrL->D

9、ataj-1 = PtrL->Dataj; /* 將 ai+1 an順序向 前移動(dòng)*/PtrL->Last-; /*Last 仍指向最后元素 */ return;8、求表長(zhǎng)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)按序號(hào)查找 : 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 個(gè)，返回指針 */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)個(gè)結(jié)點(diǎn)后插入一個(gè)

11、值為 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-1 個(gè)結(jié)點(diǎn) */if ( p = NULL ) /* 第 i-1 個(gè)不存在，不能插入 */printf(H 參數(shù) i 錯(cuò)"

12、)；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;/* 若要?jiǎng)h除的是表的/*s 指向第 1 個(gè)結(jié)點(diǎn)/* 從鏈表中刪除 */* 釋放被刪除結(jié)點(diǎn)if ( i = 1 ) 第一個(gè)結(jié)點(diǎn) */s =

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

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

15、除均在表的同一端進(jìn)行。插入和刪除發(fā)生的一端稱(chēng)為棧頂(the top of thestack)。4、第一個(gè)進(jìn)棧的元素在棧底，5、最后一個(gè)進(jìn)棧的元素在棧頂， 第一個(gè)出棧的元素為棧頂元素， 最后一個(gè)出棧的元素為棧底元素。6、連續(xù)棧(Contiguous Stack的類(lèi)型定義#define MaxStack 50Typedef structdatatype stackMaxStack;int top;Seqstack;Seqstack *s;7、判斷棧是否已滿(mǎn)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的類(lèi)型定義棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱(chēng)為鏈棧， 它是運(yùn)算受限的單鏈表， 插入和刪除操作僅限制在表頭位置上進(jìn)行。 由于只能在鏈表頭部進(jìn)行操作， 故鏈表沒(méi)有必要像單鏈表那樣附加頭結(jié)點(diǎn)。棧頂指針就是鏈表的頭指針鏈棧的類(lèi)型說(shuō)明如下：typedef struct stacknode datatype datastruct stacknode *nextstacknode11、鏈?zhǔn)綏５奶攸c(diǎn)： 鏈?zhǔn)綏o(wú)棧滿(mǎn)問(wèn)題；空間可擴(kuò)充；插入與刪除僅在棧頂處執(zhí)行； 鏈?zhǔn)綏５臈ｍ斣阪滎^；適合于多棧操作。11、棧是限定僅能在表的一端進(jìn)行插入、刪除操作的線(xiàn)性表 。12、棧

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

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

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

21、 125、若用一個(gè)大小為6的一維數(shù)組來(lái)實(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最先出棧（即C第一個(gè)且D第二個(gè)出棧）的次 序有哪幾個(gè)C、D、B、A、EC、D、E、B、AC、D、B、E、A第六章樹(shù)和二叉樹(shù)1、樹(shù)型結(jié)構(gòu)是一類(lèi)重要的非線(xiàn)性結(jié)構(gòu)。2、樹(shù)的定義：樹(shù)是n（n>=0）個(gè)結(jié)點(diǎn)的有限集T, T為空時(shí)稱(chēng)為空樹(shù)， 否則它滿(mǎn)足如下兩個(gè)條件：（

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

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

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

25、EE-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、遍歷二叉樹(shù) 二叉樹(shù)是由三個(gè)基本單元組成：根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。 若限定先左后右，則只有前三種情況，分別稱(chēng)之為 先(根)序遍歷， 中(根)序遍歷和后(根)序遍

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

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

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

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

30、b*c-d-e/f 按后序遍歷，其后序序列為： abcd-*+ef/ -8、( 1 )查詢(xún)二叉樹(shù)中某個(gè)結(jié)點(diǎn)Status Preorder (BiTree T, ElemType x, BiTree &p) / 若二叉樹(shù)中存在和 x 相同的元素，則 p 指向該結(jié)點(diǎn)并/ 返回 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)計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)int CountLeaf (BiTree T)/ 返回指針 T 所指二叉樹(shù)中所有葉子結(jié)點(diǎn)個(gè)數(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) 求二叉樹(shù)的深度 (后序遍歷 )int Depth (BiTree T ) / 返回二叉樹(shù)的深度if (

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

33、= ) T=NULL; else if(!T=(BiTNode *)malloc(sizeof(BiTNode) exit (OVERFLOW); T->data=ch; /生成根結(jié)點(diǎn)CreateBiTree(T->lchild);/構(gòu)造左子樹(shù)CreateBiTree(T->rchild);/構(gòu)造右子樹(shù)Return OK; /CreateBiTree9、遍歷二叉樹(shù)的非遞歸算法1) 先序遍歷二叉樹(shù)的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹(shù)非遞歸算法 / 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) 中序遍歷二叉樹(shù)的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹(shù)非遞歸算法 / 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)后序遍歷二叉樹(shù)的非遞歸算法void inorder(JD *r)/ 先序遍歷二叉樹(shù)非遞歸算法 / 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、線(xiàn)索二叉樹(shù)：以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左右孩子的信息，而不能在結(jié)點(diǎn)的任一序列的前驅(qū)與后繼信息，這種信息只有在遍歷的動(dòng)態(tài)過(guò)程中才能得到，為了能保存所需的信息，可增加標(biāo)志域lchildLtagdataRtagrchildLtag=O , Ichild域指示結(jié)點(diǎn)的左孩子；Ltag=1, Ichild域指示結(jié) 點(diǎn)的前驅(qū)。Rtag=O, rchild域指示結(jié)點(diǎn)的右孩子；Rtag=1, rchild域指示結(jié)點(diǎn) 的后驅(qū)。以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，

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

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

39、(3) 以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針 旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)15、二叉樹(shù)轉(zhuǎn)換成森林抹線(xiàn)：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線(xiàn)， 及沿右分支搜索到的所有 右孩子間連線(xiàn)全部抹掉，使之變成孤立的二叉樹(shù).還原：將孤立的二叉樹(shù)還原成16、樹(shù)和森林的遍歷樹(shù)的遍歷 兩種次序遍歷樹(shù)的方法：一種是先根(次序)遍歷樹(shù)，即先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù)；結(jié)點(diǎn)森林的遍歷一種是后根(次序)遍歷，即先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根先根序列：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、、赫夫曼樹(shù)及其應(yīng)用例題： w=5, 29, 7, 8, 14, 23, 3, 11習(xí)題:1、 由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹(shù)是一種特殊的 樹(shù)，這種說(shuō)法旦。（A）正確（B）錯(cuò)誤2、某二叉樹(shù)的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹(shù)一定是D_。（A）空或只有一個(gè)結(jié)點(diǎn)（B）完全二叉樹(shù)（C）二叉排序樹(shù)（D）高度等于其節(jié)點(diǎn)數(shù)3、深度為5的二叉樹(shù)至多有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，010，011，1（C）100，11，10，1，0（D）001，00

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

42、畫(huà)出該二叉樹(shù)。先序序列是：*BC*FG中序序列是：CB*EAG*后序序列是：*EDB*FA9、將右圖所示的樹(shù)轉(zhuǎn)化為二叉樹(shù)，并寫(xiě)出先序遍歷，中序遍歷和后 序遍歷的結(jié)果。解：先序：ABEFGCDHI中序：EFGBCHIDA后序：GFEIHDCBA10、設(shè)給定權(quán)集w=2, 3，4，7，8，9，試構(gòu)造關(guān)于w的一棵赫夫 曼樹(shù)，并求其加權(quán)路徑長(zhǎng)度WPL。WPL=(9+7+8)*2+4*3+(2+3)*4=80第十章內(nèi)部排序1、內(nèi)排序大致可分為五類(lèi)：插入排序、交換排序、選擇排序、歸并 排序和分配排序。2、直接插入排序直接插入的算法實(shí)現(xiàn)void sort(NODE array,i nt n)/待排序元素用一個(gè)

43、數(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=arrayj; j-; / 順序比較和移動(dòng) arrayj+1=x; 例如，n=6,數(shù)組R的六個(gè)排序碼分別為：17，3, 25,14, 20，9。它的直接插入排序的執(zhí)行過(guò)程如圖7-1所示。012345初始直接插入排序的時(shí)間復(fù)雜度為14 O( n2»)o9第

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

46、：17, 3, 25,14, 20, 9。下面用圖 10-3 給出冒泡排序算法的執(zhí)行過(guò)程。冒泡排序算法的時(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 (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 所示?？焖倥判蛩加玫妮o助空間為棧的深度， 故最好的空間復(fù)雜度為O(log2n),最壞的空間復(fù)雜度為 0(n)。快速排序是一種不穩(wěn)定的排序方法。5、選擇排序1) 直接選擇排序例如，給定n=8,數(shù)組R中的8個(gè)元素的排序碼為：(8, 3, 2, 1,乙 4， 6， 5)，則直接選擇排序過(guò)程如圖 7-5 所示。直接選擇排序的時(shí)間復(fù)雜度為 0( n2)數(shù)量級(jí)2) 樹(shù)形選擇排序例如,給定排序碼頭 50, 37, 66, 98, 75, 12, 26, 49,樹(shù)形選擇 排序過(guò)程見(jiàn)圖 7-7。3) 堆排序例如,給定排序碼 49, 38, 65

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

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

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

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

53、般很少采用。第9章查找1、順序表的查找(順序查找)順序查找的缺點(diǎn)是平均查找長(zhǎng)度較大， 特別是當(dāng)n很大時(shí)，查找效率 低。然而，它有很大的優(yōu)點(diǎn)是：算法簡(jiǎn)單且適應(yīng)面廣。2、有序表的查找(折半查找)算法實(shí)現(xiàn)：假設(shè)表長(zhǎng)為 n， low、high 和 mid 分別指向待查元素所在 區(qū)間的上界、下界和中點(diǎn)， k 為給定值，初始時(shí)，令 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 時(shí)，查找失敗。例如：已知如下 11 個(gè)數(shù)據(jù)元素的有序表（ 05，13，19，21，37，56， 64，75，80，88，92），現(xiàn)要查找關(guān)鍵字為 21和 70 的數(shù)據(jù)元素。 折半查找的效率比順序查找高， 但折半查找只適用于有序表， 且限于 順序存儲(chǔ)結(jié)構(gòu)。3、查找方法的比較4、二叉排序樹(shù)的插入例 45，24， 53， 45，12，24，905、二叉排序樹(shù)的刪除5、含有 n 個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形態(tài)有關(guān)。第 7章 圖1、圖的定義和術(shù)語(yǔ) 若圖中的邊是頂點(diǎn)的有序?qū)?，則稱(chēng)此圖為有向圖。 若圖中的邊是頂點(diǎn)的無(wú)序?qū)?，則稱(chēng)此圖為無(wú)向圖。有向邊又稱(chēng)為弧，通常用尖括號(hào)表示一條有向邊

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