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天地上一只鹅追赶下蛋恨【实现提示】将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，

16、则逐一出栈,将字母依次入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简洁，请读者思索应如何处理。应首先实现栈和队列的基本操作。【选作内容】(1)由于问题的特别性，可以实现栈和队列的依次存储空间共享。(2)代换变量的数目不限，则在程序起先运行时首先读入一组第一种形式的规则，而不是把规则固定在程序中(其次种形式的规则只能固定在程序中)。169 .马踏棋盘【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。【基本要求】将马随机放在国际象棋的8x8棋盘Board88的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走

17、路途，并按求出的行走路途，将数字1,2,，64依次填入一个8x8的方阵，输出之。170 .算术表达式求值演示【问题描述】表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。【基本要求】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3-1演示在求值中运算符械、运算数校、输入字符和主要操作的变更过程。171 .银行业务模拟【问题描述】客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。其次种是向银行投入一笔资金

18、，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，假如属于第一种，且申请额超出银行现存资金总额而得不到满意，则马上排入其次个队等候，直至满意时才离开银行；否则业务处理完后马上离开银行。每接待完一个其次种业务的客户，则依次检查和处理（假如可能）其次个队列中的客户，对能满意的申请者予以满意，不能满意者重新排到其次个队列的队尾。留意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最终一个客户（其次种业务）被接待之前的数额，或者本次已将其次个队列检查或处理了一遍，就停止检查（因为此时已不行能还有能满意者）转而接着接待第一个队列的客户。任何

19、时刻都只开一个窗口。假设检查不须要时间。营业时间结束时全部客户马上离开银行。写一个上述银行业务的事务驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。【基本要求】利用动态存储结构实现模拟。【测试数据】一天营业起先时银行拥有的款额为10000（元），营业时间为600（分钟）。其他模拟参量自定，留意测定两种极端的状况：一是两个到达事务之间的间隔时间很短，而客户的交易时间很长，另一个恰好相反，设置两个到达事务的间隔时间很长，而客户的交易时间很短。【实现提示】事务有两类：到达银行和离开银行。初始时银行现存资金总额为total。起先营业后的第一今事务是客户到达，营业时间从。到Ck）Setime。

20、到达事务发生时随机地设置此客户的交易时间和距下一到达事务之间的时间间隔。每个客户要办理的款额也是随机确定的，用负值和正值分别表示第一类和其次类业务。变量total,closetime以及上述两个随机量的上下界均交互地从终端读入，作为模拟参数。两个队列和一个事务表均要用动态存储结构实现。留意弄清应当在什么条件下设置离开事务，以及其次个队列用怎样的存储结构实现时可以获得较高的效率。留意：事务表是按时间依次有序的。【选作内容】自己实现动态数据类型。例如对于客户结点，定义Pool为CustNodepoolfMAX；/结构类型CUStNOde含四个域：aITHIne,durtime,amount,nex

21、t或者定义四个同样长的，以上述域名为名字的数组。初始时，将全部重量的next域链接起来，形成一个静态链找，设置一个楼顶元素下标指示量top,top=0表示找空。动态存储安排函数可以取名为myMalloc,其作用是出钱，将钱顶元素的下标返回。若返回的值为0,则表示无空间可安排。归还函数可取名为myFree,其作用是把该重量入钱。用FOR-TRAN和BASIC等语言实现时只能如此地自行组织。172 .航空客运订票系统【问题描述】航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。【基本要求】(1)每条航线所涉及的信息有：终点站名

22、、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名单(包括姓名、订票量、舱位等级1,2或3)以及等候替补的客户名单(包括姓名、所需票量)；(2)系统能实现的操作和功能如下：录入：可以录入航班状况，全部数据可以只放在内存中，最好存储在文件中,查询航线：依据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；承办订票业务：依据客户提出的要求(航班号、订票数额)查询该航班票额状况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若须要，可登记排队候补；承办退票业务：依据客户供应的状况(日期、航班)

23、，为客户办理退票手续,然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满意他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。【测试数据】由读者自行指定。【实现提示】两个客户名单可分别由线性表和队列实现。为查找便利，己订票客户的线性表应按客户姓名有序，并且，为插入和删除便利，应以链表作存储结构。由于预约人数无法预料，队列也应以链表作存储结构。整个系统需汇总各条航线的状况登录在一张线性表上，由于航线基本不变，可采纳依次存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为

24、分别指向队头和队尾的指针。【选作内容】当客户订票要求不能满意时，系统可向客户供应到达同一目的地的其他航线状况。读者还可充分发挥自己的想象力，增加你的系统的功能和其他服务项目。173.电梯模拟【问题描述】设计一个电梯模拟系统。这是一个离散的模拟程序，因为电梯系统是乘客和电梯等”活动体”构成的集合，虽然他们彼此交互作用，但他们的行为是基本独立的。在离散的模拟中，以模拟时钟确定每个活动体的动作发生的时刻和依次，系统在某个模拟瞬间处理有待完成的各种事情，然后把模拟时钟推动到某个动作预定要发生的下一个时刻。【基本要求】(1)模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层由下至上

25、依次称为地下层、第-层、其次层、第三层和第四层，其中第一层是大楼的迸出层，即是电梯的“本垒层”，电梯”空闲”时，将来到该层候命。(2)乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。(3)模拟时钟从O起先，时间单位为0.1秒。人和电梯的各种动作均要耗费肯定的时间单位（简记为t）,比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各须要20tg每个人进出电梯均须要25h假如电梯在某层静止时间超过300t,则驶回1层候命。（4）按时序显示系统状态的变更过程：发生的全部人和电梯的动作序列。【测试数据】模拟时钟Time的初值为

26、0,终值可在500-10000范围内逐步增加。【实现提示】（1）楼层由下至上依次编号为0,1,2,3,4。每层有要求Up（上）和DOWn（下）的两个按钮，对应10个变量CaliUP0.4和CallDOWEI0.4o电梯内5个目标层按钮对应变量CaUCar0.4。有人按下某个按钮时，相应的变量就置为1,一旦要求满意后，电梯就把该变量清为0。（2）电梯处于三种状态之-ZGOingUP（上行）、GOingDoWn（下行）和IdIe（停候）。假如电梯处于Idle状态且不在1层，则关门并驶回1层。在1层停候时，电梯是闭门候命。一旦收到往另一层的吩咐，就转入GOingUP或GOingDOWn状态，执行相应

27、的操作。（3）用变量Time表示模拟时钟，初值为0,时间单位。）为0。1秒。其他重要的变量有：Floor电梯的当前位置（楼层）；DI一一值为0,除非人们正在进入和离开电梯；D2一一值为0,假如电梯已经在某层停候30Ot以上；D3一一值为0,除非电梯门正开着又无人迸出电梯；State电梯的当前状态（GoingUp,GoingDOWEl,Idle）o系统初始时，FIoor=I,Dl=D2=D3=0,State=Idleo（4）每个人从进入系统到离开称为该人在系统中的存在周期。在此周期内，他有6种可能发生的动作：Ml.进入系统，为下一人的出现作打算产生以下数值：InFloor一一该人进入哪层楼；Ol

28、ltFIoor他要去哪层楼；GiveupTime他能容忍的等候时间；Inter-Time一一下一人出现的时间间隔，据此系统预置下一人进入系统的时刻。M2.按电钮并等候此时应对以下不同状况作不同的处理：FIoor=InFlOor且电梯的下一个活动是E6（电梯在本层，但正在关门；F100r=InFIOor且D3手0（电梯在本层，正有人迸出）；其他状况，可能D2=0或电梯处于活动El（在1层停候）。M3.进入排队在等候队列QUeUeunFlOoIl末尾插入该人，并预置在GiveupTime个t之后，他若仍在队列中将实施动作M4。M4.放弃假如Floor手InFloor或Dl=O,则从QUemInFl

29、oor和系统删除该人。假如FlOor=InFIoor且Dl学0,他就接着等候（他知道立刻就可进入电梯。M5.进入电梯从QUeUeInFloor）删除该人，并把他插入到IEleVator（电梯）校中。置Cancar011tFloor为IoM6.离去从Elevator和系统删除该人。(5)电梯的活动有9种：EL在1层停候若有人按下一个按钮，则调用ContrOler将电梯转入活动E3或E60。E2.要变更状态?假如电梯处于GoingUP(或GoingDOwn状态，但该方向的楼层却无人等待，则要看反方向楼层是否有人等候，而确定置State为GOingDOWn(或GoingUp)还是IdleoE3.开门

30、置DI和D2为非0值，预置300个t后启动活动E9和76个t后启动E5,然后预置20个t后转到目。E4.让人出入假如EleVatOr不空且有人的OlItFk)Or=Fk)or,则按进入的倒序每隔25个t让这类人马上转到他们的动作M6。Elevator中不再有要离开的人时，假如QUeUeFloor不空，则以25个t的速度让他们依次转到MLQueueFloor空时，置DI为O,D3手0,而且等候某个其他活动的到来。E5.关门每隔40个t检查DL直到是DI=O(若Dl手0,则仍有人出入。置D3为0并预置电梯再20个t后启动活动E6(再关门期间，若有人到来，则如M2所述，门再次打开)。E6.打算移动置

31、CaUCarFloor为0,而且若State手GoingDown,则置CalIUPCFIooH为05若State手GoingUp,则置CalIDoWnCFIOor为Oo调用Controler函数。假如State=Idle,则即使已经执行了ContrO也转到EL否则,假如D2手0,则取消电梯活动E9。最终，假如State=GoingUp,则预置15个t后(电梯加速转到E7；假如State=GOingDOwn,则预置15个t后(电梯加速)转到E8。E7.上升一层置Floor加1并等候51个人假如现在CaucarfFIoor)=1或CallUpfFloor=1,或者假如(FIoOr=I或CalIDO

32、WElFloor=1)且CallUpj=CallDOWEIj=Ca11Car-0=0对于全部jFloor),则预置14个t后(减速)转到E2；否则重复E7。E8.下降一层除了方向相反之外，与E7类似，但那里的51和14个3此时分别改为61和23个t(电梯下降比上升慢)。E9.置不活动指示器置D2为0并调用Controler函数(E9是由E3预置的，但几乎总是被E6取消了训I。(6)当电梯须对下一个方向作出判定时，便在若干临界时刻调用Controler函数。该函数有以下要点：CL须要推断?若State手Idle,则返回。C2.应当开门?假如电梯处于El且CallUpll,CallDownl或Ca

33、UCar1非0,则预置20个t后启动E3,并返回。C3.有按钮按下?找最小的j手FlOor,使得CallUpIj,CallDOWEl(jgCaucarj0,并转到C4。但假如不存在这样的j,那么，假如Controler正为E6所调用，则置j为1,否则返回。C4.置State假如Fkrj,则置State为GOingDOWE1；假如F100rVj,则置State为GoingUpoC5.电梯静止?假如电梯处于El而且j手1,则预置20个t后启动E6。返回。(7)由上可见，关键是按时序管理系统中全部乘客和电梯的动作设计合适的数据结构。【选作内容】(1)增加电梯数量，模拟多梯系统。(2)某高校的一座30

34、层住宅楼有三部自动电梯，每梯最多载客15人。大楼每层8户，每户平均3。5人，每天早晨平均每户有3人必需在7时之前离开大楼去上班或上学。模拟该电梯系统，并分析分别在一梯、二梯和三梯运行状况下，下楼高峰期间各层的住户应提前多少时间候梯下楼?探讨多梯运行最佳策略。174.迷宫问题【问题描述】以一个mn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对随意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中：(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷

35、宫，输出的一条通路为z(l,1,1),(1,2,2),(2,2,2),(3,2,3),(3,1,2),-O【测试数据】迷宫的测试数据如下：左上角(1,1)为入口，右下角(8,9)为出口。12345678001000100010001000001101011100100001000001000101011110011100010111000000【实现提示】计算机解迷宫通常用的是“穷举求解”方法，即从人口动身，顺着某一个方向进行探究，若能走通，则接着往前进；否则沿着原路退回，换一个方向接着探究,直至出口位置，求得一条通路。假如全部可能的通路都探究到而未能到达出口，则所设定的迷宫没有通路。可以二维

36、数组存储迷宫数据，通常设定入口点的下标为(1,1),出口点的下标为(n,n)。为处理便利起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。【选作内容】(1)编写递归形式的算法，求得迷宫中全部可能的通路；(2)以方阵形式输出迷宫及其通路。ch3串及其应用本实习单元的目的是熟识串类型的实现方法和文本模式匹配方法,熟识一般文字处理软件的设计方法,较困难问题的分解求精方法。本实习单元的难度较大,在教学支配上可以敏捷驾驭完成此单元实习的时间。编程技术训练要点：并行的模式匹配技术(3.1);字符填充技术(3.2,3.4);逻辑/物理概念隔离技术(GetAWord,3

37、.2);活区操作技术3);不定长对象的成块存储安排技术3);吩咐识别与分析技术3,3.4);串的动态组织技术(3.4);合理有效的错误处理方法(3.4);程序语法结构基本分析技术(3.5).175.文学探讨助手【问题描述】文学探讨人员须要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统,称为文学探讨助手。【基本要求】英文小说存于一个文本文件中。待统计的词汇合合要一次输入完毕,即统计工作必需在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。【测试数据】以你的C源程序模拟英文小说,c语言的保留字集作为待统计的词汇合

38、。【实现提示】约定小说中的词汇一律不跨行。这样,每读入一行,就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次,不必存多个相同的行号。假如读者希望达到选做部分(1)和(2)所提出的要求,则首先应把KMP算法改写成如下的等价形式,再将它推广到多个模式的情形。i=l;j=l；while(i!=s.curlen+l&j!=t.CUrIerI十1)(while(j!=0&s.chi!=t.chj)j=nextj;/j=0s.chi=t.chjj+；i+；每次进入循环体，i只增加一次)【选作内容】(1)模式匹配要基于KMP算法。(2)整个统计过程中只对小说文字扫描

39、一遍以提高效率。(3)假设小说中的每个单词或者从行首起先,或者前置一个空格符。利用单词匹配特点另写一个高效的统计程序,与KMP算法统计程序进行效率比较。(4)推广到更一般的模式集匹配问题,并设待查模式串可以跨行(提示:定义操作GetAChar)O176.文本格式化【问题描述】输入文件中含有待格式化或称为待排版的文本,它由多行的文字组成，例如一篇英文文章。每一行由一系列被一个或多个空格符所隔开的字组成，任何完整的字都没有被分割在两行(每行最终一个字与下一行的第一个字之间在逻辑上应当由空格分开)，每行字符数不超过80。除了上述文本类字符之外，还存在着起限制作用的字符:符号矿指示它后面的正文在格式化

40、时应另起一段排放,即空一行,并在段首缩入8个字符位置。自成一个字。一个文本格式化程序可以处理上述输入文件,依据用户指定的版面规格重排版面Z实现页内调整、分段、分页等文本处理功能,排版结果存入输出文本文件中。试写一个这样的程序。【基本要求】(1)输出文件中字与字之间只留一个空格符,即实现多余空格符的压缩。(2)在输出文件中,任何完整的字仍不能分割在两行,行尾不齐没关系,但行首要对齐(即左对齐)。(3)假如所要求的每页页底所空行数不少于3,则将页号印在页底空行中第2行的中间位置上,否则不印。(4)版面要求的参数要包含：页长(PageLength)每页内文字(不计页号)的行数。页宽(PageWedt

41、h)一一每行内文字所占最大字符数。左空白(LeftMargin)(每行文字前的固定空格数。头长(HeadingLength)每页页顶所空行数。脚长(FOotingLength)一每页页底所空行数(含页号行)。起始页号(StartingPageNumber)首页的页号。【测试数据】略。留意在标点之后加上空格符。【实现提示】可以设:左空白数X2+页宽*160,即行印机最大行宽,从而只要设置这样大的一个行缓冲区就足够了，每加工完一行,就输出一行。假如输入文件和输出文件不是由程序规定死,而是可由用户指定,则有两种做法:一是像其他参量一样,将文件名交互地读入字符串变量中；更好的方式是让用户通过吩咐行指定

42、,具体做法依机器的操作系统而定。应当首先实现GetAWOrd(v)这一操作,把诸如行尾处理、文件尾处理、多余空格符压缩等一系列低级事务留给它处理,使系统的核心部分集中应付排版要求。每个参数都可以实现缺省值设置。上述排版参数的缺省值可以分别取56,60,10,5,5和1。【选作内容】(1)输入文件名和输出文件名要由用户指定。(2)允许用户指定是否右对齐,即增加一个参量右对齐否,z(RightJustifying),缺省值可设为y(yes)。右对齐指每行最终一个字的字尾要对齐,多余的空格要匀称分布在本行中各字之间。(3)实现字符填充(CharaCterStUffing)技术。作为分段限制符之后，限

43、制了原文中不能有这样的字。现在去掉这一限制:假如原文中有这样的字,改用两个并列起来表示一个字。当然,假如原文中此符号夹在字中，就不必特别处理了。(4)允许用户自动按多栏印出一页。177.简洁行编辑程序【问题描述】文本编辑程序是利用计算机进行文字加工的基本软件工具,实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。被编辑的文本文件可能很大,全部读入编辑程序的数据空间(内存)的作法既不经济,也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存,称为活区。试依据这种方法实现一个简洁的行编辑程序。设文件每行不超过320个字符,很少超过80

44、个字符。【基本要求】实现以下4条基本编辑吩咐：(1)行插入。格式:i行号X回车X文本.回车将文本插入活区中第行号行之后。(2)行删除。格式:d行号Dk空格行号2回车删除活区中第行号1行(到第行号2行)。例如:diO和dl014.(3)活区切换。格式M回车将活区写入输出文件,并从输入文件中读入下一段,作为新的活区。(4)活区显示。格式:p回车逐页地(每页20行)显示活区内容,每显示一页之后请用户确定是否接着显示以后备页(假如存在)。印出的每一行要前置行号和一个空格符，行号固定占4位,增量为1。各条吩咐中的行号均须在活区中各行行号范围之内，只有插入吩咐的行号可以等于活区第一行行号减1,表示插入当前

45、屏幕中第一行之前，否则吩咐参数非法。【测试数据】自行设定，留意测试将活区删空等特别状况。【实现提示】(1)设活区的大小用行数ACtiVeMULen(可设为Ioo)来描述。考虑到文本文件行长通常为正态分布,且峰值在60到70之间,用320XACtiVeMULen大小的字符数组实现存储将造成大量奢侈。可以以标准行块为单位为各行安排存储,每个标准行块可含81个字符。这些行块可以组成一个数组,也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特别的ASCIl字符(如(012)8)标识。此外,还应记住活区起始行号。行插入将引起随后各行行号的依次下推。(2)初始化函数包括:请用户供应输入文件

46、名(空串表示无输入文件)和输出文件名，两者不能相同。然后尽可能多地从输入文件中读入各行,但不超过ACtiVeMULen-LX的值可以自定，例如20。(3)在执行行插入吩咐的过程中，每接收到一行时都要检查活区大小是否已达ACtiVeMaXLen。假如是,则为了在插入这一行之后仍保持活区大小不超过ACtiveMaXLen应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前,则只得将新插入的这一行输出。(4)若输入文件尚未读完,活区切换吩咐可将原活区中最终几行留在活区顶部，以保持阅读连续性;否则,它意味着结束编辑或起先编辑另一个文件。(5)可令前三条吩咐执行后自动调用活区显示。【选作内容】(1)对于吩咐格式非法等一切错误作严格检查和适当处理。(2)加入更困难的编辑操作,如对某行进行串替换；在活区内进行模式匹配等，格式可以为S行