用顺序结构表示栈并实现栈的各种基本操作文档格式.docx
《用顺序结构表示栈并实现栈的各种基本操作文档格式.docx》由会员分享，可在线阅读，更多相关《用顺序结构表示栈并实现栈的各种基本操作文档格式.docx（21页珍藏版）》请在冰点文库上搜索。
{p->
top=p->
top+1;
/*栈顶+1*/
p->
stack[p->
top]=x;
}/*数据入栈*/
}
/*出栈函数*/
ElemTypePop（SqStack*p）
{x=p->
top];
/*将栈顶元素赋给x*/
top-1;
}/*栈顶-1*/
/*获取栈顶元素函数*/
ElemTypeGetTop（SqStack*p）
{x=p->
/*遍历顺序栈函数*/
voidOutStack（SqStack*p）
{for（i=p->
top;
i>
=0;
i--）
printf（"
第%d个数据元素是：
%6d\n"
i,p->
stack[i]）;
/*置空顺序栈函数*/
voidsetEmpty（SqStack*p）
{p->
top=-1;
【参考程序】
#include<
>
#defineMAXNUM20
#defineElemTypeint
typedefstruct
{ElemTypestack[MAXNUM];
/*初始化顺序栈*/
{if（!
p）
printf（"
Eorror"
）;
top=-1;
/*入栈*/
{if（p->
{p->
}
else
Overflow!
\n"
/*出栈*/
{ElemTypex;
if（p->
top!
=0）
{x=p->
以前的栈顶数据元素%d已经被删除！
p->
top]）;
return（x）;
{printf（"
Underflow!
return（0）;
/*获取栈顶元素*/
/*遍历顺序栈*/
{inti;
0）
这是一个空栈！
"
for（i=p->
/*置空顺序栈*/
{
/*主函数*/
main（）
{SqStack*q;
inty,cord;
ElemTypea;
do{
第一次使用必须初始化！
\n主菜单\n"
\n1初始化顺序栈\n"
\n2插入一个元素\n"
\n3删除栈顶元素\n"
\n4取栈顶元素\n"
\n5置空顺序栈\n"
\n6结束程序运行\n"
\n--------------------------------\n"
请输入您的选择（1,2,3,4,5,6）"
scanf（"
%d"
&
cord）;
switch（cord）
{case1:
{q=（SqStack*）malloc（sizeof（SqStack））;
InitStack（q）;
OutStack（q）;
}break;
case2:
请输入要插入的数据元素：
a="
a）;
Push（q,a）;
case3:
{Pop（q）;
case4:
{y=GetTop（q）;
\n栈顶元素为：
%d\n"
y）;
case5:
{setEmpty（q）;
\n顺序栈被置空！
case6:
exit（0）;
}while（cord<
=6）;
【思考与提高】
（1）读栈顶元素的算法与退栈顶元素的算法有何区别？
（2）如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。
若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。
如何解决这个问题？
实验二：
栈的链式表示和实现
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化链栈
（2）链栈置空
（3）入栈
（4）出栈
（5）取栈顶元素
（6）遍历链栈
链栈是没有附加头结点的运算受限的单链表。
栈顶指针就是链表的头指针。
（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。
（3）链栈中的结点是动态分配的，所以可以不考虑上溢。
typedefintElemtype;
typedefstructstacknode{
Elemtypedata;
stacknode*next;
}StackNode;
/*定义链栈*/
stacknode*top;
//栈顶指针
}LinkStack;
/*初始化链栈函数*/
voidInitStack（LinkStack*s）
{s=（LinkStack*）malloc（sizeof（LinkStack））;
/*初始化申请空间*/
s->
top=NULL;
/*链栈置空函数*/
voidsetEmpty（LinkStack*s）
{s->
voidpushLstack（LinkStack*s,Elemtypex）
{p=（StackNode*）malloc（sizeof（StackNode））;
//建立一个节点。
data=x;
next=s->
//指向栈顶。
s->
top=p;
//插入
ElemtypepopLstack（LinkStack*s）
data;
next;
//当前的栈顶指向原栈的next
free（p）;
//释放
/*取栈顶元素函数*/
ElemtypeStackTop（LinkStack*s）
{returns->
top->
/*遍历链栈函数*/
voidDisp（LinkStack*s）
{while（p!
=NULL）
data）;
p=p->
#include"
/*初始化链栈*/
\n已经初始化链栈！
/*链栈置空*/
\n链栈被置空！
{StackNode*p;
p=（StackNode*）malloc（sizeof（StackNode））;
//由于是在栈顶pushLstack，所以要指向栈顶。
{Elemtypex;
StackNode*p;
p=s->
//指向栈顶
if（s->
top==0）
\n栈空，不能出栈！
exit（-1）;
x=p->
returnx;
/*取栈顶元素*/
{if（s->
\n链栈空\n"
returns->
/*遍历链栈*/
{printf（"
\n链栈中的数据为：
=======================================\n"
while（p!
voidmain（）
=================链栈操作=================\n\n"
inti,m,n,a;
LinkStack*s;
s=（LinkStack*）malloc（sizeof（LinkStack））;
intcord;
do{printf（"
\n1初始化链栈\n"
\n2入栈\n"
\n3出栈\n"
\n5置空链栈\n"
{InitStack（s）;
Disp（s）;
{printf（"
输入将要压入链栈的数据的个数：
n="
n）;
依次将%d个数据压入链栈：
n）;
for（i=1;
i<
=n;
i++）
{scanf（"
pushLstack（s,a）;
\n出栈操作开始!
输入将要出栈的数据个数：
m="
m）;
=m;
\n第%d次出栈的数据是：
i,popLstack（s））;
\n\n链栈的栈顶元素为：
StackTop（s））;
{setEmpty（s）;
（1）栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？
（2）在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？
如何实现？
实验三：
队列的顺序表示和实现
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
（7）遍历队列
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear所指的位置，然后将rear加1。
出队时，删去front所指的元素，然后将front加1并返回被删元素。
顺序队列中的溢出现象：
（1）"
下溢"
现象。
当队列为空时，做出队运算产生的溢出现象。
“下溢”是正常现象，常用作程序控制转移的条件。
（2）"
真上溢"
当队列满时，做进栈运算产生空间溢出的现象。
“真上溢”是一种出错状态，应设法避免。
（3）"
假上溢"
由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。
当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。
该现象称为"
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
/*定义队列*/
{Elemtypequeue[MAXNUM];
intfront;
intrear;
}sqqueue;
/*队列初始化函数*/
intinitQueue（sqqueue*q）
{q=（sqqueue*）malloc（sizeof（sqqueue））;
/*初始化申请空间*/
q->
front=-1;
q->
rear=-1;
/*入队函数*/
intappend（sqqueue*q,Elemtypex）
{q->
rear++;
queue[q->
rear]=x;
/*出队函数*/
ElemtypeDelete（sqqueue*q）
{x=q->
queue[++q->
front];
/*判断队列是否为空函数*/
intEmpty（sqqueue*q）
{if（q->
front==q->
rear）returnTRUE;
/*取队头元素函数*/
intgethead（sqqueue*q）
{return（q->
front+1]）;
/*遍历队列函数*/
voiddisplay（sqqueue*q）
{while（s<
rear）
{s=s+1;
%d<
-"
q->
queue[s]）;
/*建立顺序队列函数*/
voidSetsqqueue（sqqueue*q）
{for（i=0;
n;
i++）/*利用循环快速输入数据*/
{scanf（"
append（q,m）;
}}/*利用入队函数快速输入数据*/
#include<
#defineMAXNUM100
#defineElemtypeint
#defineTRUE1
#defineFALSE0
/*队列初始化*/
intinitQueue（sqqueue*q）
q）returnFALSE;
returnTRUE;
/*入队*/
intappend（sqqueue*q,Elemtypex）
{if（q->
rear>
=MAXNUM-1）returnFALSE;
/*出队*/
if（q->
rear）return0;
x=q->
/*判断队列是否为空*/
returnFALSE;
/*取队头元素*/
return（q->
/*遍历队列*/
{ints;
s=q->
front;
队列空!
\n顺序队列依次为：
while（s<
顺序队列的队尾元素所在位置:
rear=%d\n"
q->
rear）;
顺序队列的队头元素所在位置:
front=%d\n"
front）;
/*建立顺序队列*/
{intn,i,m;
\n请输入将要入顺序队列的长度:
\n请依次输入入顺序队列的元素值:
for（i=0;
}
{sqqueue*head;
intx,y,z,select;
head=（sqqueue*）malloc（sizeof（sqqueue））;
do{printf（"
\n第一次使用请初始化！
\n请选择操作（1--7）:
===================================\n"
1初始化\n"
2建立顺序队列\n"
3入队\n"
4出队\n"
5判断队列是否为空\n"
6取队头元素\n"
7遍历队列\n"
select）;
switch（select）
{case1:
{initQueue（head）;
已经初始化顺序队列！
break;
{Setsqqueue（head）;
\n已经建立队列！
display（head）;
请输入队的值:
\n"
x）;
append（head,x）;
b
升级会员 