栈的操作(实验报告).doc

实验三 栈和队列 3.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<stdio.h> #include<stdlib.h> #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->top<MAXNUM-1) { p->top=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->top<0) printf("这是一个空栈！"); printf("\n"); for(i=p->top;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 【栈的原理与实现】 栈是一种特殊的线性数据结构，其特点是“后进先出”（LIFO，Last In First Out）。在栈中，新添加的元素（称为入栈）会放在栈顶，而移除元素（称为出栈）总是从栈顶开始。这种结构在计算机科学中广泛应用，例如在表达式求值、递归调用、内存管理等方面。 实验报告中的涉及的是对栈的操作，具体涵盖了以下几个知识点： 1. **顺序栈**：栈的一种实现方式，使用数组来存储元素。在这种结构中，栈底固定，而栈顶的位置随着元素的入栈和出栈而改变。初始化时，栈顶指针`top`通常设为-1，表示栈为空。 2. **栈的操作**： - **初始化**：初始化顺序栈将栈顶指针`top`设置为-1，表示栈为空。 - **入栈（Push）**：在不超出栈容量（MAXNUM-1）的情况下，将元素加入栈顶，栈顶指针`top`加1。 - **出栈（Pop）**：检查栈是否为空，非空则删除栈顶元素，返回其值，同时栈顶指针`top`减1。 - **取栈顶元素（GetTop）**：同样需检查栈是否为空，非空则返回栈顶元素，但不删除。 - **遍历顺序栈（OutStack）**：输出栈中所有元素，从栈顶开始到栈底。 - **置空顺序栈（setEmpty）**：将栈顶指针`top`设回-1，使栈回到初始状态。 3. **栈溢出与下溢**： - **栈溢出**：当试图在已满的栈中插入元素时，会引发错误。实验代码中通过判断`top`是否等于`MAXNUM-1`来防止这种情况。 - **栈下溢**：当尝试从空栈中删除元素或获取栈顶元素时，也会引发错误。代码中通过判断`top`是否为0来防止。 4. **C语言实现**：实验要求使用C语言编写算法和程序，提供了示例代码来实现顺序栈的基本操作。代码中定义了一个结构体`SqStack`来存储栈的数组和栈顶指针，通过指针操作结构体成员来执行各种栈操作。 5. **主程序设计**：主程序提供了一个简单的命令行交互界面，允许用户进行初始化、插入、删除、查看栈顶元素、遍历和清空栈等操作。 6. **算法分析**：在实验报告中，需要分析算法的时间复杂度和空间复杂度。对于顺序栈，所有操作（入栈、出栈、取栈顶元素、遍历和置空）的时间复杂度均为O(1)，因为它们都是直接访问栈顶元素或数组元素。空间复杂度取决于栈的大小，即O(MAXNUM)。 7. **优化设想**：可以考虑的优化包括动态调整栈的大小以适应不同规模的数据，或者使用链式存储结构以消除栈溢出的限制，实现更灵活的存储管理。 通过这个实验，学生能够深入理解栈的特性，熟悉在顺序存储结构上实现栈操作的方法，以及如何在C语言中编写和调试相关的算法。同时，实验报告的撰写有助于巩固理论知识，提升问题解决能力。