分类号编号
华北***大学
North China Institute of Water Conservancy and
Hydroelectric Power
课程设计
题目校园导航
院系信息工程学院
专业计算机科学与技术
姓名******
学号201117000
指导教师*****
2012年7月6 日
目录
1.需求分析 (1)
1.1问题描述 (1)
1.2课程设计目的 (1)
1.3设计要求 (1)
2.概要设计 (2)
2.1任务定义 (2)
2.2数据结构 (2)
2.3 校园平面图展示 (2)
2.4系统功能图 (4)
3.详细设计 (4)
3.1各个模块名称和功能 (4)
3.2具体函数模块详解 (5)
3.2.1校园平面图展示 (5)
3.2.2任意两点的所有路径 (5)
3.2.3校园基础设施介绍 (6)
3.2.4指定两点间最短路径 (6)
3.2.5单点到其他左右顶点间最短路径 (6)
3.2.6华北水利水电学院简介 (7)
3.2.7访客留言 (7)
3.2.8浏览访客留言 (7)
3.3 主要算法思想描述 (7)
3.4各函数之间的调用关系示意图 (7)
4.测试与分析 (8)
4.1测试显示 (8)
4.2调试分析 (12)
4.2．1调试过程中遇到的问题与解决方案 (12)
4.2.2算法的时空复杂度分析 (12)
5.用户使用说明 (12)
6.实验总结 (14)
7.参考文献 (14)
8.附件 (15)
校园导航系统
1.需求分析
1.1问题描述
我们熟悉一个地方的地形情况通常是借助于一张地图，通常的地图包含的信息十分的有限，而且具体到某一个建筑物，你不能了解到它的进一步的详细的情况。因此，导航系统就应运而生了。
具体到本系统，作为用户浏览校园时，只拿着学校的地图是能够游遍全校，但是各建筑内部的情况就必须实地考察才能了解，既费时又费力。有了我们的校园的导航系统，用户可以根据自己的需要，迅速找到所关心的地点，并且可以看到它的详细的信息。
1.2课程设计目的
本课程设计的目的就是要达到理论与实际应用相结合，使我们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，培养程序设计技能如下：
(1)了解并掌握数据结构算法的设计方法，具备初步的独立分析和设计能力；
(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
(3) 独立完成，提高运用所学的理论知识和方法独立分析和解决问题的能力；
1.3设计要求
设计一个校园导航系统，为来访的客人提供导航服务，具体要求：
(1) 设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
（2）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息
(3) 为来访客人提供图中任意景点相关信息的查询。
(4) 提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径以及任意景点到其他所有景点的最短路径查询。
(5) 列出所有校内无重复排列的景点，将所有景点的距离以邻接矩阵的方式呈现给使用者，提供使用者选择功能界面，按照提示进行操作。
2.概要设计
2.1任务定义
本系统包含一个文件，设计分有菜单、显示信息、弗洛伊德算法、迪杰斯特拉算法，其中弗洛伊德算法是求两个景点之间距离最短的算法，同时在本系统中又添加一些新的功能，这些在模块分析中将介绍到，本系统的基本任务有1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径
2.2数据结构
class CNode //留言功能建立的类
{ public:
CNode(char *strMessage1,char *strTime1,int visited1);
char strMessage[ID_LEN];
char strTime[30];
int visited;
CNode *next;
};
class CList //建立链表，并保存链表的内容（留言的内容）{public:
void Save();void Load(); void Show();
void InsertToLast(char* strMessage,char* strTime,int visited);
CNode* Tail();
private:
CNode m_head;
};
typedef struct edgenode //声明邻接表所定义的结构体
{ int adjvex; int value;
struct edgenode *next;
}ArcNode;
typedef struct vexnode
{ char data[15];
ArcNode * firstarc;
}VHeadNode;
typedef struct
{ VHeadNode adjlist[n];
}AdjList
2.3 校园平面图展示
本课程设计的内容为“校园导航”，校园平面图中取华北水利水电学院的１7个常去地点，在图中已标出主要路线，各路线的长度如图中所示，本系统的基本
任务是设计你的学校的平面图，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径，为来访客人提供图中任意景点相关信息的查询，同时为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径，其平面图如下：
2.4系统功能图
图2 系统功能图
3.详细设计
3.1各个模块名称和功能
本系统可以分为9个模块，每个模块实现了一种功能，同时每个模块中又有若干个函数构成，即各个模块的名称和实现的功能如下表：
表1 模块功能略图
3.2具体函数模块详解
3.2.1校园平面图展示
平面图展示包含的函数有show ()和MatToList(Graph &t,AdjList *&G)，在show ()函数中调用MatToList(Graph &t,AdjList *&G)，将初始化的邻接矩阵转换为邻接表，然后将邻接表显示在程序中，比较笼统地展示了校园的平面图。
3.2.2任意两点的所有路径
该模块是新添的功能，在任意两点的所有路径模块中包含的函数有PathAll() , MatToList(Graph &t,AdjList *&G)和T_PathAll(AdjList *G,int u,int v,int l,int path[],int d)，其中PathAll()是调用T_PathAll(AdjList *G,int u,int v,int l,int path[],int d)，然后返回给主函数bool值，判断程序的下一步的操作，MatToList(Graph &t,AdjList *&G)是将邻接矩阵转化为邻接表，而本模块中最重要的函数是T_PathAll(AdjList *G,int u,int v,int l,int path[],int d)。
该函数核心代码是利用回溯的深度优先搜索方法，从定点u开始，进行深度优先搜索。由于在搜索过程中，每个顶点只访问一次，所以这条路径必定是一条
简单路径。因此，只要在搜索过程中，需要把当前的搜索线路记录下来。为了记录当前的搜索线路，设立一个数组path保存走过的路径，用d记录走过的长度。若当前扫描到的结点u到结点v的长度不大于l,表示找到了一条路径，则输出路径path.
3.2.3校园基础设施介绍
该模块中的核心函数是Search()，其核心代码是此函数用于为用户提供相关信息的查询服务，本函数提供华北水利水电学院相关基础设施的查询服务。用户只需输入相关的设施名称就能查询到相关的华北水利水电学院基础设施的相关信息。
3.2.4指定两点间最短路径
本模块中包含的函数有shuangdian()和pointpath(Graph &t1,char cstart[],char cend[])，此函数为一辅助函数，该函数体中调用了pointpath(Graph &t1,char cstart[],char cend[])，实际上该函数的功能就是求出起始点到终点的最小路径，只不过为了更好在函数调用过程中理清各函数间的关系同时也是为了使界面设计过程中避免各基础函数代码冗余，从而引进该函数做辅助用。
本模块色核心函数是pointpath(Graph &t1,char cstart[],char cend[])，该函数核心代码为迪杰斯特拉算法，用以求任意两景点之间最短路径。具体思想为设置并逐步扩充集合path，存放以求出的最短路劲的顶点，尚未确定最短路径的顶点放置在另一集合V中，按最短路径长度的递增顺序将V中的顶点加到path中，直到path中包含所有顶点。实现过程中引入了一个辅助数组distance，它的每一个分量distance[i]表示当前找到的从原点到终点的最短路径的长度。
3.2.5单点到其他左右顶点间最短路径
本模块在以狄克斯特拉为原型的基础上稍加改变，在采用狄克斯特拉算法时新增一个终点参数，在输出最小路径时不需要使用for循环将所有原点与其他顶点的路径信息输出，只需输出起点和终点两点间的最短距离即可。
本模块中包含的函数有dandian()和shortest_path(Graph &t,char csource[])，此函数为一辅助函数，该函数体中调用了shortest_path(Graph &t,char csource[])，实际上该函数的功能就是求出一点到其他所有点的最小路径，只不过为了更好在函数调用过程中理清各函数间的关系同时也是为了使界面设计过程中避免各基础函数代码冗余，从而引进该函数做辅助用。
单源最短路径采用狄克斯特拉算法，在集合s的初态只表包含顶点，当是s[i]为0时表示未找到源点到顶点的最短路径，当s[i]为1时表示已找到源点到顶点的最短距离，数组distance记录从源点到其他各顶点当前的最短距离，起初值为distance[i]=t.arcs[b][i](b为源顶点)，从s之外的顶点集合中选择一个顶点，使distance[u]的值最小，于是从源点到达v只通过s中的顶点，把u加入集合s中调整distance中的记录从源点到每个顶点的距离：从原点的distance[j]和
distance[u]+ t.arcs[u][j]中选择较小的值作为新的distance[j],重复上述过程，直到s 中包含其余各顶点的最短路径。另外设置一个数组path[]用于保存最短路径长度，其中path[i]保存从源点到终点当前最短路径中的前一个顶点的景点名称，
3.2.6华北水利水电学院简介
该模块是新添的功能，在该模块中的核心函数是Intro()，其核心代码是输出华北水利水电学院的办学历史和发展状况，该模块比较简单，就不在这里赘述了！
3.2.7访客留言
该模块是新添的功能，在该模块中的核心函数是W()，在该函数中应用了文件，其目的是将历史记录保存下来，以供访客浏览，在该函数中遇到的问题是留言条数变量intV，如何让它真实的显示出来留言条数，我解决的办法是把变量intV也写入到文件中，在每次保存留言时读出该变量，使该变量加1，把留言写入到文件后，将重新把该变量写入到文件中，依次进行，这样就把留言写入到文件中，而留言记录也是正确的数值，同时留言时间是调用系统函数ctime(),这样访客留言就完成了。
3.2.8浏览访客留言
该模块是新添的功能，在该模块中的核心函数是R()，在该函数中应用了文件，是将访客的留言读出来，同时将要更新留言记录中的留言条数变量。
3.3 主要算法思想描述
迪杰斯特拉算法思想
按路径长度递增次序产生最短路径算法：
把V分成两组：（1）已求出最短路径的顶点的集合（2）尚未确定最短路径的顶点集合，将T中顶点按最短路径递增的次序加入到S中。
保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值
S中顶点：从V0到此顶点的最短路径长度
T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度
依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。
3.4各函数之间的调用关系示意图
选择1 选择2 选择3 选择4 选择5 选择6 选择7 选择8
图 3 各函数调用示意图
4.测试与分析
4.1测试显示
图 4 主界面
在主界面中可以显示本系统中包含的所有操作，用户可以选择对应操作的序
MatToL ist(t,G)
函数 T_Path
All(Ad
jList*
G,int u,int v,int l int d ) 函数
show()
函数
PathA ll() 函数 Retur n()函数 Searc h()函数 shuan gdian ()函数 pointp ath(Gr aph&t1,charc start[],char cend[])函数
dandi an()函数 shorte st_pat h(Grap h&t,ch arcsou rce[])
函数
dandi an()函数 Intro()函数
W()函数 R()函数
号，输入正确将进入对应的操作界面。
图 5 两点路径小于4的路径
在该界面中显示所有从起点景点到终点景点长度小于4的所有路径，在所有的路径中可以选择其中的一条路线。
图6 基础设施介绍
用户可以输入导航景点中出现的景点名称，程序将出现相对应景点的基本信息，在该过程中如果输入的景点错误，系统将循环出现要求用户输入正确的景点名称。
图 7 两景点最短路径
用户将在这一界面根据导航景点名称中出现的景点输入起点景点和终点景点，输入正确后，将会出现一条最短了路径，在该路径中包含有经过的景点名称，和两个景点之间的距离。
图8 一点到其他景点的最短距离
用户将在这一界面根据导航景点名称中出现的景点任意输入一个景点名称，输入正确后，将会出现若干条该景点到其他景点的最短了路径，在这些路径中包含有经过的景点名称，和两个景点之间的距离。
图 9 华水简介
本界面中将介绍华北水利水电学院的办学历史和近年来取得的成就，以及华水的人文和育人环境，。
图 10 访客留言
本界面是访客留言，在该界面中用户可以输入字数小于300的留言内容，留言完毕后，将会出现“你的留言成功！”提示语，同时出现两个菜单选项，可供用户选择。
图 11 浏览访客留言
本界面是浏览访客留言，在该界面中访客可以浏览本人的留言和其他访客的留言，在显示留言内容外，还显示留言时间和留言总记录的条数。
4.2调试分析
4.2．1调试过程中遇到的问题与解决方案
本系统中的重要内容是最短路径，在运用最短路径时经常使用的算法是弗洛伊德算法，在这个算法中出现了一个错误，就是在输入一条路径长度大于3的路径时仅仅显示3个景点名称，在系统中使用断点进行测试，发现在系统中一个循环语句使用错误，经过改正后，可以输出该条路径上所有的景点名称。
同时在系统中新添了一个功能中，就是输出两点之间路径小于4的所有简单路径，在这个过程中，忽略了把对应的两点距离输出，或者是挑选出几条最有的路径，这些是经过老师的指导下发现了诸多的问题，希望在以后注意到这些问题。
4.2.2算法的时空复杂度分析
对应题目的要求，我总共提供了八个选项操作对于每一个操作的分析如下：
1.校园平面图展示，实现这个功能仅仅显示出来关于华北水利水电学院的17个经常去的景点，用邻接表大概表示学校景点的地理位置，故其时间复杂度为o(1)，空间复杂度为o(1)；
2．任意两点的所有路径，实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n^3)，空间复杂度为o(1)；
3.校园基础设施介绍，在这个操作中允许使用者输入一个景点名称，然后再根据景点名称来或取其相关的信息，这个操作要扫描线性表，其时间复杂度为o(n)，空间复杂度为o(n)；
4.定两点间最短路径，实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n^3)，空间复杂度为o(1)；
5.到其他左右顶点间最短路径，实现这个功能用到了Floyd算法，他用到了一个三重的for()循环，故其时间复杂度为o(n^3)，空间复杂度为o(1)；
6.水利水电学院简介，实现这个功能仅仅显示出来关于华北水利水电学院的基本信息，故其时间复杂度为o(1)，空间复杂度为o(1)；
7.访客留言，实现这一功能要使用文件，首先建立链表，将留言存放在链表中，将链表的内容存放到文件中，时间复杂度为o(n)，空间复杂度为o(1)；
8. 浏览访客留言，首先将存放在文件中的留言读出存放在链表中，将链表的内容显示出来，时间复杂度为o(n)，空间复杂度为o(1)；
其他操作的时空性
1．在系统的设计中考虑到道路网的复杂性，故采用邻接矩阵作为存储结构，其空间复杂度为O（e）此时的空间复杂度也为O(e)。构建邻接矩阵的时间复杂度为O（n2+e*n），故本系统在构件图的时候的时间复杂度为O（n2+e*n）。
2．由于本系统在执行的时候，需要用户临时输入求最短的路径。迪杰斯特拉算法的时间复杂度比弗洛伊德算法的时间复杂度低。从这一角度考虑用地杰斯特拉算法更为合适。且其算法的时间复杂度为O（n3）.
5.用户使用说明
本系统使用说明：当用户将程序经过编译，连接后，点击运行，在DOS环境里面将看到一个选项菜单，菜单里面提供了8种操作，同时输出了一行提示信息：
“请选择导航功能”，然后用户可以输入一个1—8之间的数字进行选择性的操作，例如，您想进行显示华北水利水电学院平面图，您可以从键盘输入数字‘1’，这样华水的校园平面图将显示出来；同时，您想查询华北水利水电学院的基础设施，您可以从键盘中输入数字“3”，当然，一般而言先应该进行“浏览所有景点名称”操作。如果您选择了浏览所有景点名称操作，在屏幕上将会显示出17个景点的名称，这些景点是事先加进去的，用户可以对这些景点进行任何程序所提供的操作。
下面，我将详细介绍本程序的使用方法：在浏览景点后，菜单将会继续显示出来，为您提供操作选择。
如果您想进行“校园平面图展示”操作，输入数字‘1’，然后程序将以邻接表的形式显示出来华水的平面图，显示完毕后，显示出两个菜单 1.返回主菜单2.退出程序，选择1可以返回到主菜单，选择2可以退出程序。
如果您想进行“任意两点的所有路径”操作，首先输入数字‘2’，然后程序将会提醒您输入起始景点名称，接着提醒输入终点景点名称，在该操作中如果输入错误，将显示出两个菜单 1.返回主菜单 2.退出程序，选择1可以返回到主菜单，选择2可以退出程序；输入正确，系统将显示出全部长度小于4的所有路径，接着系统出现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。
如果您想进行“校园基础设施介绍”操作，首先输入数字‘3’，然后程序将会提醒您输入要查询景点名称，在该操作中如果输入错误，将显示出一句提示“I'am sorry,我校没有此类设施!”接着系统出现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作；如果输入的景点名称正确将显示出该设施的基本信息，同时会出现三个菜单1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。
如果您想进行“指定两点间最短路径”操作，首先输入数字‘4’，然后程序将会提醒您输入起始景点名称，接着提醒输入终点景点名称，在该操作中如果输入错误，系统将进行循环的要求输入景点的名称，直到输入的景点名正确；如果输入正确，系统将显示出两个景点之间的最短路径，接着系统出现三个菜单 1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。
如果您想进行“单点到其他左右顶点间最短路径”操作，首先输入数字‘5’，然后程序将会提醒您任意输入一个景点名称，在该操作中如果输入错误，系统将进行循环的要求输入景点的名称，直到输入的景点名正确；如果输入正确，系统将显示出该景点到其他景点的所有最短路径，接着系统出现三个菜单 1.返回主菜单 2 返回上一级 3退出程序，我们可以跟着提示选择自己的操作。
如果您想进行“华北水利水电学院简介”操作，首先输入数字‘6’，接着将显示出华北水利水电学院的简单介绍，接着系统出现两个菜单 1.返回主菜单 2退出程序，我们可以跟着提示选择自己的操作。
如果您想进行“访客留言”操作，首先输入数字‘7’，接着将显示出提示“你输入你的留言(300字以内)”，输入完成后，接着系统出现提示“你的留言成功!”和两个菜单1. 继续留言 2退出，我们可以跟着提示选择自己的操作。
如果您想进行“浏览访客留言”操作，首先输入数字‘8’，接着将显示出所有的留言记录，接着将出现两个菜单1. 继续浏览 2退出，我们可以跟着提示选择自己的操作。
这些将是本系统中的全部操作说明，请使用者务必按步骤操作。
备注：经过测试，本程序的所有操作都能正常执行，您可以选择性的对他进行操作。
6.实验总结
本次课程设计的题目是校园导航系统，校园导航体现了一个管理系统的需求分析、系统设计、数据结构设计、界面设计和开发实现的完成过程，同时经过这两周紧张而又充实的课程设计，使我对数据结构这一门课程的相关知识有了全面深刻的认识，尤其是对图这一数据结构的相关知识掌握的更加全面和牢固，特别是对迪杰斯特拉算法的思想和具体实现有了进一步的认识。
在这次试验中，我实现了课题选定、资料查找、流程图设置、各模块的算法设计、各模块和主程序的源程序编程、最后的调试等步骤、最后的调试等步骤，完成了“校园导航系统”这个程序的设计，在确定了大致上的方向后，我也遇到了很多细节方面的问题，不过在我的努力在，一个个问题都最终解决了，通过这次课程设计，是我充分认识了自己一些方面的不足，同时经过课程设计时与同学们不断讨论，使我对数据结构有了更深入和更全面的认识。同时经过此次课程设计，使我懂得任何一门计算机语言学习，都是应该理论与实际的结合，光有理论知识是不行的。
数据结构这门课程的学习已经告一段落，但不代表这门课程的学习彻底结束，同时通过本次课程设计暴露出还有很多很多的知识还没掌握，同时也暴露了我在很多上面有误解，每门课都是要踏踏实实的学的，而不是到考前恶补，可能成绩会比较好看，但是实际就什么都不会了，脚踏实地是非常重要的学习态度，同时也是很重要的重要的态度。
本次实验对于我来说是非常重要的经历，因为在做程序的过程中，基本上体验了课题选定、资料查找、流程图设置、各模块的算法设计、各模块和主程序的源程序编程、最后的调试等步骤的流程，为我们以后做项目打好一个最基本的基础。
7.参考文献
【1】谭浩强 .C程序设计［Z］.北京：清华大学出版社，2001.
【2】严蔚敏编著数据结构（c语言版）北京：清华大学出版社
【3】夏克简编著数据结构与算法北京：国防工业出版社
【4】张选平编著数据结构北京：机械工业出版社
8.附件
#include
#include
#include
#include
#include
#define n 100
#define ID_LEN 300
#define max 99999
class CNode
{
public:
CNode(char *strMessage1,char *strTime1,int visited1);
CNode();
public:
char strMessage[ID_LEN];
char strTime[30];
int visited;
CNode *next;
};
CNode::CNode()
{
next=NULL;
strcpy(strMessage,"");
strcpy(strTime,"");
visited=0;
}
CNode::CNode(char *strMessage1,char *strTime1,int visited1) {
strcpy(strMessage,strMessage1);
this->visited = visited1;
strcpy(strTime,strTime1);
next = NULL;
}
class CList
{
public:
void Save();
void Load();
void InsertToLast(char* strMessage,char* strTime,int visited);
void Show();
CNode* Tail();
private:
CNode m_head;
};
void CList::Load()
{
FILE* fp = fopen("list.dat","rb");
if(fp==NULL)
return;
CNode tn;
int n1;
while(!feof(fp))
{
n1 = fread(&tn,sizeof(tn),1,fp);
if(n1!=1)
break;
InsertToLast(tn.strMessage,tn.strTime,tn.visited);
}
fclose(fp);
}
void CList::Save()
{
FILE* fp = fopen("list.dat","ab");
if(fp==NULL)
return;
CNode tn;
CNode* p = m_head.next;
while(p)
{
strcpy(tn.strMessage,p->strMessage);
strcpy(tn.strTime,p->strTime);
tn.visited=p->visited;
fwrite(&tn,sizeof(tn),1,fp);
p = p->next;
};
fclose(fp);
}
CNode* CList::Tail()
{
CNode* p =&m_head;
while(p->next)
p =p->next;
return p;
}
void CList::InsertToLast(char* strMessage,char* strTime,int visited)
{
CNode* p=new CNode(strMessage,strTime,visited);
Tail()->next = p;
}
void CList::Show()
{
CNode* p = m_head.next;
while(p)
{
cout.setf(ios::left);
cout<<"留言信息"< cout< cout< cout<<"留言时间"; cout< cout<<"\t\t\t\t\t\t\t留言条数"; cout< cout< p = p->next; } } class Graph { public: int arcs[n+1][n+1]; //图的邻接矩阵 void shortest_path(Graph &t,char csource[20]) ; //单点到所有其他点的最小路径 void pointpath(Graph &t,char cstart[20],char cend[20]) ; //任意两点之间的最小路径}; char *p[17]={"综合实验室","图书馆","讲堂群","1-5号教学楼群","6号教学楼","办公楼","文体中心","南区超市","软件实验室","操场","南区男生公寓楼","南区食堂","北区女生公寓楼","北区食堂","北区超市","校医楼","学校职工楼"}; char *m[17]={"综合实验楼位于学校正门西面，是我们学校的标志性建筑，主要 算法设计与分析课程设计 题目：校园导航问题 文档： 物联网工程学院物联网工程专业 学号 学生姓名 班级物联网1101 二〇一三年十二月 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路（最短路径）。 本系统为用户提供以下功能: (一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。 (二)、查询校园各个场所和景点信息; (三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。完成需要操作时，退出系统 校园导航查询系统的开发方法总结如下： (1) 需求分析，了解学校各个场所与场所或者是各个景点与景点之间的信息，路径和距离，考虑该如何设计才能满足用户需求。 (2) 概要设计，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。 (3) 详细设计，设计系统界面并编辑实现其各个功能的代码。 (4) 调试分析，在设计完成后，调试系统运行的状况，修改完善系统,然后进行测试。 一、需求分析 1学校以及各景点介绍模块 采用一维数组将学校景点依次排放好编号G.vex[i].number=i 在选择校园介绍的时候，弹出G.vex[0]校园简介。在选择各景点信息的时候，可按编号查询2查询最短路径（主要） 查出出发地到想要到达的景点的最短路径，初步构想采用最经典的迪杰斯特拉算法最短路径函数 3查询各点距离 将所有景点的距离显示出来。 4主菜单页面显示 提供使用者选择功能界面，按照提示进行操作。 5退出 完成需要操作时，退出系统 校园导航系统模式图 二、概要设计 2.1算法设计说明 校园导航模型是由各个景点和景点以及场所和场所之间的路径组成的，所 以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边 代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信 息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查 询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所 以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路 径时可分别用迪杰斯特拉（Dijkastra ）算法和哈密而顿回路算法实现。最后switch 选择语句选择执行浏览景点信息或查询最短路径和距离。 2.1.1学校以及各景点介绍模块 采用了图的邻接矩阵存储结构，首先初始化每一个景点名称（一维数组） fo r(i=1;i 《数据结构I》三级项目报告 大连东软信息学院 电子工程系 ××××年××月 三级项目报告注意事项 1. 按照项目要求书写项目报告，条理清晰，数据准确； 2. 项目报告严禁抄袭，如发现抄袭的情况，则抄袭者与被抄袭者均 以0分计； 3. 课程结束后报告上交教师，并进行考核与存档。 三级项目报告格式规范 1. 正文：宋体，小四号，首行缩进2字符，1.5倍行距，段前段后 各0行； 2. 图表：居中，图名用五号字，中文用宋体，英文用“Times New Roman”，位于图表下方，须全文统一。 目录 一项目设计方案 (3) 二项目设计分析 (4) 三项目设计成果 (4) 四项目创新创业 (5) 五项目展望 (6) 附录一：项目成员 (6) 附录二：相关代码、电路图等 (6) 一项目设计方案 1、项目名称: 垃圾回收 2、项目要求及系统基本功能： 1）利用数据结构的知识独立完成一个应用系统设计 2）程序正常运行，能够实现基本的数据增加、删除、修改、查询等功能3）体现程序实现算法复杂度优化 4）体现程序的健壮性 二项目设计分析 1、系统预期实现基本功能： （结合本系统预期具体实现，描述出对应基本要求(增、删、改、查等)的具体功能） 1. 2. 3. 4. 5. 6. 7. 2、项目模块功能描述 （基本分为组织实施组织、程序功能模块编写、系统说明撰写等。其中程序功能子模块实现） 模块一： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块二： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 模块n： 主要任务：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 1.一元稀疏多项式计算器 [问题描述] 设计一个一元稀疏多项式简单计算器。 [基本要求] 输入并建立多项式； 输出多项式，输出形式为整数序列：n, c1, e1, c2, e2,……, cn, en ，其中n是多项式的项数，ci, ei分别是第i项的系数和指数，序列按指数降序排序； 多项式a和b相加，建立多项式a+b; 多项式a和b相减，建立多项式a-b; [测试数据] (2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9-x+12x-3) (1+x+x2+x3+x4+x5)+(-x3-x4)=(x5+x2+x+1) (x+x3)+(-x-x3)=0 (x+x2+x3)+0=(x3+x2+x) [实现提示] 用带头结点的单链表存储多项式，多项式的项数存放在头结点中。 2.背包问题的求解 [问题描述] 假设有一个能装入总体积为T的背包和n件体积分别为w1, w2, …,wn的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+…+wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2） [实现提示] 可利用回溯法的设计思想来解决背包问题。首先，将物品排成一列，然后顺序选取物品转入背包，假设已选取了前i件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品“太大”不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明“刚刚”装入背包的那件物品“不合适”，应将它取出“弃之一边”，继续再从“它之后”的物品中选取，如此重复，直至求得满足条件的解，或者无解。 由于回溯求解的规则是“后进先出”因此自然要用到栈。 3.完全二叉树判断 用一个二叉链表存储的二叉树，判断其是否是完全二叉树。 4.最小生成树求解（1人） 任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 5.最小生成树求解（1人） 任意创建一个图，利用普里姆算法，求出该图的最小生成树。 6.树状显示二叉树 编写函数displaytree(二叉树的根指针，数据值宽度，屏幕的宽度)输出树的直观示意图。输出的二叉树是垂直打印的，同层的节点在同一行上。 [问题描述] 假设数据宽度datawidth=2,而屏幕宽度screenwidth为64=26,假设节点的输出位置用 （层号，须打印的空格数）来界定。 第0层：根在（0，32）处输出； 数据结构课程设计-校 园导航 -CAL-FENGHAI-(2020YEAR-YICAI)_JINGBIAN 课程设计报告 课程名称数据结构课程设计题目校园导航 指导教师 设计起始日期 5.9~5.16 学院计算机学院 系别计算机科学与工程 学生姓名 班级/学号 成绩 一、需求分析 本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。设计要包括下列要求： 设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 本课题实现校园多个场所（至少10个）的最短路径求解。 （1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。 (2 ) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。 (3) 程序所能达到的功能：本程序可供任何人使用，主要功能1.浏览各单位及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。 （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 a.首先看到的是校园导航系统的菜单： b．查看浏览路线等待输入起始景点： C．选择出发点与目的地等待输入起始景点与目的地编号： d．参看景点信息等待输入景点编号： 二、概要设计 本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。 系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看景点信息；5.退出系统。 选择“浏览各景点及简介”项，显示十个景点的有关信息，包括景点编号，景点名称，景点简介。 选择“查看所有游览路线”项，会进入输入起始景点编号的界面，输入正确编号后会显示起始景点到其余九个景点的最短路线的方案。 选择“选择出发点和目的地”项，会进入输入起始景点与目的景点的界面，输入起始景 点与目的景点，并有空格隔开就得到两景点之间的最佳路径。 选择“查看景点信息”项，会进入输入要查看的景点的界面，如入后会显示该景点的有关信息。 选择“退出系统”项，就会退出程序。 三、详细设计 （1）十三个单位的图 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 摘要 本文的研究工作在于利用计算机模拟人脑进行下黑白棋，计算机下棋是人工智能领域中的一个研究热点，多年以来，随着计算机技术和人工智能技术的不断发展，计算机下棋的水平得到了长足的进步 该程序的最终胜负是由棋盘上岗双方的棋子的个数来判断的，多的一方为胜，少的一方为负。所以该程序主要运用的战术有削弱对手行动战术、四角优先战术、在游戏开局和中局时，程序采用削弱对手行动力战术，即尽量减少对手能够落子的位置；在游戏终局时则采用最大贪吃战术，即尽可能多的吃掉对手的棋子；而四角优先战术则是贯穿游戏的始终，棋盘的四角围稳定角，不会被对手吃掉，所以这里是兵家的必争之地，在阻止对手进角的同时，自己却又要努力的进角。 关键词：黑白棋；编程；设计 题目： 学院： 专业班级： 学生姓名： 指导教师： 2016 年06 月2 9日 目录 一、课程设计目的 (3) 二、课程设计步骤 (3) 三、课程设计内容 (4) 四、课程设计报告 (6) 五、提交材料 (6) 六、考核方式与评分标准 (7) 七、参考文献 (8) 附录1 齐齐哈尔大学软件工程系课程设计说明书（报告）撰写规范 (9) 一、课程设计目的及要求 《数据结构与算法分析》课程设计培养计算机专业的学生的算法程序设计能力。通过上机实验，可以培养学生程序设计的方法和技巧，提高学生编制清晰、合理、可读性好的系统程序的能力，加深对数据结构课程和算法的理解。使学生更好地掌握数据结构的基本概念、基本原理、及基本算法,具有分析算法、设计算法、构造和开发较复杂算法的基本能力。 要求学生能综合运用《数据结构与算法分析》的相关知识，培养学生上机解决一些与实际应用结合紧密的、规模较大的问题的能力，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析实际问题的能力并提高C语言编程技巧，培养良好的编程风格。 课程设计要求独立完成，题目自选（参考题目见三，也可自拟）,但需要老师确认(6月16日前定题)，一人一题，要求程序有能采用交互式工作方式的界面进行功能的选择,只能用文件存储数据和处理数据不能使用数据库。要求在教学周的第18周前完成。 二、课程设计步骤 随着计算机性能的提高，它所面临的软件开发的复杂度也日趋增加。然而，编制一个10000行的程序的难度绝不仅仅是一个5000行的程序的两倍，因此软件开发需要系统的方法。一种常用的软件开发方法，是将软件开发过程分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的课程设计的复杂度远不如(从实际问题中提出来的)一个“真正的”软件，但为了培养一个软件工作者所应具备的科学工作的方法和作风，完成课程设计的应有如下的5个步骤： 1.问题分析和任务定义 通常，课程设计题目的陈述比较简洁，或者说是有模棱两可的含义。因此，在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么，限制条件是什么。注意：本步骤强调的是做什么，而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的形式；输出数据的类型、值的范围及输出的形式；若是会话式的输入，则结束标志是什么，是否接受非法的输入，对非法输入的回答方式是什么等等。这一步还应该为调试程序准备好测试数据，包括合法的输入数据和非法形式输入的数据。 2.数据类型和系统设计 在设计这一步骤中需分逻辑设计和详细设计两步实现。逻辑设计指的是，对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型；详细设计则为定义相应的存储结构并写出各过程和函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。作为逻辑设计的结果，应写出每个 课程设计报告 课程名称数据结构课程设计题目校园导航 指导教师 设计起始日期 5.9~5.16 学院计算机学院 系别计算机科学与工程 学生姓名 班级/学号 成绩 一、需求分析 本次实验设计的任务是实现一个简易的北京信息科技大学的校园导航平面图。设计要包括下列要求： 设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路， 且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 本课题实现校园多个场所（至少10个）的最短路径求解。 （1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char 型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。 (2 ) 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。 (3) 程序所能达到的功能：本程序可供任何人使用，主要功能1.浏览各单位及简介； 2.查看所有游览路线； 3.选择出发点和目的地求出最佳路径； 4.查看某一单位信息。 （4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。 a.首先看到的是校园导航系统的菜单： b．查看浏览路线等待输入起始景点： C．选择出发点与目的地等待输入起始景点与目的地编号： d．参看景点信息等待输入景点编号： 二、概要设计 本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。 数据结构-校园导航系统 简介:本系统采用C语言编写,运行环境为Dev-C++; 容以电子科技大学南校区为例; 主要功能有:1.查询景点信息;2.查询两景点间最短距离;3.查询两景点间所有路线;4.查询西电校园地图;5.修改景点和路径信息. 注意事项:在进行修改景点和路径信息操作前,请在可执行文件目录下用记事本创建”superUser.CODE”文件来存放用户名与密码(中间以空格隔开),否则无法进入. 源代码: #include char particular1[1000]; char particular2[1000]; char particular3[1000]; //景点详情 }VertexType; typedef struct { VertexType vex[20]; //最多存放20个景点信息ArcCell arcs[20][20]; //两个景点间的距离 int vexnum,arcnum; }MGraph; MGraph G; char nameofschool[100]; //学校名称 int NUM=9; int P[20][20]; int p[20]; int visited[20]; int a=0; long int D[20]; int x[20]={0}; //函数声明 void CreateUDN(int v,int a); void narrate(); void ShortestPath(int num); void output(int sight1,int sight2); char Menu(); void search(); char SearchMenu(); void HaMiTonian(int); void Searchpath1(MGraph g); void disppath(MGraph g,int i,int j); void path(MGraph g,int i,int j,int k); void NextValue(int); void display(); int Addnewsight(int n); int Deletesight(int n); void Changesight(); char Changemenu(); char Sightmenu(); int Maintain(void); int VerificatianIdentity(void); void map(); 数据结构课程设计报告模板 课程设计说明书 课程名称：数据结构 专业：班级： 姓名：学号： 指导教师：成绩： 完成日期：年月日 任务书 题目：黑白棋系统 设计内容及要求： 1.课程设计任务内容 通过玩家与电脑双方的交替下棋，在一个8行8列的方格中，进行棋子的相互交替翻转。反复循环下棋，最后让双方的棋子填满整个方格。再根据循环遍历方格程序，判断玩家与电脑双方的棋子数。进行大小判断，最红给出胜负的一方。并根据y/n选项，判断是否要进行下一局的游戏。 2.课程设计要求 实现黑白两色棋子的对峙 开发环境：vc++6.0 实现目标： （1）熟悉的运用c语言程序编写代码。 （2）能够理清整个程序的运行过程并绘画流程图 （3）了解如何定义局部变量和整体变量； （4）学会上机调试程序，发现问题，并解决 （5）学习使用C++程序来了解游戏原理。 （6）学习用文档书写程序说明 目录 1.引言 (1) 2.课题分析 (4) 3.具体设计过程 (5) 3.1设计思路 (5) 3.2程序设计流程图 (5) 3.3.函数实现说明 (10) 4.程序运行结果 (12) 5.软件使用说明 (16) 6.结论 (19) 参考文献 (20) 附录：源代码 (21) 1.引言 数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解的不同而有不同的表述方法： Sartaj Sahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型Abstract Data Type）的物理实现。” Lobert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。数据结构具体指同一类数据元素中，各元素之间的相互关系，包括三个组成成分，数据的逻辑结构，数据的存储结构和数据运算结构。 1.1. 重要意义 一般认为，一个数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。 在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。 选择了数据结构，算法也随之确定，是数据而不是算法是系统构造的关键因素。这种洞见导致了许多种软件设计方法和程序设计语言的出现，面向对象的程序设计语言就是其中之一。 1.2. 研究内容 课程设计报告 院、系： 专业：软件工程 班级： 课程设计科目数据结构 学生姓名： 指导教师： 完成时间： 校园导航系统设计报告 一、设计任务与目标 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 本系统是一个涉及吉林大学珠海学院相关景点和场所查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。 本系统为用户提供以下功能: (一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。 (二)、查询校园各个场所和景点信息; (三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学 校。 校园导航查询系统的开发方法总结如下： (1) 调查，了解学校各个场所与场所或者是各个景点与景点之间的信息， 路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设 计才能满足用户需求。 (2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统 结构和界面将实现的基本功能。 (3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。 (4) 调试，在设计完成后，调试系统运行的状况，修改完善系统,然后进行 测试。 二、方案设计与论证 校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的 边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。 搭建程序框架图，其图如下所示： 三、算法说明 （一）设计功能的实现 接下来根据以上搭建的程序框架完成各个模块的算法 1、首先是抽象数据类型的定义： 题号：第七题 题目：校园导航问题 1，需求分析： 设计你的学校的平面图，至少包括10个以上的景点（场所），每两个景点间可以有不同的路，且路长也可能不同，找出从任意景点到达另一景点的最佳路径（最短路径）。 要求： （1）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。 （2）为来访客人提供图中任意景点相关信息的查询。 （3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。 （4）修改景点信息。 实现提示： 一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。 选做内容： （1）提供图的编辑功能：增、删景点；增、删道路；修改已有信息等。 （2）校园导游图的仿真界面。 2，设计： 2.1 设计思想： <1>，数据结构设计： （1）图。采用邻接矩阵存储，其中图所用到的结构体为： typedef struct { SeqList vertices; //表示图中的顶点 int Edge[MaxVertices][MaxVertices]; //表示图中的边 int numOfEdge; //表示图中边的数目}AdjMGraph; （2）景点。用顺序表存储。所用到的结构体为： typedef struct { char name[20]; //顶点名称 int code; //顶点代号 char introduction[50]; //顶点信息简介 }DataType; （3）景点之间的连接描述，所用到的结构体为： typedef struct { int row; int col; int weight; }RowColWeight; 用图来存放所提供的所有景点，然后用线性表来存放每一个景点的信息，其中包括景点的名称，代号，信息简介，以及其它的一些信息。这样就将对景点的操作，变成对图中各顶点的操作。 <2>，算法设计： 关于本课题的算法，很大部分来源于这学期数据结构课程的学习，其中包括： 课程设计(论文)任务书 学院专业班 一、课程设计(论文)题目 二、课程设计(论文)工作自年月日起至年月日止。 三、课程设计(论文) 地点: 四、课程设计(论文)内容要求： 1．课程设计的目的 为了配合《数据结构》课程的教学，使学生能更深刻的领会《数据结构》课程的重要性，特开设此课程设计；编写一些在特定数据结构上的算法，通过上机调试，更好的掌握各种数据结构及其特点，培养学生综合运用所学理论知识解决复杂实际问题的实践能力、研究性学习能力和团队合作能力。 2．课程设计的任务及要求 1）基本要求 （1）课程设计前必须选定课程设计题目，并认真进行需求分析与系统设计； （2）上机调试之前要认真准备实验程序及调试时所需的测试数据； （3）独立思考，独立完成，严禁抄袭，调试过程要规范，认真记录调试结果； （4）上机结束后认真规范撰写课设报告，对设计进行总结和讨论。 2）课程设计论文编写要求 （1）要按照书稿的规格撰写打印课设论文 （2）论文包括任务书、目录、绪论、正文、总结、参考文献、附录等 （3）正文中要有问题描述、抽象数据类型的定义、数据的存储结构、设计的求解算法、算法的实现、调试分析与测试结果 （4）课设论文装订按学校的统一要求完成 3）课设考核 从以下几方面来考查： （1）考勤和态度； （2）任务的难易程度及设计思路； （3）动手调试能力； （4）论文撰写的水平、格式的规范性。 4）参考文献 [1] 严蔚敏, 吴伟民. 数据结构（C语言版）[M]. 北京：清华大学出版社, 2007年. [2] 严蔚敏, 吴伟民. 数据结构题集（C语言版）[M]. 北京：清华大学出版社, 2007年. [3] 谭浩强. C语言程序设计[M]. 北京：清华大学出版社，2006年. 5）课程设计进度安排 内容天数地点 构思及收集资料1图书馆 程序设计与调试3计算机房 撰写论文1图书馆 6）任务及具体要求 （此处填写任务书中自已所选题目的要求） 学生签名：亲笔签名 年月日 课程设计(论文)评审意见 （1）考勤和态度：优（）、良（）、中（）、一般（）、差（）（2）任务难易及设计思路：优（）、良（）、中（）、一般（）、差（）（3）动手调试能力评价：优（）、良（）、中（）、一般（）、差（）（4）论文撰写水平及规范性评价：优（）、良（）、中（）、一般（）、差（） 评阅人：职称：讲师 年月日 （一）课程设计要求 1.分组要求 每个人一个小组进行分组。 2.实训目的 （1）熟悉课程所学的内容，包括线性表、链表、串，栈，队列，树，图，查找和排序； （2）学生能够按照软件工程的规范要求，能够运用软件工程的基本概念、方法与过程来进行软件的设计与开发。 3.课程设计要求 （1）每组学生在以下项目中选择一项完成即可； （2）编写程序要严格按照程序编程规范进行代码编写; （2）必须按照个体软件的过程，真实地采集数据、填写相关的表格、编写有关的文档; （3）按照老师的要求，每个人必须独立完成; （4）按照实训的时间安排进行实训，实训结束后提交有关的表格与文档。（二）课程设计题目 1.线性表 （1）实验目的：利用顺序结构和链式结构实现线性表的基本运算。 （2）实验要求：对于顺序存储结构的线性表，验证其插入、删除操作；对以链式存储结构存储的线性表，验证其插入、删除、查找操作。 2.火车列车调度问题 （1）实验目的：利用顺序结构和链式结构实现栈和队列的基本运算 （2）实验要求：栈操作的验证火车调度；对于顺序队列、链队列的基本操作进行验证； 3.稀疏矩阵 （1）实验目的：利用三元组和十字链表实现稀疏矩阵的有关算法 （2）实验要求：以三元组作为存储结构实现稀疏矩阵的转置 4.二叉树 （1）实验目的：利用二叉链表实现二叉树的建立和遍历 （2）实验要求：以二叉链表作为存储结构建立二叉树；以二叉链表作为存储结构实现先序、中序和后序遍历二叉树 5.图的遍历和最短路径问题 （1）实验目的：在图的两种存储结构基础上实现图的遍历 （2）实验要求：采用连通无向图作为遍历对象对以邻接矩阵为存储结构的图实现深度优先搜索和广度搜索遍历；采用连通无向图作为遍历对象，建立邻接表时顶点对序号从大到小输入，对以邻接表为存储结构的图实现深度优先搜索和广度优先搜索遍历； 6.排序与查找 （1）实验目的：验证各排序与查找算法 （2）实验要求：编程实现排序与查找算法，包括直接插入排序、选择和起泡排序、折半查找 7.综合课程设计1 （1）实验目的：综合应用所学知识；培养系统设计的整体思想；提高编写程序、调试程序的能力；学习系统测试的方法；学习编写技术文档； （2）实验要求：约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列； 8.综合课程设计2 （1）实验目的:综合应用所学知识；培养系统设计的整体思想；提高编写程序、调试程序的能力；学习系统测试的方法；学习编写技术文档； （2）实验要求：设计一个校园导游程序，为来访的客人提供各种信息查询 *作者：座殿角* 作品编号48877446331144215458 创作日期：2020年12月20日 实用文库汇编之一、课程设计目的 本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。 设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。 通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 二、课程设计内容 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）主要的操作界面的显示以及无向网操作 void initgraph(graph *ga) 山东建筑大学 课程设计成果报告 题目： 1.数组实现两个矩阵的相乘运算 2.成绩分析问题 课程：数据结构A课程设计 院（部）：管理工程学院 专业：信息管理与信息系统 班级：信管*** 学生姓名：*** 学号：******** 指导教师：******* 完成日期：2016年12月29日 目录 目录 (2) 一、课程设计概述 (3) 二、课程设计题目一 (3) 用数组实现两个矩阵的相乘运算 (3) 2.1[问题描述] (3) 2.2[要求及提示]： (3) 2.3[详细设计] (4) 2.4[调试分析] (5) 2.5[运行结果及分析] (5) 三、课程设计题目二 (6) 成绩分析问题 (6) 3.1[问题描述] (6) 3.2[概要设计] (6) 3.3[存储结构] (7) 3.4[流程图] (7) 3.5[详细设计] (8) 3.6[调试分析] (8) 3.7[运行结果及分析] (22) 四、参考文献： (25) 一、课程设计概述 本次数据结构课程设计共完成两个题：用数组实现两个矩阵相乘运算、成绩分析问题。使用语言：C 编译环境：vc6.0 二、课程设计题目一 用数组实现两个矩阵的相乘运算 2.1[问题描述] #include “stdio.h” int r[6][6]; void mult(int a[6][6] , int b[6][6]){ } main(){ int i,j; int num1[6][6],num2[6][6]; printf(“请输入第一个矩阵的值:”,); for(i=1;i<=6;i++) for(j=1;j<=6;j++) scanf(“%d”,&num1[i][j]); printf(“请输入第二个矩阵的值:”,); for(i=1;i<=6;i++) for(j=1;j<=6;j++) scanf(“%d”,&num2[i][j]); mult(num1,num2); printf(“\n两个矩阵相乘后的结果为：”); for(i=1;i<=6;i++) {for(j=1;j<=6;j++) printf(“%4d”,r[i][j]); printf(“\n”); } } 2.2[要求及提示]： 1、要求完善函数mult( ), 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 分类号编号 华北***大学 North China Institute of Water Conservancy and Hydroelectric Power 课程设计 题目校园导航 院系信息工程学院 专业计算机科学与技术 姓名****** 学号201117000 指导教师***** 2012年7月6 日 目录 1.需求分析 (1) 1.1问题描述 (1) 1.2课程设计目的 (1) 1.3设计要求 (1) 2.概要设计 (2) 2.1任务定义 (2) 2.2数据结构 (2) 2.3 校园平面图展示 (2) 2.4系统功能图 (4) 3.详细设计 (4) 3.1各个模块名称和功能 (4) 3.2具体函数模块详解 (5) 3.2.1校园平面图展示 (5) 3.2.2任意两点的所有路径 (5) 3.2.3校园基础设施介绍 (6) 3.2.4指定两点间最短路径 (6) 3.2.5单点到其他左右顶点间最短路径 (6) 3.2.6华北水利水电学院简介 (7) 3.2.7访客留言 (7) 3.2.8浏览访客留言 (7) 3.3 主要算法思想描述 (7) 3.4各函数之间的调用关系示意图 (7) 4.测试与分析 (8) 4.1测试显示 (8) 4.2调试分析 (12) 4.2．1调试过程中遇到的问题与解决方案 (12) 4.2.2算法的时空复杂度分析 (12) 5.用户使用说明 (12) 6.实验总结 (14) 7.参考文献 (14) 8.附件 (15) 校园导航系统 1.需求分析 1.1问题描述 我们熟悉一个地方的地形情况通常是借助于一张地图，通常的地图包含的信息十分的有限，而且具体到某一个建筑物，你不能了解到它的进一步的详细的情况。因此，导航系统就应运而生了。 具体到本系统，作为用户浏览校园时，只拿着学校的地图是能够游遍全校，但是各建筑内部的情况就必须实地考察才能了解，既费时又费力。有了我们的校园的导航系统，用户可以根据自己的需要，迅速找到所关心的地点，并且可以看到它的详细的信息。 1.2课程设计目的 本课程设计的目的就是要达到理论与实际应用相结合，使我们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，培养程序设计技能如下： (1)了解并掌握数据结构算法的设计方法，具备初步的独立分析和设计能力； (2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； (3) 独立完成，提高运用所学的理论知识和方法独立分析和解决问题的能力； 1.3设计要求 设计一个校园导航系统，为来访的客人提供导航服务，具体要求： (1) 设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。 （2）以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息 (3) 为来访客人提供图中任意景点相关信息的查询。 (4) 提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径以及任意景点到其他所有景点的最短路径查询。 (5) 列出所有校内无重复排列的景点，将所有景点的距离以邻接矩阵的方式呈现给使用者，提供使用者选择功能界面，按照提示进行操作。校园导航系统---算法与分析课程设计
数据结构课程设计报告模板
数据结构课程设计
数据结构课程设计-校园导航
数据结构课程设计报告模板
数据结构课程设计
数据结构课程设计-校园导航
校园导航系统源代码
数据结构课程设计报告模板
数据结构课程设计—校园导航报告
校园导航系统
数据结构课程设计报告模板2013
数据结构课程设计内容
实用文库汇编之数据结构课程设计校园导航
数据结构课程设计报告
数据结构课程设计题目及要求
校园导航系统 数据结构课程设计 C++开发
相关主题
文本预览