这个上面明明已经分配空间了,为什么会这样呀?
#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;
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.data);
head->node.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; //记录顶点的连接;储存所有可接触到的顶点和确定相连顶点间最小权值
int lowcost; // 保存相关顶点间边的权值
EdgeNode *edge;
adjvex = 0;//0顶点作为最小生成树的根开始遍历,权值为0
lowcost = 0; //表示0顶点与已确定相连
//初始化------------------
for (i = 0; i < head.numVertexes; i++) {
lowcost = INFINITY;//先全部初始化为INFINITY
adjvex = 0;//先全部初始化为0
}
for (edge = head.node.first; edge; edge = edge->next){
lowcost = 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 != 0 && lowcost < min) {
min = lowcost; //记录最小权值
k = j;//记录最小权值的下标
}
j++;
}
//打印当前顶点边中权值最小的边
printf("(%d,%d) ", adjvex, k);
lowcost = 0;//将当前顶点k的权值设为0,表示k顶点与已确定相连
//逐个遍历k顶点与除已经确定连接顶点外全部顶点的权值
for (edge = head.node.first; edge; edge = edge->next) {
if (edge->weight < lowcost) { //判断顶点j与0顶点有路径的点;顶点j与0和k的路径长度
lowcost = edge->weight; //如果顶点j与k的路径长度小于与0的路径长度
adjvex = k;//讲顶点j与和k的路径设置为与确定相连顶点间权值最小的路径
}
}
}
}
int main() {
headNode head;
Create_Adjacencytables(&head);
MiniSpanTree_Prim(head);
return 0;
} 本帖最后由 jhq999 于 2023-2-23 15:29 编辑
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 发表于 2023-2-23 15:27
可是好像还是错误 御坂19090 发表于 2023-2-23 19:51
可是好像还是错误
发个样例过来
就改了一个感叹号 jhq999 发表于 2023-2-23 19:53
发个样例过来
但是这个错误好像还没有到那个!哪里。是其他原因 #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;
typedef struct line
{
int x,y,w ;
struct line *next;
}line;
typedef struct headNode
{
intpt,havpt;
line ln,*tree;
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.x,&ln.y,&ln.w);
p=ln;
while(p->next&&p->next->w<ln.w)p=p->next;
ln.next=p->next;
p->next=&ln;
}
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;
hpt=1;
ct=1;
j=0;
while(ct<hd->ptnum)
{
min=INFINITY;
for(i=1,ptmp=NULL,pt=0;pt;i+=1)
{
p=ln;
while(p->next)
{
j+=1;
if(pt==p->next->x||pt==p->next->y)
{
if(hpt&&hpt)
{
p->next=p->next->next;
continue;
}
else if((min>p->next->w)&&(hpt||hpt))
{
min=p->next->w;
if(hpt)pt=p->next->y;
else pt=p->next->x;
ptmp=p;
break;
}
}
p=p->next;
}
}
if(ptmp->next)
{
hd->tree=ptmp->next;
pt=pt;
hpt]=1;
ptmp->next=ptmp->next->next;
}
}
return 0;
}
int main()
{
headNode head={0};
create(&head);
MiniSpanTree(&head);
for(int i=1;head.tree;i+=1)
printf("%d--%d\n",head.tree->x,head.tree->y);
return 0;
}
页:
[1]