数据结构（c语言版）程海英-上机3

《数据结构（c语言版）程海英-上机3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、上机3栈与队列的应用1•问题描述栈是限制为仅仅能在表的一端插人和删除的线性表，是生活屮某些过程的抽象。插人删除的一端称为栈顶(top),插人操作通常称为进栈或者人栈(push)o不能插人删除的一端称为栈底(bottom),删除操作通常称为出栈或者退栈(pop)。栈有着后进先出(ListInFirstOut-LIFO)的特性，也称为后进先出表。使用顺序结构来表示一个栈。队列是限制为仅仅能在表的一端插人和另一端删除的线性表，是生活屮排队的抽象。插入的一端称为队尾(reaij,插人操作称进队(Enqueue)；删除的一端称为队头(front),删除操作称出队(Dequeue

2、)o队列是有着先进先出(FirstInFirstOut-FIFO)的特性，也称为先进先出表。采用顺序结构来实现的队列为顺序队列。2•数据结构设计顺序栈的数据类型：#defineMaxSize100typedefstruct{ElemTypedata[MaxSize];inttop;}SeqStack;顺序循环队列的数据类型：#defineMaxSize100typedefstruct{ElemTypedata[MaxSize];intfront;intrear;〃最大元素个数〃顺序栈的类型定义〃栈元素存储空间〃栈顶指针〃最大元素个数〃循环顺序队的类型定义〃队列元素存储

3、空间〃队头指针〃队尾指针}CircSeqQueue;3•函数说明顺序栈的基木操作:Stackinitial(SeqStack*pS)isEmpty(SeqStack*pS)〃创建一个由指针pS所指向的空顺序栈〃顺序栈为空吋返冋isFull(SeqStack*pS)〃栈满时返回Push(SeqStack*pS,ElemTypee)〃若栈不满，则元素e进栈Pop(SeqStack*pS)〃若栈不为空，则删除找顶元素，并返冋它的值GetTop(SeqStack*pS)〃若栈不为空，则返回栈顶元素的值MakeEmpty(SeqStack*pS)循环顺序队基本操作：〃将由指针p

4、S所指向的栈置空QueueInitial(CircSeqQueue*pQ)//创建一个由指针pQ所指向的空队列isEmpty(CircSeqQueue*pQ)〃循环顺序队为空吋返冋1,否则返冋0isFull(CircSeqQueue*pQ)〃循环队列为满时返冋1,否则返冋0EnQueue(CircSeqQueue*pQ,ElemTypee)〃若队列不满，则元素e进队DeQueue(CircSeqQueue*pQ)〃若循环队列不空，删除队头元素，返冋它的值GetFront(CircSeqQueue*pQ)〃若队列不为空，则返回队头元素的值MakeEmpty(CircSe

5、qQueue*pQ)//将由指针pQ所指向的队列变为空队4•编码实现#include#include#include#include#defineMaxSize100〃最大元素个数typedefintElemType;typedefstruct{ElemTypedata

6、MaxSize

7、;〃顺序栈的类型定义〃栈元素存储空间ElemTypePop(SeqStack*pS){if(isEmpty(pS)){printf(H空栈!”);〃若栈不为空，则删除栈顶元素，并返回它的值〃栈为空，退

8、出}SeqStack;typedefstruct{ElemTypedata

9、MaxSize];intfront;intrear;}CircSeqQueue;voidStackInitial(SeqStack*pS){pS->top=-1;}intisEmpty(SeqStack*pS){returnpS->top==-1;}intisFull(SeqStack*pS){returnpS->top>=MaxSize-l;}voidPush(SeqStack*pS,ElemTypee){if(isFull(pS)){printf(u栈满溢出！”)；return;}pS

10、->data

11、++pS->top]=e;〃循环顺序队的类型定义〃队列元素存储空间〃队头指针〃队尾指针〃创建一个由指针pS所指向的空栈〃顺序栈为空吋返回1,否则返回。〃栈为满吋返回1,否则返回0〃若栈不满，则元素e进栈〃栈已满，退出return0;returnpS->data

12、pS->top-・];}ElemTypeGetTop(SeqStack*pS){//若栈不为空，则返回栈顶元素的值if(isEmpty(pS)){〃栈为空，退出printf(”空栈”)；return0;}returnpS->data

13、pS->top

14、;}voidMakeEmp