实验二栈队列

1、实验二栈和行列1、实验目的：1）熟习栈的特色（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的次序储存构造和链式储存构造上的实现；2）熟习行列的特色（先进先出）及行列的基本操作，如入队、出队等，掌握行列的基本操作在行列的次序储存构造和链式储存构造上的实现。2、实验要求：1）复习课本中相关栈和行列的知识；2）用C语言达成算法和程序设计并上机调试经过；3）撰写实验报告，给出算法思路或流程图和详细实现（源程序）、算法剖析结果（包含时间复杂度、空间复杂度以及算法优化假想）、输入数据及程序运转结果（必需时给出多种可能的输入数据和运转结果）。3、实验内容实验1栈的次序表示和实现实验内容与要

2、求:编写一个程序实现次序栈的各样基本运算，并在此基础上设计一个主程序，达成以下功能：（1）初始化次序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历次序栈（6）置空次序栈剖析:栈的次序储存构造简称为次序栈,它是运算受限的次序表。关于次序栈，入栈时，第一判断栈能否为满，栈满的条件为：p-top=MAXNUM-，1栈满时，不可以入栈;不然出现空间溢出，惹起错误，这类现象称为上溢。出栈和读栈顶元素操作，先判栈能否为空，为空时不可以操作，不然产生错误。往常栈空作为一种控制转移的条件。注意：1）次序栈中元素用向量寄存2）栈底地点是固定不变的，可设置在向量两头的随意一个端点（3）栈顶地点是跟着

3、进栈和退栈操作而变化的，用一个整型量top（往常称top为栈顶指针）来指示目前栈顶地点#include#includetypedefintSElemType;typedefintStatus;#defineINIT_SIZE100#defineSTACKINCREMENT10#defineOk1#defineError0#defineTrue1#defineFalse0typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;初始化栈StatusInitStack(SqStack*s)s-base=(SElemType*)ma

4、lloc(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)free(s-base);s-base=NULL;s-top

5、=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

6、;);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+returnOk;=e;/弹栈StatusPop(SqStack*s,SElemType*e)if(s-top=s-base)returnError;-s-top;*e=*(s-top);returnOk;遍历栈StatusStackTraverse(SqStack*s,Status(*visit)(SElemType)SElemType*b=s-base;SElemType*t=s-top;while(tb)visit(*b+);printf(n);returnOk;

7、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(%dn,e);printf(%dn,*s-top);Destroy(s);return0;实验2栈的链式表示和实现实验内容与要求:编写一个程序实现链栈的各样基本运

8、算，并在此基础上设计一个主程序，达成以下功能：1）初始化链栈2）链栈置空3）入栈4）出栈5）取栈顶元素6）遍历链栈剖析:链栈是没有附带头结点的运算受限的单链表。栈顶指针就是链表的头指针。注意：（1）LinkStack构造种类的定义能够方便地在函数体中改正top（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack（3）链栈中的结点是动向分派的，因此能够不考虑上溢。指针自己种类中定义。#include#include#defineERROR0#defineOK1#defineTRUE1#defineFALSE0typedefintElemType;typedefintStatus;t

9、ypedefstructnodeElemTypedata;structnode*next;StackNode;typedefstructStackNode*top;LinkStack;初始化voidInitStack(LinkStack*s)s-top=NULL;puts(链栈初始化达成！);将链栈置空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

10、*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)StackNode*p;p=s-top;while(p)printf(%d,p-data);p=p

11、-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）遍历行列剖析:行列的次序储

12、存构造称为次序行列，次序行列其实是运算受限的次序表。入队时，将新元素插入rear所指的地点，而后将rear加1。出队时，删去front所指的元素，而后将front加1并返回被删元素。次序行列中的溢出现象：1）下溢现象。当行列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。2）真上溢现象。当行列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种犯错状态，应想法防止。3）假上溢现象。因为入队和出队操作中，头尾指针只增添不减小，以致被删元素的空间永久没法从头利用。当行列中实质的元素个数远远小于向量空间的规模时，也可能因为尾指针已超越向量空间的上界而不可以做入队操作。

13、该现象称为假上溢现象。注意：1）当头尾指针相等时，行列为空。2）在非空行列里，队头指针一直指向队头元素，尾指针一直指向队尾元素的下一地点。#include#includetypedefintQElemType;typedefintStatus;#defineMaxQSize10#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1typedefstructQElemType*base;intfront,rear;SqQueue;初始化循环行列intInitQueue(SqQueue&Q)(QElemType*)mall

14、oc(MaxQSize*sizeof(QElemType);if=NULL)puts(分派内存空间失败！);exit(OVERFLOW);=0;return0;将循环行列清空intClearQueue(SqQueue&Q)=0;求行列元素的个数intQueueLength(SqQueueQ)return-+MaxQSize)%MaxQSize;插入元素到循环行列intEnSqQueue(SqQueue&Q,QElemTypee)if(+1)%MaxQSize=returnERROR;/行列满=e;/元素e入队=+1)%MaxQSize;/改正队尾指针returnOK;从循环行列中删除元素int

15、DeSqQueue(SqQueue&Q,QElemType&e)if=returnERROR;e=;/取队头元素至e=+1)%MaxQSize;/改正队头指针,假如超内存，循环returnOK;判断一个循环行列能否为空行列intisQueueEmpty(SqQueueQ)if=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);fo

16、r(i=0;i3;i+)DeSqQueue(Q,e);printf(%d,e);printf(n);i=QueueLength(Q);printf(行列里的元素有%d个n,i);for(i=10;i12;i+)EnSqQueue(Q,i);i=QueueLength(Q);printf(行列里的元素有%d个n,i);ClearQueue(Q);i=QueueLength(Q);printf(行列里的元素有%d个n,i);return0;实验4行列的链式表示和实现实验内容与要求:编写一个程序实现链行列的各样基本运算，并在此基础上设计一个主程序，达成以下功能：1）初始化并成立链行列2）入链行列3）

17、出链行列4）遍历链行列剖析:行列的链式储存构造简称为链行列。它是限制仅在表头删除和表尾插入的单链表。注意：1）和链栈近似，不必考虑判队满的运算及上溢。2）在出队算法中，一般只要改正队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需改正尾指针，且删去此结点后行列变空。3）和单链表近似，为了简化界限条件的办理，在队头结点前可附带一个头结点。#include#includetypedefintElemType;typedefintStatus;#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefstructNode

18、ElemTypedata;structNode*next;Node;typedefstructNode*front;Node*rear;LinkQueue;StatusInitQueue(LinkQueue*q)q-front=NULL;q-rear=NULL;returnOK;/InitQueueStatusDestroyQueue(LinkQueue*q)Node*p=q-front;while(p)q-front=p-next;free(p);p=q-front;puts(行列已销毁！);returnOK;boolisEmpty(LinkQueue*q)if(q-front=NULL&q-rear=NULL)returnTRUE;returnFALSE;/isEmptyStatusPush(LinkQueue*q,ElemTypee)Node*p=(Node*)malloc(sizeof(Node);if(!p)puts(储存空间分派失败!);returnERROR;p-data=e;p-next=NULL;/防备出现野指针if(isEmpty(q)/假如是空行列，则frontq-front=p;elseq-rear-next=p;q-rear=p;/q-rear指向队尾returnOK