拓扑排序C语言实现

  Tuopu.c
  dataTest

  Created by icephone_1 on 2017/11/26.
  Copyright © 2017年 data. All rights reserved.


#include <stdio.h>
#include <stdlib.h>
#define MAXN 100001
#define MAXM 500001
#define true 1
#define false 0
typedef int status;
typedef int ElemType;

//节点数据结构
typedef struct Node{
    ElemType elem;
    struct Node *next;
}Node,*pNode;

//队列数据结构
typedef struct Queue{
    pNode front;//指向队列头部
    pNode rear;//指向队列尾部
    int size;//队列长度
}Queue,*pQueue;

//邻接表
typedef struct Vnode{
    pNode firstArc;//边表头指针
    int innum;//入度
}Vnode;
//图数据结构
typedef struct ALGraph{
    Vnode* adjList;
    int vexnum;//定点数
    int arcnum;//边数
}ALGraph,*pALGraph;

//创建一个队列
pQueue CreateQueue();
//将一个元素加入队尾
ElemType AddNode(pQueue queue,ElemType elem);
//将队头元素出队
status DeleteQueueNode(pQueue queue);
//判断当前队列是否为空
int IsQueueEmpty(pQueue queue);
//删除队列
void DeleteQueue(pQueue queue);
//创建一个图的邻接表结构
pALGraph CreateALGraph(int n,int m);
//删除邻接表
status DeleteALGraph(pALGraph G);
//进行拓扑排序
status TopSort(pALGraph G,pQueue queue);

int main() {
    int T;
    printf("请输入T：");
    scanf("%d", &T);
    while (T--) {
        //输入的N和M值,即顶点数和边数
        int n,m;
        printf("请输入N和M值");
        scanf("%d %d",&n,&m);
        pALGraph G = CreateALGraph(n,m);
        pQueue queue = CreateQueue();
        if(TopSort(G,queue)){
            printf("Correct\n");
        }
        else{
            printf("Wrong\n");
        }
    }
    return 0;
}

//创建一个队列
pQueue CreateQueue(){
    //申请内存空间
    pQueue queue = (pQueue)malloc(sizeof(Queue));
    if(queue!=NULL){
        queue->front=NULL;
        queue->rear=NULL;
        queue->size=0;
    }
    //申请内存空间失败
    else{
        printf("分配失败");
        exit(-1);
    }
    return queue;
}

//将一个元素加入队尾
ElemType AddNode(pQueue queue,ElemType elem){
    //分配内存空间
    pNode node = (pNode)malloc(sizeof(Node));
    //分配成功
    if(node!=NULL){
        node->elem=elem;
        node->next=NULL;
        if(IsQueueEmpty(queue)){
            queue->front=node;
        }
        else{
            queue->rear->next=node;
        }
        queue->rear=node;


        queue->size++;

    }
    return elem;
}
//将队头元素出队
ElemType DeleteQueueNode(pQueue queue){
    pNode node = queue->front;
    int elem=node->elem;
    //如果队列不为空则删除头结点
    if(IsQueueEmpty(queue)==false){
        queue->front=queue->front->next;
        free(node);
        //队列大小减一
        queue->size--;
        return elem;
    }
    else{
        printf("删除失败，队列已经为空");
        return -1;
    }
}

//判断当前队列是否为空
status IsQueueEmpty(pQueue queue){
    //如果队列长度为0，那么这个队列就是空队列
    if(queue->size==0){
        return true;
    }
    //如果不为0，则不是空队列
    else{
        return false;
    }
}
//销毁一个队列
void DeleteQueue(pQueue queue){
    while (IsQueueEmpty(queue)==false) {
        DeleteQueueNode(queue);
    }
    free(queue);
}

//创建一个图的邻接表结构
pALGraph CreateALGraph(int n,int m){
    //循环变量
    int i;
    //每行输入的两个顶点
    int u,v;
    pNode node = (pNode) malloc(sizeof(Node));
    Vnode * nodeHead = (Vnode *) malloc(sizeof(Vnode) * MAXN);
    nodeHead->firstArc = node;
    pALGraph G=(pALGraph)malloc(sizeof(ALGraph));
    G->vexnum=n;
    G->arcnum=m;
    G->adjList = nodeHead;
    //初始化入度为0
    for (i=0; i<m; i++) {
        G->adjList[i].innum=0;
    }
    for (i=0; i<m; i++) {
        //输入两个课程
        scanf("%d %d",&u,&v);
        //输入的课程序号是1-N，所以要减一
        u--;v--;
        pNode p = (pNode)malloc(sizeof(Node));
        p->elem=v;
        p->next=G->adjList[u].firstArc;
        G->adjList[u].firstArc=p;
        G->adjList[v].innum = G->adjList[v].innum+1;
    }
    return G;
}

status DeleteALGraph(pALGraph G){
    int i;
    pNode p;
    for (i=0; i<G->vexnum; i++) {
        p=G->adjList[i].firstArc;
        while (p!=NULL) {
            G->adjList[i].firstArc = p->next;
            free(p);
            p=G->adjList[i].firstArc;
        }
    }
    printf("delete ok!!");
    return true;
}

status TopSort(pALGraph G,pQueue queue){
    int i;
    //记录被删除的节点
    int count=0;
    //队列
    //把入度为0的加入到队列
    for (i=0; i<G->vexnum; i++) {
        if (G->adjList[i].innum==0) {
            AddNode(queue, i);
        }
    }
    while(!IsQueueEmpty(queue)){
        //删除第一个节点
        int elem = DeleteQueueNode(queue);
        count++;
        int index;
        pNode p;
        //获取与elem相连的点
        for (p=G->adjList[elem].firstArc; p!=NULL; p=p->next) {
            index=p->elem;
            int num = G->adjList[index].innum - 1;
            if(num==0){
                AddNode(queue, index);
            }
        }
    }
    if(count == G->vexnum) return true;
    else return false;
}