下载文档原格式
第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）测试程序：验证了栈在程序设计中的应用。
谈顺序存储与链式存储的异同摘要：顺序存储与链式存储的应用范围较为广泛。
顺序存储就是用一组地址连续的存储单元依次存储该线性表中的各个元素，由于表中各个元素具有相同的属性，所以占用的存储空间相同，而链式存储无需担心容量问题，读写速度相对慢些，由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。
关键词：顺序存储链式存储顺序存储与链式存储异同一、什么是顺序存储在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。
顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。
采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。
但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。
二、简述链式存储在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).它不要求逻辑上相邻的元素在物理位置上也相邻.因此它没有顺序存储结构所具有的弱点,但也同时失去了顺序表可随机存取的优点.链式存储结构不要求逻辑上相邻的两个数据元素物理上也相邻，也不需要用地址连续的存储单元来实现。
因此在操作上，它也使得插入和删除操作不需要移动大量的结点。
线性表的链式存储结构主要介绍了单链表、循环链表、双向链表和静态链表四种类型，讨论了各种链表的基本运算和实现算法。
三、栈的存储结构：顺序存储和链式存储利用顺序存储方式实现的栈称为顺序栈。
栈的概念理解栈是一种数据结构，它是一种特殊的线性表，只能在表的一端进行插入和删除操作，该一端被称为栈顶，另一端被称为栈底。
栈的特点是后进先出（Last In First Out, LIFO）。
在栈中，最后插入的元素最先弹出，而最先插入的元素最后弹出。
这就好像是一堆盘子，你只能在最上面放盘子和拿盘子，不能随意放在下面的盘子上。
栈的这种特性使得它非常适合解决一些具有“倒序”需求的问题。
栈的基本操作包括入栈和出栈。
入栈（Push）是指将元素放入栈顶；出栈（Pop）是指从栈顶弹出元素。
除此之外，还有一些常用的操作，比如获取栈顶元素（Top）、判断栈是否为空（Empty）、获取栈中元素的个数（Size）等。
栈的实现可以用数组或链表来完成。
使用数组实现的栈叫作顺序栈，使用链表实现的栈叫作链式栈。
对于顺序栈，我们需要定义一个数组和一个整数来表示栈。
数组用于存储栈中的元素，整数用于记录栈顶元素的下标。
一开始，栈为空，栈顶下标可以初始化为-1。
插入元素时，需要判断栈是否已满，如果已满则无法插入；如果未满，将元素放入栈顶，同时栈顶下标加1。
删除元素时，需要判断栈是否为空，如果为空则无法删除；如果不为空，将栈顶元素弹出，并将栈顶下标减1。
对于链式栈，我们需要定义一个结构体来表示栈中的节点。
节点包括一个数据域和一个指向下一个节点的指针域。
和顺序栈类似，链式栈也需要一个指针来表示栈顶元素。
插入元素时，需要创建一个新节点，并将栈顶指针指向该节点，新节点的指针域指向原来的栈顶元素。
删除元素时，需要判断栈是否为空，如果为空则无法删除；如果不为空，将栈顶节点删除，并将栈顶指针指向下一个节点。
栈的应用非常广泛。
在计算机科学中，栈是一种重要的数据结构，它被用于实现函数调用、表达式求值、编译器的语法分析、操作系统的进程管理等。
在编程中，我们可以使用栈来解决一些具有“倒序”性质的问题，比如字符串反转、括号匹配、计算逆波兰表达式等。
此外，栈还被用于图的深度优先搜索（DFS）算法中的节点遍历顺序。
一、实验目的1. 理解堆栈的基本概念和原理；2. 掌握堆栈的顺序存储和链式存储方法；3. 熟悉堆栈的基本操作，如入栈、出栈、判断栈空、求栈顶元素等；4. 能够运用堆栈解决实际问题。
二、实验内容1. 堆栈的基本概念和原理；2. 堆栈的顺序存储和链式存储方法；3. 堆栈的基本操作实现；4. 堆栈的应用实例。
三、实验原理1. 堆栈的基本概念和原理：堆栈是一种特殊的线性表，它按照“后进先出”（LIFO）的原则组织数据。
即最后进入堆栈的数据元素最先出栈。
2. 堆栈的顺序存储方法：使用一维数组实现堆栈，栈顶指针top指向栈顶元素。
3. 堆栈的链式存储方法：使用链表实现堆栈，每个节点包含数据域和指针域。
4. 堆栈的基本操作实现：（1）入栈：将元素插入到栈顶，如果栈未满，则top指针加1，并将元素值赋给top指向的元素。
（2）出栈：删除栈顶元素，如果栈不为空，则将top指向的元素值赋给变量，并将top指针减1。
（3）判断栈空：如果top指针为-1，则表示栈为空。
（4）求栈顶元素：如果栈不为空，则将top指向的元素值赋给变量。
四、实验步骤1. 使用顺序存储方法实现堆栈的基本操作；2. 使用链式存储方法实现堆栈的基本操作；3. 编写程序，测试堆栈的基本操作是否正确；4. 分析实验结果，总结实验经验。
五、实验结果与分析1. 使用顺序存储方法实现堆栈的基本操作：（1）入栈操作：当栈未满时，将元素插入到栈顶。
（2）出栈操作：当栈不为空时，删除栈顶元素。
（3）判断栈空：当top指针为-1时，表示栈为空。
（4）求栈顶元素：当栈不为空时，返回top指向的元素值。
2. 使用链式存储方法实现堆栈的基本操作：（1）入栈操作：创建新节点，将其作为栈顶元素，并修改top指针。
（2）出栈操作：删除栈顶元素，并修改top指针。
（3）判断栈空：当top指针为NULL时，表示栈为空。
（4）求栈顶元素：返回top指针指向的节点数据。
3. 实验结果分析：通过实验，验证了顺序存储和链式存储方法实现的堆栈基本操作的正确性。
栈的表示及栈的应用实验心得
栈是一种常见的数据结构，特点是后进先出，常用于程序内存中的函数调用、表达式
求值等方面。
栈有多种表示方法，常见的包括顺序栈和链式栈。
在顺序栈中，使用一
个数组来表示栈，通过一个指针指向栈顶元素，实现栈的基本操作。
链式栈是在链表
的基础上实现栈，其中栈顶元素表示为链表的头结点。
在实验中，我通过编写程序来熟悉了使用栈。
具体来说，我设计了一个括号匹配程序。
该程序可以读取一个字符串，检查其中的括号是否匹配，如果匹配则输出“括号匹配”，否则输出“括号不匹配”。
在程序中，我使用顺序栈来实现检查括号匹配的功能。
具体来说，我遍历每一个字符，遇到左括号时则将其压入栈中，遇到右括号时则
判断栈顶元素是否为相应的左括号，如果匹配则弹出栈顶元素，继续遍历字符串，直
至遍历完成。
如果遍历完成后栈为空，则表示字符串中的括号匹配，否则表示不匹配。
通过这个实验，我对栈的表示和使用有了更深入的了解。
共享一下这个实验心得，希
望对其他学习数据结构的同学有所帮助。
实验三栈的顺序和链式存储的表示和实现实验目的：1.熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等。
2.掌握栈的基本操作在栈的顺序存储结构和链式存储结构上的实现。
实验内容：1.栈的顺序表示和实现编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。
（1）初始化顺序栈（2）插入一个元素（3）删除栈顶元素（4）取栈顶元素（5）便利顺序栈（6）置空顺序栈#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("error");p->top=-1;}//入栈void push(sqstack *p,elemtype x){}//出栈elemtype pop(sqstack *p){}//获取栈顶元素elemtype gettop(sqstack *p){elemtype x;if(p->top!=-1){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("这是一个空栈！\n");for(i=p->top;i>=0;i--)printf("第%d个数据元素是：%6d\n",i,p->stack[i]); }//置空顺序栈void setempty(sqstack *p){}//主函数main(){sqstack *q;int y,cord;elemtype a;do{printf("\n第一次使用必须初始化！\n\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){case 1:{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;case 6:exit(0);}}while(cord<=6);}2.栈的链式表示和实现编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能。
（1）初始化链栈（2）入栈（3）出栈（4）取栈顶元素（5）置空链栈（6）遍历链栈参考代码：#include <stdio.h>#include<stdlib.h>#include<malloc.h>#define null 0typedef 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){}//出栈elemtype poplstack(linkstack *s){}//取栈顶元素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"); int i,m,n,a;linkstack *s;s=(linkstack *)malloc (sizeof(linkstack));int cord;do{printf("\n第一次使用必须初始化!\n\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){case 1:{initstack(s);disp(s);}break;case 2:{printf("输入将要压入链栈的数据的个数:n=");scanf("%d",&n);printf("依次将%d个数据压入链栈:\n",n);for(i=1;i<=n;i++){scanf("%d",&a);pushlstack(s,a);}disp(s);}break;case 3:{printf("\n出栈操作开始!\n");printf("输入将要出栈的数据个数:m=");scanf("%d",&m);for(i=1;i<=m;i++){printf("\n第%d次出栈的数据是：%d\n",i,poplstack(s));}break;}case 4:{printf("\n\n链栈的栈顶元素为:%d\n\n",stacktop(s));}break;case 5:{setempty(s);disp(s);}break;case 6:exit(0);}}while(cord<=6);}实验总结：。
