拓扑算法

寻123

这是我从网上找的代码，但是这段代码只能够一个字符一个字符的输入，像A、B、C或者1、2、3这样输入，但不能够字符串输入如c1、c2这样输入。我不会改成字符串输入，请大神帮我改改，拜托了

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. #define MaxSize 20
   
6. 
   
7. typedef char VertexType;
   
8. 
   
9. typedef struct outNode {                //定义出度的节点
   
10.         VertexType data;
    
11.         struct outNode *next;
    
12. }outNode;
    
13. 
    
14. typedef struct Vertex {                        //定义顶点结构
    
15.         int in;
    
16.         VertexType data;
    
17.         outNode *first;
    
18. }Vertex;
    
19. 
    
20. //用邻接表法创建AOV网
    
21. void CreateAOV( Vertex **g )
    
22. {
    
23.         VertexType ver;
    
24.         int i = 0;
    
25.         int VertexNum;
    
26.         outNode *p, *q;
    
27.         (*g) = (Vertex *)malloc(sizeof(Vertex)*MaxSize);
    
28. 
    
29.         printf("请输入AOV网的顶点:\n");                               
    
30.         while( '\n' != (ver=getchar()) ) {                //存储网的顶点信息
    
31.                 (*g)[i].data = ver;
    
32.                 (*g)[i].first = NULL;
    
33.                 i++;
    
34.         }
    
35.         (*g)[i].data = '\0';
    
36.         VertexNum = i;                                                        //记录顶点数
    
37. 
    
38.         printf("请依次输入AOV网顶点的入度:\n");
    
39.         for( i=0; i<VertexNum; i++ )                        //存储顶点的入度信息
    
40.                 scanf("%d", &(*g)[i].in);
    
41. 
    
42.         fflush(stdin);
    
43.        
    
44.         printf("请输入AOV网顶点对应邻接点:\n");
    
45.         for( i=0; i<VertexNum; i++ ) {                        //存储每个顶点的邻接点信息
    
46.                 printf("%c :", (*g)[i].data);
    
47.                 if( '\n' != (ver=getchar()) ) {
    
48.                         p = (outNode *)malloc(sizeof(outNode));
    
49.                         p->data = ver;
    
50.                         (*g)[i].first = p;
    
51.                         p->next = NULL;
    
52.                         q = p;
    
53.                                        
    
54.                         while( '\n' != (ver=getchar()) ) {
    
55.                                 p = (outNode *)malloc(sizeof(outNode));
    
56.                                 p->data = ver;
    
57.                                 p->next = NULL;
    
58.                                 q->next = p;
    
59.                                 q = p;
    
60.                         }
    
61.                 }
    
62.         }
    
63. }
    
64. 
    
65. //获取顶点数
    
66. int CalVerNum( Vertex *g )
    
67. {
    
68.         int len = 0;
    
69.         while( '\0' != (g++)->data )
    
70.                 len++;
    
71.         return len;
    
72. }
    
73. 
    
74. //打印AOV网
    
75. void PrintAOV( Vertex *g )
    
76. {
    
77.         int VertexNum = CalVerNum( g );
    
78.         outNode *p;
    
79.         printf("AOV的顶点、入度以及邻接点为:\n");
    
80.         for( int i=0; i<VertexNum; i++ ) {                //打印顶点
    
81.                 printf("%c  %d  ", g[i].data, g[i].in);
    
82.                 p = g[i].first;
    
83.                 while( NULL != p ) {
    
84.                         printf("%c ", p->data);
    
85.                         p = p->next;
    
86.                 }
    
87.                 printf("\n");
    
88.         }
    
89. }
    
90. 
    
91. //拓扑排序函数
    
92. void TopSort( Vertex *g )
    
93. {
    
94.         int i, j, k;
    
95.         outNode *p;
    
96.         int VertexNum = CalVerNum( g );
    
97.         printf("拓扑排序后的序列为:\n");
    
98.         for( i=0; i<VertexNum; i++ ) {                                //外循环用来控制输出的顶点数
    
99.                 for( j=0; j<VertexNum; j++ )                        //内循环用来找到下一个入度为0的顶点
    
100.                         if( 0 == g[j].in ) {
     
101.                                 printf("%c ", g[j].data);
     
102.                                 g[j].in = -1;
     
103.                                 p = g[j].first;
     
104.                                 while( NULL != p ) {                       
     
105. //删除所有从该顶点发出的全部有向边,具体就是逐个找到该顶点邻接点，然后将其入度-1
     
106.                                         for( k=0; k<VertexNum; k++ )
     
107.                                                 if( p->data == g[k].data ) {
     
108.                                                         g[k].in--;
     
109.                                                         break;
     
110.                                                 }
     
111.                                         p = p->next;
     
112.                                 }
     
113.                                 break;
     
114.                         }
     
115.         }
     
116.         printf("\n");
     
117. }
     
118. 
     
119. int main()
     
120. {
     
121.         Vertex *g;
     
122.         CreateAOV( &g );
     
123. 
     
124.         PrintAOV( g );
     
125. 
     
126.         TopSort( g );
     
127. 
     
128.         return 0;
     
129. }

复制代码

lumber2388779

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

寻123

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

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

寻123

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

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