实验二栈和队列(基本操作)讲解文档格式.doc

1、typedef structSElemType *base;SElemType *top;int stacksize;SqStack;/初始化栈Status InitStack（SqStack *s）s-base = （SElemType *）malloc（INIT_SIZE * sizeof（SElemType）;if（!s-base）puts（存储空间分配失败！）;return Error;top = s-base;stacksize = INIT_SIZE;return Ok;/清空栈Status ClearStack（SqStack *s） s- return Ok; /栈是否为空St

2、atus StackEmpty（SqStack *s） if（s-top = s- return True; else return False;/销毁栈Status Destroy（SqStack *s）free（s-base）;base = NULL;top = NULL;stacksize=0;/获得栈顶元素Status GetTop（SqStack *s, SElemType &e）if（s-base） return Error;e = *（s-top - 1）;/压栈Status Push（SqStack *s, SElemType e）top - s-base = s-stacks

3、ize）s-base = （SElemType *）realloc（s-base, （s-stacksize + STACKINCREMENT） * sizeof（SElemType）;if（!puts（return Error;base + s-stacksize;stacksize += STACKINCREMENT;*s-top+ = e;/弹栈Status Pop（SqStack *s, SElemType *e）-s-top;*e = *（s-top）;/遍历栈Status StackTraverse（SqStack *s,Status（*visit）（SElemType） SEle

4、mType *b = s- SElemType *t = s- while（t b） visit（*b+）; printf（nStatus visit（SElemType c）%d ,c）;int main（）SqStack a;SqStack *s = &a;SElemType e;InitStack（s）;int n;puts（请输入要进栈的个数：scanf（%d, &n）;while（n-）int m;scanf（m）;Push（s, m）;StackTraverse（s, visit）;Pop（s, &e）;printf（%dn, e）;, *s-Destroy（s）;return 0

5、;实验2 栈的链式表示和实现编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化链栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。（3）链栈中的结点是动态分配的，所以可以不考虑上溢。#define ERROR 0#define OK 1#define TRUE 1#define FALSE 0typedef int Ele

6、mType;typedef struct nodeElemType data;struct node *next;StackNode;StackNode *top;LinkStack;/初始化 void InitStack（LinkStack *s）链栈初始化完成！/将链栈置空Status SetEmpty（LinkStack *s）StackNode *p = s-while（p）top = p-next;free（p）;p = s-链栈已置空！return OK;Status Push（LinkStack *s, ElemType e）StackNode *p;p = （StackNode

7、 *）malloc（sizeof（StackNode）;p-data = e;next = s-top = p;Status Pop（LinkStack *s, ElemType &top = NULL）栈空, 不能进行弹栈操作!return ERROR;e = p-data;free（p）;/打印栈 Status PrintStack（LinkStack *s）p = s-printf（%d , p-data）;p = p-LinkStack s;InitStack（&s）;请输入链栈长度:请输入要录入的数据:int x;x）;Push（&s, x）;PrintStack（&SetEmpty

8、（&实验3 队列的顺序表示和实现实验内容与要求编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化队列（2）建立顺序队列（3）入队（4）出队（5）判断队列是否为空（6）取队头元素（7）遍历队列队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。顺序队列中的溢出现象：（1） 下溢现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。（2） 真上溢当队列满时，做进栈运算产生空间

9、溢出的现象。“真上溢”是一种出错状态，应设法避免。（3） 假上溢由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为（1）当头尾指针相等时，队列为空。（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。typedef int QElemType;#define MaxQSize 10#define OVERFLOW -1QElemType *base;int front, rear;SqQueue;/初始化循环队列int Ini

10、tQueue（SqQueue &Q）Q.base = （QElemType*）malloc（MaxQSize*sizeof（QElemType）;if （Q.base = NULL）分配内存空间失败！ exit（OVERFLOW）;Q.front = Q.rear = 0;/将循环队列清空int ClearQueue（SqQueue &/求队列元素的个数int QueueLength（SqQueue Q）return （Q.rear - Q.front + MaxQSize） % MaxQSize;/插入元素到循环队列int EnSqQueue（SqQueue &Q, QElemType e）

11、if （Q.rear + 1） % MaxQSize = Q.front）return ERROR; /队列满Q.baseQ.rear = e; /元素e入队Q.rear = （Q.rear + 1） % MaxQSize; /修改队尾指针/从循环队列中删除元素int DeSqQueue（SqQueue &Q, QElemType &if （Q.front = Q.rear）e = Q.baseQ.front; /取队头元素至eQ.front = （Q.front + 1） % MaxQSize; /修改队头指针,如果超内存，循环 /判断一个循环队列是否为空队列int isQueueEmpty

12、（SqQueue Q）return TRUE;elsereturn FALSE;int i, e;SqQueue Q;InitQueue（Q）;for （i=0; ifront = NULL;rear = NULL;/InitQueueStatus DestroyQueue（LinkQueue *q） Node *p = q-front; while（p） q-front = p- free（p）; p = q- puts（队列已销毁！ return OK;bool isEmpty（LinkQueue *q） if（q-front =NULL & q-rear = NULL） return T

13、RUE; return FALSE;/isEmptyStatus Push（LinkQueue *q, ElemType e）Node *p = （Node*）malloc（sizeof（Node）;p）存储空间分配失败!next = NULL;/防止出现野指针if（isEmpty（q）/如果是空队列，则front指向p（第一个元素） q-front = p; q-rear-next = p;rear = p;/q-rear指向队尾/PushStatus Pop（LinkQueue *q, ElemType *e） if（isEmpty（q） puts（队列为空！ return ERROR;

14、*e = p- q- free（p）;front = NULL）/如果出队列后队列空了，则q-rear应指向NULL，/PopStatus createQueue（LinkQueue *q） InitQueue（q）;请输入要输入的队列元素个数： int n; scanf（ while（n-） int m; scanf（ Push（q, m）;/createQueueStatus PrintQueue（LinkQueue *q）队列中有以下元素: printf（ p = p- LinkQueue q; int e; createQueue（&q）; PrintQueue（& Pop（&q, &出队列的元素是： printf（ Push（&q, 8）;8进队列后： DestroyQueue（&13