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

御坂19090

1. #include <stdio.h>
   
2. 
   
3. #define scanf scanf_s
   
4. #define MAXVEX 8                        // 最大顶点数
   
5. #define INFINITY 65535                // 用65535来代表无穷大
   
6. 
   
7. //表示元素的数据类型
   
8. typedef char ElemType;
   
9. 
   
10. //顶点节点
    
11. typedef struct VertexNode {
    
12.     ElemType data;
    
13.     struct EdgeNode *first;
    
14. }VertexNode;
    
15. 
    
16. //边节点
    
17. typedef struct EdgeNode {
    
18.     int adjvex; //邻接域
    
19.     int weight; //权
    
20.     struct EdgeNode *next;  //指向下一个邻接点
    
21. }EdgeNode;
    
22. 
    
23. //头节点；记录节点数和边数
    
24. typedef struct headNode {
    
25.     VertexNode node[MAXVEX];
    
26.     int numVertexes, numEdges;
    
27. }headNode;
    
28. 
    
29. //创建边节点
    
30. void create_Edge(struct VertexNode* Vertex, int number, int weight) {
    
31.     struct EdgeNode* Edge, * temp;
    
32. 
    
33.     Edge = (struct EdgeNode *)malloc(sizeof(struct EdgeNode));
    
34.     Edge->adjvex = number;
    
35.     Edge->weight = weight;
    
36.     Edge->next = NULL;
    
37. 
    
38.     if (Vertex->first) {
    
39.         Vertex->first = Edge;
    
40.     }
    
41.     else {
    
42.         temp = Vertex->first;
    
43.         while (temp->next) {
    
44.             temp = temp->next;
    
45.         }
    
46.         temp->next = Edge;
    
47.     }
    
48. }
    
49. 
    
50. // 建立邻接表
    
51. void Create_Adjacencytables(headNode * head){
    
52.     int i, j, k, w;
    
53. 
    
54.     printf("请输入顶点数和边数：\n");
    
55.     scanf("%d %d", &head->numVertexes, &head->numEdges);  //获取边的顶点数和边数
    
56.     getchar();  //吸收换行符
    
57. 
    
58.     //读取顶点信息
    
59.     for (i = 0; i < head->numVertexes; i++) {
    
60.         scanf("%c", &head->node[i].data);
    
61.         head->node[i].first = NULL;                // 初始化置为空表
    
62.         getchar();  //吸收换行符
    
63.     }
    
64. 
    
65.     //读取边节点信息
    
66.     printf("请输入边(i,j)的i,j和对应的权w；格式(i j w):\n");
    
67.     for (i = 0; i < head->numEdges; i++) {
    
68.         scanf_s("%d %d %d", &j, &k, &w);
    
69.         create_Edge(head->node + j, k, w);
    
70.     }
    
71. }
    
72. 
    
73. //Prim算法生成最小生成树
    
74. void MiniSpanTree_Prim(headNode head) {
    
75.     int min, i, j, k;
    
76.     int adjvex[MAXVEX];     //记录顶点的连接；储存所有可接触到的顶点和确定相连顶点间最小权值
    
77.     int lowcost[MAXVEX];    // 保存相关顶点间边的权值
    
78.     EdgeNode *edge;
    
79. 
    
80.     adjvex[0] = 0;  //0顶点作为最小生成树的根开始遍历，权值为0
    
81.     lowcost[0] = 0; //表示0顶点与已确定相连
    
82. 
    
83.     //初始化------------------
    
84.     for (i = 0; i < head.numVertexes; i++) {
    
85.         lowcost[i] = INFINITY;  //先全部初始化为INFINITY
    
86.         adjvex[i] = 0;  //先全部初始化为0
    
87.     }
    
88.     for (edge = head.node[i].first; edge; edge = edge->next){
    
89.         lowcost[edge->adjvex] = edge->weight;   //将邻接矩阵第0行所有权值先加入数组
    
90.     }
    
91. 
    
92.     //构造最小生成树的过程
    
93.     for (i = 0; i < head.numVertexes; i++) {
    
94.         min = 65535;    //初始化最小权值为65535等不可能数值
    
95.         k = 0;  //当前顶点初始化为0
    
96.         j = 1;  //从1开始遍历
    
97. 
    
98.         //遍历其他全部顶点
    
99.         while (j < head.numVertexes) {
    
100.             //找出lowcost数组已存储的最小权值
     
101.             if (lowcost[j] != 0 && lowcost[j] < min) {
     
102.                 min = lowcost[j];   //记录最小权值
     
103.                 k = j;  //记录最小权值的下标
     
104.             }
     
105.             j++;
     
106.         }
     
107. 
     
108.         //打印当前顶点边中权值最小的边
     
109.         printf("(%d,%d) ", adjvex[k], k);
     
110.         lowcost[k] = 0;//将当前顶点k的权值设为0，表示k顶点与已确定相连
     
111. 
     
112.         //逐个遍历k顶点与除已经确定连接顶点外全部顶点的权值
     
113.         for (edge = head.node[k].first; edge; edge = edge->next) {
     
114.             if (edge->weight < lowcost[edge->adjvex]) {   //判断顶点j与0顶点有路径的点；顶点j与0和k的路径长度
     
115.                 lowcost[edge->adjvex] = edge->weight;    //如果顶点j与k的路径长度小于与0的路径长度
     
116.                 adjvex[edge->adjvex] = k;  //讲顶点j与和k的路径设置为与确定相连顶点间权值最小的路径
     
117.             }
     
118.         }
     
119. 
     
120.     }
     
121. 
     
122. }
     
123. 
     
124. 
     
125. int main() {
     
126.     headNode head;
     
127. 
     
128.     Create_Adjacencytables(&head);
     
129. 
     
130.     MiniSpanTree_Prim(head);
     
131. 
     
132.     return 0;
     
133. }

复制代码

最佳答案

月排行榜 / 总排行榜

jhq999

2023-2-23 15:27:04

1. if (Vertex->first) {
   
2.         Vertex->first = Edge;
   
3.     }
   
4.     else {
   
5.         temp = Vertex->first;//////////Vertex->first为假时
   
6.         while (temp->next) {//////(temp->next出错,真假的应该调换过来
   
7.             temp = temp->next;
   
8.         }
   
9.         temp->next = Edge;
   
10.     }
    
11. 
    
12.     }
    
13.     else {
    
14.         Vertex->first = Edge;
    
15.     }

复制代码

1. if (Vertex->first) {
   
2.         temp = Vertex->first;
   
3.         while (temp->next) {
   
4.             temp = temp->next;
   
5.         }
   
6.         temp->next = Edge;
   
7.     }
   
8.     else {
   
9.     Vertex->first = Edge;   
   
10.     }

复制代码

跳转到最佳答案楼层

jhq999

1. if (Vertex->first) {
   
2.         Vertex->first = Edge;
   
3.     }
   
4.     else {
   
5.         temp = Vertex->first;//////////Vertex->first为假时
   
6.         while (temp->next) {//////(temp->next出错,真假的应该调换过来
   
7.             temp = temp->next;
   
8.         }
   
9.         temp->next = Edge;
   
10.     }
    
11. 
    
12.     }
    
13.     else {
    
14.         Vertex->first = Edge;
    
15.     }

复制代码

1. if (Vertex->first) {
   
2.         temp = Vertex->first;
   
3.         while (temp->next) {
   
4.             temp = temp->next;
   
5.         }
   
6.         temp->next = Edge;
   
7.     }
   
8.     else {
   
9.     Vertex->first = Edge;   
   
10.     }

复制代码

御坂19090

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

可是好像还是错误

jhq999

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

发个样例过来

御坂19090

就改了一个感叹号

御坂19090

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

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

jhq999

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #define MAXVEX 32                        // 最大顶点数
   
4. #define INFINITY 65535                // 用65535来代表无穷大
   
5. /*6 8
   
6. 1 2 7
   
7. 2 4 1
   
8. 4 5 4
   
9. 2 5 2
   
10. 1 5 3
    
11. 1 6 8
    
12. 1 3 2
    
13. 3 6 9*/
    
14. int pt[MAXVEX];
    
15. typedef struct line
    
16. {
    
17.     int x,y,w ;
    
18.     struct line *next;
    
19. }line;
    
20. typedef struct headNode
    
21. {
    
22.     int  pt[MAXVEX],havpt[MAXVEX];
    
23.     line ln[MAXVEX],*tree[MAXVEX];
    
24.     int ptnum,lnnum;
    
25. }headNode;
    
26. void create(headNode* hd)
    
27. {
    
28.     scanf("%d%d",&(hd->ptnum),&(hd->lnnum));
    
29.     line* ln=hd->ln,*p=hd->ln;
    
30.     for(int i=1;i<=hd->lnnum;i+=1)
    
31.     {
    
32.         scanf("%d%d%d",&ln[i].x,&ln[i].y,&ln[i].w);
    
33.         p=ln;
    
34.         while(p->next&&p->next->w<ln[i].w)p=p->next;
    
35.         ln[i].next=p->next;
    
36.         p->next=&ln[i];
    
37.     }
    
38.     p=ln;
    
39.     while(p->next)
    
40.     {
    
41.         printf("%d--%d %d\n",p->next->x,p->next->y,p->next->w);
    
42.         p=p->next;
    
43.     }
    
44. }
    
45. 
    
46. // 建立邻接表
    
47. 
    
48. 
    
49. //Prim算法生成最小生成树
    
50. int MiniSpanTree(headNode *hd) {
    
51. 
    
52.     int *pt=hd->pt,*hpt=hd->havpt,ct=0,i,min,j;
    
53.     line* ln=hd->ln,*p=NULL,*ptmp;
    
54.     pt[1]=1;
    
55.     hpt[1]=1;
    
56.     ct=1;
    
57.     j=0;
    
58.     while(ct<hd->ptnum)
    
59.     {
    
60.         min=INFINITY;
    
61.         for(i=1,ptmp=NULL,pt[0]=0;pt[i];i+=1)
    
62.         {
    
63.             p=ln;
    
64.             while(p->next)
    
65.             {
    
66.                 j+=1;
    
67.                 if(pt[i]==p->next->x||pt[i]==p->next->y)
    
68.                 {
    
69.                     if(hpt[p->next->x]&&hpt[p->next->y])
    
70.                     {
    
71.                         p->next=p->next->next;
    
72.                         continue;
    
73.                     }
    
74.                     else if((min>p->next->w)&&(hpt[p->next->x]||hpt[p->next->y]))
    
75.                     {
    
76. 
    
77.                             min=p->next->w;
    
78.                             if(hpt[p->next->x])pt[0]=p->next->y;
    
79.                             else pt[0]=p->next->x;
    
80.                             ptmp=p;
    
81.                             break;
    
82.                     }
    
83.                 }
    
84.                p=p->next;
    
85.             }
    
86.         }
    
87.         if(ptmp->next)
    
88.         {
    
89.             hd->tree[ct++]=ptmp->next;
    
90.             pt[ct]=pt[0];
    
91.             hpt[pt[0]]=1;
    
92. 
    
93.             ptmp->next=ptmp->next->next;
    
94.         }
    
95.     }
    
96.     return 0;
    
97. }
    
98. int main()
    
99. {
    
100.     headNode head={0};
     
101.     create(&head);
     
102.     MiniSpanTree(&head);
     
103.     for(int i=1;head.tree[i];i+=1)
     
104.         printf("%d--%d\n",head.tree[i]->x,head.tree[i]->y);
     
105. 
     
106.     return 0;
     
107. }

复制代码