数据结构-求有向图的所有简单回路

数据结构-求有向图的所有简单回路 课 程 设 计 报 告 课程设计名称:数据结构课程设计 课程设计题目:求有向图的所有简单回 路 院(系):计算机学院 专 业:计算机科学与技术(嵌入式方向) 班 级: 学 号: 姓 名: 指导教师: I 目 录 沈阳航空航天大学 .................................................................... 错误～未定义书签。 1 总体设计 .................................................................................. 错误～未定义书签。 1.1 课设要求............................................................................. 错误～未定义书签。 1.2 设计原理............................................................................. 错误～未定义书签。 2 详细设计 .................................................................................. 错误～未定义书签。 2.1 算法与程序的设计与实现......................................... 错误～未定义书签。 2.1.1算法描述 ........................................................................ 错误～未定义书签。 2.1.2数据结构设计及用法说明 ........................................ 错误～未定义书签。 2.2 流程图的设计与实现..................................................... 错误～未定义书签。 3 核心数据结构函数的描述 .............................................. 错误～未定义书签。 3.1 建立邻接表的函数......................................................... 错误～未定义书签。 3.2 深度优先遍历函数......................................................... 错误～未定义书签。 4 程序测试及结果分析 .......................................................... 错误～未定义书签。 4.1 程序测试及结果............................................................. 错误～未定义书签。 参考文献 ........................................................................................ 错误～未定义书签。 附 录(关键部分程序清单) .............................................. 错误～未定义书签。 II 1 总体设计 1.1 课设要求 以合适方便的方式输入一个有向图，并在内部建立有向图的邻接表储存结构，有邻接表的形式储存有向图。然后根据有向图的储存结构，求出该有向图中所有的简单回路。输入有向图的方式简单方便，能形象方便的观察有向图的顶点名称，相关弧的关系。 要求如下: (1)熟悉图的邻接表储存结构及操作方式; (2)熟悉求简单回路的算法(利用深度优先遍历); (3)熟悉运用开发环境，基于VC++6.0的软件开发环境; (4)完成课程设计基本任务的设计及编码; (5)熟练掌握VC++6.0上的基本的调试方法。 1.2 设计原理 根据所学的知识，在利用邻接表时需要做三个工作:定义表结点类型;定义头结点类型;定义邻接表类型。再对储存的图进行深度优先遍历，并将遍历过的点进行标记，放入数组储存，当发现有被标记的点出现时则表示出现重复的顶点，为找到回路，打印出有向图的回路。 1 2 详细设计 2.1 算法与程序的设计与实现 在得到该课程设计任务书时，在对求有向图的所有简单回路的算法知识做了简单的回顾与学习。首先是邻接表储存有向图，由于有向边没有权值，所有在建立有向图的邻接表的时候去除了有关弧的信息。其次才用深度优先遍历的算法遍历有向图中所有的顶点，在遍历有向图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标记成为已被访问，就不再从它出发进行搜索了。因此，遍历有向图的过程实质上是对每个顶点查找其邻接点的过程。 2.1.1算法描述 (1)邻接表:邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的接点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。每个结点由3个域组成，其中邻接点域(adjvex)指示与顶点Vi邻接的点在图中的位置，链域(nextare)指示下一条边或弧的结点;数据域(info)储存和边或弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设有链域(firstarc)指向链表中第一个结点之外，还设有储存顶点Vi的名或其它有关信息的数据域(data)。如下图所示: adjvex nextarc info 图2.1.1 表结点 data firstarc 图2.1.2 头结点 (2)深度优先遍历:设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边(x，y)。若发现顶点y已访问过，则重新 2 选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过;然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点;否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 在本次课程设计中还需要对深度优先遍历进行递归，关于深度优先遍历的递归，首先访问出发点v，并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(称为从源点可达的顶点)均已被访问为止。 2.1.2数据结构设计及用法说明 (1)邻接表的形式说明及其建表算法: 通过表头结点(可以链相接)通常以顺序结构的形式储存，以便随机访问任一顶点的链表。一个邻接表储存结构可以定于如下: //边表结点 Typedef struct ArcNode{ int adjvex;//邻接点域 struct node *nextarc; //链域 InfoType *info//若要表示边上的权，则应增加一个数据域 } ArcNode; //顶点表结点 typedef struct vnode{ VertexType data;//顶点域 EdgeNode *firstarc;//指向第一条依附该顶点的弧的指针 }VertexNode; //AdjList是邻接表类型 3 typedef VertexNode AdjList[MaxVertexNum]; typedef struct{ AdjList adjlist;//邻接表 int n，e;//图中当前顶点数和边数 }ALGraph; (2)深度优先遍历的算法说明: 在遍历图时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标记成为已被访问，就不再从它出发进行搜索了。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。 Boolean visited[MAX];//访问标志数组 Status(* VisitFunc)(int v);//函数变量 void DFS(Graph G，int v), //从第v个顶点出发递归地深度优先遍历图G visited[v] = TURE; VisitFunc(v);//访问第v个顶点 for(w=FirstAdjVex(G,v);w>=0;w =NextAdjVex(G，v，w)) if(～visited[w])DFS(G，w) , 4 2.2 流程图的设计与实现 (1)建立邻接表流程图如下: 开始 输入顶点个数和弧的条 数 输入顶点名称 Y 是否重复 N 输入弧的信息，弧的起点与 终点 Y 是否重复 N 根据顶点信息，将弧赋予当 前指针和指向下一弧的 指针 建立结点和顶点链表 N 是否弧已全部进行操 作 Y 5 结束 图2.2.1 建立邻接表流程图 (2)深度优先遍历的流程图如下: 开始 将顶点全部初始化为未遍 历 将当前顶点指针指向根顶 点 对当前顶点进行 操作并标记为遍 历 获取当前顶点的 将当前指针指向该顶下一个子顶点 点 N 对当前顶点进行操是否获得 作 Y 从顶点数记录中减 将当前顶点放入一回到上一顶点 数组保存，然后 将当前指针指向 获得的顶点 N N 是否该顶点周围 的子顶点都已遍 历 该顶点是否与 第一个顶点相 Y 同 Y 输出保存有顶点 信息的数组 6 结束 图2.2.2 深度遍历流程图 7 3 核心数据结构函数的描述 3.1 建立邻接表的函数 函数名称:int CreateADG(ALGraph &g) 函数功能:实现在键盘上输入有向图顶点数、顶点名称(用整数表示，如 1就表示顶点1)、弧数以及弧的顶点与起点，并用邻接表储存图。 函数具体代码如下: int CreateADG(ALGraph &g){ int i,j,k,l; ArcNode *p; int v1,v2; int c; printf("请输入有向图的顶点数:"); scanf("%d",&g.vexnum); i=g.vexnum*(g.vexnum-1); printf("请输入有向图的边数:"); scanf("%d",&g.arcnum); getchar(); printf("请依次输入有向图的各个顶点:"); for(i=0;i=0) { printf("输入的顶点重复，请重新输入\n"); i--; continue; 8 } g.vertices[i].data=c; g.vertices[i].firstarc=NULL; } for(k=0;kadjvex=j; p->nextarc=g.vertices[i].firstarc;//顶点i的链表 g.vertices[i].firstarc=p;//添加到最左边 } printf("\n有向图的邻接表创建成功\n\n"); return 1; } 9 3.2 深度优先遍历函数 函数名称:void dfs(ALGraph G,int cur,int* save,int size) 函数功能:实现从选定的顶点开始对有向图进行深度优先遍历，函数中g为当前要搜索的图，cur为当前搜索的顶点的下标，save是一个数组，用来保存搜索过的顶点，size为save数组的大小。在遍历中将遍历的顶点放入save中，当搜索到的顶点回到起点时，为找到回路，打印出有向图的回路。 函数的具体代码如下: void dfs(ALGraph G,int cur,int* save,int size) { int i; ArcNode *p=G.vertices[cur].firstarc; save[size]=cur; while(p) { if(save[0]==p->adjvex) { count++; printf("第%d条回路 ",count); for(i=0;i%d ",G.vertices[save[i]].data,G.vertices[save[i+1]].data); printf } printf("%d->%d\n",G.vertices[save[i]].data,G.vertices[save[0]]); } else if(flag[p->adjvex]==0) { flag[p->adjvex]=1; 10 dfs(G,p->adjvex,save,size+1); flag[p->adjvex]=0; } p=p->nextarc; } 11 4 程序测试及结果分析 4.1 程序测试及结果 (1)当输入有向图为4个顶点，5条弧时，有向图如下图所示: 1 2 3 4 图4.1.1 有向图1 图4.1.2程序测试图1 12 (2)当输入有向图为6个顶点，8条弧时，有向图如下: 1 2 3 6 5 4 图4.1.3 有向图2 图4.1.4 程序测试图2 13 (3)当输入有向图为5个顶点，4条弧时，此时有向图无回路，有向图如 下: 1 2 3 5 4 图4.1.5 有向图3 图4.1.6 程序测试图3 14 参考文献 [1] 严蔚敏，吴伟明. 数据结构(C语言版)[M]. 北京:清华大学出版社，2006 [2] 吕国英. 算法设计与分析[M]. 北京:清华大学出版社，2006 [3] 徐宝文，李志. C程序设计语音[M]. 北京:机械工业出版社，2004 15 附 录(关键部分程序清单) #include "stdafx.h" #include #include #include typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 }ArcNode; typedef struct VNode { int data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧 }VNode, AdjList[50]; typedef struct { AdjList vertices; int vexnum, arcnum; // 图的当前顶点数和弧数 }ALGraph; int flag[50]; //这个是标志顶点是否被搜索过，flag[1]=1 表示顶点1被搜索 过，否则没有被搜过过 int count; //回路条数 int locateALG(ALGraph g,int v) //v 是顶点的值，locateALG函数通 过v值，返回顶点v在 g的顶点数组的下标索引 { for(int i=0;i=0) 17 { printf("输入的顶点重复，请重新输入\n"); i--; continue; } g.vertices[i].data=c; g.vertices[i].firstarc=NULL; } //这里输入边信息 for(k=0;kadjvex=j; p->nextarc=g.vertices[i].firstarc;//顶点i的链表 g.vertices[i].firstarc=p;//添加到最左边 18 } printf("\n有向图的邻接表创建成功\n\n"); return 1; } //使用深度优先搜索方法找出回路 //g:当前要搜索的图 //cur:当前搜索的顶点的下标 //save数组: 保存搜索过的顶点 //size:save数组的大小 void dfs(ALGraph G,int cur,int* save,int size) { int i; ArcNode *p=G.vertices[cur].firstarc; //取得顶点的链接表 save[size]=cur; //保存搜索过的顶点 //遍历所有边 while(p) { //save[0]是开始顶点 //搜索到的顶点回到起点，找到回路，打印 if(save[0]==p->adjvex) { count++; printf("第%d条回路 ",count); for(i=0;i%d ",G.vertices[save[i]].data,G.vertices[save[i+1]].data); } 19 printf("%d->%d\n",G.vertices[save[i]].data,G.vertices[save[0]]); } //顶点没有被搜索过，搜索这个顶点 else if(flag[p->adjvex]==0) { flag[p->adjvex]=1; //标志已经搜索过 dfs(G,p->adjvex,save,size+1); flag[p->adjvex]=0; //搜索回来，取消标志 } p=p->nextarc; //下一条边 } } int main(void) { int save[50]; ALGraph g; int v; char sel; CreateADG(g); //创建有向图 do{ do{ printf("\n请输入开始顶点:");//输入开始顶点 scanf("%d",&v); v=locateALG(g,v); if(v<0) printf("\n没有找到顶点!\n\n"); }while(v<0); printf("\n"); 20 memset(flag,0,sizeof(flag)); //设置标志位，初始化所有顶点， 顶点全部没有访问过 flag[v]=1; //顶点v访问过 //开始搜索回路 count=0; dfs(g,v,save,0); printf("\n一共%d条回路\n\n",count); printf("是否继续?(Y/N)"); getchar(); scanf("%c",&sel); }while(sel!='n' && sel!='N'); return 0; } 21 课程设计

总结

初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf

: 本程序以C语言的相关知识为基础，通过对数据结构中邻接表和深度优先遍历的再次学习，成功的有C实现了求有向图的所有简单回路。从程序的编写来看，感觉这次自己真的学到了好多，又巩固了原来所学的知识， 当然在编写程序与调试程序的过程中也遇到了不少的问题，在与同学交流和查找相关资料的情况下也得到了解决，在这个算法中，最为核心的就是深度优先遍历了，再对这个算法的学习中遇上了不少问题，比如关于如何递归，在遍历了当前顶点之后回溯到原来的顶点继续遍历未遍历的顶点。 总之，经过本次专业课程设计，让我掌握了开发应用软件的基本流程，运用所学编程技能的基本技巧，也让我初步了解了软件设计的基本方法，提高进行工‎‎程设计的基本技能及分‎‎析、解决实际问题的能力，为以后毕业设计和工程实践等打下良好的基础。相信通过这次的课程设计，我对所学的《数据结构(C语言版)》和各种编程语言都有了一个全新的‎‎认识。我也会积极吸取本次课程设计的经验，继续研究数据结构和所学的各种编程语言。 指导教师评语: 指导教师(签字): 年 月 日 课程设计成绩 22