数据结构报告 校园导航问题

数据结构报告校园导航问题

一、引言

校园导航问题是在大型校园环境中，为了帮助学生、教职员工和访客快速准确

地找到目的地而提出的。校园导航系统需要提供用户友好的界面和高效的导航功能，以满足用户的需求。本报告将介绍一个基于数据结构的校园导航系统的设计和实现。

二、问题描述

在大型校园中，学生、教职员工和访客常常面临找不到目的地的问题。校园导

航系统的目标是提供一个方便、快捷且准确的导航服务。该系统需要满足以下需求：

1. 提供校园地图：系统需要包含校园的地图信息，包括建筑物、道路和其他地

标的位置和连接关系。

2. 支持路径规划：用户可以输入起始点和目的地，系统能够计算出最短路径，

并提供导航指引。

3. 支持多种交通方式：系统需要考虑不同交通方式，如步行、自行车和汽车，

并根据用户选择提供相应的路径。

4. 提供实时信息：系统需要实时更新校园地图信息，包括建筑物的开放时间、

道路的交通情况等。

三、设计思路

为了实现校园导航系统，我们可以采用以下数据结构和算法：

1. 图结构：校园地图可以表示为一个有向加权图，其中节点表示建筑物或地标，边表示道路或连接关系，边的权重表示距离或时间。

2. 最短路径算法：可以使用Dijkstra算法或A*算法计算起始点到目的地的最短路径。

3. 用户界面：可以设计一个用户友好的界面，包括输入起始点和目的地、选择

交通方式等功能。

四、系统实现

基于上述设计思路，我们可以实现一个校园导航系统。系统的实现可以分为以

下几个步骤：

1. 数据采集：收集校园地图信息，包括建筑物和道路的位置和连接关系。可以

使用GPS定位和地图绘制工具进行数据采集。

2. 数据存储：将采集到的数据存储到数据库中，以便系统可以快速访问和处理。

3. 路径规划：根据用户输入的起始点和目的地，使用最短路径算法计算最短路径，并生成导航指引。

4. 用户界面：设计一个用户友好的界面，包括地图显示、输入框、按钮等元素，以便用户可以输入起始点和目的地，并选择交通方式。

5. 实时信息更新：定期更新校园地图信息，包括建筑物的开放时间、道路的交

通情况等，以保持数据的准确性。

五、系统优化

为了提高系统的性能和用户体验，可以考虑以下优化措施：

1. 数据压缩：对地图数据进行压缩，以减少存储空间和传输时间。

2. 路径缓存：缓存常用路径，以减少计算时间。

3. 并行计算：使用多线程或分布式计算，以加快路径计算速度。

4. 实时数据更新：使用传感器和物联网技术，实时获取建筑物的开放时间和道路的交通情况。

六、总结

校园导航问题是一个实际且具有挑战性的问题。通过合理的数据结构设计和算法选择，我们可以实现一个高效准确的校园导航系统。在实际应用中，我们还可以根据用户反馈和需求进行不断改进和优化，以提供更好的导航服务。

校园导航系统设计需求分析

目录 一、引言 (2) 1.编写目的 (2) 2.项目背景 (3) 3.定义 (4) 4.参考资料 (4) 二、任务概述 (5) 1.系统简介 (5) 2.软件用户特点 (5) 3.开发方法 (5) 三、需求规定 (6) 四、运行环境规定 (8) 五、数据库初步设计 (8) 六、程序功能及实现方法概述 (9)

一、引言 随着科技的进步，时代地发展，计算机已越来越深入到人民的生活、工作当中，极大的方便了人民的日常生活和工作。特别是随着科技的不断发展，智能化也不是一个名词，而是实在的随处可见的。算法设计与分析对于程序的实现骑着非常重要的作用，思路才是程序的核心。这个校园导航系统，利用算法设计里的图来解决，它将校园景点作为图的结点，将景点间的路径作为图的边，路径距离作为边的权值。这样一来，求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。这也是计算机代替人工的一个实例，也充分体现算法的重要。针对校园现代化的实现，对于来访我校的访客和新生能够更方便的了解学校的景点，便于参观，也减少导游人员的数量，于是我们编写了这个校园导航系统，为刚入学的新生或是初次到学校参观的人提供一个校园自主导航器引导他们出行。 1.编写目的 目的:校园导航系统的目的： a.现在的大学占地面积越来越大，建筑物越来越多，功能越来越 多样，校内的道路也是纵横交错，校园导航系统可以帮助用户 更加快速的了解学校的道路，建筑布局等（用户主要是新生、 家长、在小学生、教职工等）。 b.在帮助用户了解学校道路、实现导航功能的基础上。校园导航 还录入学校各个建筑物的相关信息，如名称、占地面积、历史、

校园导航系统

目录 摘要 (2) 正文 (3) 1设计目的及要求 (3) 2 设计原理 (3) 2.1 C/C++语言简介 (3) 2.2 开发环境 (3) 2.3系统模块分析 (4) 3设计内容 (4) 3.1方案设计与论证 (4) 3.2数据结构描述与定义 (5) 3.3主要函数的说明 (6) 3.4设计结果验证 (11) 总结与致谢 (14) 参考文献 (15) 附录 (16)

摘要 与传统的地图相比较，地理信息系统有着不可比拟的优势，信息量大，切换方便，可扩展性强。校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。大大节约了旅客参观校园的时间。 本文是采用C++作为开发语言，又最大程度上用了C语言的有关的语法。以visual c++6.0为开发工具。旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。为来往客人参观校园提供方便。 关键字：visual c++6.0 ；校园导航系统；

正文 1设计目的及要求 1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3. 独立完成，提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5. 设计学校平面图，至少包括10个以上场所，校园导航系统能自动找出校园平面图中任意起始点与终点的最佳路径（最短路径）。求并输出路径及路径长度。 2 设计原理 2.1 C/C++语言简介 C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。 C++是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。 2.2 开发环境 随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。

数据结构课程设计模板

河南城建学院 课程设计报告书 专业：计算机科学与技术 课程设计名称：《数据结构课程设计》 题目：校园导航问题 班级：0814122 学号：081412211 姓名：谌文娟 同组人员：许华宇 指导老师：王永皎、赵军民、陈秋红、张延红 完成时间：2014年2月27日

摘要 校园导航要求每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径(最短路径)。要用“邻接矩阵”来存储各点间的距离，然后用floyd算法求出最短路径。所以采用工程思想，将系统共分以下五个模块：节点数据结构类型、创建导航图函数、最短路径导航函数、查询函数声明、主菜单。 关键词：数据结构；算法设计

目录 目录 第一章开发环境和开发工具 (1) 1.1 C语言简介 .......................................................................................................... . (1) 1.2 开发背景 (2) 1.3 开发环境 (2) 第二章算法思想 (3) 2.1 系统需求分析 (3) 2.2 系统总体设计 (4) 2.2.1 系统设计目标 (4) 2.2.2 开发设计思想 (4) 2.2.3 系统功能模块设计 (4) 2.3 算法思想描述 (4) 第三章算法实现 (6) 3.1 数据结构 (6) 3.2 程序模块 (8) 3.3 各模块之间的调用关系 (9) 3.4 源程序代码 (10) 第四章测试与分析 (16) 4.1 测试数据选择 (16) 4.2 测试结果分析 (20) 总结 (21)

校园导航系统数据结构课程设计

校园导航系统数据结构课程设计

前言 现代社会，新兴科技日新月异，信息千变万化，人们在渴望得到最多最广的信息的同时又渴望得到信息的路径能越来越简单，易操作，而且能在简易的操作中得到更多的信息。这就要求信息咨询系统的开发者在开发之时能尽可能的全面理解客户的想法要求，而且在开发的时候能更简易的操作和更新，这种思想都符程序设计的开发思想。 本次设计任务是设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径），其实就是数据结构中图类的问题。将校园景点作为图的结点，将景点间的路径作为图的边，路径距离作为边的权值。这样一来，求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。 关键字：校园导航数据结构 C语言

目录 1引言 (4) 2程序设计 (4) 2.1设计时间 (4) 2.2设计目的 (4) 2.3设计任务 (4) 2.4需求分析 (4) 2.5概要设计 (5) 2.5.1.设计思路和主要步骤 (5) 2.5.2程序流程图 (6) 2.6详细设计 (6) 2.6.1学校整体局部 (6) 2.6.2打印图 (8) 2.6.3导航函数 (9) 2.6.4查找路径 (10) 2.6.5记录最短路径 (11) 3调试分析 (11) 4附录 (15) 总结 (21) 参考文献 (22)

1引言 本概要设计说明书基于之前建立的软件需求设计基础上，对“蚌埠学院校园导航系统”做出概要分析。主要解决了实现该系统需求的程序模块设计问题。包括如何把该系统划分成若干个模块、决定各个模块之间的接口、模块之间传递的信息，以及数据结构、模块结构的设计等。在以下的概要设计报告中将对在本阶段中对系统所做的所有概要设计进行详细的说明。 2程序设计 2.1设计时间 2015-06-01—2015-06-15 2.2设计目的 1.加深对《数据结构》这门课程的进一步理解与巩固 2.通过课程设计，培养自己的编程能力以及团队协作能力 3.加强自己对实际问题的分析能力，以及如何更好的将一些经典的算法应 用于实际 2.3设计任务 该导航系统为参观者提供校园主要建筑的基本信息及各建筑间的距离，同时通过该系统计算出所在位置到目的地的最短路径。 2.4需求分析 1.程序体现的功能： (1) main()——主函数 (2) navigate()——导航函数 (3) pri()——打印校园平面图函数 (4) visit()——递归查找路线函数 2.正确输入与输出形式： 如： 执行建筑查询功能： ①输入为：sod 输出为：该建筑所在的坐标为7 8 种有花草和一些艺术标记物

数据结构报告 校园导航问题

数据结构报告校园导航问题 一、引言 校园导航问题是在大型校园环境中，为了帮助学生、教职员工和访客快速准确 地找到目的地而提出的。校园导航系统需要提供用户友好的界面和高效的导航功能，以满足用户的需求。本报告将介绍一个基于数据结构的校园导航系统的设计和实现。 二、问题描述 在大型校园中，学生、教职员工和访客常常面临找不到目的地的问题。校园导 航系统的目标是提供一个方便、快捷且准确的导航服务。该系统需要满足以下需求： 1. 提供校园地图：系统需要包含校园的地图信息，包括建筑物、道路和其他地 标的位置和连接关系。 2. 支持路径规划：用户可以输入起始点和目的地，系统能够计算出最短路径， 并提供导航指引。 3. 支持多种交通方式：系统需要考虑不同交通方式，如步行、自行车和汽车， 并根据用户选择提供相应的路径。 4. 提供实时信息：系统需要实时更新校园地图信息，包括建筑物的开放时间、 道路的交通情况等。 三、设计思路 为了实现校园导航系统，我们可以采用以下数据结构和算法： 1. 图结构：校园地图可以表示为一个有向加权图，其中节点表示建筑物或地标，边表示道路或连接关系，边的权重表示距离或时间。

2. 最短路径算法：可以使用Dijkstra算法或A*算法计算起始点到目的地的最短路径。 3. 用户界面：可以设计一个用户友好的界面，包括输入起始点和目的地、选择 交通方式等功能。 四、系统实现 基于上述设计思路，我们可以实现一个校园导航系统。系统的实现可以分为以 下几个步骤： 1. 数据采集：收集校园地图信息，包括建筑物和道路的位置和连接关系。可以 使用GPS定位和地图绘制工具进行数据采集。 2. 数据存储：将采集到的数据存储到数据库中，以便系统可以快速访问和处理。 3. 路径规划：根据用户输入的起始点和目的地，使用最短路径算法计算最短路径，并生成导航指引。 4. 用户界面：设计一个用户友好的界面，包括地图显示、输入框、按钮等元素，以便用户可以输入起始点和目的地，并选择交通方式。 5. 实时信息更新：定期更新校园地图信息，包括建筑物的开放时间、道路的交 通情况等，以保持数据的准确性。 五、系统优化 为了提高系统的性能和用户体验，可以考虑以下优化措施： 1. 数据压缩：对地图数据进行压缩，以减少存储空间和传输时间。 2. 路径缓存：缓存常用路径，以减少计算时间。 3. 并行计算：使用多线程或分布式计算，以加快路径计算速度。

校园导航系统的两个代码

#1 数据结构实验之校园导游咨询 #include #include #include #include #include #include "stdio.h" #define null 0 #define num 20 #define maxdist 10000 typedef struct{ char data[num]; int edges[num][num]; }graph; void dijkstra(graph g,int n,int i,int d[num],int p[num]) {int s[num]; int mindist,dist; int j,k,u; for(j=0;j

} } void opdijk(int v0,int n,int d[],int p[]) {int i,pre; for(i=0;id[i][k]+d[k][j]) {d[i][j]=d[i][k]+d[k][j] ; p[i][j]=p[i][k]; } } void opfloy(int n,int d[][num],int path[][num]) {int i,j,next; for(i=0;i

(整理)校园导航系统罗生存组,李建武,何月甫

数据结构课程设计报告 图书管理系统 题目：图书管理系统 组长：罗生存成员：李建武何月甫 开发日期：2011-12-30 一、需求分析 二、软件功能模块描述 1.数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要 采用邻接矩阵的存储结构来真实反映各节点到其他所有节点的路径长（权值大小）。 2.导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。包 括：各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。 3.求最短路径模块：本模块的基本思想是采用迪杰斯特拉算法求最短路径。 次模块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功能。 4.主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的 对各个地点进行导航。 三、功能模块分析 2.2导航平面图（无向图）：

河南科技学院平面图 2.3数据结构描述与定义： 2.3.1节点数据类型 #define MAX_V 30 typedef struct { char* vexs[MAX_V]; //顶点向量 int arcs[MAX_V][MAX_V];//邻接矩阵 int vexnum,arcnum;//图的当前顶点数和弧数 }MGraph; 2.3.2创建导航无向图函数 int CreateUDN(MGraph &G) 函数描述：为每个节点进行命名、每个节点到其他所有各节点的定值用 邻接矩阵进行存储

2.3.3求最短路径函数（迪杰斯特拉算法） void ShortPath(MGraph &G,int v0,int p[MAX_V][MAX_V],int d[]) 函数描述：用Dijkstra算法求无向网G中v0节点到其余节点v的最短路径P[v]及带权长度D[V]。 P[V][W]为TURE,则W是从V0到V当前求得最短路径上的顶点。 Final为TURE,当且仅当V属于S,即已经求得从V0到V的最短路径 2.3.4导航菜单函数 void menu() 函数描述：输出各节点的标号，方便用户操作 四、测试结果与分析 校园导航系统登录界面 导航一：任意两地点之间的最短路径演示图

校园导游系统数据结构实习报告

校园导游系统数据结构实习报告 校园导游系统数据结构实习报告 一、引言 随着信息技术的快速发展，数字化校园已成为许多学校的重要建设目标。其中，校园导游系统作为数字化校园的一部分，对于提高校园文化氛围，方便新生和游客游览校园，增强校园归属感起到了重要作用。在这次实习中，我们的主要任务是设计和实现一个校园导游系统，采用数据结构技术对校园地图进行建模和优化，以提供高效、便捷的导游服务。 二、系统设计 1、数据结构选择：考虑到校园地图的复杂性，我们采用了图（Graph）作为基础数据结构。图是由节点（顶点）和边组成的集合，可以很好地表示校园中各个地点之间的连接关系。 2、地图表示：我们将校园地图转化为图，其中每个地点对应一个节点，地点之间的路径对应边。为了更准确地表示实际环境，我们使用了带权重的边，权重表示路径的长度或美观度。 3、导游路径规划：我们使用了最短路径算法，如Dijkstra算法和 A*算法，来规划最佳游览路径。用户可以在系统中设定起点和终点，

系统会根据图中的边和权重计算出最短路径。 4、语音导航：系统可以通过用户的手机实时获取位置信息，并使用TTS（Text-to-Speech）技术将规划的路径转化为语音提示，方便用户边听边走。 5、数据库设计：我们设计了一个关系型数据库，用于存储校园地图信息、用户信息等。通过使用索引和查询优化技术，提高了系统性能。 三、系统实现 1、环境配置：我们使用了Python语言和相关的数据结构库来实现系统。开发环境为Windows 10操作系统，数据库采用了MySQL。 2、代码实现：我们对Python语言和相关库进行了深入学习，掌握了图算法的实现方法。在实现过程中，我们遇到了一些问题，如最短路径算法的优化、语音导航的实时性等。通过查阅资料、讨论和实践，我们成功解决了这些问题。 3、测试与调试：我们对系统进行了全面的测试，包括单元测试、集成测试和系统测试。在测试过程中，我们发现并修复了一些bug，提高了系统的稳定性和可靠性。 4、用户界面设计：我们设计了一个简洁、易用的用户界面，使用户可以方便地使用系统。用户界面包括地图展示、路径规划、语音导航等功能，并支持用户输入和交互。

数据结构课程设计校园导航

一、课程设计目的 本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型 程序的能力，并培养基本的、良好的程序设计技能以及合作能力。 设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问 题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构 和算法设计技术，掌握分析、解决实际问题的能力。 通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算 法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机 操作等基本技能和科学作风方面受到比较系统和严格的训练。 二、课程设计内容 1)问题描述 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 2)基本要求 （1）查询各景点的相关信息； （2）查询图中任意两个景点间的最短路径。 （3）查询图中任意两个景点间的所有路径。 （4）增加、删除、更新有关景点和道路的信息 三、课程设计过程 1．需求分析

（1）设计学校的校园平面图，选取出若干的具有代表性的景点构成一个抽象的无向带权图，顶点为景点，边的权值代表了景点间路径的长度。 （2）将景点的序号，名称，介绍存放起来准备查询。 （3）提供任意景点的信息； （4）提供任意经典的路径查询及其最优路线的查询 （5）平面图景点的增加及删除，以及边和权值（长度）的改变 2．概要设计 1：第一点是主界面的设计，首先，为了该系统各个功能的管理，设计出含有多个菜单项的主菜单界面，可以更方便的使用该系统。 2：第二点是存储结构的设计，采取了图结构类型（mgraph）存储校园图的信息，景点信息用结构数组vexs存储，而且利用全局变量：visited[]数组用于存储顶点是否被访问标志；d[]数组用于存放权值和查找路径顶点的编号；campus是一个图结构的全局变量。 3：第三点是设计各个功能的实现，学校景点的介绍通过函数browsecompus()来实现；查询景点间的最段路径通过Floyd(弗洛伊德)算法实现；查询景点间的所有路径通过allpath函数和path函数来实现；更改图的信息可以由主函数changegraph以及其他函数可以实现。 3．详细设计 （1）主要的操作界面的显示以及无向网操作

数据结构实践课程报告

算法设计实践课程报告 学院：计算机学院 班级： 学号： 姓名：

一、课程目的 本课程设计为培养学生综合实践的能力，理论知识和实际有机的结合起来，锻炼学生实际分析问题和解决问题的能力，提高学生适应实际、实践编程的能力，使对C++系统编程有一个深入的了解。 二、题目 3. 校园导游程序——最短路径应用 问题描述： 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 基本要求： 实现一简单的功能查询界面： （1）查询各景点的相关信息； （2）选定某一景点作为起始点，可查询从该景点出发到其余各景点的最佳游览路径。 三、算法分析与设计 首先，此算法建立了类mgraph，通过邻接矩阵存储校园景点图，并通过构造函数初始化图，手动给校园图附上相关信息（包括景点编号、名称、简介、路径及路径长度等）。然后，手动绘制了部分模拟校园图。该函数包括深度优先遍历图和迪杰斯特拉最短路径算法，主

要功能是实现校园七个景点（0.图书馆，1.三山楼，2.三江楼，3.教工浴室，4.西山操场，5.西山美食城，6.京江操场）的简介和最短路径的算法，最后用主函数输出结果，用switch语句分别输出，最后求出两点之间的最短路径。 四、运行结果及分析 输出结果：

五、总结 这个程序在调试时，我发现一次只能查找一个景点的相关介绍，之后的最短路径的计算生成时是成功的，但在调试时却不是很好，输出结果有误。 通过这次算法设计实践，我对数据结构的运用有了更深的体会，对无向图和创建无向图的理解更加深刻，理解了迪杰斯特拉算法的原理，不再是盲目地照搬书上的程序。之后，我还发现了我的不足之处，对程序的设计还不过灵活。 附录：源程序清单 #include #include using namespace std; const int maxsize=100; class mgraph { public: mgraph(string a[],int n,int e);//构造函数，建立n个顶点，e条边的图 ~mgraph(){} //析构函数 void dfstraverse(int v);//深度优先遍历 void shortpath(mgraph g,int v,int r);//求v到其余各个顶点的最短路径 private: string vertex[maxsize];//存放图中顶点的数组 int arc[maxsize][maxsize];//存放图中边的数组 int vertexnum,arcnum;//图中的顶点数和边数 }; mgraph::mgraph(string a[],int n,int e) { int i,j,k; vertexnum=n; arcnum=e; for( i=0;i

课设题目

数据结构课程设计题目 1．八皇后问题 设计要求：在棋盘上摆放八个皇后，使任意两个不在同一行，同一列，及同一对斜线上。皇后的摆位任意，由用户设定，程序给出剩余皇后的摆位。 2.哈夫曼编/译码器； 设计要求：针对字符集A及其各字符的频率值（可统计获得）给出其中给字符哈夫曼编码，并针对一段文本（定义在A上）进行编码和译码，实现一个哈夫曼编码/译码系统。 3.关键路径 设计要求：对于任何大型工程项目（由若干小工程组成），求其关键路径。 4.最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。 5.校园导航问题 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 6.一元多项式的代数运算 设计要求：计算任意两个一元多项式的加法、减法以及乘法。 7.算术表达式求值 设计要求：将任意一个算术表达式转化为逆波兰表示，并根据逆波兰表示计算表达是的值。 8、运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）要求：1).可以输入各个项目的前三名或前五名的成绩；

2)．能统计各学校总分， 3)．可以按学校编号、学校总分、男女团体总分排序输出； 4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 9、订票系统 任务：通过此系统可以实现如下功能： 录入：可以录入航班情况 查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况； 订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班； 退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 修改航班信息：当航班信息改变可以修改航班数据文件 要求： 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 10、拓扑排序 任务：编写函数实现图的拓扑排序。 11、迷宫求解 任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； 要求： 在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法； 12、文章编辑 功能：输入一页文字，程序可以统计出文字、数字、空格的个数。 静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文

顺序结构课程设计 校园导航系统总结

《数据结构》课程设计报告 计算机与信息工程系

《数据结构》课程设计评阅表

目录 一、引言 1.1项目意义 (4) (4) 二、设计过程 (4) (5) (6) (7) (7) (7) 三、测试及运行结果 (7) (7) 四、总结 (10) 五、参考文献 (11) 六、附录 (11)

一、引言 针对学校现代化的实现，对于来访我校的访客能够更方便的了解学校和学校景点，以及提供给访客从一个景点到另一个地点怎样走路径最短的方案，以节省访客的时间游览及行走路程，于是编写了这个校园导航系统。 数据结构是计算机科学与技术专业,计算机信息管理与应用专业,网络等专业的基础课,是十分重要的核心课程.所有的计算机系统软件和应用软件都要用到各种类型的数据结构.因此,要想更好地运用计算机来解决实际问题,仅掌握几种计算机程序设计语言是难以应付当前众多复杂的课题.要想有效地使用计算机,充分发挥计算机的性能,还必须学习和掌握好数据结构的有关知识.打好"数据结构"这门课程的扎实基础,对于学习计算机专业的其他课程,如操作系统,数据库管理系统,软件工程,编译原理,人工智能,图视学等都是十分有益的. 随着现在科技的发展，智能化也不是一个名词，而是实在的随处可见的。算法设计与分析对于程序的实现起着非常重要的作用，思路才是程序的核心。这个校园导航系统，利用算法设计里的图来解决，它将校园景点作为图的结点，将景点间的问题就抽象成了求图中一结点到另一结点的问题。这就是计算机代替人工的一个实例，也充分体现数据结构和算法的重要。 二、设计过程 程序设计分析 校园导航模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表点，用图的边代表景点之间的路径。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表储存，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度及路线时可用迪克斯特拉（Dijkastra）算法实现。最后用switch选择语句选择执行浏览推荐路线或查询最短路径，并且主页面会简单描述景点的信息。

校园导航问题

设计你的学校的平面图，至少包括 10 个以上的景点(场所)，每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径(最短路径)。 要求： (1)以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。 (4)修改景点信息。 实现提示： 普通情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。 (1)数据结构设计(包括逻辑结构设计和存储结构设计) 1. 创建有向图 G，在空图 G 中插入 n 个顶点和 e 条边。并实现最短路径算法。 2. 定义邻接矩阵实现图的存储类型定义。用来保存景点的数据信息，如景点间的距离。 3. 定义结构体数组实现景点信息的保存，如景点名称等 (2)算法设计 1.根据景点信息建立临接矩阵 2.调用 Dijkstra 求出两景点的最短路径 3.建立结构体数组存储数据 4.将修改的信息直接写入数组中 (1)函数调用关系图 主函数 main()挨次调用以下个函数 #include "AdjMGraph.h" #include "Dijkstra.h" (2)函数接口规格说明 调用库函数为 #include #include #include 调用自定义函数为 #include "AdjMGraph.h" #include "Dijkstra.h"

各函数说明 void ListInitiate(SeqList *L) /* 初始化顺序表 L*/ int ListLength(SeqList L) /* 返回顺序表 L 的当前数据元素个数*/ int ListInsert(SeqList *L, int i, DataType x) int ListDelete(SeqList *L, int i, DataType *x) /*删除顺序表L 中位置为 i(0 <= i = size-1)的数据元素并存放到x 中*/ /*删除成功返回 1，删除失败返回 0*/ int ListGet(SeqList L, int i, DataType *x) /*取顺序表L 中第 i 个数据元素存于 x 中，成功返回 1，失败返回 0*/ void Dijkstra(AdjMGraph G,int v0,int distance[],int path[]) 最短路径算法 //置带权有向图 G 为空图 void GraphInitiate(AdjMGraph *G) //判断顶点 vertex 是否是有向图 G 的顶点，是则返回顶点在顶点顺序表中的序号，否则返回-1。 int IsVertex(AdjMGraph *G,DataType vertex) //在带权有向图G 中插入顶点 vertex。如果图中已经有顶点 vertex,则图不变 void InsertVertex(AdjMGraph *G,DataType vertex) /* 在带权有向图G 中插入一条第v1 个顶点指向第 v2 个顶点，权值为weight 的有向边。 * 如果 v1 和 v2 有一个不是图中的顶点，则图不变；如果 v1 和 v2 相等，则图不变。 * 如果图已经包含该边，则边的权值更改为新的权值，时间复杂度:O(1)。 */ void InsertEdge(AdjMGraph *G,int v1,int v2,int weight) //判断第 v1 个顶点到第 v2 个顶点的边是否是有向图G 的边，是则返回 1，否则返回 0.时间复杂度 O(1)。 int IsEdge(AdjMGraph *G,int v1,int v2) /* 在带权有向图 G 中删除一条第 v1 个顶点指向第 v2 个顶点的有向边。 * 如果 v1 和 v2 有一个不是图中的顶点，则图不变；如果 v1 和 v2 相等，则图不变。 * 如果不是图的边，则图不变。时间复杂度:O(1)。 */ void DeleteEdge(AdjMGraph *G,int v1,int v2) //在带权有向图G 中取第v个顶点的第一个邻接顶点，如果这样的邻接顶点存在，则返回该顶点在顶点顺序表的序号，否则返回-1.时间复杂度:O(n)。 int GetFirstVex(AdjMGraph G,int v) //创建有向图 G，通过在空图 G 中插入 n 个顶点和 e 条边实现。时间复杂度:O(n^2+e)。 void GraphCreat(AdjMGraph *G,DataType v[],int n,RowColWeight W[],int e) (1)数据结构设计(包括逻辑结构设计和存储结构设计)