数据结构课程设计报告

滨江学院。

2011 --2012 年度第 2 学期)

课程名称：数据结构。

题目：公园的导游图

院系：滨江学院计算机系

班级：动漫（2）班

学号： 20102359059

姓名：郑强。

指导教师：李振宏

设计周数：两周。

日期：2012 年 5月24 日。

目录。一。设计目的 3

二、需求分析 3

2.1选题的意义及背景 3

2.2 输入/输出形式和输出值的范围 4

三．概要设计 4

3.1设计思想 4

3.2函数间的关系 4

四、详细设计 5

4.1哈夫曼的主要结构 5

4.1.1结构定义 5

4.1.2主要函数声明及功能描述 6

4.2源程序 7

4.2.1头文件 7

4.2.2源文件 8

五。程序测试结果及问题分析 14

5.1程序测试结果 14

5.2 问题分析 15

六。总结 15

七。参考文献 16

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。

通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。

实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。

。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：

1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

程序要能够显示出地图，要能够查找出地图中任意两点间的最短距离，以及不重复遍历全图的最短路径，并且在查找及遍历的每个过程都在图中显示出暂时的结果，以便演示整过过程。

程序执行要求有描述地图的两个文件，并放到相应位置。其中一个文件存放有描述地图各个景点之间距离的矩阵，另一个文件存有地图中各景点在显示器上显示的位置。两个地**件不允许有错误。

执行相应功能前要求先选择。

查找任意两点间的最短距离，要求输入要查找最短路径的两点。

在运行各个小过程后要求输出暂时结果。

4.1程序模块。

程序共有主模块、查找两点最短路径并输出具体过程、寻找不重复遍历全图图路径并输出遍历过程、三个模块。主模块包含、载入地图、显示地图、功能选择与调用三部分。查找两点最短路径并输出具体过程模块中的输出具体过程为显示地图模块。

模块结构如图：

图2.14.2 课题涉及的数据结构和数据库结构。

程序主要用了图和栈两种数据结构，采用矩阵来保存图形结构的地图，用栈保存遍历时经过的结点用以遍历的回溯，以及存储最终路径。

图的抽象数据类型：

adt graph｛

数据对象：d=

基本运算：loadimg(*g)：从相应文件中载入图数据初始化图g。

outputimg(*g)把图输出到屏幕。

bestpath（）不重复遍历图。

floyed（）计算图中所有点的两两最短路径。

栈的抽象数据类型：

adt list

数据关系：r=

基本运算：push（*s，e）：进栈：将元素e查到栈s中作为栈顶元素。

pop（*s，*e）：出栈：从栈s中退出栈顶元素，并将其值赋予e。

copsta(*s1, *s)：把栈s中的内容复制到栈s1。

4.1采用c语言定义相关的数据类型。

图的定义：typedef struct

int edges[max][max];

int n; /n 顶点数*/

int e; /e 边数 */

mgraph;

栈的定义：typedef struct

int body[max];

int top;

stack;

4.2写出各模块的类c码算法。

4.2.1读取地图：

把保存在文件中的地图数据载入到程序中相应的数据结构，图结构体g及顶点位置数组vl[2]中。

void loadimg(int vl[2],mgraph *g)

fp=fopen(""r");

fscanf(fp, "d",&g->n));

for(i=0;in; i++)

fscanf(fp, "d%d",&vl[i][0],&vl[i][1]);

fclose(fp);

fp=fopen(""r");

for(i=0,g->e=0; in; i++)

for(j=0; jn; j++)

fscanf(fp, "d",&g->edges[i][j]))

fclose(fp);

4.2.2 显示地图：

把地图以图形方式输出到显示器。

void outputimg(int vl[2],mgraph *g)

for(i=0,g->e=0; in; i++)

for(j=0; jn; j++)

for(i=0;in; i++)

画景点；4.2.3 不重复遍历全图的最短路径：

寻找从起点开始不重复走完所有景点的路径，如果该路径不存在，将提示。如果存在将会最终找出符合要求的最短路径。

step1： if（没遍历完）

if（向前有一景点没访问过）往下走；

else 回溯到上一景点点（原景点之后景点变为没访问过）；

if（遍历到起点且访问其以后景点必然与以前的试探路径相同）

//说明路径不再存在；

若以前找到过遍历路径则输出最佳结果结束；

else 到step1 开始下一步搜索；

else 若比以前有的结果更好，则输出结果并继续试探更好的遍历方法；

4.2.4 两点间最短路径：

采用弗洛伊德算法，求出每点间的最短路径，并在计算过程中输出用户所求两点间的暂时计算出的最短路径。

void floyed(mgraph *g, int a[max], int path[max],int vl[2])

for (i=0;in;i置初值*/

for (j=0;jn;j++)

输入两景点；

for (k=0;kn;k++)

{for (i=0;i< g->n;i++)

for (j=0;jn;j++)

if(a[i][k]!=inf &&a[k][j]!=inf &&a[i][j]>(a[i][k]+a[k][j]))

a[i][j]=a[i][k]+a[k][j];

path[i][j]=k;

输出0到k号顶点被考虑作为中间节点时两景点的最短路径图；

4.3各函数的调用关系图、主要函数的流程图。

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了