论坛 › 数据结构与算法 › 关于最小生成树的一道经典题目,大家救救孩子吧

447908543 发表于 2019-6-26 18:46:30

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

本帖最后由 447908543 于 2019-6-27 14:40 编辑

百炼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;

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=(int *)malloc(sizeof(int)*p->vexnum);
        }
        for(int i=0;i<p->vexnum;i++)
        {
                for(int j=0;j<p->vexnum;j++)
                {
                        p->arc=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=power;
                        p->arc=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&&graph->arc<min&&!color)
                        {
                                min=graph->arc;
                                t.name=j;
                        }
                }
                t.min=min;
        }
       
}

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

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

void end(G *graph)
{
        for(int i=0;i<graph->vexnum;i++)
        {
                free(graph->arc);
        }
        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 发表于 2019-6-26 20:16:05

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

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

447908543 发表于 2019-6-27 14:40:01

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

Prim *t;


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

查看完整版本: 关于最小生成树的一道经典题目,大家救救孩子吧