| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1627 人关注过本帖
标题:清华严奶奶的,在邻接表上 建立无向图的深度优先生产森林算法,为什么 结果 ...
只看楼主 加入收藏
wtyj112
Rank: 1
等 级:新手上路
帖 子:222
专家分:0
注 册:2007-5-9
结帖率:85.71%
收藏
 问题点数:0 回复次数:5 
清华严奶奶的,在邻接表上 建立无向图的深度优先生产森林算法,为什么 结果不对?

/* ALGraph.c */
/*邻接表 存储图 */
/*2007年 9月 19日 */
/*详细见清华大学出版社 严蔚敏 数据结构 c语言版 p163 */

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20
int visited[MAX_VERTEX_NUM]; /*定义全局变量 纪录是否访问图节点*/

typedef struct ArcNode{
int adjvexx;
struct ArcNode *nextarc;
}ArcNode; /*表节点*/

typedef struct VNode{
char data;
struct ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM]; /*头节点*/

typedef struct ALGraph{
AdjList vertices;
int vexnum, arcnum;
int kind;
}ALGraph; /*邻接表*/

typedef struct CSNode{
char data;
struct CSNode *firstchild, *nextsibling;
}CSNode; /*二叉森林结构*/


void CreateAdjList(ALGraph *p) /*生成头节点数组*/
{
int i,j,num1;
ArcNode *p0 , *p1, *p2;

for (i = 0; i < p->vexnum; i++ )
{
printf("Input the VNode: "); /*输入头节点*/
scanf ("%s", &((p->vertices+i)->data));
(p->vertices+i) -> firstarc = NULL;
}
for (i = 0; i < p->vexnum; i++ ) /* 生成 头节点的 表节点 */
{
printf("Input the num of ArcNode:");
scanf ("%d", &num1); /*输入各个头节点的表节点数*/
for (j = 0; j < num1; j++)
{
p2 = (ArcNode*)malloc(sizeof(ArcNode)); /*分配一个表节点在内存*/
printf("Input the ArcNode:");
scanf("%d", &(p2 -> adjvexx)); /*输入表节点信息*/
p2 -> nextarc = NULL;
if (j == 0)
p0 = p1 = p2;
else
{
p1 -> nextarc = p2;
p1 = p2;
}
}
if (num1 != 0)
((p->vertices)+i) -> firstarc = p0;
}

}


void ShowAdjList(ALGraph *p) /*打印图的邻接表*/
{
int i;
ArcNode *p3;

for (i = 0; i < p->vexnum; i++)
{
printf("%c", (p->vertices+i)->data);
p3 = (p->vertices+i) -> firstarc;
while (p3 != NULL)
{
printf(" -> %d ", p3->adjvexx);
p3 = p3 -> nextarc;
}
printf("\n");
}
}

void VisitFunc(int v) /*访问 函数*/
{
printf("%d->",v);
}

int FirstAdjVex(ALGraph *p, int i) /*该函数返回顶点i的第一个邻接点 如果没有就返回0*/
{
ArcNode *pl;
pl = ((p->vertices+i)->firstarc);
if(pl != NULL)
return (pl->adjvexx);
else
return 0;
}

int NextAdjVex(ALGraph *p, int i, int w)/*返回 顶点i 中邻接点 w后一个邻接点 */
{
ArcNode *pl;
pl = (p->vertices+i)->firstarc;
if (pl != NULL)
{
while (pl->adjvexx != w)
pl = pl->nextarc;
if (pl->nextarc != NULL)
{
pl = pl->nextarc;
return pl->adjvexx;
}
else
return -1;

}
else
return -1;
}

void DFSTree(ALGraph *p, int v, CSNode *p1)
{
int first, w;
CSNode *p2, *q;

visited[v] = 1;
first = 1;
for (w = FirstAdjVex(p, v); w >= 0; w = NextAdjVex(p, v, w))
{
if (!visited[w])
{
p2 = (CSNode*) malloc (sizeof(CSNode));
p2->data = (p->vertices+v)->data;
p2->firstchild = p2->nextsibling = NULL;
if (first)
{
p1->firstchild = p2;
first = 0;
}
else
q->nextsibling = p2;
q = p2;
DFSTree(p, w, q);
}
}
}

CSNode * DFSForest(ALGraph *p)
{
CSNode *T = NULL;
int v;
CSNode *p1, *q;

for (v = 0; v < p->vexnum; ++v)
visited[v] = 0;
for (v = 0; v < p->vexnum; ++v)
{
if (!visited[v])
{
p1 = (CSNode*) malloc (sizeof(CSNode));
p1->data = (p->vertices+v)->data;
p1->firstchild = p1->nextsibling = NULL;
if (!T)
T = p1;
else
q->nextsibling = p1;
q = p1;
DFSTree(p, v, p1);
}
}
return T;
}

void ShowDFSForest(CSNode *pc) /*打印森林 一排兄弟 一排兄弟的打 森林是 左第一个孩子 右兄弟结构*/
{
CSNode *pc1;

while (pc->firstchild)
{
pc1 = pc->firstchild;
while (pc)
{
printf("%c", pc->data);
pc = pc->nextsibling;
}
pc = pc1;
}
while (pc->nextsibling)
{
printf("%c", pc->data);
pc = pc->nextsibling;
}

}


void main()
{
ALGraph *p;
CSNode *pc;
ALGraph ALGrap;

p = &ALGrap;

printf("Intput the num of vexnum:");/*输入顶点数*/
scanf("%d", &(p->vexnum));

printf("Intput the num of aecnum:");/*输入弧数*/
scanf("%d", &(p->arcnum));

CreateAdjList(p); /*创建邻接表*/
ShowAdjList(p); /*打印邻接表*/
pc = DFSForest(p);
ShowDFSForest(pc);

}

我用vc6调试 跟踪递归 跟的我头的晕了 实验数据用了 严奶奶书上的 图7。14 p171

搜索更多相关主题的帖子: 清华 算法 森林 奶奶 深度 
2007-09-22 17:04
wtyj112
Rank: 1
等 级:新手上路
帖 子:222
专家分:0
注 册:2007-5-9
收藏
得分:0 

程序头的 描述是错的 我是在 邻接表基础上扩展的 所以描述没改

其中几个关键函数是
详细见 严奶奶的书 p171
大家别说没这本书哈


计算机之路是痛苦并快乐着的!!
2007-09-22 17:08
wtyj112
Rank: 1
等 级:新手上路
帖 子:222
专家分:0
注 册:2007-5-9
收藏
得分:0 

由于匆忙有些地方 注释没写好 请大家原谅 和 理解

算法基本上是严奶奶的 除了邻接表


计算机之路是痛苦并快乐着的!!
2007-09-22 17:11
myisgood
Rank: 1
等 级:新手上路
帖 子:55
专家分:0
注 册:2006-12-25
收藏
得分:0 

我用的是 李葆春的拉~~ 不一样了 ~
等我11.3过了 如果还没有人帮你解决~
我来帮你拉~-_-

2007-09-22 19:03
wtyj112
Rank: 1
等 级:新手上路
帖 子:222
专家分:0
注 册:2007-5-9
收藏
得分:0 

错误找到了 就是本该生成w的树节点 写成了 生成v的树节点
错了一个字符
我郁闷搞的闷着头 单步调试 跟踪 递归 头都晕了
那位大哥有 什么好方法 理解和 处理递归 讲一下啊!!
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20
int visited[MAX_VERTEX_NUM]; /*定义全局变量 纪录是否访问图节点*/

typedef struct ArcNode{
int adjvexx;
struct ArcNode *nextarc;
}ArcNode; /*表节点*/

typedef struct VNode{
char data;
struct ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM]; /*头节点*/

typedef struct ALGraph{
AdjList vertices;
int vexnum, arcnum;
int kind;
}ALGraph; /*邻接表*/

typedef struct CSNode{
char data;
struct CSNode *firstchild, *nextsibling;
}CSNode; /*二叉森林结构*/


void CreateAdjList(ALGraph *p) /*生成头节点数组*/
{
int i,j,num1;
ArcNode *p0 , *p1, *p2;

for (i = 0; i < p->vexnum; i++ )
{
printf("Input the VNode: "); /*输入头节点*/
scanf ("%s", &((p->vertices+i)->data));
(p->vertices+i) -> firstarc = NULL;
}
for (i = 0; i < p->vexnum; i++ ) /* 生成 头节点的 表节点 */
{
printf("Input the num of ArcNode:");
scanf ("%d", &num1); /*输入各个头节点的表节点数*/
for (j = 0; j < num1; j++)
{
p2 = (ArcNode*)malloc(sizeof(ArcNode)); /*分配一个表节点在内存*/
printf("Input the ArcNode:");
scanf("%d", &(p2 -> adjvexx)); /*输入表节点信息*/
p2 -> nextarc = NULL;
if (j == 0)
p0 = p1 = p2;
else
{
p1 -> nextarc = p2;
p1 = p2;
}
}
if (num1 != 0)
((p->vertices)+i) -> firstarc = p0;
}

}


void ShowAdjList(ALGraph *p) /*打印图的邻接表*/
{
int i;
ArcNode *p3;

for (i = 0; i < p->vexnum; i++)
{
printf("%c", (p->vertices+i)->data);
p3 = (p->vertices+i) -> firstarc;
while (p3 != NULL)
{
printf(" -> %d ", p3->adjvexx);
p3 = p3 -> nextarc;
}
printf("\n");
}
}

void VisitFunc(int v) /*访问 函数*/
{
printf("%d->",v);
}

int FirstAdjVex(ALGraph *p, int i) /*该函数返回顶点i的第一个邻接点 如果没有就返回0*/
{
ArcNode *pl;
pl = ((p->vertices+i)->firstarc);
if(pl != NULL)
return (pl->adjvexx);
else
return 0;
}

int NextAdjVex(ALGraph *p, int i, int w)/*返回 顶点i 中邻接点 w后一个邻接点 */
{
ArcNode *pl;
pl = (p->vertices+i)->firstarc;
if (pl != NULL)
{
while (pl->adjvexx != w)
pl = pl->nextarc;
if (pl->nextarc != NULL)
{
pl = pl->nextarc;
return pl->adjvexx;
}
else
return -1;

}
else
return -1;
}

void DFSTree(ALGraph *p, int v, CSNode *p1)
{
int first, w;
CSNode *p2, *q;

visited[v] = 1;
first = 1;
for (w = FirstAdjVex(p, v); w >= 0; w = NextAdjVex(p, v, w))
{
if (!visited[w])
{
p2 = (CSNode*) malloc (sizeof(CSNode));
p2->data = (p->vertices+v)->data;/*就是这个地方 错了应该改成w 找了我几个小时才找到 都郁闷死我了*/
p2->firstchild = p2->nextsibling = NULL;
if (first)
{
p1->firstchild = p2;
first = 0;
}
else
q->nextsibling = p2;
q = p2;
DFSTree(p, w, q);
}
}
}

CSNode * DFSForest(ALGraph *p)
{
CSNode *T = NULL;
int v;
CSNode *p1, *q;

for (v = 0; v < p->vexnum; ++v)
visited[v] = 0;
for (v = 0; v < p->vexnum; ++v)
{
if (!visited[v])
{
p1 = (CSNode*) malloc (sizeof(CSNode));
p1->data = (p->vertices+v)->data;
p1->firstchild = p1->nextsibling = NULL;
if (!T)
T = p1;
else
q->nextsibling = p1;
q = p1;
DFSTree(p, v, p1);
}
}
return T;
}

void ShowDFSForest(CSNode *pc) /*顺便改一下遍历森林算法 这个是递归算法说实话我对递归没好感*/
{
if (pc)
printf("%c", pc->data);
if (pc->firstchild)
ShowDFSForest(pc->firstchild);
if (pc->nextsibling)
ShowDFSForest(pc->nextsibling);
}


void main()
{
ALGraph *p;
CSNode *pc;
ALGraph ALGrap;

p = &ALGrap;

printf("Intput the num of vexnum:");/*输入顶点数*/
scanf("%d", &(p->vexnum));

printf("Intput the num of aecnum:");/*输入弧数*/
scanf("%d", &(p->arcnum));

CreateAdjList(p); /*创建邻接表*/
ShowAdjList(p); /*打印邻接表*/
pc = DFSForest(p);
ShowDFSForest(pc);

}


计算机之路是痛苦并快乐着的!!
2007-09-22 19:06
wtyj112
Rank: 1
等 级:新手上路
帖 子:222
专家分:0
注 册:2007-5-9
收藏
得分:0 
回复:(myisgood) 我用的是 李葆春的拉~~ 不一样了...
11。3是什么啊?

计算机之路是痛苦并快乐着的!!
2007-09-22 19:40
快速回复:清华严奶奶的,在邻接表上 建立无向图的深度优先生产森林算法,为什么 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019486 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved