实验二栈和队列

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为栈顶指针)来指示当前栈顶位置#i nclude #in clude typedef int SElemType;typedef int Status;#defi ne INIT_SIZE 100 #defi ne STACKINCREMENT 10#defi ne Ok 1#defi ne Error 0#defi ne True 1#defi ne False 0typedef structSEIemType *base;SEIemType *top;int stacksize;SqStack;/初始化

4、栈Status In itStack(SqStack *s)s-base = (SElemType *)malloc(INIT_SIZE * sizeof(SEIemType); 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 Tr

5、ue;elsereturn False;/销毁栈Status Destroy(SqStack *s)free(s-base);s-base = NULL; s-top = NULL; s-stacksize=O;return Ok;/获得栈顶元素Status GetTop(SqStack *s, SEIemType &e)if(s-top = s-base) retur n Error;e = *(s-top - 1);return Ok;/压栈Status Push(SqStack *s, SElemType e)if(s-top - s-base = s-stacksize)s-base(

6、SElemType *)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, SEIemType *e) if(s-top = s-base) retur n Error;-s-top;*e = *(s-top);return

7、 Ok;/遍历栈Status StackTraverse(SqStack *s,Status(*visit)(SEIemType)SEIemType *b = s-base;SEIemType *t = s-top;while(t b)visit(*b+);prin tf(n);return Ok;Status visit(SElemType c)prin tf(%d ,c);return Ok; int mai n()SqStack a;SqStack *s = &a;SEIemType e;In itStack(s);int n;puts(”请输入要进栈的个数：”);scanf(%d, &

8、n);while( n-)int m;scan f(%d, & m);Push(s, m);StackTraverse(s, visit);puts(”)；Pop(s, &e);prin tf(%dn, e);prin tf(%dn, *s-top);Destroy(s);return 0;实验2栈的链式表示和实现实验内容与要求：编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能:（1）初始化链栈（2 ）链栈置空（3）入栈（4）出栈（5 ）取栈顶元素（6 ）遍历链栈分析：链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。（1 ） LinkStack结构

9、类型的定义可以方便地在函数体中修改top指针本身（2 ）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。（3）链栈中的结点是动态分配的，所以可以不考虑上溢。#i nclude #i nclude #defi ne ERROR 0#defi ne OK 1#defi ne TRUE 1#defi ne FALSE 0 typedef int ElemType;typedef int Status;typedef struct nodeElemType data;struct node *n ext;StackNode;typedef structStackNode *to

10、p;Lin kStack;/初始化void In itStack(Li nkStack *s)s-top = NULL;puts（链栈初始化完成！）;/将链栈置空Status SetEmpty(Li nkStack *s) StackNode *p = s-top;while(p)s-top = p_n ext;free(p);p = s-top;puts(链栈已置空！);return OK;/压栈Status Push(Li nkStack *s, ElemType e)StackNode *p;p = (StackNode *)malloc(sizeof(StackNode);p-data

11、 = e;p_next = s-top;s-top = p;return OK;/弹栈Status Pop(LinkStack *s, ElemType &e)StackNode *p = s-top;if(s-top = NULL)puts(栈空，不能进行弹栈操作！”);return ERROR;s-top = p_n ext;e = p-data;free(p);return OK;/打印栈Status Prin tStack(Li nkStack *s)StackNode *p;p = s_top;while(p)prin tf(%d , p-data); p = p_n ext;put

12、s(”)；return OK; int mai n()Lin kStack s;In itStack(&s);int n;printf(请输入链栈长度:n”); scan f(%d, &n);puts(请输入要录入的数据:);while( n-)int x;scan f(%d, &x);Push( &s, x);Prin tStack（&s）;SetEmpty （&s）;return 0;实验3队列的顺序表示和实现实验内容与要求完成如下功能:编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序,（1 ）初始化队列（2 ）建立顺序队列（3）入队（4）出队（5 ）判断队列是否为空（6

13、 ）取队头元素（7 ）遍历队列分析：队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将 rear加1。出队时，删去front所指的元 素，然后将front加1并返回被删元素。顺序队列中的溢出现象：（1） 下溢现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常 用作程序控制转移的条件。（2） 真上溢”现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出 错状态，应设法避免。（3）假上溢”现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。 当队列中实际的元素个数远远小于

14、向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。（1 ）当头尾指针相等时，队列为空。（2 ）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。#i nclude #i nclude typedef int QEIemType;typedef int Status;#defi ne MaxQSize 10#defi ne OK 1#defi ne ERROR 0#defi ne TRUE 1#defi ne FALSE 0#defi ne OVERFLOW -1typedef struct QElemType *base;

15、int front, rear;SqQueue;/初始化循环队列int Ini tQueue(SqQueue &Q)Q.base = (QEIemType*)malloc(MaxQSize*sizeof(QEIemType); if (Q.base = NULL)puts(分配内存空间失败！”)；exit(OVERFLOW);Q.front = Q.rear = 0;return 0;/将循环队列清空int ClearQueue(SqQueue &Q)Q.front = Q.rear = 0;/求队列元素的个数 int QueueLe ngth(SqQueue Q)return (Q.rear

16、 - Q.fro nt + MaxQSize) % MaxQSize;/插入元素到循环队列 int En SqQueue(SqQueue &Q, QEIemType e)if (Q.rear + 1) % MaxQSize = Q.fro nt)return ERROR; / 队列满Q.baseQ.rear = e; / 元素 e 入队Q.rear = (Q.rear + 1) % MaxQSize; /修改队尾指针return OK;/从循环队列中删除元素int DeSqQueue(SqQueue &Q, QEIemType &e)if (Q.fro nt = Q.rear)return E

17、RROR;e = Q.baseQ.fro nt; / 取队头元素至 eQ.front = (Q.front + 1) % MaxQSize; /修改队头指针，如果超内存，循环return OK;/判断一个循环队列是否为空队列int isQueueEmpty(SqQueue Q)if (Q.fro nt = Q.rear)return TRUE;elsereturn FALSE;int mai n()int i, e;SqQueue Q;Ini tQueue(Q);for (i=0; iMaxQSize-1; i+)/ 只有 MaxQSize 个数据进队列En SqQueue(Q, i);i =

18、 QueueLe ngth(Q);printf(队列里的元素有d个n, i);for (i=0; i3; i+)DeSqQueue(Q, e);prin tf(%d , e);prin tf(n);i = QueueLe ngth(Q);printf(队列里的元素有%d个n, i);for (i=10; i12; i+)En SqQueue(Q, i);i = QueueLe ngth(Q);printf(队列里的元素有%d个n, i);ClearQueue(Q);i = QueueLe ngth(Q);printf(队列里的元素有%d个n, i);return 0;实验4队列的链式表示和实现

19、实验内容与要求：编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能:（1 ）初始化并建立链队列（2 ）入链队列（3 ）出链队列（4）遍历链队列分析: 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。（1）和链栈类似，无须考虑判队满的运算及上溢。（2 ）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队 头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。#i nclude #i nclude typedef int ElemType

20、;typedef int Status;#defi ne OK 1#defi ne ERROR 0#defi ne TRUE 1#defi ne FALSE 0typedef struct NodeElemType data;struct Node *n ext;Node;typedef struct Node *front;Node *rear;Lin kQueue;Status In itQueue(L in kQueue *q) q-fro nt = NULL;q-rear = NULL;return OK;/lni tQueueStatus DestroyQueue(L in kQue

21、ue *q) Node *p = q-front;while(p)q_front = p_n ext;free(p);p = q_front; puts(”队列已销毁！ ”); return OK; bool isEmpty(L in kQueue *q)if(q-fro nt =NULL & q-rear = NULL) return TRUE;return FALSE;/isEmptyStatus Push(L in kQueue *q, ElemType e)Node *p = (Node*)malloc(sizeof(Node);if(!p)puts(存储空间分配失败r?； return ERROR;p-data = e;p-next = NULL;/防止出现野指针if(isEmpty(q) 如果是空队列，则front指向p (第一个元素)q_front = p;elseq-rear- n ext = p;q-rear