数据结构栈和队列

本文格式为Word版，下载可任意编辑——数据结构栈和队列

试验二栈和队列

一、试验目的

1.把握栈的顺序表示和实现2.把握队列的链式表示和实现二、试验内容

1.编写一个程序实现顺序栈的各种基本运算。2.实现队列的链式表示和实现。三、试验步骤

1.初始化顺序栈2.插入元素3.删除栈顶元素4.取栈顶元素5.遍历顺序栈6.置空顺序栈7.初始化并建立链队列8.入链队列9.出链队列10.遍历链队列四、实现提醒

1./*定义顺序栈的存储结构*/typedefstruct{

ElemTypestack[MAXNUM];inttop;}SqStack;

/*初始化顺序栈函数*/voidInitStack(SqStack*p)

{q=(SqStack*)malloc(sizeof(SqStack)/*申请空间*/)/*入栈函数*/

voidPush(SqStack*p,ElemTypex)

{if(p->toptop=p->top+1;/*栈顶+1*/p->stack[p->top]=x;}/*数据入栈*/}

/*出栈函数*/

ElemTypePop(SqStack*p)

{x=p->stack[p->top];/*将栈顶元素赋给x*/p->top=p->top-1;}/*栈顶-1*//*获取栈顶元素函数*/ElemTypeGetTop(SqStack*p){x=p->stack[p->top];}/*遍历顺序栈函数*/voidOutStack(SqStack*p){for(i=p->top;i>=0;i--)

printf(\第%d个数据元素是：m\\n\/*置空顺序栈函数*/voidsetEmpty(SqStack*p){p->top=-1;}2./*定义链队列*/typedefstructQnode{ElemTypedata;structQnode*next;}Qnodetype;typedefstruct{Qnodetype*front;Qnodetype*rear;}Lqueue;

/*初始化并建立链队列函数*/voidcreat(Lqueue*q)

{h=(Qnodetype*)malloc(sizeof(Qnodetype));/*初始化申请空间*/h->next=NULL;q->front=h;q->rear=h;

for(i=1;idata=x;s->next=NULL;q->rear->next=s;q->rear=s;}/*出链队列函数*/

ElemTypeLdelete(Lqueue*q){p=q->front->next;q->front->next=p->next;if(p->next==NULL)q->rear=q->front;x=p->data;

free(p);}/*释放空间*//*遍历链队列函数*/voiddisplay(Lqueue*q)

{while(p!=NULL)/*利用条件判断是否到队尾*/{printf(\p=p->next;}}

五、思考与提高

1.读栈顶元素的算法与退栈顶元素的算法有何区别？

2.假使一个程序中要用到两个栈，为了不发生上溢错误，就必需给每个栈预先分派一个足够大的存储空间。若每个栈都预分派过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？

（1）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？

（2）一个程序中假使要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。假使一个程序中要用到两个队列，能否实现？如何实现？

六、完整参考程序1.栈的顺序表示和实现

#include#include#include

#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2

typedefintStatus;typedefintSElemType;

//栈的顺序存储表示#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10

typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;

StatusInitStack(SqStackStatusDestroyStack(SqStackStatusStackDisplay(SqStackStatusGetTop(SqStackS,SElemTypeStatusPush(SqStackStatusPop(SqStackStatusStackEmpty(SqStackS);

StatusInitStack(SqStackif(!S.base)exit(OVERFLOW);//存储分派失效S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;

}//InitStack

StatusDestroyStack(SqStackS.top=S.base=NULL;returnOK;

}//InitStack

StatusStackDisplay(SqStack

inti=0;

if(S.base==S.top){printf(\堆栈已空!\\n\returnOK;}

while(p#include#include#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2

//Status是函数的类型,其值是函数结果状态代码typedefintStatus;

//ElemType是顺序表数据元素类型,此程序定义为int型typedefintQElemType;

//单链队列--队列的链式存储结构typedefstructQNode{//定义结点结构

QElemTypedata;//数据域structQNode*next;//指针域

}QNode,*QueuePtr;

typedefstructlinkqueue{//定义队列结构

QueuePtrfront;//队头指针QueuePtrrear;//队尾指针

}LinkQueue;

StatusInitLinkQueue(LinkQueue//初始化一个队列StatusDestroyLinkQueue(LinkQueue//销毁一个队列intLinkQueueLength(LinkQueue//队列的长度StatusEnLinkQueue(LinkQueue//将一个元素入队列StatusDeLinkQueue(LinkQueue//将一个元素出队列StatusDisplayLinkQueue(LinkQueue);//显示队列中所有元素

voidmain(){

LinkQueueLQ;QElemTypee;intflag=1,ch,len;Statustemp;

printf(\本程序实现链式结构队列的操作。\\n\printf(\可以进行入队列、出队列等操作。\\n\InitLinkQueue(LQ);//初始化队列while(flag){

printf(\请选择:\\n\

printf(\显示队列所有元素\\n\printf(\入队列\\n\printf(\出队列\\n\printf(\求队列的长度\\n\printf(\退出程序\\n\scanf(\switch(ch){

}}

case1:DisplayLinkQueue(LQ);//显示队列中所有元素

break;

case2:printf(\请输入要人队的元素(一个整数):\

scanf(\//输入要入队列的字符EnLinkQueue(LQ,e);//入队列DisplayLinkQueue(LQ);break;

case3:temp=DeLinkQueue(LQ,e);//出队列

if(temp==OK){}

elseprintf(\队列为空!\\n\break;

printf(\出队一个元素:%d\\n\DisplayLinkQueue(LQ);

case4:len=LinkQueueLength(LQ);

printf(\队列的长度为:%d\\n\break;

default:flag=0;}

printf(\程序运行终止，按任意键退出!\\n\getch();

StatusInitLinkQueue(LinkQueue//生成一个头结点，并

把首尾指针指向头结点

}

Q.front->next=NULL;returnOK;

StatusDestroyLinkQueue(LinkQueue

p=(QueuePtr)malloc(sizeof(QNode));//生成一个新结点p->data=e;//赋值p->next=NULL;

Q.rear->next=p;//插入至队列尾Q.rear=p;//修改队尾指针returnOK;inti=0;

QueuePtrp=Q.front;while(p!=Q.rear){}returni;

++i;p=p->next;QueuePtrp;QElemTypee;while(Q.front!=Q.rear)

DeLinkQueue(Q,e);

free(Q.front);Q.front=Q.rear=NULL;returnOK;

StatusDeLinkQueue(LinkQueue

if(Q.front==Q.rear)returnERROR;//判断队列是否已空，已空返回

p=Q.front->next;//p指向队列中第一个元素e=p->data;//取得该元素值Q.front->next=p->next;//修改队首指针

if(Q