圖的遍歷2 數(shù)據(jù)結構實驗報告

南昌航空大學實驗報告課程名稱：數(shù)據(jù)結構實驗名稱：實驗八圖的遍歷班級：學生姓名：學號：指導教師評定：簽名:題目：假設無向圖采用鄰接表結構表示。編程分別實現(xiàn)圖的深度優(yōu)先搜索算法和廣度優(yōu)先搜索算法。需求分析用戶可以根據(jù)自己的需求進行輸入所需的圖（可以是非連通圖也可以是連通圖），其中1表示創(chuàng)建一個有向圖，2表示創(chuàng)建一個無向圖。用戶進入菜單頁面選擇輸入圖的狀態(tài)（1表示創(chuàng)建一個有向圖，2表示創(chuàng)建一個無向圖，3表示輸出已創(chuàng)建的圖，4表示深度優(yōu)先遍歷已有的圖，5表示廣度優(yōu)先遍歷已有的圖，6表示退出程序狀態(tài)）。程序執(zhí)行的命令包括：（1）輸入圖的結點和弧構造圖（2）輸出圖（2）廣度優(yōu)先遍歷圖（3）深度優(yōu)先遍歷圖二、概要設計⒈為實現(xiàn)上述算法，需要鏈表的抽象數(shù)據(jù)類型：ADTGraph{數(shù)據(jù)對象V：V是具有相同特征的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關系R：R={VR}VR={<v,w>|v,w∈V且P（v,w），<v,w>表示從x到w的弧，謂詞P（v,w）定義了弧<v,w>的意義或信息}基本操作P:Creatgraph(&G,V,VR)初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結果：按V和VR的定義構造圖G。destroygraph(&G)初始條件：圖G存在。操作結果：銷毀圖G。displaygraph（G）初始條件：圖G存在。操作結果：顯示圖G。locatevex(G,u)初始條件：圖G存在，u和G中的頂點有相同的特征。操作結果：若G中存在頂點u，則返回該頂點在圖中位置，否則返回其他信息。getvex(G,v)初始條件：圖G存在，v是G中的某個頂點。操作結果：返回v的值。DFStraverse(G)初始條件：圖G存在。操作結果：對圖進行深度優(yōu)先遍歷。在遍歷過程中對每個頂點訪問一次。BFStraverse(&S,e)初始條件：圖G存在。操作結果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點訪問一次。}ADTGraph2.本程序有三個模塊：⑴主程序模塊main(){初始化；Switch（參數(shù)）{Case1：接受命令（用戶創(chuàng)建一個有向圖）；Case2：接受命令（用戶創(chuàng)建一個無向圖）；Case3：接受命令（輸出已創(chuàng)建的圖）；Case4：接受命令（深度優(yōu)先遍歷已有的圖）；Case5：接受命令（廣度優(yōu)先遍歷已有的圖）；Case6：接受命令（退出程序）；｝｝⑵創(chuàng)建圖的模塊：主要建立一個圖；⑶廣度優(yōu)先遍歷和深度優(yōu)先遍歷模塊：輸出這兩種遍歷的結果；(4)輸出圖模塊：顯示已創(chuàng)建的圖。三、詳細設計⒈元素類型，結點類型structarcnode{intadjvex;/*該弧所指向的頂點的位置*/intinfo;structarcnode*nextarc;/*指向下一條弧的指針*/};structvexnode{intdata;/*頂點的信息*/structarcnode*firstarc;/*指向第一條依附該頂點的弧的指針*/};structgraph{structvexnode*vexpex;intvexnum,arcnum;/*圖的當前的頂點數(shù)和弧數(shù)*/}；/*定義隊列*/structqueue{int*elem;intfront;intrear;};/*全局變量*/intn;/*圖的頂點數(shù)*/intvisit[100];/*標志數(shù)組*/structqueueQ;2.對抽象數(shù)據(jù)類型中的部分基本操作的偽碼算法如下：/*創(chuàng)建一個空隊列*/structqueueinitqueue(){structqueueq;q.elem=(int*)malloc(maxsize*sizeof(int));if(!q.elem)exit(0);q.front=q.rear=0;returnq;}/*入隊列*/structqueueenqueue(structqueueq,intv){if((q.rear+1)%maxsize==q.front)printf("thequeueisfull?。?！\n");else{q.elem[q.rear]=v;q.rear=(q.rear+1)%maxsize;}returnq;}/*出隊列*/intdequeue(structqueueq){intcur;if(q.rear==q.front){printf("thequeueisnull!!\n");exit(0);}else{cur=q.elem[q.front];q.front=(q.front+1)%maxsize;returncur;}}/*判斷隊列是否為空*/intemptyqueue(structqueueq){if(q.front==q.rear)return1;elsereturn0;}/*創(chuàng)建有向圖*/structgraphcreatgraph1(){inte,i,s,d;inta;structgraphg;structarcnode*p;printf("thenumberofvex(n)andarc(e):");scanf("%d%d",&n,&e);g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;}returng;}/*創(chuàng)建無向圖*/structgraphcreatgraph2(){inte,i,s,d;inta;structgraphg;structarcnode*p,*q;printf("thenumberofvex(n)andarc(e):");scanf("%d%d",&n,&e);g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;q=(structarcnode*)malloc(sizeof(structarcnode));q->adjvex=s;q->info=g.vexpex[s].data;q->nextarc=g.vexpex[d].firstarc;g.vexpex[d].firstarc=q;}returng;}/*顯示有向圖*/voiddisplaygraph(structgraphg,intn){inti;structarcnode*p;printf("diaplaythegraph;\n");for(i=0;i<n;i++){printf("[%d,%d]->",i,g.vexpex[i].data);p=g.vexpex[i].firstarc;while(p!=NULL){printf("(%d,%d)->",p->adjvex,p->info);p=p->nextarc;}printf("^\n");}}/*連通圖廣度優(yōu)先遍歷*/voidBFSsearch(structgraphg,intv){inti;structarcnode*p;Q=initqueue();printf("%5d",g.vexpex[v].data);enqueue(Q,v);visit[v]=TURE;while(!emptyqueue(Q)){i=dequeue(Q);p=g.vexpex[i].firstarc;while(p!=NULL){enqueue(Q,p->adjvex);if(visit[p->adjvex]==FALSE){printf("%5d",p->info);visit[p->adjvex]=TURE;}p=p->nextarc;}}}/*非連通圖廣度優(yōu)先遍歷*/voidBFS(structgraphg){inti;printf("BFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)if(visit[i]==FALSE)BFSsearch(g,i);printf("\n\n");}/*連通圖深度優(yōu)先遍歷*/voidDFSsearch(structgraphg,intv){structarcnode*p;printf("%5d",g.vexpex[v].data);visit[v]=TURE;p=g.vexpex[v].firstarc;while(p!=NULL){if(!visit[p->adjvex])DFSsearch(g,p->adjvex);p=p->nextarc;}}/*非連通圖深度優(yōu)先遍歷*/voidDFS(structgraphg){inti;printf("DFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)if(visit[i]==FALSE)DFSsearch(g,i);printf("\n\n");}/*主菜單定義*/intmenu_select(){chars[80];intc;gotoxy(1,25);/*將光標定在第25行第1列*/printf("pressanykeyentermenu\n");/*提示按任意鍵繼續(xù)*/getch();/*讀入任意字符*/clrscr();/*清屏*/gotoxy(1,1);printf("***************MENU***************\n\n");printf("1.Makeadigraphbyyouself!\n");printf("2.Makeaundigraphbyyouself!\n");printf("3.Ontputyourgraph!\n");printf("4.Depth_firstsearchyourgraph!\n");printf("5.Bredth_firstsearchyourgraph!\n");printf("6.Quit!\n");printf("**********************************\n");do{printf("\nEnteryouchoice(1~6):\n");/*提示輸入選項*/scanf("%s",s);/*輸入選擇項*/c=atoi(s);/*將輸入的字符串轉化為整型*/}while(c<1||c>6);returnc;}3.主函數(shù)和其他函數(shù)的偽碼算法voidmain(){structgraphg;inti;clrscr();/*清屏*/for(;;){switch(menu_select()){case1:{clrscr();g=creatgraph1();break;}case2:{clrscr();g=creatgraph2();break;}case3:{clrscr();printf("diaplaythegraph;\n");displaygraph(g,n);break;}case4:{clrscr();printf("DFSresult:\n");DFS(g);break;}case5:{clrscr();printf("BFSresult:\n");BFS(g);break;}case6:exit(0);}}}4函數(shù)調(diào)用關系maincreatgraphdisplaygraphBFSDFSBFSsearchDFSsearch initqueuedequeueenqueue四、調(diào)試分析⒈本來想將圖的頂點元素的類型定義為字符型的，但是在運行的時候發(fā)現(xiàn)在輸入頂點數(shù)和弧數(shù)后，總是會在有字符沒有輸入就直接運行下一個語句了，改變了很多的方法，最后只有將頂點的類型定義為才解決了上述的問題。⒉在寫程序的時候，開始creatgraph函數(shù)的部分代碼為for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}g.vexnum=n;g.arcnum=e;總是會有這樣的提示“可能在‘g’定義以前已經(jīng)使用了在creatgraph函數(shù)中”，經(jīng)過多次的調(diào)試，最后代碼改為g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}就解決了問題，但是我還是不清楚原因。3.在編寫B(tài)FSsearch函數(shù)的時候，用指針入隊還是用下標值入隊，由于對指針的掌握不夠，最后選擇了比較容易的用下標值作為隊列的類型int。4.在調(diào)試的時候，選擇選項3、4、5的時候總是沒有執(zhí)行printf語句，最后分別在主函數(shù)和要調(diào)用的函數(shù)中都加上同一printf語句就解決了問題，能夠顯示printf中的信息。5.算法的時空分析 各操作的算法時間復雜度比較合理 initqueue，emptyqueue，enqueue，dequeue，visit為O(1)；creatgraph，displaygraph1，displaygraph2BFSsearch，DFS，DFSsearch，BFS為O(n),注：n為圖的頂點數(shù)。6.本次實驗采用數(shù)據(jù)抽象的程序設計方法，將程序化為三層次結構，設計時思路清晰，使調(diào)試也較順利，各模塊有較好的可重用性。五、用戶手冊⒈本程序的運行環(huán)境為windowsxp操作系統(tǒng)，并且在TC2.0中運行，執(zhí)行文件為Exp8.c；⒉.在輸入有向圖的信息的時候，注意輸入的順序，這關系到頂點的位置，否則就會與你想要的圖就不一樣了。如你的圖為18222021若你輸入的頂點的順序是20,18，21，22則它們對應的數(shù)值的下標為0,1,2，3。因此表示的?。ㄆ瘘c，終點）就應該為（0,2），（1,0），（2,1），（3,0），（3,2），但是弧輸入的順序沒有要求。而創(chuàng)建無向圖的時候就沒有這個要求了，只要輸入能表示該邊的兩個正確的端點即可。3.按任意鍵進入主菜單如圖：注：1：表示創(chuàng)建一個有向圖；2：表示創(chuàng)建一個無向圖；3：表示輸出已創(chuàng)建的圖；4：表示深度優(yōu)先遍歷已有的圖；5：表示廣度優(yōu)先遍歷已有的圖；6：表示退出程序狀態(tài)。4.進入演示程序后，完成編譯，再點擊超級工具集里的中文DOS環(huán)境運行選項，進入DOS環(huán)境中，用戶根據(jù)需求鍵入相應的數(shù)據(jù)，可以看到相應的結果。六、測試結果若想創(chuàng)建一個無向圖（在主菜單選擇2）在主菜單選擇2輸入的圖如圖所示：按任意鍵進入主菜單選擇3，輸出圖為：按任意鍵進入主菜單選擇4，輸出DFS的結果：按任意鍵進入主菜單選擇5，輸出BFS的結果:按任意鍵進入主菜單選擇6，退出程序。七、附錄：源程序#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<string.h>#include<ctype.h>#defineNULL0#defineFALSE0#defineTURE1#definemaxsize100structarcnode{intadjvex;/*該弧所指向的頂點的位置*/intinfo;structarcnode*nextarc;/*指向下一條弧的指針*/};structvexnode{intdata;/*頂點的信息*/structarcnode*firstarc;/*指向第一條依附該頂點的弧的指針*/};structgraph{structvexnode*vexpex;intvexnum,arcnum;/*圖的當前的頂點數(shù)和弧數(shù)*/};/*定義隊列*/structqueue{int*elem;intfront;intrear;};intn;/*圖的頂點數(shù)*/intvisit[100];/*標志數(shù)組*/structqueueQ;/*創(chuàng)建一個空隊列*/structqueueinitqueue(){structqueueq;q.elem=(int*)malloc(maxsize*sizeof(int));if(!q.elem)exit(0);q.front=q.rear=0;returnq;}/*入隊列*/structqueueenqueue(structqueueq,intv){if((q.rear+1)%maxsize==q.front)printf("thequeueisfull?。?！\n");else{q.elem[q.rear]=v;q.rear=(q.rear+1)%maxsize;}returnq;}/*出隊列*/intdequeue(structqueueq){intcur;if(q.rear==q.front){printf("thequeueisnull!!\n");exit(0);}else{cur=q.elem[q.front];q.front=(q.front+1)%maxsize;returncur;}}/*判斷隊列是否為空*/intemptyqueue(structqueueq){if(q.front==q.rear)return1;elsereturn0;}/*創(chuàng)建有向圖*/structgraphcreatgraph1(){inte,i,s,d;inta;structgraphg;structarcnode*p;printf("thenumberofvex(n)andarc(e):");scanf("%d%d",&n,&e);g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;}returng;}/*創(chuàng)建無向圖*/structgraphcreatgraph2(){inte,i,s,d;inta;structgraphg;structarcnode*p,*q;printf("thenumberofvex(n)andarc(e):");scanf("%d%d",&n,&e);g.vexnum=n;g.arcnum=e;for(i=0;i<g.vexnum;i++){printf("di%dvex'sinformation:",i);scanf("%d",&a);g.vexpex[i].data=a;g.vexpex[i].firstarc=NULL;}for(i=0;i<g.arcnum;i++){printf("di%darc'sstart,end:",i+1);scanf("%d%d",&s,&d);p=(structarcnode*)malloc(sizeof(structarcnode));p->adjvex=d;p->info=g.vexpex[d].data;p->nextarc=g.vexpex[s].firstarc;g.vexpex[s].firstarc=p;q=(structarcnode*)malloc(sizeof(structarcnode));q->adjvex=s;q->info=g.vexpex[s].data;q->nextarc=g.vexpex[d].firstarc;g.vexpex[d].firstarc=q;}returng;}/*顯示圖*/voiddisplaygraph(structgraphg,intn){inti;structarcnode*p;printf("diaplaythegraph;\n");for(i=0;i<n;i++){printf("[%d,%d]->",i,g.vexpex[i].data);p=g.vexpex[i].firstarc;while(p!=NULL){printf("(%d,%d)->",p->adjvex,p->info);p=p->nextarc;}printf("^\n");}}/*連通圖廣度優(yōu)先遍歷*/voidBFSsearch(structgraphg,intv){inti;structarcnode*p;Q=initqueue();printf("%5d",g.vexpex[v].data);enqueue(Q,v);visit[v]=TURE;while(!emptyqueue(Q)){i=dequeue(Q);p=g.vexpex[i].firstarc;while(p!=NULL){enqueue(Q,p->adjvex);if(visit[p->adjvex]==FALSE){printf("%5d",p->info);visit[p->adjvex]=TURE;}p=p->nextarc;}}}/*非連通圖廣度優(yōu)先遍歷*/voidBFS(structgraphg){inti;printf("BFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)if(visit[i]==FALSE)BFSsearch(g,i);printf("\n\n");}/*連通圖深度優(yōu)先遍歷*/voidDFSsearch(structgraphg,intv){structarcnode*p;printf("%5d",g.vexpex[v].data);visit[v]=TURE;p=g.vexpex[v].firstarc;while(p!=NULL){if(!visit[p->adjvex])DFSsearch(g,p->adjvex);p=p->nextarc;}}voidDFS(structgraphg)/*非連通圖深度優(yōu)先遍歷*/{inti;printf("DFSresult:\n");for(i=0;i<g.vexnum;i++)visit[i]=FALSE;for(i=0;i<g.vexnum;i++)