欢迎来到天天文库
浏览记录
ID:16295021
大小:136.21 KB
页数:5页
时间:2018-08-09
《拓扑算法算法的实现》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、韩山师范学院实验题目:拓扑排序算法实现班级:2015级软工班作者:黄俊聪#includeusingnamespacestd;#defineMVNum100//最大顶点数#defineOK1#defineERROR0typedefintStatus;typedefstringVerTexType;typedefintOtherInfo;typedefstructArcNode//边结点{intadjvex;//该边所指向的顶点的位置structArcNode*nextarc;//指向下一条边的指针Othe
2、rInfoinfo;//和边相关的信息}ArcNode;typedefstructVNode//顶点信息{VerTexTypedata;ArcNode*firstarc;//指向第一条依附该顶点的边的指针}VNode,AdjList[MVNum];//Adjlist表示邻接表类型typedefstruct{AdjListvertices;intvexnum,arcnum;//图的当前顶点数}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;i5、>G.vexnum>>G.arcnum;//输入总顶点数和总边数cout<<"输入各点,构造表头结点表:"<>G.vertices[i].data;//输入顶点值G.vertices[i].firstarc=NULL;//初始化表头结点的指针域为NULL}cout<<"输入各边,构造邻接表:"<>v1>>v2;//输入一条边依附的两个6、顶点i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置,即顶点在G.vertices中的序号p1=newArcNode;//生成一个新的边结点*p1p1->adjvex=j;//邻接点序号为jp1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;//将新结点*p1插入顶点v1的边表头部}returnOK;}StatusFindInDegree(ALGraphG,intindegree[]){ArcNode7、*p;for(inti=0;inextarc)indegree[p->adjvex]++;/*出度不为零,则该顶点firstarc域指向的弧指向的顶点入度加一*/returnOK;}StatusTopologicalSort(ALGraphG,inttopo[]){LinkStackS;ArcNode*p;inti8、;intindegree[G.vexnum];FindInDegree(G,indegree);InitStack(S);for(i=0;i
5、>G.vexnum>>G.arcnum;//输入总顶点数和总边数cout<<"输入各点,构造表头结点表:"<>G.vertices[i].data;//输入顶点值G.vertices[i].firstarc=NULL;//初始化表头结点的指针域为NULL}cout<<"输入各边,构造邻接表:"<>v1>>v2;//输入一条边依附的两个
6、顶点i=LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中的位置,即顶点在G.vertices中的序号p1=newArcNode;//生成一个新的边结点*p1p1->adjvex=j;//邻接点序号为jp1->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p1;//将新结点*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
此文档下载收益归作者所有