2024级数据结构课程设计任务书.docx

《2024级数据结构课程设计任务书.docx》由会员分享，可在线阅读，更多相关《2024级数据结构课程设计任务书.docx（26页珍藏版）》请在优知文库上搜索。

1、161.运动会分数统计【问题描述】参与运动会的Fl个学校编号为1仄竞赛分成外男子项目和H个女子项目，项目编号分别为1/和研1研队由于各项目参与人数差别较大，有些项目取前五名，得分依次为7,5,3,2,1；还有些项目只取前三名，得分依次为5,3,2o写一个统计程序产生各种成果单和得分报表。基本要求D可以输入各个项目的前三名或前五名的成果；2）能统计各学校总分，3）可以按学校编号或名称、学校总分、男女团体总分排序输出；4）可以按学校编号查询学校某个项目的状况；可以按项目编号查询取得前三或前五名的学校。5）数据存入文件并能随时查询6）规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形

2、式：有中文提示，各学校分数为整型。界面要求：有合理的提示，每个功能可以设立菜单，依据提示，可以完成相关的功能要求。存储结构：学生自己依据系统功能要求自己设计;但是要求运动会的相关数据要存储在数据文件中。测试数据：【测试数据】要求运用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。例如，对于=4,m=3fw=2f编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。【实现提示】可以假设W20,w30,vv20,姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次依次输入运动员姓名、校名（和成绩）。

3、【选作内容】允许用户指定某项目实行其他名次取法。162.约瑟夫环【问题描述】约瑟夫（JOSePh）问题的一种描述是：编号为1,2,.,n的个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一起先任选一个正整数作为报数上限值加，从第一个人起先按顺时针方向自1起先依次报数，报到加时停止报数。报机的人出列，将他的密码作为新的加值，从他在顺时针方向上的下一个人起先重新从1报数，如此下去，直至全部人全部出列为止。试设计一个程序求出出列依次。【基本要求】利用单向循环链表存储结构模拟此过程，依据出列的依次印出各人的编号。【测试数据】m的初值为20；二7,7个人的密码依次为：3,1,7,2,4,8,4,首

4、先m值为6(正确的出列依次应为6,1,4,7,2,3,5)。【实现提示】程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设W30。此题所用的循环链表中不须要“头结点”，请留意空表和非空表的界限。【选作内容】向上述程序中添加在依次结构上实现的部分。164 .长整数四则运算【问题描述】设计一个实现随意长的整数进行加法运算的演示程序。【基本要求】利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是一5(2凡1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。【测试数据】(1)0；0；应输出“0”。(2)-2345,6789；765

5、4,3211；应输出,-l,0000,0000o(3)-9999,9999；1,0000,0000,0000；应输出9999,0000,000,o(4) 1,0001,0001；-I,0001,0001；应输出“0。(5) 1,0001,OOOh-1,0001,0000；应输出“1。(6) -9999,9999,9999；9999,9999,9999；应输出,-l,9999,9999,9998”。(7)1,0000,9999,9999；1；应输出1,0001,0000,0000,o【实现提示】(1)每个结点中可以存放的最大整数为2,5-l=32767,才能保证两数相加不会溢出。但若这样存放，即

6、相当于按32768进制数存放，在十进制数与32768进制数之间的转换特别不便利。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。(2)可以利用头结点数据域的符号代表长整数的符号。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。【选作内容】(1)实现长整数的四则运算；(2)实现长整数的乘方和阶乘运算；(3)整型量范围是一(2-1)(2-1),其中，是由程序读人的参量。输入数据的分组方法可以另行规定。(165) 一元稀疏多项式计算器【问题描述】设计一个一元稀疏多项式简洁计算器。【基本要求】一元稀疏多项式简洁计算器的基本功能是：(1)输入并建立多

7、项式；(2)输出多项式，输出形式为整数序列：，ci,e,C2,e2,，ew,其中是多项式的项数，加和的分别是第i项的系数和指数，序列按指数降序排列；(3)多项式和b相加，建立多项式。+6(4)多项式。和b相减，建立多项式。功O【测试数据】(1)(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x,1+11x9+2x+7)(2)(6x3-x+4.4x2-1.2x9)(-6x-3+5.4x2-x2+7.8x,5)=(-7.8x,5-1.2x9+12x-3-x)(3)(1+x+x2+x3+x4+x5)+(-x3x4)=(1+x+x2+x5)(4)(x+x3)+(-xx3)=0(5)

8、(x+xl00)+(x10+x200)=(x+2x,00+x200)(6)(x+x2+x3)+0=x+x2+x3(7)互换上述测试数据中的前后两个多项式【实现提示】用带表头结点的单链表存储多项式。【选作内容】(1)计算多项式在X处的值。(2)求多项式a的导函数#。(3)多项式a和b相乘，建立乘积多项式abQ(4)多项式的输出形式为类数学表达式。例如，多项式-3x8+6x3-18的输出形式为-3x8+6x3-18,*15+(8*14的输出形式为/15-8炉7-14。留意，数值为1的非零次项的输出形式中略去系数1，如项l8的输出形式为8,项一l3的输出形式为一30(5)计算器的仿真界。166 .池

9、塘夜降彩色雨【问题描述】设计一个程序，演示漂亮的“池塘夜雨”景色：色调缤纷的雨点飘飘洒洒地从天而降，滴滴入水有声，溅起圈圈微澜。【基本要求】(1)雨点的空中出现位置、降范过程的可见程度、入水位置、颜色、最大水圈等，都是随机确定的；(2)多个雨点依据各自的随机参数和存在状态，同时演示在屏幕上。【测试数据】适当调整限制雨点密度、最大水圈和状态变更的时间间隔等参数。【实现提示】(1)每个雨点的存在周期可分为三个阶段：从天而降、入水有声和圈圈微澜，须要一个记录存储其相关参数、当前状态和下一状态的更新时刻。(2)在图形态态编程。雨点下降的可见程度应是断断续续、依稀可见；圈圈水波应是由里至外渐渐扩大和消逝

10、。(3)每个雨点发生时，生成其记录，并预置下一个雨点的发生时间。(4)用一个适当的结构管理当前存在的雨点，使系统能利用它按时更新每个雨点的状态，一旦有雨点的水圈全部消逝，就从结构中删去。【选作内容】(1)增加“电闪雷鸣”景象。(2)增加风的效果，呈现“风雨飘摇”的情景。(3)增加雨点密度的变更：时而“和风细雨”，时而“暴风骤雨”。(4)将“池塘”改为“荷塘”，雨点滴在荷叶上的效果是溅起四散的水珠，响声也不同ch2栈和队列及其应用仅仅相识到栈和队列是两种特别的线性表是远远不够的，本次实习的目的在于使读者深化了解钱和队列的特性，以便在实际问题背景下敏捷运用他们；同时还将巩固对这两种结构的构造方法的

11、理解。编程技术训练要点有：基本的“任务书”观点及其典型用法(见本实习2o2)；问题求解的状态表示及其递归算法(2.3,2.4和2.9)；利用栈实现表达式求值的技术(2.5)；事务驱动的模拟方法(2.63.8)；以及动态数据结构的实现(2.6,2.7和2.8)。167 .停车场管理问题描述设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后依次，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开

12、时，在它之后开入的车辆必需先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必需按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。测试数据设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),(4E,0,0).每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，A表示到达；D，表示离去，E表示输入结束。基本要求以栈模拟停车场，以队列模拟车场外的便道，依据从终端读入的输入

13、数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以依次结构实现，队列以链表实现。实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用依次存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。选作内容(1)两个栈共享空间，思索应开拓数组的空间是多少？(2)汽车可

14、有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆卜轮卡车占地面积相当于3辆小汽车的占地面积。(3)汽车可以干脆从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。(4)停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思索如何修改结构以满意这种要求。168 .魔王语言说明【问题描述】有一个魔王总是运用自己的一种特别精练而抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步说明成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：(1) a2-m(电24)维绍E电夕在这两种形式中，从左到右均表示说明。

15、试写一个魔王语言的说明系统，把他的话说明成人能听得懂的话。【基本要求】用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。(1) BtAdA(2) Asae【测试数据】B(ehnxgz)B说明成tsaedsaeezegexenehetsaedsae若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。tdSaeZgXnh天地上一只鹅追赶下蛋恨【实现提示】将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈,将字母依次入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简洁，请读者思索应如何处理。应首先实现栈和队列的基本操作。【选作内容】(1)由于问题的特别性，可以实现栈和队列的依次