数据结构课程设计

学年**（设计）

本科）学院计算机与信息技术学院。

专业信息管理与信息系统。

年级 2011级。

姓名刘萌。**（设计）题目图的遍历的实现。

指导教师李为华职称副教授

学生签名。年月日。

目录。一需求分析1

二、概要设计2

三、详细设计3

四、调试分析及测试6

五、总结8参考文献9

附录11一、需求分析。

为了进一步的了解图的遍历的问题，图的dfs,bfs的递归和非递归算法的实现，用有向图和无向图来实现图的遍历，用邻接矩阵和邻接表的存储方式存储图。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。训练我们灵活应用所学数据结构的基本知识，熟练的完成问题分析、算法设计、编写程序，求解出指定的问题。

训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养严谨的科学态度和良好的工作作风，且提高综合运用所学的理论知识和方法独立分析和解决问题的能力。

1.1选择题目。

问题描述】对给定的有向图或无向图，实现深度优先遍历及广度优先遍历。

【基本要求】

（1）先任意创建一个图；

（2）图的dfs,bfs的递归和非递归算法的实现。

（3）要求用有向图和无向图分别实现。

（4）要求用邻接矩阵、邻接表多种结构存储实现。

1.2功能需求。

图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功能如下：

1、用户可以随时建立一个有向图或无向图；

2、用户可以根据自己的需要，对图进行深度遍历或广度遍历；

3、用户可以根据自己的需要对图进行修改；

二、概要设计。

采用邻接矩阵作为图的存储结构。程序中主要用到以下抽象数据类型：

抽象数据类型的定义。

typedef struct{

char *vexs顶点向量

int arcs[max_vex][max_vex邻接矩阵

int vexnum,arcnum图的当前顶点数和弧数

graph;

基本操作。createudn(graph &g)

操作结果：用邻接矩阵创建带权无向网图。

dfs(graph g,int k)

操作结果：对已存在的图进行深度优先遍历。

bfs(graph g)

操作结果：对已存在的图进行广度优先遍历。

choose(graph g)

操作结果：对将要实现的操作步骤进行选择。

程序包含两个模块。

主程序模块，其中主函数为。

int main{

输入信息；根据输入要求进行选择操作和输出；

输出结果；选择操作模块——实现具体选择的对应操作及输出操作。

两模块之间的简单调用关系如图1所示。

递归调用。图1 模块调用图。

三、详细设计。

各个函数之间的调用关系如图2所示。

图2 函数调用关系图。

函数设计。程序设计中主要包括下列函数。

用邻接矩阵创建一个图：

void createudn(graph &g)

用邻接矩阵创建一个带权无向网图；

输入顶点数和弧数；

输入各个顶点及各条弧；

递归方法实现图的遍历：

void dfs(graph g, int k)

用递归的方法访问图中的结点；

对图进行深度优先遍历；

非递归方法实现图的遍历：

void bfs(graph g)

用队列辅助访问图中的结点；

对图进行广度优先遍历；

选择输出需要的遍历方法：

void choose(graph g)

给出程序运行的选项；

对相应的输入选项调用相应的函数以执行操作；

四、调试分析及测试。

在调试过程中，程序**现了许多的错误，有错误的调用、一些变量没有定义、等等。不断的对程序进行调试以得到最好的结果，程序中特别要注意的是类的对象作为作为参数时要注意如何去调用它，使程序有一个令人满意的结果，具体的调试是在上机过程中进行的，在编写程序的过程中主要有如下错误：

1、在编写程序的过程出现了一些函数名、变量的大小写不统一的错误，导致程序在运行的过程**现函数名、变量没有被定义等问题；

2、在编写程序的过程中数组的大小写没有被确定；

3、在编写程序的过程中一些变量没有被定义，导致程序出错；

4、数组visited[max]应定义为全局变量，若不是则会出错；

5、函数的返回类型要确定，是void还是其他类型要十分注意；

6、在编程的过程中，函数里一些控制语句的嵌套使用，括号要引起注意，这次的课程设计就有一些括号漏了或者多打了，导致括号不配套；

运行结果：图3 输入图的顶点数和弧数。

图4 输入各个顶点和各条弧。

图5 选择图的遍历方式。

五、总结。通过这次课程设计，我受益颇多：

首先，上课时听的理论知识，似乎很容易接受，以及各种算法都能够比较轻松的理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。感觉自己有点眼高手低，有些知识点的应用只有在实践中才能慢慢体会，在平时做实验时，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。

其次，通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我的系统思考问题的能力，在编程方面，我开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。也就是因为先前的这种编程习惯，使得我在课程设计过程中浪费了不少的时间，尝到了教训。

通过这次课程设计，我学习了很多平时很少关注的知识点，比如循环链，递归的应用，也增强了自己的实践能力和编写程序的能力。

图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。用邻接矩阵作为图的数据存储结构很好地解决了图的结构难点，借助于邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。该程序通俗易懂且实用性强，并且该程序清单详细具体、全面、具有很强的可读性；系统整体上比较完美，可以从键盘获取输入元素，并且可以根据用户输入进行选择性地输出；整体输出画面效果整洁、大方。

参考文献。 1 ]谭浩强。 c程序设计[第三版]. 北京：清华大学出版社，2005

[ 2]罗宇等。数据结构[m ].北京：北京邮电大学出版社， 2003

3]严藯敏。数据结构[c语言版]. 北京：清华大学出版社， 1997

致谢。首先，我要感谢学校给我提供了此次课程设计的机会，能让同学们在一起学习与研究，让我有机会对所学的理论知识进行实践。

而且，在**的写作过程中，也得到了许多同学的宝贵建议，同时还得到许多学长的支持和帮助，我的设计才得以顺利完成，在此一并致以诚挚的谢意。

附录：源程序清单。

/ 程序名称：

/ 程序功能：采用递归和非递归算法，有向图和无向图，邻接矩阵和邻接表等多种结构存储实现图的遍历。

#include""

#define infinity 32767

#define max_vex 20最大顶点个数

#define queue_size (max_vex+1队列长度

bool *visited访问标志数组

int z=1图的邻接矩阵存储结构

typedef struct{

char *vexs顶点向量

int arcs[max_vex][max_vex邻接矩阵

int vexnum,arcnum图的当前顶点数和弧数

graph;

class queue队列类

public:

void initqueue(){

base=(int *)malloc(queue_size*sizeof(int));

front=rear=0;

void enqueue(int e){

base[rear]=e;

rear=(rear+1)%queue_size;

void dequeue(int &e){

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了