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

447908543

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct
{
        int vexnum;
        int **arc;        
}G;

typedef struct
{
        int name;//终站 
        int min;        
}Prim;

int color[30]; 

G *Init(int n)
{
        G *p=(G *)malloc(sizeof(G));
        p->vexnum=n;
        p->arc=(int **)malloc(sizeof(int*)*p->vexnum);
        for(int i=0;i<p->vexnum;i++)
        {
                p->arc[i]=(int *)malloc(sizeof(int)*p->vexnum);
        }
        for(int i=0;i<p->vexnum;i++)
        {
                for(int j=0;j<p->vexnum;j++)
                {
                        p->arc[i][j]=0;
                }
        }
        
        char cstart,cend;
        int way,power;
        for(int i=0;i<p->vexnum-1;i++)
        {
                scanf("%c",&cstart);
                getchar();
                scanf("%d",&way);
                getchar();
                while(way--)
                {
                        scanf("%c",&cend);
                        getchar();
                        scanf("%d",&power);
                        getchar();
                        p->arc[cstart-'A'][cend-'A']=power;
                        p->arc[cend-'A'][cstart-'A']=power;
                }
        }
        return p;
}

void Create_t(G *graph,Prim *t)
{
        int min;
        for(int i=0;i<graph->vexnum;i++)
        {
                min=100;
                for(int j=0;j<graph->vexnum;j++)
                {
                        if(graph->arc[i][j]&&graph->arc[i][j]<min&&!color[j])
                        {
                                min=graph->arc[i][j];
                                t[i].name=j;
                        }
                }
                t[i].min=min;
        }
        
}

void PrimInit(G *graph)
{
        int num=graph->vexnum;
        Prim *t=(Prim *)malloc(sizeof(Prim)*graph->vexnum);
        int index,cost=0;
        color[0]=1;
        while(--num)
        {
                Create_t(graph,t); 
                int min=100;
                for(int i=0;i<graph->vexnum;i++)
                {
                        if(color[i]==1&&min>t[i].min&&!color[t[i].name])
                        {
                                min=t[i].min;
                                index=i;
                        }
                }
                color[t[index].name]=1;
                cost+=min;
                graph->arc[index][t[index].name]=100;
                graph->arc[t[index].name][index]=100; 
        }
        printf("%d\n",cost);
}

void Init_color()
{
        for(int i=0;i<30;i++)
        {
                color[i]=0;
        }
}

void end(G *graph)
{
        for(int i=0;i<graph->vexnum;i++)
        {
                free(graph->arc[i]);
        }
        free(graph);
}

int main(void)
{
        int n;
        scanf("%d",&n);
        while(n)
        {
                fflush(stdin);
                Init_color();
                G *graph=Init(n);
                PrimInit(graph);
                scanf("%d",&n);
                end(graph); 
        }
        return 0;
}

newu

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

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

447908543

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

Prim *t;  

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