(完整word版)顺序栈基本操作实验报告

第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）测试程序：验证了栈在程序设计中的应用。

顺序栈实验报告1. 实验目的本实验旨在通过实现顺序栈的基本操作，加深对栈的理解，并学习如何使用顺序栈解决实际问题。

2. 实验内容本实验包含以下内容：1.实现栈的初始化操作，并判断栈是否为空；2.实现入栈操作，将元素插入栈顶；3.实现出栈操作，将栈顶元素删除，并返回删除的元素；4.实现获取栈顶元素的操作，不改变栈的结构；5.实现获取栈的长度操作。

3. 实验步骤3.1 栈的初始化首先，我们需要定义一个顺序栈的结构体，其中包括栈的容量、栈顶指针和存放元素的数组。

栈的容量可以根据实际需要进行调整，栈顶指针初始值为-1。

#define MAX_SIZE 100typedef struct {int data[MAX_SIZE];int top;} SqStack;然后，我们可以编写初始化栈的函数：void InitStack(SqStack *s) {s->top = -1;}3.2 判断栈是否为空我们可以通过栈顶指针的值是否等于-1来判断栈是否为空，编写如下函数：int IsEmpty(SqStack *s) {if (s->top == -1) {return1;} else {return0;}}3.3 入栈操作入栈操作即将元素插入栈顶。

在插入元素前，我们需要判断栈是否已满。

若栈未满，则将元素插入栈顶，并更新栈顶指针的值。

编写如下函数：int Push(SqStack *s, int x) {if (s->top == MAX_SIZE - 1) {return0; // 栈满，插入失败} else {s->top++;s->data[s->top] = x;return1; // 插入成功}}3.4 出栈操作出栈操作即将栈顶元素删除，并返回删除的元素。

在删除元素前，我们需要判断栈是否为空。

若栈不为空，则将栈顶元素删除，并更新栈顶指针的值。

编写如下函数：int Pop(SqStack *s, int *x) {if (IsEmpty(s)) {return0; // 栈空，删除失败} else {*x = s->data[s->top];s->top--;return1; // 删除成功}}3.5 获取栈顶元素获取栈顶元素不改变栈的结构，只需要返回栈顶指针对应的元素即可。

栈的实验报告一、实验目的本次实验的主要目的是深入理解栈这种数据结构的基本概念和操作原理，并通过实际编程实现来巩固对栈的特性和应用的掌握。

二、实验环境本次实验使用的编程语言为C+＋，编程环境为Visual Studio 2019。

三、实验原理栈（Stack）是一种特殊的线性表，其操作遵循“后进先出”（Last In First Out，LIFO）的原则。

栈只允许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），另一端则被称为栈底（Bottom）。

栈的基本操作包括：1、｀Push`（入栈）：将元素添加到栈顶。

2、｀Pop`（出栈）：删除并返回栈顶元素。

3、｀Top`（获取栈顶元素）：返回栈顶元素，但不删除它。

4、｀IsEmpty`（判断栈是否为空）：如果栈为空，返回｀true`，否则返回｀false`。

四、实验内容与步骤1、定义栈的数据结构｀｀｀cppclass Stack ｛private:int stackArray;int top;int capacity;public:Stack(int size) ｛capacity ＝ size;stackArray ＝ new intcapacity; top ＝－1;｝～Stack(）｛delete stackArray;｝void Push(int element) ｛if （top ＝＝ capacity 1) ｛std:：cout ＜＜＂Stack Overflow!＂＜＜ std:：endl; return;｝stackArray+＋top ＝ element;｝int Pop(）｛if （IsEmpty(））｛std:：cout ＜＜＂Stack Underflow!＂＜＜ std:：endl; return －1;｝int element ＝ stackArraytop;stackArraytop ＝ 0;return element;｝int Top(）｛if （IsEmpty(））｛std:：cout ＜＜＂Stack is empty!＂＜＜ std:：endl; return －1;｝return stackArraytop;｝bool IsEmpty(）｛return top ＝＝－1;｝void PrintStack(）｛for （int i ＝ top; i ＞＝ 0; i) ｛std:：cout ＜＜ stackArrayi ＜＜＂＂；｝std:：cout ＜＜ std:：endl;｝｝；｀｀｀2、测试栈的基本操作｀｀｀cppint main(）｛Stack stack(5)；stackPush(10)；stackPush(20)；stackPush(30)；std:：cout ＜＜＂Top element: ＂＜＜ stackTop(）＜＜ std:：endl;stackPop(）；std:：cout ＜＜＂Top element after pop: ＂＜＜ stackTop(）＜＜std:：endl;stackPrintStack(）；return 0;｝｀｀｀五、实验结果与分析在实验过程中，我们成功地实现了栈的基本操作，并对其进行了测试。

栈和队列基本操作实验报告实验目的1. 了解栈和队列的基本概念和特点；2. 掌握栈和队列的基本操作，包括插入、删除、判空、判满等；3. 加深对数据结构的理解，提高编程能力。

实验原理1. 栈(Stack)是一种“先进后出”(Last In First Out，简称LIFO)的数据结构，类似于一摞盘子，最先放入的盘子在最底下，最后放入的盘子在最上面，取出盘子时也是从上往下取出。

2. 队列(Queue)是一种“先进先出”(First In First Out，简称FIFO)的数据结构，类似于排队，先来的人先进队列，后来的人排在后面，服务员按照队列顺序依次为每个人提供服务。

实验内容1. 栈的实现栈的基本操作包括入栈(push)、出栈(pop)、判空(empty)、栈顶(top)。

本次实验选择使用顺序栈来实现，并通过代码模拟栈的基本操作。

在顺序栈的实现中，需要设置栈顶指针(top)、初始化栈、入栈、出栈、判空、判满等操作，其中最关键的是入栈和出栈操作。

入栈操作：在栈顶指针(top)的位置加1，将元素e放到栈顶```void push(SqStack &s, ElemType e){if (s.top == MAXSIZE - 1) // 栈满return;s.top++; // 栈顶指针加1s.data[s.top] = e; // 将元素e放到栈顶return;}```出队操作：将队头元素弹出，队头指针(front)加1实验结果1. 栈的实现通过栈的实现，我们可以进行压入和弹出元素的操作。

下面是一段示例代码：通过本次实验，我学会了栈和队列的基本概念和特点，掌握了栈和队列的基本操作，如插入、删除、判空、判满等。

这些基本操作是数据结构中的重要部分，对于算法的实现与性能优化都有很大的帮助。

此外，在实现中，我们还需要注意栈和队列指针的变化，以及对于空栈和空队列的处理。

通过本次实验，我加深了对数据结构的理解，同时也提升了编程能力。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==顺序栈实验报告篇一：数据结构顺序栈实验报告一、设计人员相关信息1. 设计者姓名、学号和班号：12地信李晓婧 1201X2429832. 设计日期：201X.3. 上机环境：VC++6.0二、程序设计相关信息1. 实验题目：编写一个程序，实现顺序栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序，完成如下功能：（1）初始化栈（2）判断栈是否为空（3）依次进栈元素a,b,c,d,e（4）判断栈是否为空（5）输出栈长度（6）输出从栈顶到栈底元素（7）输出出栈序列（8）判断栈是否为空（9）释放栈2. 实验项目组成：栈的初始化、销毁、判断是否为空、进栈、出栈、取栈顶元素。

3. 实验项目的程序结构（程序中的函数调用关系图）：4. 实验项目包含的各个文件中的函数的功能描述：（1）初始化栈InitStack：建立一个新的空栈，实际上将栈顶指针指向-1即可。

（2）销毁栈DestroyStack：释放栈占用的存储空间（3）判断栈是否为空StackEmpty：栈为空的条件是s->op==-1。

（4）进栈Push：在栈不满的条件下，先将栈顶指针增1，然后在栈顶指针指向位置插入元素e。

（5）出栈Pop：在栈不为空的条件下，先将栈顶元素赋给e，然后将栈顶指针减1.（6）取栈顶元素GetTop：在栈不为空的条件下，将栈顶元素赋给e。

5. 算法描述或流程图：#include "stdio.h"#include "malloc.h"#include<stdlib.h>#define MaxSize 50typedef char ElemType;typedef struct{ElemType data[MaxSize];int top; /*栈顶指针*/}SqStack;//定义顺序栈类型void InitStack(SqStack*&s)/*初始化*/{s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;//栈顶指针置为-1}void DestroyStack(SqStack *&s)/*销毁*/{free(s);}int StackEmpty(SqStack*s)/*判断是否为空*/{return(s->top==-1);}int push(SqStack *&s,ElemType a[],int n){int i; if(s->top==MaxSize-1)//栈满的情况，即栈上溢出 return 0; for(i=0;i<n;i++){ s->top++; //栈顶指针增1s->data[s->top]=a[i];//元素e放在栈顶指针处}int Pop(SqStack*&s,ElemType &e)/*出栈一个元素*/ {if(s->top==-1)//栈为空的情况，即栈下溢出 return 0;e=s->data[s->top]; //取栈顶元素s->top--; //栈顶指针减1return 1;}} return 1;int GetTop(SqStack *s,ElemType &e)/*取栈顶元素*/ {if(s->top==-1) //栈为空的情况，即栈下溢出 return 0;e=s->data[s->top];//取栈顶元素return 1;}int StackLength(SqStack *s)/*求栈长度*/{return(s->top+1);}void DispStack(SqStack *s){}void main(){int i,j;ElemType str[5]={'a','b';,'c','d','e'}; //定义字符数组 SqStack *st;//定义栈InitStack(st);/*初始化*/i=StackEmpty(st);//判断栈是否为空if(i==0) int i; for(i=s->top;i>=0;i--) printf("%c",s->data[i]); printf("\n");printf("顺序栈非空\n"); else printf("顺序栈为空\n");push(st,str,5); //进栈j=StackEmpty(st);if(j==0)printf("顺序栈非空\n"); else printf("顺序栈为空\n");printf("栈长度为：%d\n",StackLength(st)); //输出栈长度。

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

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

二、实验内容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;}```五、实验心得通过本次实验，我对栈的基本操作有了更深入的理解。

引言：栈是一种常见的数据结构，它具有特殊的操作规则，即先进后出（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.撤销操作使用栈来实现撤销操作的原理和过程在编辑器、图形处理软件等领域的实际应用总结：本文详细介绍了栈的操作，包括基本操作（压栈、弹栈、获取栈顶元素、判断栈是否为空、栈的大小）和应用场景（括号匹配、浏览器的后退和前进功能、函数调用和递归、实现浏览器缓存、撤销操作）。

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

（封面）学生实验报告学院：国际经贸学院课程名称：数据结构专业班级：09电子商务姓名：学号：学生实验报告（经管类专业用）一、实验目的及要求：1、目的通过实验，实现顺序栈的各种基本运算。

2、内容及要求编写一个程序，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成下列功能：（1）初始化栈S。

（2）判断栈S是否非空。

（3）依次进栈元素a，b，c，d，e。

（4）判断栈S是否非空。

（5）输出栈的长度。

（6）输出从栈顶到栈底的元素。

（7）输出出栈序列；（8）判断链栈S是否为空；（9）释放链栈二、仪器用具：三、实验方法与步骤:一、查阅顺序栈等相关资料，熟悉顺序栈基本概念和流程二、“开展”顺序栈实验流程三、整理实验数据和文档，总结实验的过程，编写实验报告四、实验结果与数据处理：1、顺序栈的代码：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct{ElemType data[MaxSize];int top; //栈顶指针} SqStack;void InitStack(SqStack *&s){s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;}void ClearStack(SqStack *&s){free(s);}int StackLength(SqStack *s){return(s->top+1);}int StackEmpty(SqStack *s){return(s->top==-1);}int Push(SqStack *&s,ElemType e) {if (s->top==MaxSize-1)return 0;s->top++;s->data[s->top]=e;return 1;}int Pop(SqStack *&s,ElemType &e) {if (s->top==-1)return 0;e=s->data[s->top];s->top--;return 1;}int GetTop(SqStack *s,ElemType &e) {if (s->top==-1)return 0;e=s->data[s->top];return 1;}void DispStack(SqStack *s){int i;for (i=s->top;i>=0;i--)printf("%c ",s->data[i]);printf("\n");void main() {// 主函数SqStack S=(SqStack *)malloc(sizeof(SqStack)); printf("(1)初始化顺序栈\n");InitStack(S);printf("(2)判断顺序栈是否为空:\n"); StackEmpty(S);printf("(3)依次进栈元素a,b,c,d,e:\n");Push(S,'a');Push(S,'b');Push(S,'c');Push(S,'d');Push(S,'e');printf("(4)判断顺序栈是否为空:\n"); StackEmpty(S);printf("(5)输出栈长度:%d\n",StackLength(S)); printf("(6)输出从栈顶到栈底的元素:\n"); StackTraverse(S);printf("(7)读出栈顶元素:%d\n",GetTop(S,e));printf("(8)删除栈顶元素:%d\n",Pop(S,e));printf("(9)输出从栈顶到栈底的元素:\n");StackTraverse(S);printf("(10)判断顺序栈是否为空\n");StackEmpty(S);printf("(11)释放栈。

第1篇一、实验目的本次实验旨在通过实际操作，加深对栈这一数据结构的理解，掌握栈的基本操作，包括初始化、入栈、出栈、取栈顶元素、判栈空等。

同时，通过实验练习，提高编程能力和问题解决能力。

二、实验内容1. 栈的定义及特点2. 栈的顺序存储结构3. 栈的链式存储结构4. 栈的基本操作5. 栈的应用实例三、实验过程1. 栈的定义及特点栈是一种后进先出（LIFO）的数据结构，它只允许在一端进行插入和删除操作。

栈的顶元素总是最后被插入的元素，也是最先被删除的元素。

2. 栈的顺序存储结构顺序存储结构是使用数组来实现栈。

定义一个数组作为栈的存储空间，同时定义一个指针top来指示栈顶元素的位置。

3. 栈的链式存储结构链式存储结构是使用链表来实现栈。

定义一个节点结构体，其中包含数据和指向下一个节点的指针。

头节点作为栈顶元素。

4. 栈的基本操作（1）初始化：创建一个空栈，top指针指向栈底。

（2）入栈：将新元素插入到栈顶。

如果栈满，则进行扩容。

（3）出栈：删除栈顶元素，并将其返回。

如果栈空，则返回错误信息。

（4）取栈顶元素：返回栈顶元素的值，但不删除栈顶元素。

（5）判栈空：判断栈是否为空，如果为空，则返回true；否则，返回false。

5. 栈的应用实例（1）括号匹配检验：利用栈判断一个字符串中的括号是否匹配。

（2）算术表达式求值：利用栈实现算术表达式求值，包括四则运算和括号。

四、实验结果与分析1. 初始化栈初始化栈后，栈为空，top指针指向栈底。

2. 入栈操作将元素1、2、3依次入栈，栈的状态如下：```top -> 3 -> 2 -> 1```3. 出栈操作依次出栈元素，栈的状态如下：```top -> 2 -> 1```4. 取栈顶元素取栈顶元素2，栈的状态不变。

5. 判栈空当栈中只有一个元素时，判断栈为空，返回false。

6. 括号匹配检验对于字符串"((()))"，括号匹配检验结果为true；对于字符串"(()))"，括号匹配检验结果为false。

一、实验目的本次实验旨在使学生掌握栈的顺序存储结构，理解栈的基本操作，并能够通过编程实现栈的初始化、入栈、出栈、判空、取栈顶等基本功能。

同时，通过实验加深对数据结构中栈的应用理解，提高编程能力。

二、实验环境1. 操作系统：Windows 102. 编程语言：C/C++3. 开发环境：Visual Studio三、实验内容1. 栈的顺序存储结构- 实现栈的顺序存储结构，包括定义栈的存储空间和栈顶指针。

- 设计栈的初始化、判空、入栈、出栈、取栈顶等基本操作。

2. 栈的基本操作- 编写代码实现栈的初始化函数，初始化栈的空间和栈顶指针。

- 实现判空函数，检查栈是否为空。

- 实现入栈函数，将元素添加到栈顶。

- 实现出栈函数，从栈顶移除元素。

- 实现取栈顶函数，获取栈顶元素但不移除。

3. 栈的应用- 利用栈实现十进制数与二进制数的转换。

- 利用栈实现函数调用栈，模拟函数调用的过程。

四、实验步骤1. 定义栈的结构体```ctypedef struct {int array; // 动态分配的数组，用于存储栈元素 int top; // 栈顶指针int maxSize; // 栈的最大容量} SeqStack;```2. 实现栈的基本操作- 初始化栈```cvoid InitStack(SeqStack s, int maxSize) {s->array = (int )malloc(sizeof(int) maxSize); s->top = -1;s->maxSize = maxSize;}```- 判空```cint IsEmpty(SeqStack s) {return s->top == -1;}```- 入栈```cint Push(SeqStack s, int x) {if (s->top == s->maxSize - 1) { return 0; // 栈满}s->array[++s->top] = x;return 1;}```- 出栈```cint Pop(SeqStack s, int x) {if (IsEmpty(s)) {return 0; // 栈空}x = s->array[s->top--];return 1;}```- 取栈顶```cint GetTop(SeqStack s, int x) {if (IsEmpty(s)) {return 0; // 栈空}x = s->array[s->top];return 1;}```3. 实现十进制数与二进制数的转换- 编写函数实现十进制数转换为二进制数，利用栈存储转换过程中的余数。

数据构造实验三课程数据构造实验名称序次栈根本操作第页专业班级学号姓名实验日期：年月日评分一、实验目的1．熟悉并能实现栈的定义和根本操作。

2．认识和掌握栈的应用。

二、实验要求1．进行栈的根本操作时要注意栈"后进先出 " 的特点。

2．编写完满程序完成下面的实验内容并上机运行。

3．整理并上交实验报告。

三、实验内容1．编写程序任意输入栈长度和栈中的元素值，构造一个序次栈，对其进行清空、销毁、入栈、出栈以及取栈顶元素操作。

2．编写程序实现表达式求值，即考据某算术表达式的正确性，假设正确，那么计算该算术表达式的值。

主要功能描述以下：（1〕从键盘上输入表达式。

（2〕解析该表达式可否合法：a)是数字，那么判断该数字的合法性。

假设合法，那么压入数据到货仓中。

b)是规定的运算符，那么依照规那么进行办理。

在办理过程中，将计算该表达式的值。

c)假设是其他字符，那么返回错误信息。

（3〕假设上述办理过程中没有发现错误，那么认为该表达式合法，并打印办理结果。

程序中应主要包含下面几个功能函数：l void initstack()：初始化货仓l int Make_str()：语法检查并计算l int push_operate(int operate)：将操作码压入货仓l int push_num(double num)：将操作数压入货仓l int procede(int operate)：办理操作码l int change_opnd(int operate)：将字符型操作码变换成优先级l int push_opnd(int operate)：将操作码压入货仓l int pop_opnd() ：将操作码弹出货仓l int caculate(int cur_opnd)：简单计算+，-，*，/l double pop_num()：弹出操作数四、实验步骤〔描述实验步骤及中间的结果或现象。

在实验中做了什么事情，怎么做的，发生的现象和中间结果〕第一题：#include <iostream>using namespace std;#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW -1#define OK 1#define NO -1#define NULL 0typedef int Status;typedef char SElemType; typedef struct{//储藏空间初始分配量// 储藏空间分配增量SElemType *base; SElemType *top;// 在栈构造从前和销毁此后，// 栈顶指针base的值为NULLint stacksize;//当前已分配的储藏空间，以元素为单位} SqStack;Status Initstack(SqStack &S)// 构造一个空栈S{S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize= STACK_INIT_SIZE;return OK;}//InitStackStatus StackEmpty(SqStack &S){if(S.base==S.top)return OK;elsereturn NO;}Status ClearStack (SqStack &S)// 把 S 置为空{if(S.base=S.top);return OK;}Status DsetroyStack (SqStack &S)// 销毁栈 S{S.base=NULL;return OK;}Status Push(SqStack &S,SElemType e)//插入元素 e 为新的栈顶元素{if (S.top-S.base>=S.stacksize){S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base) //储藏分配失败exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return OK;}//PushStatus Pop(SqStack &S,SElemType &c)// 假设栈不空，那么删除S 的栈顶元素，用 c 返回其值，并返回OK；否那么返回ERROR{if(S.top==S.base)return NO;c=*--S.top;return OK;}//PopStatus GetTop(SqStack &S,SElemType &e){if (S.top==S.base)return NO;e=*(S.top-1);return OK;}//GetTopint main(){SqStack S;Initstack(S);cout<<" 输入要压到栈中的元素!"<<endl;char c;while((c=getchar())!='\n'){Push(S,c);}GetTop(S,c);cout<<" 栈顶元素为："<<c<<endl;//ClearStack (S);//DsetroyStack(S);for(int i=0;S.top!=S.base;i++){Pop(S,c);cout<<" 栈中第 "<<i+1<<" 元素的值 :";cout<<c<<endl;}return 0;}第二题：#include<iostream>using namespace std;#define STACK_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -1#define OK 1#define NO 0typedef int Status;typedef char SElemType;typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;int main(){char GetTop(SqStack &s);Status Initstack(SqStack &s);Status push_operate(SqStack &s,SElemType e);Status push_num(SqStack &s,int e);Status Stackempty(SqStack &s);Status pop_num(SqStack &s,int &c);Status pushoperate(SElemType operate);Status pushnum(SElemType num);Status caculate(SElemType a,SElemType operate,SElemType b);Status pop_operate(SqStack &s,SElemType &c);Status change(SElemType e);char Precede(SElemType a,SElemType b);char Operatecxz();int m;m=Operatecxz();cout<<m<<endl;return 0;}Status change(SElemType e){int m;m=e-48;return m;}Status Initstack(SqStack &s){s.base=(SElemType *)malloc(STACK_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_SIZE;return OK;}Status Stackempty(SqStack &s){if(s.base==s.top)return OK;elsereturn NO;}Status push_num(SqStack &s,int e){if(s.top-s.base>=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;return OK;}Status push_operate(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)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;return OK;}Status pop_operate(SqStack &s,SElemType &c){if(s.top==s.base)return NO;c=*--s.top;return OK;}Status pop_num(SqStack &s,int &c){if(s.top==s.base)return NO;c=*--s.top;return OK;}char GetTop(SqStack &s){char c;if(s.top==s.base)return NO;c=*(s.top-1);return c;}Status caculate(int a,SElemType operate,int b){int s;if(operate=='+')s=a+b;if(operate=='-')s=a-b;if(operate=='*')s=a*b;if(operate=='/')s=a/b;return s;}Status In(SElemType c){if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')') return OK;if(c>='0'&&c<='9')return NO;return -1;}char Precede(SElemType a,SElemType b){if(a=='+'||a=='-'){if(b=='+'||b=='-'||b==')'||b=='#')return '>';if(b=='*'||b=='/'||b=='(')return '<';}if(a=='*'||a=='/'){if(b=='+'||b=='-'||b==')'||b=='*'||b=='/'||b=='#')return '>';if(b=='(')return '<';}if(a=='('){if(b==')')return '=';if(b=='+'||b=='-'||b=='*'||b=='/')return '<';if(b=='#')return ' ';}if(a==')'){if(b==')')return ' ';if(b=='+'||b=='-'||b=='*'||b=='/'||b=='('||b=='#')return '>';}if(a=='#'){if(b=='#')return '=';if(b=='+'||b=='-'||b=='*'||b=='/'||b=='(')return '<';if(b==')')return ' ';}return ' ';}char Operatecxz(){SqStack Operate,Num;char c,e,x;int num,a,b,flat=1,sz=0;Initstack(Operate);push_operate(Operate,'#');Initstack(Num);c=getchar();while(c!='#'||GetTop(Operate)!='#'){if(In(c)==-1){cout<<"input error!"<<endl;flat=0;break;}if(In(c)!=1){if(sz==0){num=change(c);sz=1;c=getchar();continue;}if(sz==1)num=num*10+change(c);c=getchar();continue;}else{if(sz==1)push_num(Num,num);sz=0;x=GetTop(Operate);switch(Precede(GetTop(Operate),c)){case '<':{push_operate(Operate,c);c=getchar();break;}case '=':{pop_operate(Operate,e);c=getchar();break;}case '>':{pop_num(Num,a);pop_operate(Operate,e);pop_num(Num,b);push_num(Num,caculate(b,e,a));break;}}}}pop_operate(Operate,e);if(e!='#')flat=0;if(flat==1){pop_num(Num,a);return a;}if(flat==0)return 0;}五．实验结果与谈论〔描述最后获取的结果，并进行解析说明，可能的误差原因〕第一题： 1 把主函数中的ClearStack (S);DsetroyStack(S) 说明掉的结果：2 不把 ClearStack (S)说明掉，把栈清空：3 不把 DsetroyStack(S) 说明掉，即销毁栈：出现一堆乱码，说明销毁成功。

顺序栈实验报告顺序栈实验报告一、引言顺序栈是一种基本的数据结构，它具有先进先出的特点。

在本次实验中，我们将学习并实现顺序栈的基本操作，包括入栈、出栈、判空和获取栈顶元素等。

通过这次实验，我们将深入理解栈的概念和原理，并掌握如何使用顺序栈解决实际问题。

二、实验目的1. 学习顺序栈的定义和基本操作。

2. 掌握顺序栈的实现方法。

3. 理解顺序栈的应用场景。

三、实验过程1. 定义顺序栈的结构在本次实验中，我们选择使用数组来实现顺序栈。

首先，我们需要定义一个栈的结构体，包括栈的容量和栈顶指针。

2. 初始化栈在实验开始时，我们需要初始化一个空栈。

这里，我们将栈顶指针设置为-1，表示栈为空。

3. 入栈操作当我们需要将一个元素压入栈时，我们首先判断栈是否已满。

如果栈已满，则无法进行入栈操作；否则，我们将栈顶指针加1，并将元素放入栈顶位置。

4. 出栈操作当我们需要从栈中弹出一个元素时，我们首先判断栈是否为空。

如果栈为空，则无法进行出栈操作；否则，我们将栈顶指针减1，并返回栈顶元素。

5. 判空操作判断栈是否为空可以通过检查栈顶指针是否等于-1来实现。

如果栈顶指针等于-1，则表示栈为空；否则，表示栈非空。

6. 获取栈顶元素要获取栈顶元素，我们只需返回栈顶指针所指向的元素即可。

需要注意的是，此操作不会改变栈的状态。

四、实验结果通过实验，我们成功实现了顺序栈的基本操作，并进行了测试。

在测试过程中，我们发现顺序栈可以有效地存储和操作数据。

我们可以轻松地将元素入栈和出栈，并通过判断栈是否为空来避免错误操作。

同时，获取栈顶元素的操作也非常方便，可以快速获取栈中最新的数据。

五、实验总结通过本次实验，我们深入了解了顺序栈的概念和原理，并掌握了顺序栈的基本操作。

顺序栈作为一种基本的数据结构，在实际应用中具有广泛的用途。

例如，在计算机程序中，我们可以使用顺序栈来实现函数调用的堆栈，以便保存函数的返回地址和局部变量等信息。

此外，在表达式求值、括号匹配和逆波兰表达式等问题中，顺序栈也发挥着重要的作用。

实验三栈和队列3.1实验目的：（1）熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现；（2）熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基本操作在队列的顺序存储结构和链式存储结构上的实现。

3.2实验要求：（1）复习课本中有关栈和队列的知识；（2）用C语言完成算法和程序设计并上机调试通过；（3）撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。

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;}elseprintf("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,6)");scanf("%d",&cord);printf("\n");switch(cord){ q=(SqStack*)malloc(sizeof(SqStack));InitStack(q);OutStack(q);}break;case 2:{ printf("请输入要插入的数据元素：a=");scanf("%d",&a);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;exit(0);}}while (cord<=6);}[实验2] 栈的链式表示和实现实验内容与要求:编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化链栈（2）链栈置空（3）入栈（4）出栈（5）取栈顶元素（6）遍历链栈分析:链栈是没有附加头结点的运算受限的单链表。

第1篇一、实验目的1. 理解栈的基本概念和顺序存储结构；2. 掌握顺序栈的初始化、进栈、出栈、读栈顶元素等基本操作；3. 通过实际编程实现顺序栈，并验证其功能。

二、实验内容1. 栈的基本概念栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。

栈的插入和删除操作遵循“后进先出”（LIFO）的原则。

2. 顺序栈的定义顺序栈使用数组来存储栈中的元素，数组的大小定义为MaxSize。

栈顶指针top 指向栈顶元素。

3. 顺序栈的基本操作（1）初始化：将栈顶指针top设置为-1，表示栈为空。

（2）进栈：判断栈是否已满，如果未满，则将新元素放入栈顶，并将栈顶指针top加1。

（3）出栈：判断栈是否为空，如果栈不为空，则将栈顶元素弹出，并将栈顶指针top减1。

（4）读栈顶元素：判断栈是否为空，如果栈不为空，则返回栈顶元素。

（5）栈的销毁：释放栈所占用的内存空间。

4. 实验步骤（1）定义栈的最大容量MaxSize；（2）创建顺序栈结构体；（3）实现顺序栈的基本操作函数；（4）编写主函数，测试顺序栈的功能。

1. 定义栈的最大容量MaxSize为100；2. 创建顺序栈结构体，包含数组data和栈顶指针top；3. 实现顺序栈的基本操作函数，包括初始化、进栈、出栈、读栈顶元素和栈的销毁；4. 编写主函数，创建顺序栈，进行进栈、出栈、读栈顶元素等操作，并输出结果。

四、实验结果与分析1. 初始化顺序栈初始化顺序栈后，栈顶指针top为-1，表示栈为空。

2. 进栈操作当向顺序栈中进栈元素时，首先判断栈是否已满。

如果栈未满，则将新元素放入栈顶，并将栈顶指针top加1。

3. 出栈操作当从顺序栈中出栈元素时，首先判断栈是否为空。

如果栈不为空，则将栈顶元素弹出，并将栈顶指针top减1。

4. 读栈顶元素操作当读取栈顶元素时，首先判断栈是否为空。

如果栈不为空，则返回栈顶元素。

5. 栈的销毁当栈不再需要时，释放栈所占用的内存空间。

实验结果表明，顺序栈的基本操作能够正常进行，验证了顺序栈的正确性。

第五次实验报告——顺序栈、链栈的插入和删除一需求分析1、在演示程序中，出现的元素以数字出现定义为int型，2、演示程序在计算机终端上，用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在终端上3、顺序栈的程序执行的命令包括如下：（1）定义结构体（2）顺序栈的初始化及创建（3）元素的插入（4）元素的删除（5）顺序栈的打印结果3、链栈的程序执行的命令包括如下：（1）定义结构体（2）链栈的初始化及创建（3）元素的插入（4）元素的删除（5）链栈的打印结果二概要设计1、顺序栈可能需要用到有序表的抽象数据类型定义：ADT List{数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai ∈D, i=2,...,n }基本操作：InitStack(SqStack &S)操作结果：构造一个空栈Push(L,e)操作结果：插入元素e为新的栈顶元素Status Pop(SqStack &S)操作结果：删除栈顶元素}ADT List；2、链栈可能需要用到有序表的抽象数据类型定义：ADT List{数据对象:D={ai|ai∈ElemL, i=1,2,...,n, n≥0}数据关系:R1={<ai-1,ai>|ai-1,ai ∈D, i=2,...,n } 基本操作：LinkStack(SqStack &S)操作结果：构造一个空栈Status Push(L,e)操作结果：插入元素e为新的栈顶元素Status Pop(SqStack &S)操作结果：删除栈顶元素}ADT List；3、顺序栈程序包含的主要模块：(1) 已给定的函数库：（2）顺序栈结构体：（3）顺序栈初始化及创建:(4)元素插入(5)元素删除（6）主程序：4、链栈程序包含的主要模块：(1) 已给定的函数库：（2）链栈结构体：（3）链栈初始化及创建:(4)元素插入(5)元素删除(6)主程序：三详细设计线性栈：结构体#define STACK_INIT_SIZE 100//存储空间初始分配量#define STACKINCREMENT 10//存储空间分配增量typedef struct{int *base;//在构造栈之前和销毁之后，base的值为NULL int *top;//栈顶指针int stacksize;//当前已分配的存储空间，以元素为单位}SqStack#include"Base.h"主函数#include"construction.h"#include"stack_operation.c"int main(){SqStack S;int choice,e;S=InitStack();S=Input_Sq(S);printf("请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice=");scanf("%d",&choice);switch(choice){case 1:{printf("请输入插入元素的值e=");scanf("%d",&e);S=Push(S,e);printf("执行入栈操作后的线性栈为");Print_Stack(S);};break;case 2:{S=Pop(S);printf("执行出栈操作后的线性栈为");Print_Stack(S);};break;default : printf("您输入的值不合法");}}线性栈的创建SqStack InitStack()//线性栈的创建{SqStack S;S.base=(int*)malloc(STACK_INIT_SIZE * sizeof(int));//分配存储空间if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;return S;}输入函数SqStack Input_Sq(SqStack S)//输入函数{int n,i;printf("请输入元素个数n=");scanf("%d",&n);printf("请输入%d个元素",n);for(i=0;i<n;i++){scanf("%d",S.top);S.top++;}return S;}进栈函数SqStack Push(SqStack S,int e)//进栈函数{if(S.top-S.base>=S.stacksize)//判断栈是否为满，追加存储空间{S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(int));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;//插入元素return S;}出栈函数SqStack Pop(SqStack S)//删除函数{int e;if(S.top==S.base)printf("线性栈为空");e=*--S.top;return S;}输出函数void Print_Stack(SqStack S)//打印函数{int i;while(S.base!=S.top){for(i=0;i<S.top-S.base;i++){S.top--;printf("%5d",*S.top);}printf("\n");}库函数* Base.h (程序名) */#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */ #include<process.h> /* exit() *//* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSEl链栈程序：结构体typedef struct SNode//建立链表结构体{int data;struct SNode *next;}SNode,*LinkStack;主函数#include"Base.h"#include"construction.h"#include"LinkStack_operation.c"int main(){LinkStack S;int choice,e;S=Creatlist_Stack();printf("请选择执行的操作，输入1执行入栈操作，输入2执行出栈操作choice=");scanf("%d",&choice);switch(choice){case 1:{printf("请输入插入元素的值e=");scanf("%d",&e);S=Push(S,e);printf("执行操作入栈后的线性栈为");Print_Stack(S);};break;case 2:{S=Pop(S);printf("执行出栈操作后的线性栈为");Print_Stack(S);};break;default : printf("您输入的值不合法\n");}}创建链栈函数LinkStack Creatlist_Stack()//创建一个链栈{LinkStack S;LinkStack P;int i,n;S=(LinkStack)malloc(sizeof(SNode));S->next=NULL;/* 先建立一个链栈 */printf("请输入元素个数n=");scanf("%d",&n);printf("请输入%d个数据\n",n);i=0;scanf("%d",&S->data);for(i=1;i<n;++i){P=(LinkStack)malloc(sizeof(SNode)); /* 生成新结点 */P->next=S;S=P;scanf("%d",&S->data); /* 输入元素值 */}return S;}入栈函数LinkStack Push(LinkStack S,int e){LinkStack P;if(S==NULL)return ERROR;P=(LinkStack)malloc(sizeof(SNode));P->data=e;P->next=S;S=P;return S;}出栈函数LinkStack Pop(LinkStack S){LinkStack P,Q;P=S;S=S->next;free(P);return S;}输出函数void Print_Stack(LinkStack S){while(S){printf("%5d",S->data);S=S->next;}printf("\n");}库函数* Base.h (程序名) */#include<string.h>#include<ctype.h>#include<malloc.h> /* malloc()等 */#include<limits.h> /* INT_MAX等 */#include<stdio.h> /* EOF(=^Z或F6),NULL */ #include<stdlib.h> /* atoi() */#include<io.h> /* eof() */#include<math.h> /* floor(),ceil(),abs() */#include<process.h> /* exit() *//* 函数结果状态代码 */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSEl四调试分析:输出函数用了语句S->next!=NULL改正：语句S！=NULL五用户手册:看提示内容六测试结果线性栈：1）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1，请输入插入元素的值e=6，执行入栈操作后的线性栈为6 4 3 2 1 2）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为3 2 1链栈：1）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=1，请输入插入元素的值e=6，执行入栈操作后的线性栈为6 4 3 2 1 2）请输入元素的个数：4，请输入4个数据 1 2 3 4，请输入执行语句，选择输入1执行入栈操作，选择输入2执行出栈操作choice=2,执行出栈操作后的线性栈为3 2 1。

数据结构实验报告顺序栈的实现和基本操作一、需求分析（1）顺序栈◆栈的典型操作是入栈和出栈，前者将新元素压入栈中，后者弹出栈顶元素。

栈只提供对栈顶元素的访问操作，由top ( )完成。

Push ( )和Pop ( )还有Top ( )共同构成了栈的最小功能接口。

此外，为了方便使用，栈还有判空，判满和输出栈等功能。

◆输入形式及范围：输入形式为整型，范围为0~65535。

◆输出形式：在顺序栈的初始化后显示初始化成功，在判断栈是否为空时显示当前栈为空，入栈后显示入栈成功或者栈已满。

出栈时显示出栈元素或者栈为空。

输出栈时依次显示栈中元素。

◆程序功能：初始化栈，判断栈是否为空，判断栈是否为满，入栈，出栈，取栈顶元素，出栈同时返回栈顶元素和输出栈等功能。

◆测试数据：初始化后输入栈的长度为4。

判断栈是否为空。

进行5次入栈操作。

分别输入1 2 3 4 5输出栈。

执行2次出栈操作。

输出栈。

查看栈顶元素。

输出栈。

（2）队列◆队列的典型操作是入队和出队，前者将新元素压入队列中，后者弹出队首头元素。

队列只提供对队头元素和队尾元素的操作，由DeQueue ( ) 和EnQueue( )完成。

DeQueue还有EnQueue ( )共同构成了队列的最小功能接口。

此外，为了方便使用，队列还有判空，判满和输出队列等功能。

◆输入形式及范围：输入形式为整型，范围为0~65535。

◆输出形式：在顺序队列的初始化后显示初始化成功，在判断队列是否为空时显示当前队列为空，入队列后显示入队成功或者队列已满。

出队列时显示出队首元素或者队列为空。

输出队列时依次显示队列中元素。

◆程序功能：初始化队列，判断队列是否为空，判断队列是否为满，入队，出队，取队首元素，输出队列等功能。

◆测试数据：初始化后输入队列的长度为54。

判断队列是否为空。

进行5次入队操作。

分别输入1 2 3 4 5输出队列。

执行2次出队操作。

输出队列。

查看队首元素。

输出队列。

二、概要设计（1）顺序栈◆为了实现程序的功能，在.H文件中定义了栈的模板类. template <class T>class Stack{私有数据成员：private:栈的最大长度int MaxSize;栈顶位置int top;顺序栈首地址T *theArray;公有成员：public:栈的初始化void InitStack(int capacity=10);操作结果：初始化一个默认长度为10的空栈判断栈是否为空bool IsEmpty() const;初始条件：栈已存在。