用顺序结构表示栈并实现栈的各种基本操作

栈的顺序表示和实现栈的顺序表示和实现 2 2基础实验基础实验 2 2 1实验目的实验目的 1 掌握栈的顺序表示和实现 2 掌握栈的链式表示和实现 3 掌握队列的顺序表示和实现 4 掌握队列的链式表示和实现 2 2 2实验内容实验内容 实验一 栈的顺序表示和实现实验一 栈的顺序表示和实现 实验内容与要求实验内容与要求 编写一个程序实现顺序栈的各种基本运算 并在此基础上设计一个主程序 完成如下功能 1 初始化顺序栈 2 插入元素 3 删除栈顶元素 4 取栈顶元素 5 遍历顺序栈 6 置空顺序栈 知识要点知识要点 栈的顺序存储结构简称为顺序栈 它是运算受限的顺序表 对于顺序栈 入栈时 首先判断栈是否为满 栈满的条件为 p top MAXNUM 1 栈满时 不能入 栈 否则出现空间溢出 引起错误 这种现象称为上溢 出栈和读栈顶元素操作 先判栈是否为空 为空时不能操作 否则产生错误 通常栈空作为一种控制 转移的条件 注意 1 顺序栈中元素用向量存放 2 栈底位置是固定不变的 可设置在向量两端的任意一个端点 3 栈顶位置是随着进栈和退栈操作而变化的 用一个整型量 top 通常称 top 为栈顶指针 来指示当 前栈顶位置 实现提示实现提示 定义顺序栈的存储结构 typedef struct ElemType stack MAXNUM int top SqStack 初始化顺序栈函数 void InitStack SqStack p q SqStack malloc sizeof SqStack 申请空间 入栈函数 void Push SqStack p ElemType x if p toptop p top 1 栈顶 1 p stack p top x 数据入栈 出栈函数 ElemType Pop SqStack p x p stack p top 将栈顶元素赋给 x p top p top 1 栈顶 1 获取栈顶元素函数 ElemType GetTop SqStack p x p stack p top 遍历顺序栈函数 void OutStack SqStack p for i p top i 0 i printf 第 d 个数据元素是 6d n i p stack i 置空顺序栈函数 void setEmpty SqStack p p top 1 参考程序参考程序 include include define MAXNUM 20 define ElemType int 定义顺序栈的存储结构 typedef struct ElemType stack MAXNUM int top SqStack 初始化顺序栈 void InitStack SqStack p if p printf Eorror p top 1 入栈 void Push SqStack p ElemType x if p toptop p top 1 p stack p top x else printf Overflow n 出栈 ElemType Pop SqStack p ElemType x if p top 0 x p stack p top printf 以前的栈顶数据元素 d 已经被删除 n p stack p top p top p top 1 return x else printf Underflow n return 0 获取栈顶元素 ElemType GetTop SqStack p ElemType x if p top 0 x p stack p top return x else printf Underflow n return 0 遍历顺序栈 void OutStack SqStack p int i printf n if p toptop i 0 i printf 第 d 个数据元素是 6d n i p stack i 置空顺序栈 void setEmpty SqStack p p top 1 主函数 main SqStack q int y cord ElemType a do printf n printf 第一次使用必须初始化 n printf n printf n 主菜单 n printf n 1 初始化顺序栈 n printf n 2 插入一个元素 n printf n 3 删除栈顶元素 n printf n 4 取栈顶元素 n printf n 5 置空顺序栈 n printf n 6 结束程序运行 n printf n n printf 请输入您的选择 1 2 3 4 5 6 scanf d printf n switch cord case 1 q SqStack malloc sizeof SqStack InitStack q OutStack q break case 2 printf 请输入要插入的数据元素 a scanf d Push q a OutStack q break case 3 Pop q OutStack q break case 4 y GetTop q printf n 栈顶元素为 d n y OutStack q break case 5 setEmpty q printf n 顺序栈被置空 n OutStack q break case 6 exit 0 while cordtop NULL 链栈置空函数 void setEmpty LinkStack s s top NULL 入栈函数 void pushLstack LinkStack s Elemtype x p StackNode malloc sizeof StackNode 建立一个节点 p data x p next s top 指向栈顶 s top p 插入 出栈函数 Elemtype popLstack LinkStack s x p data s top p next 当前的栈顶指向原栈的 next free p 释放 取栈顶元素函数 Elemtype StackTop LinkStack s return s top data 遍历链栈函数 void Disp LinkStack s while p NULL printf d n p data p p next 参考程序参考程序 include stdio h include malloc h include stdlib h typedef int Elemtype typedef struct stacknode Elemtype data stacknode next StackNode typedef struct stacknode top 栈顶指针 LinkStack 初始化链栈 void InitStack LinkStack s s top NULL printf n 已经初始化链栈 n 链栈置空 void setEmpty LinkStack s s top NULL printf n 链栈被置空 n 入栈 void pushLstack LinkStack s Elemtype x StackNode p p StackNode malloc sizeof StackNode 建立一个节点 p data x p next s top 由于是在栈顶 pushLstack 所以要指向栈顶 s top p 插入 出栈 Elemtype popLstack LinkStack s Elemtype x StackNode p p s top 指向栈顶 if s top 0 printf n 栈空 不能出栈 n exit 1 x p data s top p next 当前的栈顶指向原栈的 next free p 释放 return x 取栈顶元素 Elemtype StackTop LinkStack s if s top 0 printf n 链栈空 n exit 1 return s top data 遍历链栈 void Disp LinkStack s printf n 链栈中的数据为 n printf n StackNode p p s top while p NULL printf d n p data p p next printf n void main printf 链栈操作 n n int i m n a LinkStack s s LinkStack malloc sizeof LinkStack int cord do printf n printf 第一次使用必须初始化 n printf n printf n 主菜单 n printf n 1 初始化链栈 n printf n 2 入栈 n printf n 3 出栈 n printf n 4 取栈顶元素 n printf n 5 置空链栈 n printf n 6 结束程序运行 n printf n n printf 请输入您的选择 1 2 3 4 5 6 scanf d printf n switch cord case 1 InitStack s Disp s break case 2 printf 输入将要压入链栈的数据的个数 n scanf d printf 依次将 d 个数据压入链栈 n n for i 1 i n i scanf d pushLstack s a Disp s break case 3 printf n 出栈操作开始 n printf 输入将要出栈的数据个数 m scanf d for i 1 i m i printf n 第 d 次出栈的数据是 d i popLstack s Disp s break case 4 printf n n 链栈的栈顶元素为 d n StackTop s printf n break case 5 setEmpty s Disp s break case 6 exit 0 while cordfront 1 q rear 1 入队函数 int append sqqueue q Elemtype x q rear q queue q rear x 出队函数 Elemtype Delete sqqueue q x q queue q front 判断队列是否为空函数 int Empty sqqueue q if q front q rear return TRUE 取队头元素函数 int gethead sqqueue q return q queue q front 1 遍历队列函数 void display sqqueue q while srear s s 1 printf dqueue s 建立顺序队列函数 void Setsqqueue sqqueue q for i 0 i n i 利用循环快速输入数据 scanf d append q m 利用入队函数快速输入数据 参考程序参考程序 include include define MAXNUM 100 define Elemtype int define TRUE 1 define FALSE 0 typedef struct Elemtype queue MAXNUM int front int rear sqqueue 队列初始化 int initQueue sqqueue q if q return FALSE q front 1 q rear 1 return TRUE 入队 int append sqqueue q Elemtype x if q rear MAXNUM 1 return FALSE q rear q queue q rear x return TRUE 出队 Elemtype Delete sqqueue q Elemtype x if q front q rear return 0 x q queue q front return x 判断队列是否为空 int Empty sqqueue q if q front q rear return TRUE return FALSE 取队头元素 int gethead sqqueue q if q front q rear return 0 return q queue q front 1 遍历队列 void display sqqueue q int s s q front if q front q rear printf 队列空 n else printf n 顺序队列依次为 while srear s s 1 printf dqueue s printf n printf 顺序队列的队尾元素所在位置 rear d n q rear printf 顺序队列的队头元素所在位置 front d n q front 建立顺序队列 void Setsqqueue sqqueue q int n i m printf n 请输入将要入顺序队列的长度 scanf d printf n 请依次输入入顺序队列的元素值 n for i 0 i n i scanf d append q m main sqqueue head int x y z s