实验二栈和队列基本操作讲解Word文档格式.docx
- 文档编号:6996933
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:21
- 大小:18.88KB
实验二栈和队列基本操作讲解Word文档格式.docx
《实验二栈和队列基本操作讲解Word文档格式.docx》由会员分享,可在线阅读,更多相关《实验二栈和队列基本操作讲解Word文档格式.docx(21页珍藏版)》请在冰点文库上搜索。
#defineOk1
#defineError0
#defineTrue1
#defineFalse0
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)
//栈是否为空
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)
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);
%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("
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;
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;
front=p->
p=q->
队列已销毁!
boolisEmpty(LinkQueue*q)
if(q->
front==NULL&
&
rear==NULL)
}//isEmpty
StatusPush(LinkQueue*q,ElemTypee)
Node*p=(Node*)malloc(sizeof(Node));
p)
存储空间分配失败!
next=NULL;
//防止出现野指针
if(isEmpty(q))//如果是空队列,则front指向p(第一个元素)
front=p;
rear->
next=p;
rear=p;
//q->
rear指向队尾
}//Push
StatusPop(LinkQueue*q,ElemType*e)
if(isEmpty(q))
队列为空!
*e=p->
front==NULL)//如果出队列后队列空了,则q->
rear应指向NULL,
}//Pop
StatuscreateQueue(LinkQueue*q)
InitQueue(q);
请输入要输入的队列元素个数:
intm;
Push(q,m);
}//createQueue
StatusPrintQueue(LinkQueue*q)
队列中有以下元素:
p=p->
LinkQueueq;
inte;
createQueue(&
q);
PrintQueue(&
Pop(&
q,&
出队列的元素是:
Push(&
q,8);
8进队列后:
DestroyQueue(&
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 队列 基本 操作 讲解