同济大学数据结构课程设计.zip

# 同济大学数据结构课程设计 2018同济大学数据结构课程设计 仅作为备份与参考，不允许其他用途 <br> <br> ### 数据结构课程设计题目 #### 题目一 考试报名系统 (**必做**) 项目简介： 考试报名工作给各高校报名工作带来了新的挑战，给教务管理部门增加了很大的工作量。本项目是对考试报名管理的简单模拟，用控制台选项的选择方式完成下列功能：输入考生信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生信息。 项目功能要求： 本项目的实质是完成对考生信息的建立，查找，插入，修改，删除等功能。其中考生信息包括准考证号，姓名，性别，年龄和报考类别等信息。项目在设计时应首先确定系统的数据结构，定义类的成员变量和成员函数；然后实现各成员函数以完成对数据操作的相应功能；最后完成主函数以验证各个成员函数的功能并得到运行结果。（建议采用链表实现） #### 题目二 两个有序链表序列的交集 项目内容 已知两个非降序链表序列S1和S2，设计函数构造出S1和S2的交集新链表S3。 项目功能要求：(要求采用链表) 1. 输入说明：输入分2行，分别在每行给出由若干个正整数构成的非降序序列，用-1表示序列的结尾（-1不属于这个序列）。数字用空格间隔。 2. 输出说明：在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。 3. 测试用例： | 序号 | 输入 | 输出 | 说明 | | ---- | ------------------------- | --------- | ------------------------------ | | 1 | 1 2 5 -1 2 4 5 8 10 -1 | 2 5 | 一般情况 | | 2 | 1 3 5 -1 2 4 6 8 10 -1 | NULL | 交集为空的情况 | | 3 | 1 2 3 4 5 -1 1 2 3 4 5 -1 | 1 2 3 4 5 | 完全相交的情况 | | 4 | 3 5 7 -1 2 3 4 5 6 7 8 -1 | 3 5 7 | 其中一个序列完全属于交集的情况 | | 5 | \-1 10 100 1000 -1 | NULL | 其中一个序列为空的情况 | 题目三 勇闯迷宫游戏 项目简介： 迷宫只有两个门，一个门叫入口，另一个门叫出口。一个骑士骑马从入口进入迷宫，迷宫设置很多障碍，骑士需要在迷宫中寻找通路以到达出口。 项目功能要求： 迷宫问题的求解过程可以采用回溯法即在一定的约束条件下试探地搜索前进，若前进中受阻，则及时回头纠正错误另择通路继续搜索的方法。从入口出发，按某一方向向前探索，若能走通，即某处可达，则到达新点，否则探索下一个方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的道路都探索到，或找到一条通路，或无路可走又返回入口点。在求解过程中，为了保证在达到某一个点后不能向前继续行走时，能正确返回前一个以便从下一个方向向前试探，则需要在试探过程中保存所能够达到的每个点的下标以及该点前进的方向，当找到出口时试探过程就结束了。 项目示例  题目四 表达式转换 项目内容： 算数表达式有前缀表示法，中缀表示法和后缀表示法等形式。日常使用的算术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换成为后缀表达式。 项目要求： 1. 输入说明：输入在一行中给出以空格分隔不同对象的中缀表达式，可包含+, -, \*, /, -, \*, /以及左右括号，表达式不超过20个字符（不包括空格）。 2. 输出说明：在一行中输出转换后的后缀表达式，要求不同对象（运算数，运算符号）之间以空格分隔，但是结尾不得有多余空格。 3. 测试用例： | 序号 | 输入 | 输出 | 说明 | | ---- | ---------------------------------- | ---------------------- | ------------------------------- | | 1 | 2 + 3 \* ( 7 – 4 ) + 8 / 4 | 2 3 7 4 - \* + 8 4 / + | 正常测试6种运算符 | | 2 | ( ( 2 + 3) \* 4 – ( 8 + 2 ) ) / 5 | 2 3 + 4 \* 8 2 + - 5 / | 嵌套括号 | | 3 | 1314 + 25.5 \* 12 | 1314 25.5 12 \* + | 运算数超过1位整数且有非整数出现 | | 4 | \-2 \* ( +3 ) | \-2 3 \* | 运算数有正或负号 | | 5 | 123 | 123 | 只有1个数字 | 题目五 银行业务 项目内容： 设某银行有A，B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍----即当A窗口每处理完2个顾客是，B窗口处理完1个顾客。给定到达银行的顾客序列，请按照业务完成的顺序输出顾客序列。假定不考虑顾客信后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口的顾客优先输出。 项目功能要求 1. 输入说明：输入为一行正整数，其中第一数字N（N\<=1000）为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。 2. 输出说明：按照业务处理完成的顺序输出顾客的编号。数字键以空格分隔，但是最后一个编号不能有多余的空格。 3. 测试用例： | 序号 | 输入 | 输出 | 说明 | | ---- | -------------------- | ------------------ | ------------------- | | 1 | 8 2 1 3 9 4 11 13 15 | 1 3 2 9 11 4 13 15 | 正常测试，A窗口人多 | | 2 | 8 2 1 3 9 4 11 12 16 | 1 3 2 9 11 4 12 16 | 正常测试，B窗口人多 | | 3 | 1 6 | 6 | 最小N | 题目六 家谱管理系统 项目简介： 家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世袭繁衍和重要任务事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史，地志，族谱）之一，属于珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究，均有其不可替代的独特功能。本项目兑对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息，插入家族成员，删除家族成员的功能。 项目功能要求： 本项目的实质是完成兑家谱成员信息的建立，查找，插入，修改，删除等功能，可以首先定义家族成员数据结构，然后将每个功能作为一个成员函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得到运行结果。 项目示例：  题目七 修理牧场 项目简介： 农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数*Li*个长度单位，于是他购买了一个很长的，能锯成N块的木头，即该木头的长度是*Li*的总和。 但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8，7和5的三段，第一次锯木头将木头锯成12和8，花费20；第二次锯木头将长度为12的木头锯成7和5花费12，总花费32元。如果第一次将木头锯成15和5，则第二次将木头锯成7和8，那么总的花费是35（大于32）. 项目功能要求： 1. 输�