当前位置：文档之家 › 实验二 栈及应用

实验二 栈及应用

  • 格式：doc
  • 大小：1.25 MB
  • 文档页数：46

实验二 栈及应用 一、实验目的 1.掌握顺序栈和链格的定义和操作的实现 2.掌握栈在程序中的使用方法 3.掌握栈的几个基本应用: 进制转换,括号匹配,算术表达式求值 4.基本掌握N后问题、汉诺塔问题的求解 5.深入掌握迷宫问题 6.理解回溯算法、递归程序设计的思想等

二、实验硬软件环境 硬件环境：赛扬433以上CPU，10GB以上硬盘，64MB以上内存 软件环境：DOS+Turbo C 2.0 或 Borland C++ 3.1以上 Windowx 9X+VC++ 5.0以上

三、实验要求 1．认真阅读和掌握本实验内容所给的全部程序。 2．保存和打印出程序运行结果，并结合程序进行分析。 3．

按照你对本实验操作的需要，屏幕考贝运行结果到实验报告中。

4．本实验要由实验小组成员共同完成，由于实验工作量较大，请同学们在实验过程中，注意任务分解与分工，注意相互沟通与交流。 5．撰写实验报告、并准时上交

四、注意事项 在做第一次“数据结构”课程实验之前，要在硬盘上建立好自己的工作目录，专门用来存储你所做的实验程序及相关信息，以后每次做实验都采用这个目录。工作目录建议如下建立，最后注明实验作者（张三）： D:\数据结构实验（张三） | +-----实验一 | +-----实验二 |….. +-----实验九 实验一至九的有关材料请同学在网上下载（下载网址：http://eol.gzu.edu.cn），本实验设计完全由老师设计，版权限本班同学使用，勿外传。 实验材料下载到本机后，请用winrar软件释放到你的电脑磁盘的“数据结构实验（张三）”文件夹中，形成如上图的文件夹结构。 上交实验报告时，请把“实验二”的所有内容（含实验报告）用winrar打包成.rar文件后一并交上来。上传名字为“实验二（张三）.rar”

五、基本理论及应用 栈（Stack）：实质上是一种受限制的线性表——限定了元素的插入和删除只能在表的一端进行，这一端称为“栈顶”，另一端称为“栈底”。栈的插入操作又称为入栈操作（Push）,删除操作又称为出栈(Pop)，当栈中没有元素称为“空栈”，此时不能进行Pop操作，当栈满时，想再插入元素会发出“溢出”问题。 由于栈的操作固定于表的某一端，因此，先进栈（Push）的元素总是后出栈，根据这一特点，又把栈称为“LIFO”（后进先出）表。 栈是一种简单的数据结构，但在程序设计中却有着很广泛的应用，很多程序都需要用栈来作存储结构，如：括号匹配、表达式求值、进制转换、N后问题、迷宫老鼠、树或图的遍历、拓扑排序、关键路径等。在操作系统中栈还可以用来保存中断现场，保存自动变量、形式参数、函数返回结果等。 栈的基本操作包括： • 创建一个栈（初始化）。 • 确定栈是否为空。 • 确定栈是否为满。 • 取得栈顶元素。 • 出栈（删除）元素运算。 • 入栈（插入）元素运算。

线性表ADT（图1）：

图1 栈抽象数据类型ADT 顺序栈： 正如顺序表一样，可以采用数组来表示栈，一个数组元素可以保存一个栈元素。可以使用数组任一端作为“栈顶”，由于栈是在栈顶进行操作，所以要保存栈顶的位置，可以设置一个栈顶指针Top来指向栈顶。 Top的初值很重要。第一种情形：当栈空时，可以设置栈顶指针Top不指向任何元素，即Top=-1，这样，当Top > -1时，Top指向的位置即栈顶的元素。 第二一种形是：让Top指针总是指向栈顶元素上面第一个未用的数组元素位置，如栈顶元素位于i, 则栈的指针Top为i+1。栈空时对应Top=0。 Top的初值影响了栈的基本操作，前者出栈时要取得栈顶元素值，再让栈顶指针Top的值减1；入栈时要先让栈顶指针加1，再把元素存入新栈顶位置。 后者出栈时，先要把栈顶指针Top减1，然后再取得当前指针所在元素，进栈时则是先把进栈元素放入到指针Top指向的数组位置，Top指针再加1。 顺序栈的类型定义如下： #define int DataType typedef struct { DataType data[StackSize]; int Top; }SqStack; StackSize是栈允许存储的元素个数的上限。

链栈： 即用单链表来表示栈。考虑到单链表创建时有两种方法，即首插入法和尾插入法两种。前者每次插入元素，总是在链表的首结点插入，后者则在链表的表尾插入。“前插入”的方法其是就对应了栈的进栈操作。 如果我们限定单链表的元素的插入与删除都在“头指针”的位置进行，就可以用单链表表示栈。 为了实现这种存储结构，可以使用C语言作如下定义：

typedef int DataType; typedef struct Lnode { DataType data; struct Lnode *next; /*递归定义，保存下一个元素的首地址*/ }*LkStack,LNode;

可以看到以上定义与单链表的结点定义是完全相同的。第一行把int定义成了一种新的类型DataType，这并非多此一举。未来如果栈的元素类型发生变化，我们只需要把int改为对应的类型即可。

栈的应用： 栈在程序设计中有着非常重要的应用，比如：表达式括号匹配，进制转换，表达式求值，以及著名的“迷宫老鼠”、N后问题和汉内塔问题等。 表达式括号匹配的基本思想是，左括号“（”总是与之最近的右括号“）”相匹配，并且在可匹配的一对括号里面的所有括号总是相匹配的。如果把表达式放在一个字符串中，我们可以依次取出每个字符ch。如果ch是左括号“（”，在让它入栈；如果是右括号” ）”，则检查栈顶括号，看是否与ch匹配，匹配，则出栈一个括号，得到一个匹配。重复上述两个操作，直至栈为空，且表达式处理完， 则表达式中括号肯定是匹配的。 进制转换（整数）把要转换的数除X除以N（待转换的进制），余数入栈，商去替代X的值，重复操作，直至X为0为止。此时对应的N进制数的所有位保存在栈中，栈顶元素是对应的N进制的最高位，栈底元素是最低位。只要把栈中元素依次出栈就可以得到转换结果。注意的是，当N进制的位操过10时，为了避免歧义，超过10的数分别用“A”、“B”，….等字母表示。 表达式求值要按运算符的优先级进行，优先级高的先计算，优先级低的后计算，括号可以改变运算的优先级。 （1）中缀表达式求值一般要设置两个栈，一个运行数栈（S1），另一个为运算符栈（S2）。 对于任一个表达式，从左至右扫描表达式的成份，如果是运算数，则直接进S1栈。如果是运算符，要根据此运算符(op)与S2栈的栈顶运算符（op1）的优先级进行比较，根据比较结果作不同的处理： (a) 如果op>op1,则让op直接入栈； (b) 如果op两个运算数x1和x2，计算 x2 op1 x1的结果x'，把x1'进到栈S1中；重复与栈顶运算符进行比较。 (c) 如果op==op1,则直接把op1从S2栈顶出栈即可。继续取一个运算成份。 直到表达式中的所有成份处理完即可，为了方便处理，通常要在表达式的两端分别添加一个运算符“#”或“@”。

（2）也可以先把中缀表达式变成后缀表达式后再求值，中缀表达式变成后缀表达式只需要设置一个运算符栈S就可以了。对表达式的每一成份依次扫描，如果是运算数直接“输出”，如果是运算符op，则检查栈S中的栈顶元素op1，比较op与op1的优先级以选反相应的操作： (a) 如果op>op1,则让op进栈 (b) 如果相等，则让op1出栈即可 (c) 如果op直到最后一个运算符处理完即可。后缀表达式有这样的特点：（a）运算数的顺序与中缀表达式的顺序是一样的；（b）运算符是已经按照优先级排列好的，即计算顺序已经按要求排列好了。

（3）如果要对后缀表达式求值，则需要设置一个运算数栈S。从左至右扫描表达式，碰到运算数，直接入栈，碰到运算符op, 则从S中出栈两个元元素x1和x2，计算表达式 x2 op x1的值x'，并让x'入栈，重复以上操作即可。

迷宫老鼠"rat in maze"是一个简单小游戏，即给定一个“地图”，地图有m*n个小方格构成的，每格的坐标用(x,y)表示，左上角坐标为(0,0)，右下角坐标为(m-1,n-1)。 在“地图”中的一些小方格中可能存在墙或“障碍”，这是小老鼠无法“穿越”的。给定一个小老鼠的初始位置begin（x0,y0），有求找到小老鼠从begin和最终位置end(x1,y1)的一条“路径”，这条路径path={begin,p1,p2,…end}，是相邻位置的有序集合。 解决这个问题的方法是，用一个m*n的二维数组表示地图，有墙的格子用 “1”表示，没有墙的格式用”0”表示。 为了让老鼠走路，我们可以假设老鼠只能按照“东、南、西、北”四个方向行走，老鼠总是先判断东方是否有路，如果有，则向东走，如果东方没有路，才判断南方，南方有路，则走南方，….。由于前面走过的“格子”不能重复走，因此，对于走过的格子，我们可以放一个“脚印”在上面，即把相应的格子设置为“2”就行了，这样的格子表明已走过，不能再走。 当老鼠处于一个位置p(x1,y1)时，与其东边相邻的格子坐标为：东（x1,y1+1）, 南边的为（x1+1,y1）,西边的为（x1,y1-1）,北边的为(x1-1,y1)。或者说位置p的相邻“格子”与p的“偏移值”分为：东（0,1）、南(1,0)、西(0,-1)和北（-1，0），可以把四个偏移值保存在一个数组offset[1..4]中。格子p的想邻位置可以通过p与偏移值相计算得到。 为了保存路径path，我们可以设置一个栈S来保存老鼠走过的所有“格子”，最近走过的格子总是放在“栈顶”，当“栈顶”格子p相邻的格子（东、南、西、北）在二维数组中的的值都不为0时，表示再往下走已无路可走。此时，我们可以从S中出栈一个位置，并设该位置（格子）对应的值为“3”，表明，该格子已无路可走。然后以新的“栈”顶元素为当前位置（回溯），依次从“东、南、西、北”四个方向寻找可以走的位置，找到该位置后，把该位置“入栈”，表明走入该位置。继续寻找下一个位置，直到该位置为end位置或找不到合适的路径——即栈为空时算法结束。

N后问题也是比较著名的程序设计问题。这个问题是这样描述的：有一个N*N的棋盘，要求在格子中放入N个王后，并且使每个王后不能相互“攻击”，攻击的意思是一个王后可以吃另一个王后或者说两个王后不能在横向、纵向或斜向几个方向上构成一条直线。 这个问题的解可以写成这样一个向量：S=（x1,x2,……xn），x1表示在第1列王后放的位置，xi表示第i列元素放在位置，因此，向量S表示了N个王后放的位置{(1,x1),(2,x2),…..,(n,xn)},由于S中的每个元素可以有N种放法，所以S的解空间有N*N*….*N=NN种组合（组合爆炸），但是只有有限种组合是满足“约束”条件的“可行解”。 求解的时候也可以用栈来表示解向量S。刚开始时在第1列第1个位置放入王后，即S=(1)；接着在第2列中“适合”的地方放入第2个王后，毫无疑问，第2列的值只能是3至N的任一值（1，2与前面产生攻击），如果我们选3，则S=（1,3）,第3列应该放多少，即向量S=（1,3,X）中X的值是多少呢？X不可能是1,3，因为这样与前面放的王后有“攻击”，能不能是1-4的位置呢？不行，因为1与第1列的后有攻击，2-4分别与第2列的后有攻击，所以X只能为5，即：S=(1,3,5)。 ① ……

合集下载

栈的表示及栈的应用

栈的表示及栈的应用

while(N)
{
Push(S,N % M);
N=N/M;
}
printf("其对应的%d进制数是",M);
while(!StackEmpty(S)){
Pop(S,e);
printf("%d",e);
}
printf("\n");
}
递归程序
#include<stdio.h>
long Fibonacci(int n);
3.编写程序，实现Hanoi塔问题（课本P55-P58）。
【实验步骤】
1.打开VC++。
2.建立工程：点File->New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK->finish。至此工程建立完毕。
3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。
if (!S.base) exit(OVERFLOW);//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
} //PUSH
Status Pop(SqStack &S, SElemType &e)
S.base=(SElemType *)malloc (STACK_INIT_SIZE*sizeof(SElemType));
实验二、堆栈

实验二、堆栈

实验二堆栈的应用一、实验目的（1）了解栈的定义。

（2）理解栈的顺序存储结构。

（3）实现进栈和出栈程序。

二、实验内容栈是只能在表的一端—表尾进行插入和删除运算的线性表，表尾也称作栈顶（Top），表头也称为栈底(Bottom)。

当表中没有元素时称为空栈。

（1）栈的顺序存储结构栈的顺序存储可用一维数组，用一个指针指示栈顶的位置。

设栈的最大容量为maxsize，则用C语言来描述顺序存储结构的栈：#define maxsize 10int data[maxsize+1];int *top,k,d,num,x;其中，maxsize是栈可能达到的最大容量；data[0]为栈顶指针，栈空时data[0]为0；data[1]表示第一个进栈的元素；data[i]表第i个进栈的元素；data[data[0]]表栈顶元素。

当data[0]=maxsize时，表示栈满，如果再有元素进入时，则栈要溢出，称“上溢”；当data[0]=0时再作退栈运算，就要发生“下溢”。

（2）栈的基本运算1）把一个给定的元素x压入栈内。

该过程称为进栈，它是在栈顶位置加一个新数据项，程序如下：void push_stack(x,s)int x;int s[maxsize+1];{printf("压栈前：top=%d x=%d\n",s[0],x);if(s[0]==maxsize) printf("OVERFLOW\n");else{s[0]=s[0]+1;s[s[0]]=x;printf("压栈后：");printf("top=%ds[top]=%d\n",s[0],s[s[0]]);printf("\n");}}2）弹出栈顶元素。

该过程称为出栈（Pop），它是从栈顶取出一个数据项紧接着这个数据项下面的数据项变为栈顶，程序如下：void pop_stack(s)int s[maxsize+1];{if(s[0]==0)printf("栈空！\n");else{s[0]=s[0]-1;printf("出栈的元素是：%d;当前栈顶是：%d",s[s[0]+1],s[0]);}}3）读栈顶元素。

栈和队列的应用数据结构实验

栈和队列的应用数据结构实验

实验二（1）1实验题目: 栈和队列的应用2实验内容: 迷宫问题3实验目的: 掌握栈和队列的概念及工作原理，运用其原理完成 实验题目中的内容。

4实验要求: 为了使学生更好的掌握与理解课堂上老师所讲的概 念与原理，实验前每个学生要认真预习所做的实验 内容及编写源程序代码（写在纸上与盘中均可），以 便在实验课中完成老师所布置的实验内容5设计原理:6程序清单及注释说明:#include<stdio.h>#include<stdlib.h>#define M 15#define N 15定义迷宫内点的坐标类型struct mark //{int x;int y;};恋"栈元素，嘿嘿。

struct Element //"{行,y列int x,y; //x下一步的方向int d; //d};链栈typedef struct LStack //{Element elem;struct LStack *next;}*PLStack;/*************栈函数****************/构造空栈int InitStack(PLStack &S)//{S=NULL;return 1;}int StackEmpty(PLStack S)//判断栈是否为空{if(S==NULL)return 1;elsereturn 0;}int Push(PLStack &S, Element e)//压入新数据元素 {PLStack p;p=(PLStack)malloc(sizeof(LStack));p->elem=e;p->next=S;S=p;return 1;}int Pop(PLStack &S,Element &e) //栈顶元素出栈 {PLStack p;if(!StackEmpty(S)){e=S->elem;p=S;S=S->next;free(p);return 1;}elsereturn 0;}/***************求迷宫路径函数***********************/void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2]) {int i,j,d;int a,b;Element elem,e;PLStack S1, S2;InitStack(S1);InitStack(S2);入口点作上标记maze[start.x][start.y]=2; //elem.x=start.x;elem.y=start.y;elem.d=-1; //开始为-1Push(S1,elem);栈不为空 有路径可走while(!StackEmpty(S1)) //{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1; //下一个方向试探东南西北各个方向while(d<4) //{a=i+diradd[d][0];b=j+diradd[d][1];如果到了出口if(a==end.x && b==end.y && maze[a][b]==0) //{elem.x=i;elem.y=j;elem.d=d;Push(S1,elem);elem.x=a;elem.y=b;elem.d=886; //方向输出为-1 判断是否到了出口Push(S1,elem);东 1=南 2=西 3=北 886为则走出迷宫\n\n通路为:(行坐标,列坐标,方向)\n"); printf("\n0=逆置序列 并输出迷宫路径序列while(S1) //{Pop(S1,e);Push(S2,e);}while(S2){Pop(S2,e);printf("-->(%d,%d,%d)",e.x,e.y,e.d);}跳出两层循环，本来用break,但发现出错，exit又会结束程序，选用return还是不return; //错滴o(∩_∩)o...}if(maze[a][b]==0) //找到可以前进的非出口的点{标记走过此点maze[a][b]=2; //elem.x=i;elem.y=j;elem.d=d;Push(S1,elem); //当前位置入栈下一点转化为当前点i=a; //j=b;d=-1;}d++;}}没有找到可以走出此迷宫的路径\n");printf("}建立迷宫*******************//*************void initmaze(int maze[M][N]){int i,j;迷宫行,列int m,n; //请输入迷宫的行数 m=");printf("scanf("%d",&m);请输入迷宫的列数 n=");printf("scanf("%d",&n);请输入迷宫的各行各列:\n用空格隔开,0代表路,1代表墙\n",m,n);printf("\nfor(i=1;i<=m;i++)for(j=1;j<=n;j++)scanf("%d",&maze[i][j]);printf("\n");你建立的迷宫为o(∩_∩)o...加一圈围墙for(i=0;i<=m+1;i++) //{maze[i][0]=1;maze[i][n+1]=1;}for(j=0;j<=n+1;j++){maze[0][j]=1;maze[m+1][j]=1;}输出迷宫for(i=0;i<=m+1;i++) //{for(j=0;j<=n+1;j++)printf("%d ",maze[i][j]);printf("\n");}}void main(){int sto[M][N];入口和出口的坐标struct mark start,end; //start,end行增量和列增量 方向依次为东西南北 int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//建立迷宫initmaze(sto);//输入入口的横坐标,纵坐标[逗号隔开]\n");printf("scanf("%d,%d",&start.x,&start.y);输入出口的横坐标,纵坐标[逗号隔开]\n");printf("scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add); //find pathsystem("PAUSE");}7.运行与测试及结果。

栈的实现及应用实验原理

栈的实现及应用实验原理

栈的实现及应用实验原理一、栈的实现栈是一种先进后出（FILO）的数据结构，它可以被用来实现许多算法和数据结构。

栈可以使用数组或链表来实现。

在这里，我将介绍一下基于数组的栈的实现原理。

1.1 基于数组的栈基于数组的栈实现非常简单，可以使用一个固定大小的数组来存储栈中的元素。

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

在基于数组的栈中，当一个元素压入栈时，它被放入数组的末尾（栈顶），而当一个元素弹出栈时，数组的末尾元素被移除，并返回给调用者。

1.2 实现细节在基于数组的栈中，我们需要跟踪栈顶元素的位置，通常通过一个指示栈顶索引的变量来实现。

当一个元素被压入栈时，我们将它放入数组的栈顶位置，并将栈顶索引加一；当一个元素被弹出栈时，我们将栈顶索引减一，并返回数组中当前栈顶索引位置的元素。

为了避免栈的溢出（stack overflow）或者栈的下溢（stack underflow），我们还需要处理一些边界情况。

例如，在压入元素前，我们需要检查是否数组已满；在弹出元素前，我们需要检查栈中是否有元素。

这些细节需要涵盖在栈的实现中，以保证栈的正确性和健壮性。

1.3 时间复杂度基于数组的栈的时间复杂度非常简单：压入和弹出元素的时间复杂度均为O(1)，因为它们只涉及数组末尾的操作。

对于数组的访问（取得栈顶元素）的时间复杂度也为O(1)。

二、栈的应用栈是一种非常重要的数据结构，它在编程中有着广泛的应用。

以下是栈的一些应用实例：2.1 逆波兰表达式逆波兰表达式是一种不包含括号的数学表达式，它使用操作符在操作数之间排列。

逆波兰表达式的计算可以通过栈来实现。

具体地，当遇到一个操作数时，将其压入栈中；当遇到一个操作符时，弹出栈顶的两个元素，并进行相应的计算，将结果压入栈中。

这样，最终栈中剩下的元素就是逆波兰表达式的计算结果。

2.2 括号匹配在编程中，括号匹配是一个非常常见的问题。

给定一个包含括号的字符串，我们需要判断其中的括号是否匹配。