一元稀疏多项式的计算和停车场管理系统

数据结构上机实验报告

实验一 一元稀疏多项式的计算

一、需求分析

1、问题描述

实现一元稀疏多项式的如下运算：

(1)两个一元稀疏多项式相加运算

(2)两个一元稀疏多项式相减运算

(3)两个一元稀疏多项式相乘运算

2、输入输出形式：

输入形式：每次只输入多项式中的一项，输入的数据为系数coef ，指数expn ，重复多次。当结束输入时，则输入指数expn 为-1.

输出形式：

举例说明：

3、程序功能

基本功能：

(1)多项式的输入

(2)两个一元稀疏多项式相加运算：P(x)+Q(x

(3)两个一元稀疏多项式相减运算：P(x)－Q(x)

(4)两个一元稀疏多项式相乘运算：P(x)×Q(x)

(5)多项式打印

辅助功能：

(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。

(2)插入结点位置查找：确定将一个新结点插入到多项式链表结构中的位置，以保证链表中结点按指数升序排列。

(3)交互选择：当出现重复性操作时，提供交互式选择方式，以确定其重复操作是否进行。

(4)撤消多项式：释放表示多项式链表中所有结点的存储空间。

(5)多项式项插入：将表示多项式中一项的结点插入到链表中给定的位置。

(6)判多项式非空：判断某个多项式是否存在。

(7)判断两个多项式的当前运算项的关系（指数大于，等于，小于）

4、测试数据

P(x)=x2+2x+1

Q(x)=x2+1

二、概要设计

1、一元稀疏多项式的链式存储表示。

使用带头结点的链表表示一元稀疏多项式。

结点结构定义如下：

typedef struct Item{

double coef;

int expn;

struct Item *next;

}Item,*Polyn;

每个多项式都独立存在，即参与运算的两个多项式的数据不能因运算而受到破坏，加、减、乘运算的结果应相互不受影响。因此，对于每种情况都必须单独建立一个链表进行表示。

每一种重复性的操作都要进行确认，以免破坏原有操作的结果。如需要输入A 多项式，而A 多项式已经存在，这时通过“确认”后再确定是否真正需要输入。

3、程序结构

本程序可以由13个函数组成，其中主函数1个，基本功能函数5个，辅助功能函数7个。

三、详细设计

一元稀疏多项式运算原理

设有两个稀疏多项式A 和B ，其运算原理如下：

（1）两个多项式相加(C=A＋B) 的运算原则：

指数相同，系数相加，若不为0，则在结果多项式中构成一新项。 指数不同，则两项分别抄入结果多项式中。

（2）两个多项式相减(C=A－B) 的运算原则：

指数相同，系数相减，若不为0，则构成一新项。

指数不同，对A 多项式的项，直接抄入结果多项式中。

对B 多项式的项，系数符号变换后，再将放入结果多项式中

（3）两个多项式相乘(C=A×B) 的运算原则

用B 多项式的每一项分别去乘A 多项式的每一项，并将乘得得结果放入结 果多项式中。

若结果多项式中有指数相同的项，则应把它们合并为一项。

四、用户使用说明

1、运行程序。

2、选择功能1--create P(x)，按正确的输入格式逐项输入多项式P(x)。如果P(x)已存在，则会提示是否覆盖已有的值。输入y 选择覆盖，输入n 放弃输入。

3、选择功能2--create Q(x)，输入多项式Q(x)。如果Q(x)已存在，则会提示是否覆盖已有的值。输入y 选择覆盖，输入n 放弃输入。

4、功能3，计算并输出P(x)+Q(x)的结果。

5、功能4，计算并输出P(x)-Q(x)的结果。

6、功能5，计算并输出P(x)*Q(x)的结果。

7、功能6，输出P(x)表达式。

8、功能7，输出Q(x)表达式。

9、功能8，输出P(x)+Q(x)的结果。

10、功能9，输出P(x)-Q(x)的结果。

11、功能10，输出P(x)*Q(x)的结果。

12、功能11，退出程序。

五、测试结果

实验二 停车场管理系统

一、需求分析

1、问题描述

设停车场是一个可以停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。

汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）；

若车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可进入；

当停车场某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场；

汽车可以直接从便道上离开。离开时排在前面的车也应该为其让道，随后应回到原来的位置。

每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。交费按车的类型不同而不同，假定小车每小时2元，客车每小时3元，卡车每小时5元。停在便道上的车也要交费，假设其费用为停车场的车的1/3。

停车只限于当天0点至24点。

编写程序实现上面要求的停车场停车管理功能。

2、输入输出形式

输入形式：

（1）车辆进入停车场时，输入车辆的编号BNo ，车辆到达的时间Arrivetime ，车辆类型type 。

（2）车辆离开时，输入车辆编号，离开的时间。

输出形式：

有车辆进入时，输出目前停车场内所停的车辆：

车辆离开时，输出停车费用和停车场内剩余的车辆：

3、程序功能

基本功能：

车辆进入车场信息录入

车辆离开车场信息录入

辅助功能：

（1）菜单选择：将上述基本功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。

（2）队列初始化InitQueue

（3）静态栈进栈操作Push

（4）静态栈出栈操作Pop

（5）判栈空满操作StackEmpty

（6）判栈满操作StackFull

（7）队列进队操作EnQue

（8）队列出队操作DeQue

（9）判队列空操作QueueEmpty

（10）撤销队列操作DestroyQue

（11）链式栈进栈操作（从暂停便道让道的车辆信息用链式栈保存）LPush

（12）链式栈出栈操作LPop

（13）栈信息查找SearchStack ：车辆进入车场的信息录入后，通过查找判断停车场栈中是否有重复信息录入；当离开车辆的信息录入后，通过查找确定要离

开车辆在停车场栈中的位置。

（14）队列信息查找SearchQueue ：：车辆进入车场的信息录入后，通过查找判断停车场栈中是否有重复信息录入；当离开车辆的信息录入后，通过查找确定要离开车辆在停车场栈中的位置。

（15）计算停车缴费CalcultPay

（16）输出车场车辆信息OutputBusData

二、概要设计

停车场包括正式的停车场和停车场外的暂停便道。按照要求，汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端），离开时只能从大门口离开。因此以栈模拟停车场比较合适。对栈的操作，汽车进入停车场是严格按入栈操作进行。汽车离开停车场时不一定是最接近大门的车辆，可以是停车场中的任何一辆车，所以汽车离开操作不是严格的出栈操作。但汽车离开停车场后的数据仍然按栈的方式进行组织。

由于暂停便道的车辆当停车场有空位时要进入停车场，而进入停车场的顺序是按进入便道的先后顺序进行的。因此用队列模拟停车场外的暂停便道比较恰当。

假设停车场最多可停放5辆车，初始为空，有连续9两车进入车场，则其中5辆车停在停车场，另有4辆车停在便道上，如图3-1所示。

按照从终端读入的输入数据进入模拟管理。每一组输入数据包括三个数据项：

汽车“到达”或“离去”信息

汽车牌照号码

汽车到达或离去的时刻（以小时为单位记数）

对每一组输入数据进行操作后的输出信息为：

若是车辆“到达”，则输出汽车在停车场内或便道上的停车位置。

若是车辆“离去”，则输出汽车在车场内停留的时间和应交纳的费用。

1、数据存储结构设计

（1）栈的存储结构

因为停车场的大小是固定的，所以表示停车场的栈存储结构采用顺序存储结构。与停车场对应让车栈的大小不会超过停车场栈，也同样采用顺序存储结构。

（2）队列的存储结构

假设暂停便道的长度不受限制，即暂停便道可以容纳所有不能进入停车场的车辆。因此与暂停便道对应的队列采用链式存储结构。与队列对应的让车站也采用链式存储结构。

根据上面讨论，数据存储结构定义如下：

#define STACKSIZE 5 //顺序栈的存储空间

（1）车辆停放数据描述

typedef struct{

int BNo; //车辆编号

int type; //车辆类型（小车=1，客车=2，货车=3） int arrivetime; //到达车场时间

int pushtime; //进入停车场时间

int departuretime; //离开车场时间

}BUSINF;

若到达车场时间arrivetime 等于进入停车场时间pushtime ，表示车辆直接进入停车场。如果两者不等，表示车辆先停在暂停便道上，然后进入停车场。 车辆类型用整数编码表示， 1表示小车，2表示客车，3表示货车。

为了简化处理过程，到达时间、进入停车场时间和离开车场时间都用0～24的整数表示。

（2）暂停便道队列的存储结构描述

因为车辆可以直接从暂停便道离开，所以每个结点中除包括车辆基本信息外，也包括到达时间和离开时间，为了统一起见，在队列结构的数据域中可以包括BUSINF 中全部信息。所以队列结点结构描述如下：

typedef struct QNODE{

BUSINF elm;

struct QNODE *next;

}QNODE;

其队列存储结构描述如下：

struct LinkQueue{

QNODE *front;

QNODE *rear;

}Queue;

（3）停车场栈存储结构描述

由于停车场大小基本确定，所以表示停车场的栈及协调车辆从停车场开出的辅助栈的大小基本确定。其顺序存储结构描述如下：

struct SqStack{

BUSINF elm[STACKSIZE];

int top;

}stack;；

记录车辆信息的停车场栈和暂停便道队列是整个程序操作的数据对象，也是几乎所有函数操作的主要对象，因此将其设置成全局变量能使程序设计更简单。 为了便于计算停车费用，不同类型车辆每小时停车费用用一数组pay 进行列举，类型编号对应的数组元素值即为每小时停车费用。描述如下：

int pay[]={0,2,3,5};

表示小车每小时停车费为2元，客车每小时停车费为3元，货车每小时停车费为5元。

三、详细设计

算法分析：

【算法1】车辆到达数据录入算法功能：

（1）录入一组有效的车辆到达数据。数据有效指车辆编号大于0，到达时间大于0，车辆类型编码满编码约定要求。

（2）判断车辆是否满足唯一性要求。车辆编号是车辆的唯一性标志，唯一性要求指新到达的车辆在停车场和暂停便道上都未出现。

（3）若停车场还可以停车（停车场栈不满），则把车辆数据插入到停车场栈中，否则插入到暂停便道队列中。

【算法2】车辆离开数据录入算法功能：

（1）录入一组有效的车辆离开数据。数据有效指车辆编号大于0，离开时间大于0。

（2）若要离开的车辆在停车场栈中，则：

① 将栈中要离开的车辆的栈顶前面的车辆数据移到让车便道栈中， ② 计算离开车辆应缴停车费并显示。 ③ 让车便道栈的数据移到停车场栈。

④ 如果暂停便道队列有数据，则将对头数据移到停车场栈。 （3）若要离开的车辆数据在暂停便道队列中，则：

① 将队列中要离开的车辆的队头前面的车辆数据移到链式栈中。 ② 计算离开车辆应缴停车费并显示。

③ 将链式栈中数据移到暂停便道队列头部。

源程序代码：

四、用户使用说明

1、运行程序。

2、选择功能1-arrival ，依次输入到达车辆的编号，到达时间，类型（类型用数字表示，1-car 、2-bus 、3-lorry ）

输入完成后按回车键，程序会输出停车场内车辆信息。 3、如果要继续输入车辆信息，则执行第二步。 如果有车辆要离开停车场，则执行第四步。 如果要结束程序，选择功能3-end 。

4、选择功能2-departure ，依次输入车辆编号，离开时间。

输入完成后按回车，程序会输出应付的停车费用。再按回车，则输出停车场内剩余车辆信息。

5、如果要继续输入车辆信息，则执行第二步。

如果有车辆要离开停车场，则执行第四步。

如果要结束程序，选择功能3-end 。

五、测试结果