數(shù)據(jù)結構課程設計報告模板-圖的遍歷

PAGEPAGE18數(shù)據(jù)結構課程設計報告書設計題目圖遍歷的演示姓名專業(yè)班級學號指導教師成績評語2014年6月20日目錄目錄 1一、功能需求 1（一）原始數(shù)據(jù) 1（二）系統(tǒng)功能 1三、程序總體設計 2（一）數(shù)據(jù)結構 2(二)函數(shù)原形清單 2（三）程序總體框架 4（四）詳細代碼 4四、程序清單 15五、總結 17一、功能需求 以鄰接多重表為存儲結構，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的頂點為起點，分別輸出每種遍歷下的頂點訪問序列和相應生成樹的邊集。二、系統(tǒng)功能和原始數(shù)據(jù)（一）原始數(shù)據(jù) 設圖的頂點不超過20個，每個頂點用一個編號表示（如果一個圖有n個頂點，則它們的編號分別為1,2，…，n）。通過輸入圖的全部邊輸入一個圖，每條邊為一對整數(shù)，可以對邊的輸入順序作某種限制。注意，生成樹的邊是有向邊，端點順序不能顛倒。（二）系統(tǒng)功能 1.創(chuàng)建無向圖 2.打印無向圖 3.深度優(yōu)先搜索 4.廣度優(yōu)先搜索三、程序總體設計（一）數(shù)據(jù)結構typedefstructEBox{ intmark;//訪問標記,1代表已訪問，0代表未訪問 intivex,jvex;//該邊依附的兩個頂點的位置 structEBox*ilink,*jlink;//分別指向依附這兩個頂點的下一條邊 //InfoType*info;//該邊信息指針}EBox;typedefstructVexBox{ VertexTypedata; EBox*firstedge;//指向第一條依附該頂點的邊}VexBox;typedefstruct{ VexBoxadjmulist[NUM]; intvexnum,edgenum;//無向圖的當前頂點數(shù)和邊數(shù)}AMLGraph;//隊列的定義typedefintQElemType;typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront,rear;}LinkQueue;(二)函數(shù)原形清單 intLocateVex(AMLGraphG,VertexTypeu) //尋找輸入的數(shù)據(jù)在圖中的位置,若不存在則返回-1 intCreateGraph(AMLGraph&G) //采用鄰接多重表存儲表示，構造無向圖G VertexType*GetVex(AMLGraphG,intv)//返回V的值 intFirstAdjVex(AMLGraphG,VertexTypev)//返回V的第一個鄰接點的序號，若沒有則返回-1 intNextAdjVex(AMLGraphG,VertexTypev,VertexTypew)//返回V的(相對于W)的下一個鄰接結點的序號，若W是V的最后一個鄰接結點， 則返回-1 voidDFS(AMLGraphG,intv)//深度優(yōu)先搜索//深度優(yōu)先遍歷圖 voidDFSTraverse(AMLGraphG,int(*Visit)(VertexType)) intInitQueue(LinkQueue*Q)//隊列的初始化 intQueueEmpty(LinkQueueQ)//判斷隊列是否為空，為空則返回1，否則返回0 intEnQueue(LinkQueue*Q,QElemTypee)//向隊列中插入元素 intDeQueue(LinkQueue*Q,QElemType*e)//若隊列不為空，則刪除對頭元素，并返回1；否則返回0 voidBFSTraverse(AMLGraphG,int(*Visit)(VertexType))//廣度優(yōu)先非遞歸遍歷圖G voidMarkUnVisited(AMLGraphG)//把邊的訪問標記設置為0，即未被訪問 voidDisplay(AMLGraphG)//顯示構造的無向圖(包括定點數(shù)、頂點、邊數(shù)、邊)（三）程序總體框架開始開始創(chuàng)建無向圖打印無向圖深度優(yōu)先搜索創(chuàng)建無向圖結束（四）詳細代碼#include<iostream>usingnamespacestd;//無向圖的鄰接多重表存儲結構的定義constintNUM=20;constintData_Num=2;//每個頂點所表示的數(shù)據(jù)typedefcharVertexType[Data_Num];typedefstructEBox{ intmark;//訪問標記,1代表已訪問，0代表未訪問 intivex,jvex;//該邊依附的兩個頂點的位置 structEBox*ilink,*jlink;//分別指向依附這兩個頂點的下一條邊}EBox;typedefstructVexBox{ VertexTypedata; EBox*firstedge;//指向第一條依附該頂點的邊}VexBox;typedefstruct{ VexBoxadjmulist[NUM]; intvexnum,edgenum;//無向圖的當前頂點數(shù)和邊數(shù)}AMLGraph;//隊列的定義typedefintQElemType;typedefstructQNode{ QElemTypedata; structQNode*next;}QNode,*QueuePtr;typedefstruct{ QueuePtrfront,rear;}LinkQueue;//尋找輸入的數(shù)據(jù)在圖中的位置,若不存在則返回-1intLocateVex(AMLGraphG,VertexTypeu){ inti; for(i=0;i<G.vexnum;i++) if(strcmp(u,G.adjmulist[i].data)==0) returni; return-1;}//采用鄰接多重表存儲表示，構造無向圖GintCreateGraph(AMLGraph&G){ cout<<"請輸入圖的頂點數(shù)、邊數(shù):"; cin>>G.vexnum;//輸入圖當前的頂點數(shù) cin>>G.edgenum;//輸入圖當前的邊數(shù) cout<<"請輸入每個頂點所對應的值:"<<endl; for(inti=0;i<G.vexnum;i++) { cin>>G.adjmulist[i].data;//輸入頂點值 G.adjmulist[i].firstedge=NULL;//初始化指針 } VertexTypev1,v2; EBox*p; intj;//每條弧所關聯(lián)的兩個結點 for(intk=0;k<G.edgenum;k++) { cout<<"請輸入第"<<k<<"邊的始點和終點:"; cin>>v1;cin>>v2; i=LocateVex(G,v1);j=LocateVex(G,v2);//確定v1和v2在圖G中的位置 p=(EBox*)malloc(sizeof(EBox)); //對弧結點進行賦值 (*p).mark=0; (*p).ivex=i; (*p).jvex=j; (*p).ilink=G.adjmulist[i].firstedge; (*p).jlink=G.adjmulist[j].firstedge; G.adjmulist[i].firstedge=G.adjmulist[j].firstedge=p; } return1;}//返回V的值VertexType*GetVex(AMLGraphG,intv){ if(v>G.vexnum||v<0) exit(0); return&G.adjmulist[v].data;}//返回V的第一個鄰接點的序號，若沒有則返回-1intFirstAdjVex(AMLGraphG,VertexTypev){ inti; i=LocateVex(G,v); if(i<0) return-1; if(G.adjmulist[i].firstedge)//V有鄰接結點 if(G.adjmulist[i].firstedge->ivex==i) returnG.adjmulist[i].firstedge->jvex; else returnG.adjmulist[i].firstedge->ivex; else return-1;}//返回V的(相對于W)的下一個鄰接結點的序號，若W是V的最后一個鄰接結點，則返回-1intNextAdjVex(AMLGraphG,VertexTypev,VertexTypew){ inti,j; EBox*p; i=LocateVex(G,v); j=LocateVex(G,w); if(i<0||j<0) return-1; p=G.adjmulist[i].firstedge; while(p) if(p->ivex==i&&p->jvex!=j) p=p->ilink; elseif(p->jvex==i&&p->ivex!=j) p=p->jlink; else break; if(p&&p->ivex==i&&p->jvex==j) { p=p->ilink; if(p&&p->ivex==i) returnp->jvex; elseif(p&&p->jvex==i) returnp->jvex; } if(p&&p->ivex==j&&p->jvex==i) { p=p->jlink; if(p&&p->ivex==i) returnp->jvex; elseif(p&&p->jvex==i) returnp->jvex; } return-1; }//隊列的操作intvisite[NUM];//訪問標志數(shù)組int(*VisitFunc)(VertexTypev);voidDFS(AMLGraphG,intv){ intj; EBox*p; VisitFunc(G.adjmulist[v].data); visite[v]=1;//該頂點已經被訪問 p=G.adjmulist[v].firstedge; while(p) { j=p->ivex==v?p->jvex:p->ivex; if(!visite[j]) DFS(G,j); p=p->ivex==v?p->ilink:p->jlink; }}//深度優(yōu)先遍歷圖voidDFSTraverse(AMLGraphG,int(*Visit)(VertexType)){ intv,start; VisitFunc=Visit; for(v=0;v<G.vexnum;v++) visite[v]=0; cout<<"請輸入你要開始進行查找的位置："; cin>>start; cout<<"按廣深度優(yōu)先搜索的結果是:"<<endl; for(v=start;v<G.vexnum;v++) { if(v>=G.vexnum) { for(v=0;v<G.vexnum;v++) { if(!visite[v]) DFS(G,v); }//內層for }//if else { if(!visite[v]) DFS(G,v); }//else }//外層for cout<<"\b\b\b"; cout<<endl;}//隊列的初始化intInitQueue(LinkQueue*Q){ (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if(!(*Q).front) exit(0); (*Q).front->next=NULL; return1;}//判斷隊列是否為空，為空則返回1，否則返回0intQueueEmpty(LinkQueueQ){ if(Q.front==Q.rear) return1; else return0;}//向隊列中插入元素intEnQueue(LinkQueue*Q,QElemTypee){ QueuePtrp=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(0); p->data=e; p->next=NULL; (*Q).rear->next=p; (*Q).rear=p; return1;}//若隊列不為空，則刪除對頭元素，并返回1；否則返回0intDeQueue(LinkQueue*Q,QElemType*e){ QueuePtrp; if((*Q).front==(*Q).rear) return0; p=(*Q).front->next; *e=p->data; (*Q).front->next=p->next; if((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return1;}//廣度優(yōu)先非遞歸遍歷圖GvoidBFSTraverse(AMLGraphG,int(*Visit)(VertexType)){ intu,v,w,start=0; VertexTypew1,u1; LinkQueueQ; for(v=0;v<G.vexnum;v++) visite[v]=0; InitQueue(&Q); cout<<"請輸入你要開始進行查找的位置："; cin>>start; cout<<"按廣度優(yōu)先搜索的結果是:"<<endl; for(v=start;v<G.vexnum;v++) { if(!visite[v]) { visite[v]=1; Visit(G.adjmulist[v].data); EnQueue(&Q,v);//v入隊列 while(!QueueEmpty(Q)) { DeQueue(&Q,&u); strcpy(u1,*GetVex(G,u)); for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) if(!visite[w]) { visite[w]=1; Visit(G.adjmulist[w].data); EnQueue(&Q,w); } } } }//for InitQueue(&Q); for(v=0;v<start;v++) { if(!visite[v]) { visite[v]=1; Visit(G.adjmulist[v].data); EnQueue(&Q,v);//v入隊列 while(!QueueEmpty(Q)) { DeQueue(&Q,&u); strcpy(u1,*GetVex(G,u)); for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) if(!visite[w]) { visite[w]=1; Visit(G.adjmulist[w].data); EnQueue(&Q,w); } } } }//for cout<<"\b\b\b"; cout<<endl;}//把邊的訪問標記設置為0，即未被訪問voidMarkUnVisited(AMLGraphG){ inti; EBox*p; for(i=0;i<G.vexnum;i++) { p=G.adjmulist[i].firstedge; while(p) { p->mark=0; if(p->ivex==i) p=p->ilink; else p=p->jlink; } }}//顯示構造的無向圖(包括定點數(shù)、頂點、邊數(shù)、邊)voidDisplay(AMLGraphG){ inti; EBox*p; MarkUnVisited(G); cout<<G.vexnum<<"個頂點："; for(i=0;i<G.vexnum;i++) cout<<G.adjmulist[i].data<<""; cout<<";"<<G.edgenum<<"條邊:"<<endl; for(i=0;i<G.vexnum;i++) { p=G.adjmulist[i].firstedge; while(p) if(p->ivex==i) { if(!p->mark) { cout<<G.adjmulist[i].data<<"-->"<<G.adjmulist[p->jvex].data<<""; p->mark=1;//已經被訪問過了 } p=p->ilink; } else { if(!p->mark) { cout<<G.adjmulist[p->ivex].data<<"-->"<<G.adjmulist[i].data<<""; p->mark=1;//已經被訪問過了 } p=p->jlink; } cout<<endl; }}intVisit(VertexTypev){ cout<<v<<"