數(shù)據(jù)結(jié)構(gòu)：圖子系統(tǒng)

/**題目：編寫按鍵盤輸入的數(shù)據(jù)建立圖的鄰接矩陣存儲*編寫圖的深度優(yōu)先遍歷程序*編寫圖的廣度優(yōu)先遍歷程序*設(shè)計一個選擇式菜單形式如下：*圖子系統(tǒng)**************************************1------更新鄰接矩陣***2------深度優(yōu)先遍歷***3------廣度優(yōu)先遍歷***0------返回**************************************請選擇菜單號（0--3）：*/#include<stdio.h>#include<stdlib.h>#defineGRAPHMAX30#defineQUEUEMAX30typedefstruct//圖的鄰接表的結(jié)構(gòu)體{charvalue[GRAPHMAX];//記錄圖中的點值intdata[GRAPHMAX][GRAPHMAX];//記錄圖中的邊的關(guān)系intn,e;//記錄圖中的點的個數(shù)及邊的個數(shù)}pGraph;typedefstruct//隊列結(jié)構(gòu)體{intqueueData[QUEUEMAX];intfront,rear,count;//隊頭，隊尾，數(shù)目}grQueue;voidcreateCraph(pGraph*G);voidDFSTraverse(pGraph*G);voidBFSTraverse(pGraph*G);voidDFS(pGraph*G,inti);voidBFS(pGraph*G,inti);voidinitQueue(grQueue*Q);intqueueEmpty(grQueue*Q);intqueueFull(grQueue*Q);intoutQueue(grQueue*Q);voidinQueue(grQueue*Q,inti);intvisited[GRAPHMAX];//用于標志性的數(shù)組（全局變量）voidmain(){pGraphG;intchoice,i,j,k=1;printf("建立一個有向圖的鄰接矩陣表示\n");createCraph(&G);printf("已建立一個圖的鄰接矩陣存儲\n\n");for(i=0;i<G.n;i++){for(j=0;j<G.n;j++){printf("%5d",G.data[i][j]);}printf("\n");}while(k){printf("\n圖子系統(tǒng)\n");printf("***********************************\n");printf("*1------更新鄰接矩陣*\n");printf("*2------深度優(yōu)先遍歷*\n");printf("*3------廣度優(yōu)先遍歷*\n");printf("*0------返回*\n");printf("***********************************\n");printf("請選擇菜單號（0--3）：");fflush(stdin);scanf("%d",&choice);switch(choice){case1:createCraph(&G);printf("圖的鄰接矩陣存儲成功\n\n");break;case2:DFSTraverse(&G);break;case3:BFSTraverse(&G);break;case0:k=0;break;default:printf("輸入錯誤，請重新輸入。");getchar();k=1;break;}}}voidcreateCraph(pGraph*G)//建立鄰接表{inti,j,k;charch1,ch2;printf("請輸入定點數(shù)，邊數(shù)（格式如3,3）:");scanf("%d,%d",&(G->n),&(G->e));for(i=0;i<G->n;i++)//輸入頂點值{getchar();printf("請輸入第%d頂點的值：",i+1);scanf("%c",&(G->value[i]));}//初始化鄰接表for(i=0;i<G->n;i++){for(j=0;j<G->n;j++){G->data[i][j]=0;}}for(k=0;k<G->e;k++){getchar();printf("請輸入第%d條邊的頂點值（格式4,5）：",k+1);scanf("%c,%c",&ch1,&ch2);//構(gòu)建鄰接表for(i=0;i<G->n;i++){if(ch1==G->value[i]){for(j=0;j<G->n;j++){if(ch2==G->value[j]){G->data[i][j]=1;}}}}}}//深度遍歷voidDFSTraverse(pGraph*G){inti;for(i=0;i<G->n;i++){visited[i]=0;}for(i=0;i<G->n;i++){if(!visited[i]){DFS(G,i);}}}//廣度遍歷voidBFSTraverse(pGraph*G){inti;for(i=0;i<G->n;i++){visited[i]=0;}for(i=0;i<G->n;i++){if(!visited[i]){BFS(G,i);}}}voidDFS(pGraph*G,inti){intj;printf("深度優(yōu)先遍歷序列：%c\n",G->value[i]);visited[i]=1;for(j=0;j<G->n;j++){if(G->data[i][j]==1&&!visited[j]){DFS(G,j);}}}voidBFS(pGraph*G,inti){intk,j;grQueueQ;initQueue(&Q);//初始化visited[i]=1;inQueue(&Q,i);while(!queueEmpty(&Q)){k=outQueue(&Q);printf("廣度優(yōu)先遍歷序列：%c\n",G->value[k]);for(j=0;j<G->n;j++){if(G->data[k][j]==1&&!visited[j]){visited[j]=1;inQueue(&Q,j);}}}}voidinitQueue(grQueue*Q)//隊列初始化{Q->front=Q->rear=0;Q->count=0;}intqueueEmpty(grQueue*Q)//隊列判空{(diào)returnQ->count==0;}intqueueFull(grQueue*Q)//隊列判滿{returnQ->count==QUEUEMAX;}intoutQueue(grQueue*Q)//出隊{inttemp;if(queueEmpty(Q)){printf("隊列為空。");return-1;}else{temp=Q->queueData[Q->front];//出隊的元素Q->count--;Q->front=(Q->front+1)%QUEUEMAX;returntemp;}}voidinQueue(grQueue*Q,i