数据结构课程设计报告

西安郵電大學。

实验题目延安市旅游导游系统。

一、实验目的。

1．加深对《数据结构》这一课程所学内容的进一步理解与巩固。

2．通过完成课程设计，逐渐培养自己的编程能力；

3．培养给出题目后，构建框架，用计算机解决的能力；

4．通过调试程序积累调试c程序设计的经验；

二、实验内容。

编写一个延安市旅游导游系统，其中有平面图，有景点列表，可以查询景点简介，也可以查询两个景点间的最短路径，中转次数最少路径以及所有路径，其中要用到数据结构中的图的部分的知识。

三、需求分析。

1.开发系统功能描述。

1）菜单类函数。

void menushow()主界面菜单函数。

void menushow0()输出延安市旅游景点平面图。

void menushow1()延安市简介。

void menulist()旅游景点列表。

void s_menu()查询菜单。

2）查询两点间最短路径。（权值最小）

shortroad(mgraph *g)弗洛伊德法来查询两点间最短路径。

3）查询两点间所有路径。

depsearch(mgraph *g,int v,int w)

allroads(mgraph *g)

利用深度优先遍历图，递归的思想来完成所有路径的查找。

4）.查询中转次数最少的路径。

int isempty(linkqueue *q)判断队是否为空函数。

int initqueue(linkqueue *q)初始化队列函数。

int enterqueue(linkqueue *q,int x)进队函数。

int deletequeue(linkqueue *q,int *x)出队函数。

int nextadjvertex(mgraph *g,int w,int v)求当前顶点的前一个顶点函数。

void bfs(mgraph *g,int vi,int vj)

void reseach(mgraph *g) 广度优先遍历图，递归思想完成查询中转次数最少的功能。

5）.确定顶点位置函数。

int locatevertex(mgraph * g, char v)确定当前顶点所在矩阵位置函数。

6）.查询景点简介函数。

void search_k (mgraph * g) 按景点名称查询。

void search_n (mgraph * g)按景点编号查询。

7）.文件保存以及读出函数。

int read_info(mgraph *g)文件保存函数。

int s**e_info (mgraph * g)文件读出函数。

8）.平面图的创建函数。

mgraph * creatudn(mgraph *g)平面图创建函数，若们有文件，则重新建立文件并保存。

9）.主函数。

void main(void)

四、概要设计。

1、方案设计。

整个程序要实现的功能是导游功能，平面图如果文件里面有存储的话便从文件读出，如果没有存储便创建文件存储。

其中可以实现的功能为：按景点名称查询，按景点编号查询，查询两点间的所有路径，查询两点间的最短路径，查询两点间中转次数最少的路径。按景点名称查询和按景点编号查询在此不做赘述，重要介绍其他三种查询方式。

查询两点间所有路径：该查询方法应用的是深度优先遍历平面图的方法，其中定义两个数组，visit用来标记已遍历过的结点，path用来存储已找到景点的编号，利用递归的思想一层一层向下遍历，最后打印出path数组便可完成该功能。

查询两点间最短路径：该查询方法应用的是弗洛伊德算法，定义的两个二维数组d[和q[其中q数组是用来存储查询到最短路径的景点矩阵的，d数组是用来比较每两个景点之间的权值，每得到一个最小值便将d数组刷新一次，将最后结果存入q数组。

查询两点间中转次数最少的路径：利用广度优先思想遍历平面图。其中应用的队列的知识。

先将最后一个顶点入队，然后利用nextadjvertex函数求它的上一个结点，利用递归思想一直找到最开始的一个结点。

景区图：延安市主要景点平面图 ↑北延安杨家岭革命旧址延安大学

清凉山景区。

人民公园。二道街

中国抗日军政大学延河大桥百米大道

凤凰山景区

宝塔山。火车站。

万花山景区。

2.数据结构说明。

typedef struct arcell

int adj; /路径长度 */

arcell,adjmatrix[max_vertex_num][max_vertex_num];

adjmatrix[max_vertex_num][max_vertex_num];邻接矩阵。

typedef struct /*图中顶点表示主要景点，存放景点的编号、名称、简介等信息， *

char name[max]; 景点名称。

int num; 景点编号。

char introduction[1000];/简介*/

infotype;

typedef struct

infotype vexs[max_vertex_num]; 存储景点信息的数组。

adjmatrix arcs; 存储邻接矩阵的权值。

int vexnum;//图中的顶点数。

int arcnum; /图中的弧数。

mgraph;

/队列的结构体。

typedef struct node

int date;队列元素的值，在该程序中用来存储景点编号。

struct node *next;

linkqueuenode;队中的每个结点。

typedef struct

linkqueuenode *front;队头指针。

linkqueuenode *fear;队尾指针。

linkqueue;

int visit[max];用来存储景点是否被访问，访问标做1，未访问标做0

int path[max];用来存储所有访问路径。

int top=-1;/*记录路径的长度*/

int d[max][max],用来比较最短路径，不断刷新数组值。

int q[max][max];用来存储最短路径的邻接矩阵。

五、详细设计及运行结果。

1.各函数之间的调用关系图。

2.各模块流程图。

创建函数。查询所有路径。

查询中转次数最少的路径。

查询带权值最小路径。

程序设计过程及编码。

创建函数。mgraph * creatudn(mgraph *g初始化图形，接受用户输入。

int i,j,k,w;

char v1[20],v2[20];

printf("请输入地图所有景点的数目，以及所有路径的数目：")

scanf("%d %d",&g->vexnum,&g->arcnum);

for (i=1;i<=g->vexnum;ig的初始化邻接矩阵）

for (j=1;j<=g->vexnum;j++)

g->arcs[i][j].adj=infinity;

printf("请输入景点的编号：、名称、简介：");

for(i=1;i<=g->vexnum;i++)

for(j=1;j<=g->vexnum;j++)

g->arcs[i][j].adj=infinity;

printf("请输入每条路径长度：");

for(k=1;k<=g->arcnum;k++)

printf("第%d条边：",k);

printf("连接的景点名称为：");

scanf("%s",v1);

scanf("%s",v2);

printf("该路径长度为：");

scanf("%d",&w);

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了