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

1 实验二实验二 栈和队列栈和队列 1 实验目的 实验目的 1 熟悉栈的特点 先进后出 及栈的基本操作 如入栈 出栈等 掌握栈的基本操作 在栈的顺序存储结构和链式存储结构上的实现 2 熟悉队列的特点 先进先出 及队列的基本操作 如入队 出队等 掌握队列的基 本操作在队列的顺序存储结构和链式存储结构上的实现 2 实验要求 实验要求 1 复习课本中有关栈和队列的知识 2 用 C 语言完成算法和程序设计并上机调试通过 3 撰写实验报告 给出算法思路或流程图和具体实现 源程序 算法分析结果 包 括时间复杂度 空间复杂度以及算法优化设想 输入数据及程序运行结果 必要 时给出多种可能的输入数据和运行结果 3 实验内容 实验内容 实验实验 1 栈的顺序表示和实现栈的顺序表示和实现 实验内容与要求实验内容与要求 编写一个程序实现顺序栈的各种基本运算 并在此基础上设计一个主程序 完成如下功能 1 初始化顺序栈 2 插入元素 3 删除栈顶元素 4 取栈顶元素 5 遍历顺序栈 6 置空顺序栈 分析分析 栈的顺序存储结构简称为顺序栈 它是运算受限的顺序表 对于顺序栈 入栈时 首先判断栈是否为满 栈满的条件为 p top MAXNUM 1 栈 满时 不能入栈 否则出现空间溢出 引起错误 这种现象称为上溢 出栈和读栈顶元素操作 先判栈是否为空 为空时不能操作 否则产生错误 通常栈空作 为一种控制转移的条件 注意注意 1 顺序栈中元素用向量存放 2 栈底位置是固定不变的 可设置在向量两端的任意一个端点 3 栈顶位置是随着进栈和退栈操作而变化的 用一个整型量 top 通常称 top 为栈顶指 针 来指示当前栈顶位置 include include typedef int SElemType typedef int Status 2 define INIT SIZE 100 define STACKINCREMENT 10 define Ok 1 define Error 0 define True 1 define False 0 typedef struct SElemType base SElemType top int stacksize SqStack 初始化栈 Status InitStack 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 return False 销毁栈 3 Status Destroy SqStack s free s base s base NULL s top NULL s stacksize 0 return Ok 获得栈顶元素 Status GetTop SqStack s SElemType 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 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 4 遍历栈 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 SElemType e InitStack s int n puts 请输入要进栈的个数 scanf d while n int m scanf d Push s m StackTraverse s visit puts Pop s printf d n e printf d n s top Destroy s return 0 5 实验实验 2 栈的链式表示和实现栈的链式表示和实现 实验内容与要求实验内容与要求 编写一个程序实现链栈的各种基本运算 并在此基础上设计一个主程序 完成如下功能 1 初始化链栈 2 链栈置空 3 入栈 4 出栈 5 取栈顶元素 6 遍历链栈 分析 链栈是没有附加头结点的运算受限的单链表 栈顶指针就是链表的头指针 注意 1 LinkStack 结构类型的定义可以方便地在函数体中修改 top 指针本身 2 若要记录栈中元素个数 可将元素个数属性放在 LinkStack 类型中定义 3 链栈中的结点是动态分配的 所以可以不考虑上溢 include include define ERROR 0 define OK 1 define TRUE 1 define FALSE 0 typedef int ElemType typedef int Status typedef struct node ElemType data struct node next StackNode typedef struct StackNode top LinkStack 初始化 void InitStack LinkStack s s top NULL puts 链栈初始化完成 6 将链栈置空 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 p return OK 弹栈 Status Pop LinkStack s ElemType if s top NULL puts 栈空 不能进行弹栈操作 return ERROR s top p next e p data free p return OK 打印栈 Status PrintStack LinkStack s 7 StackNode p p s top while p printf d p data p p next puts return OK int main LinkStack s InitStack int n printf 请输入链栈长度 n scanf d puts 请输入要录入的数据 while n int x scanf d Push PrintStack SetEmpty return 0 实验实验 3 队列的顺序表示和实现队列的顺序表示和实现 实验内容与要求实验内容与要求 编写一个程序实现顺序队列的各种基本运算 并在此基础上设计一个主程序 完成如下功 能 1 初始化队列 2 建立顺序队列 3 入队 4 出队 5 判断队列是否为空 6 取队头元素 7 遍历队列 8 分析分析 队列的顺序存储结构称为顺序队列 顺序队列实际上是运算受限的顺序表 入队时 将新元素插入 rear 所指的位置 然后将 rear 加 1 出队时 删去 front 所指的元素 然后将 front 加 1 并返回被删元素 顺序队列中的溢出现象 1 下溢 现象 当队列为空时 做出队运算产生的溢出现象 下溢 是正常现象 常用 作程序控制转移的条件 2 真上溢 现象 当队列满时 做进栈运算产生空间溢出的现象 真上溢 是一种出错 状态 应设法避免 3 假上溢 现象 由于入队和出队操作中 头尾指针只增加不减小 致使被删元素的 空间永远无法重新利用 当队列中实际的元素个数远远小于向量空间的规模时 也可能由 于尾指针已超越向量空间的上界而不能做入队操作 该现象称为 假上溢 现象 注意 1 当头尾指针相等时 队列为空 2 在非空队列里 队头指针始终指向队头元素 尾指针始终指向队尾元素的下一位置 include include typedef int QElemType typedef int Status define MaxQSize 10 define OK 1 define ERROR 0 define TRUE 1 define FALSE 0 define OVERFLOW 1 typedef struct QElemType base int front rear SqQueue 初始化循环队列 int InitQueue SqQueue if Q base NULL puts 分配内存空间失败 exit OVERFLOW Q front Q rear 0 return 0 将循环队列清空 int ClearQueue SqQueue 求队列元素的个数 int QueueLength SqQueue Q return Q rear Q front MaxQSize MaxQSize 插入元素到循环队列 int EnSqQueue SqQueue 队列满 Q base Q rear e 元素 e 入队 Q rear Q rear 1 MaxQSize 修改队尾指针 return OK 从循环队列中删除元素 int DeSqQueue SqQueue e Q base Q front 取队头元素至 e Q front Q front 1 MaxQSize 修改队头指针 如果超内存 循环 return OK 判断一个循环队列是否为空队列 int isQueueEmpty SqQueue Q if Q front Q rear return TRUE else return FALSE int main int i e SqQueue Q InitQueue Q for i 0 i MaxQSize 1 i 只有 MaxQSize 个数据进队列 EnSqQueue Q i i QueueLength Q printf 队列里的元素有 d 个 n i 10 for i 0 i 3 i DeSqQueue Q e printf d e printf n i QueueLength Q printf 队列里的元素有 d 个 n i for i 10 i 12 i EnSqQueue 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 在出队算法中 一般只需修改队头指针 但当原队中只有一个结点时 该结点既是队 头也是队尾 故删去此结点时亦需修改尾指针 且删去此结点后队列变空 3 和单链表类似 为了简化边界条件的处理 在队头结点前可附加一个头结点 include include typedef int ElemType typedef int Status define OK 1 define ERROR 0 define TRUE 1 define FALSE 0 typedef struct Node 11 ElemType data struct Node next Node typedef struct Node front Node rear LinkQueue Status InitQueue LinkQueue q q front NULL q rear NULL return OK InitQueue Status 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 return FALSE isEmpty Status Push LinkQueue q ElemType e Node p Node malloc sizeof Node if p puts 存储空间分配失败存储空间分配失败 12 return ERROR p data e p next NULL 防止出现野指针防止出现野指针 if isEmpty q 如果是空队列 则如果是空队列 则 front 指向指向 p 第一个元素 第一个元素 q front p else q rear next p q rear p q rea