/* 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
