论坛 › 数据结构与算法 › 拓扑算法

寻123 发表于 2017-5-28 10:11:08

拓扑算法

这是我从网上找的代码，但是这段代码只能够一个字符一个字符的输入，像A、B、C或者1、2、3这样输入，但不能够字符串输入如c1、c2这样输入。我不会改成字符串输入，请大神帮我改改，拜托了{:5_100:}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxSize 20

typedef char VertexType;

typedef struct outNode {                //定义出度的节点
        VertexType data;
        struct outNode *next;
}outNode;

typedef struct Vertex {                        //定义顶点结构
        int in;
        VertexType data;
        outNode *first;
}Vertex;

//用邻接表法创建AOV网
void CreateAOV( Vertex **g )
{
        VertexType ver;
        int i = 0;
        int VertexNum;
        outNode *p, *q;
        (*g) = (Vertex *)malloc(sizeof(Vertex)*MaxSize);

        printf("请输入AOV网的顶点:\n");                               
        while( '\n' != (ver=getchar()) ) {                //存储网的顶点信息
                (*g).data = ver;
                (*g).first = NULL;
                i++;
        }
        (*g).data = '\0';
        VertexNum = i;                                                        //记录顶点数

        printf("请依次输入AOV网顶点的入度:\n");
        for( i=0; i<VertexNum; i++ )                        //存储顶点的入度信息
                scanf("%d", &(*g).in);

        fflush(stdin);
       
        printf("请输入AOV网顶点对应邻接点:\n");
        for( i=0; i<VertexNum; i++ ) {                        //存储每个顶点的邻接点信息
                printf("%c :", (*g).data);
                if( '\n' != (ver=getchar()) ) {
                        p = (outNode *)malloc(sizeof(outNode));
                        p->data = ver;
                        (*g).first = p;
                        p->next = NULL;
                        q = p;
                                       
                        while( '\n' != (ver=getchar()) ) {
                                p = (outNode *)malloc(sizeof(outNode));
                                p->data = ver;
                                p->next = NULL;
                                q->next = p;
                                q = p;
                        }
                }
        }
}

//获取顶点数
int CalVerNum( Vertex *g )
{
        int len = 0;
        while( '\0' != (g++)->data )
                len++;
        return len;
}

//打印AOV网
void PrintAOV( Vertex *g )
{
        int VertexNum = CalVerNum( g );
        outNode *p;
        printf("AOV的顶点、入度以及邻接点为:\n");
        for( int i=0; i<VertexNum; i++ ) {                //打印顶点
                printf("%c%d", g.data, g.in);
                p = g.first;
                while( NULL != p ) {
                        printf("%c ", p->data);
                        p = p->next;
                }
                printf("\n");
        }
}

//拓扑排序函数
void TopSort( Vertex *g )
{
        int i, j, k;
        outNode *p;
        int VertexNum = CalVerNum( g );
        printf("拓扑排序后的序列为:\n");
        for( i=0; i<VertexNum; i++ ) {                                //外循环用来控制输出的顶点数
                for( j=0; j<VertexNum; j++ )                        //内循环用来找到下一个入度为0的顶点
                        if( 0 == g.in ) {
                                printf("%c ", g.data);
                                g.in = -1;
                                p = g.first;
                                while( NULL != p ) {                       
//删除所有从该顶点发出的全部有向边,具体就是逐个找到该顶点邻接点，然后将其入度-1
                                        for( k=0; k<VertexNum; k++ )
                                                if( p->data == g.data ) {
                                                        g.in--;
                                                        break;
                                                }
                                        p = p->next;
                                }
                                break;
                        }
        }
        printf("\n");
}

int main()
{
        Vertex *g;
        CreateAOV( &g );

        PrintAOV( g );

        TopSort( g );

        return 0;
}

lumber2388779 发表于 2017-5-29 10:04:44

先明确下你的需求 你是要把结点的名称改成是一个字符串呢 还是一次性输入多个结点

寻123 发表于 2017-5-29 10:27:27

lumber2388779 发表于 2017-5-29 10:04
先明确下你的需求 你是要把结点的名称改成是一个字符串呢 还是一次性输入多个结点

一次性输入多个节点，就比如 输入 c1 c2 c3 c4 这样

寻123 发表于 2017-5-29 10:48:30

寻123 发表于 2017-5-29 10:27
一次性输入多个节点，就比如 输入 c1 c2 c3 c4 这样

是 一次性输入多个字符串类型的节点c1 c2 c3 这样的 然后能够成功读取他们并能执行下面的代码

查看完整版本: 拓扑算法