《数据结构》课程设计报告单。
题目】中国道路交通网络信息查询系统。
目的】加深理解线性表、树、图的基本概念及它们的存储，掌握无向图的重要应用——最短路径的算法，广度优先搜索方法的应用，构造最小生成树的算法。
要求】城市间的距离网采用邻接表表示。要求能：
1) 显示网图。
2) 显示邻接表。
3) 显示城市间最短路径。
4) 显示两城市间最少中转路径。
5) 显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
主要内容及实现的功能】给定26个城市间的距离网（p187），用dijkstra方法求最短路径；广度优先搜索方法显示城市间最少中转路径；用prim算法建立最小生成树，并计算得到的最小生成树的代价。
原始数据及资料】参考课本p187
主要参考资料】
课程设计报告单】
1、系统设计分析。
本系统有三大模块组成：
1、图的存储：图的存储有两种方法a.矩阵法b.邻接法，矩阵发和邻接法两种存储结构的比较如下图。
在本次课程设计中，我们要求使用邻接法，因为本次设计使用的交通图为无向图，使用邻接法可以比矩阵法更节省空间，而且时间复杂度也相对降低。
2、图的遍历：
图的遍历有两种方法a.广度优先b.深度优先。
本次设计中要求显示两城市间最少中转路径，而广度优先遍历图的过程是以起点，由近至远，依次访问和起点有路径相通的其它节点。因此，通过广度优先算法可以查询出两个城市间最少中转的路径。
3、最短路径和最小生成树：
交通图的任意两个城市均有一条或多条路径可以相连，通过最短路径，我们可以将两个城市间距离（权值）最短的路径找到并打印出来。最小生成树是求将所有城市相连所需的最短路径。
2、系统设计结构图。
1）显示网图。
2）显示城市间最短路径（城市**）
3）显示邻接表。
4）显示城市间最短路径（城市名称）
5）两个城市间最短路径（城市**）
6）两个城市间最少中转路径。
7）最小生成树。
3、算法描述（实现思路）
1、最短路径的算法描述：
假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空；② 所有其他点： di=∞,pi=?;标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min［dj, dk+lkj］
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min［dj, 所有未标记的点j］
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点，设置：
i=j5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。
2、广度优先遍历的算法描述：
设图g的初态是所有顶点均未访问过。在g中任选一顶点v为源点，则广度优先遍历可以定义为：首先访问出发点v，接着依次访问v的所有邻接点w1，w2，…，wt，然后再依次访问与wl，w2，…，wt邻接的所有未曾访问过的顶点。
依此类推，直至图中所有和源点v有路径相通的顶点都已访问到为止。此时从v开始的搜索过程结束。
设立初值，并令起始结点进队：
f:=0;r:=1;ll[r]:=st,e[st]:=1;w:=1;h:=1;
将此时第h层（开始h=1，表示第一层）的w（开始时w=1，表示一个结点）顶点的顺序出队，并访问与该层各顶点相邻接但又没有访问过的顶点，同时将这些结点进队列，且设立前趋链接指针和访问过标记，若此时的结点为目标结点，则只设立前趋链接指针而不设立访问过标记。
计算此时第h+1层的顶点个数w:=r+1-g[h]，然后看该层有多少个顶点为目标结点，凡是出现目标顶点的，就将其个数累计，也就是为最短路径的条数，同时从这个目标结点按前趋链接指针将到达该目标结点的路径的各个顶点编号存入c[s,j]中，然后转⑷，若目标顶点累计个数为0，表明该层没有出现目标结点，则转⑵。
打印搜索到的各条最短路径的各结点编号，并结束程序。
3、最小生成树的算法描述：
求mst的一般算法可描述为：针对图g，从空树t开始，往集合t中逐条选择并加入n-1条安全边(u，v)，最终生成一棵含n-1条边的mst。当一条边(u，v)加入t时，必须保证t∪仍是mst的子集，我们将这样的边称为t的安全边。
用伪**可将算法描述为：
generiemst(g)仍为mst的子集。
t=t∪； 加入安全边，扩充t
return t； /t为生成树且是g的一棵mst
4、各个模块（函数）的实现功能、所用参数、说明及原始**。
1)void bfsal(algraph &g,int i)//图的广度优先搜索算法(邻接表存储表示)
2)void createalgraph(algraph &g)//生成邻接表。
3)void printalgraph(algraph &g)//显示邻接表。
4)void printmgraph(algraph &g)//显示图。
5)void printpath1(algraph &g,int v0)//显示城市间最短路径（**输出）
6)void printpath2(algraph &g,int v0)//显示城市间最短路径。
7)void shortestpath(algraph &g,int v0)//最短路径算法。
8)void minispantree(algraph &g, int v0)//最小生成树。
9)int menu(void)//菜单函数。
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...