《实验二栈和队列基本操作.doc》由会员分享，可在线阅读，更多相关《实验二栈和队列基本操作.doc（12页珍藏版）》请在三一办公上搜索。
1、实验二 栈和队列1、实验目的：（1） 熟悉栈的特点先进后出及栈的根本操作，如入栈、出栈等，掌握栈的根本操作在栈的顺序存储构造和链式存储构造上的实现；（2） 熟悉队列的特点先进先出及队列的根本操作，如入队、出队等，掌握队列的根本操作在队列的顺序存储构造和链式存储构造上的实现。2、实验要求：（1） 复习课本中有关栈和队列的知识；（2） 用C语言完成算法和程序设计并上机调试通过；（3） 撰写实验报告，给出算法思路或流程图和具体实现源程序、算法分析结果包括时间复杂度、空间复杂度以及算法优化设想、输入数据及程序运行结果必要时给出多种可能的输入数据和运行结果。3、实验容实验1 栈的顺序表示和实现实验容与要
2、求:编写一个程序实现顺序栈的各种根本运算，并在此根底上设计一个主程序，完成如下功能：1初始化顺序栈2插入元素3删除栈顶元素4取栈顶元素5遍历顺序栈6置空顺序栈分析:栈的顺序存储构造简称为顺序栈,它是运算受限的顺序表。对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p-top= =MA*NUM-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 InitStack(SqStack *s)s-base = (SEl
4、emType *)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 return False; /销毁栈Status Destro
5、y(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 = (SElemType *)realloc(s-base, (s-stacks
6、ize + 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;/遍历栈Status StackTraverse(SqStack *s
7、,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);while(n-)int m;scanf(%d, &m);Push
8、(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遍历链栈分析:链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。注意：1LinkStack构造类型的定义可以方便地在函数体中修改top指针本身2假设要记录栈中元素个数，可将元素个数属性放在LinkStack类型
9、中定义。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 *ne*t;StackNode;typedef structStackNode *top;LinkStack;/初始化 void InitStack(LinkStack *s)s-top = NULL;puts(链栈初始化完成
10、！);/将链栈置空Status SetEmpty(LinkStack *s)StackNode *p = s-top;while(p)s-top = p-ne*t;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-ne*t = s-top;s-top = p;return OK;/弹栈Status Pop(LinkStack *s, ElemType
11、 &e)StackNode *p = s-top;if(s-top = NULL)puts(栈空, 不能进展弹栈操作!);return ERROR;s-top = p-ne*t;e = p-data;free(p);return OK;/打印栈 Status PrintStack(LinkStack *s)StackNode *p;p = s-top;while(p)printf(%d , p-data);p = p-ne*t;puts();return OK;int main()LinkStack s;InitStack(&s);int n;printf(请输入链栈长度:n);scanf(%
12、d, &n);puts(请输入要录入的数据:);while(n-)int *;scanf(%d, &*);Push(&s, *);PrintStack(&s);SetEmpty(&s);return 0;实验3 队列的顺序表示和实现实验容与要求编写一个程序实现顺序队列的各种根本运算，并在此根底上设计一个主程序，完成如下功能：1初始化队列2建立顺序队列3入队4出队5判断队列是否为空6取队头元素7遍历队列分析:队列的顺序存储构造称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删
13、元素。顺序队列中的溢出现象：1 下溢现象。当队列为空时，做出队运算产生的溢出现象。“下溢是正常现象，常用作程序控制转移的条件。2 真上溢现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢是一种出错状态，应设法防止。3 假上溢现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。注意：1当头尾指针相等时，队列为空。2在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。#include #include typede
14、f int QElemType;typedef int Status;#define Ma*QSize 10#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1typedef structQElemType *base;int front, rear;SqQueue;/初始化循环队列int InitQueue(SqQueue &Q)Q.base = (QElemType*)malloc(Ma*QSize*sizeof(QElemType);if (Q.base = NULL)puts(分配存空间失
15、败！); e*it(OVERFLOW);Q.front = Q.rear = 0;return 0;/将循环队列清空int ClearQueue(SqQueue &Q)Q.front = Q.rear = 0;/求队列元素的个数int QueueLength(SqQueue Q)return (Q.rear - Q.front + Ma*QSize) % Ma*QSize;/插入元素到循环队列int EnSqQueue(SqQueue &Q, QElemType e)if (Q.rear + 1) % Ma*QSize = Q.front)return ERROR; /队列满Q.baseQ.r
16、ear = e; /元素e入队Q.rear = (Q.rear + 1) % Ma*QSize; /修改队尾指针return OK;/从循环队列中删除元素int DeSqQueue(SqQueue &Q, QElemType &e)if (Q.front = Q.rear)return ERROR;e = Q.baseQ.front; /取队头元素至eQ.front = (Q.front + 1) % Ma*QSize; /修改队头指针,如果超存，循环 return OK;/判断一个循环队列是否为空队列int isQueueEmpty(SqQueue Q)if (Q.front = Q.rea
17、r)return TRUE;elsereturn FALSE;int main()int i, e;SqQueue Q;InitQueue(Q);for (i=0; iMa*QSize-1; i+)/只有Ma*QSize个数据进队列EnSqQueue(Q, i);i = QueueLength(Q);printf(队列里的元素有%d个n, i);for (i=0; i3; i+)DeSqQueue(Q, e);printf(%d , e);printf(n);i = QueueLength(Q);printf(队列里的元素有%d个n, i);for (i=10; i12; i+)EnSqQue
18、ue(Q, i);i = QueueLength(Q);printf(队列里的元素有%d个n, i);ClearQueue(Q);i = QueueLength(Q);printf(队列里的元素有%d个n, i);return 0;实验4 队列的链式表示和实现实验容与要求:编写一个程序实现链队列的各种根本运算，并在此根底上设计一个主程序，完成如下功能：1初始化并建立链队列2入链队列3出链队列4遍历链队列分析:队列的链式存储构造简称为链队列。它是限制仅在表头删除和表尾插入的单链表。注意：1和链栈类似，无须考虑判队满的运算及上溢。2在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结
19、点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。3和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。#include #include typedef int ElemType;typedef int Status;#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef struct NodeElemType data;struct Node *ne*t;Node;typedef structNode *front;Node *rear;LinkQueue;Status Init
20、Queue(LinkQueue *q)q-front = NULL;q-rear = NULL;return OK;/InitQueueStatus DestroyQueue(LinkQueue *q) Node *p = q-front; while(p) q-front = p-ne*t; free(p); p = q-front; puts(队列已销毁！); return OK;bool isEmpty(LinkQueue *q) if(q-front =NULL & q-rear = NULL) return TRUE; return FALSE;/isEmptyStatus Push
21、(LinkQueue *q, ElemType e)Node *p = (Node*)malloc(sizeof(Node);if(!p)puts(存储空间分配失败!);return ERROR;p-data = e;p-ne*t = NULL;/防止出现野指针if(isEmpty(q)/如果是空队列，则front指向p第一个元素 q-front = p;else q-rear-ne*t = p; q-rear = p;/q-rear指向队尾return OK;/PushStatus Pop(LinkQueue *q, ElemType *e) Node *p = q-front; if(is
22、Empty(q) puts(队列为空！); return ERROR; *e = p-data; q-front = p-ne*t; free(p); if(q-front = NULL)/如果出队列后队列空了，则q-rear应指向NULL， q-rear = NULL; return OK;/PopStatus createQueue(LinkQueue *q) InitQueue(q); puts(请输入要输入的队列元素个数：); int n; scanf(%d, &n); while(n-) int m; scanf(%d, &m); Push(q, m); return OK;/cre
23、ateQueueStatus PrintQueue(LinkQueue *q) Node *p = q-front; puts(队列中有以下元素:); while(p) printf(%d , p-data); p = p-ne*t; puts(); return OK;int main() LinkQueue q; int e; createQueue(&q); PrintQueue(&q); Pop(&q, &e); puts(出队列的元素是：); printf(%dn, e); PrintQueue(&q); Push(&q, 8); puts(8进队列后：); PrintQueue(&q); DestroyQueue(&q);return 0;
