栈的顺序表示和实现

1《数据结构》实验报告实验室：****实验日期和时间：****班级：****学号：****姓名：****成绩及教师评语：实验一：栈的顺序表示和实现一．我的实验选题：栈的顺序表示和实现二．实验主要内容和目的：实验主要内容：编制一个顺序栈的演示，实现顺序栈的基本操作，并由这些基本操作实现一些复杂的函数，如进行数值转换、判断回文数等。实验目的：1.编制一个演示顺序栈的初始化、插入、删除、取栈顶元素、置空顺序表、数制转换、判断回文数等操作的程序2.学会定义顺序栈的结构类型，实现对顺序栈的一些基本操作和具体的函数定义。三．概要设计：1)为了实现上述程序功能，需要定义单链表的抽象数据类型：ADTStack{数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,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的栈顶元素并用e返回其值。OutStack(&s)初始条件：栈S已存在。操作结果：将栈S的数据元素从栈顶到栈底依次输出。2shuzhi(&S,n,x)初始条件：空栈S已存在。操作结果：将一个十进制转化为其他进制。huiwen(&S,n)初始条件：空栈S已存在。操作结果：若进栈序列和入栈序列相同，即是回文数，则返回1；否则，返回0。}ADTStack2）本程序包含9个函数：a)主函数main()b)初始化顺序栈InitStack()c)入栈Push()d)出栈Pop()e)获取栈顶元素GetTop()f)遍历顺序表OutStack()g)置空顺序表setEmpty()h)数值转换shuzhi()i)判断回文huiwen()3）各函数间关系如下：四．运用的存储结构说明：//顺序存储结构#defineMAXNUM20#defineElemTypeint/*定义顺序栈的存储结构*/typedefstruct{ElemTypestack[MAXNUM];inttop;3}SqStack;五．主要算法及相关函数功能、参数说明：1.switch（cord）语句，随之cord的选择（1至8）而进行不同的操作。2.a.主函数main()无返回值，为void型。b．初始化顺序表InitStack()参数SqStack*p；无返回值；void型。c.入栈Push()参数SqStack*p,ElemTypex；无返回值；void型。d.出栈Pop()参数SqStack*p；返回值为ElemType型，又#defineElemTypeint，即为整型；ElemType型e.获取栈顶元素GetTop()参数SqStack*p；返回值为ElemType型，又#defineElemTypeint，即为整型；ElemType型f.遍历顺序表OutStack()参数SqStack*p;inti;无返回值；void型。g．置空顺序表setEmpty()参数SqStack*p;无返回值；void型。h．数值转换shuzhi()参数SqStack*p，intn,intx;无返回值；void型。i．判断回文huiwen()参数SqStack*p，intn；返回值非1即0；bool型。六．在设计和调试程序时我遇到的主要问题及其解决方案：无七．程序运行结果截图：1.开始界面，如图（1）2.初始化顺序栈，如图（2）（1）开始界面（2）初始化线性表3.插入:下面是插入第一个元素的图（3），插入后再一次插入其他元素，最终插完元素，见图（4）4(3)插入第一个元素(4)插入最后一个元素（第五个）4.删除栈顶元素，如图（5）5.取栈顶元素，如图（6）(5)删除栈顶元素（6）取栈顶元素6.置空顺序栈，如图（7）（7）置空顺序表7.数值转换（将一个十进制数转换为任意进制），如图（8），是将一个十进制数78三进制数2220。5（8）数值转换8.判断整数回文数，如图(9)和图（10）（9）回文数判断a（10）回文数判断b实验结论：实验成功八．我对本次实验的总结：1.通过对该程序的调试和运行，使的对顺序栈的功能及其构成有了进一步的了解。2.通过多个函数出现在同一个程序中的实现,便于熟悉全局变量和局部变量在程序中的不同作用域的问题3.通过该程序中的的函数思想,可以重新熟悉函数在编程中的设置方法,熟悉函数中参数的设置和传递过程.九．附录：#includestdio.h#includestdlib.h#defineMAXNUM20#defineElemTypeint/*定义顺序栈的存储结构*/typedefstruct{ElemTypestack[MAXNUM];inttop;}SqStack;/*初始化顺序表*/6voidInitStack(SqStack*p){if(!p)printf(内存分配失败!);p-top=-1;}/*入栈*/voidPush(SqStack*p,ElemTypex){if(p-topMAXNUM-1){p-top=p-top+1;p-stack[p-top]=x;}elseprintf(Overflow!\n);}/*出栈*/ElemTypePop(SqStack*p){ElemTypex;if(p-top=0){x=p-stack[p-top];printf(以前的栈顶数据元素%d已经被删除!\n,p-stack[p-top]);p-top=p-top-1;return(x);}else{printf(Underflow!\n);return(0);}}/*获取栈顶元素*/ElemTypeGetTop(SqStack*p){ElemTypex;if(p-top=0){x=p-stack[p-top];printf(\n栈顶元素为:%d\n,x);return(x);}else{printf(Underflow!\n);return(0);}}/*遍历顺序表*/voidOutStack(SqStack*p){inti;7printf(\n);if(p-top0)printf(这是一个空表!);for(i=p-top;i=0;i--)printf(第%d个数据元素是:%6d\n,i,p-stack[i]);}/*置空顺序表*/voidsetEmpty(SqStack*p){p-top=-1;}/*数值转换*/voidshuzhi(SqStack*p,intn,intx){while(n){Push(p,n%x);n=n/x;}}/*判断回文数*/boolhuiwen(SqStack*p,intn){inti=0,j=0;inta[MAXNUM];while(n){a[i]=n%10;Push(p,n%10);n=n/10;i++;}while(p-stack[p-top-j]==a[j])j++;if(ji)return0;elsereturn1;}/*主函数*/voidmain(){SqStack*q;intcord,x,n,y;ElemTypea;printf(第一次使用必须初始化!\n);do{printf(\n);printf(\n----------主菜单------------\n);printf(\n1初始化顺序表\n);printf(\n2插入一个元素\n);printf(\n3删除栈顶元素\n);8printf(\n4取栈顶元素\n);printf(\n5置空顺序栈\n);printf(\n6数制转换\n);printf(\n7判断回文数\n);printf(\n8结束程序运行\n);printf(\n----------------------------\n);printf(请输入您的选择(1,2,3,4,5,6,7));scanf(%d,&cord);printf(\n);switch(cord){case1:{q=(SqStack*)malloc(sizeof(SqStack));InitStack(q);OutStack(q);}break;case2:{printf(请输入要插入的数据元素:a=);scanf(%d,&a);Push(q,a);OutStack(q);}break;case3:{Pop(q);OutStack(q);}break;case4:{GetTop(q);OutStack(q);}break;case5:{setEmpty(q);printf(\n顺序栈被置空!\n);OutStack(q);}break;case6:{q=(SqStack*)malloc(sizeof(SqStack));inti;InitStack(q);printf(请输入要转换的数制：\n);scanf(%d,&x);printf(请输入要转换的数：N=);scanf(%d,&n);shuzhi(q,n,x);if(q-top0)9printf(!);for(i=q-top;i=0;i--)printf(%6d,q-stack[i]);}break;case7:{q=(SqStack*)malloc(sizeof(SqStack));ints;InitStack(q);printf(请输入要判断的正数：\n);scanf(%d,&y);s=huiwen(q,y);if(s==1)printf(%d是回文数!,y);elseprintf(%d不是回文数!,y);}break;case8:exit(0);}}while(cord=8);}