同济2022年数据结构课程设计项目代码及实验报告

每一个实验包含以下六个文件，可以在Windows与Linux双系统上运行

• .cpp文件（main函数）
• .h文件（库函数）
• .exe文件（可执行文件）
• Makefile
• out

项目简介：

考试报名工作给各高校报名工作带来了新的挑战，给教务管理部门增加了很大的工作 量。本项目是对考试报名管理的简单模拟，用控制台选项的选择方式完成下列功能：输入考 生信息；输出考生信息；查询考生信息；添加考生信息；修改考生信息；删除考生信息。

项目功能要求：

本项目的实质是完成对考生信息的建立，查找，插入，修改，删除等功能。其中考生信 息包括准考证号，姓名，性别，年龄和报考类别等信息。项目在设计时应首先确定系统的数 据结构，定义类的成员变量和成员函数；然后实现各成员函数以完成对数据操作的相应功能； 最后完成主函数以验证各个成员函数的功能并得到运行结果。（建议采用链表实现）

项目功能要求：(要求采用链表)

1. 输入说明：输入分 2 行，分别在每行给出由若干个正整数构成的非降序序列，用- 1 表示序列的结尾（- 1不属于这个序列）。数字用空格间隔。
2. 输出说明：在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能 有多余空格；若新链表为空，输出NULL。
3. 测试用例：

项目简介：

迷宫只有两个门，一个门叫入口，另一个门叫出口 。一个骑士骑马从入口进入迷宫，迷 宫设置很多障碍，骑士需要在迷宫中寻找通路以到达出口 。

项目功能要求：

迷宫问题的求解过程可以采用回溯法即在一定的约束条件下试探地搜索前进，若前进中 受阻，则及时回头纠正错误另择通路继续搜索的方法。从入口出发，按某一方向向前探索， 若能走通，即某处可达，则到达新点，否则探索下一个方向；若所有的方向均没有通路，则 沿原路返回前一点，换下一个方向再继续试探，直到所有可能的道路都探索到，或找到一条 通路，或无路可走又返回入口点。在求解过程中，为了保证在达到某一个点后不能向前继续 行走时，能正确返回前一个以便从下一个方向向前试探，则需要在试探过程中保存所能够达 到的每个点的下标以及该点前进的方向，当找到出口时试探过程就结束了。

项目内容：

算数表达式有前缀表示法，中缀表示法和后缀表示法等形式。日常使用的算术表达式是 采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达式转换成为后 缀表达式。

项目要求：

1. 输入说明：输入在一行中给出以空格分隔不同对象的中缀表达式，可包含+, -, *, /, -, *, /以及左右括号，表达式不超过 20个字符（不包括空格）。
2. 输出说明：在一行中输出转换后的后缀表达式，要求不同对象（运算数，运算符号） 之间以空格分隔，但是结尾不得有多余空格。
3. 测试用例：

项目内容：

设某银行有A，B 两个业务窗口，且处理业务的速度不一样，其中A 窗口处理速度是 B 窗口的 2 倍----即当 A 窗口每处理完 2 个顾客是，B 窗口处理完 1 个顾客。给定到达银行的 顾客序列，请按照业务完成的顺序输出顾客序列。假定不考虑顾客信后到达的时间间隔，并且当不同窗口同时处理完 2 个顾客时，A 窗口的顾客优先输出。

项目功能要求

1. 输入说明：输入为一行正整数，其中第一数字N（N<=1000）为顾客总数，后面跟 着 N 位顾客的编号。编号为奇数的顾客需要到 A 窗口办理业务，为偶数的顾客则 去 B 窗口 。数字间以空格分隔。
2. 输出说明：按照业务处理完成的顺序输出顾客的编号。数字键以空格分隔，但是最 后一个编号不能有多余的空格。
3. 测试用例：

项目简介：

家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世袭繁衍和重要任务事迹的 特殊图书体裁。家谱是**特有的文化遗产，是中华民族的三大文献（国史，地志，族谱） 之一，属于珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究， 均有其不可替代的独特功能。本项目兑对家谱管理进行简单的模拟，以实现查看祖先和子孙 个人信息，插入家族成员，删除家族成员的功能。

项目功能要求：

本项目的实质是完成兑家谱成员信息的建立，查找，插入，修改，删除等功能，可以首 先定义家族成员数据结构，然后将每个功能作为一个成员函数来完成对数据的操作，最后完 成主函数以验证各个函数功能并得到运行结果。

项目简介：

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要 N块木头，每块木头长度为整 数 L_i 个长度单位，于是他购买了一个很长的，能锯成N 块的木头，即该木头的长度是 L_i的 总和。但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨 就设酬金等于所锯木头的长度。例如，要将长度为 20 的木头锯成长度为 8，7 和 5 的三段， 第一次锯木头将木头锯成 12 和 8，花费 20；第二次锯木头将长度为 12 的木头锯成 7 和 5 花 费 12，总花费32 元。如果第一次将木头锯成 15 和 5，则第二次将木头锯成 7 和 8，那么总 的花费是 35（大于 32）.

项目功能要求：

1. 输入格式：输入第一行给出正整数N（N≤10^4），表示要将木头锯成N 块。第二行给出N 个正整数，表示每块木头的长度。
2. 输出格式：输出一个整数，即将木头锯成N 块的最小花费。

项目简介

假设一个城市有 n 个小区，要实现 n 个小区之间的电网都能够相互接通，构造这个城市 n 个小区之间的电网，使总工程造价最低。请设计一个能够满足要求的造价方案。

项目功能要求：

在每个小区之间都可以设置一条电网线路，都要付出相应的经济代价。n 个小区之间最 多可以有 n（n- 1）/2 条线路，选择其中的 n- 1 条使总的耗费最少。

项目内容：

本实验项目是要求在任务调度问题中，如果还给出了完成每个字任务需要的时间，则可 以算出完成整个工程项目需要的最短时间。在这些子任务中，有些任务即使推迟几天完成， 也不会影响全局的工期；但是有些任务必须准时完成，否则整个项目的工期就要因此而延误， 这些任务叫做“关键活动”。

请编写程序判定一个给定的工程项目的任务调度是否可行；如果该调度方案可行，则计 算完成整个项目需要的最短时间，并且输出所有的关键活动。

项目功能要求：

1. 输入说明：输入第 1 行给出两个正整数N（N≤100）和 M，其中N 是任务交接点（即衔接两个项目依赖的两个子任务的结点，例如：若任务2要在任务 1 完成后才 开始，则两个任务之间必有一个交接点）的数量，交接点按 1～N 编号，M 是字任 务的数量，依次编号为 1～M。随后 M 行，每行给出 3 个正整数，分别是该任务开 始和完成设计的交接点编号以及完成该任务所需要的时间，整数间用空格分隔。
2. 输出说明：如果任务调度不可行，则输出0；否则第一行输出完成整个项目所需要 的时间，第 2 行开始输出所有关键活动，每个关键活动占一行，按照格式“v->W” 输出，其中V 和 W 为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是：任务开始的交接点编号小者优先，起点编号相同时，与输入时任务的顺序 相反。如下面测试用例 2 中，任务<5，7>先于任务<5，8>输入，而作为关键活动输 出时则次序相反。
3. 测试用例：

项目简介：

随机函数产生一百，一千，一万和十万个随机数，用快速排序，直接插入排序，冒泡排 序，选择排序的排序方法排序，并统计每种排序所花费的排序时间和交换次数。其中，随机 数的个数由用户定义，系统产生随机数。并且显示他们的比较次数。

请在文档中记录上述数据量下，各种排序的计算时间和存储开销，并且根据实验结果说 明这些方法的优缺点。