数据结构A课程设计指导书-改后.doc

数据结构A课程设计指导书

计算机与信息工程学院

一、设计目的
熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。
二、设计要求
在本课程设计过程中要求学生：
（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；
（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。
（3）认真编写课程设计报告。课程设计报告的书写格式及要求见附录2。
三、设计步骤
1、 问题分析和任务定义；
2、 数据类型和系统设计；
3、 编码实现和静态检查；
4、 上机调试；
5、 总结和整理课程设计说明书。
四、考核方式和成绩评定
考核分为两个部分：
l 程序运行情况：按规定时间到机房运行程序，由教师检查运行情况。针对自己的程序，学生能熟练清楚地回答教师的问题。
l 课程设计说明书：是否按规定书写课程设计说明书的各项内容。
课程设计成绩采用五级分制。
100%=程序运行情况（60%）+课程设计说明书（40%）
五、上交相关内容要求
l 上交时间：最后一次课，验收程序时。
l 纸质版：课程设计说明书，内容与电子版完全一致，具体要求见电子版说明。
l 电子版：压缩包上传到ftp，命名“学号姓名”，必须由以下部分组成，缺一不可：
1．源程序：学生按照课程设计的具体要求所开发的所有源程序（放到一个文件夹中）；
2．说明文件：（保存在.doc中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；
3．课程设计说明书：（保存在word 文档中，文件名要求 按照"学号-姓名-课程设计说明书"命名，如文件名为"101-张三-课程设计说明书".doc ）根据《附录1：数据结构课程设计的具体内容》 的题目要求，完成课程设计说明书，内容按照如下几个方面展开，格式见《附录2：课程设计说明书规范》 ；
1、需求分析
1． 程序的功能；
2． 输入输出的要求；
3． 测试数据。
2、概要设计
包括程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。
3、详细设计
包括模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等），每个模块的算法设计说明（可以是描述算法的流程图）。
4、调试分析
测试数据，测试输出的结果。分析时间复杂度，思考每个模块在设计和调试时存在的问题及解决方案（问题是哪些？问题如何解决？），算法的改进设想。
5、核心源程序清单和执行结果
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序清单中应有足够的注释描述问题和功能设计。
通过一系列的程序执行结果截图，展示程序的所有功能。
附录1 数据结构课程设计的具体内容
本次课程设计完成如下模块（共15个模块，见题目分配表，确定自己题目）
1、信号放大器
1) 问题描述
天然气经过管道网络从其生产基地输送到消耗地，在传输过程中，其性能的某一个或几个方面可能会有所衰减（例如气压）。为了保证信号衰减不超过容忍值，应在网络中的合适位置放置放大器以增加信号（例如电压）使其与源端相同。设计算法确定把信号放大器放在何处，能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。
2) 基本要求
(1) 建立模型，设计数据结构；
(2) 设计算法完成放大器的放置；
(3) 分析算法的时间复杂度。
3) 设计思想
为了简化问题，假设分布网络是二叉树结构，源端是树的根结点，信号从一个结点流向其孩子结点，树中的每一结点（除了根）表示一个可以用来放置放大器的位置。图5是一个网络示意图，边上标出的是从父结点到子结点的信号衰减量。
A
B
C
D
E
F
G
H
I
J
K
1
3
1
2
2
2
2
1
2
2
图5 网络分布示意图

对于网络中任一结点i，设d(i)表示结点i与其父结点间的衰减量，D(i)为从结点i到结点i的子树中任一叶子结点的衰减量的最大值，并有如下递推公式：
D(i)=0 若i为叶子结点
D(i)= max{D(j) + d(j)} 若i不是叶子结点且j是i的孩子

在此公式中，要计算某结点的D值，必须先计算其孩子结点的D值，因而必须后序遍历二叉树，当访问一个结点时，计算其D值。
例如，D(B)=max{D(D)+d(D)，D(E)+ d(E)}=4，若容忍值为3，则在B点或其祖先的任意一点放置放大器，并不能减少B与其后代的衰减量，必须在D点放置一个放大器或在其孩子结点放置一个或多个放大器。若在结点D 处放置一个放大器，则D(B)=2。
根据上述分析，设计如下存储结构：
struct element
{
int D; // 该结点的衰减量
int d; // 父结点的衰减量
bool boost; //当且仅当本处设置放大器，则boost为true
};
struct BiNode
{
element data;
BiNode *lchild,*rchild;
};
计算并放置放大器的伪代码为：
1. D(i) = 0 ;
2. for (i 的每个孩子j )
2.1 如果D(j) +d(j)>容忍值，则在j处放置放大器;
2.2 否则D(i) = max{D(i)，D(j) +d(j)} ;
【思考题】本题假设分布网络是一棵二叉树结构，如果是树结构应如何设计算法？

2、迷宫问题
迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图2所示为一个迷宫示意图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。

0
1
2
3
4
5
6
7
8
9
0
1
1
1
1
1
1
1
1
1
1
入口(1, 1)
出口(6, 8)

图2 迷宫示意图，其中1代表有障碍，0代表无障碍
前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下
1
1
0
1
1
1
0
1
1
1
1
2
1
1
0
1
0
1
1
1
1
1
3
1
0
1
0
0
0
0
0
1
1
4
1
0
1
1
1
0
1
1
1
1
5
1
1
0
0
1
1
0
0
0
1
6
1
0
1
1
0
0
1
1
0
1
7
1
1
1
1
1
1
1
1
1
1

2) 基本要求
(1) 设计数据结构存储迷宫；
(2) 设计存储结构保存从入口到出口的通路；
(3) 设计算法完成迷宫问题的求解；
(4) 分析算法的时间复杂度。
3) 设计思想
可以采用回溯法实现该问题的求解。回溯法是一种不断试探及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向；若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都搜索到，或找到一条通路，或无路可走又返回到入口点。
在求解过程中，为了保证在任何位置上都能沿原路退回，需要一个后进先出的栈来保存从入口到当前位置的路径。
可以将迷宫定义成一个二维数组，则每个点有8个试探方向，如当前点的坐标是(x, y)，与其相邻的8个点的坐标都可根据与该点的相邻方位而得到，规定试探顺序为顺时针方向，将这8个方向的坐标增量放在一个结构数组move[8]中，在move数组中，每个元素由两个域组成：x表示横坐标增量，y表示纵坐标增量。这样会很方便地求出从某点(x，y)按某一方向 v (0≤v≤7) 到达新点（i，j）的坐标：i=x+move[v].x ； j=y+move[v].y。
算法用伪代码描述如下：
1. 栈初始化；
2. 将入口点坐标(x , y)及该点的方向d（设为-1）入栈；
3. 当栈不空时循环执行下述操作：
3.1 (x , y , d)<==栈顶元素出栈；
3.2 求出下一个要试探的方向d++ ;
3.3 沿顺时针试探每一个方向，执行下述操作：
3.3.1 如果方向d可走，则
3.3.1.1 将(x , y , d)入栈；
3.3.1.2 求新点坐标(i, j)；
3.3.1.3 将新点(i , j)切换为当前点(x , y)；
3.3.1.4 若(x, y)是终点，则算法结束；
否则，重置d=0；
3.3.2 否则，试探下一个方向d++；
3、TSP问题
1) 问题描述
所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。
2) 基本要求
(1) 上网查找TSP问题的应用实例；
(2) 分析求TSP问题的全局最优解的时间复杂度；
(3) 设计一个求近似解的算法；
(4) 分析算法的时间复杂度。
3) 设计思想
对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!)，当n大到一定程度后是不可解的。
本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。
为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下：
1. 任意选择某个顶点v作为出发点；
2. 执行下述过程，直到所有顶点都被访问：
2.1 v=最后一个被访问的顶点；
2.2 在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j；
2.2 访问顶点j；
3. 从最后一个访问的顶点直接回到出发点v；
4、医院选址问题
1)问题描述
n个村庄之间的交通图可以用有向网图来表示，图中边<vi, vj>上的权值表示从村庄i到村庄j的道路长度。现在要从这n个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄，才能使所有的村庄离医院都比较近？
2) 基本要求
(1) 建立模型，设计存储结构；
(2) 设计算法完成问题求解；
(3) 分析算法的时间复杂度。
3) 设计思想
医院选址问题实际是求有向图中心点的问题。首先定义顶点的偏心度。
设图G=（V，E），对任一顶点k，称E(k)=max{d(i, k)}（i∈V）为顶点k的偏心度。显然，偏心度最小的顶点即为图G的中心点。
如图7(a)所示是一个带权有向图，其各顶点的偏心度如图(b)所示。

a
b
c
d
e
1
2
5
3
2
1
4
顶点
偏心度
a
¥
b
6
c
8
d
5
e
7
(a) (b)
图7 带权有向图及各顶点的偏心度

医院选址问题的算法用伪代码描述如下：
1．对加权有向图，调用Floyd算法，求每对顶点间最短路径长度的矩阵；
2．对最短路径长度矩阵的每列求大值，即得到各顶点的偏心度；
3．具有最小偏心度的顶点即为所求。
【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。从医院选址问题的求解过程，你有什么感想？
5、机器调度问题
1)问题描述
机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：
(1) 一台机器在同一时间内只能处理一个作业；
(2) 一个作业不能同时在两台机器上处理；
(3) 作业i一旦运行，则需要ti个连续时间单位。
设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。
2) 基本要求
(1) 建立问题模型，设计数据结构；
(2) 设计调度算法，为每个作业分配一台可用机器；
(3) 给出分配方案。
3) 设计思想
假设有七个作业，所需时间分别为{2, 14, 4, 16, 6, 5, 3}，有三台机器，编号分别为m1、m2和m3。这七个作业在三台机器上进行调度的情形如图9所示，阴影区代表作业的运行区间。作业4在0到16时间被调度到机器1上运行，在这16个时间单位中，机器1完成了对作业4的处理；作业2在0到14时间被调度到机器2上处理，之后机器2在14到17时间处理作业7；在机器3上，作业5在0～6时间完成，作业6在6～11时间完成，作业3在11～15时间完成，作业1在15～17时间完成。注意到作业i只能在一台机器上从si时刻到si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为17。
m1
m2
m3
时间
分配
作业5
作业6
作业3
作业1
作业2
作业7
作业4
17
16
图9 三台机器的调度示例
6
5
4

在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。
下面设计完成LPT算法的存储结构。
· 为每个机器设计数据类型：
struct MachineNode
{
int ID; //机器号
int avail; //机器可用时刻
};
· 为每个作业设计数据类型：
struct JobNode
{
int ID; //作业号
int time; //处理时间
};
LPT算法用伪代码描述如下：
1. 如果作业数n≤机器数m，则
1.1 将作业i分配到机器i上；
1.2 最短调度长度等于n个作业中处理时间最大值；
2. 否则，重复执行以下操作，直到n个作业都被分配：
2.1 将n个作业按处理时间建成一个大根堆H1；
2.2 将m个机器按可用时刻建立一个小根堆H2；
2.3 将堆H1的堆顶作业分配给堆H2的堆顶机器；
2.4 将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入H2中；
2.5 将堆H1的堆顶元素删除；
3. 堆H2的堆顶元素就是最短调度时间；

6、运动会分数统计
1)问题描述
参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（n<=20,m+w<=20）
2) 基本要求
(1)可以输入各个项目的前三名或前五名的成绩；
(2)能统计各学校总分；
(3)可以按学校编号、学校总分、男女团体总分排序输出；
(4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）
输出形式：有中文提示，各学校分数为整型
界面要求：有合理提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c++语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；
测试数据：要求使用1、全部合法数据；2、全部非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。
7、模拟网上订票系统
1)问题描述
通过此系统可以实现如下功能：
(1)录入：
可以录入航班情况（数据存储能在一个数据文件中，数据结构、具体数据自定）
(2)查询：可以查询某个航线的情况
可以输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓；
可以输入起飞抵达城市，查询飞机航班情况；
(3)订票：（订票情况能存在一个数据文件中，结构自己设定）
可以按航班号订票，如果该航班已经无票，可以提供相关可选择航班；
可以按起飞抵达城市订票；
订票信息包含订单编号、客户姓名，证件号，航班情况。
(4)退票： 可退票，退票后修改相关数据文件；
(5)修改航班信息：
当航班信息改变可以修改航班数据文件
2) 基本要求
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。
8、停车场管理
1)问题描述
　　设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
2)基本要求
　　以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
3)测试数据
设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3， 20）， （‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。
4)实现提示
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
5)选作内容
　　（1） 两个栈共享空间，思考应开辟数组的空间是多少？
　　（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
　　（3） 汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
　　（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。
9、简单行编辑程序
1)问题描述
文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。
被编辑的文本文件可能很大，全部读入编辑程序的数据空间（内存）的做法既不经济，也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存，称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行最多含320个字符，实际含量很少超过80字符。
2)基本要求
实现以下4条基本编辑命令：
　（1） 行插入。格式：i<行号><回车><文本><回车>
　　将<文本>插入活区中第<行号>行之后
　（2）行删除。格式：d<行号1>[□<行号2>]<回车>
　　删除活区中第<行号1>行（到第<行号2>行）。两种格式的例子是：“d10↙”和“d10□14↙”
　（3）活区切换。格式：n<回车>
　　将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。
　（4）活区显示。格式：p<回车>
逐页地（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。打印出的每一行要前置行号和一个空格符，行号固定占4位，增量为1。
各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减1，表示插入当前屏幕中第一行之前，否则命令参数非法。
3)测试数据
由学生依据软件工程的测试技术自己确定。注意测试边界数据，如首行、尾行。
4)实现提示
（1） 设活区的大小用行数activemaxlen（可设为100）来描述。考虑到文本文件行长通常为正态分布，且峰值在60到70之间，用320×activemaxlen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储，每个标准行块含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。
（2） 初始化过程包括：请用户提供输入文件名（空串表示无输入文件）和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过activemaxlen-x。x的值可以自定，例如20。
（3） 在执行行插入命令的过程中，每接收到一行时都要检查活区大小是否已达activemaxlen。如果是，则为了在插入这一行之后仍保持活区大小不超过activemaxlen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。
（4） 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。
（5） 可令前三条命令执行后自动调用活区显示。
5)选作内容
（1） 对于命令格式非法等一切错误作严格检查和适当处理。
（2） 加入更复杂的编辑操作，如对某行进行串替换、在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。
10、哈希表设计
1)问题描述
　　针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
2)基本要求
　　假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。用除留余数法设计哈希函数，分别用两种方法处理冲突：线性探测法和拉链法，构造两个散列表，并给出两个散列表的平均查找长度。
3)测试数据
　　取读者周围较熟悉的30个人名。
4)选作内容
（1） 从教材上介绍的几种哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。
（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。
（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。
11、校园导游程序
1)问题描述
　　用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
2)基本要求
　　（1） 查询各景点的相关信息；
　　（2） 查询图中任意两个景点间的最短路径。
　　（3） 查询图中任意两个景点间的所有路径。
　　（4） 增加、删除、更新有关景点和道路的信息。
3)选作内容
　　（1） 求多个景点的最佳（最短）游览路径。
　　（2） 区分机动车道和人行道。
　　（3） 实现导游图的仿真界面。
12、排序系统设计
1)问题描述
设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出列编号序列。
2) 基本要求
（1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
（2）完成最低要求：建立一个系统，包括5个人的情况。
13、某机场的机票管理系统
1)问题描述
一机场每天有n个航班，每个班次都有一班次号（1、2、3…n），固定的起飞时间，固定的路线（起始站、终点站），大致的飞行车时间，固定的额定载客量。如

班次 起飞时间 起点站 终点站 飞行时间 额定载量 已定票人数
1 8:00 天津 广汉 2 145 130
2 6:30 天津 成都 0.5 140 140
3 7:00 天津 成都 0.5 140 120
4 10:00 天津 成都 0.5 140 120
…
试设计一个机票管理系统，对机场的售票情况进行管理。
2) 基本要求
（1）录入班次信息(信息用文件保存),可不定时地增加班次数据；
（2）浏览班次信息,可显示出所有班次当前状况(如果当前系统时间超过了某班次的起飞时间,则显示“此班已发出”的提示信息)。
（3）查询路线：可按班次号查询 ,可按终点站查询；
（4）售票和退票功能(信息用文件保存)
A：当查询出已定票人数小于额定载量且当前系统时间小于起飞时间时才能售票，自动更新已售票人数
B：退票时，输入退票的班次，当本航班飞机未发出时才能退票，自动更新已售票人数。
14、集合运算
1)问题描述
使用链表来表示集合，完成集合的合并，求交集等操作。
2) 基本要求
（1）用链表表示两个集合
（2）对两个集合分别从小到大排序
（3）两个集合合并成另一个新集合，如数值相同，合并为一个数据项
（4）求出两个集合的交集建立一个新的集合。
15、二叉排序树的遍历（ 用递归或非递归方法都可以）
1)问题描述
输入树的各个结点，建立二叉排序树，对建立的二叉排序树进行层序、先序、中序和后序遍历并统计该二叉树中叶子结点的数目，以及该二叉树的平均查找长度。
2)基本要求
(1)用菜单实现
(2)能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列和叶子结点的数目，以及该二叉树的平均查找长度。
附录2：课程设计说明书规范
一、课程设计说明书规范
课程设计说明书是课程设计主要成果之一，对于设计类，应包括图纸、程序、实物成果等。
1、说明书基本格式
说明书打印，正文采用5号宋体，A4纸，页边距均为20mm，行间距采用18磅。文中标题采用宋体加粗。
2、说明书结构及要求
（1）封面（见附录3）
包括：题目、系别、班级、完成日期、成绩及指导教师（签字）、学生姓名等项。
（2）课程设计任务书 （格式见附录4）
（3）目录（自动生成目录）
要求层次清晰，列出正文的5个标题及页码，并且最后一项为"参考资料"。
各章题序及标题用小4号黑体，其余用小4号宋体。
（4）正文
正文应按照目录所确定的顺序依次撰写，要求计算准确，论述清楚、简练、通顺，插图清晰整洁。文中图、标及公式应规范地绘制和书写。
（5）参考资料
参考资料按下述顺序和格式书写：
[1]毛昶熙，周名德等．闸坝工程水力学与设计管理.北京：水利电力出版社，1995：8—9

如参考网上资料，请写明网址。

注：正文内容可参考以下内容：
正文
a) 需求分析：程序的功能；输入输出的要求；测试数据。
b) 概要设计：程序设计组成框图，程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。
c) 详细设计：模块功能说明（如函数功能、入口及出口参数说明，函数调用关系描述等），每个模块的算法设计说明（可以是描述算法的流程图）
d) 调试分析：测试数据，测试输出的结果。分析时间复杂度，思考每个模块在设计和调试时存在的问题及解决方案（问题是哪些？问题如何解决？），算法的改进设想。
e) 核心源程序清单和执行结果：源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序清单中应有足够的注释描述问题和功能设计。通过一系列的程序执行结果截图，展示程序的所有功能。
（附录3：封面要求）

学 号

（数据结构A）
课程设计说明书

（题目）

起止日期： 2016 年 1 月 11 日 至 2016 年 1 月 15 日

学生姓名

班级

成绩

指导教师(签字)

计算机与信息工程学院计算机科学与技术系
2016年 1 月 15 日

（附录4）

天津城建大学
课程设计任务书
2015 —2016 学年第 1 学期
计算机与信息工程 学院 软件工程 系 软件工程 专业 14级1 班级
课程设计名称： 数据结构A
设计题目：
完成期限： 自 2016 年 1 月 11 日至 2016 年 1 月 15 日共 1 周
设计依据、要求及主要内容（可另加附页）：
（一）设计依据
依据数据结构授课的理论内容，通过课程设计，以达到熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题的设计目标。
（二）设计要求：
在本课程设计过程中要求学生：
（1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务；
（2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。
（3）学生在接受设计任务后，首先要按设计任务书的要求编写设计进程表。
（4）认真编写课程设计说明书。
（三）设计内容
（自填，只填自己的设计内容）

指导教师（签字）：
系 主 任（签字）：
批准日期： 2016 年 1 月 11 日