算法与数据结构报告

《算法与数据结构报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构课程设计班级：姓名：指导老师：2010年6月14日——2010年6月25日目录第一章课程设计方案…………………………………………………3第二章代码实现过程…………………………………………………3第三章课设代码测试…………………………………………………6第四章程序使用说明…………………………………………………12第五章难点与收获……………………………………………………13第六章可改进的地方…………………………………………………14第一章课程设计方案1.1课程设计简述本实验采用模块化设计方案，界面友好，可读性强，采用v

2、c环境编程。该程序实现菜单化，可视化，界面良好的输入输出效果，各部分之间采用模块连接，第一部分模块为输入部分，用户可根据提示输入选择，进入第二部分模块，输入对应的数字，分别进入不同的模块，第一模块为无向图的基本操作，其中包含无向图的邻接矩阵存储，无向图的邻接表存储，无向图的深度遍历和广度遍历。用户根据提示输入数据，创建无向图，完成相关操作，并将结果显示在输出屏幕上；第二模块为无向网的基本操作，包括无向网的邻接矩阵建立，邻接表建立，最小生成树的求解（分别采用普里姆和克鲁斯卡尔算法来实现），操作同上；第三模块为有向图的基本操作，包括

3、有向图的邻接矩阵建立，邻接表建立，拓扑排序，操作同上；第四模块为有向网的基本操作，包括有向网的邻接矩阵建立，邻接表建立，关键路径求法，单源顶点最短路径问题，操作同上；最后的第三部分模块，即是输出结果部分。1.2课程设计分析本课题要求实现无向图，无向网，有向图，有向网的一系列基本操作，对上述四种结构，都采用邻接矩阵和邻接表两种存储方式，在这两种存储方式的基础上分别进行无向图的深度优先搜索和广度优先搜索，无向网中求最小生成树，有向图的拓扑排序，有向网中求关键路径和单源顶点最短路径。第二章代码实现过程2.1存储结构2.11邻接矩阵存储

4、结构图的邻接矩阵存储表示即是数组存储表示，在邻接矩阵中，我们定义两个数组分别存储数据元素的信息和数据元素之间的关系（边或弧）的信息，以二维数组表示有n个顶点的图时，需存放n个顶点信息和n的平方个弧信息的存储量。借助于邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求得各个顶点的度。故在建立邻接矩阵之前，必须先定义顶点关系类型和相关指针指示弧的信息。2.12邻接表存储结构邻接表是一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由

5、3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。此时要分四种种情况：无向图，有向图，无向网，有向网。对于无向图，一条边的两个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边

6、结点，即起点。对于有向图，只能向起点的单链表的表头插入一个边结点，即终点，但不能反过来。对于无向网和有向网，存储方式类似，不过应该加入权值。至于邻接表的输出，由于不了解C++中的绘图操作，故采用for语句输出各结点，并配合一些符号完成邻接表的输出。2.2无向图的深度优先搜索和广度优先搜索深度优先搜索深度优先搜索遍历类似于数的先根序遍历，是树的先根序遍历的推广。假设初始状态是图中所有结点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的临界点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；

7、若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。为了在遍历过程中便于区分顶点是否已被访问，需附设一个访问编制数组visited[0..n-1]，其初值为false,一旦某个顶点被访问，则其相应的分量置为true。具体过程为：先访问初始点Vi，并标志其已被访问。此时定义一指向边结点的指针p，并建立一个while（）循环，以指针所指对象不为空为控制条件，当Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将p指针指向下一个边结点。这样就可以完成图的深度优先

8、遍历了。广度优先搜索广度优先搜索类似于树的按层次遍历的过程。假设从图总某顶点出发，在访问了v之后依次访问v的各个未曾访问到的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的邻接点”先于“后被访问的邻接点”被访问，直至图中所有已被访问的邻接点