数据结构课程设计2013

1、数据结构课程设计题目（2013年）一、必做题1、图书管理系统（线性表）问题描述设计一个程序，记录并统计图书使用情况。基本要求（1）图书信息包括图书ID号，图书名，出版社名，出版年月，馆藏册数。（2）学生信息包括学号，姓名，班级，在借册数，已还册数，违约次数。（3）借阅信息包括图书ID号，图书名，学号，姓名，借阅日期，应还日期，归还日 期。（4）采用顺序存储线性表表示图书信息。采用链式存储线性表表示学生信息。采用双向循环链表表示借阅信息。其中一个双向循环链表表示在借的借阅信息，按照图书ID号非递减排序；另一个双向循环链表表示已还的借阅信息，按照图书ID号非递减排序。（5 ）图书信息，学生信息、借

2、阅信息采用文件方式输入。图书信息示例如下，每条信息一行：16000001数据结构 清华大学出版社 2012.10 30学生信息示例如下，每条信息一行：161340106 张三 1613401510借阅信息示例如下，每条信息一行：腹有诗书气自华标志位1( 1表示借阅2表示归还)16000001数据结构 161340106 张三2013.9.12(借阅时表示借阅日期，应还日期自动生成，根据借阅日期+60天;归还时表示归还日期，归还日期要在借阅日期之后，应还日期之前，如果超过应还日期，则记录一次违约次数)。例如借阅：1 16000001数据结构161340106张三2013.9.12归还：2 160

3、00001数据结构161340106张三2013.10.20(6) 规定每位学生不能同时借阅同一本书两本及以上。图书归还后，将该条借阅信息 从借阅链表中转移到归还链表中。(7) 要求模拟数据中图书信息至少 30本以上，学生信息至少20条以上，借阅信息 至少50条以上。(8) 能够统计每一本图书被借阅次数(已还)，在借册数。查询每一位学生的借阅历 史明细记录。统计学生平均借阅次数，最大借阅次数，最少借阅次数。(9) 可在此要求基础上进行功能扩展。2、算术表达式求值(栈)问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter) 组成的。假设操作数

4、是正实数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符 “#”，如：# (7+15)* (23-28/4 )#。引入表达式起始、 结束符是为了方便。编程利用“算符优先法”求算术表达式的值。基本要求（1）从键盘或文件读入一个合法的算术表达式，输出正确的结果。（2）显示输入序列和栈的变化过程。（3）考虑算法的健壮性，当表达式错误时，要给出错误原因的提示。3、二叉树的应用（二叉树）问题描述编程实现二叉树的建立，先序、中序、后序（递归和非递归方法）、层序遍历，二叉树的高度、繁茂度，交换左右子树，统计叶子节点的数目，判断是否为完全二叉树， 按树的形态在屏幕上打印输出。基本要求（1

5、 1） 从文件中读入建树信息，树的节点数目不小于2020个，树的高度不小于4 4。（2） 建树信息采用两行英文字符表示，每个英文字符代表一个结点，第1行为树的 中序遍历结果，第2行为树的后序遍历结果。4、Huffman 编码与解码（Huffman 编码、二叉树）问题描述对一篇英文文章（大于2000个英文字符），统计各字符出现的次数，实现Huffman 编码，以及对编码结果的解码。基本要求（1） 输出每个字符出现的次数和编码，其中求最小权值要求用堆实现。（2） 在Huffman 编码后，要将编码表和英文文章编码结果保存到文件中，编码结 果必须是二进制形式，即0 1的信息用比特位表示，不能用字符

6、和表示。（3）提供读编码文件生成原文件的功能。5、关键路径问题（图）问题描述设计并实现关键路径的一种应用。基本要求（1 1实现拓扑排序和关键路径的发现。（2 2）给出一个具体的应用环境。6、排序算法比较（排序）问题描述利用随机函数产生10个样本（其中之一已为正序，之一为倒序），每个样本有20000 随机整数，利用直接插入排序、希尔排序，冒泡排序、快速排序、选择排序、堆排序， 归并排序（递归和非递归），基数排序八种排序方法进行排序（结果为由小到大的顺序） 并统计每一种排序所耗费的平均时间基本要求（1） 原始数据存在文件中，每个整数一行，方便读入。（2） 屏幕显示每种排序所花的比较次数。二、选做题

7、1、迷宫问题（栈与递归）问题描述利用栈操作实现迷宫问题求解。基本要求（1 1）随机生成模拟迷宫地图，不少于 1010行1010列，存在文件中（2 2）动态显示每一步的结果 。（3 3）可在此基础上有改进方法。2、家谱管理系统（树）问题描述实现具有下列功能的家谱管理系统基本要求（1）输入文件以存放最初家谱中各成员的信息，成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡），也可附加其它信息、但不是必需的。（2）实现数据的存盘和读盘。（3 ）以图形方式显示家谱。（4）显示第n代所有人的信息。（5）按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。（6

8、）按照出生日期查询成员名单。（7）输入两人姓名，确定其关系。（8）某成员添加孩子。（9）删除某成员（若其还有后代，则一并删除）。（10） 修改某成员信息。（11 ）按出生日期对家谱中所有人排序。（12 ）打开一家谱时，提示当天生日的健在成员。（13） 要求建立至少30个成员的数据，以较为直观的方式显示结果，并提供文稿形式 以便检查。（14） 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关 的功能要求。（15） 存储结构：根据系统功能要求自行设计，但是要求相关数据要存储在数据文件中。测试数据：要求使用1、全部合法数据；2、局部非法数据。进行程序测试，以保 证程序的稳定。3、

9、公交线路提示（图）问题描述建立南京主要公交线路图。基本要求（1 ）输入任意两站点，给出最佳的乘车线路和转车地点。路线信息：可上网查询最新的公交线路信息4、社交网络图实现（图）问题描述设计并实现一种简单的社交网络模型图。基本要求（1 1）每个人的信息是一个结点，人与人的联系构成边。个人信息里要有地理坐标信息， 以便后续应用中能方便找靠近的人。（2 2）根据输入的任意两个人信息，给出他们之间的联系路径，最少经过多少人构成联 系。（3 3） 根据位置信息的动态变化，找寻附近能够联络的人，能够通过1 1次中间人能联络 的人等。（4 4）模拟仿真结点的联络密切程度，根据联络密切程度发现社交网络中的小团体

10、。（5 5）可根据自己的创意添加更多的功能。5、营业窗口队列模拟任务：实现具有n （n=3 ）个窗口的现实队列模拟，统计每人的等待时间 要求：1） .随机产生顾客的到达时间和服务时间存盘2） .利用存盘数据实现队列的插入和删除。2) .当有顾客离开时，根据队列长度调整队尾。3) .考虑顾客中途离队的情况。4) .考虑顾客具有优先级的情况。6、 电子小字典任务：建立一个微型电子字典，实现生词的加入，单词的查找、删除，修改等操作。 数据结构：键树7、 稀疏矩阵相乘任务：以三元组形式存储稀疏矩阵，实现矩阵相乘8、 平衡二叉树任务：平衡二叉树的建立、结点的插入和删除。9、B-树任务：3阶B-树的结点的

11、插入和删除。10、 编写“连连看”程序。11、 (自选合适的题目)成绩评定细则：1.正确性：程序是否可以运行，结果是否正确（20分）2.功能的完备性：是否实现要求的所有子功能（20分）3.课程设计报告中的算法说明的清晰程度，课程设计报告中总结的深刻程度（20分）4.独立完成情况（40分）总计：100分加分项目：1.工作量和选题难度2.可读性：代码编写是否规范，是否便于阅读。如函数、变量命名， 的缩进，关键位置适量注释等3.功能的完善：除要求实现的功能外，完成了其它的功能，实现了功能的完善4.健壮性：异常处理的情况5.界面的设计：可视化界面，或者交互良好的DOS界面6.（自荐加分项目）代码量要求

12、：=2200 行 代码总量=课设题目1代码量+课设题目2代码量 若代码总量低于2200行，则成绩按比例打折。编程语言：C、C+ 或JAVA 任选其一检查方式：1.一对一上机检查2.总体上检查程序的代码量，正确性，可读性，健壮性，功能的完备性，程序的结构 是否合理；根据实际情况进行详细的程序代码检查。时间安排：1上机时间安排2课程设计报告上交时间3课程设计检查时间课程设计报告要求：1.课程设计报告封面：包括课题名称、班级、学号、学生姓名、成绩和指导教师;2.课程设计报告目录：每部分内容所在页码；3.需求分析：给出每道题的需求；4.概要设计：给出每道题采用的数据结构，算法设计思想，算法的时间复杂度

13、；5.详细设计：给出每道题的源程序，并在必要的代码处给出注释；6.功能测试：给出每道题的测试数据和结果；7.完成情况：每道题完成部分和未完成部分，自己最满意的部分；8.代码量：每道题代码的行数和总行数；9.心得体会：包括课程设计设中遇到的问题，如何解决，编程的体验，感想和建议;10.课程设计报告的电子文档在检查后一周内上交班长。出师表两汉：诸葛亮先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。然侍卫之臣不懈于 内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。诚宜开张圣听，以光先帝遗德，恢 弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。宫中府中，俱为一体；陟罚臧否

14、，不宜异同。若有作奸犯科及为忠善者，宜付有司论其刑赏， 以昭陛下平明之理；不宜偏私，使内外异法也。侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：愚以为宫 中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰能”是以众议举宠为督：愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。先帝在时，每与 臣论此事，未尝不叹息痛恨于桓、灵也。侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲 之、信之，则汉室之隆，可计日而待也 F。臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。先帝不以臣卑鄙，猥自枉屈，三 顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。后值倾覆，受任于败军之际，奉 命于危难之间，尔来二十有一年矣。先帝知臣谨慎，故临崩寄臣