本科课程【数据结构与算法】实验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. 实验任务

输入图的节点信息，构造邻接表并输出邻接表和排序

2. 程序设计

1） 数据输入（输入哪些数据、个数、类型、来源、输入方式）
图的顶点数据（data）char字符型；
图的边关系（v1,v2）int 整型；
各边的权值（w）int 整型

2） 数据存储（输入数据在内存中的存储）
邻接表旳形式存储数据

3） 数据处理（说明处理步骤。若不是非常简单，需要绘制流程图）
①在有向图中选一个没有前驱的顶点且把它输出
②从图中删除该顶点和所有以它为尾的弧
③重复上述两步，直至全部顶点都输出，或者当图中不存在无前驱的顶点为止

4） 数据输出

三、 实验环境

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

源代码（C++实现）

#include<iostream>

using namespace std;#define m 100#define n 6#define e 8struct{int s[n];int top;} stack;typedefstruct node1 
{int info;//这个域就是本节点在数组中的位置int adjvertex;char data;struct node1 *nextarc;} glinklistnode;//这个是在后面邻接的节点typedefstruct node2 {int vertexinfo;
    glinklistnode *firstarc;} glinkheadnode;//邻接表的数组，vertexinfo存的是每个点的入度//创建邻接链表voidcreateAdjlist(glinkheadnode g[]){int i, j, k;
    glinklistnode *p;for(i =0; i<n; i++){
        g[i].vertexinfo = i;
        g[i].firstarc =0;}//初始化每个节点在数组中的位置
    cout <<"输入边节点关系："<< endl;for(k =0; k<e; k++){
        cin >> i >> j;
        p =(glinklistnode *)malloc(sizeof(glinklistnode));
        p->adjvertex = j;
        p->nextarc = g[i].firstarc;//使用的插入方式建立，后来的更接近根节点
        g[i].firstarc = p;//第一个邻接点是p}}//拓扑排序函数voidtoposort(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;//因为前导节点会被删掉，因此它的入度值需要-1if(indegree[w]==0)//如果它的入度等于0，就将这个节点也入栈{
                stack.top = stack.top +1;
                stack.s[stack.top]= w;}
            p = p->nextarc;//往下走}}
    cout << endl;if(sum < n){
        cout <<"存在回路"<< endl;}}intmain(){
    glinkheadnode g[m];createAdjlist(g);toposort(g);system("pause");return0;}

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html