数据结构与算法实习实验指导书

实验四 综合应用

一、运动会分数统计

问题描述

参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m+1~m+w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 基本要求

产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 测试数据

对于n=4,m=3,w=2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 实现提示

可以假设n<=20,m<=30,w<=20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 选作内容

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

二、一元稀疏多项式简单计算器

问题描述

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

一元稀疏多项式简单计算器的基本功能是： （1）输入并建立多项式；

（2）输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,……,cn,en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；

（3）多项式a和b相加，建立多项式a+b； （4）多项式a和b相减，建立多项式a-b。 测试数据

（1）（2x+5x3-3.1x11）+(7-5x8+11x9)=(-3.1x11+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 实现提示

用带表头结点的单链表存储多项式。

选作内容

（1） （2） （3） （4）

计算多项式在X处的值。 计算多项式a的导函数a’。

多项式a和b相乘，建立乘积多项式ab。

多项式的输出形式为类数学表达式。例如，多项式-3x8+6x3-18的输出形式为-3x^8+6x^3-18。注意，系数为1的非零次项的输出形式中略去系数1，如1x8的输出形式为x^8。

（5） 计算器的仿真界面。

三、停车场管理

问题描述

设停车场是一个可停放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） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修

改结构以满足这种要求。

四、航空客运订票系统

问题描述

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

（1） 每条航线所涉及的信息有：终点站名、航班号、飞机型号、飞行周日（星期

几）、乘员定额?、余票量、已定票的客户名单（包括姓名、订票量、舱位等级1，2或3）以及等候替补的客户名单（包括姓名、所需票量）；

（2） 作为示意系统，全部数据可以只放在内存中； （3） 系统能实现的操作和功能如下：

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

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

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

自行指定。 实现提示

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

当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其它航线情况。还可以充分发挥自己的想象力，增加系统的功能和其他服务项目。

五、简单行编辑程序

问题描述

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

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

实现以下4条基本编辑命令：

（1） 行插入。格式：i<行号><回车><文本>.<回车>

将文本插入活区中第<行号>行之后。

（2） 行删除。格式：d<行号1>[<空格><行号2>]<回车>

删除活区中第<行号1>行（到第<行号2>行）。例如“d10”和“d10 14” （3） 活区切换。格式：n<回车>

将活区写入输出文件，并从输入文件中读入下一段，作为新的活区。 （4） 活区显示。格式：p<回车>

逐页的（每页20行）显示活区内容，每显示一页之后请用户决定是否继续显示以后各页（如果存在）。印出的每一行要前置行号和一个空格符，行号固定占4位，增量为1。

各条命令中的行号均须在活区中各行行号范围之内，只有插入命令的行号可以等于活区第一行行号减一，表示插入当前屏幕中第一行之前，否则命令参数非法。 测试数据

自行设定，注意测试将活区删空等特殊情况。 实现提示

（1） 设活区的大小用行数ActiveMaxLen（可设为100）来描述。考虑到文本文件

行长通常为正态分布，且峰值在60到70之间，用320*ActiveMaxLen大小的字符数组实现存储将造成大量浪费，可以以标准行块为单位为各行分配存储，每个标准行块可含81个字符。这些行块可以组成一个数组，也可以利用动态链表连接起来。一行文字可能占多个行块。行尾可用一个特殊的ASCII字符（如(012)8）标识。此外，还应记住活区起始行号。行插入将引起随后各行行号的顺序下推。

（2） 初始化函数包括：请用户提供输入文件名（空串表示无输入文件）和输出文

件名，两者不能相同。然后尽可能多地从输入文件中读入各行，但不超过ActiveMaxLen-x。x的值可以自定，例如20。

（3） 在执行行插入命令的过程中，每接收到一行时都要检查活区大小是否已达

ActiveMaxLen。如果是，则为了在插入这一行之后仍保持活区大小不超过ActiveMaxLen，应将插入点之前的活区部分中第一行输出到输出文件中；若插入点为第一行之前，则只得将新插入的这一行输出。

（4） 若输入文件尚未读完，活区切换命令可将原活区中最后几行留在活区顶部，

以保持阅读连续性；否则，它意味着结束编辑或开始编辑另一个文件。

（5） 可令前三条命令执行后自动调用活区显示。 选作内容

（1） 对于命令格式非法等一切错误作严格检查和适当处理。

（2） 加入更复杂的编辑操作，如对某行进行串替换；在活区内进行模式匹配等，格

式可以为S<行号>@<串1>@<串2><回车>和m<串><回车>。

【实验环境】 VC++ 6.0

【实验要求】

将如上文件保存在命名为“学号+姓名”的文件夹中并上传到指定的服务器。

附录A 实验报告示例

“学生通讯录管理系统”的设计与实现

一、 设计要求

1、 问题描述

纸质的通讯录已经不能满足大家的要求，容易丢失，查找困难等问题是纸质通讯录所不能克服的缺点。“学生通讯录管理系统”是为了帮助老师、同学，或者其它一些需要使用通讯录的人员进行管理和分析的一种应用程序。 2、 需求分析

（1） 输入数据建立通讯录

（2） 查询通讯录中满足要求的信息 （3） 插入新的通讯录信息 （4） 删除不需要的通讯录信息 （5） 查看所有的通讯录信息

二、 概要设计

为了实现需求分析中的功能，可以从3个方面着手设计 1、 主界面设计

为了实现学生通讯录管理系统各功能的管理，设计一个含有多个菜单项的主控菜单子程序以链接系统的各项子功能，方便用户使用本系统。 2、 存储结构设计

本系统主要采用链表结构类型来表示存储在“学生通讯录管理系统”中的信息。其中，链表结点有4个分量构成：通讯录成员学号、姓名、电话号码、指向该结构体的指针。此外，本系统还设置一个全局变量seat，表示成员序号。 3、 系统功能设计

本系统设置5个子功能：

（1） 建立通讯录系统：可以一次输入多个成员的信息，建立通讯录。 （2） 插入通讯录记录：每次可以插入一个成员的信息。

（3） 查询通讯录记录：可以按两种方式查询所要的记录，一是按学号查询，二

是按姓名查询。

（4） 删除通讯录记录：可以按三种方式删除信息，按序号删除，按学号删除，

按姓名删除。

（5） 显示通讯录记录：可以查看通讯录中所有成员信息。

三、 模块设计

1、 模块设计

本程序包含两个模块：主程序模块和链表操作模块，其调用关系如下： 主程序模块 链表操作模块