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

1、实验二栈和队列1、实验目的：（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作 在栈的顺序存储结构和链式存储结构上的实现：（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基 本操作在队列的顺序存储结构和链式存储结构上的实现。2、实验要求：（1）复习课本中有关栈和队列的知识；（2）用C语言完成算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结呆（包扌舌 时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给 出多种可能的输入数据和运行结果）。3、实验内容实验1栈的顺序表

2、示和实现实验内容与要求：编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能:（1）初始化顺序栈（2）插入元素（3）删除栈顶元素（4）取栈顶元素（5）遍历顺序栈（6）置空顺序栈分析：栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p-top=MAXNUM-l, 满 时，不能入栈；否则出现空间溢出，引起错误，这种现彖称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为 一种控制转移的条件。注意：（1）顺序栈中元素用向量存放（2）栈底位置是固定不变的，可设置在向量两端的任意一个

3、端点（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top （通常称top为栈顶指针） 来指示当前栈顶位置#include include tvpedef int SElemType; tvpedef int Status; define INIT SIZE 100define STACKINCREMENT 10define Ok 1define Error 0#define True 1define False 0tvpedef stmctSElemType *base;SElemType *top;int stacksize;JSqStack;初始化栈Status IintStac

4、k(SqStack *s)s-base = (SElemType *)nialloc(INIT_SIZE * sizeof(SElemType);if(!s-base)puts(”存储空间分配失败！ ”)；return Error;s-top = s-base;s-stacksize = INIT_SIZE;return Ok;清空栈Status CleaiStack(SqStack *s)s-top = s-base;return Ok;栈是否为空Status StackEmpty(SqStack *s)if(s-top = s-base)return True;elsereturn Fal

5、se; 销毁栈Status Destioy(SqStack *s)fiee(s-base); s-base = NULL; s-top = NULL; s-stacksize=O; return Ok; 获得栈顶元素Status GetTop(SqStack *s, SElemTvpe &亡) if(s-top = s-base) return Error;e = *(s-top - 1); return Ok; 压栈Status Push(SqStack SElemTvpe e)if(s-top - s-base = s-stacksize)STACKINCREMENT) *s-base =

6、 (SElemTvpe *)realloc(s-base, (s-stacksize sizeof(SElemType);if(!s-base) puts(#储空间分配失败！ ”)； return Enor;s-top = s-base + s-stacksize;s-stacksize += STACKINCREMENT:return Ok;弹栈Status Pop(SqStack *s, SElemType *e) if(s-top = s-base) return Error;-s-top;*e = *(s-top);return Ok;遍历栈Status StackTiaveise(S

7、qStack *s,Status(*visit)(SElemType) SElemType *b = s-base;SElemType *t = s-top;wlule(t b)visit(*b+);prmtf(unH);return Ok;Status visit(SElemType c)prmtf(H%d 蔦c);return Ok; mt mam()SqStack a;SqStack *s = &a;SElemType e;IiutStack(s);int n;puts(“请输入要进栈的个数：”); scanf(H%d,； &n);while(n)mt m;scanf(%cT, &m);

8、Push(s, Hl)；StackTiaverse(s, visit); puts(,H,);Pop(s, &亡)；e);*s-top);Destroy(s); return 0;实验2栈的链式表示和实现 实验内容与要求：编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能:（1）初始化链栈（2）链栈置空入栈（4）出栈（5）取栈顶元素（6）遍历链栈分析：链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。注意：（1）LuikStack结构类型的定义可以方便地在函数体中修改top指针本身（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中

9、定义。（3）链栈中的结点是动态分配的，所以可以不考虑上溢。#include #include #define ERROR 0#define OK 1#define TRUE 1#define FALSE 0tvpedef int ElemType;tvpedef int Status;tvpedef stmct nodeElemTvpe data;stmct node *next;JStackNode;tvpedef stmctStackNode *top;JLuikStack;/初始化void InitStack（LnikStack *s）s-top = NULL;puts（n栈初始化完成!

10、 ”）;将链栈置空Status SetEmpty(LuikStack *s) StackNode *p = s-top;while(p)s-top = p-next; fiee(p);p = s-top;puts(“链栈已置空！ ”)； retuin OK; 压栈Status Push(LuikStack *s. ElemTvpe e)StackNode *p;p = (StackNode *)malloc(sizeof(StackNode);p-data = e;p-next = s-top;s-top = p;retuin OK; 弹栈Status Pop(LuikStack *s. El

11、emTe &e) StackNode *p = s-top;if(s-top = NULL)puts(”栈空，不能进行弹栈操作!”); return ERROR;s-top = p-next;e = p-data;fiee(p);retuin OK; 打印栈Status PrmtStack(LuikStack *s)StackNode *p;p = s-top;while(p)printf(” d”, p-data);p = p-next;puts(HH); return OK;mtLinkStack s;IiutStack( &s);int n;pmitf(”请输入链栈长度:n”)； sca

12、nf(n%d, &n);puts(”请输入要录入的数据:”); while(n)mt x;scanf(%cT, &x); Push(&s, x);PrintStack(&s);SetEmpty( &s); return 0;实验3队列的顺序表示和实现 实验内容与要求编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如卞功能:（1）初始化队列（2）建立顺序队列（3）入队（4）出队（5）判断队列是否为空（6）取队头元素（7）遍历队列分析：队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入ear所指的位置，然后将war加1。出队时，删去仕ou

13、t所指的元素, 然后将front加1并返回被删元素。顺序队列中的溢出现彖：（1）”卞溢”现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用 作程序控制转移的条件。（2）”真上溢”现彖。当队列满时，做进栈运算产生空间溢出的现彖。“真上溢”是一种出错 状态，应设法避免。（3）”假上溢”现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空 间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾 指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现彖。注意：（1）当头尾指针相等时，队列为空。（2）在非空队列里，队头指针始终指向队头

14、元素，尾指针始终指向队尾元素的下一位置。#include #include tvpedef mt QElemTvpe; tvpedef int Status; frdefine MaxQSize 10 define OK 1 frdefine ERROR 0 define TRUE 1 define FALSE 0 define OVERFLOW-1 tvpedef stmctQElemType *base; int front, rear;JSqQueue;初始化循环队列mt IiutQueue(SqQueue &Q)Q.base = (QElemType*)malloc(MaxQSize*

15、sizeof(QElemT7pe); if(Q.base NULL)puts(f,配内存空间失败！”); exit(OVERFLOW);Q.fiont = Q.reai = 0;return 0;将循环队列清空mt CleaiQueue(SqQueue &Q)Q.fiont = Q.reai = 0;求队列元素的个数mt QueueLength(SqQueue Q)return (Q.ieai - Q.front + MaxQSize) % MaxQSize;/插入元素到循环队列mt EnSqQueue(SqQueue &Q. QElemTvpe e)if (Q.iear + 1) % Max

16、QSize = Q.front)return ERROR; /队列满Q.baseQ.reai = e; /元素亡入队Q.ieai = (Q.war + 1) % MaxQSize; /修改队尾指针return OK;从循环队列中删除元素mt DeSqQueue(SqQueue &Q QElemTvpe &亡)if (Q. front = Q.reai)return ERROR;e = Q.baseQ.fiont; 取队头元素至 eQ.fiont = (Q.front + 1) % MaxQSize; 修改队头指针,如果超内存，循坏 return OK;判断一个循环队列是否为空队列mt isQu

17、eueEmpty(SqQueue Q)if (Q.fiont = Q.reai)return TRUE;elsereturn FALSE;mt mam()int i? e;SqQueue Q;IiutQueue(Q);for (i=0; iMaxQSize-l; i+)只有 MaxQSize 个数据进队列EnSqQueue(Q, i);i = QueueLength(Q);printf(“队列里的元素有d个3,1);for (i=0; i3; i+)DeSqQueue（Q, e）;pimtf（n%d e）;pmirffE）;i = QueueLength（Q）;printf（”队列里的元素有d

18、个曲,1）;for（i=10; i12;i+）EnSqQueue（Q, i）;i = QueueLength（Q）;printf（”队列里的元素有d个曲,1）;ClearQueue（Q）;i = QueueLength（Q）;printf（”队列里的元素有d个曲,1）;return 0;实验4队列的链式表示和实现实验内容与要求：编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能:（1）初始化并建立链队列（2）入链队列（3）出链队列（4）遍历链队列分析：队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。注意：（1）和链栈类似，无须考虑判队满的运算

19、及上溢。（2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队 头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。#include #include typedef int ElemType;typedef int Status;#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef struct NodeElemTy pe data; struct Node 来next;Node;typedef struc

20、tNode front;Node 参rear;JLinkQueue;Status InitQueue(LinkQueue q)q-front = NULL;q-rear = NULL; return OK;/InitQueueStatus DestroyQueue(LinkQueue 那q)Node 耶p = q-front;while(p)q-front = p-next;free(p);p = q-front;puts(“队列已销毁! ”)；return OK;bool isEmpty(LinkQueue 来q)if(q-front =NULL & qrear = NULL) return TRUE;return FALSE;/isEmptyStatus Push(LinkQueue 参q, ElemType e)Node 参p = (Node*)malloc(sizeof(Node);puts(“存储空间分配失败! ”)； return ERROR;p-data = e;p-next = NULL;/防止出现野指针iF(isEmpty(q)如果是空队列，则front指向p (第一个元素) q-front = p;elseq-rear-next = p;q-rear =