无向图的邻接表表示及遍历实验报告电子版.doc

福州大学数计学院数据结构上机实验报告专业：应用数学学号姓名班级实验名称图的实验实验内容无向图的邻接表表示及遍历实验目的和要求掌握图的邻接表表示方法及实现技术掌握在图的邻接表表示方式下的图的遍历操作问题描述和主要步骤【实验内容】从键盘输入无向网络G的顶点个数v、边的个数e。建立由v个顶点、e条边构成的无向图G，采用邻接表表示。V个顶点的值由键盘输入，元素类型为字符型，e条边的信息亦由键盘输入 调用图的深度优先搜索遍历图并输出相应的遍历序列代码：#include stdafx.h#include #include #define MAX 20 /无向图最大顶点数typedef struct nodeint adjvex; /顶点序号struct node *next; /指向下一条弧的顶点*pointer;typedef structchar data; /顶点名称pointer first; /头指针headtype;typedef structheadtype adlistMAX;int n; /顶点数int e; /边数lkgraph;typedef struct treechar data; /结点名称struct tree *lchild; /存放第一个孩子struct tree *rchild; /存放兄弟*BTree;typedef structint *base;int *top;SqStack; /用于简单路径算法，最大长度为MAXbool visitMAX; /遍历中判断是否被访问int t_num; /非连通图生成子树BTree tMAX;bool flag=false; /判断是否存在简单路径void creategraph(lkgraph *g)/建立无向图的邻接表pointer p;int i,j,e=0;char c; /吸收回车printf(无向图邻接表的建立：n);printf( 顶点位置序号从0开始n);printf( 顶点名称用一个字符表示n);s1: printf( 请输入无向图的顶点数（小于等于20）：n);scanf(%d,&i);if(i20) goto s1; /顶点数目输入不符合要求g-n=i;for(i=0;in;i+) /初始化c=getchar();printf(请输入顶点名称：n);scanf(%c,&g-adlisti.data);g-adlisti.first=NULL;printf(请输入一条边的两个顶点，用“，”隔开（当输入的第一个数为-1时，停止输入）：n);scanf(%d,%d,&i,&j);while(i!=-1)e+;p=(pointer)malloc(sizeof(struct node);p-adjvex=j;p-next=g-adlisti.first;g-adlisti.first=p;p=(pointer)malloc(sizeof(struct node);p-adjvex=i;p-next=g-adlistj.first;g-adlistj.first=p;printf(请输入一条边的两个顶点，用“，”隔开（当输入的第一个数为-1时，停止输入）：n);scanf(%d,%d,&i,&j);g-e=e;void show(lkgraph *g)/邻接表输出pointer p;printf(邻接表输出：n);for(int i=0;in;i+)printf(%c: ,g-adlisti.data);p=g-adlisti.first;while(p!=NULL)printf(%5d,p-adjvex);p=p-next;printf(n);void DFS(lkgraph *g,int v,BTree q)/从顶点v出发，递归地深度优先遍历gvisitv=true;BTree q1,l;q1=(BTree)malloc(sizeof(struct tree);q1-lchild=NULL;q1-rchild=NULL;printf(%5c,g-adlistv.data);q-data=g-adlistv.data;pointer p=g-adlistv.first;for(int w=0;p!=NULL;p=p-next)w=p-adjvex;if(!visitw)DFS(g,w,q1);l=q;if(l-lchild=NULL)l-lchild=q1;elsel=l-lchild;while(l-rchild!=NULL)l=l-rchild;l-rchild=q1;q1=(BTree)malloc(sizeof(struct tree);q1-lchild=NULL;q1-rchild=NULL;void DFSTraverse(lkgraph *g)printf(图的深度优先遍历：n);printf(请输入起始点序号（0%d）：n,(g-n-1);int m,i;scanf(%d,&m);for(int v=0;vn;v+)visitv=false; /初始化if(!visitm)t0=(BTree)malloc(sizeof(struct tree);t0-lchild=NULL;t0-rchild=NULL;DFS(g,m,t0);printf(n);t_num=1;for(v=0,i=1;vn;v+)if(!visitv)ti=(BTree)malloc(sizeof(struct tree);ti-lchild=NULL;ti-rchild=NULL;DFS(g,v,ti);t_num+;i+;printf(n);BTree CreateBiTree()/将森林转化为二叉树BTree T,p,q;T=t0;p=T;for(int i=1;irchild=q;p=p-rchild;return T;void preorder(BTree l)/先序遍历if(l!=NULL)printf(%5c,l-data);preorder(l-lchild);preorder(l-rchild);void pasorder(BTree l)/后序遍历if(l!=NULL)pasorder(l-lchild);pasorder(l-rchild);printf(%5c,l-data); SqStack& InitStack(SqStack &s)/构造空栈s.base=(int*)malloc(MAX*sizeof(int);s.top=s.base;return s;void lujing(lkgraph *g,int a,int b,SqStack &s)int w,*i;pointer p;visita=true;*s.top=a;s.top+;i=s.top;if(a=b) /找到简单路径，输出flag=true;while(i!=s.base)i-;printf(%5d,*i); printf(n); p=g-adlista.first;while(p!=NULL)w=p-adjvex;if(!visitw)lujing(g,w,b,s);p=p-next;visita=false;s.top-;void Menu()printf(*n);printf(1建立无向图n);printf(2指定起始点，深度优先遍历n);printf( 先序遍历深度优先生成树n);printf( 后序遍历深度优先生成树n);printf(3求两点简单路径n);printf(0退出n);printf(*n);void main()lkgraph *g;SqStack s;BTree T;s=InitStack(s);int x;Menu();scanf(%d,&x);while(x!=0)if(x=1)g=(lkgraph*)malloc(sizeof(lkgraph);creategraph(g);show(g);else if(x=2)DFSTraverse(g);T=CreateBiTree();printf(n深度优先生成树的先序遍历为：n);preorder(T);printf(n深度优先生成树的后序遍历为：n);pasorder(T);printf(n);else if(x=3)printf(请输入起始点和终点位置，以“，”隔开：n);int a,b;scanf(%d,%d,&a,&b)