数据结构实验顺序栈的实现.pdf
实验四 顺序栈的操作 一.实验目的 掌握顺序栈的基本操作：初始化栈、判栈空、入栈、出栈、取栈顶数据元素等运算及程序实现方法。二.实验内容（1）定义栈的顺序存取结构。（2）分别定义顺序栈的基本操作（初始化栈、判栈空、入栈、出栈等）。（3）设计一个测试主函数进行测试。三.实验要求（1）根据实验内容编写程序，上机调试并获得运行结果（2）撰写实验报告 四.准备工作 本次实验将会建立下图所示顺序栈，并会根据此顺序栈进行新增，删除等操作 五.关键操作思路与算法 (1)定义顺序栈 利用顺序存储方式实现的栈称为顺序栈。栈中的数据元素可用一个预设的足够长度的一维数组来实现:datatype dataMAXNUM，栈底位置一般设置在数组的低端处，在整个进栈和出栈的过程中不改变，而栈顶位置将随着数据元素进栈和出栈而变化，为了指明当前栈顶在数组中的位置，一般用 top 作为栈顶指针，算法如下；1.#define MAXNUM 100 2.typedef int datatype;3.4.typedef struct 5.datatype dataMAXNUM;6.int top;7.SeqStack;(2)置空栈 算法思路；(1)向系统申请栈空间(2)初始化栈顶指针 top，置空栈标志 top=-1 算法如下；1.void StackSetNull(SeqStack*s)2.3.s-top=-1;4.（3）判断是否为空栈 算法如下；1./判断栈是否为空 2.int StackIsEmpty(SeqStack*s)3.4.if(s-top=-1)5.return TRUE;6.else 7.return FALSE;8.9.（4）入栈 算法思路；（1）判断当前栈空间是否已满，若已满，则返回0，未满则转第（2 步）（2）栈顶指针 top+（3）将元素赋值到 top 所指位置作为新的栈顶元素，成功返回值 1.算法如下；1./进栈 2.int StackPush(SeqStack*s,datatype x)3.4.if(s-top=MAXNUM-1)5.6.printf(栈上溢出!n);7.return FALSE;8.9.else 10.11.s-top=s-top+1;12.s-datas-top=x;13.return TRUE;14.15.（五）出栈 算法思路；（1）判断当前栈空间是否为空，若为空，则返回 0，不为空则转第（2 步）（2）将 top 指针所指位置元素值取出（3）栈顶指针 top-指向新的栈顶元素，成功返回值 1.算法如下；1./出栈 2.int StackPop(SeqStack*s,datatype*x)3.4.if(s-top=-1)5.6.printf(栈下溢出!n);7.return FALSE;8.9.else 10.11.*x=s-datas-top;12./s-top=s-top-1;13.s-top-;14.return TRUE;15.16.（六）读栈顶元素 算法如下；1./读栈顶 2.datatype StackGetTop(SeqStack*s)3.4.if(s-top=-1)5.6.printf(栈下溢出!n);7.return FALSE;8.9.else 10.return(s-datas-top);11.六.注意事项（1）置空栈需要向系统申请空间后再设置空栈标志，而判断空栈则无须申请空间直接判断空栈标志是否成立。（2）对于顺序栈，入栈时，需要先判断栈是否满，栈满的条件为s-top=MAXNUM-1，当栈满时，无空间，不能入栈；否则出现空间溢出，引起错误，这种现象称为栈上溢出。（3）出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误（4）出栈时修改栈顶指针位置，栈顶元素位置会改变；而读栈顶元素操作则只需返回当前栈顶元素值，并不改变栈顶指针位置，栈顶元素位置不会改变。七.源代码 1.#include 2.#include 3.#include 4.#include 5.#include 6.#include 7.#include 8.#include 9.#define TRUE 1 10.#define FALSE 0 11.#define OK 1 12.#define ERROR-1 13.#define INFEASIBLE-1 14.#define MAXNUM 100 15.typedef int datatype;16.17.typedef struct 18.datatype dataMAXNUM;19.int top;20.SeqStack;21./置空栈 22.void StackSetNull(SeqStack*s)23.24.s-top=-1;25.26./判断栈是否为空 27.int StackIsEmpty(SeqStack*s)28.29.if(s-top=-1)30.return TRUE;31.else 32.return FALSE;33.34./进栈 35.int StackPush(SeqStack*s,datatype x)36.37.if(s-top=MAXNUM-1)38.39.printf(栈上溢出!n);40.return FALSE;41.42.else 43.44.s-top=s-top+1;45.s-datas-top=x;46.return TRUE;47.48.49./出栈 50.int StackPop(SeqStack*s,datatype*x)51.52.if(s-top=-1)53.54.printf(栈下溢出!n);55.return FALSE;56.57.else 58.59.*x=s-datas-top;60./s-top=s-top-1;61.s-top-;62.return TRUE;63.64.65./读栈顶 66.datatype StackGetTop(SeqStack*s)67.68.if(s-top=-1)69.70.printf(栈下溢出!n);71.return FALSE;72.73.else 74.return(s-datas-top);75.76./输出栈 77.void StackPrint(SeqStack*s)78.79.int p;80.if(StackIsEmpty(s)=TRUE)81.82.printf(栈空!n);83.84./*if(s-top=-1)85.86.printf(输出错误);87.*/88.else 89.90.printf(栈数据元素如下；);91.p=s-top;92.while(p=0)93.94.printf(%d,s-datap);95.p-;96.97.printf(nn);98.99.100./判断栈满 101.int StackIsFull(SeqStack*s)102.103.if(s-top=MAXNUM-1)104.105.return TRUE;106.107.else return FALSE;108.109.110.void main()111.datatype x;112.SeqStack s;113.int read;114.do 115.116.puts(关于顺序栈的操作n);117.puts(=n);118.puts(1-置空栈);119.puts(2-入栈);120.puts(3-出栈);121.puts(4-输出);122.puts(0-退出);123.printf(请选择代号(0-4):);124.scanf(%d,&read);125.printf(n);126.switch(read)127.128.case 1:129.StackSetNull(&s);130.break;131.case 2:132.printf(请输入需要入栈的元素:);133.scanf(%d,&x);134.StackPush(&s,x);135.break;136.case 3:137.if(StackPop(&s,&x)!=FALSE)138.printf(t 出栈数据元素为:%dn,x);139.break;140.case 4:141.StackPrint(&s);142.break;143.case 0:read=0;144.break;145.146.while(read!=0);147.八测试结果图 九实验总结 这一节，学习了栈这种操作受限的线性结构，它只允许在一段进行插入和删除，在表中只允许进行插入和删除的一段称为栈顶，另一端成为栈底，栈顶元素总是最后入栈的因而是最先出栈的；栈底元素总是最先入栈的，因而也是最后出栈的，由于栈的这个特性栈也被称为“先进后出”表。
