數(shù)據(jù)結(jié)構(gòu)實驗-圖實驗報告

數(shù)據(jù)結(jié)構(gòu)實驗報告

目的要求１．掌握圖的存儲思想及其存儲實現(xiàn)..２．掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)..３．掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)..實驗內(nèi)容１．鍵盤輸入數(shù)據(jù);建立一個有向圖的鄰接表..２．輸出該鄰接表..3．在有向圖的鄰接表的基礎(chǔ)上計算各頂點的度;并輸出..4．以有向圖的5．采用鄰接表存儲實現(xiàn)6．采用鄰接表存儲實現(xiàn)7．在主函數(shù)中設(shè)計一個簡單的鄰接表為基礎(chǔ)實現(xiàn)輸出它的拓?fù)渑判蛐蛄?.無向圖的深度優(yōu)先遞歸遍歷..無向圖的廣度優(yōu)先遍歷..菜單;分別調(diào)試上述算法..源程序：主程序的頭文件：隊列#include<stdio.h>#include<stdlib.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintQElemType;typedefstructQNode{//隊的操作QElemTypedata;structQNode*next;}QNode;*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;voidInitQueueLinkQueue&Q{//初始化隊列Q.front=Q.rear=QueuePtrmallocsizeofQNode;ifQ.frontexitOVERFLOW;//存儲分配失敗Q.front->next=NULL;}intEnQueueLinkQueue&Q;QElemTypee//插入元素e為Q的新的隊尾元素{QueuePtrp;p=QueuePtrmallocsizeofQNode;ifpexitOVERFLOW;p->data=e;

p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}intDeQueueLinkQueue&Q;QElemType&e//刪除Q的隊頭元素;用e返回其值{ifQ.front==Q.rearreturnERROR;QueuePtrp;p=Q.front->next;e=p->data;Q.front->next=p->next;ifQ.rear==pQ.rear=Q.front;freep;returnOK;}主程序：#include<stdio.h>#include<stdlib.h>#include"duilie.h"#defineTRUE1#defineFALSE0#defineStatusint#defineMAX_VERTEX_NUM8/*頂點最大個數(shù)#defineVertexTypechar/*頂點元素類型enumBOOlean{False;True};*/*/BOOleanvisitedMAX_VERTEX_NUM;//全局變量——訪問標(biāo)志數(shù)組typedefstructArcNode{intadjvex;structArcNode*nextarc;intweight;/*邊的權(quán)*/}ArcNode;/*表結(jié)點*/typedefstructVNode{intdegree;indegree;/*頂點的度;入度*/VertexTypedata;ArcNode*firstarc;}VNode/*頭結(jié)點*/;AdjListMAX_VERTEX_NUM;typedefstruct{AdjListvertices;intvexnum;arcnum;/*頂點的實際數(shù);邊的實際數(shù)*/}ALGraph;//建立圖的鄰接表voidcreat_linkALGraph*G{inti;j;ArcNode*s;

printf"請依次輸入頂點數(shù)、邊數(shù)：";scanf"%d%d";&G->vexnum;&G->arcnum;fori=0;i<G->vexnum;i++{G->verticesi.data='A'+i;G->verticesi.firstarc=NULL;}fori=0;i<G->vexnum;{printf"請輸入頂點的數(shù)組坐標(biāo)若退出;請輸入-1：";scanf"%d";&i;ifi==-1break;printf"請輸入頂點所指向下一個頂點的數(shù)組坐標(biāo)：";scanf"%d";&j;s=ArcNode*mallocsizeofArcNode;s->adjvex=j;s->nextarc=G->verticesi.firstarc;G->verticesi.firstarc=s;}}//輸出鄰接表voidvisitALGraphG{inti;ArcNode*p;printf"%4s%6s%18s\n";"NO";"data";"adjvexsofarcs";fori=0;i<G.vexnum;i++{printf"%4d%5c";i;G.verticesi.data;forp=G.verticesi.firstarc;p;p=p->nextarcprintf"%3d";p->adjvex;printf"\n";}}//計算各頂點的度及入度voidcacuALGraph*G{ArcNode*p;inti;fori=0;i<G->vexnum;i++{G->verticesi.degree=0;G->verticesi.indegree=0;}//度與初度初始化為零fori=0;i<G->vexnum;i++forp=G->verticesi.firstarc;p;p=p->nextarc{G->verticesi.degree++;G->verticesp->adjvex.degree++;G->verticesp->adjvex.indegree++;}

}voidprint_degreeALGraphG{inti;printf"\nNomdatadegreeindegree\n";fori=0;i<G.vexnum;i++printf"\n%4d%5c%7d%8d";i;G.verticesi.data;G.verticesi.degree;G.verticesi.indegree;printf"\n";}//拓?fù)渑判騍tatusTopologiSortALGraphG{inti;count;top=0;stack50;ArcNode*p;cacu&G;print_degreeG;printf"\nTopologiSortis\n";fori=0;i<G.vexnum;i++ifG.verticesi.indegreestacktop++=i;count=0;whiletop=0{i=stack--top;ifcount==0printf"%c";G.verticesi.data;elseprintf"-->%c";G.verticesi.data;count++;forp=G.verticesi.firstarc;p;p=p->nextarcif--G.verticesp->adjvex.indegreestacktop++=p->adjvex;}ifcount<G.vexnumreturnFALSE;elsereturnTRUE;}//在圖G中尋找第v個頂點的第一個鄰接頂點intFirstAdjVexALGraphG;intv{ifG.verticesv.firstarcreturn0;elsereturnG.verticesv.firstarc->adjvex;}//在圖G中尋找第v個頂點的相對于u的下一個鄰接頂點intNextAdjVexALGraphG;intv;intu{ArcNode*p;p=G.verticesv.firstarc;whilep->adjvex=up=p->nextarc;//在頂點v的弧鏈中找到頂點uifp->nextarc==NULLreturn0;//若已是最后一個頂點;返回0

elsereturnp->nextarc->adjvex;//返回下一個鄰接頂點的序號}//采用鄰接表存儲實現(xiàn)無向圖的深度優(yōu)先遞歸遍歷voidDFSALGraphG;inti{intw;visitedi=True;//訪問第i個頂點printf"%d->";i;forw=FirstAdjVexG;i;w;w=NextAdjVexG;i;wifvisitedwDFSG;w;//對尚未訪問的鄰接頂點w調(diào)用DFS}voidDFSTraverseALGraphG{inti;printf"DFSTraverse:";fori=0;i<G.vexnum;i++visitedi=False;//訪問標(biāo)志數(shù)組初始化fori=0;i<G.vexnum;i++ifvisitediDFSG;i;//對尚未訪問的頂點調(diào)用DFS}//按廣度優(yōu)先非遞歸的遍歷圖G;使用輔助隊列Q和訪問標(biāo)志數(shù)組visitedvoidBFSTraverseALGraphG{inti;u;w;LinkQueueQ;printf"BFSTreverse:";fori=0;i<G.vexnum;i++visitedi=False;//訪問標(biāo)志數(shù)組初始化InitQueueQ;//初始化隊列fori=0;i<G.vexnum;i++ifvisitedi{visitedi=True;//訪問頂點iprintf"%d->";i;EnQueueQ;i;//將序號i入隊列whileQ.front==Q.rear//若隊列不空;繼續(xù){DeQueueQ;u;//將隊頭元素出隊列并置為uforw=FirstAdjVexG;u;w;w=NextAdjVexG;u;wifvisitedw//對u的尚未訪問的鄰接頂點w進(jìn)行訪問并入隊列{visitedw=True;printf"%d->";w;EnQueueQ;w;}}}}voidmain{ALGraphG;

intselect;printf"do{圖的有關(guān)操作實驗\n";printf"\n1創(chuàng)建printf"3.輸出該有向圖的度和入度printf"5.創(chuàng)建一個無向圖的鄰接表一個有向圖的鄰接表2輸出該鄰接表\n";4.輸出該有拓?fù)渑判蛐蛄衆(zhòng)n";6.深度優(yōu)先遞歸遍歷該無向圖\n";0.退出向圖printf"7.廣度優(yōu)先遍歷該無向圖printf"請輸入選擇：";scanf"%d";&select;switchselect{\n";case1:printf"\n創(chuàng)建一個有向圖的鄰接表：\n";creat_link&G;break;case2:printf"\n輸出該鄰接表：\n";visitG;break;case3:printf"\n輸出該有向圖的度和入度：\n";cacu&G;print_degreeG;break;case4:printf"\n輸出該有向圖拓?fù)渑判蛐蛄校篭n";ifTopologiSortGprintf"Toposortisnotsuccess";break;case5:printf"\n創(chuàng)建一個無向圖的鄰接表:\n";creat_link&G;break;case6:printf"\n深度優(yōu)先遞歸遍歷該無向圖:\n";DFSTraverseG;break;case7:printf"\n廣度優(yōu)先遍歷該無向圖：\n";BFSTraverseG;break;case0:break;default:printf"輸入選項錯誤重新輸入\n";}

}2.創(chuàng)建一個有向圖的領(lǐng)接表4.在有向圖的鄰接表的基礎(chǔ)上計算各頂點的度;并輸出..5.輸出它的拓?fù)渑判蛐蛄?.輸出所建無向圖的鄰接表7.