實驗報告

20010 – 2011 學年第 1 學期 任課老師： 課程名稱 實驗題目 實驗目的、要求 實驗目的 數(shù)據(jù)結(jié)構(gòu) 圖 班級 實驗時間 座號 姓名 實驗日期： 3—11 提交日期： 3—12 1．熟悉圖的存儲結(jié)構(gòu)； 2．熟悉圖的創(chuàng)建操作； 3．熟悉圖的遍歷操作。 實驗設計內(nèi)容 1

1．理解實現(xiàn)無向圖鄰接表的創(chuàng)建的算法，理解實現(xiàn)無向圖的深度優(yōu)先遍歷的算法；轉(zhuǎn)換成程序并上機實現(xiàn)，并按要求撰寫實驗報告；以下例子作為一個測試用例. 例 a b c d G2 e 深度遍歷：a? b ?c ? d ?e 2．實現(xiàn)無向圖鄰接矩陣的創(chuàng)建，實現(xiàn)無向圖鄰接矩陣方式存儲的深度優(yōu)先遍歷的算法，轉(zhuǎn)換成程序并上機實現(xiàn)； 3．（選做）無向圖鄰接表存儲方式的廣度優(yōu)先遍歷，轉(zhuǎn)換成程序并上機實現(xiàn)； 1． 二、 實驗報告 1.鄰接表 #include #include #define MaxVertexNum 100 typedef enum{FALSE,TRUE}Boolean; Boolean visited[MaxVertexNum]; typedef char VertexType; typedef struct node { /*邊表結(jié)點*/ int adjvex; /*鄰接點域*/ struct node *nextedge; /*鏈域 */ } EdgeNode; typedef struct vnode { /*頂點表結(jié)點*/ VertexType vertex; /*頂點域*/ EdgeNode *firstedge; /*邊表頭指針*/ }VertexNode; typedef VertexNode AdjList[MaxVertexNum];/*AdjList是鄰接表類型*/ 2

typedef struct { AdjList adjlist;/*鄰接表*/ int n,e;/*圖中當前頂點數(shù)和邊數(shù)*/ int kind; /* 圖的種類標志*/ } ALGraph; void CreateALGraph(ALGraph *G1) {/*建立無向圖的鄰接表表示 */ int i,j,k; EdgeNode *s; printf(\"qing shu ru dingdian shu he bian shu:\\n\"); scanf(\"%d %d\讀入頂點數(shù)和邊數(shù)*/ fflush(stdin); printf(\"input dingdian information:\\n\"); for(i=0;in;i++) { /*建立頂點表*/ /*scanf(\"%c\ G1->adjlist[i].vertex=getchar(); /*讀入頂點信息*/ G1->adjlist[i].firstedge=NULL;/*邊表置為空表*/ } printf(\"input (vi,vj)dingdian duixuhao:\\n\"); for(k=0;ke;k++) { /*建立邊表*/ scanf(\"%d %d\讀入邊(vi，vj)的頂點對序號*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成邊表結(jié)點*/ s->adjvex=j; /*鄰接點序號為j*/ s->nextedge=G1->adjlist[i].firstedge; G1->adjlist[i].firstedge=s; /*將新結(jié)點*s插入頂點vi的邊表頭部*/ s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adjvex=i; /*鄰接點序號為i*/ s->nextedge=G1->adjlist[j].firstedge; G1->adjlist[j].firstedge=s; /*將新結(jié)點*s插入頂點vj的邊表頭部*/ }/*end for?*/ }/* end CreateALGraph */ void DFS(ALGraph *G1,int i) { EdgeNode *p; printf(\"visit vertex:%c\\n\ visited[i]=TRUE; p=G1->adjlist[i].firstedge; while(p) { if(!visited[p->adjvex]) 3

DFS(G1,p->adjvex); p=p->nextedge; } } void DFSTraverse(ALGraph *G1) /* 深度優(yōu)先遍歷*/ { int i; for(i=0;in;i++) visited[i]=FALSE; /*訪問標志數(shù)組初始化*/ for(i=0;in;i++) if(!visited[i]) DFS(G1,i); } void main() { ALGraph *G; printf(\"Network Engeering 0902 zhangbinghuang NO.10\\n\"); CreateALGraph(G); DFSTraverse(G); } 2.鄰接矩陣 #include #include #define MaxVertexNum 100 typedef char VertexType;/*頂點類型應由用戶定義*/ typedef int EdgeType;/*邊上的權(quán)值類型應由用戶定義*/ typedef struct { VertexType vexs[MaxVertexNum]; /*頂點表 */ EdgeType edges[MaxVertexNum][MaxVertexNum]; /*鄰接矩陣，可看作邊表*/ int n,e; /*圖中當前的頂點數(shù)和邊數(shù)*/ }MGraph; void CreateMGraph(MGraph *G1) { /*建立無向網(wǎng)的鄰接矩陣表示*/ int i,j,k,w; printf(\"qing shu ru dingdian shu he bian shu:\\n\"); scanf(\"%d%d\輸入頂點數(shù)和邊數(shù)*/ fflush(stdin); printf(\"input dingdian:\\n\"); 4

for(i=0;in;i++) /*讀人頂點信息，建立頂點表*/ G1->vexs[i]=getchar(); fflush(stdin); for(i=0;in;i++) for(j=0; jn;j++) G1->edges[i][j]=0; /*鄰接矩陣初始化*/ printf(\"input duiying dingdian de bian and quan: \\n \"); for(k=0;ke;k++) {/*讀入e條邊，建立鄰接矩陣*/ scanf(\"%d%d%d\輸入邊(vi,vj)上的權(quán)w */ G1->edges[i-1][j-1]=w; G1->edges[j-1][i-1]=w; } }/*Create_MGraph */ typedef enum{FALSE,TRUE}Boolean; Boolean visited[MaxVertexNum]; void DFSM(MGraph *G1,int i) { int j; printf(\"visit vertex:%c\\n\ visited[i]=TRUE; for(j=0;jn;j++) if(G1->edges[i][j]==1&&!visited[j]) DFSM(G1,j); } void DFSTraverse(MGraph *G1) /* 深度優(yōu)先遍歷*/ { int i; for (i=0;i< G1->n;++i) visited[i] = FALSE; /*訪問標志數(shù)組初始化*/ for (i=0;in;++i) if(!visited[i]) DFSM(G1, i); } void main() { MGraph *G; printf(\"Network Engeering 0902 zhangbinghuang NO.10\\n\"); CreateMGraph(G); DFSTraverse(G); } 5

調(diào)試過程記錄 實驗結(jié)果記錄以及與預期結(jié)果比較以及分析 1.鄰接表 2.鄰接矩陣 6

總結(jié)以及心得體會 教師評閱意見 教師： 年 月 日 填寫內(nèi)容時，可把表格擴大。實驗的源程序代碼（要有注釋）附在表后。

7