数据结构实验 栈和队列及其应用Word文档下载推荐.docx
《数据结构实验 栈和队列及其应用Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《数据结构实验 栈和队列及其应用Word文档下载推荐.docx（14页珍藏版）》请在冰点文库上搜索。
“E”表示输入结束（End）。
2．实验原理
（1）栈的修改时按照先进后出的原则进行的，试验中用到构造空栈，及入栈出栈操作。
队列是一种先进先出的线性表，只允许在表的一端插入，而在另一端删除元素，试验中构造队并且入队出队。
（2）
三、主要仪器设备
计算机，VC++高级程序语言
四、调试分析
试验中，有些小错误经常犯，比如符号，函数声明等。
停车场试验栈与队列的扩展应用在做好实验栈队列的基础上熟练掌握栈和队列基本性质及基本操作显得很必要。
实验中需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。
输入数据按达到或离去的时刻有序。
栈中每个元素表示一辆汽车，包括两个数据项：
汽车的牌照号码和进入停车场的时刻。
五、测试结果
六、附录（源程序）
1、#include<
stdio.h>
#include<
malloc.h>
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefintelemtype;
typedefintstatus;
typedefstructQNode{
elemtypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
typedefstructlnode{
structlnode*next;
}stacknode,*linkstack;
statusinitstack（linkstacktop）{
top->
next=NULL;
}
statusisempty（linkstacktop）{
if（top->
next==NULL）returnOK;
returnERROR;
statuspush（linkstacktop,elemtypee）{
stacknode*p;
p=（stacknode*）malloc（sizeof（stacknode））;
if（p==NULL）returnERROR;
p->
data=e;
next=top->
next;
next=p;
returnOK;
statuspop（linkstacktop,elemtype*e）{
if（isempty（top））returnERROR;
stacknode*p=top->
*e=p->
data;
next=p->
free（p）;
statusshstack（linkstacktop）{
next=top->
while（p->
next!
=NULL）{
printf（"
%d"
p->
next->
data）;
next=p->
}
statusinitqueue（LinkQueue*q）{
（*q）.front=（*q）.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
（*q）.front）exit（OVERFLOW）;
（*q）.front->
next=NULL;
statusenqueue（LinkQueue*q,elemtypee）{
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）exit（OVERFLOW）;
data=e;
（*q）.rear->
next=p;
（*q）.rear=p;
statusdequeue（LinkQueue*q,elemtype*e）{
if（（*q）.front==（*q）.rear）returnERROR;
QueuePtrp;
p=（*q）.front->
*e=p->
//注意
if（（*q）.rear==p）（*q）.rear==（*q）.front;
voidmain（）
{
linkstacks;
s=（linkstack）malloc（sizeof（stacknode））;
initstack（s）;
进入栈的4个元素依次为：
\n"
）;
for（inti=0;
i<
4;
i++）
{
elemtypea;
scanf（"
%d"
&
a）;
push（s,a）;
\n栈顶到栈底的元素依次为；
shstack（s）;
elemtypeb,c,d;
pop（s,&
b）;
c）;
d）;
push（s,b）;
\n\n出栈的元素为:
"
c）;
%d\n"
d）;
\n现在栈中的元素为：
LinkQueueq;
initqueue（&
q）;
elemtypea;
\n\n\n请输入5个进队的元素:
for（inti=0;
5;
scanf（"
enqueue（&
q,a）;
\n元素的出列为:
elemtypee;
dequeue（&
q,&
e）;
printf（"
%d"
e）;
}
2、#include<
stdlib.h>
string.h>
#defineSTACK_INIT_SIZE1
typedefintStatus;
typedefstruct{
charnum[10];
inttime;
}SElemType;
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
intlength;
StatusInitStack（SqStack&
S）{
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
S.base）exit（OVERFLOW）;
S.top=S.base;
S.stacksize=0;
}//InitStack
StatusPush（SqStack&
S,SElemTypee）{
*S.top++=e;
S.stacksize++;
}//Push
StatusPop（SqStack&
S,SElemType&
e）{
///SElemTypee;
if（S.top==S.base）{
Nocarinthepark!
return（ERROR）;
e=*--S.top;
S.stacksize--;
}//Pop
StatusInitQueue（LinkQueue&
Q）{
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
Q.front）exit（OVERFLOW）;
Q.front->
Q.length=0;
}//InitQueue
StatusEnQueue（LinkQueue&
Q,chare_n[10],inte_t）{
inti;
p=（QueuePtr）malloc（sizeof（QNode））;
for（i=0;
i<
10;
i++）
num[i]=e_n[i];
time=e_t;
Q.rear->
Q.rear=p;
Q.length++;
}//EnQueue
StatusDeQueue（LinkQueue&
Q,chare_n[10],int&
e_t）{
if（Q.front==Q.rear）{
Nocarintheway!
p=Q.front->
e_n[i]=p->
num[i];
e_t=p->
time;
Q.length--;
if（Q.rear==p）
Q.rear=Q.front;
}//DeQueue
voidarrive（SqStack&
S,LinkQueue&
Q,SElemTypee,intn）{
if（S.stacksize<
n）{
Push（S,e）;
Thecarnumber-%sparkintheparkNo.%dlane\n"
e.num,S.stacksize）;
**************************************************\n"
else{
EnQueue（Q,e.num,e.time）;
Carparkisfull!
\nThecarnum-%sparkinthesidewalkNo.%dlane\n"
e.num,Q.length）;
}//arrive
voiddepart（SqStack&
Q,SElemTypee,floatfee,intn）{
SqStackST;
SElemTypex,y;
charz_n[10];
intz_t;
intflag=0;
floatcost;
InitStack（ST）;
while（!
flag）{
Pop（S,x）;
Push（ST,x）;
strcmp（x.num,e.num））{
flag=1;
cost=（e.time-x.time）*fee;
Pop（ST,y）;
while（ST.stacksize）{
Push（S,y）;
n&
&
Q.length!
=0）
DeQueue（Q,z_n,z_t）;
y.num[i]=z_n[i];
y.time=z_t;
Thecarnum-%sparktotheprakNo.%dlanefromsidewalk.\n"
y.num,S.stacksize）;
--------------------------------------------------\n"
|car_num|A_time|D_time|L_time|Cost|\n"
|%-10s|%-6d|%-6d|%-6d|%-6.2f|\n"
e.num,x.time,e.time,e.time-x.time,cost）;
voidmain（）{
intn;
floatfee;
charsign;
SqStackS;
LinkQueueQ;
SElemTypee;
InitQueue（Q）;
Inputthecapacityoftheparks:
n）;
getchar（）;
Inputthefees（RMB/h）:
%f"
fee）;
\nInputcarsinformation:
\na/A-Arrived/D-Departe/E-Endcar_numbertime\n"
InitStack（S））
StackFail!
\nInputA/D/E,carnumber,time:
do{
%c%s%d"
sign,e.num,&
e.time）;
switch（sign）{
case'
a'
:
A'
arrive（S,Q,e,n）;
break;
d'
D'
depart（S,Q,e,fee,n）;
e'
E'
Finish!
default:
Inputerror!
}while（sign!
='
&
sign!
}//else
}//main
升级会员 