數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書-2014

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書計(jì)算機(jī)專業(yè)實(shí)驗(yàn)中心2014年9月目 錄實(shí)驗(yàn)一、線性表的實(shí)現(xiàn)及操作（一）5實(shí)驗(yàn)二、線性表的實(shí)現(xiàn)及操作（二）8實(shí)驗(yàn)三、線性表的應(yīng)用13實(shí)驗(yàn)四、二叉樹(shù)的實(shí)現(xiàn)及操作14實(shí)驗(yàn)五、二叉樹(shù)的應(yīng)用19實(shí)驗(yàn)六、圖的遍歷操作20實(shí)驗(yàn)七、圖的應(yīng)用27數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)的內(nèi)容和要求通過(guò)上機(jī)實(shí)驗(yàn)加深對(duì)課程內(nèi)容的理解，增加感性認(rèn)識(shí)，提高程序設(shè)計(jì)、開(kāi)發(fā)及調(diào)試能力。序號(hào)實(shí) 驗(yàn)名 稱內(nèi) 容提 要每組人數(shù)實(shí)驗(yàn)時(shí)數(shù)實(shí)驗(yàn)要求實(shí)驗(yàn)類別分值（總100分）1線性表的實(shí)現(xiàn)及操作（一）順序表建立、插入、刪除等基本操作12必做設(shè)計(jì)15分2線性表的實(shí)現(xiàn)及操作（二）單鏈表的建立、插入、刪除等基本操作12必做設(shè)計(jì)15分3線性表的應(yīng)用約

2、瑟夫環(huán)問(wèn)題或者長(zhǎng)整數(shù)相加的設(shè)計(jì)與實(shí)現(xiàn)12選作綜合10分4二叉樹(shù)的實(shí)現(xiàn)及操作二叉樹(shù)的基本操作：樹(shù)的建立、前序、中序、后序遍歷12必做設(shè)計(jì)20分5二叉樹(shù)的應(yīng)用赫夫曼樹(shù)12選作綜合10分6圖的遍歷圖的遍歷：深度優(yōu)先和廣度優(yōu)先12必做設(shè)計(jì)20分7圖的應(yīng)用最短路徑算法：Dijkstra算法和Floyd算法12選作綜合10分8算法性能測(cè)試、總結(jié)和答疑對(duì)實(shí)驗(yàn)課涉及到的算法進(jìn)行性能測(cè)試、對(duì)實(shí)驗(yàn)所遇到的問(wèn)題進(jìn)行總結(jié)和答疑12本實(shí)驗(yàn)指導(dǎo)書適用于16學(xué)時(shí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課，實(shí)驗(yàn)項(xiàng)目具體內(nèi)容如下：其中，第1、2、4、6實(shí)驗(yàn)項(xiàng)目為設(shè)計(jì)性實(shí)驗(yàn)，的其內(nèi)容為程序代碼分析與調(diào)試，要求每位同學(xué)在每次實(shí)驗(yàn)課結(jié)束前通過(guò)檢查。這部分實(shí)驗(yàn)應(yīng)

3、撰寫1份實(shí)驗(yàn)報(bào)告，總分70分。第3、5、7實(shí)驗(yàn)項(xiàng)目為綜合應(yīng)用性實(shí)驗(yàn)，學(xué)生根據(jù)自己的興趣和基礎(chǔ)選作。這三個(gè)實(shí)驗(yàn)要求學(xué)生利用所學(xué)的理論知識(shí)解決實(shí)際問(wèn)題，每一個(gè)實(shí)驗(yàn)應(yīng)撰寫一份實(shí)驗(yàn)報(bào)告，每個(gè)實(shí)驗(yàn)10分。此實(shí)驗(yàn)指導(dǎo)書也適用于8學(xué)時(shí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課，要求完成第1、2、4、6實(shí)驗(yàn)項(xiàng)目。實(shí)驗(yàn)報(bào)告要求請(qǐng)按照實(shí)驗(yàn)教師要求，按時(shí)提交實(shí)驗(yàn)報(bào)告電子版文件。實(shí)驗(yàn)報(bào)告格式可個(gè)性化定義，內(nèi)容包括但不限于以下內(nèi)容：1、 題目、姓名、學(xué)號(hào)、班級(jí)（首頁(yè)）2、 需求分析：陳述程序設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)程序要做什么，明確規(guī)定：（1） 輸入的形式和輸出值的范圍；（2） 輸出的形式；（3） 程序所能達(dá)到的功能；（4） 測(cè)試數(shù)據(jù)：包括正確的輸入輸出

4、結(jié)果和錯(cuò)誤的輸入及輸出結(jié)果。3、 概要設(shè)計(jì)：說(shuō)明用到的數(shù)據(jù)結(jié)構(gòu)定義、主程序的流程及各程序模塊之間的調(diào)用關(guān)系。4、 詳細(xì)設(shè)計(jì)：提交帶注釋的源程序或者用偽代碼寫出每個(gè)操作所涉及的算法。5、 調(diào)試分析：（1） 調(diào)試過(guò)程中所遇到的問(wèn)題及解決方法；（2） 算法的時(shí)空分析；（3） 經(jīng)驗(yàn)與體會(huì)。6、 用戶使用說(shuō)明：說(shuō)明如何使用你設(shè)計(jì)的程序，詳細(xì)列出每一步操作步驟。（如果程序操作簡(jiǎn)單，可略去）7、 測(cè)試結(jié)果：列出對(duì)于給定的輸入所產(chǎn)生的輸出結(jié)果。（若有可能，測(cè)試隨輸入規(guī)模的增長(zhǎng)所用算法的實(shí)際運(yùn)行時(shí)間的變化）8、總結(jié)實(shí)驗(yàn)一、線性表的實(shí)現(xiàn)及操作（一）一、實(shí)驗(yàn)?zāi)康牧私夂驼莆站€性表的順序存儲(chǔ)結(jié)構(gòu)；掌握用C語(yǔ)言上機(jī)調(diào)試線

5、性表的基本方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算，以及對(duì)相應(yīng)算法的性能分析。二、實(shí)驗(yàn)要求給定一段程序代碼，程序代碼所完成的功能為：（1）建立一個(gè)線性表；（2）依次輸入數(shù)據(jù)元素1,2,3,4,5,6,7,8,9,10；（3）刪除數(shù)據(jù)元素5；（4）依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性表的數(shù)據(jù)元素個(gè)數(shù)在最壞情況下不會(huì)超過(guò)100個(gè)，要求使用順序表。程序中有3處錯(cuò)誤的地方，有標(biāo)識(shí)，屬于邏輯錯(cuò)誤，對(duì)照書中的代碼仔細(xì)分析后，要求同學(xué)們修改錯(cuò)誤的代碼，修改后上機(jī)調(diào)試得到正確的運(yùn)行結(jié)果。三、程序代碼#include <stdio.h>

6、;#define MaxSize 100typedef int DataType;typedef structDataType listMaxSize;int size; SeqList;void ListInitiate(SeqList *L)/*初始化順序表L*/L->size = 0;/*定義初始數(shù)據(jù)元素個(gè)數(shù)*/ int ListLength(SeqList L)/*返回順序表L的當(dāng)前數(shù)據(jù)元素個(gè)數(shù)*/return L.size;int ListInsert(SeqList *L, int i, DataType x) /*在順序表L的位置i（0 i size）前插入數(shù)據(jù)元素值x*/

7、 /*插入成功返回1，插入失敗返回0*/int j;if(L->size >= MaxSize)printf("順序表已滿無(wú)法插入! n");return 0;else if(i < 0 | i > L->size )printf("參數(shù)i不合法! n");return 0;else /此段程序有一處錯(cuò)誤for(j = L->size; j > i; j-) L->listj = L->listj;/*為插入做準(zhǔn)備*/L->listi = x;/*插入*/L->size +;/*元素個(gè)數(shù)加

8、1*/return 1;int ListDelete(SeqList *L, int i, DataType *x)/*刪除順序表L中位置i（0 i size - 1）的數(shù)據(jù)元素值并存放到參數(shù)x中*/*刪除成功返回1，刪除失敗返回0*/int j;if(L->size <= 0)printf("順序表已空無(wú)數(shù)據(jù)元素可刪! n");return 0;else if(i < 0 | i > L->size-1)printf("參數(shù)i不合法");return 0;else/此段程序有一處錯(cuò)誤*x = L->listi;/*保

9、存刪除的元素到參數(shù)x中*/for(j = i +1; j <= L->size-1; j+) L->listj = L->listj-1;/*依次前移*/L->size-;/*數(shù)據(jù)元素個(gè)數(shù)減1*/return 1;int ListGet(SeqList L, int i, DataType *x)/*取順序表L中第i個(gè)數(shù)據(jù)元素的值存于x中，成功則返回1，失敗返回0*/if(i < 0 | i > L.size-1)printf("參數(shù)i不合法! n");return 0;else*x = L.listi;return 1;void

10、main(void) SeqList myList; int i , x; ListInitiate(&myList); for(i = 0; i < 10; i+) ListInsert(&myList, i, i+1); ListDelete(&myList, 4, &x); for(i = 0; i < ListLength(myList); i+) ListGet( , i, &x); /此段程序有一處錯(cuò)誤printf("%d ", x); 實(shí)驗(yàn)二、線性表的實(shí)現(xiàn)及操作（二）一、實(shí)驗(yàn)?zāi)康牧私夂驼莆站€性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

11、；掌握用C語(yǔ)言上機(jī)調(diào)試線性表的基本方法；掌握線性表的基本操作：插入、刪除、查找以及線性表合并等運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)上的運(yùn)算，以及對(duì)相應(yīng)算法的性能分析。二、實(shí)驗(yàn)要求給定一段程序代碼，程序代碼所完成的功能為：（1）建立一個(gè)線性表；（2）依次輸入數(shù)據(jù)元素1,2,3,4,5,6,7,8,9,10；（3）刪除數(shù)據(jù)元素5；（4）依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性表的數(shù)據(jù)元素個(gè)數(shù)在最壞情況下不會(huì)超過(guò)100個(gè)，要求使用單鏈表。程序中有3處錯(cuò)誤的地方，有標(biāo)識(shí)，屬于邏輯錯(cuò)誤，對(duì)照書中的代碼仔細(xì)分析后，要求同學(xué)們修改錯(cuò)誤的代碼，上機(jī)調(diào)試并得到正確的運(yùn)行結(jié)果。三、程序代碼：#include <

12、;stdio.h>/*該文件包含pringtf()等函數(shù)*/#include <stdlib.h>/*該文件包含exit()等函數(shù)*/#include <malloc.h>/*該文件包含malloc()等函數(shù)*/typedef int DataType;/*定義DataType為int*/typedef struct NodeDataType data;struct Node *next; SLNode;void ListInitiate(SLNode *head)/*初始化*/*如果有內(nèi)存空間，申請(qǐng)頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/if(*head =

13、(SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);(*head)->next = NULL;/*置鏈尾標(biāo)記NULL */int ListLength(SLNode *head)SLNode *p = head;/*p指向首元結(jié)點(diǎn)*/int size = 0;/*size初始為0*/while(p->next != NULL)/*循環(huán)計(jì)數(shù)*/p = p->next;size +;return size;int ListInsert(SLNode *head, int i, DataType x)/*在帶頭結(jié)點(diǎn)的單鏈表head的數(shù)據(jù)元

14、素ai（0 i size）結(jié)點(diǎn)前*/*插入一個(gè)存放數(shù)據(jù)元素x的結(jié)點(diǎn)*/SLNode *p, *q;int j;p = head; /*p指向首元結(jié)點(diǎn)*/j = -1;/*j初始為-1*/while(p->next != NULL && j < i - 1) /*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點(diǎn)*/p = p->next;j+;if(j != i - 1)printf("插入位置參數(shù)錯(cuò)！");return 0;/*生成新結(jié)點(diǎn)由指針q指示*/if(q = (SLNode *)malloc(sizeof(SLNode) = NULL) exi

15、t(1);q->data = x;/此段程序有一處錯(cuò)誤p->next = q->next;/*給指針q->next賦值*/p->next = q;/*給指針p->next重新賦值*/return 1;int ListDelete(SLNode *head, int i, DataType *x)/*刪除帶頭結(jié)點(diǎn)的單鏈表head的數(shù)據(jù)元素ai（0 i size - 1）結(jié)點(diǎn)*/*刪除結(jié)點(diǎn)的數(shù)據(jù)元素域值由x帶回。刪除成功時(shí)返回1；失敗返回0*/SLNode *p, *s;int j;p = head; /*p指向首元結(jié)點(diǎn)*/j = -1;/*j初始為-1*/wh

16、ile(p->next != NULL && p->next->next!= NULL && j < i - 1) /*最終讓指針p指向數(shù)據(jù)元素ai-1結(jié)點(diǎn)*/p = p->next;j+;if(j != i - 1)printf("插入位置參數(shù)錯(cuò)！");return 0;/此段程序有一處錯(cuò)誤s = p->next; /*指針s指向數(shù)據(jù)元素ai結(jié)點(diǎn)*/*x = s->data;/*把指針s所指結(jié)點(diǎn)的數(shù)據(jù)元素域值賦予x*/p->next = s->next;/*把數(shù)據(jù)元素ai結(jié)點(diǎn)從單鏈表中刪

17、除指*/free(s);/*釋放指針s所指結(jié)點(diǎn)的內(nèi)存空間*/return 1;int ListGet(SLNode *head, int i, DataType *x)/*取數(shù)據(jù)元素ai和刪除函數(shù)類同，只是不刪除數(shù)據(jù)元素ai結(jié)點(diǎn)*/SLNode *p;int j;p = head;j = -1;while(p->next != NULL && j < i)p = p->next;j+;if(j != i)printf("取元素位置參數(shù)錯(cuò)！");return 0;/此段程序有一處錯(cuò)誤*x = p->next;return 1;void

18、Destroy(SLNode *head)SLNode *p, *p1;p = *head;while(p != NULL)p1 = p;p = p->next;free(p1);*head = NULL;void main(void)SLNode *head;int i , x;ListInitiate(&head);/*初始化*/for(i = 0; i < 10; i+)if(ListInsert(head, i, i+1) = 0) /*插入10個(gè)數(shù)據(jù)元素*/printf("錯(cuò)誤! n");return;if(ListDelete(head, 4

19、, &x) = 0) /*刪除數(shù)據(jù)元素5*/printf("錯(cuò)誤! n");return;for(i = 0; i < ListLength(head); i+)if(ListGet(head, i, &x) = 0) /*取元素*/printf("錯(cuò)誤! n");return;else printf("%d ", x);/*顯示數(shù)據(jù)元素*/Destroy(&head);實(shí)驗(yàn)三、線性表的應(yīng)用一、實(shí)驗(yàn)?zāi)康募由顚?duì)線性表各項(xiàng)操作實(shí)現(xiàn)的理解，增強(qiáng)學(xué)生問(wèn)題模擬、數(shù)據(jù)抽象的能力。二、實(shí)驗(yàn)要求本實(shí)驗(yàn)共有兩個(gè)題目，作為實(shí)

20、驗(yàn)一和實(shí)驗(yàn)二的拓展題目，可選作其中一個(gè)或者兩個(gè)都做。選取根據(jù)題目要求進(jìn)行設(shè)計(jì)，并編程實(shí)現(xiàn)，在實(shí)驗(yàn)報(bào)告中給出測(cè)試數(shù)據(jù)。三、實(shí)驗(yàn)內(nèi)容1、 約瑟夫環(huán)問(wèn)題的設(shè)計(jì)與實(shí)現(xiàn)據(jù)說(shuō)著名猶太歷史學(xué)家 Josephus有過(guò)以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開(kāi)始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個(gè)人開(kāi)始，越過(guò)k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過(guò)），并殺掉第k個(gè)人。接

21、著，再越過(guò)k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過(guò)程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問(wèn)題是，給定了和，一開(kāi)始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過(guò)了這場(chǎng)死亡游戲。問(wèn)題：假設(shè)41個(gè)人圍成一圈，其中有m個(gè)你的朋友不想死掉，從第一個(gè)開(kāi)始報(bào)數(shù)，第3個(gè)將被殺掉。為了保護(hù)自己和m個(gè)朋友，現(xiàn)在編寫程序，求出如何安排自己和m個(gè)朋友的初始位置。2、 長(zhǎng)整數(shù)表示與相加很長(zhǎng)整數(shù)是指無(wú)法用long型數(shù)存儲(chǔ)的數(shù)，因此需要用字符串?dāng)?shù)組來(lái)存儲(chǔ)兩個(gè)被加數(shù)，相加的結(jié)果也保存于字符數(shù)組中，假如被加數(shù)長(zhǎng)度不超過(guò)十進(jìn)制40位

22、，請(qǐng)編程實(shí)現(xiàn)該加法程序并將相加結(jié)果輸出。四、 實(shí)驗(yàn)報(bào)告要求1、 基本要求見(jiàn)第3頁(yè)。2、 給出實(shí)驗(yàn)結(jié)果。3、 對(duì)算法的性能進(jìn)行測(cè)試。要求分析算法的復(fù)雜度，測(cè)試程序?qū)τ诓煌笮≥斎氲倪\(yùn)行情況（例如約瑟夫環(huán)，改變?nèi)藬?shù)個(gè)數(shù)為50,100,1000等，測(cè)試其是否正常運(yùn)行，比較運(yùn)行時(shí)間等）。實(shí)驗(yàn)四、二叉樹(shù)的實(shí)現(xiàn)及操作一、 實(shí)驗(yàn)?zāi)康恼莆斩鏄?shù)的定義、結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及使用范圍，各種遍歷算法。掌握用指針類型描述、訪問(wèn)和處理二叉樹(shù)的運(yùn)算。二、 實(shí)驗(yàn)內(nèi)容及要求有如下二叉樹(shù)：ABCDEFG根程序代碼給出了該二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的建立、前序、中序、后序遍歷的算法，同時(shí)也給出了查詢“E”是否在二叉樹(shù)里的

23、代碼。代碼有四處錯(cuò)誤，有標(biāo)識(shí)，屬于邏輯錯(cuò)誤，對(duì)照書中的代碼仔細(xì)分析后，請(qǐng)修改了在電腦里運(yùn)行，該實(shí)驗(yàn)無(wú)需寫實(shí)驗(yàn)報(bào)告，程序能完全執(zhí)行得滿分。改對(duì)一處得總分的四分之一。#include <stdlib.h>#include <stdio.h>typedef char DataType;typedef struct Node DataType data;/*數(shù)據(jù)域*/struct Node *leftChild;/*左子樹(shù)指針*/struct Node *rightChild;/*右子樹(shù)指針*/BiTreeNode;/*結(jié)點(diǎn)的結(jié)構(gòu)體定義*/*初始化創(chuàng)建二叉樹(shù)的頭結(jié)點(diǎn)*/void

24、 Initiate(BiTreeNode *root)*root = (BiTreeNode *)malloc(sizeof(BiTreeNode);(*root)->leftChild = NULL;(*root)->rightChild = NULL;void Destroy(BiTreeNode *root)if(*root) != NULL && (*root)->leftChild != NULL)Destroy(&(*root)->leftChild);if(*root) != NULL && (*root)->

25、rightChild != NULL)Destroy(&(*root)->rightChild);free(*root);/*若當(dāng)前結(jié)點(diǎn)curr非空，在curr的左子樹(shù)插入元素值為x的新結(jié)點(diǎn)*/*原curr所指結(jié)點(diǎn)的左子樹(shù)成為新插入結(jié)點(diǎn)的左子樹(shù)*/*若插入成功返回新插入結(jié)點(diǎn)的指針，否則返回空指針*/BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x)BiTreeNode *s, *t;if(curr = NULL) return NULL;t = curr->leftChild;/*保存原curr所指結(jié)點(diǎn)的左子樹(shù)指

26、針*/s = (BiTreeNode *)malloc(sizeof(BiTreeNode);s->data = x;s->leftChild = t;/*新插入結(jié)點(diǎn)的左子樹(shù)為原curr的左子樹(shù)*/s->rightChild = NULL;curr->leftChild = s;/*新結(jié)點(diǎn)成為curr的左子樹(shù)*/return curr->leftChild;/*返回新插入結(jié)點(diǎn)的指針*/*若當(dāng)前結(jié)點(diǎn)curr非空，在curr的右子樹(shù)插入元素值為x的新結(jié)點(diǎn)*/*原curr所指結(jié)點(diǎn)的右子樹(shù)成為新插入結(jié)點(diǎn)的右子樹(shù)*/*若插入成功返回新插入結(jié)點(diǎn)的指針，否則返回空指針*/BiT

27、reeNode *InsertRightNode(BiTreeNode *curr, DataType x)BiTreeNode *s, *t;if(curr = NULL) return NULL;t = curr->rightChild;/*保存原curr所指結(jié)點(diǎn)的右子樹(shù)指針*/s = (BiTreeNode *)malloc(sizeof(BiTreeNode);s->data = x;s->rightChild = t;/*新插入結(jié)點(diǎn)的右子樹(shù)為原curr的右子樹(shù)*/s->leftChild = NULL;curr->rightChild = s;/*新結(jié)點(diǎn)

28、成為curr的右子樹(shù)*/return curr->rightChild;/*返回新插入結(jié)點(diǎn)的指針*/void PreOrder(BiTreeNode *t, void visit(DataType item)/使用visit(item)函數(shù)前序遍歷二叉樹(shù)tif(t != NULL)/此小段有一處錯(cuò)誤visit(t->data);PreOrder(t-> rightChild, visit);PreOrder(t-> leftChild, visit);void InOrder(BiTreeNode *t, void visit(DataType item)/使用visi

29、t(item)函數(shù)中序遍歷二叉樹(shù)tif(t != NULL)/此小段有一處錯(cuò)誤InOrder(t->leftChild, visit);InOrder(t->rightChild, visit);visit(t->data);void PostOrder(BiTreeNode *t, void visit(DataType item)/使用visit(item)函數(shù)后序遍歷二叉樹(shù)tif(t != NULL)/此小段有一處錯(cuò)誤visit(t->data);PostOrder(t->leftChild, visit);PostOrder(t->rightChil

30、d, visit);void Visit(DataType item)printf("%c ", item);BiTreeNode *Search(BiTreeNode *root, DataType x)/需找元素x是否在二叉樹(shù)中BiTreeNode *find=NULL;if(root!=NULL)if(root->data=x)find=root;elsefind=Search(root->leftChild,x);if(find=NULL)find=Search(root->rightChild,x);return find;void main(v

31、oid)BiTreeNode *root, *p, *pp,*find;char x='E'Initiate(&root);p = InsertLeftNode(root, 'A');p = InsertLeftNode(p, 'B');p = InsertLeftNode(p, 'D');p = InsertRightNode(p, 'G');p = InsertRightNode(root->leftChild, 'C');pp = p;InsertLeftNode(p, '

32、;E');InsertRightNode(pp, 'F');printf("前序遍歷：");PreOrder(root->leftChild, Visit);printf("n中序遍歷：");InOrder(root->leftChild, Visit);printf("n后序遍歷：");PostOrder(root->leftChild, Visit);find=Search(root,x);if(find!=NULL)printf("n數(shù)據(jù)元素%c在二叉樹(shù)中 n",x)

33、;elseprintf("n數(shù)據(jù)元素%c不在二叉樹(shù)中 n",x);Destroy(&root);實(shí)驗(yàn)五、二叉樹(shù)的應(yīng)用一、實(shí)驗(yàn)?zāi)康募由顚?duì)二叉樹(shù)的各項(xiàng)操作實(shí)現(xiàn)的理解，增強(qiáng)學(xué)生利用二叉樹(shù)知識(shí)解決實(shí)際問(wèn)題的能力。二、實(shí)驗(yàn)要求本實(shí)驗(yàn)為選作題目。需編程實(shí)現(xiàn)，撰寫實(shí)驗(yàn)報(bào)告，并在實(shí)驗(yàn)報(bào)告中給出測(cè)試結(jié)果。三、實(shí)驗(yàn)內(nèi)容假設(shè)有一串字符串“DBDBDABDCDADBDADBDADACDBDBD”或者你自己給定一串任意的字符串，利用赫夫曼樹(shù)編程給出這串字符串的赫夫曼編碼。以下是上面字符串編碼后程序運(yùn)行結(jié)果示例（自己所編程序的輸入輸出形式可自由發(fā)揮）：四、 實(shí)驗(yàn)報(bào)告要求1、 基本要求見(jiàn)第3頁(yè)。

34、2、 給出實(shí)驗(yàn)結(jié)果。3、 對(duì)算法的性能進(jìn)行測(cè)試，要求分析算法的復(fù)雜度，測(cè)試程序在不同長(zhǎng)度的字符串下運(yùn)行情況。實(shí)驗(yàn)六、圖的遍歷操作一、實(shí)驗(yàn)?zāi)康恼莆沼邢驁D和無(wú)向圖的概念；掌握鄰接矩陣和鄰接鏈表建立圖的存儲(chǔ)結(jié)構(gòu)；掌握DFS及BFS對(duì)圖的遍歷操作；了解圖結(jié)構(gòu)在人工智能、工程等領(lǐng)域的廣泛應(yīng)用。二、 實(shí)驗(yàn)要求采用鄰接矩陣和鄰接鏈表作為圖的存儲(chǔ)結(jié)構(gòu)，完成有向圖和無(wú)向圖的DFS和BFS操作。本實(shí)驗(yàn)給出了示例程序，其中共有4處錯(cuò)誤，錯(cuò)誤段均有標(biāo)識(shí)，屬于邏輯錯(cuò)誤。請(qǐng)認(rèn)真理解程序，修改程序代碼，并在電腦上調(diào)試運(yùn)行。三、 DFS和BFS 的基本思想深度優(yōu)先搜索法DFS的基本思想：從圖G中某個(gè)頂點(diǎn)Vo出發(fā)，首先訪問(wèn)Vo

35、，然后選擇一個(gè)與Vo相鄰且沒(méi)被訪問(wèn)過(guò)的頂點(diǎn)Vi訪問(wèn)，再?gòu)腣i出發(fā)選擇一個(gè)與Vi相鄰且沒(méi)被訪問(wèn)過(guò)的頂點(diǎn)Vj訪問(wèn)，依次繼續(xù)。如果當(dāng)前被訪問(wèn)過(guò)的頂點(diǎn)的所有鄰接頂點(diǎn)都已被訪問(wèn)，則回退到已被訪問(wèn)的頂點(diǎn)序列中最后一個(gè)擁有未被訪問(wèn)的相鄰頂點(diǎn)的頂點(diǎn)W，從W出發(fā)按同樣方法向前遍歷。直到圖中所有的頂點(diǎn)都被訪問(wèn)。廣度優(yōu)先算法BFS的基本思想：從圖G中某個(gè)頂點(diǎn)Vo出發(fā)，首先訪問(wèn)Vo，然后訪問(wèn)與Vo相鄰的所有未被訪問(wèn)過(guò)的頂點(diǎn)V1，V2，Vt；再依次訪問(wèn)與V1，V2，Vt相鄰的起且未被訪問(wèn)過(guò)的的所有頂點(diǎn)。如此繼續(xù)，直到訪問(wèn)完圖中的所有頂點(diǎn)。V6V4V5V7V2V3V1V0Vo圖G的示例四、 示例程序1 鄰接矩陣作為存儲(chǔ)結(jié)

36、構(gòu)的程序示例#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100 /定義最大頂點(diǎn)數(shù)typedef struct char vexsMaxVertexNum; /頂點(diǎn)表 int edgesMaxVertexNumMaxVertexNum; /鄰接矩陣，可看作邊表 int n,e; /圖中的頂點(diǎn)數(shù)n和邊數(shù)eMGraph; /用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=void CreatMGraph(MGraph *G) int i,j,k; char a; printf("Input

37、 VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); /輸入頂點(diǎn)數(shù)和邊數(shù) scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i<G->n;i+) scanf("%c",&a); G->vexsi=a; /讀入頂點(diǎn)信息，建立頂點(diǎn)表 for(i=0;i<G->n;i+)for(j=0;j<G->

38、;n;j+) G->edgesij=0; /初始化鄰接矩陣 printf("Input edges,Creat Adjacency Matrixn"); for(k=0;k<G->e;k+) /讀入e條邊，建立鄰接矩陣 scanf("%d%d",&i,&j); /輸入邊（Vi，Vj）的頂點(diǎn)序號(hào) G->edgesij=1; G->edgesji=1; /若為無(wú)向圖，矩陣為對(duì)稱矩陣；若建立有向圖，去掉該條語(yǔ)句 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolea

39、n visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(MGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣 int j; printf("%c",G->vexsi); /訪問(wèn)頂點(diǎn)Vi visitedi=TRUE; /置已訪問(wèn)標(biāo)志 for(j=0;j<G->n;j+) /依次搜索Vi的鄰接點(diǎn)if(G->edgesij=1 && ! visitedj) DFSM(G,j); /（Vi，Vj）E，且Vj未訪問(wèn)過(guò)，故Vj為新出發(fā)點(diǎn)void DF

40、S(MGraph *G) 此段代碼有一處錯(cuò)誤 int i; for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化 for(i=0;i<G->n;i+)if(!visitedi) /Vi未訪問(wèn)過(guò) DFS (G,i); /以Vi為源點(diǎn)開(kāi)始DFS搜索/=BFS：廣度優(yōu)先遍歷=void BFS(MGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索 int i,j,f=0,r=0; int cqMaxVertexNum; /定義隊(duì)列 for(i=0;i<G->n;i+)visitedi=FALSE; /

41、標(biāo)志向量初始化 for(i=0;i<G->n;i+)cqi=-1; /隊(duì)列初始化 printf("%c",G->vexsk); /訪問(wèn)源點(diǎn)Vk visitedk=TRUE; cqr=k; /Vk已訪問(wèn)，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì) while(cqf!=-1) /隊(duì)非空則執(zhí)行 i=cqf; f=f+1; /Vf出隊(duì) for(j=0;j<G->n;j+) /依次Vi的鄰接點(diǎn)Vj if(G->edgesij=1 && !visitedj) /Vj未訪問(wèn) 以下三行代碼有一處錯(cuò)誤 printf("%c"

42、,G->vexsj); /訪問(wèn)Vj visitedj=FALSE; r=r+1; cqr=j; /訪問(wèn)過(guò)Vj入隊(duì) /=main=void main() int i; MGraph *G; G=(MGraph *)malloc(sizeof(MGraph); /為圖G申請(qǐng)內(nèi)存空間 CreatMGraph(G); /建立鄰接矩陣 printf("Print Graph DFS: "); DFS(G); /深度優(yōu)先遍歷 printf("n"); printf("Print Graph BFS: "); BFS(G,3); /以序號(hào)為3

43、的頂點(diǎn)開(kāi)始廣度優(yōu)先遍歷 printf("n");執(zhí)行順序：Input VertexNum(n) and EdgesNum(e): 8，9Input Vertex string: 01234567Input edges,Creat Adjacency Matrix0 10 21 31 42 52 63 74 75 6Print Graph DFS: 01374256Print Graph BFS: 317042562 鄰接鏈表作為存儲(chǔ)結(jié)構(gòu)程序示例#include"stdio.h"#include"stdlib.h"#define Max

44、VertexNum 50 /定義最大頂點(diǎn)數(shù)typedef struct node /邊表結(jié)點(diǎn) int adjvex; /鄰接點(diǎn)域 struct node *next; /鏈域EdgeNode;typedef struct vnode /頂點(diǎn)表結(jié)點(diǎn) char vertex; /頂點(diǎn)域 EdgeNode *firstedge; /邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是鄰接表類型typedef struct AdjList adjlist; /鄰接表 int n,e; /圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) ALGraph;

45、 /圖類型/=建立圖的鄰接表=void CreatALGraph(ALGraph *G) int i,j,k; char a; EdgeNode *s; /定義邊表結(jié)點(diǎn) printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); /讀入頂點(diǎn)數(shù)和邊數(shù) scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i<G->n;i+

46、) /建立邊表 scanf("%c",&a);G->adjlisti.vertex=a; /讀入頂點(diǎn)信息G->adjlisti.firstedge=NULL; /邊表置為空表 printf("Input edges,Creat Adjacency Listn"); for(k=0;k<G->e;k+) /建立邊表 scanf("%d%d",&i,&j); /讀入邊（Vi，Vj）的頂點(diǎn)對(duì)序號(hào)s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成邊表結(jié)點(diǎn)s-&g

47、t;adjvex=j; /鄰接點(diǎn)序號(hào)為js->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode); s->adjvex=i; /鄰接點(diǎn)序號(hào)為is->next=G->adjlistj.firstedge; G->adjlistj.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boole

48、an visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(ALGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表示的圖G進(jìn)行DFS搜索 EdgeNode *p; printf("%c",G->adjlisti.vertex); /訪問(wèn)頂點(diǎn)Vi visitedi=TRUE; /標(biāo)記Vi已訪問(wèn) p=G->adjlisti.firstedge; /取Vi邊表的頭指針while(p) /依次搜索Vi的鄰接點(diǎn)Vj，這里j=p->adjvex 以下3行代碼有一處錯(cuò)誤if(! visitedp->adjvex) /若Vj尚未被訪問(wèn) DFS (G,p->adj