数据结构课程设计任务书2011
《数据结构》课程设计任务书
一、数据结构课程设计要求
仔细阅读《数据结构课程设计指导》一书，选好题目，认真制定课程设计方案，在规定的时间内设
计完成并按一定格式以书面形式上交报告。设计报告内容一般包括以下几个方面：（1）问题描述；
（2）设计思路；（3）数据结构定义；（4）系统功能模块介绍。（5）程序清单；（6）运行及调试分析；（7）课程设计总结等。
二、数据结构课程设计的具体内容
本次课程设计参考题目如下，要求完成至少两个题目，且至少包含一个非线性结构题型，16周前每
人需上报题目，定题后无特殊情况不准修改。（可自行选题）
1．一元多项式计算
能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减和相乘，并将结果
输出。
2．矩阵的运算
采用十字链表表示稀疏矩阵，并实现矩阵的加法运算, 要求：要检查有关运算的条件，并对错误的条件产生报警。
3．订票系统
设计航班信息，订票信息的存储结构，设计程序完成如下功能：
录入：可以录入航班情况(数据可以存储在一个数据文件中，数据结构、具体数据自定)
查询：可以查询某个航线的情况(如，输入航班号，查询起降时间，起飞抵达城市，航班票价，
票价折扣，确定航班是否满仓)；可以输入起飞抵达城市，查询飞机航班情况；
订票：(订票情况可以存在一个数据文件中，结构自己设定)可以订票，如果该航班已经无票，
可以提供相关可选择航班；
退票：可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
修改航班信息：当航班信息改变可以修改航班数据文件
4．迷宫求解
输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出；
5．文章编辑器
编写一个简单的文本编辑软件，能基本实现文本的输入、修改、插入、删除等功能。
6．宾馆订房和退房系统
假设一个宾馆有n个标准的客房，每个标准客房有m个标准间，利用链表、栈或者队列等数据
结构设计出具有订房和退房等功能的管理系统。
7．建立二叉树和线索二叉树
分别用以下方法建立二叉树并用图形显示出来：
1）用先序遍历的输入序列
2）用层次遍历的输入序列
3）用先序和中序遍历的结果
最后对所建立的二叉树进行中序线索化，并对此线索树进行中序遍历(不使用栈)。
8．学生成绩查询系统
试编写程序完成学生成绩记录的查询。
学生基本情况
①若按学号进行顺序查找，例如：输入99070103，则输出 56 。
②按学号排序后对学号进行折半查找。
③随机输入以学号为关键字的学生信息并构建二叉排序树，对学号进行二叉排序树查找。
9．马的遍历问题
设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。
要求：
1)依次输出所走过的各位置的坐标。
2)最好能画出棋盘的图形形式，并在其上动态地标注行走过程。
10. 教学计划编制问题
大学的每个专业都要编制教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。每个课程的先修关系都是确定的，可以有任意多门，也可以没有。每一门课程恰好一个学期。试在这样的情况下设置一个教学计划编制程序。
设计要求：针对计算机系本科课程，根据课程之间的依赖关系(如高级语言、离散数学应在数据结构之前开设)制定课程安排计划，并满足各学期课程数目大致相同。
11. 大数相乘问题
例如：输入第一个数为：13286754398172586，输入第二个数为：2397567453241147则程序运行后输出13286754398172586*2397567453241147=正确答案。
12. 设计一个模拟计算器来完成表达式的计算
要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解，操作数可以是多位数。
13. 八皇后问题
设计程序完成如下要求：在8×8的国际象样棋盘上，放置8个皇后，使得这8个棋子不能互相被对方吃掉。
要求： 1)依次输出各种成功的放置方法。
2)最好能画出棋盘的图形形式，并在其上动态地演示试探过程。
14. 3×3的九宫问题
在一个3×3的九宫中有1∽8这8个数及一个空格随机地摆放在其中的格子里。如下图
10.1(a)所示。现在要求实现这样的问题：将该九宫格调整为如下图10.1(b)所示的形式。调整的规则是：每次只能将与空格(上、下或左、右)相邻的一个数字平移到空格中。试编程实现这一问题的求解。
237123
18684
54765
(a) (b)
15. 图的遍历过程演示
设计程序完成如下功能：对给定的图结构和起点，产生深度优先遍历和广度优先遍历序列，并
给出求解过程的动态演示。
16. 运动会分数统计
参加运动会有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) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
规定：输入数据形式和范围：20以内的整数(如果做得更好可以输入学校的名称，运动项目的名称)
输出形式：有中文提示，各学校分数为整型
界面要求：有合理提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
17．构造n个城市连接的最小生成树
一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。基本要求：
1) 城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
2)表示城市间距离网的邻接矩阵(要求至少6个城市，10条边)
18．输入带排序序列生成二叉排序树，并调整使其变为平衡二叉树。
要求能将平衡化过程动态地演示出来。
三、几点说明
1、学期结束前在机房验收程序和课程设计报告；
2、课程设计报告注意事项：
1）运行结果请截图（Alt + PrtSc）；
2) 系统功能模块介绍请请采用流程图形式；
3）课程设计总结可以从以下几个方面书写: 课程设计的收获、遇到问题及其解决过程、程序调试技巧、在课程设计过程中对《数据结构》课程的认识等内容。
附一：课程设计报告封面 ( 打印时删除此行 )《数据结构》课程设计报告
学 号姓 名班 级指导教师储岳中
安徽工业大学计算机学院2011年6月严等问交叉时源，线缆进行调试卷技资料试卷关高中资试卷保资料试中资料试
附二：实验报告封面(打印时删除此行)
《数据结构》实 验 报 告
学 号姓 名班 级指导教师储岳中
安徽工业大学计算机学院2011年6月严等问交叉时源，线缆进行调试卷技资料试卷关高中资试卷保资料试中资料试