【學(xué)生版】實(shí)驗(yàn)六圖基本操作的編程實(shí)現(xiàn)

1、實(shí)驗(yàn)六 圖基本操作的編程實(shí)現(xiàn)【實(shí)驗(yàn)?zāi)康摹繄D基本操作的編程實(shí)現(xiàn)要求：圖基本操作的編程實(shí)現(xiàn)（2學(xué)時(shí)，驗(yàn)證型），掌握?qǐng)D的建立、遍歷、插入、刪除等基本操作的編程實(shí)現(xiàn)，存儲(chǔ)結(jié)構(gòu)可以在順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、聯(lián)合使用多種結(jié)構(gòu)等中任選，也可以全部實(shí)現(xiàn)。也鼓勵(lì)學(xué)生利用基本操作進(jìn)行一些應(yīng)用的程序設(shè)計(jì)。【實(shí)驗(yàn)性質(zhì)】驗(yàn)證性實(shí)驗(yàn)（學(xué)時(shí)數(shù)：2H）【實(shí)驗(yàn)內(nèi)容】編程對(duì)圖進(jìn)行存儲(chǔ)（鄰接矩陣或鄰接表都可以，由學(xué)生自由選擇），之后可以詢問任何兩個(gè)結(jié)點(diǎn)之間是否有通路和路徑數(shù)。設(shè)計(jì)一個(gè)將圖形轉(zhuǎn)成鄰接鏈表的程序。設(shè)計(jì)一個(gè)深度優(yōu)先搜索法來查找圖形的程序。設(shè)計(jì)一個(gè)廣度優(yōu)先搜索法來查找一個(gè)圖形的程序。鼓勵(lì)開發(fā)出難度更高的程序。【思考問題】1.

2、圖的定義和特性？2. 圖的主要存儲(chǔ)結(jié)構(gòu)是什么？是獨(dú)立的某種還是多種數(shù)據(jù)結(jié)構(gòu)的綜合？3. 圖的主要遍歷思路是哪些？4. 舉出圖的應(yīng)用范例？【參考代碼】（一）基礎(chǔ)篇/將一個(gè)圖采用鄰接表存儲(chǔ)，并在該存儲(chǔ)方法上進(jìn)行深度優(yōu)先遍歷/程序構(gòu)思：/用戶鍵盤輸入結(jié)點(diǎn)與各條邊，再將邊轉(zhuǎn)成鄰接鏈表。/然后對(duì)采用鄰接表表示的圖進(jìn)行深度優(yōu)先遍歷。#include<stdio.h>#include <stdlib.h>#define vertexnum 100 /定義最大可輸入的結(jié)點(diǎn)個(gè)數(shù)typedef struct node /定義圖形的頂點(diǎn)結(jié)構(gòu) int vertex; /圖中的頂點(diǎn)信息為數(shù)字 s

3、truct node *next;Graph;Graph headvertexnum; /鄰接表的表頭結(jié)點(diǎn)int Visitedvertexnum; /遍歷記錄void Create_l_Graph(int Vertex1,int Vertex2,int no) /以鄰接鏈表建立圖形 Graph *searchP; /結(jié)點(diǎn)聲明 Graph *New; /新結(jié)點(diǎn)聲明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) New->vertex=Vertex2; New->next=NULL; searchP=&(h

4、eadVertex1); 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 showme

5、nu() /顯示菜單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 DF

6、S(int vertex) /深度優(yōu)先遍歷 Graph *SearchP; /結(jié)點(diǎn)聲明 /標(biāo)記某個(gè)結(jié)點(diǎn)已遍歷過 printf("%d=>",vertex); SearchP=headvertex.next; while(SearchP!=NULL) if( ) /判斷結(jié)點(diǎn)未被遍歷過 /遞歸調(diào)用深度優(yōu)先遍歷函數(shù) SearchP=SearchP->next; /下一個(gè)鄰接點(diǎn) void main() int source; /圖中一條邊的起始頂點(diǎn) int destination; /圖中一條邊的終止頂點(diǎn) int i,j; int vermax; /定義圖中最大的頂點(diǎn)數(shù)

7、 int edgemax; /定義圖中最大的邊數(shù) int choice; int no; while(1)showmenu();printf(" 請(qǐng)輸入你的選擇：");scanf("%d",&choice);fflush(stdin);/清除鍵盤緩沖區(qū)switch(choice) case 1:printf("請(qǐng)輸入圖的類別（有向圖-1，無向圖-0）:"); scanf("%d",&no); printf("請(qǐng)輸入圖中的總頂點(diǎn)數(shù)和邊數(shù):"); scanf("%d%d&q

8、uot;,&vermax,&edgemax); for(i=1;i<vermax;i+)headi.vertex = i;headi.next = NULL; for(i=1;i<=edgemax;i+)printf("請(qǐng)輸入第%d條邊的起點(diǎn)：",i);scanf("%d",&source);printf("請(qǐng)輸入第%d條邊的終點(diǎn)：",i);scanf("%d",&destination);if(source=destination) printf("輸入有誤！

9、n");/出錯(cuò)：自身循環(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("頂點(diǎn)%d:",i); print_l_graph(&headi);/調(diào)用輸出鄰接鏈表數(shù)據(jù) printf("n");

10、system("pause"); system("cls"); break; case 3:for(i=1;i<=vermax;i+) Visitedi=0; printf("請(qǐng)輸入遍歷的起點(diǎn):"); scanf("%d",&source); printf("圖的深度優(yōu)先遍歷結(jié)果為：n"); DFS(source); printf("ENDn"); system("pause"); system("cls"); break

11、; case 4:return; default: printf("你的輸入有誤，請(qǐng)從新輸入！n"); system("pause"); system("cls"); (二)提高篇/將一個(gè)圖采用鄰接表存儲(chǔ)，并在該存儲(chǔ)方法上進(jìn)行深度優(yōu)先遍歷/程序構(gòu)思：/用戶鍵盤輸入結(jié)點(diǎn)與各個(gè)邊，再將邊轉(zhuǎn)成鄰接鏈表。/然后對(duì)采用鄰接表表示的圖進(jìn)行廣度優(yōu)先遍歷。#include<stdio.h>#include <stdlib.h>#define vertexnum 100 /定義最大可輸入的結(jié)點(diǎn)個(gè)數(shù)#define QueueMax

12、 100typedef struct node /定義圖形的頂點(diǎn)結(jié)構(gòu) int vertex; /圖中的頂點(diǎn)信息為數(shù)字 struct node *next;Graph;Graph headvertexnum; /鄰接表的表頭結(jié)點(diǎn)int Visitedvertexnum; /遍歷記錄int Front=-1;int Rear=-1;int QueueQueueMax;int Enqueue(int Vertex) /元素入隊(duì) if (Rear>=QueueMax) /隊(duì)列已滿 return -1; else Rear+; /隊(duì)列尾端指針后移 QueueRear=Vertex; /將值存入隊(duì)列

13、中 return 1; int Dequeue() /元素出隊(duì) if (Front>=Rear) /隊(duì)列已空 return -1; else Front+; /隊(duì)頭指針后移 return QueueFront; void BFS(int Vertex)/廣度優(yōu)先搜索 void Create_l_Graph(int Vertex1,int Vertex2,int no) /以鄰接鏈表建立圖形 Graph *searchP; /結(jié)點(diǎn)聲明 Graph *New; /新結(jié)點(diǎn)聲明 New=(Graph *)malloc(sizeof(struct node); if (New!= NULL ) N

14、ew->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) sea

15、rchP=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->

16、;next; while(searchP!=NULL) printf("%d",searchP->vertex); searchP=searchP->next; printf("n");void main() int source; /圖中一條邊的起始頂點(diǎn) int destination; /圖中一條邊的終止頂點(diǎn) int i,j; int vermax; /定義圖中最大的頂點(diǎn)數(shù) int edgemax; /定義圖中最大的邊數(shù) int choice; int no; while(1)showmenu();printf(" 請(qǐng)輸入你的選

17、擇：");scanf("%d",&choice);fflush(stdin);/清除鍵盤緩沖區(qū)switch(choice) case 1:printf("請(qǐng)輸入圖的類別（有向圖-1，無向圖-0）:"); scanf("%d",&no); printf("請(qǐng)輸入圖中的總頂點(diǎn)數(shù)和邊數(shù):"); scanf("%d%d",&vermax,&edgemax); for(i=1;i<vermax;i+)headi.vertex = i;headi.next =

18、 NULL; for(i=1;i<=edgemax;i+)printf("請(qǐng)輸入第%d條邊的起點(diǎn)：",i);scanf("%d",&source);printf("請(qǐng)輸入第%d條邊的終點(diǎn)：",i);scanf("%d",&destination);if(source=destination) printf("輸入有誤！n");/出錯(cuò)：自身循環(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