/**//*
标题：<<系统设计师>>应试编程实例-[图程序设计]
作者：成晓旭
时间：2002年09月06日(16:30:00-17:16:00)
完成图的创建函数、顺序遍历函数
时间：2002年09月08日(21:30:00-22:35:00)
完成图的深度优先遍历函数[非堆栈、堆栈实现]
*/
#include "stdio.h"
#include "stdlib.h"
//如:FROMHEAD = 1，则用头插法;否则:则用尾插法
#define FROMHEAD 1
/**//*
如:HASHEAD 被定义，则各顶点的邻接点链中<带起始顶点>;
否则:各顶点的邻接点链中<不带起始顶点>;
*/
#define NODE_NUM 5
#ifdef HASHEAD
//<带起始顶点>
int GraphNode[NODE_NUM][3] = ...{...{1,'A',4},...{2,'B',4},...{3,'C',5},...{4,'D',5},...{5,'E',3}};
int ConnectTable[] = ...{0,1,2,3,1,0,2,3,2,0,1,3,4,3,0,1,2,4,4,2,3};
#else
//<不带起始顶点>
int GraphNode[NODE_NUM][3] = ...{...{1,'A',3},...{2,'B',3},...{3,'C',4},...{4,'D',4},...{5,'E',2}};
int ConnectTable[] = ...{1,2,3,0,2,3,0,1,3,4,0,1,2,4,2,3};
#endif
//邻接表中图各顶点结构类型定义
#define gVertexNode struct gVertexNode
gVertexNode
...{
int order; //顶点在图中的序号
int data; //顶点的数据域
gVertexNode *link; //指向顶点的下一个邻接顶点节点的指针
};
//邻接表中图各顶点的遍历头节点结构类型定义
#define gHeadNode struct gHeadNode
gHeadNode
...{
int vcount; //邻接链表的节点数目[即当前顶点的邻接顶点个数]
//int order; //顶点在图中的序号
int data; //顶点的数据域
gVertexNode *firstnode; //指向邻接表的首顶点节点的指针
};
/**//*
创建以邻接表方式存储的图
参数描述：
gHeadNode HeadNode 图的邻接存储的头节点数组
int max：图的顶点个数
int fromhead：插入邻接占点的方式
fromhead=1 头插入方式
fromhead=0 尾插入方式
*/
void CreateGraph(gHeadNode HeadNode[],int max,int fromhead)
...{
gVertexNode *p,*tail; //当前顶点节点及邻接表当前节点的邻接链表的尾节点
int i,j,k; //i,j为循环计数器,k为当前顶点的邻接顶点数目
for(i=0;i<max;i++)
...{
HeadNode[i].vcount = GraphNode[i][2];
HeadNode[i].data = GraphNode[i][1];
HeadNode[i].firstnode = NULL;
//printf(" 顶点[%c]有[%d]个邻接点！ ",HeadNode[i].data,HeadNode[i].vcount);
}
for(i=0,k=0;i<max;i++)
...{
for(j=0;j<HeadNode[i].vcount;j++)
...{
//创建图的顶点节点
p = (gVertexNode *)malloc(sizeof(gVertexNode));
if(p==NULL)
...{
exit(1);
}
else
...{
//图的新顶点赋值
p->order = GraphNode[ConnectTable[k+j]][0];
p->data = GraphNode[ConnectTable[k+j]][1];
p->link = NULL;
if(fromhead)
...{//新节点放在最前面<紧接头节点的后面>头插法
p->link = HeadNode[i].firstnode;
HeadNode[i].firstnode = p;
}
else
...{//新节点放在最后面<紧接最后一个表节点的后面>尾插法
if(HeadNode[i].firstnode == NULL)
...{//插入第一个节点
HeadNode[i].firstnode = p;
tail = p;
}
else
...{//插入非第一个节点[直接接到最后一个节点之后]
tail->link = p;
tail = p;
}
}
}
}
//移动关联表计数位置“指针”
k = k + HeadNode[i].vcount;
}
}
/**//*
顺序访问图中的各个节点[以创建的邻接表的头节点数组前后顺序]
参数描述：
gHeadNode HeadNode 图的邻接存储的头节点数组
int max：图的顶点个数
*/
void Sequence_Journey(gHeadNode HeadNode[],int max)
...{
gVertexNode *p;
int i;
printf("以创建的邻接表的头节点数组前后顺序访问的图： ");
for(i=0;i<max;i++)
...{
p = HeadNode[i].firstnode;
//printf(" 顶点[%c]的[%d]个邻接点： ",HeadNode[i].data,HeadNode[i].vcount);
while(p != NULL)
...{
printf("顶点[%d][%c]",p->order,p->data);
p = p->link;
}
printf(" ");
}
}
//图的[深度优先遍历]算法<非堆栈实现算法>
void nsDeepthFirst_Journey(gHeadNode HeadNode[],int max)
...{
gVertexNode *p; //顶点
int visited[NODE_NUM]; //0：未访问 1：已访问
int i;
printf("图的[深度优先遍历]结果<非堆栈实现>: ");
for(i=0;i<max;i++) //设置所有的顶点未访问标志
visited[i] = 0;
for(i=0;i<max;i++)
...{
p = HeadNode[i].firstnode; //指向当前访问顶点
//printf("顶点[%d][%c]",p->order,p->data);
while(p != NULL) //如果顶点有邻接顶点
...{
if(visited[p->order] == 0)
...{//当前顶点的邻接顶点还未访问
printf("顶点[%d][%c]",p->order,p->data);
visited[p->order] = 1;
}
p = p->link; //移向下一个顶点
}
}
}
//图的[深度优先遍历]算法<堆栈实现算法>
void DeepthFirst_Journey(gHeadNode HeadNode[],int max)
...{
gVertexNode *p; //顶点
gVertexNode *vstack[NODE_NUM+1]; //顶点堆栈
int visited[NODE_NUM+1]; //0：未访问 1：已访问
int i,top; //循环计数器和堆栈指针
printf("图的[深度优先遍历]结果<堆栈实现>: ");
for(i=0;i<=max;i++) //设置所有的顶点未访问标志
visited[i] = 0;
for(i=0;i<max;i++)
...{
top = 1;
vstack[top] = HeadNode[i].firstnode;//将本次访问的起始节点进栈，以便将来正确返回
while(top != 0) //堆栈不为空
...{
p = vstack[top]; //取堆栈中的栈顶元素
while((p != NULL) && (visited[p->order] == 1)) //还有邻接顶点，且已被访问
p = p->link;
if(p == NULL) //当前顶点没有邻接顶点，或有，但都已经被访问过
top--; //完成退栈
else
...{//否则，则访问之
printf("顶点[%d][%c]",p->order,p->data);
visited[p->order] = 1;
vstack[++top] = p; //访问顶点进栈
}
}
}
}
int main(int argc, char* argv[])
...{
gHeadNode HeadNodeArray[NODE_NUM];
int InsertMode = -1;
while(InsertMode != 0 && InsertMode != 1)
...{
printf("请输入顶点的插入方式[0尾插入法:/1:头插入法]");
scanf("%d",&InsertMode);
}
CreateGraph(HeadNodeArray,NODE_NUM,InsertMode);
Sequence_Journey(HeadNodeArray,NODE_NUM);
//nsDeepthFirst_Journey(HeadNodeArray,NODE_NUM);
DeepthFirst_Journey(HeadNodeArray,NODE_NUM);
printf(" 应用程序运行结束！ ");
return 0;
}
免责声明：本文为网络用户发布，其观点仅代表作者个人观点，与本站无关，本站仅提供信息存储服务。文中陈述内容未经本站证实，其真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
