电气与信息工程学院
实 践 管 理 手 册
课 程 名 称： 《数据结构课程设计》
专 业： 数据科学与大数据技术
电气与信息工程学院实践项目训练记录 第（ 1 ）阶段
|
训练任务
|
问题分析和任务定义
|
训练时间
|
11.30-12.1
|
|
训练地点
|
数据基础实验室一
|
指导教师
|
赵晓敏
|
|
目 的
|
掌握实际问题分析能力；
理解任务划分和内部关系的设计方法；
|
|
环 境
|
Windows7及以上、
VC6.0
|
|
方法描述
|
通过对....进行需求分析,构建了....项目，包含....功能。对设计的内容做简要介绍
|
|
训练过程
|
对问题进行细致分析；设计项目的整体框架结构；
|
|
训练结果
|
确定题目及设计要完成的主要功能
|
|
总 结
|
|
|
成 绩
|
|
附 件：
训练任务：问题分析及任务定义
对于一个通讯录来说，要管理联系人的信息，包括编号姓名，性别，电话。开发其系统主要是为了帮助用户提高通讯录的管理效率，节约资源，提高信息的精确度。
本课题为构建通讯录管理系统，主要设计功能包括：
（1）打开文件读取通讯录信息
（2）通过链式存储接受文件储存信息
（3）对文件信息进行修改
（4）保存修改并将信息写回文件
二、问题分析过程
“飞行”校园导航仪系统是我为了满足现代人们在我们学校里迷路而设计出来的程序。
l菜单模块是为了让人们能够认识到此功能的界面以及多元化，在这里，主要是把该程序的功能方面一一列举出来，使用switch循环（进行查询时的循环显示）和printf设置菜单的输出样式。
l校园地图设计，在这个模块中，主要是数据结构中图的邻接矩阵的运用,对于邻接矩阵的构建和输出，以及地图的显示（printf）。
l景点详述模块，依然是switch循环和break语句的联合使用，此外，需多写对应函数（景点）的信息。
l最短路径显示（INF为路径长度），在这里，使用了弗洛伊德算法计算最短路径，需使用for循环以及二维数组进行构造顶点及弧。
主函数的使用：在主函数中，调用以上的函数，然后输出各景点之间的路径长度。
电气与信息工程学院实践项目训练记录 第（ 2 ）阶段
|
训练任务
|
数据类型和系统设计
|
训练时间
|
12.2-12.5
|
|
训练地点
|
数据基础实验室一
|
指导教师
|
赵晓敏
|
|
目 的
|
掌握分析问题及抽象数据类型定义的方法；
理解项目设计整体流程；
|
|
环 境
|
Windows7及以上、
VC6.0
|
|
方法描述
|
针对自己的问题描述中涉及的相应的数据类型进行介绍，并按照以数据结构为中心的原则划分模块，定义主程序模块及其他模块之间的关系和流程。
|
|
训练过程
|
根据相应的数据存储结构的类型定义，按照算法书写规范用类C语言写出各过程和函数的伪码算法框架。
|
|
训练结果
|
项目的整体流程及主要包含的模块
|
|
总 结
|
本部分的总结体会
|
|
成 绩
|
|
训练任务：数据类型和系统设计【案例参照】
在本项目中，采用了数据结构类型中的最短路径类型，本项目是飞行校园导航系统，在人们行走过程中，需要计算出最短的距离，所以使用最短路径的模型是恰到好处，而相比栈以及队列来说，相对复杂，且并没有这个好处和功能，链式结构在查找过程中，过于复杂，自然也不适用于此，而最短路径是用于计算一个节点到其他所有节点的最短路径，使用邻接矩阵来储存学校景点，而使用线性表的思想来存储景点中的信息。
在这里，最短路径的主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，也最适合于确定起点终点的最短路径问题，即已知起点和终点，求两结点之间的最短路径 （与本项目的操作非常符合），在设计地图时，我们需要画出一张图，即边或弧以及点，而这样的结构恰恰还需要邻接矩阵的功能，导航过程中，需要使用带有权值的图形结构（网状），此外，在使用栈的结构时，不能同时出或入，即使用最短路径以及邻接矩阵，
通过最短路径的迪杰特斯拉算法和弗洛伊德算法，在带权图的中单个起点到所有顶点的最短路径问题使用迪杰特斯拉算法，但是求每一个（所有）顶点与其他顶点之间的最短路径，由于如果使用迪杰斯特拉算法过于复杂，所以在本项目中使用了弗洛伊德算法来计算最短路径，所以不能够拘泥于一种算法计算最短路径，要找到最优的算法，他的状态转移方程如下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，如果这条路通达失败，还必须特殊处理，比如没有map[i,k]这条路，即使用它来计算最短路径。
在本项目中，使用了最短路径的数据结构类型，其程序流程图如下：
主要函数如下：
建立地图函数：
void ecjtumap（）
用于建立本项目（黑龙江工业学院）的地图梗概
如：printf("\t| ---------- |\n");
printf("\t| ==============================| 学生宿舍 |\n");
printf("\t| 。 ---------- |\n")
地图各景点距离函数：
void Dispmat（MGraph g）
在这个函数中，使用了邻接矩阵的方法，输出各地点的距离，printf("%3s","∞T"); 这里分别用%3s和%3d控制输出字符∞或数字宽度为3个字符，即邻接矩阵中的权值。
求取景点函数：
void ppath(int path[][MAXV],int i,int j)
i表示起点，j表示终点，k为中间经过的景点，ppath(path,i,k);是指期间景点。
最短距离求取函数：
void put_shortdistance(int x,int y,int A[][MAXV],int path[][MAXV],int n)，if分支结构确定了求取最短距离，当起终点之间无路径时，则输出无路径，若存在，则计算出其路径的形式如" -- 到--"的形式。
以下是弗洛伊德算法的算法设计图：
求取最短路径函数：
void shortdistance(MGraph g,int x,int y)
该模块使用的是弗洛伊德算法，三个for循环，将每一个起点到终点的路径长度都计算出来。
导航菜单函数声明
void menu() 输出各个节点的编号，放便导航。
主函数：为了调用各个函数且输出各个景点的距离，并更改字体输出颜色，做最后的显示工作等等。
电气与信息工程学院实践项目训练记录 第（ 3 ）阶段
|
训练任务
|
编码实现和静态检查
|
训练时间
|
12.6-12.7
|
|
训练地点
|
数据基础实验室一
|
指导教师
|
赵晓敏
|
|
目 的
|
掌握综合编程思维及设计能力；
掌握项目整体测试和维护能力。
|
|
环 境
|
Windows7及以上、
VC6.0
|
|
方法描述
|
根据项目的整体流程及各模块的相互关系，细化设计过程，完成项目整体实施及检验。
|
|
训练过程
|
实现各模块的细节，完成项目整体设计
|
|
训练结果
|
项目的运行及检测
|
|
总 结
|
本部分内容的总结体会
|
|
成 绩
|
|
训练任务：编码实现及检测【案例参照】
下面项目的运行界面
（1）进行调试到菜单界面：
在此界面中，仅能输入1~5的数字。
（2）然后输入数字1，即可进行查看本项目的地图梗概（黑龙江工业学院）
在此界面中，无需输入值的范围需略读一遍地图大概即可。
（3）输入数字2进行到地图详解模块：
在此界面中，输入（1）步讲述之后，可以输入1~10的数字，进行各个景点的详解，以便大家了解。
（4）然后输入数字3进行进店一览表模块：
在此界面中，输入（1）步讲述之后，可以看到第（2）步的概览，以便大家可以自行选择。
（5）点击数字4问路查询：
此模块中，输入（1）步讲述之后，输入起点与终点的所对应的各个数字（1~10），即可找出他们的最短路径，以便节约时间。
（6）最后输入数字5，即可退出整个程序：
退出即可！！！
电气与信息工程学院实践项目训练记录 第（ 4 ）阶段
|
训练任务
|
经验及总结
|
训练时间
|
12.8-12.9
|
|
训练地点
|
数据基础实验室一
|
指导教师
|
赵晓敏
|
|
目 的
|
深入理解整体设计流程、及时总结发现问题；为后期课程设计及实训提供借鉴；
|
|
环 境
|
Windows7及以上、
VC6.0
|
|
方法描述
|
针对自己项目中的问题，对设计的项目进行总结，对于待完善的功能可以进行拓展规划，好的经验可以总结。
|
|
训练过程
|
总结经验，为今后的设计做好基础和铺垫。
|
|
训练结果
|
课程设计的作品及课程报告
|
|
总 结
|
本部分内容的总结体会
|
|
成 绩
|
|
训练任务：经验与体会【案例参照】
(1) 改进设想；
我个人认为这个程序还有修改之处，可以分为以下几点：
Ø 在输入数字的时候，应该设计一下当输错数字或者输入其他时（字母等），该程序会出现死循环的情况，所以我们应该友好的提出操作者的失误，我们可以使用if分支结构来完成此模块。
Ø 紧接着，我们可以提供给旅游者（不熟悉校园的人）一些交通工具所在的地方，以防迷路，可以使用if与for来完成此模块。
Ø 除此之外：我们还可以设计使用百度地址的方式来对我们的这个学校的景点做更全面的介绍，而该程序的介绍仅仅是粗略的用代码形式写出的，比较笼统，而我们如果使用引用文件或网址的形式，则可以让参观者更加印象深刻，也更加了解我们学校。
Ø 然后，我们还可以将每个最短路径的平均最短时间求解出来，以便参观者充分利用时间，可以引用求时间的函数来完成该模块。
以上就是我的改进思想，如果有不同看法，欢迎修改！！！
(2)实验体会:
通过了一周的实训课，我学到了许多有用的东西，在这个项目中，首先，也通过数据结构的书本知识，我知道了构造邻接矩阵的方法，ypedef struct
{ int no; InfoType info; } VertexType; typedef struct { int edges[MAXV][MAXV]; int vexnum,arcnum; VertexType vexs[MAXV]; } MGraph;
通过网络和书本上的知识，成功理解了相应概念，也发现了自己的一些错误，也知道了很多手段和方法来解决一些问题，比如：网络上的天天云搜、百度文库等等，其次，我也知道了求解最短路径的不同方法，如：Dijkstra算法（迪杰斯特拉），还有弗洛伊德算法等等，在这里，我也知道了解决一件事要变通，不可以拘泥于一种方式，而且也要多看书籍或多搜网站上的资料以丰富自己，体验了一下设计提高提高能力，也可以理解为一次实践与理论的很好的连接。特别是本次所做的题目都是课堂上所讲的例子，在实行的过程中却并不是那么容易，一开始让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅，绝知此事要躬行。
设计过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，也形成了一定的个人做事风格。 通过这次课程设计，也让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等类型，有时用二维数组等，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，提高了程序的运行效率，而不是拘泥于迪杰特斯拉算法来进行最短路径的求解，在编写这个程序的过程中，我复习了之前学的基本语法，自学了最短路径的求取方法（弗洛伊德算法），又预习了学校所讲的Dijkstra算法，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己综合运用知识的能力，体会了学以致用、突出自己的喜悦心情，也从中发现自己平时学习的不足和薄弱之处，从而加以弥补，取其精华，弃其糟粕，除此之外，我还知道了改变程序运行时颜色的方法，即：system("color 0a");其中，0a为绿色，（其余颜色代码参照网络）。
在这过程里，收获还是不少，虽然说以前不是特别理解这门课程，且在它上面花费了好多心血，觉得它很难，是需花费大量的时间理解出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。
以上便是我对数据结构这门课的学习总结，我会抓紧时间将没有吃透的知识点补齐,克服学习中遇到的困难，在打牢基础的前提下向更深入的层面迈进！希望自己以后可以再接再厉！！！
