关于最小生成树的一道经典题目,大家救救孩子吧

447908543

百炼1251:丛林中的路,http://bailian.openjudge.cn/practice/1251/,我用prim算法写的c程序,一直提示Runtime Error,我是真的不知道错在哪了,大家救救孩子吧

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #include <stdbool.h>
   
5. 
   
6. typedef struct
   
7. {
   
8.         int vexnum;
   
9.         int **arc;       
   
10. }G;
    
11. 
    
12. typedef struct
    
13. {
    
14.         int name;//终站
    
15.         int min;       
    
16. }Prim;
    
17. 
    
18. int color[30];
    
19. 
    
20. G *Init(int n)
    
21. {
    
22.         G *p=(G *)malloc(sizeof(G));
    
23.         p->vexnum=n;
    
24.         p->arc=(int **)malloc(sizeof(int*)*p->vexnum);
    
25.         for(int i=0;i<p->vexnum;i++)
    
26.         {
    
27.                 p->arc[i]=(int *)malloc(sizeof(int)*p->vexnum);
    
28.         }
    
29.         for(int i=0;i<p->vexnum;i++)
    
30.         {
    
31.                 for(int j=0;j<p->vexnum;j++)
    
32.                 {
    
33.                         p->arc[i][j]=0;
    
34.                 }
    
35.         }
    
36.        
    
37.         char cstart,cend;
    
38.         int way,power;
    
39.         for(int i=0;i<p->vexnum-1;i++)
    
40.         {
    
41.                 scanf("%c",&cstart);
    
42.                 getchar();
    
43.                 scanf("%d",&way);
    
44.                 getchar();
    
45.                 while(way--)
    
46.                 {
    
47.                         scanf("%c",&cend);
    
48.                         getchar();
    
49.                         scanf("%d",&power);
    
50.                         getchar();
    
51.                         p->arc[cstart-'A'][cend-'A']=power;
    
52.                         p->arc[cend-'A'][cstart-'A']=power;
    
53.                 }
    
54.         }
    
55.         return p;
    
56. }
    
57. 
    
58. void Create_t(G *graph,Prim *t)
    
59. {
    
60.         int min;
    
61.         for(int i=0;i<graph->vexnum;i++)
    
62.         {
    
63.                 min=100;
    
64.                 for(int j=0;j<graph->vexnum;j++)
    
65.                 {
    
66.                         if(graph->arc[i][j]&&graph->arc[i][j]<min&&!color[j])
    
67.                         {
    
68.                                 min=graph->arc[i][j];
    
69.                                 t[i].name=j;
    
70.                         }
    
71.                 }
    
72.                 t[i].min=min;
    
73.         }
    
74.        
    
75. }
    
76. 
    
77. void PrimInit(G *graph)
    
78. {
    
79.         int num=graph->vexnum;
    
80.         Prim *t=(Prim *)malloc(sizeof(Prim)*graph->vexnum);
    
81.         int index,cost=0;
    
82.         color[0]=1;
    
83.         while(--num)
    
84.         {
    
85.                 Create_t(graph,t);
    
86.                 int min=100;
    
87.                 for(int i=0;i<graph->vexnum;i++)
    
88.                 {
    
89.                         if(color[i]==1&&min>t[i].min&&!color[t[i].name])
    
90.                         {
    
91.                                 min=t[i].min;
    
92.                                 index=i;
    
93.                         }
    
94.                 }
    
95.                 color[t[index].name]=1;
    
96.                 cost+=min;
    
97.                 graph->arc[index][t[index].name]=100;
    
98.                 graph->arc[t[index].name][index]=100;
    
99.         }
    
100.         printf("%d\n",cost);
     
101. }
     
102. 
     
103. void Init_color()
     
104. {
     
105.         for(int i=0;i<30;i++)
     
106.         {
     
107.                 color[i]=0;
     
108.         }
     
109. }
     
110. 
     
111. void end(G *graph)
     
112. {
     
113.         for(int i=0;i<graph->vexnum;i++)
     
114.         {
     
115.                 free(graph->arc[i]);
     
116.         }
     
117.         free(graph);
     
118. }
     
119. 
     
120. int main(void)
     
121. {
     
122.         int n;
     
123.         scanf("%d",&n);
     
124.         while(n)
     
125.         {
     
126.                 fflush(stdin);
     
127.                 Init_color();
     
128.                 G *graph=Init(n);
     
129.                 PrimInit(graph);
     
130.                 scanf("%d",&n);
     
131.                 end(graph);
     
132.         }
     
133.         return 0;
     
134. }

复制代码

newu

首先没看逻辑错误，语法错误主要在指针和结构体这边

Prim *t;  
(*t).name和t->name应该这样用。
还有里面那个color=0应该是color[i] = 0;

447908543

newu 发表于 2019-6-26 20:16
首先没看逻辑错误，语法错误主要在指针和结构体这边

Prim *t;  

感谢回答,不知道为什么我直接复制粘贴在帖子里面有些 [] 没有显示出来,我重新编辑了一下,个人感觉语法应该没有问题,可能是在测试某一组数据的时候崩了,因为使用测试数据的时候我这个程序都完全正常,还是谢谢您的回复!