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

《數(shù)據(jù)構(gòu)造》實(shí)驗(yàn)指引書計(jì)算機(jī)專業(yè)實(shí)驗(yàn)中心編TIME\@"yyyy'年'M'月'd'日'"10月23日

目錄《數(shù)據(jù)構(gòu)造》上機(jī)實(shí)驗(yàn)內(nèi)容和規(guī)定 3實(shí)驗(yàn)一、順序表實(shí)現(xiàn)及應(yīng)用 5實(shí)驗(yàn)二、鏈表實(shí)現(xiàn)及應(yīng)用 8實(shí)驗(yàn)三、棧實(shí)現(xiàn)及應(yīng)用 13實(shí)驗(yàn)四、隊(duì)列實(shí)現(xiàn)及應(yīng)用 14實(shí)驗(yàn)五、二叉樹操作及應(yīng)用 15實(shí)驗(yàn)六、圖遍歷操作及應(yīng)用 20實(shí)驗(yàn)七、查找算法實(shí)現(xiàn) 27實(shí)驗(yàn)八、排序算法實(shí)現(xiàn) 29

《數(shù)據(jù)構(gòu)造》上機(jī)實(shí)驗(yàn)內(nèi)容和規(guī)定通過上機(jī)實(shí)驗(yàn)加深對課程內(nèi)容理解，增長感性結(jié)識，提高程序設(shè)計(jì)、開發(fā)及調(diào)試能力。序號實(shí)驗(yàn)名稱內(nèi)容提要每組人數(shù)實(shí)驗(yàn)時數(shù)實(shí)驗(yàn)規(guī)定實(shí)驗(yàn)類別分值（總100分）1順序表實(shí)現(xiàn)及應(yīng)用掌握順序表構(gòu)造，實(shí)現(xiàn)其插入、刪除等算法。運(yùn)用順序表將兩個有序線性表合并為一種有序表。12必做設(shè)計(jì)10分2鏈表實(shí)現(xiàn)及應(yīng)用掌握單鏈表構(gòu)造，實(shí)現(xiàn)其插入、刪除、查找等算法。運(yùn)用單鏈表將兩個有序鏈表合并為一種有序鏈表。12必做設(shè)計(jì)10分3棧實(shí)現(xiàn)及應(yīng)用掌握棧構(gòu)造，將棧應(yīng)用于表達(dá)式計(jì)算問題12必做設(shè)計(jì)15分4隊(duì)列實(shí)現(xiàn)及應(yīng)用掌握隊(duì)列構(gòu)造，將隊(duì)列應(yīng)用于模仿服務(wù)臺前排隊(duì)現(xiàn)象問題12必做設(shè)計(jì)15分5二叉樹操作及應(yīng)用掌握二叉樹存儲，實(shí)現(xiàn)三種遍歷遞歸算法、實(shí)現(xiàn)前序或中序非遞歸遍歷算法12必做設(shè)計(jì)15分6圖遍歷操作及應(yīng)用實(shí)現(xiàn)圖存儲、深度遍歷和廣度遍歷算法12必做設(shè)計(jì)10分7查找算法實(shí)現(xiàn)實(shí)現(xiàn)順序表二分查找算法12必做設(shè)計(jì)10分8排序算法實(shí)現(xiàn)實(shí)現(xiàn)直接插入排序、迅速排序等算法12必做設(shè)計(jì)15分本實(shí)驗(yàn)指引書合用于16學(xué)時《數(shù)據(jù)構(gòu)造》實(shí)驗(yàn)課，實(shí)驗(yàn)項(xiàng)目詳細(xì)內(nèi)容如下：實(shí)驗(yàn)報(bào)告規(guī)定請按照實(shí)驗(yàn)教師規(guī)定，準(zhǔn)時提交實(shí)驗(yàn)報(bào)告電子版文獻(xiàn)。實(shí)驗(yàn)報(bào)告格式可個性化定義，內(nèi)容涉及但不限于如下內(nèi)容：題目、姓名、學(xué)號、班級（首頁）需求分析：陳述程序設(shè)計(jì)任務(wù)，強(qiáng)調(diào)程序要做什么，明確規(guī)定：輸入形式和輸出值范疇；輸出形式；程序所能達(dá)到功能；測試數(shù)據(jù)：涉及對的輸入輸出成果和錯誤輸入及輸出成果。概要設(shè)計(jì)：闡明用到數(shù)據(jù)構(gòu)造定義、主程序流程及各程序模塊之間調(diào)用關(guān)系。詳細(xì)設(shè)計(jì)：提交帶注釋源程序或者用偽代碼寫出每個操作所涉及算法。調(diào)試分析：調(diào)試過程中所遇到問題及解決辦法；算法時空分析；經(jīng)驗(yàn)與體會。顧客使用闡明：闡明如何使用你設(shè)計(jì)程序，詳細(xì)列出每一步操作環(huán)節(jié)。（如果程序操作簡樸，可略去）測試成果：列出對于給定輸入所產(chǎn)生輸出成果。（若有也許，測試隨輸入規(guī)模增長所用算法實(shí)際運(yùn)營時間變化）8、總結(jié)

實(shí)驗(yàn)一、順序表實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)坷斫夂驼莆站€性表順序存儲構(gòu)造；掌握用C語言上機(jī)調(diào)試線性表基本辦法；掌握線性表基本操作：插入、刪除、查找以及線性表合并等運(yùn)算在順序存儲構(gòu)造和鏈接存儲構(gòu)造上運(yùn)算，以及對相應(yīng)算法性能分析。二、實(shí)驗(yàn)規(guī)定給定一段程序代碼，程序代碼所完畢功能為：（1）建立一種線性表；（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ù)元素個數(shù)在最壞狀況下不會超過100個，規(guī)定使用順序表。程序中有3處錯誤地方，有標(biāo)記，屬于邏輯錯誤，對照書中代碼仔細(xì)分析后，規(guī)定同窗們修改錯誤代碼，修改后上機(jī)調(diào)試得到對的運(yùn)營成果。三、程序代碼#include<stdio.h>#defineMaxSize100typedefintDataType;typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;voidListInitiate(SeqList*L)/*初始化順序表L*/{L->size=0;/*定義初始數(shù)據(jù)元素個數(shù)*/}intListLength(SeqListL)/*返回順序表L當(dāng)前數(shù)據(jù)元素個數(shù)*/{returnL.size;}intListInsert(SeqList*L，inti，DataTypex)/*在順序表L位置i（0≤i≤size）前插入數(shù)據(jù)元素值x*//*插入成功返回1，插入失敗返回0*/{intj;if(L->size>=MaxSize){printf("順序表已滿無法插入！\n");return0;}elseif(i<0||i>L->size){printf("參數(shù)i不合法！\n");return0;}else{//此段程序有一處錯誤for(j=L->size；j>i；j--)L->list[j]=L->list[j];/*為插入做準(zhǔn)備*/L->list[i]=x;/*插入*/L->size++;/*元素個數(shù)加1*/return1;}}intListDelete(SeqList*L，inti，DataType*x)/*刪除順序表L中位置i（0≤i≤size-1）數(shù)據(jù)元素值并存儲到參數(shù)x中*//*刪除成功返回1，刪除失敗返回0*/{intj;if(L->size<=0){printf("順序表已空無數(shù)據(jù)元素可刪！\n");return0;}elseif(i<0||i>L->size-1){printf("參數(shù)i不合法");return0;}else{//此段程序有一處錯誤*x=L->list[i];/*保存刪除元素到參數(shù)x中*/for(j=i+1；j<=L->size-1；j++)L->list[j]=L->list[j-1];/*依次前移*/L->size--;/*數(shù)據(jù)元素個數(shù)減1*/return1;}}intListGet(SeqListL，inti，DataType*x)/*取順序表L中第i個數(shù)據(jù)元素值存于x中，成功則返回1，失敗返回0*/{if(i<0||i>L.size-1){printf("參數(shù)i不合法！\n");return0;}else{*x=L.list[i];return1;}}voidmain(void){SeqListmyList;inti，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)；//此段程序有一處錯誤printf("%"，x);}}四、實(shí)驗(yàn)任務(wù)1.改正上述程序中錯誤（必作）。2.編寫合并函數(shù)，將兩個有序線性表合并為一種有序表并在主函數(shù)中加以測試（選作）。3.完畢實(shí)驗(yàn)報(bào)告撰寫。

實(shí)驗(yàn)二、鏈表實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)坷斫夂驼莆站€性表鏈?zhǔn)酱鎯?gòu)造；掌握用C語言上機(jī)調(diào)試線性表基本辦法；掌握線性表基本操作：插入、刪除、查找以及線性表合并等運(yùn)算在順序存儲構(gòu)造和鏈接存儲構(gòu)造上運(yùn)算，以及對相應(yīng)算法性能分析。二、實(shí)驗(yàn)規(guī)定給定一段程序代碼，程序代碼所完畢功能為：（1）建立一種線性表；（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ù)元素個數(shù)在最壞狀況下不會超過100個，規(guī)定使用單鏈表。程序中有3處錯誤地方，有標(biāo)記，屬于邏輯錯誤，對照書中代碼仔細(xì)分析后，規(guī)定同窗們修改錯誤代碼，上機(jī)調(diào)試并得到對的運(yùn)營成果。三、程序代碼：#include<stdio.h>/*該文獻(xiàn)包括pringtf()等函數(shù)*/#include<stdlib.h>/*該文獻(xiàn)包括exit()等函數(shù)*/#include<malloc.h>/*該文獻(xiàn)包括malloc()等函數(shù)*/typedefintDataType;/*定義DataType為int*/typedefstructNode{DataTypedata;structNode*next;}SLNode;voidListInitiate(SLNode**head)/*初始化*/{/*如果有內(nèi)存空間，申請頭結(jié)點(diǎn)空間并使頭指針head指向頭結(jié)點(diǎn)*/if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);(*head)->next=NULL;/*置鏈尾標(biāo)記NULL*/}intListLength(SLNode*head)/*單鏈表長度*/{SLNode*p=head;/*p指向首元結(jié)點(diǎn)*/intsize=0;/*size初始為0*/while(p->next!=NULL)/*循環(huán)計(jì)數(shù)*/{p=p->next;size++;}returnsize;}intListInsert(SLNode*head，inti，DataTypex)/*在帶頭結(jié)點(diǎn)單鏈表head數(shù)據(jù)元素ai（0≤i≤size）結(jié)點(diǎn)前*//*插入一種存儲數(shù)據(jù)元素x結(jié)點(diǎn)*/{SLNode*p，*q;intj;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ù)錯！");return0;}/*生成新結(jié)點(diǎn)由指針q批示*/if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);q->data=x;//此段程序有一處錯誤p->next=q->next;/*給指針q->next賦值*/p->next=q;/*給指針p->next重新賦值*/return1;}intListDelete(SLNode*head，inti，DataType*x)/*刪除帶頭結(jié)點(diǎn)單鏈表head數(shù)據(jù)元素ai（0≤i≤size-1）結(jié)點(diǎn)*//*刪除結(jié)點(diǎn)數(shù)據(jù)元素域值由x帶回。刪除成功時返回1；失敗返回0*/{SLNode*p，*s;intj;p=head；/*p指向首元結(jié)點(diǎn)*/j=-1;/*j初始為-1*/while(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ù)錯！");return0;}//此段程序有一處錯誤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)從單鏈表中刪除指*/free(s);/*釋放指針s所指結(jié)點(diǎn)內(nèi)存空間*/return1;}intListGet(SLNode*head，inti，DataType*x)/*取數(shù)據(jù)元素ai和刪除函數(shù)類同，只是不刪除數(shù)據(jù)元素ai結(jié)點(diǎn)*/{SLNode*p;intj;p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j!=i){printf("取元素位置參數(shù)錯！");return0;}//此段程序有一處錯誤*x=p->next;return1;}voidDestroy(SLNode**head){SLNode*p，*p1;p=*head;while(p!=NULL){p1=p;p=p->next;free(p1);}*head=NULL;}voidmain(void){SLNode*head;inti，x;ListInitiate(&head);/*初始化*/for(i=0；i<10；i++){if(ListInsert(head，i，i+1)==0)/*插入10個數(shù)據(jù)元素*/{printf("錯誤！\n");return;}}if(ListDelete(head，4，&x)==0)/*刪除數(shù)據(jù)元素5*/{printf("錯誤！\n");return;}for(i=0；i<ListLength(head)；i++){if(ListGet(head，i，&x)==0)/*取元素*/{printf("錯誤！\n");return;}elseprintf("%d"，x);/*顯示數(shù)據(jù)元素*/}Destroy(&head);}三、實(shí)驗(yàn)任務(wù)1.改正上述程序中錯誤（必作）。2.編寫合并函數(shù)，將兩個有序單鏈表合并成一種有序單鏈表（選作）。3.完畢實(shí)驗(yàn)報(bào)告撰寫。

實(shí)驗(yàn)三、棧實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)?.掌握棧存儲表達(dá)和實(shí)現(xiàn)2.掌握?；静僮鲗?shí)現(xiàn)。3.掌握棧在解決實(shí)際問題中應(yīng)用。二、實(shí)驗(yàn)規(guī)定問題描述：編寫程序?qū)崿F(xiàn)算術(shù)表達(dá)式求值，即驗(yàn)證某算術(shù)表達(dá)式對的性，若對的，則計(jì)算該算術(shù)表達(dá)式值。重要功能描述如下：1、從鍵盤上輸入表達(dá)式。2、分析該表達(dá)式與否合法。3、若上述解決過程中沒有發(fā)現(xiàn)錯誤，則以為該表達(dá)式合法，計(jì)算并打印解決成果。三、重要功能函數(shù)參照程序中重要包括下面幾種功能函數(shù)：voidinitstack()：初始化堆棧intMake_str()：語法檢查intpush_operate(intoperate)：將操作碼壓入堆棧intpush_num(doublenum)：將操作數(shù)壓入堆棧intprocede(intoperate)：解決操作碼intchange_opnd(intoperate)：將字符型操作碼轉(zhuǎn)換成優(yōu)先級intpush_opnd(intoperate)：將操作碼壓入堆棧intpop_opnd()：將操作碼彈出堆棧intcaculate(intcur_opnd)：簡樸計(jì)算+，-，*，/doublepop_num()：彈出操作數(shù)四、實(shí)驗(yàn)任務(wù)認(rèn)真閱讀與理解實(shí)驗(yàn)內(nèi)容詳細(xì)規(guī)定，參照教材有關(guān)章節(jié)，結(jié)合實(shí)驗(yàn)內(nèi)容規(guī)定，編寫實(shí)驗(yàn)程序并上機(jī)調(diào)試與測試，完畢實(shí)驗(yàn)報(bào)告撰寫。

實(shí)驗(yàn)四、隊(duì)列實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)?.掌握隊(duì)列存儲表達(dá)和實(shí)現(xiàn)。2.掌握隊(duì)列基本操作實(shí)現(xiàn)。3.掌握隊(duì)列在解決實(shí)際問題中應(yīng)用。二、實(shí)驗(yàn)規(guī)定運(yùn)用隊(duì)列模仿服務(wù)臺前排隊(duì)現(xiàn)象問題。問題描述：某銀行有一種客戶辦理業(yè)務(wù)站，在單位時間內(nèi)隨機(jī)地有客戶到達(dá)，設(shè)每位客戶業(yè)務(wù)辦理時間是某個范疇隨機(jī)值。設(shè)只有一種窗口，一位業(yè)務(wù)人員，規(guī)定程序模仿記錄在設(shè)定期間內(nèi)，業(yè)務(wù)人員總空閑時間和客戶平均等待時間。假定模仿數(shù)據(jù)已按客戶到達(dá)先后順序依次存于某個文本數(shù)據(jù)文獻(xiàn)中，相應(yīng)每位客戶有兩個數(shù)據(jù)：到達(dá)時間和需要辦理業(yè)務(wù)時間。三、實(shí)驗(yàn)任務(wù)認(rèn)真閱讀與理解實(shí)驗(yàn)內(nèi)容詳細(xì)規(guī)定，參照教材有關(guān)章節(jié)，結(jié)合實(shí)驗(yàn)內(nèi)容規(guī)定，編寫實(shí)驗(yàn)程序并上機(jī)調(diào)試與測試，完畢實(shí)驗(yàn)報(bào)告撰寫。

實(shí)驗(yàn)五、二叉樹操作及應(yīng)用實(shí)驗(yàn)?zāi)空莆斩鏄涠x、構(gòu)造特性，以及各種存儲構(gòu)造特點(diǎn)及使用范疇，各種遍歷算法。掌握用指針類型描述、訪問和解決二叉樹運(yùn)算。掌握前序或中序非遞歸遍歷算法。實(shí)驗(yàn)規(guī)定有如下二叉樹：∧∧AB∧C∧D∧E∧∧F∧∧G∧根程序代碼給出了該二叉樹鏈?zhǔn)酱鎯?gòu)造建立、前序、中序、后序遍歷算法，同步也給出了查詢“E”與否在二叉樹里代碼。代碼有三處錯誤，有標(biāo)記，屬于邏輯錯誤，對照書中代碼仔細(xì)分析后，請修改了在電腦里運(yùn)營。#include<stdlib.h>#include<stdio.h>typedefcharDataType;typedefstructNode{DataTypedata;/*數(shù)據(jù)域*/structNode*leftChild;/*左子樹指針*/structNode*rightChild;/*右子樹指針*/}BiTreeNode;/*結(jié)點(diǎn)構(gòu)造體定義*//*初始化創(chuàng)立二叉樹頭結(jié)點(diǎn)*/voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}voidDestroy(BiTreeNode**root){if((*root)!=NULL&&(*root)->leftChild!=NULL)Destroy(&(*root)->leftChild);if((*root)!=NULL&&(*root)->rightChild!=NULL)Destroy(&(*root)->rightChild);free(*root);}/*若當(dāng)前結(jié)點(diǎn)curr非空，在curr左子樹插入元素值為x新結(jié)點(diǎn)*//*原curr所指結(jié)點(diǎn)左子樹成為新插入結(jié)點(diǎn)左子樹*//*若插入成功返回新插入結(jié)點(diǎn)指針，否則返回空指針*/BiTreeNode*InsertLeftNode(BiTreeNode*curr，DataTypex){BiTreeNode*s，*t;if(curr==NULL)returnNULL;t=curr->leftChild;/*保存原curr所指結(jié)點(diǎn)左子樹指針*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->leftChild=t;/*新插入結(jié)點(diǎn)左子樹為原curr左子樹*/s->rightChild=NULL;curr->leftChild=s;/*新結(jié)點(diǎn)成為curr左子樹*/returncurr->leftChild;/*返回新插入結(jié)點(diǎn)指針*/}/*若當(dāng)前結(jié)點(diǎn)curr非空，在curr右子樹插入元素值為x新結(jié)點(diǎn)*//*原curr所指結(jié)點(diǎn)右子樹成為新插入結(jié)點(diǎn)右子樹*//*若插入成功返回新插入結(jié)點(diǎn)指針，否則返回空指針*/BiTreeNode*InsertRightNode(BiTreeNode*curr，DataTypex){BiTreeNode*s，*t;if(curr==NULL)returnNULL;t=curr->rightChild;/*保存原curr所指結(jié)點(diǎn)右子樹指針*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->rightChild=t;/*新插入結(jié)點(diǎn)右子樹為原curr右子樹*/s->leftChild=NULL;curr->rightChild=s;/*新結(jié)點(diǎn)成為curr右子樹*/returncurr->rightChild;/*返回新插入結(jié)點(diǎn)指針*/}voidPreOrder(BiTreeNode*t，voidvisit(DataTypeitem))//使用visit(item)函數(shù)前序遍歷二叉樹t{if(t!=NULL){//此小段有一處錯誤visit(t->data);PreOrder(t->rightChild，visit);PreOrder(t->leftChild，visit);}}voidInOrder(BiTreeNode*t，voidvisit(DataTypeitem))//使用visit(item)函數(shù)中序遍歷二叉樹t{if(t!=NULL){//此小段有一處錯誤InOrder(t->leftChild，visit);InOrder(t->rightChild，visit);visit(t->data);}}voidPostOrder(BiTreeNode*t，voidvisit(DataTypeitem))//使用visit(item)函數(shù)后序遍歷二叉樹t{if(t!=NULL){//此小段有一處錯誤visit(t->data);PostOrder(t->leftChild，visit);PostOrder(t->rightChild，visit);}}voidVisit(DataTypeitem){printf("%c"，item);}BiTreeNode*Search(BiTreeNode*root，DataTypex)//需找元素x與否在二叉樹中{BiTreeNode*find=NULL;if(root!=NULL){if(root->data==x)find=root;else{find=Search(root->leftChild,x);if(find==NULL)find=Search(root->rightChild,x);}}returnfind;}voidmain(void){BiTreeNode*root，*p，*pp,*find;charx='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，'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在二叉樹中\(zhòng)n",x);elseprintf("\n數(shù)據(jù)元素%c不在二叉樹中\(zhòng)n",x);Destroy(&root);}實(shí)驗(yàn)任務(wù)：1.改正程序錯誤（必作）。2.編寫二叉樹前序（或中序）非遞歸遍歷算法并進(jìn)行測試（選作）。3.完畢實(shí)驗(yàn)報(bào)告撰寫。

實(shí)驗(yàn)六、圖遍歷操作及應(yīng)用一、實(shí)驗(yàn)?zāi)空莆沼邢驁D和無向圖概念；掌握鄰接矩陣和鄰接鏈表建立圖存儲構(gòu)造；掌握DFS及BFS對圖遍歷操作；理解圖構(gòu)造在人工智能、工程等領(lǐng)域廣泛應(yīng)用。實(shí)驗(yàn)規(guī)定采用鄰接矩陣和鄰接鏈表作為圖存儲構(gòu)造，完畢有向圖和無向圖DFS和BFS操作。本實(shí)驗(yàn)給出了示例程序，其中共有4處錯誤，錯誤段均有標(biāo)記，屬于邏輯錯誤。請認(rèn)真理解程序，修改程序代碼，并在電腦上調(diào)試運(yùn)營。DFS和BFS基本思想深度優(yōu)先搜索法DFS基本思想：從圖G中某個頂點(diǎn)Vo出發(fā)，一方面訪問Vo，然后選取一種與Vo相鄰且沒被訪問過頂點(diǎn)Vi訪問，再從Vi出發(fā)選取一種與Vi相鄰且沒被訪問過頂點(diǎn)Vj訪問，……依次繼續(xù)。如果當(dāng)前被訪問過頂點(diǎn)所有鄰接頂點(diǎn)都已被訪問，則回退到已被訪問頂點(diǎn)序列中最后一種擁有未被訪問相鄰頂點(diǎn)頂點(diǎn)W，從W出發(fā)按同樣辦法向前遍歷。直到圖中所有頂點(diǎn)都被訪問。廣度優(yōu)先算法BFS基本思想：從圖G中某個頂點(diǎn)Vo出發(fā)，一方面訪問Vo，然后訪問與Vo相鄰所有未被訪問過頂點(diǎn)V1，V2，……，Vt；再依次訪問與V1，V2，……，Vt相鄰起且未被訪問過所有頂點(diǎn)。如此繼續(xù)，直到訪問完圖中所有頂點(diǎn)。V6V4V6V4V5V7V2V3V1V0Vo圖G示例鄰接矩陣作為存儲構(gòu)造程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定義最大頂點(diǎn)數(shù)typedefstruct{charvexs[MaxVertexNum]；//頂點(diǎn)表intedges[MaxVertexNum][MaxVertexNum]；

//鄰接矩陣，可看作邊表intn,e；//圖中頂點(diǎn)數(shù)n和邊數(shù)e}MGraph；//用鄰接矩陣表達(dá)圖類型//=========建立鄰接矩陣=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e)：");scanf("%d,%d",&G->n,&G->e)；//輸入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a)；printf("InputVertexstring:");for(i=0;i<G->n;i++){scanf("%c",&a);G->vexs[i]=a；//讀入頂點(diǎn)信息，建立頂點(diǎn)表}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0；//初始化鄰接矩陣printf("Inputedges,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){//讀入e條邊，建立鄰接矩陣scanf("%d%d",&i,&j)；//輸入邊（Vi，Vj）頂點(diǎn)序號G->edges[i][j]=1；G->edges[j][i]=1；//若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句}}//=========定義標(biāo)志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷遞歸算法======voidDFSM(MGraph*G,inti){//以Vi為出發(fā)點(diǎn)對鄰接矩陣表達(dá)圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣intj;printf("%c",G->vexs[i])；//訪問頂點(diǎn)Vivisited[i]=TRUE；//置已訪問標(biāo)志for(j=0;j<G->n;j++)//依次搜索Vi鄰接點(diǎn)if(G->edges[i][j]==1&&！visited[j])DFSM(G,j)；//（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發(fā)點(diǎn)}voidDFS(MGraph*G){\\此段代碼有一處錯誤inti;for(i=0;i<G->n;i++)visited[i]=FALSE；//標(biāo)志向量初始化for(i=0;i<G->n;i++)if(!visited[i])//Vi未訪問過DFS(G,i)；//以Vi為源點(diǎn)開始DFS搜索}//===========BFS：廣度優(yōu)先遍歷=======voidBFS(MGraph*G,intk){//以Vk為源點(diǎn)對用鄰接矩陣表達(dá)圖G進(jìn)行廣度優(yōu)先搜索inti,j,f=0,r=0;intcq[MaxVertexNum]；//定義隊(duì)列for(i=0;i<G->n;i++)visited[i]=FALSE；//標(biāo)志向量初始化for(i=0;i<G->n;i++)cq[i]=-1；//隊(duì)列初始化printf("%c",G->vexs[k])；//訪問源點(diǎn)Vkvisited[k]=TRUE;cq[r]=k；//Vk已訪問，將其入隊(duì)。注意，事實(shí)上是將其序號入隊(duì)while(cq[f]!=-1){//隊(duì)非空則執(zhí)行i=cq[f]；f=f+1；//Vf出隊(duì)for(j=0;j<G->n;j++)//依次Vi鄰接點(diǎn)Vjif(G->edges[i][j]==1&&!visited[j]){//Vj未訪問\\如下三行代碼有一處錯誤printf("%c",G->vexs[j])；//訪問Vjvisited[j]=FALSE;

r=r+1；cq[r]=j；//訪問過Vj入隊(duì)}}}//==========main=====voidmain(){inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph))；//為圖G申請內(nèi)存空間CreatMGraph(G)；//建立鄰接矩陣printf("PrintGraphDFS：");DFS(G)；//深度優(yōu)先遍歷printf("\n");printf("PrintGraphBFS：");BFS(G,3)；//以序號為3頂點(diǎn)開始廣度優(yōu)先遍歷printf("\n");}執(zhí)行順序：InputVertexNum(n)andEdgesNum(e)：8，9InputVertexstring：01234567Inputedges,CreatAdjacencyMatrix010213142526374756PrintGraphDFS：01374256PrintGraphBFS：31704256鄰接鏈表作為存儲構(gòu)造程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50//定義最大頂點(diǎn)數(shù)typedefstructnode{//邊表結(jié)點(diǎn)intadjvex；//鄰接點(diǎn)域structnode*next；//鏈域}EdgeNode;typedefstructvnode{//頂點(diǎn)表結(jié)點(diǎn)charvertex；//頂點(diǎn)域EdgeNode*firstedge；//邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum]；//AdjList是鄰接表類型typedefstruct{AdjListadjlist；//鄰接表intn,e；//圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)}ALGraph；//圖類型//=========建立圖鄰接表=======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s；//定義邊表結(jié)點(diǎn)printf("InputVertexNum(n)andEdgesNum(e)：");scanf("%d,%d",&G->n,&G->e)；//讀入頂點(diǎn)數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++)//建立邊表{scanf("%c",&a);G->adjlist[i].vertex=a；//讀入頂點(diǎn)信息G->adjlist[i].firstedge=NULL；//邊表置為空表}printf("Inputedges,CreatAdjacencyList\n");for(k=0;k<G->e;k++){//建立邊表scanf("%d%d",&i,&j)；//讀入邊（Vi，Vj）頂點(diǎn)對序號s=(EdgeNode*)malloc(sizeof(EdgeNode))；//生成邊表結(jié)點(diǎn)s->adjvex=j；//鄰接點(diǎn)序號為js->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s；//將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi邊表頭部s=(EdgeNode*)malloc(sizeof(EdgeNode))；s->adjvex=i；//鄰接點(diǎn)序號為is->next=G->adjlist[j].firstedge；G->adjlist[j].firstedge=s；//將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj邊表頭部}}//=========定義標(biāo)志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷遞歸算法======voidDFSM(ALGraph*G,inti){//以Vi為出發(fā)點(diǎn)對鄰接鏈表表達(dá)圖G進(jìn)行DFS搜索EdgeNode*p;printf("%c",G->adjlist[i].vertex)；//訪問頂點(diǎn)Vivisited[i]=TRUE；//標(biāo)記Vi已訪問p=G->adjlist[i].firstedge；//取Vi邊表頭指針while(p){//依次搜索Vi鄰接點(diǎn)Vj，這里j=p->adjvex\\如下3行代碼有一處錯誤if(！visited[p->adjvex])//若Vj尚未被訪問DFS(G,p->adjvex)；//則以Vj為出發(fā)點(diǎn)向縱深搜索p=p->next；//找Vi下一種鄰接點(diǎn)}}voidDFS(ALGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE；//標(biāo)志向量初始化for(i=0;i<G->n;i++)if(!visited[i])//Vi未訪問過

DFSM(G,i)；//以Vi為源點(diǎn)開始DFS搜索

}

//==========BFS：廣度優(yōu)先遍歷=========voidBFS(ALGraph*G,intk)

{//以Vk為源點(diǎn)對用鄰接鏈表表達(dá)圖G進(jìn)行廣度優(yōu)先搜索inti,f=0,r=0;

EdgeNode*p;

intcq[MaxVertexNum]；//定義FIFO隊(duì)列

for(i=0;i<G->n;i++)visited[i]=FALSE；//標(biāo)志向量初始化for(i=0;i<=G->n;i++)cq[i]=-1；//初始化標(biāo)志向量printf("%c",G->adjlist[k].vertex)；//訪問源點(diǎn)Vkvisited[k]=TRUE;cq[r]=k；//Vk已訪問，將其入隊(duì)。注意，事實(shí)上是將其序號入隊(duì)while(cq[f]!=-1){隊(duì)列非空則執(zhí)行i=cq[f]；f=f+1；//Vi出隊(duì)p=G->adjlist[i].firstedge；//取Vi邊表頭指針while(p){//依次搜索Vi鄰接點(diǎn)Vj（令p->adjvex=j）if(!visited[p->adjvex]){//若Vj未訪問過printf("%c",G->adjlist[p->adjvex].vertex)；//訪問Vjvisited[p->adjvex]=TRUE;//