【學生版】實驗六 圖基本操作的編程實現(xiàn).doc

實驗六 圖基本操作的編程實現(xiàn)【實驗目的】圖基本操作的編程實現(xiàn)要求：圖基本操作的編程實現(xiàn)（2學時，驗證型），掌握圖的建立、遍歷、插入、刪除等基本操作的編程實現(xiàn)，存儲結(jié)構(gòu)可以在順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、聯(lián)合使用多種結(jié)構(gòu)等中任選，也可以全部實現(xiàn)。也鼓勵學生利用基本操作進行一些應用的程序設計?！緦嶒炐再|(zhì)】驗證性實驗（學時數(shù)：2H）【實驗內(nèi)容】編程對圖進行存儲（鄰接矩陣或鄰接表都可以，由學生自由選擇），之后可以詢問任何兩個結(jié)點之間是否有通路和路徑數(shù)。設計一個將圖形轉(zhuǎn)成鄰接鏈表的程序。設計一個深度優(yōu)先搜索法來查找圖形的程序。設計一個廣度優(yōu)先搜索法來查找一個圖形的程序。鼓勵開發(fā)出難度更高的程序?！舅伎紗栴}】1. 圖的定義和特性？2. 圖的主要存儲結(jié)構(gòu)是什么？是獨立的某種還是多種數(shù)據(jù)結(jié)構(gòu)的綜合？3. 圖的主要遍歷思路是哪些？4. 舉出圖的應用范例？【參考代碼】（一）基礎篇/將一個圖采用鄰接表存儲，并在該存儲方法上進行深度優(yōu)先遍歷/程序構(gòu)思：/用戶鍵盤輸入結(jié)點與各條邊，再將邊轉(zhuǎn)成鄰接鏈表。/然后對采用鄰接表表示的圖進行深度優(yōu)先遍歷。#include#include #define vertexnum 100 /定義最大可輸入的結(jié)點個數(shù)typedef struct node /定義圖形的頂點結(jié)構(gòu) int vertex; /圖中的頂點信息為數(shù)字 struct node *next;Graph;Graph headvertexnum; /鄰接表的表頭結(jié)點int Visitedvertexnum; /遍歷記錄void Create_l_Graph(int Vertex1,int Vertex2,int no) /以鄰接鏈表建立圖形 Graph *searchP; /結(jié)點聲明 Graph *New; /新結(jié)點聲明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New-vertex=Vertex2; New-next=NULL; searchP=&(headVertex1); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New-vertex=Vertex1; New-next=NULL; searchP=&(headVertex2); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New; void showmenu() /顯示菜單printf( 歡迎使用圖的操作演示軟件n);printf(t1、創(chuàng)建圖的鄰接表n);printf(t2、圖的輸出n);printf(t3、圖的深度優(yōu)先遍歷n);printf(t4、退出程序n);void print_l_graph(Graph *head) /輸出鄰接鏈表的數(shù)據(jù) Graph *searchP; searchP=head-next; while(searchP!=NULL) printf(n);void DFS(int vertex) /深度優(yōu)先遍歷 Graph *SearchP; /結(jié)點聲明 /標記某個結(jié)點已遍歷過 printf(%d=,vertex); SearchP=headvertex.next; while(SearchP!=NULL) if( ) /判斷結(jié)點未被遍歷過 /遞歸調(diào)用深度優(yōu)先遍歷函數(shù) SearchP=SearchP-next; /下一個鄰接點 void main() int source; /圖中一條邊的起始頂點 int destination; /圖中一條邊的終止頂點 int i,j; int vermax; /定義圖中最大的頂點數(shù) int edgemax; /定義圖中最大的邊數(shù) int choice; int no; while(1)showmenu();printf( 請輸入你的選擇：);scanf(%d,&choice);fflush(stdin);/清除鍵盤緩沖區(qū)switch(choice) case 1:printf(請輸入圖的類別（有向圖-1，無向圖-0）:); scanf(%d,&no); printf(請輸入圖中的總頂點數(shù)和邊數(shù):); scanf(%d%d,&vermax,&edgemax); for(i=1;ivermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i=edgemax;i+)printf(請輸入第%d條邊的起點：,i);scanf(%d,&source);printf(請輸入第%d條邊的終點：,i);scanf(%d,&destination);if(source=destination) printf(輸入有誤！n);/出錯：自身循環(huán) else /調(diào)用建立鄰接鏈表 Create_l_Graph(source,destination,no); printf(圖創(chuàng)建成功，按任意鍵繼續(xù)n); getch(); system(cls); break; case 2:printf(圖的鄰接表如下：n); for(i=1;i=vermax;i+)printf(頂點%d:,i); print_l_graph(&headi);/調(diào)用輸出鄰接鏈表數(shù)據(jù) printf(n); system(pause); system(cls); break; case 3:for(i=1;i=vermax;i+) Visitedi=0; printf(請輸入遍歷的起點:); scanf(%d,&source); printf(圖的深度優(yōu)先遍歷結(jié)果為：n); DFS(source); printf(ENDn); system(pause); system(cls); break; case 4:return; default: printf(你的輸入有誤，請從新輸入！n); system(pause); system(cls); (二)提高篇/將一個圖采用鄰接表存儲，并在該存儲方法上進行深度優(yōu)先遍歷/程序構(gòu)思：/用戶鍵盤輸入結(jié)點與各個邊，再將邊轉(zhuǎn)成鄰接鏈表。/然后對采用鄰接表表示的圖進行廣度優(yōu)先遍歷。#include#include #define vertexnum 100 /定義最大可輸入的結(jié)點個數(shù)#define QueueMax 100typedef struct node /定義圖形的頂點結(jié)構(gòu) int vertex; /圖中的頂點信息為數(shù)字 struct node *next;Graph;Graph headvertexnum; /鄰接表的表頭結(jié)點int Visitedvertexnum; /遍歷記錄int Front=-1;int Rear=-1;int QueueQueueMax;int Enqueue(int Vertex) /元素入隊 if (Rear=QueueMax) /隊列已滿 return -1; else Rear+; /隊列尾端指針后移 QueueRear=Vertex; /將值存入隊列中 return 1; int Dequeue() /元素出隊 if (Front=Rear) /隊列已空 return -1; else Front+; /隊頭指針后移 return QueueFront; void BFS(int Vertex)/廣度優(yōu)先搜索 void Create_l_Graph(int Vertex1,int Vertex2,int no) /以鄰接鏈表建立圖形 Graph *searchP; /結(jié)點聲明 Graph *New; /新結(jié)點聲明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New-vertex=Vertex2; New-next=NULL; searchP=&(headVertex1); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New;if(no=0)New=(Graph *)malloc(sizeof(struct node);New-vertex=Vertex1; New-next=NULL; searchP=&(headVertex2); while(searchP-next!=NULL) searchP=searchP-next; searchP-next =New; void showmenu() /顯示菜單printf( 歡迎使用圖的操作演示軟件n);printf(t1、創(chuàng)建圖的鄰接表n);printf(t2、圖的輸出n);printf(t3、圖的廣度優(yōu)先遍歷n);printf(t4、退出程序n);void print_l_graph(Graph *head) /輸出鄰接鏈表的數(shù)據(jù) Graph *searchP; searchP=head-next; while(searchP!=NULL) printf(%d,searchP-vertex); searchP=searchP-next; printf(n);void main() int source; /圖中一條邊的起始頂點 int destination; /圖中一條邊的終止頂點 int i,j; int vermax; /定義圖中最大的頂點數(shù) int edgemax; /定義圖中最大的邊數(shù) int choice; int no; while(1)showmenu();printf( 請輸入你的選擇：);scanf(%d,&choice);fflush(stdin);/清除鍵盤緩沖區(qū)switch(choice) case 1:printf(請輸入圖的類別（有向圖-1，無向圖-0）:); scanf(%d,&no); printf(請輸入圖中的總頂點數(shù)和邊數(shù):); scanf(%d%d,&vermax,&edgemax); for(i=1;ivermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i=edgemax;i+)printf(請輸入第%d條邊的起點：,i);scanf(%d,&source);printf(請輸入第%d條邊的終點：,i);scanf(%d,&destination);if(source=destination) printf(輸入有誤！n);/出錯：自身循環(huán) else /調(diào)用建立鄰接鏈表 Create_l_Graph(source,destination,no); printf(圖創(chuàng)建成功，按任意鍵繼續(xù)n); getch(); system(cls); break; case 2:printf(圖的鄰接表如下：n); for(i=1;i=vermax;i+)printf(頂點%d:,i); print_l_graph(&headi);/調(diào)用輸出鄰接鏈表數(shù)據(jù) printf(n); system(pause); system(cls); break; case 3:for(i=1;i=vermax;i+) Visitedi=0; printf(請輸入遍歷的起點:); scanf(%d,&source); pri