《数据结构》课程设计参考题目
一、运动会分数统计——实习1（P79）
任务：参加运动会有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)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
5)数据存入文件并能随时查询
6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称
输出形式：有中文提示，各学校分数为整形
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；
测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；
二、稀疏矩阵运算器
[问题描述]
设计一个稀疏矩阵运算器。 [设计要求]
以十字链表表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。矩阵的输入输出均按通常的阵列形式。
三、停车场管理
[问题描述]
设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。
[设计要求]
（1）要求以顺序栈模拟停车场，以链队列模拟便道。
（2）从终端读入汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”的时刻。与每组输入信息相应的输出信息为：
如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。
四、表达式求值
[问题描述]
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
[设计要求]
（1）从键盘读入一个合法的算术表达式，利用算符优先关系，实现对算术四则混合运算的求值，输出正确的结果。
（2）显示输入序列和栈的变化过程。 [选作内容]
（1）扩充运算符集合。 （2）引入变量操作数。 （3）操作数类型扩充到实数。
五、迷宫问题——实习2（P105）
任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
要求在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
六、文学研究助手——实习3（P116） 七、压缩软件
[问题描述]
用哈夫曼编码设计一个压缩软件,能对输入的任何类型的文件进行哈夫曼编码,产生编码后的文件-压缩文件;也能对输入的压缩文件进行译码,生成压缩前的文件----解压文件。 [设计要求]
要求编码/译码效率尽可能高。
八、校园导游咨询
[问题描述]
设计一个校园导游程序，为来访的客人提供各种信息查询服务。 [设计要求]
设计校园平面图，景点不少于10个；为来访客人提供任意景点的相关信息查询；为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
1、基本要求：
…… 此处隐藏1484字 ……
利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 [设计要求]：
1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。
3)如果采用4种或4种以上的方法者，可适当加分。
十五、树的应用
[问题描述]
实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。 [设计要求]
遍历的内容应是千姿百态的。