实验二 栈和队列(基本操作)

1实验二栈和队列1、实验目的：（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。2、实验要求：（1）复习课本中有关栈和队列的知识；（2）用C语言完成算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。3、实验内容[实验1]栈的顺序表示和实现实验内容与要求:编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历顺序栈（6）置空顺序栈分析:栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p-top==MAXNUM-1，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。注意：（1）顺序栈中元素用向量存放（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置#includestdio.h#includemalloc.htypedefintSElemType;typedefintStatus;#defineINIT_SIZE1002#defineSTACKINCREMENT10#defineOk1#defineError0#defineTrue1#defineFalse0typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;//初始化栈StatusInitStack(SqStack*s){s-base=(SElemType*)malloc(INIT_SIZE*sizeof(SElemType));if(!s-base){puts(存储空间分配失败！);returnError;}s-top=s-base;s-stacksize=INIT_SIZE;returnOk;}//清空栈StatusClearStack(SqStack*s){s-top=s-base;returnOk;}//栈是否为空StatusStackEmpty(SqStack*s){if(s-top==s-base)returnTrue;elsereturnFalse;}//销毁栈StatusDestroy(SqStack*s)3{free(s-base);s-base=NULL;s-top=NULL;s-stacksize=0;returnOk;}//获得栈顶元素StatusGetTop(SqStack*s,SElemType&e){if(s-top==s-base)returnError;e=*(s-top-1);returnOk;}//压栈StatusPush(SqStack*s,SElemTypee){if(s-top-s-base=s-stacksize){s-base=(SElemType*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s-base){puts(存储空间分配失败！);returnError;}s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;}*s-top++=e;returnOk;}//弹栈StatusPop(SqStack*s,SElemType*e){if(s-top==s-base)returnError;--s-top;*e=*(s-top);returnOk;}4//遍历栈StatusStackTraverse(SqStack*s,Status(*visit)(SElemType)){SElemType*b=s-base;SElemType*t=s-top;while(tb)visit(*b++);printf(\n);returnOk;}Statusvisit(SElemTypec){printf(%d,c);returnOk;}intmain(){SqStacka;SqStack*s=&a;SElemTypee;InitStack(s);intn;puts(请输入要进栈的个数：);scanf(%d,&n);while(n--){intm;scanf(%d,&m);Push(s,m);}StackTraverse(s,visit);puts();Pop(s,&e);printf(%d\n,e);printf(%d\n,*s-top);Destroy(s);return0;}5[实验2]栈的链式表示和实现实验内容与要求:编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化链栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈分析:链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。注意：（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。（3）链栈中的结点是动态分配的，所以可以不考虑上溢。#includestdio.h#includemalloc.h#defineERROR0#defineOK1#defineTRUE1#defineFALSE0typedefintElemType;typedefintStatus;typedefstructnode{ElemTypedata;structnode*next;}StackNode;typedefstruct{StackNode*top;}LinkStack;//初始化voidInitStack(LinkStack*s){s-top=NULL;puts(链栈初始化完成！);}6//将链栈置空StatusSetEmpty(LinkStack*s){StackNode*p=s-top;while(p){s-top=p-next;free(p);p=s-top;}puts(链栈已置空！);returnOK;}//压栈StatusPush(LinkStack*s,ElemTypee){StackNode*p;p=(StackNode*)malloc(sizeof(StackNode));p-data=e;p-next=s-top;s-top=p;returnOK;}//弹栈StatusPop(LinkStack*s,ElemType&e){StackNode*p=s-top;if(s-top==NULL){puts(栈空,不能进行弹栈操作!);returnERROR;}s-top=p-next;e=p-data;free(p);returnOK;}//打印栈StatusPrintStack(LinkStack*s){7StackNode*p;p=s-top;while(p){printf(%d,p-data);p=p-next;}puts();returnOK;}intmain(){LinkStacks;InitStack(&s);intn;printf(请输入链栈长度:\n);scanf(%d,&n);puts(请输入要录入的数据:);while(n--){intx;scanf(%d,&x);Push(&s,x);}PrintStack(&s);SetEmpty(&s);return0;}[实验3]队列的顺序表示和实现实验内容与要求编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列（2）建立顺序队列（3）入队（4）出队（5）判断队列是否为空（6）取队头元素（7）遍历队列分析:队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。8入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。顺序队列中的溢出现象：（1）下溢现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。（2）真上溢现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。（3）假上溢现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。注意：（1）当头尾指针相等时，队列为空。（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。#includestdio.h#includemalloc.htypedefintQElemType;typedefintStatus;#defineMaxQSize10#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1typedefstruct{QElemType*base;intfront,rear;}SqQueue;//初始化循环队列intInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MaxQSize*sizeof(QElemType));if(Q.base==NULL){puts(分配内存空间失败！);exit(OVERFLOW);}Q.front=Q.rear=0;return0;}//将循环队列清空intClearQueue(SqQueue&Q){Q.front=Q.rear=0;9}//求队列元素的个数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;//修改队尾指针returnOK;}//从循环队列中删除元素intDeSqQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];//取队头元素至eQ.front=(Q.front+1)%MaxQSize;//修改队头指针,如果超内存，循环returnOK;}//判断一个循环队列是否为空队列intisQueueEmpty(SqQueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}intmain(){inti,e;SqQueueQ;InitQueue(Q);for(i=0;iMaxQSize-1;i++)//只有MaxQSize个数据进队列EnSqQueue(Q,i);i=QueueLength(Q);printf(队列里的元素有%d个\n,i);for(i=0;i3;i++){10DeSqQueue(Q,e);printf(%d,e);}printf(\n