《实验二栈和队列(基本操作)剖析》由会员分享，可在线阅读，更多相关《实验二栈和队列(基本操作)剖析（13页珍藏版）》请在金锄头文库上搜索。
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 #include typedef int SElemType;typedef int Status;#define INIT_SIZE 100#define STACKINCREMENT 10#define Ok 1#define Error 0#define True 1#define False 0typedef structSElemType *base;SElemType *top;int stacksize;SqStack;/初始化栈Status In
4、itStack(SqStack *s)s-base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType);if(!s-base)puts(存储空间分配失败！);return Error;s-top = s-base;s-stacksize = INIT_SIZE;return Ok;/清空栈Status ClearStack(SqStack *s) s-top = s-base; return Ok; /栈是否为空Status StackEmpty(SqStack *s) if(s-top = s-base) return True; else
5、 return False; /销毁栈Status Destroy(SqStack *s)free(s-base);s-base = NULL;s-top = NULL;s-stacksize=0;return Ok;/获得栈顶元素Status GetTop(SqStack *s, SElemType &e)if(s-top = s-base) return Error;e = *(s-top - 1);return Ok;/压栈Status Push(SqStack *s, SElemType e)if(s-top - s-base = s-stacksize)s-base = (SElem
6、Type *)realloc(s-base, (s-stacksize + STACKINCREMENT) * sizeof(SElemType);if(!s-base)puts(存储空间分配失败！);return Error;s-top = s-base + s-stacksize;s-stacksize += STACKINCREMENT;*s-top+ = e;return Ok;/弹栈Status Pop(SqStack *s, SElemType *e)if(s-top = s-base) return Error;-s-top;*e = *(s-top);return Ok;/遍历
7、栈Status StackTraverse(SqStack *s,Status(*visit)(SElemType) SElemType *b = s-base; SElemType *t = s-top; while(t b) visit(*b+); printf(n); return Ok; Status visit(SElemType c) printf(%d ,c); return Ok; int main()SqStack a;SqStack *s = &a;SElemType e;InitStack(s);int n;puts(请输入要进栈的个数：);scanf(%d, &n);w
8、hile(n-)int m;scanf(%d, &m);Push(s, m);StackTraverse(s, visit);puts();Pop(s, &e);printf(%dn, e);printf(%dn, *s-top);Destroy(s);return 0;实验2 栈的链式表示和实现实验内容与要求:编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化链栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈分析:链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。注意：（1）LinkStack结构类型的定义可以方便地在
9、函数体中修改top指针本身（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。（3）链栈中的结点是动态分配的，所以可以不考虑上溢。#include #include #define ERROR 0#define OK 1#define TRUE 1#define FALSE 0typedef int ElemType;typedef int Status;typedef struct nodeElemType data;struct node *next;StackNode;typedef structStackNode *top;LinkStack;/初始化 voi
10、d InitStack(LinkStack *s)s-top = NULL;puts(链栈初始化完成！);/将链栈置空Status SetEmpty(LinkStack *s)StackNode *p = s-top;while(p)s-top = p-next;free(p);p = s-top;puts(链栈已置空！);return OK;/压栈Status Push(LinkStack *s, ElemType e)StackNode *p;p = (StackNode *)malloc(sizeof(StackNode);p-data = e;p-next = s-top;s-top
11、= p;return OK;/弹栈Status Pop(LinkStack *s, ElemType &e)StackNode *p = s-top;if(s-top = NULL)puts(栈空, 不能进行弹栈操作!);return ERROR;s-top = p-next;e = p-data;free(p);return OK;/打印栈 Status PrintStack(LinkStack *s)StackNode *p;p = s-top;while(p)printf(%d , p-data);p = p-next;puts();return OK;int main()LinkSta
12、ck s;InitStack(&s);int n;printf(请输入链栈长度:n);scanf(%d, &n);puts(请输入要录入的数据:);while(n-)int x;scanf(%d, &x);Push(&s, x);PrintStack(&s);SetEmpty(&s);return 0;实验3 队列的顺序表示和实现实验内容与要求编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列（2）建立顺序队列（3）入队（4）出队（5）判断队列是否为空（6）取队头元素（7）遍历队列分析:队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺
13、序表。入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。顺序队列中的溢出现象：（1） 下溢现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。（2） 真上溢现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。（3） 假上溢现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。注意：（1）当头尾指针相等时，队列为空。（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。#include #
