课程设计实验报告|本科课程【数据结构与算法】实验8 - 拓扑排序实验|本科课程|拓扑排序|C++|数

【课程设计实验报告|本科课程【数据结构与算法】实验8 - 拓扑排序】大家好，我是【1+1=王】，热爱java的计算机（人工智能）渣硕研究生在读。
如果你也对java、人工智能等技术感兴趣，欢迎关注，抱团交流进大厂！！！
Good better best, never let it rest, until good is better, and better best.
近期会把自己本科阶段的一些课程设计、实验报告等分享出来，供大家参考，希望对大家有帮助。
博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

一、实验目的

掌握图的邻接矩阵存储结构
实现图的拓扑排序操作

二、实验内容 1. 实验任务输入图的节点信息，构造邻接表并输出邻接表和排序
2. 程序设计 1）数据输入（输入哪些数据、个数、类型、来源、输入方式）
图的顶点数据（data）char字符型；
图的边关系（v1,v2）int 整型；
各边的权值（w）int 整型
2）数据存储（输入数据在内存中的存储）
邻接表旳形式存储数据
3）数据处理（说明处理步骤。若不是非常简单，需要绘制流程图）
①在有向图中选一个没有前驱的顶点且把它输出
②从图中删除该顶点和所有以它为尾的弧
③重复上述两步，直至全部顶点都输出，或者当图中不存在无前驱的顶点为止
4）数据输出

文章图片

三、实验环境

操作系统：WINDOWS 10
开发工具：VC++ 2013
实验设备：PC

源代码（C++实现）

#includeusing namespace std; #define m 100 #define n 6 #define e 8struct { int s[n]; int top; } stack; typedef struct node1 { int info; //这个域就是本节点在数组中的位置 int adjvertex; char data; struct node1 *nextarc; } glinklistnode; //这个是在后面邻接的节点typedef struct node2 { int vertexinfo; glinklistnode *firstarc; } glinkheadnode; //邻接表的数组，vertexinfo存的是每个点的入度//创建邻接链表 void createAdjlist(glinkheadnode g[]) { int i, j, k; glinklistnode *p; for (i = 0; i> i >> j; p = (glinklistnode *)malloc(sizeof(glinklistnode)); p->adjvertex = j; p->nextarc = g[i].firstarc; //使用的插入方式建立，后来的更接近根节点 g[i].firstarc = p; //第一个邻接点是p } }//拓扑排序函数 void toposort(glinkheadnode g[]) { int i, v, w, sum = 0, indegree[n]; glinklistnode *p; for (i = 0; i < n; i++) { indegree[i] = 0; //初始化indegree数组，完全可以使用memset } for (i = 0; i < n; i++) { for (p = g[i].firstarc; p != 0; p = p->nextarc) //这一层for循环用来统计 indegree[p->adjvertex]++; //经过两个for循环，即可把所有节点的入度算统计出来 } for (i = 0, stack.top = -1; i < n; i++) { if (indegree[i] == 0) { stack.top++; stack.s[stack.top] = i; }//这个for循环用来入栈入度为0的节点 } while (stack.top != -1) { cout << stack.s[stack.top]+1 << " "; sum = sum + 1; v = stack.s[stack.top]; stack.top = stack.top - 1; //出栈top p = g[v].firstarc; //读取该节点的第一个邻接点 while (p != 0) //遍历p的所有邻接点 { w = p->adjvertex; indegree[w] = indegree[w] - 1; //因为前导节点会被删掉，因此它的入度值需要-1 if (indegree[w] == 0) //如果它的入度等于0，就将这个节点也入栈 { stack.top = stack.top + 1; stack.s[stack.top] = w; } p = p->nextarc; //往下走 } } cout << endl; if (sum < n) { cout << "存在回路" << endl; } }int main() { glinkheadnode g[m]; createAdjlist(g); toposort(g); system("pause"); return 0; }