//算法6.12 拓扑排序
#include <iostream>
using namespace std;
#include <string.h>
#define MVNum 100 //最大顶点数
#define OK 1
#define ERROR 0
typedef char VerTexType[3];
//- - - - -图的邻接表存储表示- - - - -
typedef struct ArcNode{ //边结点
int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
}ArcNode;
typedef struct VNode{
VerTexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode, AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct{
AdjList vertices; //邻接表
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;
//- - - - - - - - - - - - - - - -
int indegree[MVNum]; //数组indegree存放个顶点的入度
int LocateVex(ALGraph G , VerTexType v){
//确定点v在G中的位置
for(int i = 0; i < G.vexnum; ++i)
if(strcmp(G.vertices[i].data , v)==0)
return i;
return -1;
}//LocateVex
int CreateUDG(ALGraph &G){
//创建有向图G的邻接表、逆邻接表
int i , k;
// cout <<"请输入总顶点数，总边数，以空格隔开:";
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
cout << endl;
for(i = 0; i < G.vexnum; ++i) indegree[i]=0;//数组indegree存放个顶点的入度
//输入各点，构造表头结点表
// cout << "输入点的名称，如a" << endl;
for(i = 0; i < G.vexnum; ++i){ //输入各点，构造表头结点表
// cout << "请输入第" << (i+1) << "个点的名称:";
cin >> G.vertices[i].data; //输入顶点值
//初始化表头结点的指针域为NULL
G.vertices[i].firstarc=NULL;
}//for
// cout << endl;
// cout << "输入边依附的顶点，如a b" << endl;
for(k = 0; k < G.arcnum;++k){ //输入各边，构造邻接表
VerTexType v1 , v2;
int i , j;
// cout << "请输入第" << (k + 1) << "条边依附的顶点:";
cin >> v1 >> v2; //输入一条边依附的两个顶点
i = LocateVex(G, v1); j = LocateVex(G, v2);
//确定v1和v2在G中位置，即顶点在G.vertices中的序号
ArcNode *p1=new ArcNode; //生成一个新的边结点*p1
p1->adjvex=j; //邻接点序号为j
p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
//将新结点*p1插入顶点vi的边表头部
indegree[j]++; //V2顶点的入度加1；
}//for
return OK;
}//CreateUDG
int TopologicalSort(ALGraph G , int topo[]){
//有向图G采用邻接表存储结构
//若G无回路，则生成G的一个拓扑序列topo[]并返回OK，否则ERROR
int st[MVNum],top=-1,i , m;
//栈S初始化为空
for(i = 0; i < G.vexnum; ++i)
if(!indegree[i]) {top++;st[top]=i;} //入度为0者进栈
m = 0; //对输出顶点计数，初始为0
while(top>-1){ //栈S非空
i=st[top];top--; //将栈顶顶点vi出栈
topo[m]=i; //将vi保存在拓扑序列数组topo中
++m; //对输出顶点计数
ArcNode *p = G.vertices[i].firstarc; //p指向vi的第一个邻接点
while(p){
int k = p->adjvex; //vk为vi的邻接点
--indegree[k]; //vi的每个邻接点的入度减1
if(indegree[k] ==0) {top++;st[top]=k;} //若入度减为0，则入栈
p = p->nextarc; //p指向顶点vi下一个邻接结点
}//while
}//while
if(m < G.vexnum) return ERROR; //该有向图有回路
else return OK;
}//TopologicalSort
int main(){
// cout << "************算法6.12 拓扑排序**************" << endl << endl;
ALGraph G;
CreateUDG(G);
int *topo = new int [G.vexnum];
// cout << endl;
// cout << "有向图的邻接表、逆邻接表创建完成!" << endl << endl;
if(TopologicalSort(G , topo)){
//cout << "该有向图的拓扑有序序列为：";
for(int j = 0 ; j < G.vexnum; j++){
if(j != G.vexnum - 1)
cout << G.vertices[topo[j]].data ;
else
cout << G.vertices[topo[j]].data << endl << endl;
if(j<G.vexnum-1) cout <<" ";
}
else
cout << "网中存在环，无法进行拓扑排序！" <<endl << endl;
return OK;
}//main
数据结构C语言版教材全部算法代码实现
需积分: 18 149 浏览量
2019-01-20
14:22:05
上传
评论 6
收藏 481KB RAR 举报
数据结构C语言版教材全部算法代码实现 （109个子文件） 
6.13.cpp 8KB 2.6-2.12.cpp 6KB avltree.cpp 6KB 6.12.cpp 5KB 2.13-2.14.cpp 5KB 7.8-7.9.cpp 5KB 6.7.cpp 5KB 锐格-拓扑排序.cpp 5KB 2.1-2.5.cpp 5KB 6.10.cpp 4KB 未命名1.cpp 4KB 8.12.cpp 4KB bstree.cpp 4KB 7.4-7.7.cpp 4KB bstree-锐格.cpp 4KB 6.9.cpp 4KB 5.12-5.13.cpp 4KB 6.8.cpp 4KB 6.6.cpp 4KB 6.11.cpp 4KB 6.4.cpp 3KB 6.3.cpp 3KB 5.11.cpp 3KB 6.5.cpp 3KB 线索化二叉树.cpp 3KB 6.14.cpp 3KB 6.2.cpp 3KB 2.18-2.19.cpp 3KB 3.16-3.19.cpp 3KB 3.11-3.15.cpp 3KB 3.1-3.4.cpp 3KB 3.5-3.8.cpp 2KB 5.8.cpp 2KB 6.1.cpp 2KB 2.16.cpp 2KB 2.17.cpp 2KB 8.5.cpp 2KB 8.11.cpp 2KB 3.21.cpp 2KB 8.9.cpp 2KB 1.cpp 2KB 5.2.cpp 2KB 2.15(顺序表).cpp 2KB 2.15(链表).cpp 2KB 5.10.cpp 2KB 8.3.cpp 2KB 5.7.cpp 2KB 8.8.cpp 2KB 8.2.cpp 2KB 4.4.cpp 2KB 7.10.cpp 1KB 8.10.cpp 1KB 8.1.cpp 1KB 4.2-4.3.cpp 1KB 7.3.cpp 1KB 8.4.cpp 1KB 8.7.cpp 1KB 5.4.cpp 1KB 8.6.cpp 1KB 7.2.cpp 1KB 3.20.cpp 1KB 7.1.cpp 1KB 4.1.cpp 1KB 5.5.cpp 1KB 3.9.cpp 1KB 5.1.cpp 1KB 5.3.cpp 1KB 5.6.cpp 1011B 3.22.cpp 560B 3.23.cpp 327B 3.10.cpp 293B
bstree.exe 889KB bstree-锐格.exe 465KB 3.22.h 3KB 3.23.h 3KB 3.10.h 646B bstree.o 3KB 3.5-3.8.suo 16KB 3.16-3.19.suo 14KB 3.21.suo 13KB 3.22.suo 13KB 3.23.suo 11KB 3.10.suo 11KB 3.1-3.4.suo 11KB 3.11-3.15.suo 10KB 3.20.suo 10KB 3.9.suo 9KB
6.12拓扑排序.txt 4KB 新建文本文档.txt 2KB book.txt 622B book.txt 622B book.txt 622B DancePartner.txt 178B 病毒感染检测输入数据.txt 172B PolyA.txt 52B PolyB.txt 45B ListB.txt 16B ListB.txt 16B SqStack.txt 10B QNode.txt 10B共 109 条
- 1
- 2
资源评论
