數(shù)據(jù)結(jié)構(gòu)與算法-課件

1、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)西安科技大學(xué) 張小艷知識(shí)結(jié)構(gòu)基本概念： 第1章 緒論線性結(jié)構(gòu)非線性結(jié)構(gòu) 應(yīng) 用第2章 線性表第3章 棧與隊(duì)列第4章 串第5章 數(shù)組與廣義表第6章 二叉樹與樹第7章 圖第8章查找第9章排序第一章24/07/20223概念術(shù)語邏輯結(jié)構(gòu)集合線形表樹圖順序存儲(chǔ)結(jié)構(gòu)（物理位置相鄰反應(yīng)邏輯關(guān)系）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（指針反應(yīng)邏輯關(guān)系）初始化、插入、刪除、排序、合并。問題求解步驟。五大特性、四大要求。時(shí)間復(fù)雜度空間復(fù)雜度算法分析操 作算 法物理結(jié)構(gòu)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)問題規(guī)模的函數(shù)1.數(shù)據(jù)：數(shù)據(jù)是用于描述客觀事物的數(shù)值、字符，以及一切可以輸入到計(jì)算機(jī)中的并由計(jì)算機(jī)程序加以處理

2、的符號(hào)的集合。2.數(shù)據(jù)元素：數(shù)據(jù)的基本單位是數(shù)據(jù)元素，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。3.數(shù)據(jù)項(xiàng)：是數(shù)據(jù)的不可分割的最小單位，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。4.數(shù)據(jù)對象：性質(zhì)相同的元素的集合叫做數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、對數(shù)據(jù)所施加的運(yùn)算（操作）。第一章24/07/20224概念術(shù)語邏輯結(jié)構(gòu)集合線形表樹圖順序存儲(chǔ)結(jié)構(gòu)（物理位置相鄰反應(yīng)邏輯關(guān)系）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（指針反應(yīng)邏輯關(guān)系）初始化、插入、刪除、排序、合并。問題求解步驟。五大特性、四大要求。時(shí)間復(fù)雜度空間復(fù)雜度算法分析操 作算 法物理結(jié)構(gòu)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)問題

3、規(guī)模的函數(shù)正確性（四個(gè)境界） 沒有語法錯(cuò)誤 對于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出 對于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果 對于任何測試數(shù)據(jù)都有滿足要求的輸出結(jié)果可讀性：便于閱讀、理解和交流健壯性：不合法數(shù)據(jù)也能合理處理高效率低存儲(chǔ)：時(shí)間效率高和存儲(chǔ)量低（1）有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。（3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。（4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。（5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。例題解析1

4、數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。線性結(jié)構(gòu)包括數(shù)組、鏈表、棧、隊(duì)列等；非線性結(jié)構(gòu)包括樹、圖等，這兩類結(jié)構(gòu)各自的特點(diǎn)是什么？【解答】 線性結(jié)構(gòu)的特點(diǎn)是：在結(jié)構(gòu)中所有數(shù)據(jù)成員都處于一個(gè)序列中，有且僅有一個(gè)開始成員和一個(gè)終端成員，并且所有數(shù)據(jù)成員都最多有一個(gè)直接前驅(qū)和一個(gè)直接后繼。例如，一維數(shù)組、線性表等就是典型的線性結(jié)構(gòu)。 非線性結(jié)構(gòu)的特點(diǎn)是：一個(gè)數(shù)據(jù)成員可能有零個(gè)、一個(gè)或多個(gè)直接前驅(qū)和直接后繼。例如，樹、圖或網(wǎng)絡(luò)等都是典型的非線性結(jié)構(gòu)。樹：一對多；圖：多對多 2. 即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生預(yù)料不到的運(yùn)行結(jié)果，這種算法好壞的評價(jià)因素稱為( ) A.正

5、確性 B.易讀性 C.健壯性 D.時(shí)空性 3.結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈”的數(shù)據(jù)結(jié)構(gòu)是( ) A.集合 B.線性結(jié)構(gòu) C.樹形結(jié)構(gòu) D.圖狀結(jié)構(gòu) 4.下面算法程序段的時(shí)間復(fù)雜度為( ) for ( int i=0; im; i+) for ( int j=0; jnext=NULL（帶頭結(jié)點(diǎn)）對于帶頭結(jié)點(diǎn)的單鏈表H若定義LinkList p;且 p=H-next 那么 p-data=a1 p-next-data=a2 其余依此類推。a1a2an H頭指針和頭結(jié)點(diǎn)的異同 頭 指 針頭 結(jié) 點(diǎn)指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針具有標(biāo)示作用，常用頭指針作為鏈表的名字

6、放在第一個(gè)元素之前，其數(shù)據(jù)域一般無意義(也可以放鏈表的長度)造成存儲(chǔ)空間浪費(fèi)a1a2an H 不帶頭結(jié)點(diǎn)的鏈表和帶頭結(jié)點(diǎn)的鏈表的區(qū)別 不帶頭結(jié)點(diǎn)帶 頭 結(jié) 點(diǎn)鏈表為空：L=NULL為真鏈表的第一個(gè)數(shù)據(jù)元素由L指向在第一個(gè)元素之前插入一個(gè)元素和刪除第一個(gè)元素要單獨(dú)處理，和在其他位置插入、刪除操作不同鏈表為空：L-next=NULL為真鏈表的第一個(gè)數(shù)據(jù)元素由 L-next指向插入、刪除操作統(tǒng)一a1a2an Ha1a2an H1 建立單鏈表 建立過程是一個(gè)動(dòng)態(tài)生成的過程，即從“空表”起，依次建立結(jié)點(diǎn)，并逐個(gè)插入鏈表頭插法尾插法逆序創(chuàng)建鏈表順序創(chuàng)建鏈表單鏈表上的基本運(yùn)算1） 用頭插法建立單鏈表的算法

7、算法思路：(1) 建立一個(gè)帶頭結(jié)點(diǎn)的空的單鏈表L(2) 按線性表中元素的逆序依次讀入數(shù)據(jù)元素，如果不是結(jié)束標(biāo)識(shí)時(shí)，申請結(jié)點(diǎn)s，將s結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后。 1 Linklist CreateFromHead( ) 2 LinkList L; 3 LNode *s; 4 char c; int flag=1; L=(Linklist)malloc(sizeof(LNode); 7 L-next=NULL; 8 while(flag)9 c=getchar( ); 10 if(c!=$) s=(Linklist)malloc(sizeof(LNode); s-data=c; s-next=L-nex

8、t; 14 L-next=s; 15 16 else 17 flag=0; /*讀入符號(hào)為“$”，修改結(jié)束標(biāo)識(shí)*/ 18 19 return L; 20 設(shè)置一個(gè)標(biāo)識(shí)變量flag，初值為1，當(dāng)輸入“$”時(shí)，將flag置為0，建表結(jié)束2） 尾插法建表算法思路：(1) 建立帶頭結(jié)點(diǎn)的空單鏈表L，設(shè)一指針r指向線性表表尾L.(2) 按線性表中元素的順序依次讀入數(shù)據(jù)元素，如果不是結(jié)束標(biāo)識(shí)時(shí)，申請結(jié)點(diǎn)s，將s結(jié)點(diǎn)插入到r所指結(jié)點(diǎn)的后面，然后r指向新的表尾結(jié)點(diǎn)s， 求鏈表長度的操作 求單鏈表的長度可以采用“數(shù)”結(jié)點(diǎn)的方法，從第一個(gè)元素開始“數(shù)”，一直“數(shù)”到最后一個(gè)結(jié)點(diǎn)(p-next=NULL)，就可求得

9、單鏈表的長度。算法思路：(1) 設(shè)一個(gè)臨時(shí)變量p指向頭結(jié)點(diǎn)，計(jì)數(shù)器j等于0。(2) 當(dāng)p-next!=NULL時(shí)，循環(huán)：指針p后移，指向它的直接后繼結(jié)點(diǎn)，計(jì)數(shù)器j加1。int ListLength(LinkList L) LinkList p; p=L; j=0; while(p-next!=NULL) p=p-next; j +; return j; p=p-next;j +;單鏈表插入操作 要在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入一個(gè)數(shù)據(jù)元素e1 int InsList(LinkList L, int i, char e)2 /*在帶頭結(jié)點(diǎn)的單鏈表L中第i個(gè)位置插入值為e的新結(jié)點(diǎn)*/3 Li

10、nkList pre, s; 4 int k; 5 pre=L; k=0; 6 while(pre!=NULL & knext; 8 k=k+1; 9 10 if(k!=i-1) /*插入位置不合理*/11 printf(插入位置不合理! ); 12 return ERROR;13 14 s=(LinkList)malloc(sizeof(LNode); 15 s-data=e; /*將待插入結(jié)點(diǎn)的值e賦給s的數(shù)據(jù)域*/16 s-next=pre-next; /*完成插入操作*/17 pre-next=s; 18 return OK;19 刪除 要在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)結(jié)點(diǎn)，首先需要

11、在單鏈表中找到第i-1個(gè)結(jié)點(diǎn)，并由指針pre指示，然后刪除第i個(gè)結(jié)點(diǎn)并釋放結(jié)點(diǎn)空間。1 int DelList(LinkList L, int i, char *e)2 /*在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個(gè)元素*/ 3 LinkList p, r;4 int k;5 pre=L; k=0;6 while(pre-next!=NULL & knext;8 k=k+1; 9 10 if(k!=i-1) /* while循環(huán)是因?yàn)閜-next=NULL或inext; 15 pre-next=pre-next-next; /*刪除結(jié)點(diǎn)r */16 *e=r-data;17 free(r); /*釋放被

12、刪除的結(jié)點(diǎn)所占的內(nèi)存空間*/ 18 return OK;19 總結(jié)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)在于：2 單鏈表不具有按序號(hào)隨機(jī)訪問的特點(diǎn)，順序存取元素。1 動(dòng)態(tài)分配存儲(chǔ)空間，不需要事先估計(jì)表的長度。3 插入、刪除操作不需要移動(dòng)數(shù)據(jù)元素，只需修改指針域。必須知道其前驅(qū)結(jié)點(diǎn)。從上述操作可以看到：鏈表中結(jié)點(diǎn)所占的空間，是動(dòng)態(tài)分配通過上面的基本操作我們得知： 在單鏈表上插入、刪除一個(gè)結(jié)點(diǎn)，必須知道其前驅(qū)結(jié)點(diǎn)。 單鏈表不具有按序號(hào)隨機(jī)訪問的特點(diǎn)，插入位置的查找只能從頭指針開始一個(gè)一個(gè)順序進(jìn)行。2. 循環(huán)單鏈表 將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域由NULL改為指向頭結(jié)點(diǎn)或線性表中的第一個(gè)結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表

13、，并稱為循環(huán)鏈表。 為了使某些操作實(shí)現(xiàn)起來方便，在循環(huán)單鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。 這樣，空循環(huán)鏈表僅由一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。 LLa1a2aian假設(shè) P指向鏈表最后一個(gè)結(jié)點(diǎn)時(shí)： 單鏈表： p-next= =NULL為真。 循環(huán)單鏈表： p-next=L為真。判斷鏈表不為空的條件： 單鏈表： L-next != NULL為真。 循環(huán)單鏈表： L-next!=L為真。 對于單鏈表只能從頭結(jié)點(diǎn)開始遍歷整個(gè)鏈表，而對于循環(huán)單鏈表則可以從表中任意結(jié)點(diǎn)開始遍歷整個(gè)鏈表。 對鏈表常做的操作是在表尾、表頭進(jìn)行時(shí)，用一個(gè)指向尾結(jié)點(diǎn)的指針R來標(biāo)識(shí)，可以提高操作效率。 例：有兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA、L

14、B，編寫一個(gè)算法，將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為LA。3 修改第二個(gè)表的尾Q，使它的鏈域指向第一個(gè)表的頭結(jié)點(diǎn)。 算法步驟：p=LA; q=LB; while (p-next! =LA) p=p-next; while (q-next! =LB) q=q-next;1 找到兩個(gè)鏈表的尾，并分別由指針p、q指向它們2 將第一個(gè)鏈表的尾與第二個(gè)表的第一個(gè)結(jié)點(diǎn)鏈接起來q-next=LA; p-next=LB-next; free(LB);LinkList merge-1(LinkList LA, LinkList LB) LNode *p, *q; p=LA; q=LB; while

15、 (p-next! =LA) p=p-next; while (q-next! =LB) q=q-next; q-next=LA; p-next=LB-next; free(LB); return(LA); 算法實(shí)現(xiàn)如下：執(zhí)行時(shí)間是兩個(gè)表的長度之和O(m+n)。 兩個(gè)用尾指針標(biāo)識(shí)的循環(huán)單鏈表的連接 1 LinkList merge2(LinkList R1, LinkList R2)2 3 Node *p; 4 p=R1-next; 5 R1-next=R2-next-next; 6 free(R2-next); 7 R2-next=p; 8 return R1; 9 若在尾指針表示的單循環(huán)鏈

16、表上實(shí)現(xiàn)，則只需要修改指針，無需遍歷，其執(zhí)行時(shí)間是 O(1)。 在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其前驅(qū)的指針域prior。 這樣形成的鏈表中就有兩條方向不同的鏈，我們可稱之為雙(向)鏈表(Double Linked List)。typedef struct DLnode datatype data; struct DLnode *prior, *next; DLNode, *DLinkList; 3 雙向鏈表雙鏈表的結(jié)構(gòu)定義如下: proirdatanext前驅(qū)指針域后繼指針域數(shù)據(jù)域由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)變得非常方便。p-prior-

17、next = p = p-next-prior 設(shè)指針p指向雙鏈表中某一結(jié)點(diǎn)，則有下式成立：ai-1aiai+1P雙向鏈表的插入操作 aiai+1PeSs-next=p-next; p-next-prior=s; p-next=s; s-prior=p; 雙向鏈表的刪除操作算法描述： ai-1aiai+1Pr *e=p-data; p-next=r-next; r-next-prior=p;free(r); 1. 線性表采用鏈表存儲(chǔ)，其地址( )。 A 必須是連續(xù)的 B 部分地址必須是連續(xù)的 C 一定是不連續(xù)的 D 連續(xù)不連續(xù)都可以2. 設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為head，則判斷該鏈表是

18、否為空的條件是( ) A. head-next=head B. head-next=NULL C. head!=NULL D. head=NULL3. 在單鏈表中，存儲(chǔ)每個(gè)結(jié)點(diǎn)有兩個(gè)域，即數(shù)據(jù)域和指針域，后者指向該結(jié)點(diǎn)的（ ）。 A 開始結(jié)點(diǎn) B . 結(jié)束結(jié)點(diǎn) C 直接前驅(qū) D 直接后繼4. 從一維數(shù)組an中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為 。例 題5. 所有存儲(chǔ)結(jié)點(diǎn)存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里，利用結(jié)點(diǎn)在存儲(chǔ)器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。這種存儲(chǔ)方式是_。 6. 單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)（存在且不釋放存儲(chǔ)空間），則需要修改指針的操作為 p-next=_。

19、7. 若線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，則采用_存儲(chǔ)方式節(jié)省時(shí)間。8. 在順序表（即順序存儲(chǔ)結(jié)構(gòu)的線性表）中插入一個(gè)元素，需要平均移動(dòng)_個(gè)元素。9. 試比較順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。10. 簡述在線性表中設(shè)置頭結(jié)點(diǎn)的作用。11在單鏈表、雙向鏈表和單循環(huán)鏈表中，若僅知道指針p指向某結(jié)點(diǎn)，不知道頭指針，能否將結(jié)點(diǎn)*p從相應(yīng)的鏈表中刪去？若可以，其時(shí)間復(fù)雜度各為多少? 單鏈表：若要?jiǎng)h除單鏈表中的結(jié)點(diǎn)p，必須獲得p的前驅(qū)。但是如果在單鏈表中僅知道p指向某結(jié)點(diǎn)，則只能根據(jù)該指針找到其直接后繼，由于不知道其頭指針，所以無法訪問到p指針指向的結(jié)點(diǎn)的直接前驅(qū)。因此無法刪去該結(jié)點(diǎn)，如圖

20、2所示。雙向鏈表：由于這樣的鏈表提供雙向指針，根據(jù)*p結(jié)點(diǎn)的前驅(qū)指針和后繼指針可以查找到其直接前驅(qū)和直接后繼，從而可以刪除該結(jié)點(diǎn)。其時(shí)間復(fù)雜度為O(1)。如圖p指向雙向鏈表中的某結(jié)點(diǎn)，刪除*p，操作如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 單循環(huán)鏈表：根據(jù)已知結(jié)點(diǎn)位置，可以直接得到其后相鄰的結(jié)點(diǎn)位置（直接后繼），又因?yàn)槭茄h(huán)鏈表，所以我們可以從p開始找后繼，直到找到后繼結(jié)點(diǎn)是p時(shí)停止，即可得到p結(jié)點(diǎn)的直接前驅(qū)，如圖2.5所示。因此可以刪去p所指結(jié)點(diǎn)。其時(shí)間復(fù)雜度應(yīng)為O(n)。算法設(shè)計(jì)題 1、設(shè)順序表va中的數(shù)據(jù)元素遞增有序。

21、試設(shè)計(jì)一個(gè)算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。 在順序表va中從表尾元素開始向前依次與x進(jìn)行比較，如果當(dāng)前位置元素比x大，則當(dāng)前元素后移一個(gè)位置，直到找到插入位置，即當(dāng)前元素小于等于x，或者比較到第一個(gè)元素。24/07/202247算法如下： define MAXSIZE=線性表可能達(dá)到的最大長度 typedef struct DataType dataMAXSIZE； int last； SeqList； int Insert_SeqList(SeqList *va, int x) int i; if (va-last+1MAXSIZE) return 0; /*表已滿

22、*/ va-last+; for (i=va-last-1; va-dataix &i=0; i-) /*查找插入位置 */ va-datai+1=va-datai; va-datai+1=x; return 1; 2假設(shè)某個(gè)單向循環(huán)鏈表的長度大于1，且表中既無頭結(jié)點(diǎn)也無頭指針。已知S為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法在鏈表中刪除指針s所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。算法如下：Status ListDelete_CL(LinkList &S)LinkList p,q;if(S=S-next)return ERROR;q=S;p=S-next;while(p-next!=S) q=p; p=p-next

23、; q-next=p-next;free(p);return OK;3試寫一個(gè)將線性表就地逆置的算法，即在原表的存儲(chǔ)空間內(nèi)將線性表（a1，a2， ，an）逆置為（an，a2，a1）解： 第一步：構(gòu)建只有包含原表中第一個(gè)元素結(jié)點(diǎn)的表（帶頭結(jié)點(diǎn)鏈表），且設(shè)一指針指向第二個(gè)元素結(jié)點(diǎn)（一個(gè)無頭結(jié)點(diǎn)的包含該鏈表剩余結(jié)點(diǎn)的鏈表）。 第二步：將無頭結(jié)點(diǎn)鏈表中的所有結(jié)點(diǎn)順著鏈表指針，由前往后將每個(gè)結(jié)點(diǎn)依次從無頭結(jié)點(diǎn)鏈表中摘下，用頭插法插入到帶頭結(jié)點(diǎn)鏈表中。這樣就可以得到逆置的鏈表?！窘獯稹?設(shè)鏈表帶頭結(jié)點(diǎn)Typedef struct lnode elemtype data； struct node *next

24、； lnode，*linklist；void example(linklist *la) linklist p, q; p=(*la)-next; (*la)-next=null; while (p) q=p-next; p-next=(*la)-next; (*la)-next=p; 4已知單鏈表L是一個(gè)遞增有序表，試寫一高效算法，刪除表中值大于min 且小于max的結(jié)點(diǎn)（若表中有這樣的結(jié)點(diǎn))，同時(shí)釋放被刪結(jié)點(diǎn)的空間，這里min 和 max是兩個(gè)給定的參數(shù)。請分析你的算法的時(shí)間復(fù)雜度。 【解答】 解這樣的問題，首先想到的是將鏈表中的元素一個(gè)一個(gè)地與max和min比較，然后刪除這個(gè)結(jié)點(diǎn)。由于已

25、知鏈表是有序的，則介于min 和max之間的結(jié)點(diǎn)必為連續(xù)的一段元素序列，所以只要先找到所有大于min的結(jié)點(diǎn)中的最小結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)*p，依次刪除小于max的結(jié)點(diǎn)，直到第一個(gè)大于等于max的結(jié)點(diǎn)*q位置，再將*p結(jié)點(diǎn)的直接后繼指針指向*q結(jié)點(diǎn)。算法如下：void DeleteList(LinkList L, DataType min, DataType max)ListNode *p, *q, *s;p=L;while(p-next& p-next-datanext;q=p-next; /*p指向第一個(gè)不大于min結(jié)點(diǎn)的直接前驅(qū)， q指向第一個(gè)大于min的結(jié)點(diǎn)*/while(q&q-datan

26、ext;free(s); /*刪除結(jié)點(diǎn)，釋放空間*/p-next=q; /*將*p結(jié)點(diǎn)的直接后繼指針指向*q結(jié)點(diǎn)*/5寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果表中各結(jié)點(diǎn)值均不相同?！窘獯稹?先取開始結(jié)點(diǎn)中的值，將它與其后的所有結(jié)點(diǎn)值一一比較，發(fā)現(xiàn)相同的就刪除掉，然后再取第二結(jié)點(diǎn)的值，重復(fù)上述過程直到最后一個(gè)結(jié)點(diǎn)。void DeleteList ( LinkList L )ListNode *p , *q , *s; p=L-next; while( p-next&p-next-next) q=p;/由于要做刪除操作，所以q指針指向要?jiǎng)h除元素的直接前趨 while (q-next) if

27、 (p-data=q-next-data) /刪除與*p的值相同的結(jié)點(diǎn) s=q-next; q-next=s-next; free(s); else q=q-next; p=p-next; 第三章 棧與隊(duì)列24/07/202258 棧的基本概念：LIFO 棧的存儲(chǔ)棧的應(yīng)用（了解）順序棧（熟練掌握）鏈棧（熟練掌握）初始化取棧頂入棧出棧判斷?？?棧初始化取棧頂入棧出棧判斷棧空24/07/202259 基本概念：FIFO 存儲(chǔ)基本操作順序隊(duì)列循環(huán)隊(duì)列（隊(duì)空、隊(duì)滿）鏈隊(duì)列初始化取隊(duì)頭入隊(duì) 出隊(duì)隊(duì)列 a1a2an 出隊(duì) 入隊(duì) 隊(duì)頭 隊(duì)尾 rear front J3 J4 J2 J3J1 J4 J5fro

28、ntrearfronta1a2aianrear解決假溢出的方法之一：將隊(duì)列的數(shù)據(jù)區(qū)看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關(guān)系不變，將其稱為“循環(huán)隊(duì)列” 入隊(duì)操作為：sq-rear=(sq-rear+1)%MAXSIZE出隊(duì)操作為:sq-front=(sq-front+1)% MAXSIZErear01234567EFGHIJfrontrearrearfrontfrontfrontfrontfrontrearrearLK“隊(duì)滿”和“隊(duì)空”的條件相同。這顯然是必須要解決的一個(gè)問題。frontfrontfront 方法一： 附設(shè)一個(gè)存儲(chǔ)隊(duì)中元素個(gè)數(shù)的變量 num，當(dāng)num=0時(shí)隊(duì)空， 當(dāng) num=MAX

29、SIZE 時(shí)為隊(duì)滿。方法二：少用一個(gè)元素空間，把圖(d)所示的情況就視為隊(duì)滿，此時(shí) 隊(duì)滿的條件是：(rear+1)% MAXSIZE=front。typedef struct datatype dataMAXSIZE; int front, rear; int num; c_SeQueue; 下面的循環(huán)隊(duì)列及操作按第一種方法實(shí)現(xiàn)循環(huán)隊(duì)列的類型定義及基本運(yùn)算如下：1. 有六個(gè)元素6，5，4，3，2，1的順序進(jìn)棧，下列（ ）不是合法的出棧序列 A 5 4 3 6 1 2 B 4 5 3 2 1 6 C 3 4 6 5 2 1 D 2 3 4 1 5 6 2. 在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為_

30、。3. 一個(gè)棧的輸入序列是1，2，3，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素為_。4解決計(jì)算機(jī)與打印機(jī)之間速度不匹配問題,需要設(shè)置一個(gè)緩沖區(qū),應(yīng)是一個(gè) 數(shù)據(jù)結(jié)構(gòu) 5. 簡述順序棧的結(jié)構(gòu)特點(diǎn)，棧滿與棧空的判斷條件。6. 順序隊(duì)列的“假溢出”是怎樣產(chǎn)生的？如何知道循環(huán)隊(duì)列是空還是滿？7. 遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間，對嗎？為什么？ 8試各舉一個(gè)實(shí)例，簡要闡述棧和隊(duì)列在程序設(shè)計(jì)中所起的作用。 【解答】 棧的特點(diǎn)是先進(jìn)后出，所以在解決實(shí)際問題涉及到后進(jìn)先出的情況時(shí)，可以考慮使用棧。例如表達(dá)式的括號(hào)匹配問題。利用“期待的緊迫程度”這個(gè)概念來描述，在具體實(shí)現(xiàn)中，設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，

31、若是右括號(hào)，則或者是置于棧頂?shù)淖罴逼鹊钠诖靡韵?，或者是不合法的情況，若是左括號(hào)，則作為一個(gè)新的更急迫的期待壓入棧中，使原有的在棧中的所有未消解的期待的急迫程度都降了一級。 隊(duì)列的特點(diǎn)是先進(jìn)先出。例如：操作系統(tǒng)中的作業(yè)排隊(duì)。在允許多道程序運(yùn)行的計(jì)算機(jī)系統(tǒng)中，同時(shí)有幾個(gè)作業(yè)運(yùn)行，如果運(yùn)行的結(jié)果都需要通過通道輸出，那就要按請求輸出的先后次序排隊(duì)。每當(dāng)通道傳輸完畢并可以接受新的輸出任務(wù)時(shí)，隊(duì)頭的作業(yè)先從隊(duì)列中退出作輸出操作。凡是申請輸出的作業(yè)都從隊(duì)尾進(jìn)入隊(duì)列。9. 鏈棧中為何不設(shè)置頭結(jié)點(diǎn)?【解答】 鏈棧不需要在頭部附加頭結(jié)點(diǎn)，因?yàn)闂６际窃陬^部進(jìn)行操作的，如果加了頭結(jié)點(diǎn)，等于要對頭結(jié)點(diǎn)之后的結(jié)點(diǎn)進(jìn)行

32、操作，反而使算法更復(fù)雜，所以只要有鏈表的頭指針就可以了。10. 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么? 如何判別它的空和滿?【解答】 循環(huán)隊(duì)列的優(yōu)點(diǎn)是：它可以克服順序隊(duì)列的“假溢出”現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。判別循環(huán)隊(duì)列的“空”或“滿”不能以頭尾指針是否相等來確定，一般是通過以下幾種方法：一是少用一個(gè)元素的空間,每次入隊(duì)前測試入隊(duì)后頭尾指針是否會(huì)重合，如果會(huì)重合就認(rèn)為隊(duì)列已滿。二是設(shè)置一計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)，不僅可判別空或滿，還可以得到隊(duì)列中元素的個(gè)數(shù)。第四章 串 s是串的名字; n是串中字符的個(gè)數(shù), 稱為串的長度字符在串中的序號(hào)稱為該字符在串中的位置串是一種特殊的線性表。數(shù)據(jù)元素僅

33、由一個(gè)字符組成。 保持線性表的特點(diǎn)； 但操作有所不同：對串整體進(jìn)行操作。串的基本概念 是零個(gè)或多個(gè)字符組成的有限序列。一般記為：s= a1a2.an (n0)其中: 串的順序存儲(chǔ)及模式匹配 typedef struct char chMAXLEN; int last; SeqString;定義一個(gè)串變量： SeqString S;1串是一種特殊的線性表，其特殊性表現(xiàn)在哪里？ 【解答】其特殊性表現(xiàn)在： 組成串的數(shù)據(jù)元素只能是字符；操作對象為數(shù)據(jù)元素序列 2. 串常用的存儲(chǔ)結(jié)構(gòu)有哪些？【解答】 串常用的存儲(chǔ)結(jié)構(gòu)主要有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。 串的順序存儲(chǔ)是用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值中

34、的字符序列。C語言規(guī)定，在串的末尾用0來表示串的結(jié)束。用這一特殊符號(hào)來判定串是否結(jié)束，從而求得串的長度。在順序存儲(chǔ)結(jié)構(gòu)中，可以在計(jì)算機(jī)中開辟一個(gè)存儲(chǔ)串的自由存儲(chǔ)區(qū)，即串的堆存儲(chǔ)結(jié)構(gòu)。 串的鏈?zhǔn)酱鎯?chǔ)是用不帶頭結(jié)點(diǎn)的單鏈表來存儲(chǔ)串結(jié)點(diǎn)。具體實(shí)現(xiàn)時(shí)，每個(gè)結(jié)點(diǎn)既可以存放一個(gè)字符，也可以存放多個(gè)字符。每個(gè)結(jié)點(diǎn)稱為塊，整個(gè)鏈表稱為塊鏈結(jié)構(gòu)。第五章 數(shù)組與廣義表 數(shù)組、廣義表是線性表的推廣。數(shù)組 邏輯結(jié)構(gòu) ：每個(gè)數(shù)據(jù)元素受多個(gè)線性關(guān)系的約束 存儲(chǔ)結(jié)構(gòu) ：以行為主序的順序存儲(chǔ)結(jié)構(gòu)。 隨機(jī)存取公式 矩陣的壓縮存儲(chǔ)特殊矩陣對稱矩陣三角矩陣帶狀矩陣稀疏矩陣三元組表十字鏈表（了解）隨機(jī)存取公式數(shù)組的順序存儲(chǔ)結(jié)構(gòu)有兩種

35、：1. 按行序存儲(chǔ)。如：BASIC、 COBOL和PASCAL語言。 2. 按列序存儲(chǔ)。如：FORTRAN語言。a23a22a21a13a12a11a23a22a21a13a12a11a23a13a22a12a21a11(a) 23數(shù)組的邏輯狀態(tài)(b) 以行為主序(c) 以列為主序23數(shù)組的物理狀態(tài)設(shè)數(shù)組的基址為LOC(a11)，每個(gè)數(shù)組元素占據(jù)k個(gè)地址單元，那么aij的物理地址計(jì)算：設(shè)有二維數(shù)組Amn，按元素的下標(biāo)求其地址的計(jì)算：2 以“以列為主序”的分配比例： LOC(aij)=LOC(a11)+(j-1)*m+(i-1)*k 1 以“以行為主序”的分配為例： LOC(aij)=LOC(a

36、11)+(i-1)*n+j-1)*k3 在C語言中，數(shù)組中每一維的下界定義為0，則： LOC(aij)=LOC(a00)+(i*n+j)*k對于三維數(shù)組Amnp，即mnp數(shù)組，對于數(shù)組元素aijk，其物理地址為： Loc(aijk)=Loc(a111)+(i-1)np+(j-1)p+k-1)L推廣到一般的三維數(shù)組：Ac1.d1c2.d2c3.d3，則aijk的物理地址為Loc(aijk)=Loc(a c1 c2 c3)+(i-c1)(d2-c2+1)(d3-c3+1) +(j-c2)(d3-c3+1)+(k-c3)L對于n維數(shù)組A(c1.d1, c2.d2, , cn.dn)，我們只要把上式推

37、廣，就可以容易地得到維數(shù)組中任意元素aj1j2jn的存儲(chǔ)地址的計(jì)算公式： 容易看出，數(shù)組元素的存儲(chǔ)位置是其下標(biāo)的線性函數(shù)，一旦數(shù)組下標(biāo)確定之后，數(shù)組中的元素可隨機(jī)存取。我們稱具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。例：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是 多少個(gè)字節(jié)。答： Volume=m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288例： 設(shè)數(shù)組a60, 70的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a32,58的存儲(chǔ)地址？答：根據(jù)行優(yōu)先公式 LO

38、C(aij)=LOC(a00)+(i*n+j)*k (0im，0jn)得：LOC(a32,58)=2048+(32*70+58)*26644特殊矩陣的壓縮存儲(chǔ)為了節(jié)省存儲(chǔ)空間，特別是在高階矩陣的情況下，可以利用特殊矩陣的分布規(guī)律對他們進(jìn)行壓縮存儲(chǔ)。壓縮存儲(chǔ)：為多個(gè)值相同的元素只分配一個(gè)存儲(chǔ)空間，值為零的元素不分配空間。壓縮存儲(chǔ)時(shí)，節(jié)約了存儲(chǔ)單元，但在壓縮后還需解決如何找到某元素的方法，因此，還必須給出壓縮前下標(biāo)和壓縮后下標(biāo)之間的變換公式，使壓縮存儲(chǔ)變得有意義。注意：特點(diǎn)：在一個(gè)n階方陣中，有aij=aji ，其中1i、jn。如圖所示是一個(gè)5階對稱矩陣 對稱矩陣對于對稱矩陣，因其元素滿足aij=

39、aji，只需存儲(chǔ)其下三角（或上三角）,即可實(shí)現(xiàn)壓縮存儲(chǔ)。對于n階對稱方陣，將nn個(gè)元素壓縮到 n(n+1)/2 個(gè)空間中。 對下三角部分以行為主序順序存儲(chǔ)到一個(gè)向量中去，在下三角中共有n(n+1)/2個(gè)元素，因此，不失一般性，設(shè)存儲(chǔ)到向量SAn(n+1)/2中。設(shè)矩陣元素aij存儲(chǔ)在A數(shù)組的Ak中，則關(guān)鍵問題是要找i、j與k的關(guān)系。K=I*(I+1)/2+J (其中I=max(i,j),J=min(i,j); ) 對于下三角元素aij，前面共有i行,這i行共有 (i+1)*i/2 個(gè)元素,當(dāng)前行中aij前亦有 j個(gè)元素。所以aij前共有 (i+1)*i/2+j 個(gè)元素，對于上三角元素aij，由

40、于aij=aji,則訪問和它對應(yīng)的下三角中的aji即可。如圖為一個(gè)三角矩陣，其中c為某個(gè)常數(shù)。其中：(a)為下三角矩陣：主對角線以上均為同一個(gè)常數(shù)；(b)為上三角矩陣，主對角線以下均為同一個(gè)常數(shù)；三角矩陣下面討論它們的壓縮存儲(chǔ)方法，可以借用對稱矩陣的壓縮存儲(chǔ)方法 3 c c c c6 2 c c c4 8 1 c c 7 4 6 0 c8 2 9 5 73 4 8 1 0c 2 9 4 6c c 1 5 7 c c c 0 8c c c c 7(a) 下三角矩陣(b) 上三角矩陣主對角線上下方各有b條次對角線。b為矩陣的半帶寬，2b+1為矩陣的帶寬，常見的有三對角、五對角、七對角矩陣。帶狀矩陣

41、 若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱此矩陣為對角矩陣。對角矩陣具有如下特點(diǎn)：Amn=a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 a45 1.確定存儲(chǔ)該矩陣所需的一維向量空間的大小 假設(shè)每個(gè)非零元素所占空間的大小為1個(gè)單元。 所需一維向量空間的大小為2+2+3(n-2)=3n-2以三對角矩陣為例討論對角矩陣的壓縮存儲(chǔ)Loci,j = Loc0,0+前i行非零元個(gè)數(shù)+第i行中aij前非零元個(gè)數(shù);前i行元素個(gè)數(shù)為：3(i-1)+2 (因?yàn)榈?行只有2個(gè)非零元素);第i行中aij前非零元素個(gè)數(shù)=j-i+1，其中 2.確定

42、非零元素在一維數(shù)組空間中的位置-1 (ji) j-i =由此得到:Loci, j=Loc0, 0+3(i-1)+2+j-i+1 =Loc0,0+2i+j稀疏矩陣的壓縮存儲(chǔ) 稀疏矩陣：設(shè)mn矩陣中有t個(gè)非零元素，且tn，則無左孩子； 3)i的右孩子是2i + 1，如果2i + 1n則無右孩子。二叉樹的存儲(chǔ)24/07/202292二叉樹存儲(chǔ)方法有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)二叉樹順序存儲(chǔ)結(jié)構(gòu)完全二叉樹：用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)結(jié)點(diǎn)元素，即將編號(hào)為 i 的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為 i 的分量中（不用下標(biāo)為0存儲(chǔ)單元）。此順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹 不是完全二叉樹怎么辦？一律

43、轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。缺點(diǎn)：浪費(fèi)空間；插入、刪除不便FEDCBA1514131211109876543210T16若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。 A B c F E D 1 2 4 8 91011 5 6 3 712131415(1) 順序存儲(chǔ)結(jié)構(gòu)2h-1=24-1 = 15二叉樹的存儲(chǔ)24/07/202294（2）二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 存儲(chǔ)方式 一般從根結(jié)點(diǎn)開始存儲(chǔ)，用二叉鏈表來表示。（相應(yīng)地，訪問樹中結(jié)點(diǎn)時(shí)也只能從根開始） 二叉樹結(jié)點(diǎn)的特點(diǎn)二叉樹是非線性結(jié)構(gòu)，適合用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) data parentlc

44、hildrchild二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義：typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)rchildDatalchildADBCEFN個(gè)結(jié)點(diǎn)的二叉鏈表有幾個(gè)空鏈域有n1個(gè)空的鏈域。24/07/202296若規(guī)定先左后右，則只有前三種情況： DLR 前（根）序遍歷， LDR 中（根）序遍歷， LRD 后（根）序遍歷-+*/ecdba表達(dá)式的前綴、中綴、后綴形式： 前綴： -+a*bc/de 中綴： a+b*c-d/e 后綴： abc*+de/- 二叉樹的層

45、次遍歷算法按層次遍歷所得到的結(jié)果序列為：ABCDEFG。 在進(jìn)行層次遍歷時(shí)，可設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)指針入隊(duì)列，依次執(zhí)行下面操作： (1) 隊(duì)列不空，出隊(duì)列，取隊(duì)頭元素。 (2) 訪問該元素所指結(jié)點(diǎn)。 (3) 若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，則將該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。 此過程不斷進(jìn)行，當(dāng)隊(duì)列為空時(shí)，二叉樹的層次遍歷結(jié)束。在下面的層次遍歷算法中，二叉樹以二叉鏈表存放，一維數(shù)組QueueMAXNODE用以實(shí)現(xiàn)隊(duì)列，變量front和rear分別表示當(dāng)前隊(duì)首元素和隊(duì)尾元素在數(shù)組中的位置。1 void LevelOrder(BiTree

46、bt) /*層次遍歷二叉樹bt*/2 3 BiTree QueueMAXNODE; 4 int front, rear;5 if(bt=NULL) return;6 front=-1;7 rear=0;8 queuerear=bt; /*根入隊(duì)列*/9 while(front!=rear) /*隊(duì)列不空*/10 front+;11 visite(queuefront-data); /*訪問隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)域*/12 if(queuefront-lchild!=NULL) /*將隊(duì)首結(jié)點(diǎn)的左孩子結(jié)點(diǎn)入隊(duì)列*/13 rear+;14 queuerear=queuefront-lchild;15 16

47、 if(queuefront-rchild!=NULL) /*將隊(duì)首結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì)列*/17 rear+;18 queuerear=queuefront-rchild;19 20 21 已知一棵二叉樹的先序序列與中序序列分別為：先序：A B C D E F G H I 中序： B C A E D G H F I 試恢復(fù)該二叉樹。ABCDEFGHIBCDEFGHIFGIH根據(jù)遍歷順序確定一棵二叉樹已知二叉樹的前序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的后序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的前序序列和后序序列，不能唯一確定一棵二叉樹。設(shè)二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下：

48、（1）根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫出該二叉樹。（2）寫出按前序、中序、后序遍歷該二叉樹所得的結(jié)點(diǎn)序列。1234567891011121314151617181920EAFDHCGIB前序序列為 E A D C B F H G I中序序列為 A B C D E F G H I后序序列為 B C D A G I H F E樹的存儲(chǔ)結(jié)構(gòu)雙親表示法孩子表示法帶雙親的孩子鏈表孩子兄弟表示法（二叉樹表示法）多重鏈表表示法樹與森林樹的遍歷先序遍歷后序遍歷森林的遍歷先序遍歷中序后序遍歷問題1：樹的先序、中序、后序遍歷分別與其相應(yīng)的二叉樹哪種遍歷方式對應(yīng)。樹的先根遍歷序列為 1, 2, 3, 4, 5, 6, 8, 7；

49、 后根遍歷序列為 3, 4, 8, 6, 7, 5, 2, 1。 二叉樹的前序序列 二叉樹的中序序列 問題2：森林的先序、中序、后序遍歷分別與其相應(yīng)的二叉樹哪種遍歷方式對應(yīng)。前序遍歷：A B D G H J K E C F I M中序遍歷：G D J H K B E A C F I M后序遍歷：G J K H D E B M I F C A習(xí)題：分別畫出具有3個(gè)結(jié)點(diǎn)的樹和3個(gè)結(jié)點(diǎn)的二叉樹的所有 不同形態(tài)。 具有3個(gè)結(jié)點(diǎn)的樹有兩種不同形態(tài)， 具有3個(gè)結(jié)點(diǎn)的二叉樹有5種不同形態(tài)試找出分別滿足下面條件的所有二叉樹：（1）前序序列和中序序列相同； （2）中序序列和后序序列相同；（3）前序序列和后序序列

50、相同； （4）前序、中序、后序序列均相同。復(fù)習(xí)： 二叉樹的五種基本形態(tài)【解答】 （1）前序序列和中序序列相同的二叉樹是： 空二叉樹或每個(gè)結(jié)點(diǎn)沒有左子樹的二叉樹（右單支樹）。 （2）中序序列和后序序列相同的二叉樹是： 空二叉樹或每個(gè)結(jié)點(diǎn)沒有右子樹的二叉樹（左單支樹）。 （3）前序序列和后序序列相同的二叉樹是： 空二叉樹或只有根結(jié)點(diǎn)的二叉樹。 （4）前序、中序、后序序列均相同的二叉樹： 空樹或只有根結(jié)點(diǎn)的二叉樹。二叉樹的應(yīng)用：哈夫曼樹24/07/2022108哈夫曼樹的應(yīng)用帶權(quán)路徑計(jì)算WPL帶權(quán)路徑長度WPL最小的二叉樹稱作哈夫曼樹具有相同帶權(quán)結(jié)點(diǎn)的哈夫曼樹不惟一滿二叉樹不一定是哈夫曼樹哈夫曼樹的

51、結(jié)點(diǎn)的度數(shù)為 0 或 2， 沒有度為 1 的結(jié)點(diǎn)。包含 n 個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中共有2n1 個(gè)結(jié)點(diǎn)。哈夫曼樹的構(gòu)造過程給定權(quán)值集w=2,3,4,7,8,9,試構(gòu)造關(guān)于w的的一顆哈夫曼樹，并求其帶權(quán)路徑長度WPL。24/07/20221092347894789235789235499235497815哈夫曼樹的構(gòu)造過程24/07/2022110給定權(quán)值集w=2,3,4,7,8,9,試構(gòu)造關(guān)于w的的一顆哈夫曼樹，并求其帶權(quán)路徑長度WPL。78159235491878159235491833WPL=(2+3)4+43+92+(7+8)2=80【例題】T=(a,2),(b,3),(c,4),(d,7

52、),(e,9)為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長度。23479哈夫曼編碼過程23479235234792352347923523549234792352354923479235235497916234792352354979162347923523549791623549791625234792352354979162354979162523549791625abcdeWPL=5500001111a:010b:011c:00d:10e:11哈夫曼編碼的平均長度=32+33+24+27+29=55第七章 圖圖邏輯結(jié)

53、構(gòu)（多對多）存儲(chǔ)結(jié)構(gòu)圖的遍歷典型應(yīng)用鄰接矩陣鄰接表深度優(yōu)先廣度優(yōu)先圖的連通性最小生成樹（普利姆、克魯斯卡爾算法）最短路徑（迪杰斯特拉、弗羅伊德算法）拓?fù)渑判颉㈥P(guān)鍵路徑（了解） 用一維數(shù)組來存儲(chǔ)頂點(diǎn)信息用二維數(shù)組來存儲(chǔ)邊或者弧的信息。 二維數(shù)組被稱為鄰接矩陣。 頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ) 每個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)用單鏈表存儲(chǔ)。圖存儲(chǔ)結(jié)構(gòu)鄰接矩陣、鄰接表1 鄰接矩陣表示法 圖的信息包括兩部分： 頂點(diǎn)的信息 頂點(diǎn)之間的關(guān)系(邊或者弧的信息) 分兩部分來存儲(chǔ)： 用一維數(shù)組來存儲(chǔ)頂點(diǎn)信息 用二維數(shù)組來存儲(chǔ)邊或者弧的信息。 二維數(shù)組被稱為鄰接矩陣。 鄰接矩陣圖或網(wǎng)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)的C語言描述形式如下： #d

54、efine INFINITY #define MAXNODE typedef char VertexType; /*假設(shè)頂點(diǎn)數(shù)據(jù)為字符型*/ typedef struct int adj; ArcType; typedef struct VertexType vertexsMAXNODE; ArcType arcsMAXNODEMAXNODE; int vexnum, arcnum; /*圖的頂點(diǎn)數(shù)和弧數(shù)*/ GraphType;與頂點(diǎn)有關(guān)的信息圖：若兩頂點(diǎn)相鄰則adj=1， 否則 adj=0；網(wǎng)：若兩頂點(diǎn)相鄰則adj=wij， 若i=j則adj=0；否則adj= 表示圖中頂點(diǎn)之間的關(guān)系鄰接表

55、 鄰接表表示法是一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)相結(jié)合的存儲(chǔ)方法，順序存儲(chǔ)部分用來保存圖中頂點(diǎn)的信息，鏈?zhǔn)酱鎯?chǔ)部分用來保存圖中邊(或弧)的信息。 該方法與樹的孩子鏈表表示法類似。 圖中的頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)，每個(gè)數(shù)組元素包含兩部分，一部分用于存儲(chǔ)頂點(diǎn)信息，一部分用于存放與該頂點(diǎn)相鄰接的所有頂點(diǎn)組成的單鏈表的頭指針(即與頂點(diǎn)vi鄰接的第一個(gè)鄰接點(diǎn))。 圖中的每個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表，由于鄰接點(diǎn)的個(gè)數(shù)不定，所以用單鏈表存儲(chǔ)。若是無向圖，該鏈表稱為頂點(diǎn)vi的邊表；若是有向圖，該鏈表稱為頂點(diǎn)vi作為弧尾的出邊表。 (1)表頭結(jié)點(diǎn)結(jié)構(gòu)為:data firstarcadjverdataweight

56、nextarc(2) 邊結(jié)點(diǎn)的結(jié)構(gòu)為：操作的實(shí)現(xiàn)：結(jié)點(diǎn)的度、鄰接點(diǎn)等圖的鄰接表存儲(chǔ)結(jié)構(gòu)的C語言描述形式： #define MAXNODE 圖中頂點(diǎn)的最大個(gè)數(shù) typedef struct arc int adjvex; /*鄰接點(diǎn)域，存儲(chǔ)鄰接點(diǎn)在表頭結(jié)點(diǎn)表中的位置*/ int weight; /*權(quán)值域*/ struct arc *next; /*鏈域，指向下一鄰接點(diǎn)*/ ArcType; /*邊表結(jié)點(diǎn)*/ typedef struct ElemType data; /*頂點(diǎn)信息*/ ArcType *firstarc; /*指向第一條依附該頂點(diǎn)的邊或弧的指針*/ VertexType; /*

57、頂點(diǎn)表結(jié)點(diǎn)*/ typedef struct VertexType vertexsMAXNODE; int vexnum, arcnum; /*圖中頂點(diǎn)數(shù)和弧數(shù)*/ AdjList;在邊稀疏的情況下，比鄰接矩陣節(jié)省存儲(chǔ)空間求某結(jié)點(diǎn)的度 無向圖中：頂點(diǎn)vi的度是第i個(gè)鏈表上結(jié)點(diǎn)的個(gè)數(shù)。 有向圖中：vi的出度是第i個(gè)鏈表上結(jié)點(diǎn)的個(gè)數(shù)； 入度需要遍歷整個(gè)鏈表（建立逆鄰接表）圖的鄰接表存儲(chǔ)特點(diǎn)： 采用鄰接表表示圖，如要判斷任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連，則需要遍歷所有的鄰接單鏈表，這樣比較麻煩。 圖的遍歷 圖的遍歷是指從圖中的任一頂點(diǎn)出發(fā)，對圖中的所有頂點(diǎn)訪問一次且只訪問一次。圖的許多其他操作都是建

58、立在遍歷操作的基礎(chǔ)之上。由于圖結(jié)構(gòu)本身的復(fù)雜性，所以圖的遍歷操作也較復(fù)雜，主要表現(xiàn)在以下四個(gè)方面： 圖中任意一個(gè)頂點(diǎn)都可作為第一個(gè)被訪問的結(jié)點(diǎn)。 在非連通圖中，從一個(gè)頂點(diǎn)出發(fā)，只能夠訪問它所在的連通分量上的所有頂點(diǎn)。 如果有回路存在，有可能沿回路又回到該頂點(diǎn)。 一個(gè)頂點(diǎn)和其它多個(gè)頂點(diǎn)相連，存在如何選取下一個(gè)要訪問的頂點(diǎn)的問題。 為了保證圖中的各頂點(diǎn)在遍歷過程中訪問且僅訪問一次，需要為每個(gè)頂點(diǎn)設(shè)一個(gè)訪問標(biāo)識(shí)，因此我們?yōu)閳D設(shè)置一個(gè)訪問標(biāo)識(shí)數(shù)組visitedn，用于表示圖中每個(gè)頂點(diǎn)是否被訪問過，它的初始值為0(“假”)，表示頂點(diǎn)均未被訪問；一旦訪問過頂點(diǎn)vi，則置訪問標(biāo)識(shí)數(shù)組中的visitedi為1

59、(“真”)，以表示該頂點(diǎn)已被訪問。 圖的遍歷通常有兩種方法，即深度優(yōu)先遍歷和廣度優(yōu)先遍歷。這兩種遍歷方法對于無向圖和有向圖均適用 ABDCEGHFABDCEGHFABDCEGHF深度優(yōu)先生成樹：深度優(yōu)先搜索得到的序列：BFDGACEH從某個(gè)結(jié)點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷圖的算法采用遞歸的形式說明如下：(1) 訪問結(jié)點(diǎn)v。(2) 找到v的第一個(gè)鄰接點(diǎn)w。(3) 如果鄰接點(diǎn)w存在且未被訪問，則從w出發(fā)深度優(yōu)先遍歷圖；否則，結(jié)束。(4) 找頂點(diǎn)v關(guān)于w的下一個(gè)鄰接點(diǎn)，轉(zhuǎn)(3)。深度優(yōu)先遍歷深度優(yōu)先搜索算法 int visitedMAXNUM; /*訪問標(biāo)識(shí)數(shù)組*/1 void TraveGraph(Cr

60、aph G)3 int v;4 for(v=0; vG.vexnum; v+) /*初始化訪問標(biāo)識(shí)數(shù)組*/5 visitedv=0; 6 for(v=0; vG.vexnum; v+) 7 if(!visitedv) DepthFirstSearch(G, v); /*調(diào)用深度遍歷算法*/8 void DepthFirstSearch(Graph G, int v) /*深度遍歷v所在的連通子圖*/10 int w;11 visit(v); /*訪問頂點(diǎn)v*/12 visitedv=1; /*置訪問標(biāo)識(shí)數(shù)組相應(yīng)分量值*/13 w=FirstAdjVertex(G, v); /*找第一個(gè)鄰接點(diǎn)*