数据结构课程设计-图的遍历 [文档在线提供].docVIP

实习报告 题目：图的遍历 班级：031013 姓名 陈晶晶 完成日期：2005-1-6 需求分析 以邻接多重表为存储结构，实现连通或非连通的无向图的深度优先与广度优先遍历。 设图的结点不超过30个，每个结点用一个编号表示。通过输入图的边输入一个图，每条边为一个数对。 问题描述： 以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边。 测试数据： n=5，m=7，1, 2,1 ,3,1, 5,2,3,2,4,3,4,4,5 概要设计 本程序包含三个模块： 主程序模块： void main() {处理命令 } 邻接多重表的构造模块 深度优先遍历模块 广度优先遍历模块 各模块之间的调用关系如下： 主程序模块 邻接多重表的构造模块 详细设计 #include stdio.h #include stdlib.h #define MAX 30 #define N 30 #define M 10 #define NULL 0 typedef struct ebox { int ivex,jvex; //该边依附两个顶点的位置 struct ebox *ilink,*jlink;//分别指向依附这两个顶点的下一条边 }ebox,*pebox; typedef struct vexbox { char *data; pebox firstedge;//指向第一条依附该顶点的边 }vexbox,*pvexbox; typedef struct amlgraph//邻接多重表 { vexbox adjmulist[MAX]; }amlgraph,pamlgraph; typedef struct QNode//链式队列 { int data; struct QNode*next; }QNode,*QueuePtr; typedef struct { QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue; LinkQueue InitQueue()//构造一个空队列Q { LinkQueue Q; Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.front-next=NULL; return Q; } int DeQueue(LinkQueue*Q)//队列不为空时，删除队头元素 { QueuePtr p; int e; p=Q-front-next; e=p-data; Q-front-next=p-next; if(Q-rear==p) Q-rear=Q-front; free(p); return e; } void EnQueue(LinkQueue*Q,int e)//插入e为新的队尾元素 { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); p-data=e; p-next=NULL; Q-rear-next=p; Q-rear=p; } int QueueEmpty(LinkQueue Q)//判定队列是否为空 { if(Q.front==Q.rear) return 1; else return 0; } int visited[MAX]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; void initgraph(amlgraph G,int n)//？ { for(int i=0;in;i++) G.adjmulist[i].firstedge=NULL; } void SCANF(char name[N][M],int n,amlgraph G) { int i; printf(请输入结点名称：\n); for(i=0;in;i++) { scanf(%s,name[i]); G.adjmulist[i].data=name[i]; } } void CreateGraph(int n,amlgraph G)//构造邻接多重表 { pebox p1,p2; int i,j,k,m; int mark; initgraph(G,n); printf(请输入边的数量:); scanf(%d,m); for(k=0;km;k++) { printf(请输入第%d条边的两个