ch1 线性表及其应用
本次实习的主要目的在于帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用作为重点内容。
161. 运动会分数统计
【问题描述】
参加运动会的n个学校编号为1～n。比赛分成m个男子项目和w个女子项目，项目编号分别为1～m和m+1～m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】
1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各学校总分，
3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；
4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前
三或前五名的学校。
5) 数据存入文件并能随时查询
6) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整型。
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。
测试数据： 【测试数据】
要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。
例如，对于n=4，m=3，w =2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】
可以假设n≤20，m≤30，w≤20，姓名长度不超过 20 个字符。每个项目结束时，将其 编号、类型符(区分取前五名还是前三名) 输入，并按名次顺序输入运动员姓名、校名(和成 绩)。 【选作内容】
允许用户指定某项目采取其他名次取法。
162. 约瑟夫环
【问题描述】
约瑟夫 (Joseph) 问题的一种描述是：编号为 1，2，… ，n 的n个人按顺时针方向围坐一 圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
【测试数据】 m 的初值为 20；n=7，7 个人的密码依次为：3，1，7，2，4，8，4， 首先 m 值为 6( 正确的出列顺序应为 6，1，4，7，2，3，5) 。 【实现提示】
程序运行后，首先要求用户指定初始报数上限值，然后读取各人的密码。可设n≤30。 此题所用的循环链表中不需要 “头结点”，请注意空表和非空表的界限。
【选作内容】
向上述程序中添加在顺序结构上实现的部分。
164. 长整数四则运算
【问题描述】 设计一个实现任意长的整数进行加法运算的演示程序。
【基本要求】
利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范 围是－(215-l)~(215-1) 。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 【测试数据】
(1) 0；0； 应输出 \。
(2)－2345，6789； －7654，3211； 应输出 \－1，0000，0000\。
(3)－9999，9999；1，0000，0000，0000； 应输出 \，0000，0001\。 (4) 1，0001，0001；－1，0001，0001； 应输出 \。 (5) 1，0001，0001；－1，0001，0000； 应输出 \。
(6) -9999，9999，9999；－9999，9999，9999；应输出 \－1，9999，9999，9998\。 (7) 1，0000，9999，9999；1； 应输出 \，0001，0000，0000 \。 【实现提示】
(1) 每个结点中可以存放的最大整数为 215-1=32767， 才能保证两数相加不会溢出。但若这样存放，即相当于按32768进制数存放，在十进制数与32768进制数之间的转换十分不方便。故可以在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。
(2) 可以利用头结点数据域的符号代表长整数的符号。相加过程中不要破坏两个操作数链表。不能给长整数位数规定上限。 【选作内容】
(1) 实现长整数的四则运算；
(2) 实现长整数的乘方和阶乘运算；
(3) 整型量范围是－ (2n－1) ~ (2n－1)， 其中，n是由程序读人的参量。输入数据的分
组方法可以另行规定。
165. 一元稀疏多项式计算器
【问题描述】 设计一个一元稀疏多项式简单计算器。
【基本要求】
一元稀疏多项式简单计算器的基本功能是： (1) 输入并建立多项式 ；
(2) 输出多项式，输出形式为整数序列：n，cl，el，c2，e2，…，cn，en，其中n是多项式的项数，ci 和ei，分别是第 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+x2+x3
(7) 互换上述测试数据中的前后两个多项式 【实现提示】 用带表头结点的单链表存储多项式。 【选作内容】
(1) 计算多项式在x处的值。 (2) 求多项式 a 的导函数a? 。
(3) 多项式a和b相乘，建立乘积多项式ab 。
(4) 多项式的输出形式为类数学表达式。例如 ，多项式 -3x8+6x3－18 的输出形式为
157?????3x8?6x3?18，x+(－8)x－14的输出形式为x15?8x7?14。注意，数值为1的非零次项的输出形式中略去系数1，如项1x8的输出形式为x8，项 －1x3的输出形式为－x3。
(5) 计算器的仿真界。
166. 池塘夜降彩色雨
【问题描述】
设计一个程序，演示美丽的“池塘夜雨”景色：色彩缤纷的雨点飘飘洒洒地从天而降， 滴滴入水有声，溅起圈圈微澜。 【基本要求】 (1) 雨点的空中出现位置、降范过程的可见程度、入水位置、颜色、最大水圈等，都是随机确定的 ； (2) 多个雨点按照各自的随机参数和存在状态，同时演示在屏幕上。 【测试数据】 适当调整控制雨点密度、最大水圈和状态变化的时间间隔等参数。 【实现提示】 (1) 每个雨点的存在周期可分为三个阶段：从天而降、入水有声和圈圈微澜，需要一
个记录存储其相关参数、当前状态和下一状态的更新时刻。 (2) 在图形状态编程。雨点下降的可见程度应是断断续续、依稀可见；圈圈水波应是
由里至外逐渐扩大和消失。 (3) 每个雨点发生时，生成其记录，并预置下一个雨点的发生时间。
(4) 用一个适当的结构管理当前存在的雨点，使系统能利用它按时更新每个雨点的状态，一旦有雨点的水圈全部消失，就从结构中删去。 【选作内容】
(1) 增加“电闪雷鸣”景象。
(2) 增加风的效果，展现“风雨飘摇”的情景。
(3) 增加雨点密度的变化：时而“和风细雨”， 时而“暴风骤雨”。
(4) 将“池塘”改为“荷塘”，雨点滴在荷叶上的效果是溅起四散的水珠，响声也不同 ch2 栈和队列及其应用
仅仅认识到栈和队列是两种特殊的线性表是远远不够的，本次实习的目的在于使读者深入了解钱和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的理解。
编程技术训练要点有：基本的“任务书“观点及其典型用法(见本实习2。2)；问题求解的状态表示及其递归算法(2.3，2.4和2.9)；利用栈实现表达式求值的技术(2.5)；事件驱动的模拟方法(2.6 3.8)；以及动态数据结构的实现(2.6，2.7和2.8)。
167. 停车场管理
[问题描述]
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，
在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
[测试数据]
设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），（‘E’，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。
[基本要求]
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
[实现提示]
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
[选作内容]
（1） 两个栈共享空间，思考应开辟数组的空间是多少？
（2） 汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。
（3） 汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。
（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。
168. 魔王语言解释
【问题描述】
有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能昕得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
(1) (2)
???1?2??m
n?1(??1?2??n)???n?????1?
在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。 【基本要求】
用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。
(1) B?tAdA (2) A?sae
【测试数据】
B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae
若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。 t 天 d 地 s 上 a 一只 e 鹅 z 追 g 赶 x 下 n 蛋 h 恨 【实现提示】 将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。 【选作内容】
(1)由于问题的特殊性，可以实现栈和队列的顺序存储空间共享。
(2)代换变量的数目不限，则在程序开始运行时首先读入一组第一种形式的规则，而不是把规则固定在程序中(第二种形式的规则只能固定在程序中)。
169. 马踏棋盘
【问题描述】
设计一个国际象棋的马踏遍棋盘的演示程序。 【基本要求】
将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。
170. 算术表达式求值演示
【问题描述】
表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 【基本要求】
以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书表3.1给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例3-1演示在求值中运算符械、运算数校、输入字符和主要操作的变化过程。
171. 银行业务模拟
【问题描述】
客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第二个队等候，直至满足时才离开银行；否则业务处理完后立刻离开银行。每接待完一个第二种业务的客户，则顺序检查和处理(如果可能)第二个队列中的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户(第二种业务)被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查(因为此时已不可能还有能满足者)转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。 写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。
【基本要求】
利用动态存储结构实现模拟。 【测试数据】
一天营业开始时银行拥有的款额为10000(元)，营业时间为600(分钟)。其他模拟参
量自定，注意测定两种极端的情况：一是两个到达事件之间的间隔时间很短，而客户的交易时间很长，另一个恰好相反，设置两个到达事件的间隔时间很长，而客户的交易时间很短。
【实现提示】
事件有两类：到达银行和离开银行。初始时银行现存资金总额为total。开始营业后的第一今事件是客户到达，营业时间从0到closetime。到达事件发生时随机地设置此客户的交易时间和距下一到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的，用负值和正值分别表示第一类和第二类业务。变量total，closetime以及上述两个随机量的上下界均交互地从终端读入，作为模拟参数。 两个队列和一个事件表均要用动态存储结构实现。注意弄清应该在什么条件下设置离开事件，以及第二个队列用怎样的存储结构实现时可以获得较高的效率。注意：事件表是按时间顺序有序的。
【选作内容】
自己实现动态数据类型。例如对于客户结点，定义pool为 CustNodepoolfMAX]；
// 结构类型CustNode含四个域：aITHIne，durtime，amount，next
或者定义四个同样长的，以上述域名为名字的数组。初始时，将所有分量的next域链接起来，形成一个静态链找，设置一个楼顶元素下标指示量top，top=0表示找空。动态存储分配函数可以取名为myMalloc，其作用是出钱，将钱顶元素的下标返回。若返回的值为0，则表示无空间可分配。归还函数可取名为myFree，其作用是把该分量入钱。用FOR-TRAN和BASIC等语言实现时只能如此地自行
组织。
172. 航空客运订票系统
【问题描述】
航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。
【基本要求】
(1)每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名单(包括姓名、订票量、舱位等级1，2或3)以及等候替补的客户名单(包括姓名、所需票量)；
(2)系统能实现的操作和功能如下：
①录入：可以录入航班情况，全部数据可以只放在内存中，最好存储在文件中；
②查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；
③承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补；
④承办退票业务：根据客户提供的情况(日期、航班)，为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。
【测试数据】 由读者自行指定。 【实现提示】
两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。
【选作内容】
当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其他航线情况。读者还可充分发挥自己的想象力，增加你的系统的功能和其他服务项目。
173. 电梯模拟
【问题描述】
设计一个电梯模拟系统。这是一个离散的模拟程序，因为电梯系统是乘客和电梯等“活动体“构成的集合，虽然他们彼此交互作用，但他们的行为是基本独立的。在离散的模拟中，以模拟时钟决定每个活动体的动作发生的时刻和顺序，系统在某个模拟瞬间处理有待完成的各种事情，然后把模拟时钟推进到某个动作预
定要发生的下一个时刻。
【基本要求】
(1) 模拟某校五层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。五个楼层由下至上依次称为地下层、第→层、第二层、第三层和第四层，其中第一层是大楼的迸出层，即是电梯的“本垒层“，电梯“空闲“时，将来到该层候命。 (2) 乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。
(3) 模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要耗费一定的时间单位(简记为t)，比如：
有人进出时，电梯每隔40t测试一次，若无人进出，则关门； 关门和开门各需要20tg 每个人进出电梯均需要25h
如果电梯在某层静止时间超过300t，则驶回1层候命。
(4) 按时序显示系统状态的变化过程：发生的全部人和电梯的动作序列。 【测试数据】
模拟时钟Time的初值为0，终值可在500~10000范围内逐步增加。 【实现提示】
(1)楼层由下至上依次编号为0，1，2，3，4。每层有要求Up(上)和Down(下〉的两个按钮，对应10个变量CaliUp[0..4]和CallDOWEl[0..4]。电梯内5个目标层按钮对应变量Caucar[0..4]。有人按下某个按钮时，相应的变量就置为1，一旦要求满足后，电梯就把该变量清为0。
(2)电梯处于三种状态之-zGoingUp(上行)、GoingDown(下行)和Idle(停候)。如果电梯处于Idle状态且不在1层，则关门并驶回1层。在1层停候时，电梯是闭门候命。一旦收到往另一层的命令，就转入GoingUp或GoingDown状态，执行相应的操作。
(3)用变量Time表示模拟时钟，初值为0，时间单位。)为0。l秒。其他重要的变量有：
Floor ——电梯的当前位置(楼层)；
DI ——值为0，除非人们正在进入和离开电梯；
D2 ——值为0，如果电梯已经在某层停候30Ot以上； D3 ——值为0，除非电梯门正开着又无人迸出电梯；
State ——电梯的当前状态(GoingUp，GoingDOWEl，Idle)。 系统初始时，Floor=1，Dl=D2=D3=0，State=Idle。
(4)每个人从进入系统到离开称为该人在系统中的存在周期。在此周期内，他有6种可能发生的动作：
M1. [进入系统，为下一人的出现作准备]产生以下数值： InFloor ——该人进入哪层楼； 011tFloor ——他要去哪层楼；
GiveupTime ——他能容忍的等候时间；
Inter-Time ——下一人出现的时间间隔，据此系统预置下一人进入系统的时刻。
M2. [按电钮并等候]此时应对以下不同情况作不同的处理：
①Floor=InFloor且电梯的下一个活动是E6(电梯在本层，但正在关门〉； ②Floor=InFloor且D3手0(电梯在本层，正有人迸出)；
③其他情况，可能D2=0或电梯处于活动El(在1层停候)。
M3. [进入排队]在等候队列Queue[InFloor]末尾插入该人，并预置在GiveupTime个t之后，他若仍在队列中将实施动作M4。
M4. [放弃]如果Floor手InFloor或Dl=0，则从Quem[InFloor]和系统删除该人。如果Floor=InFloor且D1学0，他就继续等候(他知道马上就可进入电梯〉。 M5. [进入电梯]从Queue[InFloor〕删除该人，并把他插入到lElevator(电梯)校中。置Cancar[011tFloor]为1。
M6. [离去]从Elevator和系统删除该人。 (5)电梯的活动有9种：
E1. [在1层停候]若有人按下一个按钮，则调用Controler将电梯转入活动E3或E60。
E2. [要改变状态?]如果电梯处于GoingUp(或GoingDown〉状态，但该方向的楼层却无人等待，则要看反方向楼层是否有人等候，而决定置State为GoingDown(或GoingUp〉还是Idle。
E3. [开门]置DI和D2为非0值，预置300个t后启动活动E9和76个t后启动E5，然后预置20个t后转到目。
E4. [让人出入]如果Elevator不空且有人的011tFloor=Floor，则按进入的倒序每隔25个t让这类人立即转到他们的动作M6。Elevator中不再有要离开的人时，如果Queue[Floor]不空，则以25个t的速度让他们依次转到MLQueue[Floor]空时，置Dl为0，D3手0，而且等候某个其他活动的到来。
E5. [关门]每隔40个t检查D1，直到是D1=O(若D1手0，则仍有人出入〉。置D3为0并预置电梯再20个t后启动活动E6(再关门期间，若有人到来，则如M2所述，门再次打开)。
E6. [准备移动]置Caucar[Floor]为0，而且若State手GoingDown，则置CallUP CFloor]为05若State手GoingUp，则置CallDownCFloor]为0。调用Controler函数。
如果State=Idle，则即使已经执行了Controler，也转到E1。否则，如果D2手0，则取消电梯活动E9。最后，如果State=GoingUp，则预置15个t后(电梯加速〉转到E7；如果State=GoingDown，则预置15个t后(电梯加速)转到E8。
E7. [上升一层]置Floor加1并等候51个人如果现在Caucar[Floor〕=1或CallUp[Floor]=1，或者如果((Floor=1或CallDOWEl[Floor]=1)且CallUp[j]=CallDOWEl[j]=CallCar-0]=0对于所有j>Floor)，则预置14个t后(减速)转到E2；否则重复E7。
E8. [下降一层]除了方向相反之外，与E7类似，但那里的51和14个t，此时分别改为61和23个t(电梯下降比上升慢)。
E9. [置不活动指示器]置D2为0并调用Controler函数(E9是由E3预置的，但几乎总是被E6取消了训。
(6)当电梯须对下一个方向作出判定时，便在若干临界时刻调用Controler函数。该
函数有以下要点：
C1. [需要判断?]若State手Idle，则返回。
C2. [应该开门?]如果电梯处于E1且CallUp[1]，CallDown[1]或Caucar[1]非0，则
预置20个t后启动E3，并返回。
C3. [有按钮按下?]找最小的j手Floor，使得CallUp[j]，CallDOWEl〔j]或Caucar[j]非0，并转到C4。但如果不存在这样的j，那么，如果Controler正为E6所调用，则置j为1，否则返回。
C4. [置State]如果Floor>j，则置State为GoingDOWEl；如果Floor C5. [电梯静止?]如果电梯处于E1而且j手1，则预置20个t后启动E6。返回。 (7)由上可见，关键是按时序管理系统中所有乘客和电梯的动作设计合适的数据结构。 【选作内容】 (l) 增加电梯数量，模拟多梯系统。 (2) 某高校的一座30层住宅楼有三部自动电梯，每梯最多载客15人。大楼每层8户，每户平均3。5人，每天早晨平均每户有3人必须在7时之前离开大楼去上班或上学。模拟该电梯系统，并分析分别在一梯、二梯和三梯运行情况下，下楼高峰期间各层的住户应提前多少时间候梯下楼?研究多梯运行最佳策略。 174. 迷宫问题 【问题描述】 以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 【基本要求】 编写一个求解迷宫的非递归程序。求得的通路以三元组(i，j，d)的形式输出，其中：(i，j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为z(1，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，··。 【测试数据】 迷宫的测试数据如下：左上角(1，1)为入口，右下角(8，9)为出口。 1 2 3 4 5 6 7 8 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 【实现提示】 计算机解迷宫通常用的是“穷举求解“方法，即从人口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。 可以二维数组存储迷宫数据，通常设定入口点的下标为(1，1)，出口点的下标为(n，n)。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。 【选作内容】 (l) 编写递归形式的算法，求得迷宫中所有可能的通路； (2) 以方阵形式输出迷宫及其通路。 ch3 串及其应用 本实习单元的目的是熟悉串类型的实现方法和文本模式匹配方法,熟悉一般文字处理软件的设计方法,较复杂问题的分解求精方法。本实习单元的难度较大,在教学安排上可以灵活掌握完成此单元实习的时间。 编程技术训练要点:并行的模式匹配技术(3.1);字符填充技术(3.2,3.4);逻辑/物理概念隔离技术(GetAWord,3.2);活区操作技术(3.3);不定长对象的成块存储分配技术(3.3);命令识别与分析技术(3.3,3.4);串的动态组织技术(3.4);合理有效的错误处理方法(3.4);程序语法结构基本分析技术(3.5). 175. 文学研究助手 【问题描述】 文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统,称为\文学研究助手\。 【基本要求】 英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。 【测试数据】 以你的C源程序模拟英文小说,C语言的保留字集作为待统计的词汇集。 【实现提示】 约定小说中的词汇一律不跨行。这样,每读入一行,就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次,不必存多个相同的行号。 如果读者希望达到选做部分(1)和(2)所提出的要求,则首先应把KMP算法改写成如下的等价形式,再将它推广到多个模式的情形。 i=1;j=1; while(i!=s.curlen+1&&j!=t.curlerl十1) { while(j!=0&&s.ch[i]!=t.ch[j]) j=next[j]; //j==O或s.ch[i]==t.ch[j] j++;i++;//每次进入循环体,i只增加一次 } 【选作内容】 (1)模式匹配要基于KMP算法。 (2)整个统计过程中只对小说文字扫描一遍以提高效率。 (3)假设小说中的每个单词或者从行首开始,或者前置一个空格符。利用单词匹配特点另写一个高效的统计程序,与KMP算法统计程序进行效率比较。 (4)推广到更一般的模式集匹配问题,并设待查模式串可以跨行(提示:定义操作GetAChar)。 176. 文本格式化 【问题描述】 输入文件中含有待格式化〈或称为待排版〉的文本,它由多行的文字组成,例如一篇英文文章。每一行由一系列被一个或多个空格符所隔开的字①组成,任何完整的字都没有被分割在两行(每行最后一个字与下一行的第一个字之间在逻辑上应该由空格分开),每行字符数不超过80。除了上述文本类字符之外,还存在着起控制作用的字符:符号\指示它后面的正文在格式化时应另起一段排放,即空一行,并在段首缩入8个字符位置。\自成一个字。 一个文本格式化程序可以处理上述输入文件,按照用户指定的版面规格重排版面z实现页内调整、分段、分页等文本处理功能,排版结果存入输出文本文件中。 试写一个这样的程序。 【基本要求】 (1)输出文件中字与字之间只留一个空格符,即实现多余空格符的压缩。 (2)在输出文件中,任何完整的字仍不能分割在两行,行尾不齐没关系,但行首要对齐(即左对齐)。 (3)如果所要求的每页页底所空行数不少于3,则将页号印在页底空行中第2行的中间位置上,否则不印。 (4)版面要求的参数要包含： 页长(PageLength)一一每页内文字(不计页号)的行数。 页宽(PageWedth)一一每行内文字所占最大字符数。 左空白(LeftMargin)-一一每行文字前的固定空格数。 头长(HeadingLength)一一每页页顶所空行数。 脚长(FootingLength)一一每页页底所空行数(含页号行)。 起始页号(StartingPageNumber)一一首页的页号。 【测试数据】 略。注意在标点之后加上空格符。 【实现提示】 可以设:左空白数×2+页宽<=160,即行印机最大行宽,从而只要设置这样大的一个行缓冲区就足够了,每加工完一行,就输出一行。 如果输入文件和输出文件不是由程序规定死,而是可由用户指定,则有两种做法:一是像其他参量一样,将文件名交互地读入字符串变量中;更好的方式是让用户通过命令行指定,具体做法依机器的操作系统而定。 应该首先实现GetAWord(w)这一操作,把诸如行尾处理、文件尾处理、多余空格符压缩等一系列\低级\事务留给它处理,使系统的核心部分集中对付排版要求。 每个参数都可以实现缺省值②设置。上述排版参数的缺省值可以分别取56,60,10,5,5和1。 【选作内容】 (1)输入文件名和输出文件名要由用户指定。 (2)允许用户指定是否右对齐,即增加一个参量\右对齐否 \缺省值可设为\。右对齐指每行最后一个字的字尾要对齐,多余的空格要均匀分布在本行中各字之间。 (3)实现字符填充(characterstuffing)技术。\作为分段控制符之后,限制了原文中不能有这样的字。现在去掉这一限制:如果原文中有这样的字,改用两个\并列起来 表示一个\字。当然,如果原文中此符号夹在字中,就不必特殊处理了。 (4)允许用户自动按多栏印出一页。 177. 简单行编辑程序 【问题描述】 文本编辑程序是利用计算机进行文字加工的基本软件工具,实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。 被编辑的文本文件可能很大,全部读入编辑程序的数据空间(内存)的作法既不经济,也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存,称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符,很少超过80个字符。 【基本要求】 实现以下4条基本编辑命令: (1) 行插入。格式:i<行号><回车><文本>.<回车> 将<文本>插入活区中第<行号>行之后。 (2) 行删除。格式:d<行号l>[<空格><行号2>]<回车> 删除活区中第<行号l>行(到第<行号2>行)。例如:\和\。 (3) 活区切换。格式n<回车> 将活区写入输出文件,并从输入文件中读入下一段,作为新的活区。 (4) 活区显示。格式:p<回车> 逐页地(每页20行)显示活区内容,每显示一页之后请用户决定是否继续显示以后备页(如果存在)。印出的每一行要前置行号和一个空格符,行号固定占4位,增量为1。 各条命令中的行号均须在活区中各行行号范围之内,只有插入命令的行号可以等于活区第一行行号减1,表示插入当前屏幕中第一行之前,否则命令参数非法。 【测试数据】 自行设定,注意测试将活区删空等特殊情况。 【实现提示】 (1)设活区的大小用行数ActiveMULen(可设为100)来描述。考虑到文本文件行长通常为正态分布,且峰值在60到70之间,用320×ActiveMULen大小的字符数组实现存储将造成大量浪费。可以以标准行块为单位为各行分配存储,每个标准行块可含81个字符。这些行块可以组成一个数组,也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符(如(012)8)标识。此外,还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。 (2)初始化函数包括:请用户提供输入文件名(空串表示无输入文件)和输出文件名,两者不能相同。然后尽可能多地从输入文件中读入各行,但不超过ActiveMULen-LX的值可以自定,例如20。 (3)在执行行插入命令的过程中,每接收到一行时都要检查活区大小是否已达ActiveMaxLen。如果是,则为了在插入这一行之后仍保持活区大小不超过ActiveMaxLen应将插入点之前的活区部分中第一行输出到输出文件中;若插入点为第一行之前,则只得将新插入的这一行输出。 (4)若输入文件尚未读完,活区切换命令可将原活区中最后几行留在活区顶部,以保持阅读连续性;否则,它意味着结束编辑或开始编辑另一个文件。 (5)可令前三条命令执行后自动调用活区显示。 【选作内容】 (1)对于命令格式非法等一切错误作严格检查和适当处理。 (2)加入更复杂的编辑操作,如对某行进行串替换；在活区内进行模式匹配等，格式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。 178. 串基本操作的演示 【问题描述】 如果语言没有把串作为一个预先定义好的基本类型对待,又需要用该语言写一个涉及串操作的软件系统时,用户必须自己实现串类型。试实现串类型,并写一个串的基本操作的演示系统。 【基本要求】 在教科书4.2.2节用堆分配存储表示实现HString串类型的最小操作子集的基础上,实现串抽象数据类型的其余基本操作(不使用C语言本身提供的串函数)。参数合法性检查必须严格。 利用上述基本操作函数构造以下系统:它是一个命令解释程序,循环往复地处理用户键入的每一条命令,直至终止程序的命令为止。命令定义如下: (1)赋值。 格式: A <串标识> <回车> 用<串标识>所表示的串的值建立新串,并显示新串的内部名和串值。例:A ‘Hi!’ (2)判相等。格式: E <串标识1> <串标识2> <回车> 若两串相等,则显示\否则显示\。 (3)联接。 格式:C <串标识1> <串标识2> <回车> 将两串拼接产生结果串,它的内部名和串值都显示出来。 (4)求长度。格式:L〈串标识> <回车> 显示串的长度。 (5)求子串。格式:S <串标识> +<数1>+<数2><回车> 如果参数合法,则显示子串的内部名和串值。<数>不带正负号。 (6)子串定位。格式:I <串标识1> <串标识2> <回车> 显示第二个串在第一个串中首次出现时的起始位置。 (7)串替换。格式: R <串标识1> <串标识2> <串标识3> <回车> 将第一个串中所有出现的第二个串用第三个串替换,显示结果串的内部名和串值,原串不变。 (8)显示。格式:P <回车> 显示所有在系统中被保持的串的内部名和串值的对照表。 (9)删除。格式:D <内部名> <回车> 删除该内部名对应的串,即赋值的逆操作。 (10)退出。格式:Q <回车> 结束程序的运行。 在上述命令中,如果一个自变量是串,则应首先建立它。基本操作函数的结果(即函数值)如果是一个串,则应在尚未分配的区域内新辟空间存放。 【测试数据】 自定。但要包括以下几组: (1)E ‘’ ‘’<回车>,应显示\。 (2)E ‘abc’ ‘abcd’<回车>,应显示\。 (3)C ‘ ‘ ‘ ‘ <回车>,应显示\。 (4)I ‘a’ ‘’ <回车>,应报告:参数非法。 (5)R ‘aaa’ ‘aa’ ‘b’<回车>,应显示'ba’ (6)R ‘aaabc’ ‘a’ ‘aab’<回车>,应显示’aabaabaabbc’。 (7)R ‘Faaaaaaaa’ ‘aaaa’ ‘ab’,<回车>,应显示’abab’。 【实现提示】 【选作内容】 (1) 串头表改用单链表实现。 (2) 对命令的格式(即语法)作严格检查,使系统既能处理正确的命令,也能处理错误的命令。注意,语义检查(如某内部名对应的串已被删除而无定义等)和基本操作参数合法性检查仍应留给基本操作去做。 (3) 支持串名。将串名(可设不超过6个字符)存于串头表中。命令(1)(3)(5)要增加命令参数<结果串名>;命令(7)中的<串标识1> 改为<串名>,并用此名作为结果串名,删除原被替串标识,用<串名>代替<串标识>定义和命令解释中的内部名。每个命令执行完毕时立即自动删除无名串。 179. 程序分析 【问题描述】 读入一个C程序,统计程序中代码、注释和空行的行数以及函数的个数和平均行数,并利用统计信息分析评价该程序的风格。 【基本要求】 (1) 把 C 程序文件按字符顺序读入源程序; (2) 边读入程序,边识别统计代码行、注释行和空行,同时还要识别函数的开始和结束,以便统计其个数和平均行数。 (3) 程序的风格评价分为代码、注释和空行三个方面。每个方面分为 A,B,C 和 D 四个等级 , 等级的划分标准是 : A级 B级 8~9或16~20行 10~14或26~30% 10~14或26~30% C级 5~7或21~24行 5~9或31~35% 5~9或31~35% D级 <5或>24行 <5%或>35% <5%或>35% 代码(函数平均长度) 10~15行 注释(占总行数比率) 15~25% 空行(占总行数比率) 15~25% 【测试数据】 先对较小的程序进行分析。当你的程序能正确运行时,对你的程序本身进行分析。 【实现提示】 为了实现的方便,可作以下约定: (1) 头两个字符是 FFF 的行称为注释行(该行不含语句)。除了空行和注释行外,其余均为代码行(包括类型定义、变量定义和函数头)。 (2) 每个函数代码行数(除去空行和注释行)称为该函数的长度。 (3) 每行最多只有一个\、\、\和\便于识别函数的结束行)。 【选作内容】 (1) 报告函数的平均长度。 (2) 找出最长函数及其在程序中的位置。 (3) 允许函数的嵌套定义,报告最大的函数嵌套深度。 ch4 数组和广义表 本实习单元是作为从线性结构到非线性结构的过渡来安排的。数组和广义表可以看成其元素本身也是自身结构 ( 递归结构 ) 的线性表。广义表本质上是一种层次结构 , 自顶向下识别并建立一个广义表的操作,可视为某种树的遍历操作:遍历逻辑的〈或符号形式的)结构,访问动作是建立一个结点。稀疏矩阵的十字链表存储结构也是图的一种存储结构。由此可见,这个实习单元的训练具有承上启下的作用。希望读者能深入研究数组的存储表示和实现技术,熟悉广义表的 存储结构的特性。 编程技术训练要点:稀疏矩阵的表示方法及其运算的实现(4.1〉;共享数据的存储表示方法(4.2);形式系统的自底向上和自顶向下识别技术(4.3 〉; 递归算法的设计方法(4.3);表达式求值技术 (4.4) 。 180. 稀疏矩阵运算器 【问题描述】 稀疏矩阵是指那些多数元素为零的矩阵。利用 \稀疏 \特点进行存储和计算可以大大 节省存储空间 , 提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。 【基本要求】 以\带行逻辑链接信息\的三元组顺序表表示稀疏矩阵,实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示 , 而运算结果的矩阵则以通常的阵列形式列出。 【测试数据】 【实现提示】 1. 首先应输入矩阵的行数和列数 , 并判别给出的两个矩阵的行、列数对于所要求作 的运算是否相匹配。可设矩阵的行数和列数均不超过 20 。 2. 程序可以对三元组的输入顺序加以限制 , 例如 , 按行优先。注意研究教科书 5.3.2 节中的算法 , 以便提高计算效率。 3. 在用三元组表示稀疏矩阵时 , 相加或相减所得结果矩阵应该另生成 , 乘积矩阵也 可用二维数组存放。 【选作内容】 1. 按教科书 5.3.2 节中的描述方法 , 以十字链表表示稀疏矩阵。 2. 增添矩阵求逆的运算 , 包括不可求逆的情况。在求逆之前 , 先将稀疏矩阵的内部表示改为十字链表。 181. 多维数组 【问题描述】 设计并模拟实现整型多维数组类型。 【 基本要求】 尽管 C 等程序设计语言已经提供了多维数组 , 但在某些情况下 , 定义用户所需的多维数组很有用的。通过设计并模拟实现多维数组类型 , 可以深刻理解和掌握多维数组。整型多维数组应具有以下基本功能 : (1) 定义整型多维数组类型 , 各维的下标是任意整数开始的连续整数 ; (2) 下标变量赋值 , 执行下标范围检查 ; (3 〉同类型数组赋值 ; (4) 子数组赋值 , 例如 ,a[1..n]=a [2..n+1];a[2..4][3..5]=b[1..3][2..4]; (5) 确定数组的大小。 【 测试数据】 由读者指定。 【实现提示】 各基本功能可以分别用函数模拟实现 , 应仔细考虑函数参数的形式和设置。 定义整型多维数组类型时 , 其类型信息可以存储在如下定义的类型的记录中： ＃define MaxDim 5 Typedef struct int dim , BoundPtr lower , Upper; ConstPtr constants; )NArray,*NarrayPtr; 整型多维数组变量的存储结构类型可定义为: Typedef struct{ ElemType *elem; Int num; NArrayType TypeRecord; }NArrayType; 【选作内容】 (1) 各维的下标是任意字符开始的连续字符。 (2) 数组初始化。 (3) 可修改数组的下标范围。 182. 识别广义表的头或尾 【问题描述】 写一个程序,建立广义表的存储结构,演示在此存储结构上实现的广义表求头/求尾操作序列的结果。 【基本要求】 (1) 设一个广义表允许分多行输入,其中可以任意地输入空格符,原子是不限长的仅由字母或数字组成的串。 (2) 广义表采用如教科书中图5.8所示结点的存储结构,试按表头和表尾的分解方法编写建立广义表存储结构的算法。 (3) 对已建立存储结构的广义表施行操作,操作序列为一个仅由\或\组成的串,它可以是空串(此时印出整个广义表),自左至右施行各操作,再以符号形 式显示结果。 【测试数据】 【实现提示】 (1) 广义表串可以利用 C 语言中的串类型或者利用实习三中已实现的串类型表示。 (2) 输入广义表时靠括号匹配判断结束,滤掉空格符之后,存于一个串变量中。 (3) 为了实现指定的算法，应在上述广义表串结构上定义以下4个操作: Test(s):当 S 分别为空串、原子串和其他形式串时，分别返回‘N’，‘E’和‘O’(代表Null,Element和Other)。 hsub(s,h):s 表示一个由逗号隔开的广义表和原子的混合序列,h为变量参数,返回时为表示序列第一项的字符串。如果s为空串,则h也赋为空串。 tsub(s,t):s的定义同hsub操作；t为变量参数,返回时取从S中除去第一项(及其之后的逗号,如果存在的话)之后的子串。 strip(s,r)：s 的定义同 hsub 操作；r为变量参数。如果串S以\开头和以\结束,则返回时取除去这对括号后的子串,否则取空串。 (4) 在广义表的输出形式中,可以适当添加空格符,使得结果更美观。 【选作内容】 (1) 将hsub和tsub这两个操作合为一个(用变量参数h和t分别返回各自的结果),以便提高执行效率。 (2) 设原子为单个字母。广义表的建立算法改用边读入边建立的自底向上识别策略实现,广义表符号串不整体地缓冲。 183. 简单LISP算术表达式计算器 【问题描述】 设计一个简单的 LISP 算术表达式计算器。 简单 LISP 算术表达式(以下简称表达式)定义如下: (1) 一个 0..9 的整数;或者 (2)(运算符 表达式 表达式) 例如,6,(+45),(+(+25)8) 都是表达式,其值分别为6,9和15。 【基本要求】 实现LISP加法表达式的求值。 【测试数据】 6,(+45),(+(+25)8),(+2(+58)),(+(+(+12)(+34))(+(+56)(+78))) 【 实现提示】 写一个递归函数: int Evaluate(FILE * CharFile) 字符文件 CharFile 的每行是一个如上定义的表达式。每读入CharFile 的一行, (3) 提供两种最优决策 : 最快到达或最省钱到达。全程只考虑一种交通工具。 (4) 旅途中耗费的总时间应该包括中转站的等候时间。 (5) 咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具 , 输出信息 : 最快需要多长时间才能到达或者最少需要多少旅费才能到达 , 并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。 【测试数据】 参考教科书 7.6 节图 7.33 的全国交通图 , 自行设计列车时刻表和飞机航班。 【实现提示】 (1) 对全国城市交通图和列车时刻表及飞机航班表的编辑 , 应该提供文件形式输入 和键盘输入两种方式。飞机航班表的信息应包括 : 起始站的出发时间、终点站的到达时间 和票价 ; 列车时刻表则需根据交通图给出各个路段的详细信息；例如：基于教科书7.6节。图 7.33 的交通图 , 对从北京到上海的火车 , 需给出北京至天津、天津至徐州及徐州至上海 各段的出发时间、到达时间及票价等信息。 (2 )以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，还应包 括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。 【选作内容】 增加旅途中转次数最少的最优决策。 ch6 存储管理、查找和排序 与前五个实习单元不同，本实习单元旨在集中对几个专门的问题作较为深入的探讨和理解，不强调对某些特定的编程技术的训练。 动态存储管理问题的实习遇到高级语言限制方面的困难。6.1题绕过了这个限制。尽管与实际情况有差距，例如，求得伙伴地址以后不能用它寻址得到伙伴的头，但还是较完整地体现了伙伴系统的主要框架和意图。希望选择此题的读者认真思考:如何修改自己的程序才能得到实用的系统。 探讨了不同的索引技术。散列技术是索引技术中的一种非常重要和有效的技术，但与实际问题(主要是关键字集的形态和特点)关系甚密。哈希函数的选择和冲突解决方法的选用都带有较强的技巧性和经验性，自己动手试一试是非常有益的：平衡树和键树有其一定的实用范围：B树是动态索引文件的一种极好的组织方式，也是物理数据库实现的基本技术。尽管此题难度大了一些，但给读者带来的提高也相应地大些，其中所含的程序设计技巧也比较多。 除了使读者对各种内部排序方法及效率获得深入理解之外，还可以给读者以启发：对于一个一般的问题而言，开发高效算法的可能性如何?应该如何寻找和构造高效算法。 192. 伙伴存储管理系统演示 【问题描述】 伙伴存储管理系统是一种巧妙而有效的方法。试写一个演示系统，演示分配和回收存储块前后的存储空间状态变化。 【基本要求】 程序应不断地从终端读取整数n。每个整数是一个请求。如果n>0，则表示用户申请大小为n的空间：如果n<0，则表示归还起始地址(即下标)为-n的块才日果n=0，则表示结束运行。每读入一个数，就处理相应的请求，并显示处理之后的系统状态。 系统状态由占用表和空闲表构成。显示系统状态意味着显示占用表中各块的始址和长度，以及空闲表中各种大小的空闲块的始址和长度。 【测试数据】 l，一<①1>，3，4，4，4，一<①4>，一<①3>，2，2，2，2，一<②4>，一<①2>，一<②2>，一<③2>，一<④2>，一<③4>，40，0。其中，<③，2>表示第③次申请大小为2的空间使得块的始址。其余类推。 【实现提示】 可以取m=5，即Spacesize=25，数据结构如下: Typedef struct BlkHeader{ BlkHeader *llink，*rlink； int tag； Int kvalue； Int blkstart； //块起始地址 }BlkHeader，*Link； Typedef struct{ Int blksize； Link first； }ListHeader； Typedef char ell； //cell也可以是其他单位 主要变量是: cell space[Spacesize] //被管理的空间 ListHeader avail[m+1]； //可用空间表 Link ailocated；.//占用表的表头指针 在这里，我们把每块的块头分离出来，通过blkstart域与相应的块建立联系。每个块一旦被分配，其块头就进入占用表，其中的各块头由rlink域链接在一起。tag域实际上不起作用，但为了与实际伙伴管理系统更接近，没有把它去掉。显然，在这种模拟实现方法中，不对数组space作任何引用或赋值。 【选作内容】 (1)同时还用直观的图示方式显示状态。 (2)写一个随机地申请和归还各种规格的存储块的函数考验你的伙伴系统。