数据结构与算法问题分析及源代码之图的遍历.doc

《数据结构与算法问题分析及源代码之图的遍历.doc》由会员分享，可在线阅读，更多相关《数据结构与算法问题分析及源代码之图的遍历.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的遍历1题目题目:编写一个程序，实现图的遍历运算，并在此基础上设计一个主程序完成如下功能：输出如图的有向图G从顶点0开始的深度优先遍历序列（递归算法）。输出如图的有项图G从顶点0开始的深度优先遍历序列（非递归算法）。输出如图的有向图G从顶点0开始的广度优先遍历序列 01234554319765582 目标 熟悉图的定义及其基本操作的实现。3 设计思想 图的输入采用邻接矩阵的形式，在程序内部以邻接表形式进行操作。将上图进行深度优先遍历和广度优先遍历。4 算法描述（1） 邻接矩阵转换为邻接表：邻接表的结点元素是由结点组成的矩阵两个计数量。把邻接矩阵的结点数据值赋值给邻接表元素结点的数据变量，并初

2、始化其元素结点指针为空；测试邻接矩阵的非零位，若为1则在邻接表中使前一个结点指向后一个结点。（2） 广度优先遍历：数组visited标记结点是否被访问，初始化为全零；从结点Vi开始访问，访问此顶点后，依次访问Vi的各个未曾访问过的邻接点，然后分别从这些邻接点出发，直至图中所有已有已被访问的顶点的邻接点都被访问到。（3） 深度优先遍历：深度优先遍历可有两种方式，递归和非递归。其中递归的深度优先遍历的思想是首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点

3、)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。5 程序结构图开始main( )初始化图转换邻接矩阵为邻接表广度优先遍历深度优先遍历（递归）深度优先遍历（非递归）结束6 源程序#include#include#include #define MAXVEX 100typedef char VertexType3;typedef struct edgenode int adjvex; int value; struct edgenode *next;ArcNode;typedef struct vexnode Vert

4、exType data; ArcNode *firstarc;VHeadNode;typedef struct vertex int adjvex;VertexType data;VType;typedef struct graph int n,e;VType vexsMAXVEX;int edges MAXVEXMAXVEX;AdjMatix;typedef struct int n,e; VHeadNode adjlistMAXVEX;AdjList;/将邻接矩阵g转化成邻接表G:void MatToList(AdjMatix g, AdjList *&G) int i,j; ArcNod

5、e *p; G=(AdjList *)malloc(sizeof(AdjList); for (i=0;iadjlisti.firstarc=NULL; strcpy( G-adjlisti.data,g.vexsi.data); for (i=0;i=0;j-) if (g.edgesij!=0) p=(ArcNode *)malloc(sizeof(ArcNode); p-value=g.edgesij;p-adjvex=j; p-next=G-adjlisti.firstarc; G-adjlisti.firstarc=p; G-n=g.n;G-e=g.e;/广度优先：void BFS(

6、AdjList *G,int vi) int i,v,visitedMAXVEX; int QuMAXVEX,front=0,rear=0; ArcNode *p; for (i=0;in;i+) visitedi=0;printf(%d,vi);visitedvi=1;rear=(rear+1)%MAXVEX;Qurear=vi;while(front!=rear) front=(front+1)%MAXVEX; v=Qufront; p=G-adjlistv.firstarc; while(p!=NULL) if(visitedp-adjvex=0) visitedp-adjvex=1;

7、printf(%d,p-adjvex); rear=(rear+1)%MAXVEX; Qurear=p-adjvex; p=p-next; /深度优先递归：int visitedMAXVEX;void DFS(AdjList *g,int vi) ArcNode *p; printf(%d,vi); visitedvi=1; p=g-adjlistvi.firstarc; while(p!=NULL) if (visitedp-adjvex=0) DFS(g,p-adjvex); p=p-next; /深度优先非递归：void DFS1(AdjList *G,int vi) ArcNode *

8、p; ArcNode *StMAXVEX; int top=-1,v; printf(%d,vi); visitedvi=1; top+; Sttop=G-adjlistvi.firstarc; while(top-1) p=Sttop;top-; while(p!=NULL) v=p-adjvex; if(visitedv=0) printf(%d,v); visitedv=1; top+; Sttop=G-adjlistv.firstarc; break; p=p-next; void main() int i,j; AdjMatix g; AdjList *G; int a66=0,1,

9、0,1,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,0,1,0,0,0,1,0; char *vnameMAXVEX=a,b,c,d,e,f; g.n=6;g.e=10; for(i=0;ig.n;i+) strcpy(g.vexsi.data,vnamei); for(i=0;ig.n;i+) for(j=0;jg.n;j+) g.edgesij=aij; MatToList(g,G); printf(从顶点0的广度优先遍历序列：n); printf(t);BFS(G,0); printf(n);for(i=0;ig.n;i+)visi

10、tedi=0;printf(从顶点0的深度优先遍历序列：n);printf(递归算法：);DFS(G,0);printf(n);for(i=0;i10）要求编写C程实现时应该考虑边界条件的处理。2 目的掌握大数的处理方法。3 设计思想由于阶乘数据一般较大，因此用整形数组来存储结果，数组的每一元素是结果数字的某一位。计算时从低位开始，依次从2开始乘，每乘一位计算其进位，加到高位中去。4 程序流程图NY开始carry=0i=2i=ntemp=resultj-1*i+carryresultj-1=temp%10arrayi=temp%10i+结束5 源程序#include #include void factorial(int * result,int n)int carry,digit=1,temp; result0=1;for(int i=2;i=n;i+)for(int j=1,carry=0;j=1;-i)printf(%d,resulti-1);void main()int result200;int n;printf(请输入n的值：);scanf(%d,&n); factorial(result,n);printf(n);return;