2014年数据结构课程设计题目及报告范例

更新时间：2023-10-22 15:06:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

1. 运动会分数统计

【问题描述】

参加运动会的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 个字符。每个项目结束时，将其编号、类型符(区分取前五名还是前三名) 输入，并按名次顺序输入

运动员姓名、校名(和成绩)。【选作内容】

允许用户指定某项目采取其他名次取法。

2. 集合的并、交和差运算

【问题描述】

编制一个能演示执行集合的并、交和差运算的程序。【基本要求】

(1) 集合的元素限定为小写字母字符 [‘a’..’z’] 。 (2) 演示程序以用户和计算机的对话方式执行。【测试数据】

(1)Set1=\，Set2=\，

Set1∪Set2=\，Setl ∩Set2=\，Set1-Set2=\。 (2)Set1= \，Set2=\，

Set1∪Set2=\，Setl ∩Set2=\，Set1-Set2=\。【实现提示】

以有序链表表示集合。【选作内容】

(1) 集合的元素判定和子集判定运算。 (2) 求集合的补集。

(3) 集合的混合运算表达式求值。

(4) 集合的元素类型推广到其他类型，甚至任意类型。

3. 一元稀疏多项式计算器

【问题描述】

设计一个一元稀疏多项式简单计算器。【基本要求】

一元稀疏多项式简单计算器的基本功能是： (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 的输出形式为

?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×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。

7. 魔王语言解释

【问题描述】

有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能昕得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：

(1) ???1?2??m

(2) (??1?2??n)???n??n?1???1?

在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。【基本要求】

用下述两条具体规则和上述规则形式(2)实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。

(1) B?tAdA (2) A?sae

【测试数据】

B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae

若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。

t 天 d 地 s 上 a 一只 e 鹅 z 追 g 赶 x 下 n 蛋 h 恨【实现提示】

将魔王的语言自右至左进栈，总是处理栈顶字符。若是开括号，则逐一出栈，将字母顺序入队列，直至闭括号出栈，并按规则要求逐一出队列再处理后入栈。其他情形较简单，请读者思考应如何处理。应首先实现栈和队列的基本操作。【选作内容】

(1)由于问题的特殊性，可以实现栈和队列的顺序存储空间共享。

(2)代换变量的数目不限，则在程序开始运行时首先读入一组第一种形式的规则，而不是把规则固定在程序中(第二种形式的规则只能固定在程序中)。

8. 航空客运订票系统

【问题描述】

航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。

【基本要求】

(1)每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名单(包括姓名、订票量、舱位等级1，2或3)以及等候替补的客户名单(包括姓名、所需票量)；

(2)系统能实现的操作和功能如下：

①录入：可以录入航班情况，全部数据可以只放在内存中，最好存储在文件中；

②查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；

③承办订票业务：根据客户提出的要求(航班号、订票数额)查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补；

④承办退票业务：根据客户提供的情况(日期、航班)，为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。

【测试数据】由读者自行指定。【实现提示】

两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。

【选作内容】

当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其他航线

情况。读者还可充分发挥自己的想象力，增加你的系统的功能和其他服务项目。

9. 电梯模拟

【问题描述】

设计一个电梯模拟系统。这是一个离散的模拟程序，因为电梯系统是乘客和电梯等“活动体“构成的集合，虽然他们彼此交互作用，但他们的行为是基本独立的。在离散的模拟中，以模拟时钟决定每个活动体的动作发生的时刻和顺序，系统在某个模拟瞬间处理有待完成的各种事情，然后把模拟时钟推进到某个动作预定要发生的下一个时刻。

【基本要求】

(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函

数。该则

预置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

C1. [需要判断?]若State手Idle，则返回。

C2. [应该开门?]如果电梯处于E1且CallUp[1]，CallDown[1]或Caucar[1]非0，

State为 GoingUp。

C5. [电梯静止?]如果电梯处于E1而且j手1，则预置20个t后启动E6。返

回。

(7)由上可见，关键是按时序管理系统中所有乘客和电梯的动作设计合适的数

据结构。【选作内容】

(l) 增加电梯数量，模拟多梯系统。

(2) 某高校的一座30层住宅楼有三部自动电梯，每梯最多载客15人。大楼

每层8户，每户平均3。5人，每天早晨平均每户有3人必须在7时之前离开大楼去上班或上学。模拟该电梯系统，并分析分别在一梯、二梯和三梯运行情况下，下楼高峰期间各层的住户应提前多少时间候梯下楼?研究多梯运行最佳策略。

10. 文学研究助手

【问题描述】

文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试

写一个实现这一目标的文字统计系统,称为\文学研究助手\。【基本要求】

英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕,即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号,格式自行设计。【测试数据】

以你的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)。

11. 文本格式化

【问题描述】

输入文件中含有待格式化〈或称为待排版〉的文本,它由多行的文字组成,例如一篇英文文章。每一行由一系列被一个或多个空格符所隔开的字①组成,任何完整的字都没有被分割在两行(每行最后一个字与下一行的第一个字之间在逻辑上应该由空格分开),每行字符数不超过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)允许用户自动按多栏印出一页。

12. 简单行编辑程序

【问题描述】

文本编辑程序是利用计算机进行文字加工的基本软件工具,实现对文本文件的插入、删除等修改操作。限制这些操作以行为单位进行的编辑程序称为行编辑程序。

被编辑的文本文件可能很大,全部读入编辑程序的数据空间(内存)的作法既不经济,也不总能实现。一种解决方法是逐段地编辑。任何时刻只把待编辑文件的一段放在内存,称为活区。试按照这种方法实现一个简单的行编辑程序。设文件每行不超过320个字符,很少超过80个字符。

合肥学院

计算机科学与技术系

课程设计报告

20 ～20 学年第学期

课学学专指

业导

班教生

姓

程数据结构与算法

高苏广 020202086 03计科(1)

名号级师

课程设计名称

20 年月

计算机科学与技术系课程设计评分表

学生/学号：（5号字、宋体）专业/班级：计算机科学与技术06级1班设计题目一、内容课程设计主要内容二元多项式加减运算问题成绩设计程序以实现降幂建立、输出、加、减任意两个二元多项式。要求：（1）所设计的数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。二、任务和要求任务：⑴ 通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。⑵ 深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。⑶ 在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。要求：按“课程设计教学大纲”的要求完成不“数据结构与算法课程设计报告”。序号 1 2 3 4 5 6 7 8 9 10 实验过程出勤率好。评价项目评分满分得分 10 10 10 10 10 10 10 10 10 10 累计得分日期实验预研报告清晰、正确、图表齐全、质量高态度认真，作风严谨，并按规定的进度开展实验工作能很好地完成任务书规定的工作量在实验中，学生使用和操作仪器的能力、观察和分析实验现象的能力、主动排除故障的能力对实验结果有自己独立见解答辩简明扼要、重点突出地阐述课题的主要内容准确流利地回答各种问题，能否阐明自己的观点课程设计报告，内容充实、图表齐全、数据处理正确、结构合理、书面整洁文字表达能力强，准确地表达自己的思想。总体评价教师签名注：（1）成绩评定采用五级记分制优秀(90～100分)、良好(80～89分)、中等(70～79分)、及格(60～69分)、不及格(60分以下)

合肥学院

计算机科学与技术系

课程设计任务书

2008 ～2009 学年第一学期

课专指

业导

班教

程级师

数据结构与算法

二元多项式加减运算问题

课程设计名称

计算机科学与技术06级1班

2008年9 月

一、课程设计目的

“数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一，是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并用软件解决问题，培养良好的程序设计技能。

二、课程设计名称及内容

名称：二元多项式加减运算问题

内容：设计程序以实现降幂建立、输出、加、减任意两个二元多项式。要求：

（1）所设计的数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。

三、任务和要求

任务：⑴ 通过独立解决某个课程设计问题，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。⑵ 深刻理解、牢固掌握数据结构和算法设计技术，提高分析和解决实际问题的能力。⑶ 在程序设计方法以及上机操作等基本技能和科学作风方面进行比较系统和严格的训练。

要求：按“课程设计教学大纲”的要求完成“数据结构与算法课程设计报告”。

四、设计方案提示

参考教材相应章节。五、参考资料

[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。 [2] 其它。

节中的算法 , 以便提高计算效率。

3. 在用三元组表示稀疏矩阵时 , 相加或相减所得结果矩阵应该另生成 , 乘积矩阵也可用二维数组存放。【选作内容】

1. 按教科书 5.3.2 节中的描述方法 , 以十字链表表示稀疏矩阵。 2. 增添矩阵求逆的运算 , 包括不可求逆的情况。在求逆之前 , 先将稀疏

矩阵的内部表示改为十字链表。

16. 多维数组

【问题描述】

设计并模拟实现整型多维数组类型。

【基本要求】

尽管 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) 可修改数组的下标范围。

17. 简单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 的一行,求出并返回表达式的值。

可以设计以下辅助函数

status isNumber(char ReadInChar); //视ReadInchar 是否是数字而返回 TRUE 或 FALSE 。

int TurnToInteger(char IntChar); // 将字符’0’..’9’ 转换为整数 0..9

【选做内容】

(1) 标准整数类型的 LISP 加法表达式的求值。 (2) 标准整数类型的 LISP 四则运算表达式的求值。 (3) LISP 算术表达式的语法检查。

18. 重言式判别

【问题描述】

一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。

【基本要求】

(1) 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括 \，\和 \，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。

(2) 若是重言式或矛盾式，可以只显示\，或\，否则显示 \以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。

【测试数据】 (1) (A|~A)&(B|~B) (2) (A&~A)&C (3) A|B|C|D|E|~A (4) A&B&C&~B (5) (A|B)&(A|~B)

(6) A&~B|~A&B;O ,0;0,1;1,0;1,1 。

19. 哈夫曼编/译码器

【问题描述】

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编 /译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。

【基本要求】

一个完整的系统应具有以下功能：

(1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

(3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。

(4)P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。

(5)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

【测试数据】

(1)利用教科书例 6-2 中的数据调试程序。

(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树 , 并实现以下报文的编码和译码：\VORITE\。字符 A B C D E F G H I J K 5 Y L M 频度 186 64 13 22 32 103 21 15 47 57 1 字符 N O P Q R S T 25

32 20 Z U V W X

频度 57

63 15 1 48 51 80 23 8 18 1 16 1 【选作内容】

(1)上述文件CodeFile中的每个\或\实际上占用了一个字节的空间，只起到示意或模拟的作用。为最大限度地利用编码存储能力，试改写你的系统，将编码结果以二进制形式存放在文件CodeFile中。

(2)修改你的系统，实现对你的系统的原程序的编码和译码(主要是将行尾符编/译码问题)。

(3)实现各个转换操作的源/目文件，均由用户在选择此操作时指定。

20. 图遍历的演示

【问题描述】

很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。

【基本要求】

以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。

【测试数据】

任选国内城市，起点为合肥，暂时忽略里程。【实现提示】

设图的结点20-30个，每个结点用一个编号表示(如果一个图有n个结点，则它们的编号分别为1，2，?，n)。通过输入图的全部边(存于数据文件中，从文件读写)输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。

【选作内容】

(1)借助于栈类型(自己定义和实现)，用非递归算法实现深度优先遍历。 (2)以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。

21. 教学计划编制问题

【问题描述】

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

【基本要求】

(1)输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。

(2)允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。

(3)若根据给定的条件问题无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。

【测试数据】

学期总数：65；学分上限：103；该专业共开设12门课，课程号从CO1到C12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见教科书图7.26。

22. 校园导游咨询

【问题描述】

设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】

(1) 设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息。

(2)为来访客人提供图中任意景点相关信息的查询。

(3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一

条最短的简单路径。【测试数据】

以合肥学院南艳湖校区为例。【实现提示】

一般情况下,校园的道路是双向通行的,可设校园平面图是一个无向网。顶点和边均含有相关信息。【选作内容】

(1) 求校园图的关节点。

(2) 提供图中任意景点问路查询 , 即求任意两个景点之间的所有路径。 (3) 提供校园图中多个景点的最佳访问路线查询 , 即求途经这多个景点的最佳 ( 短 )路径。

(4) 校园导游图的景点和道路的修改扩充功能。

(5) 扩充道路信息 , 如道路类别 ( 车道、人行道等 ) 、沿途景色等级 , 以至可按客人所需分别查询人行路径或车行路径或观景路径等。

(6) 扩充每个景点的邻接景点的方向等信息 , 使得路径查询结果能提供详尽的导向信息。

(7) 实现校园导游图的仿真界面。

23. 图书管理

【问题描述】

图书管理基本业务活动包括:对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。【基本要求】

〈1〉每种书的登记内容至少包括书号、书名、著者、现存量和总库存量等五项。

〈2〉作为演示系统，不必使用文件，全部数据可以都在内存存放。但是由于上述四项基本业务活动都是通过书号(即关键字〉进行的，所以要用B树〈24树〉对书号建立索引，以获得高效率。

〈3〉系统应实现的操作及其功能定义如下:

① 采编入库z新购入一种书，经分类和确定书号之后登记到图书账目中去。如果这种书在账中已有，则只将总库存量增加。

② 清除库存:某种书已无保留价值，将它从图书账目中注销。

③ 借阅:如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。

④ 归还z注销对借阅者的登记，改变该书的现存量。

⑤ 显示:以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。【测试数据】

入库书号:35，16，18，70，5，50，22，60，13，17，12，45，25，毡，15，90，30，7然后清除:45，90，50，22，42

其余数据自行设计。由空树开始，每插入删除一个关键字后就显示B树的状态。【实现提示】

(1)24树的查找算法是基础，入库和清除操作都要调用。难点在于删除关键字的算法，因而只要算法对2-3树适用就可以了，暂时不必追求高阶B树也适用的删除算法。

(2)每种书的记录可以用动(或静)态链式结构。借阅登记信息可以链接在相应的那种书的记录之后。

【选作内容】

(l)将一次会话过程(即程序一次运行)中的全部人机对话记入一个日志文件

\中去。

(2)增加列出某著者全部著作名的操作。思考如何提高这一操作的效率，参阅

教科书12.6.2节。

(3〉增加列出某种书状态的操作。状态信息除了包括这种书记录的全部信息

外还包括最早到期(包括已逾期)的借阅者证号，日期可用整数实现，以求简化。

(4)增加预约借书功能。

24. 多关键字排序

【问题描述】

多关键字的排序有其一定的实用范围。例如:在进行高考分数处理时，除了需对总分进行排序外，不同的专业对单科分数的要求不同，因此尚需在总分相同的情况下，按用户提出的单科分数的次序要求排出考生录取的次序。【基本要求】

(1)假设待排序的记录数不超过10000，表中记录的关键字数不超过5，各个关键字的范围均为0至100。按用户给定的进行排序的关键字的优先关系，输出排序结果。

(2)约定按LSD法进行多关键字的排序。在对各个关键字进行排序时采用两种策略:其一是利用稳定的内部排序法，其二是利用\分配\和\收集\的方法。并综合比较这两种策略。【测试数据】

由随机数产生器生成。【实现提示】

用5至8组数据比较不同排序策略所需时间。由于是按LSD方法进行排序，则对每个关键字均可进行整个序列的排序，但在利用通常的内部排序方法进行排序时，必须选用稳定的排序方法。借助\分配\和\收集\策略进行的排序，如同一趟\基数排序\，由于关键字的取值范围为0至100，则分配时将得到104个链表。【选作内容】

增添按MSD策略进行排序，并和上述两种排序策略进行综合比较。

25手机通讯录的制作

设计目的：用〈〈数据结构〉〉中的双向链表作数据结构。编写一个手机通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容：本系统应完成一下几方面的功能：（1）. 添加信息

（2）. 显示信息：它可以按按固定电话排列、按手机、联系人名字的拼音顺序排列。（3）. 查找：可以不同的关键字作为查找的依据，进行查找; （4）. 编辑信息（5）. 删除信息

（6）. 保存到文件：将以上信息保存到文件，以便下次运行程序时能载入此通信录设计要求：

（1）. 每条信息至包含：姓名（NAME ）,手机号，固定电话号，电子邮箱，QQ号码，城

市（CITY）邮编（EIP）几项

（2）. 作为一个完整的系统，应具有友好的界面和较强的容错能力（3）. 上机能正常运行，并写出课程设计报告

26 奇数阶幻方求解

要求必须在空间复杂度为O(N)的要求下实现N阶幻方的输出。 Problem description

幻方是一种很有意思的数字矩阵，在很早著名的九宫八卦阵就与幻方有关。幻方的定义为：

1 到 N*N 的整数填入N*N的方格中，每行和每列以及对角线的数字之和必须是相等的。你作为八卦公司的顶级程序员，现在需要你解决一个问题，将任意奇数阶的幻方找出来。 Input

输入包括多个测试集，每行为一个正奇数N(1 <= N < 1000)，0作为输入的结束且不需要处理。

Output

对于输入的每一个N，输出一个它所对应的N阶幻方，如果存在多个，任意一个即可。每个幻方为N*N的矩阵，

对于每个幻方，每行输出幻方的一行，每行中的数字之间用一个或多个空格分开。不同的幻方之间用一个空行分开。

Sample Input 1 3 0

Sample Output 1

27 算术表达式与二叉树

【问题描述】

一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。【任务要求】

假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。实现以下操作：

1) ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。 2) WriteExpre(E)—用带括弧的中缀表达式输出表达式E。 3) Assign(V,c)—实现对变量V的赋值（V=c），变量的初值为0。 4) Value(E)—对算术表达式E求值。

5) CompoundExpr（P，E1，E2）--构造一个新的复合表达式（E1）P（E2）【测试数据】

1) 分别输入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并输出。 2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。

28 内部排序算法比较

【问题描述】

在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机数据比较各种算法的关键字比较次数和关键字移动次数，以取得直观感受。

【任务要求】

1) 对以下7种常用的内部排序算法进行比较：冒泡排序、直接插入排序、简单选择排

序、希尔排序、堆排序、归并排序、快速排序。

2) 待排序表的表长不小于100；其中的数据要用伪随机数程序产生；至少要用5组不

同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。

3) 最后要对结果作出简单分析，包括对各组数据得出结果波动大小的解释。【测试数据】

由随机数产生器生成

29 动态查找表

【问题描述】

利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。

【任务要求】

算法输入：指定一组数据。

算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。

算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。【测试数据】

自行设定，注意边界等特殊情况。

30 joseph环

【问题描述】

编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。

【任务要求】

利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。

测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？要求：

输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。

输出形式：建立一个输出函数，将正确的输出序列【测试数据】

自行设定，注意边界等特殊情况。

31 哈希表应用

【问题描述】

利用哈希表进行存储。【任务要求】

任务要求：针对一组数据进行初始化哈希表，可以进行显示哈希表，查找元素，插入元素，删除元素，退出程序操作。

设计思想：哈希函数用除留余数法构造，用线性探测再散列处理冲突。设计目的：实现哈希表的综合操作

简体中文控制台界面：用户可以进行创建哈希表，显示哈希表，查找元素，插入元素，删除元素。

显示元素：显示已经创建的哈希表。

查找元素：查找哈希表中的元素，分为查找成功和查找不成功。插入元素：在哈希表中，插入一个元素，分为插入成功和失败。删除元素：在已有的数据中，删除一个元素。退出系统：退出程序。【测试数据】

自行设定，注意边界等特殊情况。

32 商品货架管理

[问题描述]

商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。 [基本要求]

针对一种特定商品，实现上述管理过程。 [实现提示]

用栈模拟货架和周转空间。 [测试数据]

由学生依据软件工程的测试技术自己确定。注意测试边界数据，如空栈。

33 停车场管理

[问题描述]

设停车场内只有一个可停放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’表示输入结束。 [基本要求]

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。

[实现提示]

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

34 稀疏矩阵的完全链表表示及其运算

[问题描述]

稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。

实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。

（2）设计目的

认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构 (3) 基本要求

建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。读取一个稀疏矩阵建立其完全链表表示输出一个稀疏矩阵的内容删除一个稀疏矩阵两个稀疏矩阵相加两个稀疏矩阵相减两个稀疏矩阵相乘稀疏矩阵的转置（4）实现提示链表上的操作。

35 电视大赛观众投票及排名系统（排序应用）

【问题描述】

在很多的电视大赛中，通常当选手表演结束后，现场观众通过手中的按键对参赛选手进行投票，然后对选手获得的票数进行统计，从高到低进行降序排序，从而自动产生冠军、亚军和季军。现在要求编写一程序模拟实现上述系统的功能。【实现提示】

在本例中，首先输入参赛选手的人数（范围为1-9个），然后根据人数通过malloc函数来开辟存放选手信息的顺序表。将选手的编号和姓名依此存入顺序表单元中，观众通过按键进行投票，按’1’为1号选手投票，按’2’为2号选手投票，以此类推，以按’0’作为投票结束标志。投票结束后进行排序，在此采用希尔排序，然后为每个选手计算名次，得票相同的名次也相同，

（1）存储类型的定义

参赛选手信息存储类型的定义： typedef struct node{

char name[8]; /*选手姓名*/ int num; /*选手编号*/ int score; /*选手得分*/ int tax; /*选手名次*/ }Node;

36 学生搭配问题。

一班有m个女生,有n个男生（m不等于n），现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。

请设计一系统模拟动态地显示出上述过程，要求如下：（1）输出每曲配对情况；

（2）计算出任何一个男生（编号为X）和任意女生（编号为Y），在第K曲配对跳舞的情况.至少求出K的两个值；

（3）尽量设计出多种算法及程序。提示：用队列来解决比较方便.

37 敢死队问题

有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。

要求：至少采用两种不同的数据结构的方法实现。

38 数制转换问题

任意给定一个M进制的数x ，请实现如下要求 : 1) 求出此数x的10进制值（用MD表示）

2) 实现对x向任意的一个非M进制的数的转换。

3) 至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，其它方法解决）。

39迷宫问题（栈）

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：

首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),?。测试数据：

迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。实现提示：

计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。选做内容：（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。

40 迷宫问题（队列）（同上）

首先实现一个以链表作存储结构的队列，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),?。测试数据：

迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。实现提示：

西、北四个方向可通。选做内容：

（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路。

41 最短路

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式

共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入

3 3 1 2 -1 2 3 -1 3 1 2

样例输出

-1 -2

42 拦截导弹

问题描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，为导弹依次飞来的高度

输出格式

两行，分别是最多能拦截的导弹数与要拦截所有导弹最少要配备的系统数

样例输入

389 207 155 300 299 170 158 65

样例输出

6 2

43 二叉搜索树

判断两序列是否为同一个二叉搜索树序列

要求：输入：开始一个数n，(1<=n<=20) 表示有n个序列需要判断，n= 0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

输出：如果序列相同则输出YES，否则输出NO Sample Input 2

567432 543267 576342 0

Sample Output YES NO

44 会议中心

会议中心 Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣，他们希望能够在里面举行会议。

对于一个客户而言，仅当在开会时能够独自占用整个会堂，他才会租借会堂。会议中心的销售主管认为：最好的策略应该是将会堂租借给尽可能多的客户。显然，有可能存在不止一种满足要求的策略。

例如下面的例子。总共有4个公司。他们对租借会堂发出了请求，并提出了他们所需占用会堂的起止日期（如下表所示）。开始日期结束日期公司1 4 9 公司2 9 11 公司3 13 19 公司4 10 17

上例中，最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3，或是公司2和公司3，也可以是公司1和公司4。注意会议中心一天最多租借给一个公司，所以公司1和公司2不能同时租借会议中心，因为他们在第九天重合了。

销售主管为了公平起见，决定按照如下的程序来确定选择何种租借策略：首先，将租借给客户数量最多的策略作为候选，将所有的公司按照他们发出请求的顺序编号。对于候选策略，将策略中的每家公司的编号按升序排列。最后，选出其中字典序最小[1]的候选策略作为最终的策略。

例中，会堂最终将被租借给公司1和公司3：3个候选策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。

你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

输入格式

输入的第一行有一个整数N，表示发出租借会堂申请的公司的个数。第2到第N+1行每行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。对于每个公司

的申请，起始日期为不小于1的整数，终止日期为不大于10的整数。

输出格式

输出的第一行应有一个整数M，表示最多可以租借给多少家公司。第二行应列出M个数，表示最终将会堂租借给哪些公司。

数据规模和约定

对于50%的输入，N≤3000。在所有输入中，N≤200000。

样例输入

4 4 9 9 11 13 19 10 17

样例输出

2 1 3

[1] 字典序指在字典中排列的顺序，如果序列l1是序列l2的前缀，或者对于l1和l2的第一个不同位置j，l1[j]

45 串数

一个A和两个B一共可以组成三种字符串:\给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串.

要求：输入：每组测试数据分两行,第一行为n(1<=n<=26),表示不同字母的个数,第二行为n个数A1,A2,...,An(1<=Ai<=12),表示每种字母的个数.测试数据以n=0为结束. 输出：对于每一组测试数据,输出一个m,表示一共有多少种字符串. Sample Input 2 1 2 3

2 2 2 0

Sample Output 3 90

46 树的应用

要实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。

47 求先序排列

问题描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入格式

两行，每行一个字符串，分别表示中序和后序排列

输出格式

一个字符串，表示所求先序排列

样例输入

BADC BDCA

样例输出

ABCD

48 大臣的旅费

问题描述

很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。

为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。

J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。

聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。

J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？

输入格式

输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数城市从1开始依次编号，1号城市为首都。

接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）

每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。

输出格式

输出一个整数，表示大臣J最多花费的路费是多少。

样例输入1

5 1 2 2 1 3 1 2 4 5 2 5 4

样例输出1

135

输出格式

大臣J从城市4到城市5要花费135的路费。

49 小朋友排队

问题描述

n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。

每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。

如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。

请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。

如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。

输入格式

输入的第一行包含一个整数n，表示小朋友的个数。

第二行包含 n 个整数 H1 H2 ? Hn，分别表示每个小朋友的身高。

输出格式

输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。

样例输入

3 3 2 1

样例输出

样例说明

首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。

50 接水问题

问题描述

学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1 到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队等候接水的同学k 马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即 j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n’不足m，则只有n’个龙头供水，其它m?n’个龙头关闭。现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。

输入格式

第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。第2 行n 个整数w1、w2、??、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量。

输出格式

输出只有一行，1 个整数，表示接水所需的总时间。

样例输入

5 3

4 4 1 2 1

样例输出

样例输入

8 4

23 71 87 32 70 93 80 76

样例输出