实验二 栈与队列一、实验目得1、掌握栈得特点(先进后出FILO)及基本操作,如入栈、出栈等,栈得顺序存储结构与链式存储结构,以便在实际问题背景下灵活应用。2、掌握队列得特点(先进先出FIFO)及基本操作,如入队、出队等,队列顺序存储结构、链式存储结构与循环队列得实现,以便在实际问题背景下灵活应用。二、实验内容1、顺序栈得实现与运算;2、循环队列得实现与运算;3、栈得运用—十进制转八进制运算。三、实验要求1、学生用C++/C完成算法设计与程序设计并上机调试通过;2、撰写实验报告,提供实验测试数据与实验结果;3、分析算法,要求给出具体得算法分析结果,包括时间复杂度与空间复杂度,并简要给出算法设计小结与心得。四、实验准备1、掌握栈与队列这两种抽象数据类型得特点,并能在相应得应用任务中正确选用它们;2、熟练掌握顺序栈与循环队列得基本操作实现算法,特别应注意栈满与栈空得条件以及它们得描述方法,循环队列中队满与队空得描述方法。3、在学习顺序栈得基本操作实现算法时,应注意:在书上给出得结构定义就是采纳了一种动态管理方式(不够时,可以再分配),但在C 语言中,用数组来存储顺序栈,就是静态分配,即不能随机分配空间,这点易引起大家得误解。五、实验步骤1、编程实现顺序栈得各种基本运算,并在此基础上设计一个主程序,完成如下功能:(1)初始化顺序栈;(2)给定一个元素,将此元素压入此栈中;(3)将栈顶一个元素弹出此栈。2、编写一个程序实现循环队列得各种基本运算,并在此基础上设计一个主程序,完成如下功能:(1)初始化循环队列;(2)给定一个元素,将此元素插入此队列中;(3)将队头一个元素出队。3、栈得运用实例 十进制转八进制。六、实验参考代码1、顺序栈得实现与运算;#include #include #define OK 1#define ERROR 0#define OVERFLOW 2typedef int ElemType;typedef int Status;// 栈得顺序存储表示 #define STACK_INIT_SIZE 100 // 存储空间得初始分配量#define STACKINCREMENT 10 // 存储空间得分配增量typedef struct {ElemType *base;ElemType *top;int stacksize;} SqStack;// 构造一个空栈SStatus InitStack(SqStack &S){S、base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));if(!S、base) exit (OVERFLOW);S、top = S、base;S、stacksize = STACK_INIT_SIZE;return OK;}// 判栈S就是否为空栈Status StackEmpty(SqStack S){if (S、top==S、base) ...
