数据结构实验 栈和队列及其应用.docx

本科实验报告专用纸课程名称 数据结构 成绩评定 实验项目名称 栈和队列及其应用 指导教师 一、 实验目的和要求1. 实验目的：熟练掌握栈及队列基本操作的实现；熟练栈和队列的结构特性，掌握在实际问题背景下的应用。2. 实验要求：在上机前写出全部源程序完毕并调试完毕。二、实验原理和主要内容1实验内容（1）建立栈并进行元素（8，9，5，4）入栈，实现链栈的建立及入栈的基本操作；实现元素（9，5）的出栈，实现链栈的出栈的操作；建立链队列，并实现元素(4,5,7,6,8)入队，实现链队列的建立和入队的基本操作；实现元素(4,5,7,6,8)出队，实现链队列的出队的基本操作。（2）问题描述： 设停车场是一个可停放n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆达到时间的先后顺序，依次由北向南排列（大门在最南端，最先达到的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退车车场为它让路，待赶辆车开出大门外，其它车辆在按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短叫纳费用。试为停车场编制按上述要求进行管理的模拟程序。基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“达到”或“离去”信息、汽车牌照号码以及达到或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆达到、则输出汽车在停车场内或便道上停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。测试数据设n=2，输入数据为(“A”,1,5), (“A”,2,10), (“D”,1, 15), (“A”,3,20),(“D”,2, 35), (“E”,0,0),(“A”,1,5), 其中：“A”表示达到（Arrival）;“D”表示离去(Departure); “E”表示输入结束(End)。2实验原理（1）栈的修改时按照先进后出的原则进行的，试验中用到构造空栈，及入栈出栈操作。队列是一种先进先出的线性表，只允许在表的一端插入，而在另一端删除元素，试验中构造队并且入队出队。（2）三、主要仪器设备计算机，VC+高级程序语言四、 调试分析试验中，有些小错误经常犯，比如符号，函数声明等。停车场试验栈与队列的扩展应用在做好实验栈队列的基础上熟练掌握栈和队列基本性质及基本操作显得很必要。实验中需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按达到或离去的时刻有序。栈中每个元素表示一辆汽车，包括两个数据项：汽车的牌照号码和进入停车场的时刻。五、测试结果六、附录（源程序）1、#include#include#define OK 1#define ERROR 0#define OVERFLOW -2typedef int elemtype;typedef int status;typedef struct QNode elemtype data; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;typedef struct lnode elemtype data; struct lnode *next;stacknode, *linkstack;status initstack(linkstack top) top-next = NULL;status isempty(linkstack top) if(top-next = NULL) return OK; return ERROR;status push(linkstack top, elemtype e) stacknode *p; p= (stacknode *)malloc(sizeof(stacknode); if(p = NULL) return ERROR; p-data = e; p-next = top-next; top-next = p; return OK;status pop(linkstack top, elemtype *e) if(isempty(top) return ERROR; stacknode *p = top-next; *e = p-data; top-next = p-next; free(p); return OK;status shstack(linkstack top)stacknode *p; p= (stacknode *)malloc(sizeof(stacknode); p-next=top-next; while(p-next!=NULL)printf(%d ,p-next-data);p-next=p-next-next;return OK;status initqueue(LinkQueue *q)(*q).front=(*q).rear=(QueuePtr)malloc(sizeof(QNode);if (!(*q).front) exit(OVERFLOW);(*q).front-next=NULL;return OK;status enqueue(LinkQueue *q,elemtype e)QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p) exit(OVERFLOW);p-data=e;p-next=NULL;(*q).rear-next=p;(*q).rear=p;return OK;status dequeue(LinkQueue *q,elemtype *e)if(*q).front=(*q).rear) return ERROR;QueuePtr p;p=(*q).front-next;*e=p-data;/注意 (*q).front-next=p-next;if(*q).rear=p) (*q).rear=(*q).front;free(p);return OK;void main()linkstack s;s=(linkstack)malloc(sizeof(stacknode);initstack(s);printf(进入栈的4个元素依次为：n);for (int i=0;i4;i+)elemtype a;scanf(%d,&a);push(s,a);printf(n栈顶到栈底的元素依次为；n);shstack(s);elemtype b,c,d;pop(s,&b);pop(s,&c);pop(s,&d);push(s,b);printf(nn出栈的元素为:); printf(%d,c);printf( %dn,d);printf(n现在栈中的元素为：);shstack(s);LinkQueue q;initqueue(&q);elemtype a;printf(nnn请输入5个进队的元素:n);for(int i=0;i5;i+) scanf(%d,&a); enqueue(&q,a);printf(n元素的出列为:n); for(int i=0;i5;i+)elemtype e;dequeue(&q,&e);printf( %d,e);2、#include#include#include#include#define OVERFLOW -2#define OK 1#define ERROR 0#define STACK_INIT_SIZE 1typedef int Status;typedef struct char num10; int time;SElemType;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;typedef struct QNode char num10; int time; struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front; QueuePtr rear; int length;LinkQueue;Status InitStack(SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; S.stacksize=0; return OK;/InitStackStatus Push(SqStack &S, SElemType e) *S.top+=e; S.stacksize+; return OK;/PushStatus Pop(SqStack &S,SElemType &e)/ SElemType e; if(S.top=S.base) printf(No car in the park!n); return(ERROR); e=*-S.top; S.stacksize-; return OK;/PopStatus InitQueue(LinkQueue &Q) Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; Q.length=0; return OK;/InitQueueStatus EnQueue(LinkQueue &Q, char e_n10, int e_t) QueuePtr p; int i; p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); for(i=0; inumi=e_ni; p-time=e_t; p-next=NULL; Q.rear-next=p; Q.rear=p; Q.length+; return OK;/EnQueueStatus DeQueue(LinkQueue &Q, char e_n10, int &e_t) QueuePtr p; int i; if(Q.front=Q.rear) printf(No car in the way!); return ERROR; p=Q.front-next; for(i=0; inumi; e_t=p-time; Q.front-next=p-next; Q.length-; if(Q.rear=p) Q.rear=Q.front; free(p); return OK;/DeQueuevoid arrive(SqStack &S, LinkQueue &Q, SElemType e, int n) if(S.stacksizen) Push(S,e); printf(The car number-%s park in the park No.%d lanen,e.num,S.stacksize); printf(*n); else EnQueue(Q,e.num,e.time); printf(Car park is full!nThe car num-%s park in the sidewalk No.%d lanen,e.num,Q.length); printf(*n); /arrivevoid depart(SqStack &S, LinkQueue &Q, SElemType e, float fee, int n) SqStack ST; SElemType x,y; int i; char z_n10; int z_t; int flag=0; float cost; InitStack(ST); while(!flag) Pop(S,x); Push(ST,x); if(!strcmp(x.num,e.num) flag=1; cost=(e.time-x.time)*fee; Pop(ST,y); while(ST.stacksize) Pop(ST,y); Push(S,y); if(S.stacksizen & Q.length!=0) DeQueue(Q,z_n,z_t); for(i=0; i10; i+) y.numi=z_ni; y.time=z_t; Push(S,y); printf(The car num-%s park to the prak No.%d lane from sidewalk.n,y.num,S.stacksize); printf(-n); printf(|car_num |A_time |D_time |L_time |Cost |n); printf(|%-10s|%-6d |%-6d |%-6d |%-6.2f |n,e.num,x.time,e.time,e.time-x.time,cost); printf(*n);void main() int n;