[已解决]这个上面明明已经分配空间了，为什么会这样呀？

御坂19090

#include <stdio.h>

#define scanf scanf_s
#define MAXVEX 8                        // 最大顶点数
#define INFINITY 65535                // 用65535来代表无穷大

//表示元素的数据类型
typedef char ElemType;

//顶点节点
typedef struct VertexNode {
    ElemType data;
    struct EdgeNode *first;
}VertexNode;

//边节点
typedef struct EdgeNode {
    int adjvex; //邻接域
    int weight; //权
    struct EdgeNode *next;  //指向下一个邻接点
}EdgeNode;

//头节点；记录节点数和边数
typedef struct headNode {
    VertexNode node[MAXVEX];
    int numVertexes, numEdges;
}headNode;

//创建边节点
void create_Edge(struct VertexNode* Vertex, int number, int weight) {
    struct EdgeNode* Edge, * temp;

    Edge = (struct EdgeNode *)malloc(sizeof(struct EdgeNode));
    Edge->adjvex = number;
    Edge->weight = weight;
    Edge->next = NULL;

    if (Vertex->first) {
        Vertex->first = Edge;
    }
    else {
        temp = Vertex->first;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = Edge;
    }
}

// 建立邻接表
void Create_Adjacencytables(headNode * head){
    int i, j, k, w;

    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &head->numVertexes, &head->numEdges);  //获取边的顶点数和边数
    getchar();  //吸收换行符

    //读取顶点信息
    for (i = 0; i < head->numVertexes; i++) {
        scanf("%c", &head->node[i].data);
        head->node[i].first = NULL;                // 初始化置为空表
        getchar();  //吸收换行符
    }

    //读取边节点信息
    printf("请输入边(i,j)的i,j和对应的权w；格式(i j w):\n");
    for (i = 0; i < head->numEdges; i++) {
        scanf_s("%d %d %d", &j, &k, &w);
        create_Edge(head->node + j, k, w);
    }
}

//Prim算法生成最小生成树
void MiniSpanTree_Prim(headNode head) {
    int min, i, j, k;
    int adjvex[MAXVEX];     //记录顶点的连接；储存所有可接触到的顶点和确定相连顶点间最小权值
    int lowcost[MAXVEX];    // 保存相关顶点间边的权值
    EdgeNode *edge;

    adjvex[0] = 0;  //0顶点作为最小生成树的根开始遍历，权值为0
    lowcost[0] = 0; //表示0顶点与已确定相连

    //初始化------------------
    for (i = 0; i < head.numVertexes; i++) {
        lowcost[i] = INFINITY;  //先全部初始化为INFINITY
        adjvex[i] = 0;  //先全部初始化为0
    }
    for (edge = head.node[i].first; edge; edge = edge->next){
        lowcost[edge->adjvex] = edge->weight;   //将邻接矩阵第0行所有权值先加入数组
    }

    //构造最小生成树的过程
    for (i = 0; i < head.numVertexes; i++) {
        min = 65535;    //初始化最小权值为65535等不可能数值
        k = 0;  //当前顶点初始化为0
        j = 1;  //从1开始遍历

        //遍历其他全部顶点
        while (j < head.numVertexes) {
            //找出lowcost数组已存储的最小权值
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];   //记录最小权值
                k = j;  //记录最小权值的下标
            }
            j++;
        }

        //打印当前顶点边中权值最小的边
        printf("(%d,%d) ", adjvex[k], k);
        lowcost[k] = 0;//将当前顶点k的权值设为0，表示k顶点与已确定相连

        //逐个遍历k顶点与除已经确定连接顶点外全部顶点的权值
        for (edge = head.node[k].first; edge; edge = edge->next) {
            if (edge->weight < lowcost[edge->adjvex]) {   //判断顶点j与0顶点有路径的点；顶点j与0和k的路径长度
                lowcost[edge->adjvex] = edge->weight;    //如果顶点j与k的路径长度小于与0的路径长度
                adjvex[edge->adjvex] = k;  //讲顶点j与和k的路径设置为与确定相连顶点间权值最小的路径
            }
        }

    }

}


int main() {
    headNode head;

    Create_Adjacencytables(&head);

    MiniSpanTree_Prim(head);

    return 0;
}

最佳答案

月排行榜 / 总排行榜

jhq999

2023-2-23 15:27:04

 if (Vertex->first) {
        Vertex->first = Edge;
    }
    else {
        temp = Vertex->first;//////////Vertex->first为假时
        while (temp->next) {//////(temp->next出错,真假的应该调换过来
            temp = temp->next;
        }
        temp->next = Edge;
    }

    }
    else {
        Vertex->first = Edge;
    }

if (Vertex->first) {
        temp = Vertex->first;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = Edge;
    }
    else {
    Vertex->first = Edge;    
    }

跳转到最佳答案楼层

jhq999

 if (Vertex->first) {
        Vertex->first = Edge;
    }
    else {
        temp = Vertex->first;//////////Vertex->first为假时
        while (temp->next) {//////(temp->next出错,真假的应该调换过来
            temp = temp->next;
        }
        temp->next = Edge;
    }

    }
    else {
        Vertex->first = Edge;
    }

if (Vertex->first) {
        temp = Vertex->first;
        while (temp->next) {
            temp = temp->next;
        }
        temp->next = Edge;
    }
    else {
    Vertex->first = Edge;    
    }

御坂19090

jhq999 发表于 2023-2-23 15:27

可是好像还是错误

jhq999

御坂19090 发表于 2023-2-23 19:51
可是好像还是错误

发个样例过来

御坂19090

就改了一个感叹号

御坂19090

jhq999 发表于 2023-2-23 19:53
发个样例过来

但是这个错误好像还没有到那个！哪里。是其他原因

jhq999

#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 32                        // 最大顶点数
#define INFINITY 65535                // 用65535来代表无穷大
/*6 8
1 2 7
2 4 1
4 5 4
2 5 2
1 5 3
1 6 8
1 3 2
3 6 9*/
int pt[MAXVEX];
typedef struct line
{
    int x,y,w ;
    struct line *next;
}line;
typedef struct headNode
{
    int  pt[MAXVEX],havpt[MAXVEX];
    line ln[MAXVEX],*tree[MAXVEX];
    int ptnum,lnnum;
}headNode;
void create(headNode* hd)
{
    scanf("%d%d",&(hd->ptnum),&(hd->lnnum));
    line* ln=hd->ln,*p=hd->ln;
    for(int i=1;i<=hd->lnnum;i+=1)
    {
        scanf("%d%d%d",&ln[i].x,&ln[i].y,&ln[i].w);
        p=ln;
        while(p->next&&p->next->w<ln[i].w)p=p->next;
        ln[i].next=p->next;
        p->next=&ln[i];
    }
    p=ln;
    while(p->next)
    {
        printf("%d--%d %d\n",p->next->x,p->next->y,p->next->w);
        p=p->next;
    }
}

// 建立邻接表


//Prim算法生成最小生成树
int MiniSpanTree(headNode *hd) {

    int *pt=hd->pt,*hpt=hd->havpt,ct=0,i,min,j;
    line* ln=hd->ln,*p=NULL,*ptmp;
    pt[1]=1;
    hpt[1]=1;
    ct=1;
    j=0;
    while(ct<hd->ptnum)
    {
        min=INFINITY;
        for(i=1,ptmp=NULL,pt[0]=0;pt[i];i+=1)
        {
            p=ln;
            while(p->next)
            {
                j+=1;
                if(pt[i]==p->next->x||pt[i]==p->next->y)
                {
                    if(hpt[p->next->x]&&hpt[p->next->y])
                    {
                        p->next=p->next->next;
                        continue;
                    }
                    else if((min>p->next->w)&&(hpt[p->next->x]||hpt[p->next->y]))
                    {

                            min=p->next->w;
                            if(hpt[p->next->x])pt[0]=p->next->y;
                            else pt[0]=p->next->x;
                            ptmp=p;
                            break;
                    }
                }
               p=p->next;
            }
        }
        if(ptmp->next)
        {
            hd->tree[ct++]=ptmp->next;
            pt[ct]=pt[0];
            hpt[pt[0]]=1;

            ptmp->next=ptmp->next->next;
        }
    }
    return 0;
}
int main()
{
    headNode head={0};
    create(&head);
    MiniSpanTree(&head);
    for(int i=1;head.tree[i];i+=1)
        printf("%d--%d\n",head.tree[i]->x,head.tree[i]->y);

    return 0;
}