2010级软件专业数据结构课程设计计划

信息工程学院1010级软件工程专业

数据结构课程设计计划

设计名称 《数据结构》课程设计 专业、班级 软件10级1班 课程性质 必修 设计周数 2周 课程学期学时数 68学时 学期学分 4分 指导教师签字 系主任审核签字 一．课程设计的目的

通过课程设计的综合训练，旨在帮助学生进一步系统的掌握数据结构这门课的主要内容，并进一步培养学生分析问题和解决问题的能力，主要体现在能够让学生针对实际问题有效地组织数据，选择合适的数据结构，并进行正确和高效的算法设计，并用程序实现算法。该课的课程设计是一个良好的程序设计技能训练的过程使学生能够：

1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工程专业学生所应具备的科学的工作方法和作风。 二．实习内容及安排 时间 第1天 第2天 第3天 第4天 第5天 第6天 第7天 第8天 第9天 地点 校内 校内 校内 校内 校内 校内 校内 校内 校内 内容 课程设计内容宣讲和选题 问题分析和任务定义 概要设计 详细设计 程序编码 程序调试与测试 程序调试与测试 程序调试与测试 程序调试与测试 负责人 黄橡丽 黄橡丽 黄橡丽 黄橡丽 黄橡丽 黄橡丽 黄橡丽 黄橡丽 黄橡丽 1

第10天 第11天 校内 校内 编写课程设计报告 课程设计内容总体展示与成绩评定 黄橡丽 黄橡丽 三．课程设计主要内容 1．设计题目

题目1：运动会分数统计 【问题描述】

参加运动会有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) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前

三或前五名的学校；

(5) 学生自己根据系统功能要求自己设计存储结构，但是要求运动会的相关数据要存储在数据文件中并能随时查询；

(6) 输入数据形式和范围：可以输入学校的名称，运动项目的名称； (7) 使用汉字显示。

题目2：飞机订票系统 【问题描述】

编写一个飞机订票系统，完成如下功能：

（1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）；

（2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；

（3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；

（4）退票： 可退票，退票后修改相关数据文件；

（5）修改航班信息：当航班信息改变可以修改航班数据文件。 【设计要求】

（1）客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 （2）根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。

（3）使用汉字显示。

题目3：通讯录的制作 【问题描述】

用《数据结构》中的链表作数据结构，结合C语言基本知识。编写一个通讯

2

录管理系统，完成如下功能：

(1) 输入信息； (2) 显示信息；

(3) 查找以姓名作为关键字； (4) 删除信息； (5) 存盘； (6) 装入。 【设计要求】

(1) 每条信息至少包含 ：姓名（NAME ）、街道（STREET）、城市（CITY）邮编（EIP）、国家（STATE）几项；

(2) 作为一个完整的系统，应具有友好的界面和较强的容错能力； (3) 使用汉字显示。

题目4：学生成绩管理系统 【问题描述】

现有学生成绩信息文件1（1.txt）和文件2（2.txt），试编写一管理系统，完成如下功能：

(1) 实现对两个文件数据进行合并,生成新文件3.txt；

(2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt； (3) 合并后的文件3.txt中的数据按总分降序排序；

(4) 输入一个学生姓名后，能查找到此学生的信息并输出结果； (5) 要求使用结构体，链或数组等实现上述要求。 【设计要求】

(1) 每条信息至少包含 ：姓名、学号、语文、数学、英语；

(2) 作为一个完整的系统，应具有友好的界面和较强的容错能力； (3) 使用汉字显示。

题目5：活期储蓄帐目管理 【问题描述】

活期储蓄处理中，储户开户、销户、存入、支出活动频繁。试编写一个活期储蓄帐目管理系统对其进行管理。 【基本要求】

(1) 能比较迅速地找到储户的帐户，以实现存款、取款记账；

(2) 能比较简单，迅速地实现插入和删除，以实现开户和销户的需要； (3) 使用汉字显示。

题目6：客户消费积分管理系统 【问题描述】

针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。 【基本要求】

(1) 采用一定的存储结构进行客户信息的存储； (2) 对客户的信息可以进行修改、删除、添加； (3) 能够根据消费情况进行客户积分的计算； (4) 根据积分情况实行不同程度的打折优惠；

3

(5) 使用汉字显示。

题目7：产品进销存管理系统 【问题描述】

针对某一种行业的库房的产品进销存情况进行管理。 【基本要求】

(1) 采用一定的存储结构对库房的货品及其数量进行分类管理； (2) 可以进行产品类的添加、产品的添加、产品数量的添加；

(3) 能够查询库房每种产品的总量、进货日期、销出数量、销售时间等； (5) 使用汉字显示。

题目8：一元稀疏多项式计算器 【问题描述】

设计一个一元稀疏多项式简单计算器，可以计算任意两个一元多项式的加法、减法以及乘法。 【基本要求】

(1) 输入并建立多项式； (2) 输出多项式；

(3) 多项式A和B相加，建立多项式A+B； (4) 多项式A和B相减，建立多项式A-B； (5) 使用汉字显示。

题目9：算术表达式的求解 【问题描述】

给定一个算术表达式，通过程序求出最后的结果。 【基本要求】

(1) 从键盘输入要求解的算术表达式；

(2) 采用栈结构进行算术表达式的求解过程； (3) 能够判断算术表达式正确与否； (4) 对于错误表达式给出提示；

(5) 对于正确的表达式给出最后的结果； (6) 使用汉字显示。

题目10：车厢调度 【问题描述】

假设停在铁路调度站入口处的车厢序列的编号依次为1，2，3……N。设计一个程序，求出所有由此输出的长度为N的车厢序列。 【基本要求】

(1) 采用栈数据结构实现上述求解； (2) 使用汉字显示。

题目11：数制转换问题 【问题描述】

任意给定一个M进制的数x，实现将其转换成任意的一个非M进制的数。 【基本要求】

4

(1) 求出此数x的10进制值（用MD表示）；

(2) 实现对x向任意的一个非M进制的数的转换；

(3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）；

(4) 使用汉字显示。

题目12：任意长的整数加法 【问题描述】

设计一个程序实现两个任意长的整数的求和运算。 【基本要求】

(1) 利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。

(2) 使用汉字显示。

题目13：学生搭配问题 【问题描述】

一班有m个女生,有n个男生(m不等于n)，现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。请设计一系统模拟动态地显示出上述过程。 【基本要求】

(1)输出每曲配对情况；

(2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值；

(3) 使用汉字显示。

提示：用队列来解决比较方便。

题目14：猴子吃桃子问题 【问题描述】

有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。

【基本要求】

(1) 采用数组数据结构实现上述求解； (2) 采用链数据结构实现上述求解； (3) 采用递归实现上述求解； (4) 使用汉字显示。

题目15：二叉树的遍历 【问题描述】

二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现。 【基本要求】

(1) 作为一个完整的系统，应具有友好的界面和较强的容错能力；

5

(2) 使用汉字显示。

题目16：构造可以使n个城市连接的最小生成树 【问题描述】

给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 【基本要求】

(1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价；

(2) 表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）；

(3) 最小生成树中包括的边及其权值，并显示得到的最小生成树的代价； (4) 使用汉字显示。

题目17：图的遍历的实现 【问题描述】

图的DFS,BFS的递归和非递归算法的实现。 【基本要求】

(1) 先任意创建一个图；

(2) 图的DFS,BFS的递归和非递归算法的实现； (3) 要求用有向图和无向图分别实现；

(4) 要求用邻接矩阵、邻接表多种结构存储实现。

题目18：教学计划编制问题 【问题描述】

大学的每个装业都要制定教学计划，假设任何专业都有固定的学习年限，每学年含两学期，每学期的实际长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设实际的安排必须满足先修关系，每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有，每门课恰好占一个学期，试在这样的前提下设计一个教学计划编制程序。 【基本要求】

(1) 属于参数包括学期总数，一学期的学分上限，每门课的课程号（固定占三位的字母数字串），学分和直接先修课的课程号；

(2) 允许用户指定下列两种编排策略之一，一是使学生在各学期中的学习负担尽量均匀，二是使课程尽可能的集中在前几个学期中；

(3) 若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中，计划的表格格式自行设计；

(4) 使用汉字显示。

题目19：关键路径问题 【问题描述】

设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。

【基本要求】

6

（1）对一个描述工程的AOE网，应判断其是否能够顺利进行；

（2）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间；

（3）使用汉字显示。

题目20：二叉排序树的实现 【问题描述】

实现二叉排序树的操作算法，包括建立、插入、删除、查找以及中序遍历。 【基本要求】

（1）作为一个完整的系统，应具有友好的界面和较强的容错能力； （2）使用汉字显示。

题目21：散列法的实验研究 【问题描述】

散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观察，不同的解决冲突方法对查询性能的影响。 【基本要求】

（1） 设计不同的散列函数，比较冲突率；

（2） 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察

平均查找长度的变化； （3） 使用汉字显示。

题目22：排序综合 【问题描述】

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法排序。

【基本要求】

(1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中；

(2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法；

(3) 使用汉字显示。 学生应在教师的指导下，根据自己的实际情况，选择设计题目（以小组为单位实现）。一组一题。如需自行申请选题，需经指导教师批准。 2．设计步骤

(1) 问题分析和任务定义

根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ (2) 概要设计

7

对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。概要设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。 (3) 详细设计

定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；界面要求有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求；有些数据要存储在数据文件中（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）。 (4) 程序编码

把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚。 (5) 程序调试与测试

采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。测试数据要求使用合法数据和非法数据进行程序测试，以保证程序的稳定；调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 (6) 结果分析

程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。

(7) 编写课程设计报告 3．课程设计的基本要求

（1）严格遵守软件系统开发步骤，适当应用理论知识，充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。

（2）严格考勤，独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，如报告内容雷同，成绩以不及格计。

（3）每组实现的结果必须进行检查和演示。课程设计结束后，应提交以下文档： 1）纸质文档：课程设计报告，格式请参考课程设计报告模版。

2）电子文档：放在一个以题目命名的文件夹中，包括课程设计报告电子版和系统源程序。

四．课程设计说明书（报告）的撰写规范

学生按要求完成课程设计报告的写作，具体格式请参考课程设计报告模版。课程设计报告应按照规定的格式撰写，其中总结部分可以包括：课程设计过程中遇到的困难及其采用的解决办法；进行了哪些功能扩展，特别是重点说明独创或

8

创新的部分；在课程设计过程中的收获、以及对《数据结构》课程的认识等内容。

各种设计文档用A4纸打印，报告中使用的图形或图表应使用适当工具绘制，清晰、准确。 五．课程设计的考核

采用出勤情况、完成的程序、课程设计报告相结合的形式，按优、良、中、及格、不及格五级记分制给出每位学生的成绩。

1、出勤情况（20%） 2、程序运行（30%） 3、课程设计报告（45%） 4、创新部分（5%-10%）

9

本文来源：https://www.bwwdw.com/article/xqe6.html