2017年数据结构课程设计题目及报告范例
1.
运动会分数统计
【问题描述】
参加运动会的n个学校编号为1?n。比赛分成m个男子项目和w个女子项目，项目编号分别为1?m和m+1?m+wo由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。
【基本要求】
1) 可以输入各个项目的前三名或前五名的成绩；
2) 能统计各学校总分，
3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；
4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学
校。
5) 数据存入文件并能随时查询
6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文
提示，各学校分数为整型。
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。
测试数据：
【测试数据】
要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。
例如，对于n=4，m=3，w =2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。
【实现提示】
可以假设n w 20, m w 30, w< 20,姓名长度不超过20个字符。每个项目结束时，将其编号、类型符(区分取前五名还是前三名) 输入，并按名次顺序输入运动员姓名、校名(和成绩)。
【选作内容】
允许用户指定某项目采取其他名次取法
2. 集合的并、交和差运算
问题描述】
编制一个能演示执行集合的并、交和差运算的程序。
基本要求】
(1) 集合的元素限定为小写字母字符[ ‘a'.. 'z' ]。
(2) 演示程序以用户和计算机的对话方式执行。
测试数据】
(1) Set1="magazine", Set2="paper",
Setl u Set2="aegimnprz", Setl n Set2="ae", Set1-Set2="gimnz"。
(2) Set1= " 012oper4a6tion89", Set2="error data",
Set1 u Set2="adeinoprt", Setl n Set2="aeort", Set1-Set2="inp"。实现提示】以有序链表表示集合。
【选作内容】
(1) 集合的元素判定和子集判定运算。
(2) 求集合的补集。
(3) 集合的混合运算表达式求值。
(4) 集合的元素类型推广到其他类型 , 甚至任意类型。
3. 一元稀疏多项式计算器
【问题描述】
设计一个一元稀疏多项式简单计算器
【基本要求】
元稀疏多项式简单计算器的基本功能是：
(1) 输入并建立多项式；
(2) 输出多项式，输出形式为整数序列：n, c i, e , C2, e2,…，c n, e n,其
中n是多项式的项数，c i和e,分别是第i项的系数和指数，序列按指数降序排列；
(3) 多项式a和b相加，建立多项式a +b；
(4) 多项式a和b相减，建立多项式a -b 。
【测试数据】
(1) (2x+5x8－3.1x11) + (7－5x8+11x9)=(－3.lx11+11x9+2x+7)
(2) (6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15)
=(-7.8x15-1.2x9+12x-3-x)
(3) (1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5)
(4) (x+x3)+(-x－x3)=0
(5) (x+x100)+(x100 +x200)=(x+2x100+x200)
(6) (x+x2+x3)+0=x+x 2+x3
(7) 互换上述测试数据中的前后两个多项式
【实现提示】用带表头结点的单链表存储多项式。
【选作内容】
(1) 计算多项式在x处的值。
(2) 求多项式a 的导函数a 。
(3) 多项式a和b相乘，建立乘积多项式
ab 。
(4) 多项式的输出形式为类数学表达式。例如，多项式-3x8+6x3－18 的输出形式为
3x 8 6x 3 18，x15+(-8)x7—14的输出形式为x 15 8x 7 14。注意，数
值为1的非零次项的输出形式中略去系数1,如项1x8的输出形式为x8,项一1x3 的输出形式为—x3。
(5) 计算器的仿真界。
4. 池塘夜降彩色雨
【问题描述】设计一个程序，演示美丽的“池塘夜雨”景色：色彩缤纷的雨点飘飘洒洒地从天而降，滴滴入水有声，溅起圈圈微澜。
【基本要求】
(1) 雨点的空中出现位置、降范过程的可见程度、入水位置、颜色、最大水圈等，都是随机确定的；
(2) 多个雨点按照各自的随机参数和存在状态，同时演示在屏幕上。
【测试数据】适当调整控制雨点密度、最大水圈和状态变化的时间间隔等参数。
【实现提示】
(1) 每个雨点的存在周期可分为三个阶段：从天而降、入水有声和圈圈微澜，曲: *
需要一个记录存储其相关参数、当前状态和下一状态的更新时刻。
(2) 在图形状态编程。雨点下降的可见程度应是断断续续、依稀可见；圈圈水波应是
由里至外逐渐扩大和消失。
(3) 每个雨点发生时，生成其记录，并预置下一个雨点的发生时间。
(4) 用一个适当的结构管理当前存在的雨点，使系统能利用它按时更新每个雨点的状态，一旦有雨点的水圈全部消失，就从结构中删去。
【选作内容】
(1) 增加“电闪雷鸣”景象。
(2) 增加风的效果，展现“风雨飘摇”的情景。
(3) 增加雨点密度的变化：时而“和风细雨”，时而“暴风骤雨”。
(4) 将“池塘”改为“荷塘”，雨点滴在荷叶上的效果是溅起四散的水珠，
响声也不同。
5. 银行业务模拟
【问题描述】
客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第二个队等候，直至满足时才离开银行；否则业务处理完后立刻离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列中的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为
此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假
设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。
【基本要求】
利用动态存储结构实现模拟。
【测试数据】
一天营业开始时银行拥有的款额为10000（元），营业时间为600（分钟）。其他模拟参量自定，注意测定两种极端的情况：一是两个到达事件之间的间隔时间很短，而客户的交易时间很长，另一个恰好相反，设置两个到达事件的间隔时间很长，而客户的交易时间很短。
【实现提示】
事件有两类：到达银行和离开银行。初始时银行现存资金总额为total。开始营业后的第一今事件是客户到达，营业时间从0到closetime。到达事件发生时随机地设置此客户的交易时间和距下一到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的，用负值和正值分别表示第一类和第二类业务。变量total，closetime以及上述两个随机量的上下界均交互地从
终端读入，作为模拟参数。
两个队列和一个事件表均要用动态存储结构实现。注意弄清应该在什么条件下设置离开事件，以及第二个队列用怎样的存储结构实现时可以获得较高的效率。注意：事件表是按时间顺序有序的。
【选作内容】
自己实现动态数据类型。例如对于客户结点，定义pool 为
CustNodepoolfMAX] ；
// 结构类型CustNode 含四个域：aITHIne，durtime，amount，next 或者定义四个同样长的，以上述域名为名字的数组。初始时，将所有分量的next 域链接起来，形成一个静态链找，设置一个楼顶元素下标指示量top，top=0 表
示找空。动态存储分配函数可以取名为myMalloc ，其作用是出钱，将钱顶元素的下标返回。若返回的值为0，则表示无空间可分配。归还函数可取名为myFree，其作用是把该分量入钱。用FOR-TRAN 和BASIC 等语言实现时只能如此地自行组织。
6. 马踏棋盘
【问题描述】
设计一个国际象棋的马踏遍棋盘的演示程序。
【基本要求】
将马随机放在国际象棋的8$棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1, 2,…，64依次填入一个8>8的方阵，输出之。
7. 魔王语言解释
【问题描述】
有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能昕得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
⑴ 1 2 m
(2
) ( 1 2 n) n n 1 1
在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。
【基本要求】
用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。
(1) B tAdA
(2) A sae
【测试数据】
B(ehnxgz)B 解释成tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。
【实现提示】
将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈, 将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。
【选作内容】
(1) 由于问题的特殊性，可以实现栈和队列的顺序存储空间共享。
(2) 代换变量的数目不限，则在程序开始运行时首先读入一组第一种形式的规则，而不是把规则固定在程序中(第二种形式的规则只能固定在程序中)。