实验二栈和队列(基本操作)讲解文档格式.doc
《实验二栈和队列(基本操作)讲解文档格式.doc》由会员分享，可在线阅读，更多相关《实验二栈和队列(基本操作)讲解文档格式.doc（13页珍藏版）》请在冰点文库上搜索。
typedefstruct
{
SElemType*base;
SElemType*top;
intstacksize;
}SqStack;
//初始化栈
StatusInitStack（SqStack*s）
s->
base=（SElemType*）malloc（INIT_SIZE*sizeof（SElemType））;
if（!
s->
base）
{
puts（"
存储空间分配失败！
"
）;
returnError;
}
top=s->
base;
stacksize=INIT_SIZE;
returnOk;
}
//清空栈
StatusClearStack（SqStack*s）
{
s->
returnOk;
}
//栈是否为空
StatusStackEmpty（SqStack*s）
if（s->
top==s->
returnTrue;
else
returnFalse;
//销毁栈
StatusDestroy（SqStack*s）
free（s->
base）;
base=NULL;
top=NULL;
stacksize=0;
//获得栈顶元素
StatusGetTop（SqStack*s,SElemType&
e）
if（s->
base）returnError;
e=*（s->
top-1）;
//压栈
StatusPush（SqStack*s,SElemTypee）
top-s->
base>
=s->
stacksize）
s->
base=（SElemType*）realloc（s->
base,（s->
stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
{
puts（"
returnError;
}
base+s->
stacksize;
stacksize+=STACKINCREMENT;
*s->
top++=e;
//弹栈
StatusPop（SqStack*s,SElemType*e）
--s->
top;
*e=*（s->
top）;
//遍历栈
StatusStackTraverse（SqStack*s,Status（*visit）（SElemType））
SElemType*b=s->
SElemType*t=s->
while（t>
b）
visit（*b++）;
printf（"
\n"
Statusvisit（SElemTypec）
%d"
c）;
intmain（）
SqStacka;
SqStack*s=&
a;
SElemTypee;
InitStack（s）;
intn;
puts（"
请输入要进栈的个数：
scanf（"
%d"
&
n）;
while（n--）
intm;
scanf（"
m）;
Push（s,m）;
StackTraverse（s,visit）;
Pop（s,&
e）;
printf（"
%d\n"
e）;
*s->
Destroy（s）;
return0;
[实验2]栈的链式表示和实现
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化链栈
（2）链栈置空
（3）入栈
（4）出栈
（5）取栈顶元素
（6）遍历链栈
链栈是没有附加头结点的运算受限的单链表。
栈顶指针就是链表的头指针。
（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。
（3）链栈中的结点是动态分配的，所以可以不考虑上溢。
#defineERROR0
#defineOK1
#defineTRUE1
#defineFALSE0
typedefintElemType;
typedefstructnode
ElemTypedata;
structnode*next;
}StackNode;
StackNode*top;
}LinkStack;
//初始化
voidInitStack（LinkStack*s）
链栈初始化完成！
//将链栈置空
StatusSetEmpty（LinkStack*s）
StackNode*p=s->
while（p）
top=p->
next;
free（p）;
p=s->
链栈已置空！
returnOK;
StatusPush（LinkStack*s,ElemTypee）
StackNode*p;
p=（StackNode*）malloc（sizeof（StackNode））;
p->
data=e;
next=s->
top=p;
StatusPop（LinkStack*s,ElemType&
top==NULL）
栈空,不能进行弹栈操作!
returnERROR;
e=p->
data;
free（p）;
//打印栈
StatusPrintStack（LinkStack*s）
p=s->
printf（"
%d"
p->
data）;
p=p->
LinkStacks;
InitStack（&
s）;
请输入链栈长度:
请输入要录入的数据:
intx;
x）;
Push（&
s,x）;
PrintStack（&
SetEmpty（&
[实验3]队列的顺序表示和实现
实验内容与要求
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
（7）遍历队列
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear所指的位置，然后将rear加1。
出队时，删去front所指的元素，然后将front加1并返回被删元素。
顺序队列中的溢出现象：
（1）"
下溢"
现象。
当队列为空时，做出队运算产生的溢出现象。
“下溢”是正常现象，常用作程序控制转移的条件。
（2）"
真上溢"
当队列满时，做进栈运算产生空间溢出的现象。
“真上溢”是一种出错状态，应设法避免。
（3）"
假上溢"
由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。
当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
该现象称为"
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
typedefintQElemType;
#defineMaxQSize10
#defineOVERFLOW-1
QElemType*base;
intfront,rear;
}SqQueue;
//初始化循环队列
intInitQueue（SqQueue&
Q）
Q.base=（QElemType*）malloc（MaxQSize*sizeof（QElemType））;
if（Q.base==NULL）
分配内存空间失败！
exit（OVERFLOW）;
Q.front=Q.rear=0;
//将循环队列清空
intClearQueue（SqQueue&
//求队列元素的个数
intQueueLength（SqQueueQ）
return（Q.rear-Q.front+MaxQSize）%MaxQSize;
//插入元素到循环队列
intEnSqQueue（SqQueue&
Q,QElemTypee）
if（（Q.rear+1）%MaxQSize==Q.front）
returnERROR;
//队列满
Q.base[Q.rear]=e;
//元素e入队
Q.rear=（Q.rear+1）%MaxQSize;
//修改队尾指针
//从循环队列中删除元素
intDeSqQueue（SqQueue&
Q,QElemType&
if（Q.front==Q.rear）
e=Q.base[Q.front];
//取队头元素至e
Q.front=（Q.front+1）%MaxQSize;
//修改队头指针,如果超内存，循环
//判断一个循环队列是否为空队列
intisQueueEmpty（SqQueueQ）
returnTRUE;
else
returnFALSE;
inti,e;
SqQueueQ;
InitQueue（Q）;
for（i=0;
i<
MaxQSize-1;
i++） //只有MaxQSize个数据进队列
EnSqQueue（Q,i）;
i=QueueLength（Q）;
队列里的元素有%d个\n"
i）;
3;
i++）
DeSqQueue（Q,e）;
for（i=10;
12;
ClearQueue（Q）;
[实验4[队列的链式表示和实现
编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化并建立链队列
（2）入链队列
（3）出链队列
（4）遍历链队列
队列的链式存储结构简称为链队列。
它是限制仅在表头删除和表尾插入的单链表。
（1）和链栈类似，无须考虑判队满的运算及上溢。
（2）在出队算法中，一般只需修改队头指针。
但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。
typedefstructNode
structNode*next;
}Node;
Node*front;
Node*rear;
}LinkQueue;
StatusInitQueue（LinkQueue*q）
q->
front=NULL;
rear=NULL;
}//InitQueue
StatusDestroyQueue（LinkQueue*q）
Node*p=q->
front;
while（p）
{
q->
front=p->
free（p）;
p=q->
}
puts（"
队列已销毁！
returnOK;
boolisEmpty（LinkQueue*q）
if（q->
front==NULL&
&
q->
rear==NULL）
returnTRUE;
returnFALSE;
}//isEmpty
StatusPush（LinkQueue*q,ElemTypee）
Node*p=（Node*）malloc（sizeof（Node））;
p）
存储空间分配失败!
next=NULL;
//防止出现野指针
if（isEmpty（q））//如果是空队列，则front指向p（第一个元素）
q->
front=p;
q->
rear->
next=p;
rear=p;
//q->
rear指向队尾
}//Push
StatusPop（LinkQueue*q,ElemType*e）
if（isEmpty（q））
puts（"
队列为空！
returnERROR;
*e=p->
q->
free（p）;
front==NULL）//如果出队列后队列空了，则q->
rear应指向NULL，
}//Pop
StatuscreateQueue（LinkQueue*q）
InitQueue（q）;
请输入要输入的队列元素个数：
intn;
scanf（"
while（n--）
intm;
scanf（"
Push（q,m）;
}//createQueue
StatusPrintQueue（LinkQueue*q）
队列中有以下元素:
printf（"
p=p->
LinkQueueq;
inte;
createQueue（&
q）;
PrintQueue（&
Pop（&
q,&
出队列的元素是：
printf（"
Push（&
q,8）;
8进队列后：
DestroyQueue（&
13
升级会员 