实验四、栈的顺序和链式存储的表示和实现

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

线性结构-栈的顺序存储和链式存储实现栈的顺序存储表⽰栈的顺序存储结构简称为顺序栈，和线性表相类似，⽤⼀维数组来存储栈。

根据数组是否可以根据需要增⼤，⼜可分为静态顺序栈和动态顺序栈。

静态顺序栈实现简单，但不能根据需要增⼤栈的存储空间；动态顺序栈可以根据需要增⼤栈的存储空间，但实现稍为复杂。

栈的动态顺序存储表⽰采⽤动态⼀维数组来存储栈。

所谓动态，指的是栈的⼤⼩可以根据需要增加。

⽤bottom表⽰栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作⽽变化。

⽤top(称为栈顶指针)指⽰当前栈顶位置。

⽤top=bottom作为栈空的标记，每次top指向栈顶数组中的下⼀个存储位置。

结点进栈：⾸先将数据元素保存到栈顶(top所指的当前位置)，然后执⾏top加1，使top指向栈顶的下⼀个存储位置;结点出栈：⾸先执⾏top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。

栈的静态顺序存储表⽰采⽤静态⼀维数组来存储栈。

栈底固定不变的；栈顶则随着进栈和退栈操作⽽变化，⽤⼀个整型变量top(称为栈顶指针)来指⽰当前栈顶位置。

⽤top=0表⽰栈空的初始状态，每次top指向栈顶在数组中的存储位置。

结点进栈：⾸先执⾏top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。

结点出栈：⾸先把top指向的栈顶元素取出，然后执⾏top减1，使top指向新的栈顶位置。

若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。

/*!* \file 栈的顺序存储实现.cpp** \author ranjiewen* \date 2017/03/17 11:13***/#include <stdio.h>#include <stdlib.h>typedef int Position;typedef int ElemType;#define ERROR NULL#define MAXSIVE 100struct SNode{ElemType *Data; /*存储元素的数组，动态分配内存*/Position Top; /*栈顶元素数组下标*/int MaxSize; // 堆栈最⼤容量};typedef struct SNode* Stack;Stack CreateStack(int MaxSize){Stack S = (Stack)malloc(sizeof(struct SNode));S->Data = (ElemType*)malloc(MaxSize*sizeof(ElemType));S->Top = -1; //顺序存储结构时，表⽰空S->MaxSize = MaxSize;return S;}bool IsFull(Stack S){return (S->Top == S->MaxSize - 1);}bool Push(Stack S, ElemType x){if (IsFull(S)){printf("堆栈满.\n"); //栈满时可以再申请空间return false;}else{S->Data[++(S->Top)] = x;return true;}}bool IsEmpty(Stack S){return (S->Top == -1);}ElemType Pop(Stack S){if (IsEmpty(S)){printf("堆栈为空。

数据结构实验报告班级：计学号：姓名：设计日期：西安计算机学院实验题目1)栈的顺序存储结构2)栈的链式存储结构3)队列的链式存储结构4)队列的循环存储结构2.需求分析本演示程序用C语言编写，完成栈和列的初始化，入栈、出栈、输出操作。

1）对于顺序栈，入栈时要先判断栈是否满了，栈满不能入栈，否则出现空间溢出；在进栈出栈和读取栈顶时先判栈是否为空，为空时不能操作。

2）在一个链队表中需设定两个指针分别指向队列的头和尾。

3）队列的存储结构：注意要判断队满和队空。

4）程序所能达到的功能：完成栈的初始化，入栈，出栈和输出操作；完成队列的初始化，入队列，出队列和输出操作。

3.概要设计本程序包含1、栈的顺序存储结构包含的函数：1）主函数main（）2）入栈函数Push（）3）出栈函数Pop（）2、栈的链式存储结构包含的函数：1）主函数main（）2）入栈函数PushStack（）3）退栈函数PopStack（）4）取栈顶元素函数Getstack top（）3、队列的链式存储结构所包含的函数：1）主函数main（）2）入队函数EnQueue（）3）出队函数DeQueue（）4 队列的循环所包含的函数：1）主函数main（）2）初始化循环函数CircSeqQueue（）3）入队函数EnQueue（）4）出队函数DeQueue（）5）取队首元素函数GetFront（）4.详细设计1）栈的顺序存储结构#include<stdio.h>#include<stdlib.h>#include<conio.h>#define MAXSIZE 20typedef int datatype;typedef struct{ datatype elem[MAXSIZE];int top;}SeqStack;int init(SeqStack *s){ s->top=-1; return 1;}void print(SeqStack *s){char ch; int i;if(s->top==-1)printf("\n 栈已空.");else{i=s->top;while(i!=-1){printf("\n data=%d",s->elem[i]); i--;}}printf("\n 按回车继续");ch=getch();}void push(SeqStack *s,datatype x){if(s->top==MAXSIZE-1) printf("\n 栈已满！");else s->elem[++s->top]=x;}datatype pop(SeqStack*s){datatype x;if(s->top==-1){printf("\n 栈已空! "); x=-1;}else{x=s->elem[s->top--];}return(x);}void main(){SeqStack s; int k; datatype x;if(init(&s)){do {printf("\n\n\n");printf("\n***************************************");printf("\n\n 1. x进栈");printf("\n\n 2.出栈返回其值");printf("\n\n 3 结束");printf("\n***************************************");printf("\n 请选择(123)");scanf("%d",&k);switch(k){case 1:{printf("\n 请输入进栈整数X=?");scanf("%d",&x);push(&s,x);print(&s);}break;case 2:{ x=pop(&s);printf("\n 出栈元素:%d",x);print(&s);}break;case 3:exit(0);}printf("n---------");}while(k>=1 &&k<3);printf("\n 按回车返回");getch();}elseprintf("\n 初始化失败！\n");}2).栈的链式存储结构#include<stdio.h>#include<stdlib.h>typedef struct SNode{int data;struct SNode*next;}SNode,*LinkStack;LinkStack top;LinkStack PushStack(LinkStack top,int x)//入栈{LinkStack s;s=(LinkStack)malloc(sizeof(SNode));s->data=x;s->next=top;top=s;return top;}LinkStack PopStack(LinkStack top) //退栈{LinkStack p;if(top!=NULL){p=top;top=top->next;free(p);printf("退栈已完成\n");return top;}elseprintf("栈是空的，无法退栈！\n");return 0;}int GetStackTop(LinkStack top) //取栈顶元素{return top->data;}bool IsEmpty(){return top==NULL?true:false;}void Print(){SNode*p;p=top;if(IsEmpty()){printf("The stack is empty!\n");return;}while(p){printf("%d ",p->data);p=p->next;}printf("\n");}void main(){int x,a,b;char m;do{printf("\n");printf(" 链栈的基本操作\n");printf(" \n");printf(" 1.置空栈\n");printf(" 2.进栈\n");printf(" 3.退栈\n");printf(" 4.取栈顶元素\n");printf(" 5.退出程序\n");printf("\n 请选择一个数字（1 2 3 4 5）：");scanf("%c",&m);switch(m){case '1':{top=NULL;printf("\n栈已置空!");break;}case '2':{printf("请输入要进栈的元素个数是：");scanf("%d",&a);printf("\n请输入要进栈的%d个元素:",a);for(b=0;b<a;b++){scanf("%d",&x);top=PushStack(top,x);}printf("进栈已完成！\n");printf("\n输出栈为:");Print();}break;case '3':{printf("\n操作之前的输出栈为:");Print();top=PopStack(top);printf("\n操作过后的输出栈为:");Print();}break;case '4':{printf("\n输出栈为:");Print();if(top!=NULL)printf("\n栈顶元素是：%d\n",GetStackTop(top));elseprintf("\n栈是空的，没有元素！");}break;case '5':break;default:printf("\n输入的字符不对，请重新输入!");break;}getchar();}while(m!='5'); }运算结果:3）队列的链式存储结构#include<stdio.h>#include<stdlib.h>#include<conio.h>#include<stdio.h>#include<stdlib.h>#include<math.h>typedef int dataType;typedef struct node{ dataType data;struct node *next;}QNode;typedef struct{QNode *front,*rear;}LQueue;/*初始化*/int init(LQueue *q){if((q->front=(QNode *)malloc(sizeof(QNode)))==NULL) return 0;q->rear=q->front;q->front->next=NULL;return 1;}/*出队*/void print(LQueue Q){ QNode *p; char ch;p=Q.front->next;while(p!=NULL){printf("\n%d",p->data); p=p->next; } printf("\n 按回车键继续。

实验二：栈的表示与实现及栈的应用【实验目的】（1） 掌握栈的顺序存储结构及其基本操作的实现。

（2） 掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。

（3） 掌握用递归算法来解决一些问题。

【实验内容】1. 编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。

2. 编写递归程序，实现N ！的求解。

3. 编写递归程序，实现以下函数的求解。

4. 编写程序，实现Hanoi 塔问题。

【实验步骤】1.打开VC++。

2.建立工程：点File->New ，选Project 标签，在列表中选Win32 Console Application ，再在右边的框里为工程起好名字，选好路径，点OK->finish 。

至此工程建立完毕。

3.创建源文件或头文件：点File->New ，选File 标签，在列表里选C++ Source File 。

给文件起好名字，选好路径，点OK 。

至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码5．编译－＞链接－＞调试1、#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1⎩⎨⎧>-+-==1),2()1(0,1,)(n n Fib n Fib n n n Fib#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int SElemType;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct{SElemType *base;SElemType *top;int stacksize;}SqStack;Status InitStack(SqStack &S){S.base=(SElemType *)malloc (STACK_INIT_SIZE*sizeof(SElemType));if (!S.base) return OVERFLOW;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}//InitStackStatus Push(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;} //PUSHStatus Pop(SqStack &S, SElemType &e) {if(S.top==S.base)return ERROR;e=*--S.top;return OK;} //PopStatus StackEmpty(SqStack S){if (S.top==S.base)return OK;elsereturn ERROR;} //StackEmptyvoid conversion(){int N;int e;SqStack S;InitStack(S);printf("输入要转换的数据：");scanf("%d",&N);while (N){Push(S, N % 8);N = N/8;}printf("\n其对应的八进制数是：");while (!StackEmpty(S)){Pop(S,e);printf ( "%d", e );}}void main(){conversion();}2、#include <stdio.h>Int fact(int n){If(n==1)return 1;elsereturn n*fact(n-1);}void main(){Int n;printf(“输入一个数n:”);scanf(“%d”,&n);printf("fact(%d)=%d\n",n,fact(n)); }3、#include <stdio.h>int fib(int n){if(n>1)return fib(n-1)+fib(n-2);elsereturn n;}void main(){int n;printf("\n输入一个数n:");scanf("%d",&n);printf("fib(%d)=%d\n",n,fib(n));}4、#include <stdio.h>void move(char x,int n,char z){printf("将%d号盘从%c柱移到%c柱\n",n,x,z);}void hanoi (int n, char x, char y, char z) { if (n==1)move(x,1,z);else{hanoi(n-1, x, z, y);move(x, n, z);hanoi(n-1, y, x, z);}}void main(){int n;scanf("%d",&n);hanoi(n,'x','y','z');}【实验心得】这节课的实验内容是栈的表示与实现及栈的应用。

一、实验目的1. 理解栈的定义、特点、逻辑结构及其在计算机科学中的应用。

2. 掌握顺序栈和链栈的存储结构及基本操作实现。

3. 通过具体应用实例，加深对栈的理解，提高问题分析和解决的能力。

二、实验内容1. 实现顺序栈和链栈的基本操作。

2. 编写一个算法，判断给定的字符序列是否为回文。

3. 编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。

4. 给定一个整数序列，实现一个求解其中最大值的递归算法。

三、实验步骤1. 实现顺序栈和链栈的基本操作（1）顺序栈的存储结构及操作实现顺序栈使用数组来实现，其基本操作包括：- 初始化栈：使用数组创建一个空栈，并设置栈的最大容量。

- 入栈：将元素插入栈顶，如果栈满，则返回错误。

- 出栈：从栈顶删除元素，如果栈空，则返回错误。

- 获取栈顶元素：返回栈顶元素，但不删除。

- 判断栈空：判断栈是否为空。

（2）链栈的存储结构及操作实现链栈使用链表来实现，其基本操作包括：- 初始化栈：创建一个空链表，作为栈的存储结构。

- 入栈：在链表头部插入元素，如果链表为空，则创建第一个节点。

- 出栈：删除链表头部节点，如果链表为空，则返回错误。

- 获取栈顶元素：返回链表头部节点的数据。

- 判断栈空：判断链表是否为空。

2. 判断字符序列是否为回文编写一个算法，判断给定的字符序列是否为回文。

算法步骤如下：（1）使用顺序栈或链栈存储字符序列。

（2）从字符序列的头部开始，依次将字符入栈。

（3）从字符序列的尾部开始，依次将字符出栈，并与栈顶元素比较。

（4）如果所有字符均与栈顶元素相等，则字符序列为回文。

3. 利用栈的基本运算将指定栈中的内容进行逆转编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。

算法步骤如下：（1）创建一个空栈，用于存储逆转后的栈内容。

（2）从原栈中依次将元素出栈，并依次入新栈。

（3）将新栈的内容赋值回原栈，实现栈内容的逆转。

4. 求解整数序列中的最大值给定一个整数序列，实现一个求解其中最大值的递归算法。

一、实验目的1. 理解栈的基本概念和特性；2. 掌握栈的顺序存储和链式存储结构；3. 熟练掌握栈的基本操作，如入栈、出栈、初始化等；4. 通过实际操作，加深对栈在实际问题中的应用理解。

二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容1. 栈的顺序存储结构实现2. 栈的链式存储结构实现3. 栈的基本操作实现4. 栈的实际应用案例分析四、实验步骤1. 栈的顺序存储结构实现（1）定义栈的顺序存储结构体（2）实现栈的初始化、入栈、出栈等基本操作2. 栈的链式存储结构实现（1）定义栈的链式存储结构体（2）实现栈的初始化、入栈、出栈等基本操作3. 栈的基本操作实现（1）编写函数实现栈的初始化（2）编写函数实现栈的入栈操作（3）编写函数实现栈的出栈操作（4）编写函数实现获取栈顶元素4. 栈的实际应用案例分析（1）模拟火车进站和出站过程（2）计算表达式求值（3）实现函数调用栈五、实验结果与分析1. 栈的顺序存储结构实现（1）成功实现了栈的顺序存储结构体（2）成功实现了栈的初始化、入栈、出栈等基本操作2. 栈的链式存储结构实现（1）成功实现了栈的链式存储结构体（2）成功实现了栈的初始化、入栈、出栈等基本操作3. 栈的基本操作实现（1）成功实现了栈的初始化函数（2）成功实现了栈的入栈函数（3）成功实现了栈的出栈函数（4）成功实现了获取栈顶元素函数4. 栈的实际应用案例分析（1）成功模拟了火车进站和出站过程（2）成功实现了表达式求值（3）成功实现了函数调用栈六、实验心得通过本次实验，我对栈的存储结构、基本操作以及实际应用有了更深入的理解。

以下是我对本次实验的几点心得体会：1. 栈是一种后进先出（LIFO）的数据结构，在解决实际问题中具有重要的应用价值；2. 栈的顺序存储和链式存储结构各有优缺点，选择合适的存储结构可以更好地满足实际需求；3. 栈的基本操作相对简单，但需要注意栈满和栈空的情况；4. 栈在实际应用中具有广泛的应用场景，如函数调用栈、表达式求值等。

一、实验目的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、通过具体的应用实例，进一步熟悉和掌握栈在实际问题中的运用。

二.实验内容1、设栈采用顺序存储结构（用动态数组），请编写栈的各种基本操作的实现函数，并存放在头文件stack.h中。

同时建立一个验证操作实现的主函数文件stack.cpp，编译并调试程序，直到正确运行。

提示：⑴栈的动态数组顺序存储结构可定义如下：int IsReverse(char struct Stack {ElemType *stack ; // 存栈元素int top; // 栈顶指示器int MaxSize; // 栈的最大长度};⑵栈的基本操作可包括：①void InitStack (Stack &S); //构造一个空栈S②int EmptyStack (Stack S); //若栈S为空栈返回1，否则返回0③void Push(Stack &S, ElemType item); //元素item进栈④ElemType Pop(Stack &S); //栈S的栈顶元素出栈并返回⑤ElemType Peek(Stack S); //取栈S的当前栈顶元素并返回⑥void ClearStack (Stack &S); //清除栈s，使成为空栈2、应用：写一函数，判断给定的字符串是否中心对称。

如字符串“abcba”、“abccba”均为中心对称，字符串“abcdba”不中心对称。

要求利用test7.h中已实现的有关栈的基本操作函数来实现。

请把该函数添加到文件test7.cpp中的主函数前，并在主函数中添加相应语句进行测试。

函数原型如下：*s) //判断字符串S是否中心对称，是返回1，否则返回03、填写实验报告，实验报告文件取名为report7.doc。

4、上传实验报告文件report7.doc 、源程序文件test7.cpp及test7.h到Ftp服务器上（ftp://10.61.14.240:5000 ）自己的文件夹下。

栈的表示及栈的应用实验心得
栈是一种常见的数据结构，特点是后进先出，常用于程序内存中的函数调用、表达式
求值等方面。

栈有多种表示方法，常见的包括顺序栈和链式栈。

在顺序栈中，使用一
个数组来表示栈，通过一个指针指向栈顶元素，实现栈的基本操作。

链式栈是在链表
的基础上实现栈，其中栈顶元素表示为链表的头结点。

在实验中，我通过编写程序来熟悉了使用栈。

具体来说，我设计了一个括号匹配程序。

该程序可以读取一个字符串，检查其中的括号是否匹配，如果匹配则输出“括号匹配”，否则输出“括号不匹配”。

在程序中，我使用顺序栈来实现检查括号匹配的功能。

具体来说，我遍历每一个字符，遇到左括号时则将其压入栈中，遇到右括号时则
判断栈顶元素是否为相应的左括号，如果匹配则弹出栈顶元素，继续遍历字符串，直
至遍历完成。

如果遍历完成后栈为空，则表示字符串中的括号匹配，否则表示不匹配。

通过这个实验，我对栈的表示和使用有了更深入的了解。

共享一下这个实验心得，希
望对其他学习数据结构的同学有所帮助。