《数据结构》课程设计指导书

《数据结构》

课程设计指导书。

天津职业技术师范大学信息技术工程学院。

数据结构》课程组。

数据结构》课程设计指导书。

一、指导思想。

以cdio理念为理论指导，以技能训练为教学手段，以项目驱动为训练模式，以知识结构为评价标准，以小组协作为组织形式，以培养学生的工程意识和实际操作能力为宗旨目标。二、项目分类1.入门级项目。

知识结构：线性结构；成绩等级：0--80；小组人数：2人2.提高级项目。

知识结构：图、树之一；成绩等级：0--90；小组人数：2-3人3.专业级项目。

知识结构：两种结构以上；成绩等级：0--100；小组人数：3-4人。

三、具体步骤。

1.构思：确定项目名称，撰写项目建议书。

全班学生根据自身专长和兴趣爱好，分成若干小组，每组选出一个小组长，在小组长的带领下小组成员观察生活，结合自己掌握的知识结构，构思任务要求，确定项目名称（难度、工作量需要通过指导教师审核）。

项目建议书一般应按照以下提纲编写：1)项目的选题意义；2)项目的主要内容和目标；

3)项目的技术基础、特点及实施的条件；

4)完**员分工（按照功能模块分工）。2.设计：撰写设计方案。

从问题的需求入手，设计合理的数据结构，明确输入和输出信息，并进行功能设计（模块层次图）、界面设计、程序流程图、算法设计等。

要求每个学生在查阅相关文献的基础上，提出自己的设计方案，并介绍为什么要采用此方案，由小组长组织小组讨论，取本小组每一个成员方案的长处，避其短处，形成本小组的最佳方案。3.实践：

程序实现。

编写**并上机调试。4.验收：对程序进行测试。

指导教师对程序进行测试，主要考查：数据结构设计、功能设计、系统结构设计及界面设计是否合理；可读性、健壮性、任意性是否良好；是否具有创新性（如能从文件读输入数据或向文件写输出数据则酌情加分）；进行小组答辩（对每名小组成员进行提问并给出评价和相应成绩）。5.

总结：提交设计报告。

第一部分：项目建议书；第二部分：设计方案；第三部分：

源程序（刻录成光盘，不需抄写）；第四部分：参考文献；第五部分：课程设计体会（工作过程、思路、难点及解决办法、收获、亮点、不足等）

注意：手写，不许打印。每人一份，重点写自己所做工作。四、评分标准。

自评（小组组长给成员打分，占10%）、考勤（10%）、答辩成绩（40%）、报告成绩（40%）。

附课程设计报告范例：天津城市轨道交通咨询模拟系统。

天津城市轨道交通咨询模拟系统。

一、项目建议书。

1.项目的选题意义。

随着社会的发展，城市轨道交通成为社会离不开的重要交通方式，有利于缓解城市的交通堵塞和节能减排。为了方便大家了解天津城市轨道交通、查询最优换乘方案，特参照天津地铁运营线路图（图1），实现天津城市轨道交通的模拟咨询。

图1 天津地铁运营线路图。

2.项目的主要内容和目标。

天津城市轨道交通咨询模拟系统主要实现三种换乘方案的咨询：一是以途经的站数作为计算依据，查询从甲地到乙地的最短路径；

二是以换乘次数作为计算依据，查询从甲地到乙地的最少换乘次数；三是以邻接站点之间的运行时间作为计算依据，查询从甲地到乙地的最短时间。

3.项目的技术基础、特点及实施的条件。

该项目可用c++语言实现，适于在单机环境下运行，提供vc++可视化界面。小组成员均已学习过高级语言程序设计、visual c++基础程序应用开发，数据结构和算法等课程，具有一定的开发能力。

4.项目人员分工。

所有人都参与了项目的选题、设计、实现及测试工作，项目负责人归纳并整理小组成员在各个阶段的讨论成果，并确定最终方案。在实践阶段，按照功能模块具体分工如下：

项目负责人：张三，构建模型、设计数据结构、实现第一种方案项目组成员：李四，初始化数据、实现第二种方案项目组成员：王五，设计界面、实现第三种方案。

二、设计方案。

1.数据结构的选择与设计。

此项目**于实际问题。天津地铁是双向运行的，可以根据站点信息和连接情况将天津地铁线路抽象成一个无向网；由于地铁站点相对较少，而每个站点都需要存储包括“站点名称”、“属于几号线”、“是否是起点/终点站”、“是否是换乘站点”、“邻接站点的运行时间”等较多的信息，如果采用邻接矩阵的数据结构和回溯法，则效率较低，所以选择邻接表用于存储图形信息）。

而在功能实现过程中，天津城市轨道交通咨询模拟系统实现的三种咨询功能都与图的遍历有关，所以在遍历时会用到栈或队列的数据结构，以便于算法的设计与实现。具体数据结构设计详见头文件其中站点类设计如下所示。

class node;

2.总体设计方案。

首先构建模型，初始化数据；其次，为三种需求设计算法并实现；最后，设计界面，完善系统的人机交互功能。

3.详细设计方案。

1)算法设计及流程图第一种咨询功能是以途经的站数作为计算依据，计算最短路径。在实现上，可以通过深度优先搜索遍历图查找从甲地到乙地的所有路径，通过计算途经站点总数，得到最短路径。

第二种咨询功能是以换乘次数作为计算依据，计算最少换乘次数。在实现上，可以通过深度优先搜索遍历图查找从甲地到乙地的所有路径，通过计算换乘站点的总数，得到最少换乘次数。图的深度优先搜索遍历算法的流程图如图2和图3

所示。开始。

标志数组初始化。

v=0v访问过？ny

dfs递归算法。

v=v+1v《顶点个数？

y结束。图2图的深度优先遍历算法流程图。

开始。访问v，置标志。

求v邻接点。

有邻接点w？y返回。

w访问过？nw→v求下一邻接点。

图3dfs递归算法流程图。

第三种咨询功能是以邻接站点之间的运行时间作为计算依据，计算最短时间。在实现上，可以通过迪杰斯特拉算法计算从甲地到乙地需要的最短时间。迪杰斯特拉算法流程图如图4所示。

开始。d[s]=0d[v]=集合s=i=0

集合s中包含顶点集v中除顶点s外所有顶点且v=t?

f从v-s中取一个顶点u使d[u]的值最小。

t结束。d[u]为从s到t的最短路径集合。s为从s到t的最短路径的结点集。

用d[u]和d[u]+w(u,v)中较小的替换原来的d[v]的值。

调整d[v]中各点的值i=i+1

图4迪杰斯特拉算法算法流程图。

2)界面的设计。

vc++可视化界面，具体如图5所示。

图5 天津城市轨道交通咨询模拟系统界面。

4.项目测试方案。

项目负责人张三：单元测试、集成测试项目组成员李四：单元测试、系统重构项目组成员王五：单元测试、黑盒测试。

三、参考文献。

1]严蔚敏，吴伟民。《数据结构（c语言版）》.清华大学出版社，2007[2]许秀林，董杨琴。《程序设计基础教程（c语言与数据结构）（第二版）》.中国电力出版社，2009

3]李建学，李光元，吴春芳。《数据结构课程设计案例精编（用c/c++描述）》.清华大学出版社，2007

4]王育坚。《visual c++面向对象编程教程（第2版）》.清华大学出版社，2007

5]孙鑫，余安萍。《vc++深入详解》. 电子工业出版社，2006[6]张海藩。《软件工程导论（第5版）》.清华大学出版社，2008四、课程设计体会。

本次课程设计题目是“天津城市轨道交通咨询模拟系统”，是由我们这个小组的几名同学通过结合生活实际共同选定的。刚开始做这个系统的时候，感到完全无从下手，甚至让我觉得这次课程设计根本无法完成。，于是我们决定按照传统的软件工程方法即结构化技术来完成该系统的开发。

通过对实际问题的思考和分析，将天津地铁线路抽象成数学模型，并选择了线性结构和图结构这两种数据结构来完成对计算机模型的构建，最后通过算法实现了三种咨询需求。

在该系统的开发过程中，我们遇到了一些困难，如：无法将初始数据存入ini配置文件中，无法正确显示地铁站点等。后来经过查阅资料及同学讨论，找到了相应的解决办法。

在测试时又发现了很多问题，主要原因是编写**时考虑不周，经常运行一些语法错误，但通过同学间的帮助最终都解决了问题。

在本次课程设计中，我明白了理论与实践相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技。

能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对vc有了更深入的了解。

《数据结构》是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个环节。因此，在《数据结构》的学习过程中，必须严格按照实验大纲的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。同时，在学习《数据结构》之前，必须要复习c/c++语言，要对指针和结构体的相关知识进行深入学习并上机实践以提高编程能力。

本系统的创新之处是：初始数据存储在ini配置文件中，三种咨询方法从不同角度进行查询，vc++可视化界面等。但是也存在不足，如：

没有实现在界面上显示各个节点及节点间运行时间等相关信息等。

总的来说，这次课程设计让我获益匪浅，在项目实施过程中，提高了分析问题和解决问题的能力，更加强了实践操作能力。对《数据结构》也有了进一步的理解和认识。在课程设计的一周里，我与团队其他成员积极协作，有效沟通，圆满地设计并实现了天津城市轨道交通咨询模拟系统。

课程设计让我对团队精神的重要性有了深刻认识，在工作生活当中，个人力量往往显得有限，只有加强合作才能顺利完成任务。

《数据结构》课程设计指导书

数据结构课程设计指导书

数据结构课程设计指导书

数据结构课程设计指导书

其他用户还读了