栈的顺序表示和实现

1、数据结构实验报告实验室：*实验日期和时间：*班级：*学号：*姓名：*成绩及教师评语：实验一：栈的顺序表示和实现一我的实验选题：栈的顺序表示和实现二实验主要内容和目的：实验主要内容：编制一个顺序栈的演示，实现顺序栈的基本操作，并由这些基本操作实现一些复杂的函数，如进行数值转换、判断回文数等。实验目的：1.编制一个演示顺序栈的初始化、插入、删除、取栈顶元素、置空顺序表、数制转换、判断回文数等操作的程序2.学会定义顺序栈的结构类型，实现对顺序栈的一些基本操作和具体的函数定义。三概要设计：1) 为了实现上述程序功能，需要定义单链表的抽象数据类型：ADT Stack数据对象：D=ai|aiElemSet

2、,i=1,2,n,n0数据关系：R1=<ai-1,ai>|ai-1,aiD, i=1,2,n 约定an端为栈顶，a1端为栈底。 基本操作：InitStack（&S）操作结果：构造一个空栈SStackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回true；否则返回false。GetTop(S，&e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(&S，e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。Pop(&S，&e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元

3、素并用e返回其值。 OutStack(&s)初始条件：栈S已存在。操作结果：将栈S的数据元素从栈顶到栈底依次输出。shuzhi(&S, n, x)初始条件：空栈S已存在。操作结果：将一个十进制转化为其他进制。huiwen(&S,n)初始条件：空栈S已存在。操作结果：若进栈序列和入栈序列相同，即是回文数，则返回1；否则，返回0。ADT Stack2）本程序包含9个函数：a) 主函数main( )b) 初始化顺序栈InitStack ( )c) 入栈Push ( )d) 出栈 Pop( )e) 获取栈顶元素 GetTop( )f) 遍历顺序表 OutStack( )g) 置

4、空顺序表 setEmpty( )h) 数值转换 shuzhi( )i) 判断回文 huiwen( )3） 各函数间关系如下：四运用的存储结构说明：/顺序存储结构#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef structElemType stackMAXNUM;int top;SqStack;五主要算法及相关函数功能、参数说明：1.switch（cord）语句，随之cord的选择（1至8）而进行不同的操作。2.a. 主函数main()无返回值，为void型。b初始化顺序表InitStack ( )参数SqStack *p；无

5、返回值；void型。c. 入栈Push ( )参数SqStack *p,ElemType x；无返回值；void型。d. 出栈 Pop( )参数 SqStack *p；返回值为ElemType型，又#define ElemType int，即为整型；ElemType型e. 获取栈顶元素 GetTop( )参数SqStack *p；返回值为ElemType型，又#define ElemType int，即为整型；ElemType型f. 遍历顺序表 OutStack( )参数SqStack *p;int i; 无返回值；void型。g置空顺序表 setEmpty( )参数SqStack *p;无返

6、回值；void型。h数值转换 shuzhi( )参数SqStack *p， int n,int x;无返回值；void型。i 判断回文 huiwen( )参数SqStack *p， int n；返回值非1即0；bool型。六在设计和调试程序时我遇到的主要问题及其解决方案：无七程序运行结果截图：1.开始界面，如图（1） 2.初始化顺序栈，如图（2） （1）开始界面 （2）初始化线性表3.插入:下面是插入第一个元素的图（3），插入后再一次插入其他元素，最终插完元素，见图（4） (3)插入第一个元素 (4)插入最后一个元素（第五个）4.删除栈顶元素 ，如图（5） 5.取栈顶元素，如图（6） (5)删

7、除栈顶元素 （6）取栈顶元素6.置空顺序栈，如图（7）（7）置空顺序表7. 数值转换（将一个十进制数转换为任意进制），如图（8），是将一个十进制数78三进制数2220。（8）数值转换8. 判断整数回文数，如图(9)和图（10） （9）回文数判断a （10）回文数判断b实验结论：实验成功八我对本次实验的总结：1.通过对该程序的调试和运行，使的对顺序栈的功能及其构成有了进一步的了解。2.通过多个函数出现在同一个程序中的实现,便于熟悉全局变量和局部变量在程序中的不同作用域的问题3.通过该程序中的的函数思想,可以重新熟悉函数在编程中的设置方法,熟悉函数中参数的设置和传递过程.九附录：#include&

8、lt;stdio.h>#include<stdlib.h>#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef structElemType stackMAXNUM;int top;SqStack;/*初始化顺序表*/void InitStack(SqStack *p)if(!p)printf("内存分配失败!");p->top =-1;/*入栈*/void Push(SqStack *p,ElemType x)if(p->top <MAXNUM-1)p->top =p

9、->top+1;p->stackp->top=x;elseprintf("Overflow! n");/*出栈*/ElemType Pop(SqStack *p)ElemType x;if(p->top>=0) x=p->stackp->top;printf("以前的栈顶数据元素%d已经被删除!n",p->stackp->top);p->top=p->top-1;return(x);elseprintf("Underflow! n");return(0);/*获取栈顶元

10、素*/ElemType GetTop(SqStack *p) ElemType x;if(p->top>=0) x=p->stackp->top;printf("n栈顶元素为:%dn",x);return(x);else printf("Underflow! n");return(0);/*遍历顺序表*/void OutStack(SqStack *p) int i;printf("n");if(p->top<0)printf("这是一个空表!");for(i=p->top

11、;i>=0;i-)printf("第%d个数据元素是: %6dn",i,p->stacki);/*置空顺序表*/void setEmpty(SqStack *p)p->top=-1;/* 数值转换 */void shuzhi(SqStack *p,int n,int x) while(n) Push(p,n%x); n=n/x;/*判断回文数*/bool huiwen(SqStack *p,int n)int i=0,j=0;int aMAXNUM;while(n)ai=n%10; Push(p,n%10); n=n/10; i+;while(p->

12、stackp->top-j=aj) j+;if(j<i)return 0;else return 1;/*主函数*/void main()SqStack *q;int cord,x,n,y;ElemType a;printf("第一次使用必须初始化!n");doprintf("n");printf("n-主菜单-n");printf("n 1 初始化顺序表 n");printf("n 2 插入一个元素 n");printf("n 3 删除栈顶元素 n");prin

13、tf("n 4 取栈顶元素 n");printf("n 5 置空顺序栈 n"); printf("n 6 数制转换 n");printf("n 7 判断回文数 n");printf("n 8 结束程序运行 n");printf("n-n");printf("请输入您的选择(1,2,3,4,5,6,7)");scanf("%d",&cord);printf("n");switch(cord)case 1:q=(

14、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: GetTop(q); OutStack(q);break;case 5: setEmpty(q);printf("n顺序栈被置空! n"); OutStack(q);

15、break;case 6:q=(SqStack * )malloc(sizeof(SqStack);int i; InitStack(q);printf("请输入要转换的数制：n"); scanf("%d",&x); printf("请输入要转换的数：N="); scanf("%d",&n); shuzhi(q,n,x); if(q->top<0) printf("!"); for(i=q->top;i>=0;i-) printf("%6d",q->stacki);break;case 7: q=(SqStack *