拓?fù)渌惴ㄋ惴ǖ膶崿F(xiàn)

《拓?fù)渌惴ㄋ惴ǖ膶崿F(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、韓山師范學(xué)院實驗題目：拓?fù)渑判蛩惴▽崿F(xiàn)班級：2015級軟工班作者：黃俊聰#includeusingnamespacestd;#defineMVNum100//最大頂點數(shù)#defineOK1#defineERROR0typedefintStatus;typedefstringVerTexType;typedefintOtherInfo;typedefstructArcNode//邊結(jié)點{intadjvex;//該邊所指向的頂點的位置structArcNode*nextarc;//指向下一條邊的指針Othe

2、rInfoinfo;//和邊相關(guān)的信息}ArcNode;typedefstructVNode//頂點信息{VerTexTypedata;ArcNode*firstarc;//指向第一條依附該頂點的邊的指針}VNode,AdjList[MVNum];//Adjlist表示鄰接表類型typedefstruct{AdjListvertices;intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)}ALGraph;typedefstructStackNode{intdata;structStackNode*next;}StackN

3、ode,*LinkStack;StatusInitStack(LinkStack&S){S=NULL;returnOK;}StatusPush(LinkStack&S,inte){LinkStackp;p=newStackNode;p->data=e;p->next=S;S=p;returnOK;}StatusPop(LinkStack&S,int&e){LinkStackp;p=newStackNode;if(S==NULL)returnERROR;e=S->data;p=S;S=S->next;deletep;retu

4、rnOK;}StatusStackEmpty(LinkStackS){if(S==NULL)returnOK;elsereturnERROR;}StatusLocateVex(ALGraphG,stringv){inti;for(inti=0;i

5、>G.vexnum>>G.arcnum;//輸入總頂點數(shù)和總邊數(shù)cout<<"輸入各點，構(gòu)造表頭結(jié)點表："<>G.vertices[i].data;//輸入頂點值G.vertices[i].firstarc=NULL;//初始化表頭結(jié)點的指針域為NULL}cout<<"輸入各邊，構(gòu)造鄰接表："<>v1>>v2;//輸入一條邊依附的兩個

6、頂點i=LocateVex(G,v1);j=LocateVex(G,v2);//確定v1和v2在G中的位置，即頂點在G.vertices中的序號p1=newArcNode;//生成一個新的邊結(jié)點*p1p1->adjvex=j;//鄰接點序號為jp1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;//將新結(jié)點*p1插入頂點v1的邊表頭部}returnOK;}StatusFindInDegree(ALGraphG,intindegree[]){ArcNode

7、*p;for(inti=0;inextarc)indegree[p->adjvex]++;/*出度不為零，則該頂點firstarc域指向的弧指向的頂點入度加一*/returnOK;}StatusTopologicalSort(ALGraphG,inttopo[]){LinkStackS;ArcNode*p;inti

8、;intindegree[G.vexnum];FindInDegree(G,indegree);InitStack(S);for(i=0;i