数据结构与算法问题分析及源代码之图的遍历.doc
图的遍历1题目题目:编写一个程序，实现图的遍历运算，并在此基础上设计一个主程序完成如下功能：输出如图的有向图G从顶点0开始的深度优先遍历序列（递归算法）。输出如图的有项图G从顶点0开始的深度优先遍历序列（非递归算法）。输出如图的有向图G从顶点0开始的广度优先遍历序列 01234554319765582 目标 熟悉图的定义及其基本操作的实现。3 设计思想 图的输入采用邻接矩阵的形式，在程序内部以邻接表形式进行操作。将上图进行深度优先遍历和广度优先遍历。4 算法描述（1） 邻接矩阵转换为邻接表：邻接表的结点元素是由结点组成的矩阵两个计数量。把邻接矩阵的结点数据值赋值给邻接表元素结点的数据变量，并初始化其元素结点指针为空；测试邻接矩阵的非零位，若为1则在邻接表中使前一个结点指向后一个结点。（2） 广度优先遍历：数组visited标记结点是否被访问，初始化为全零；从结点Vi开始访问，访问此顶点后，依次访问Vi的各个未曾访问过的邻接点，然后分别从这些邻接点出发，直至图中所有已有已被访问的顶点的邻接点都被访问到。（3） 深度优先遍历：深度优先遍历可有两种方式，递归和非递归。其中递归的深度优先遍历的思想是首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。5 程序结构图开始main( )初始化图转换邻接矩阵为邻接表广度优先遍历深度优先遍历（递归）深度优先遍历（非递归）结束6 源程序#include<stdio.h>#include<stdlib.h>#include <string.h>#define MAXVEX 100typedef char VertexType3;typedef struct edgenode int adjvex; int value; struct edgenode *next;ArcNode;typedef struct vexnode VertexType 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; ArcNode *p; G=(AdjList *)malloc(sizeof(AdjList); for (i=0;i<g.n;i+) G->adjlisti.firstarc=NULL; strcpy( G->adjlisti.data,g.vexsi.data); for (i=0;i<g.n;i+) for(j=g.n-1;j>=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(AdjList *G,int vi) int i,v,visitedMAXVEX; int QuMAXVEX,front=0,rear=0; ArcNode *p; for (i=0;i<G->n;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; 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 *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,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;i<g.n;i+) strcpy(g.vexsi.data,vnamei); for(i=0;i<g.n;i+) for(j=0;j<g.n;j+) g.edgesij=aij; MatToList(g,G); printf("从顶点0的广度优先遍历序列：n"); printf("t");BFS(G,0); printf("n");for(i=0;i<g.n;i+)visitedi=0;printf("从顶点0的深度优先遍历序列：n");printf("递归算法：");DFS(G,0);printf("n");for(i=0;i<g.n;i+)visitedi=0;printf("非递归算法：");DFS1(G,0);printf("n");第九题 阶乘1 题目求N！（N>10）要求编写C程实现时应该考虑边界条件的处理。2 目的掌握大数的处理方法。3 设计思想由于阶乘数据一般较大，因此用整形数组来存储结果，数组的每一元素是结果数字的某一位。计算时从低位开始，依次从2开始乘，每乘一位计算其进位，加到高位中去。4 程序流程图NY开始carry=0i=2i<=ntemp=resultj-1*i+carryresultj-1=temp%10arrayi=temp%10i+结束5 源程序#include <stdio.h>#include <stdlib.h>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<=digit;+j)temp=resultj-1*i+carry;resultj-1=temp%10;carry=temp/10;while(carry)digit+;resultdigit-1=carry%10;carry/=10;printf("结果为：n%d ! = ",n);for(i=digit;i>=1;-i)printf("%d",resulti-1);void main()int result200;int n;printf("请输入n的值：");scanf("%d",&n); factorial(result,n);printf("n");return;
