/*
- 将node链接到list的末尾
*/
static void link_last(ENode *list, ENode *node)
{
ENode *p=list ;
while(p->next_edge)
p = p->next_edge;
p->next_edge = node;
}
编译会提示这方面里的错误
0XFEFEFFEFE6表示明指针所指向的空间已经被释放
咋办
求大神解决
完整代码：
#include
#include
#include
#include
#define MAX 100
#define INF (~(0x1<
#define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
#define LENGTH(a) (sizeof(a)/sizeof(a[0]))
// 邻接表中表对应的链表的顶点
typedef struct _ENode
{
int ivex; // 该边的顶点的位置
int weight; // 该边的权
struct _ENode *next_edge; // 指向下一条弧的指针
}ENode, *PENode;
// 邻接表中表的顶点
typedef struct _VNode
{
char data; // 顶点信息
ENode *first_edge; // 指向第一条依附该顶点的弧
}VNode;
// 邻接表
typedef struct _LGraph
{
int vexnum; // 图的顶点的数目
int edgnum; // 图的边的数目
VNode vexs[MAX];
}LGraph;
/*
- 返回ch在matrix矩阵中的位置 */ static int get_position(LGraph G, char ch) { int i; for(i=0; i<G.vexnum; i++) if(G.vexs[i].data==ch) return i; return -1; }
/*
-
读取一个输入字符
*/
static char read_char()
{
char ch;do {
ch = getchar();
} while(!isLetter(ch));return ch;
}
/*
- 将node链接到list的末尾 */ static void link_last(ENode *list, ENode *node) { ENode *p=list ; while(p->next_edge) p = p->next_edge; p->next_edge = node; }
/*
-
创建邻接表对应的图(自己输入)
/
LGraph create_lgraph()
{
char c1, c2;
int v, e;
int i, p1, p2;
int weight;
ENode node1, *node2;
LGraph pG;// 输入"顶点数"和"边数"
printf("输入顶点数: ");
scanf("%d", &v);
printf("输入边数: ");
scanf("%d", &e);
if ( v < 1 || e < 1 || (e > (v * (v-1))))
{
printf("input error: invalid parameters!\n");
return NULL;
}if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
return NULL;
memset(pG, 0, sizeof(LGraph));// 初始化"顶点数"和"边数"
pG->vexnum = v;
pG->edgnum = e;
// 初始化"邻接表"的顶点
for(i=0; ivexnum; i++)
{
printf("顶点(%d): ", i);
pG->vexs[i].data = read_char();
pG->vexs[i].first_edge = NULL;
}// 初始化"邻接表"的边
for(i=0; iedgnum; i++)
{
// 读取边的起始顶点,结束顶点,权
printf("边(%d): ", i);
c1 = read_char();
c2 = read_char();
scanf("%d", &weight);p1 = get_position(*pG, c1); p2 = get_position(*pG, c2); // 初始化node1 node1 = (ENode*)malloc(sizeof(ENode)); node1->ivex = p2; node1->weight = weight; // 将node1链接到"p1所在链表的末尾" if(pG->vexs[p1].first_edge == NULL) pG->vexs[p1].first_edge = node1; else{ link_last(pG->vexs[p1].first_edge, node1); } // 初始化node2 node2 = (ENode*)malloc(sizeof(ENode)); node2->ivex = p1; node2->weight = weight; // 将node2链接到"p2所在链表的末尾" if(pG->vexs[p2].first_edge == NULL) pG->vexs[p2].first_edge = node2; else{ link_last(pG->vexs[p2].first_edge, node2);} free(node1); free(node2);}
return pG;
}
// 边的结构体
typedef struct _edata
{
char start; // 边的起点
char end; // 边的终点
int weight; // 边的权重
}EData;
/*
-
打印邻接表图
*/
void print_lgraph(LGraph G)
{
int i;
ENode *node;printf("List Graph:\n");
for (i = 0; i < G.vexnum; i++)
{
printf("%d(%c): ", i, G.vexs[i].data);
node = G.vexs[i].first_edge;
while (node != NULL)
{
printf("%d(%c) ", node->ivex, G.vexs[node->ivex].data);
node = node->next_edge;
}
printf("\n");
}
}
/*
-
获取G中边的权值；若start和end不是连通的，则返回无穷大。
*/
int getWeight(LGraph G, int start, int end)
{
ENode *node;if (start==end)
return 0;node = G.vexs[start].first_edge;
while (node!=NULL)
{
if (end==node->ivex)
return node->weight;
node = node->next_edge;
}return INF;
}
/*
-
获取图中的边
/
EData get_edges(LGraph G)
{
int i;
int index=0;
ENode *node;
EData *edges;edges = (EData*)malloc(G.edgnum*sizeof(EData));
for (i=0; i {
node = G.vexs[i].first_edge;
while (node != NULL)
{
if (node->ivex > i)
{
edges[index].start = G.vexs[i].data; // 起点
edges[index].end = G.vexs[node->ivex].data; // 终点
edges[index].weight = node->weight; // 权
index++;
}
node = node->next_edge;
}
}return edges;
}
/*
-
对边按照权值大小进行排序(由小到大)
/
void sorted_edges(EData edges, int elen)
{
int i,j;for (i=0; i {
for (j=i+1; j {
if (edges[i].weight > edges[j].weight)
{
// 交换"第i条边"和"第j条边"
EData tmp = edges[i];
edges[i] = edges[j];
edges[j] = tmp;
}
}
}
}
/*
- 获取i的终点 */ int get_end(int vends[], int i) { while (vends[i] != 0) i = vends[i]; return i; }
/*
-
克鲁斯卡尔（Kruskal)最小生成树
*/
void kruskal(LGraph G)
{
int i,m,n,p1,p2;
int length;
int index = 0; // rets数组的索引
int vends[MAX]={0}; // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
EData rets[MAX]; // 结果数组，保存kruskal最小生成树的边
EData *edges; // 图对应的所有边// 获取"图中所有的边"
edges = get_edges(G);
// 将边按照"权"的大小进行排序(从小到大)
sorted_edges(edges, G.edgnum);for (i=0; i<G.edgnum; i++)
{
p1 = get_position(G, edges[i].start); // 获取第i条边的"起点"的序号
p2 = get_position(G, edges[i].end); // 获取第i条边的"终点"的序号m = get_end(vends, p1); // 获取p1在"已有的最小生成树"中的终点 n = get_end(vends, p2); // 获取p2在"已有的最小生成树"中的终点 // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的终点为n rets[index++] = edges[i]; // 保存结果 }}
free(edges);// 统计并打印"kruskal最小生成树"的信息
length = 0;
for (i = 0; i < index; i++)
length += rets[i].weight;
printf("Kruskal=%d: ", length);
for (i = 0; i < index; i++)
printf("(%c,%c) ", rets[i].start, rets[i].end);
printf("\n");
}
void main()
{
LGraph* pG;
pG = create_lgraph();
print_lgraph(*pG); // 打印图
kruskal(*pG); // kruskal算法生成最小生成树
}
