下载文档原格式
第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、栈的存储结构：顺序存储和链式存储；3、双栈及操作；4、栈的几种运算（操作）实现；5、栈的简单应用举例；[重点难点]1、栈的特性和应用场合；2、栈的存储结构；3、栈的操作实现；[内容讲授]1．栈的概念和特性栈（stack）是一种特殊的线性表。
作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。
在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。
而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。
如果我们把冼净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么上例的特点是：后进栈的先出栈。
然而，摞起来的碗实际上是一个线性表，只不过“进栈”和“出栈”都在最顶上进行，或者说，元素的插入和删除操作都是在线性表的一端进行而已。
一般而言，栈是一个线性表，其所有的插入和删除操作均是限定在线性表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。
若给定一个栈S=（a1,a 2，a3，……，an），则称a1为栈底元素，an为栈顶元素，元素ai位于元素ai-1之上。
栈中元素按a 1, a2，a3，……，an的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an, an-1，……，a1。
也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。
因此栈又称为后进先出(LIFO—Last In First Out)表。
我们常用一个图来形象地表示栈，其形式如下图：⑴在使用栈之前，首先需要建立一个空栈，称建栈（栈的初始化）；⑵往栈顶加入一个新元素，称进栈（压栈、入栈）；⑶删除栈顶元素，称出栈（退栈、弹出）；⑷查看当前的栈顶元素，称读栈；{注意与⑶的区别}⑸在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。
2．栈的存储结构（1）顺序栈栈是一种线性表，在计算机中用一维数组作为栈的存储结构最为简单，操作也最为方便。
case 5:
{ setEmpty(q);
printf("\n顺序栈被置空!\n");
OutStack(q);
}break;
case 6:
exit(0);
}
}while(cord<=6);
}
运行结果1、初始化书序栈
2、
3、入栈及出栈
4、出栈及取栈顶元素
5、
6、初始化队列并输入顺序队列
7、插入新的队尾元素，即入队
8、删除队头数据元素，即出队
9、判断队列是否为空。
10、取队列头元素。
电子信息工程学院2012级《数据结构》实验报告
11、遍历顺序队列。
实验总结此次实验，初步学会了建立顺序栈与顺序队列，并学会了栈和队列的基本算法，再次巩固了指针的用法。
巩固了在课本上学的知识，加深了对栈和
队列的认识与掌握。
不过，在编程时，发觉自己在定义结构体和变量时，还
有很多不足。
而且，在编写程序时，自己有点粗心大意，经常忘记加“；”和
“{}”等。
路漫漫其修远兮，还得上下而求索啊！！。
陕西师范大学硕士研究生招生考试“856-数据结构与程序设计”考试大纲本《数据结构与程序设计》考试大纲适用于陕西师范大学计算机科学学院各类硕士研究生招生考试。
数据结构与程序设计是大学计算机学科本科学生的核心课程，而且也是其他理工专业的热门选修课。
它的主要内容包括线性、树型、图型这些基本数据结构及其相关算法，以及查找和排序的典型算法和算法的时间复杂度和空间复杂度分析。
要求考生掌握基本的数据结构和经典算法，具备对实际问题进行分析，抽象出表达实际问题的数学模型，设计出解决问题的算法，能灵活运用程序设计技术实现相应算法，具有分析问题、解决问题的能力。
一、考试的基本要求要求考生比较系统地掌握数据结构与程序设计的基本概念和理论，不仅能解答基础知识题，且能综合运用所学的基本数据结构和程序设计技术给出相应实际问题的解决方案，具备对实际问题进行分析，抽象出计算机加工的数据对象及其间的关系，能选择的合适的数据结构表达应用问题，并选择合适的存储结构实现相应的程序设计，解决实际应用问题。
要求考生具有计算机专业学生的基本素质，具有良好的程序设计风格，能综合运用所学的基本数据结构和程序设计知识分析问题、解决问题。
二、考试方法和考试时间数据结构与程序设计考试采用闭卷笔试形式，试卷满分150分，考试时间180分钟。
三、考试内容（一）数据结构概述1．数据结构的基本概念以及相关术语；2．数据结构的抽象数据类型表示与实现；3．算法的基本概念及设计要求；4．算法的时间复杂度和空间复杂度分析。
（二）线性表1．线性表的类型定义、基本算法，以及集合运算等应用问题的解决方案；2．线性表的顺序表示和实现，及集合运算等应用问题的解决方案的顺序表实现；3．线性表的链式表示和实现，及集合运算等应用问题的解决方案的单链表实现；4．一元多项式的表示及相加，即一元多项式的单链表加法算法实现。
（三）栈和队列1．栈的类型定义；2．栈的顺序存储表示和栈的基本操作在顺序栈的实现；3．栈的链式存储表示和实现；4．队列的类型定义；5．队列的链式存储表示和实现；6．队列的顺序存储表示和实现，特别是循环队列。
实验三栈的顺序和链式存储的表示和实现实验目的：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);}实验总结：。
