实验四 栈的操作实验指导

数据结构实验指导书（C++）-栈、队列、串的操作实验二栈、队列、串的操作实验类型：验证性实验要求：必修实验学时： 2学时一、实验目的：参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。

二、实验要求：1、掌握栈、队列、串的特点。

掌握特殊线性表的常见算法。

2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。

三、实验内容：1. 堆栈类测试和应用问题。

要求：(1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。

测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。

(2)定义数据元素的数据类型为如下形式的结构体：typedef struct{ char taskname[10];//任务名int taskno; //任务号｝DataType；设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。

2. 队列类测试和应用问题。

要求：设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。

3．设计串采用顺序存储结构，编写函数实现两个串的比较Compare(S, T)。

要求比较结果有大于、等于和小于三种情况。

*4. 设计算法利用栈类实现把十进制整数转换为二至九进制之间的任一进制输出。

*5. 设计串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回０。

并要求设计主函数进行测试。

一个测试例子为：S＝”I am a student”，T=”student”，V=”teacher “。

第1篇一、实验目的1. 理解栈的基本概念和操作；2. 掌握栈的顺序存储和链式存储实现方法；3. 熟悉栈在程序设计中的应用。

二、实验内容1. 栈的顺序存储结构实现；2. 栈的链式存储结构实现；3. 栈的基本操作（入栈、出栈、判空、求栈顶元素）；4. 栈在程序设计中的应用。

三、实验方法1. 采用C语言进行编程实现；2. 对实验内容进行逐步分析，编写相应的函数和程序代码；3. 通过运行程序验证实验结果。

四、实验步骤1. 实现栈的顺序存储结构；（1）定义栈的结构体；（2）编写初始化栈的函数；（3）编写入栈、出栈、判空、求栈顶元素的函数；（4）编写测试程序，验证顺序存储结构的栈操作。

2. 实现栈的链式存储结构；（1）定义栈的节点结构体；（2）编写初始化栈的函数；（3）编写入栈、出栈、判空、求栈顶元素的函数；（4）编写测试程序，验证链式存储结构的栈操作。

3. 栈在程序设计中的应用；（1）实现一个简单的四则运算器，使用栈进行运算符和操作数的存储；（2）实现一个逆序输出字符串的程序，使用栈进行字符的存储和输出；（3）编写测试程序，验证栈在程序设计中的应用。

五、实验结果与分析1. 顺序存储结构的栈操作实验结果：（1）入栈操作：在栈未满的情况下，入栈操作成功，栈顶元素增加；（2）出栈操作：在栈非空的情况下，出栈操作成功，栈顶元素减少；（3）判空操作：栈为空时，判空操作返回真，栈非空时返回假；（4）求栈顶元素操作：在栈非空的情况下，成功获取栈顶元素。

2. 链式存储结构的栈操作实验结果：（1）入栈操作：在栈未满的情况下，入栈操作成功，链表头指针指向新节点；（2）出栈操作：在栈非空的情况下，出栈操作成功，链表头指针指向下一个节点；（3）判空操作：栈为空时，判空操作返回真，栈非空时返回假；（4）求栈顶元素操作：在栈非空的情况下，成功获取栈顶元素。

3. 栈在程序设计中的应用实验结果：（1）四则运算器：成功实现加、减、乘、除运算，并输出结果；（2）逆序输出字符串：成功将字符串逆序输出；（3）测试程序：验证了栈在程序设计中的应用。

实验2栈的基本操作实验指导1.实验内容基本内容：输入一个中缀一位整数算术表达式，先将其转换为后缀表达式，转换的方法采用栈实现，并且考虑算符的优先级，然后用另一个栈来计算后缀表达式的值。

对输入的表达式，做如下假设：(1)只考虑+、-、*、/这四种运算符；(2)输入的中缀表达式中数字是一位整数，没有小数；(3)假定输入表达式是合法的。

2.测试用例中缀表达式：3*4-5+7#后缀表达式：34*5-7+测试结果：143.算法描述计算中缀算术表达式是有关栈的经典算法题，很多公司面试或者笔试的时候都会把计算中缀表达式作为一个考察点。

这里先讨论如何直接计算中缀表达式的值，再讨论如何把中缀表达式转化为后缀表达式，最后计算后缀表达式。

3.1直接计算中缀表达式设置两个工作栈，一个操作数栈，一个操作符栈，在（自左至右）扫描算术表达式时，遇到操作数直接入操作数栈，若遇到操作符，则根据操作符优先级判断下一步操作（“操作符优先级规则”）：若其优先级高于栈顶操作符，则入栈，否则（相等或小于），弹出栈顶算符，并从操作数栈弹出两个操作数，计算，将计算结果入操作数栈，继续比较与栈顶操作符的优先级，若仍然等于或低于之，则计算，直至大于之，则将此操作符入栈；左括号一定入栈，且其优先级低于后续来到的任何操作符，右括号一定出栈并计算直至遇到左括号，另外栈的开始以“#”开始，算术表达式以“#”结束，做结束标志。

当栈空时，计算结束。

3.2 中缀表达式转为后缀表达式中缀转化为后缀，要先设一个栈存储运算符，从左到右遍历表达式，主要遵循以下原则：（1）读到操作数，直接输出；（2）栈为空时，遇到运算符，入栈；（3）遇到左括号，将其入栈；（4）遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出，左括号也要弹出；（5）遇到其他运算符’+”-”*”/’时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈，遇到左括号时不能再弹出；（6）最终将栈中的元素依次出栈，输出。

一、实验目的本次实验旨在通过编程实现栈的顺序存储结构和链式存储结构，并熟练掌握栈的基本操作，包括栈的建立、入栈、出栈、取栈顶元素、判栈空等。

通过实验，加深对栈这一数据结构的理解，提高数据结构在实际问题中的应用能力。

二、实验内容1. 顺序栈的建立与基本操作（1）顺序栈的建立顺序栈使用一维数组来实现，其大小为栈的最大容量。

在建立顺序栈时，需要初始化栈顶指针top为-1，表示栈为空。

（2）顺序栈的基本操作① 入栈操作（Push）当栈未满时，将新元素插入到栈顶，同时栈顶指针top加1。

② 出栈操作（Pop）当栈非空时，将栈顶元素出栈，同时栈顶指针top减1。

③ 取栈顶元素操作（GetTop）当栈非空时，返回栈顶元素。

④ 判栈空操作（IsEmpty）当栈顶指针top为-1时，表示栈为空。

2. 链式栈的建立与基本操作（1）链式栈的建立链式栈使用链表来实现，每个节点包含数据域和指针域。

在建立链式栈时，需要创建一个头节点，其指针域为空。

（2）链式栈的基本操作① 入栈操作（Push）当栈为空时，创建新节点作为栈顶节点；当栈非空时，将新节点插入到头节点的下一个节点，同时修改头节点的指针域。

② 出栈操作（Pop）当栈非空时，删除头节点的下一个节点，同时修改头节点的指针域。

③ 取栈顶元素操作（GetTop）当栈非空时，返回头节点的下一个节点的数据域。

④ 判栈空操作（IsEmpty）当头节点的指针域为空时，表示栈为空。

三、实验步骤1. 编写顺序栈和链式栈的建立函数。

2. 编写顺序栈和链式栈的基本操作函数。

3. 编写测试程序，验证顺序栈和链式栈的基本操作。

四、实验结果与分析1. 顺序栈实验结果通过编写顺序栈的建立和基本操作函数，成功实现了顺序栈的入栈、出栈、取栈顶元素、判栈空等操作。

在测试程序中，依次进行入栈、出栈、取栈顶元素等操作，均能正确执行。

2. 链式栈实验结果通过编写链式栈的建立和基本操作函数，成功实现了链式栈的入栈、出栈、取栈顶元素、判栈空等操作。

栈的基本操作实验报告
《栈的基本操作实验报告》
实验目的：
通过本次实验，我们旨在掌握栈的基本操作，包括入栈、出栈、获取栈顶元素
等操作，并理解栈的特点和应用场景。

实验内容：
1. 入栈操作：将元素依次压入栈顶；
2. 出栈操作：从栈顶弹出元素；
3. 获取栈顶元素：不改变栈的状态，获取栈顶元素的值；
4. 判断栈空：判断栈是否为空；
5. 判断栈满：判断栈是否已满。

实验步骤：
1. 初始化一个栈；
2. 将元素依次入栈；
3. 依次进行出栈操作，观察栈的变化；
4. 获取栈顶元素，并进行判断栈空和栈满操作。

实验结果：
经过实验，我们成功掌握了栈的基本操作。

我们发现栈具有后进先出（LIFO）
的特点，适合于一些需要后续处理的数据结构，比如递归函数调用、表达式求
值等场景。

同时，我们也发现了栈的容量限制，需要在使用时注意栈是否已满。

结论：
栈是一种非常重要的数据结构，掌握了栈的基本操作能够帮助我们更好地理解
和应用它。

通过本次实验，我们对栈的特点和应用场景有了更深入的了解，相信在今后的学习和工作中能够更好地运用栈来解决问题。

一、实验目的1. 掌握栈的定义、特点、逻辑结构，理解栈的抽象数据类型。

2. 熟练掌握顺序栈和链栈两种结构类型的定义、特点以及基本操作的实现方法。

3. 了解栈在解决实际问题中的应用。

二、实验内容1. 编写顺序栈和链栈的基本操作函数，包括入栈（push）、出栈（pop）、判断栈空（isEmpty）、获取栈顶元素（getTop）等。

2. 利用栈实现字符序列是否为回文的判断。

3. 利用栈实现整数序列中最大值的求解。

三、实验步骤1. 创建顺序栈和链栈的结构体，并实现相关的基本操作函数。

2. 编写一个函数，用于判断字符序列是否为回文。

该函数首先将字符序列中的字符依次入栈，然后逐个出栈，比较出栈的字符是否与原序列相同，若相同则表示为回文。

3. 编写一个函数，用于求解整数序列中的最大值。

该函数首先将序列中的元素依次入栈，然后逐个出栈，每次出栈时判断是否为当前栈中的最大值，并记录下来。

四、实验结果与分析1. 顺序栈和链栈的基本操作函数实现如下：```c// 顺序栈的基本操作void pushSeqStack(SeqStack s, ElemType x) {if (s->top < MAXSIZE - 1) {s->top++;s->data[s->top] = x;}}void popSeqStack(SeqStack s, ElemType x) {if (s->top >= 0) {x = s->data[s->top];s->top--;}}bool isEmptySeqStack(SeqStack s) {return s->top == -1;}ElemType getTopSeqStack(SeqStack s) {if (s->top >= 0) {return s->data[s->top];}return 0;}// 链栈的基本操作void pushLinkStack(LinkStack s, ElemType x) {LinkStack p = (LinkStack )malloc(sizeof(LinkStack)); if (p == NULL) {exit(1);}p->data = x;p->next = s->top;s->top = p;}void popLinkStack(LinkStack s, ElemType x) { if (s->top != NULL) {LinkStack p = s->top;x = p->data;s->top = p->next;free(p);}}bool isEmptyLinkStack(LinkStack s) {return s->top == NULL;}ElemType getTopLinkStack(LinkStack s) {if (s->top != NULL) {return s->top->data;}return 0;}```2. 判断字符序列是否为回文的函数实现如下：```cbool isPalindrome(char str) {SeqStack s;initStack(&s);int len = strlen(str);for (int i = 0; i < len; i++) {pushSeqStack(&s, str[i]);}for (int i = 0; i < len; i++) {char c = getTopSeqStack(&s);popSeqStack(&s, &c);if (c != str[i]) {return false;}}return true;}```3. 求解整数序列中最大值的函数实现如下：```cint getMax(int arr, int len) {LinkStack s;initStack(&s);int max = arr[0];for (int i = 0; i < len; i++) {pushLinkStack(&s, arr[i]);if (arr[i] > max) {max = arr[i];}}while (!isEmptyLinkStack(&s)) {popLinkStack(&s, &max);}return max;}```五、实验心得通过本次实验，我对栈的基本操作有了更深入的理解。

XXXXXX 实验报告班级 XXXXXX 学号 XXXXXXXXXXXXX 姓名 XXXXXXX 实验组别实验日期 5.27 室温 报告日期 6.6 成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等） 实验名称： 栈的实现和应用实验目的：1.掌握栈的含义。

2.掌握栈的基本操作的实现，并能用于解决实际问题。

实验环境: windows2000, visual c++ 6.0.实验内容：1.实现栈的如下基本操作：push,pop,isempty,isfull,creatstack 。

2.利用栈的基本操作实现conversion()函数，该函数能将任意输入的十进制整数转化成二进制形式表示。

实验要求：1.用顺序存储结构实现栈的进本操作：push,pop,isempty,isfull,creatstack 。

2.利用栈的基本操作实现conversion()函数。

3.编写主函数完成实验内容2.实验原理：栈的概念和特性栈，stack ，是一种特殊的线性表。

作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。

在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。

而在使用时，却是从顶上拿取，也就是说，后冼的先取后后摞上的先取用。

好果我们把冼净的碗“摞上”称为进栈。

压栈，把“取用碗”称为出栈，弹出那么上例的特点是：后进栈的先出栈。

然而，摞起来的碗实际上是一个表。

只不过“进栈”和“出栈”都在最顶上进行。

或者说，元素的插入和删除是在表的一端进行而已。

一般而言，栈是一个线性表 其所有的插入和删除均是限定在表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。

若给定一个栈S=a1, a2a3an 则称a1为栈底元素an 为栈顶元素 元素ai 位于元素ai-1之上。

栈中元素按a1, a2，a3，an 的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an, an-1，a1。

引言：栈是一种常见的数据结构，它具有特殊的操作规则，即先进后出（LIFO）。

本文将介绍栈的操作，并结合实验报告的方式详细阐述栈的概念、基本操作以及应用场景。

概述：栈是一种线性数据结构，由相同类型的元素按照特定顺序排列而成。

在栈中，只能在栈顶进行插入和删除操作，其他位置的元素无法直接访问。

栈具有两个基本操作：压栈（push）和弹栈（pop）。

其中，压栈将一个元素添加到栈顶，弹栈则是删除栈顶的元素。

除了基本操作外，栈还具有其他常见的操作，如获取栈顶元素（top）、判断栈是否为空（empty）等。

正文内容：一、栈的基本操作1.压栈（push）push操作的实现原理和步骤在实际应用中的使用场景和例子2.弹栈（pop）pop操作的实现原理和步骤在实际应用中的使用场景和例子3.获取栈顶元素（top）top操作的实现原理和步骤在实际应用中的使用场景和例子4.判断栈是否为空（empty）empty操作的实现原理和步骤在实际应用中的使用场景和例子5.栈的大小（size）size操作的实现原理和步骤在实际应用中的使用场景和例子二、栈的应用场景1.括号匹配使用栈实现括号匹配的原理和过程在编译器、计算表达式等领域中的应用2.浏览器的后退和前进功能使用栈来记录浏览器访问历史的原理和过程实现浏览器的后退和前进功能3.函数调用和递归使用栈来实现函数调用和递归的原理和过程在程序执行过程中的应用和注意事项4.实现浏览器缓存使用栈来实现浏览器缓存的原理和过程提高用户浏览速度的实际应用案例5.撤销操作使用栈来实现撤销操作的原理和过程在编辑器、图形处理软件等领域的实际应用总结：本文详细介绍了栈的操作，包括基本操作（压栈、弹栈、获取栈顶元素、判断栈是否为空、栈的大小）和应用场景（括号匹配、浏览器的后退和前进功能、函数调用和递归、实现浏览器缓存、撤销操作）。

通过了解栈的操作和应用，我们可以更好地理解数据结构中的栈，并能够在实际问题中灵活运用栈的特性。

堆栈寄存器实验一、实验目的1、熟悉堆栈概念2、熟悉堆栈寄存器的组成和硬件电路二、实验要求按照实验步骤完成实验项目，对4个堆栈寄存器进行读出、写入数据操作。

三、实验原理1、堆栈寄存器组实验构成(图2-5-1)本系统内有4个寄存器R0~R3，寄存器组由4个74LS374组成，由1片74LS139（2-4译码器）来选择4个74LS374，并且由2片74LS32来组成控制线。

8芯插座R-IN、R-OUT作为数据输入、输出端，可通过短8芯扁平电缆把数据输入、输出端连接到数据总线上。

图2-5-12、堆栈寄存器组原理由SA、SB两根控制线通过74LS139译码来选择4个寄存器（74LS374）。

当WR＝0时，表示数据总线向寄存器写入数据，RCK为寄存器的工作脉冲，在有上升沿时把总线上数据打入74LS139选择的那个寄存器。

当RR=0时，74LS139所选择的寄存器上的数据输出至数据总线。

在本系统内使用了WR=0作为写入允许，RCK信号为上升沿时打入数据、RR=0时数据输出。

3、控制信号说明四、实验步骤实验1 对4个寄存器进行写入操作将R-IN(8芯盒形插座)与CPT-B板上的二进制开关单元中J03插座相连(对应二进制开关H0~H7)，R-OUT可通过短8芯扁平电缆与数据总线上DJ4相连。

把RR、WR、SA、SB接入二进制拨动开关（SA，SB借用X0，X1的H12，1、把数据写入寄存器R0)按启停单元中的运行按钮，置实验平台为运行状态。

置WR=0、RR=1按脉冲单元中的PLS1脉冲按键，在RCK上产生一个上升沿的脉冲，把11H 打入R0寄存器。

2、把数据写入寄存器R1置二进制开关H0~H7(D0~D7)为22H，各控制信号对应开关如下表。

按脉冲单元中的PLS1脉冲按键，在RCK上产生一个上升沿的脉冲，把22H 打入R1寄存器。

3、把数据写入寄存器R2按脉冲单元中的PLS1脉冲按键，在RCK上产生一个上升沿的脉冲，把33H 打入R2寄存器。

一、实验目的1. 理解栈的基本概念和操作。

2. 掌握栈的创建、入栈、出栈、判断栈空和栈满等基本操作。

3. 通过实验加深对栈在实际问题中的应用理解。

二、实验仪器1. 计算机一台2. 编程语言：C/C++或Python3. 输入设备：键盘、鼠标4. 输出设备：显示器、打印机三、实验步骤1. 创建栈（1）定义栈的数据结构，包括栈的最大容量、栈顶指针、栈底指针和栈元素数组。

（2）初始化栈，设置栈顶指针为-1，表示栈为空。

2. 入栈操作（1）判断栈是否已满，如果已满，则返回错误信息；如果未满，则将元素插入到栈顶指针指向的位置。

（2）将栈顶指针向上移动一位，表示栈顶元素已增加。

3. 出栈操作（1）判断栈是否为空，如果为空，则返回错误信息；如果栈不为空，则取出栈顶元素。

（2）将栈顶指针向下移动一位，表示栈顶元素已减少。

4. 判断栈空（1）判断栈顶指针是否为-1，如果是，则表示栈为空；如果不是，则表示栈不为空。

5. 判断栈满（1）判断栈顶指针是否等于栈的最大容量减1，如果是，则表示栈已满；如果不是，则表示栈未满。

6. 实验验证（1）创建一个栈，并初始化。

（2）进行一系列的入栈和出栈操作，观察栈的变化。

（3）验证栈空和栈满的判断是否正确。

四、实验结论1. 通过实验，我们成功地实现了栈的创建、入栈、出栈、判断栈空和栈满等基本操作。

2. 实验结果表明，栈是一种后进先出（LIFO）的数据结构，在实际问题中具有广泛的应用。

3. 栈在实际应用中可以解决许多问题，如括号匹配、表达式求值、递归算法等。

五、反思体会1. 在实验过程中，我们深入理解了栈的基本概念和操作，为后续学习数据结构打下了坚实的基础。

2. 通过编写程序实现栈操作，我们提高了编程能力，学会了如何将理论知识应用于实际编程。

3. 在实验过程中，我们遇到了一些问题，如栈满时的错误处理、栈空时的错误处理等。

通过查阅资料和讨论，我们找到了解决方案，提高了自己的问题解决能力。