数据结构实验三栈的表示和实现

《数据结构实验三栈的表示和实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验三栈的表示和实现一、实验目的1.掌握栈的顺序存储结构2.掌握栈的基本操作算法。二、实验内容对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数。(算法3.1)三、实验步骤：1.将计算过程中得到的八进制数的各位顺序进栈。2.按出栈序列打印输出对应的八进制数。四、算法说明在利用栈的存储结构时初始化设空栈时不应限定栈的最大容量，可设定存储空间初始分配量和存储空间分配增量，用typedefstruct来定义栈。然后构造空栈，用e返回栈顶元素，插入栈顶元素e,用ClearStack(sqstack&s)清空S这个栈，函数StackEmpty(sqstack&

2、S)表示返回S的元素个数，及栈的长度，最后函数conversion(intNum)是数字的转化。五、测试结果"D:PROGRAz1C-FREE~1.5tempUntitled2.exe"请输入您要转换的十进制的大小:1012Pressanykeytocontinue...六、分析与探讨了解和掌握数字转化的基本规律，由于计算过程是从地位到高位顺序产生的八进制各个数位，而打卬输岀，是从高位到地位进行的，与计算过程相反。因此，八进制的各位顺序进栈，则按出栈序列打印输出的即是正确的计算结果。七、附录：源代码源代码列在附录屮，要求程序风格清晰易理解，有充分的注释

3、。有意义的注释行不少于30%。#include#include#include#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstructint*base;〃栈底指针int*top;〃栈顶指针intstacksize;//当前分配的存储空间}sqstack;voidInitStack(sqstack&S)〃构造空栈{S.base=newint[STACK_INIT_SIZE];if(!S.base)cou

4、t«H内存分配失败M«endl;S.top=S.base;S.stacksize=STACK_INIT_SIZE;}voidGetTop(sqstackS,int&e)〃用e返冋栈顶元素{if(S.top==S.base)cout«"该栈为空栈"«endl;e=*(S.top-l);cout«e«endl;}voidPush(sqstack&S,inte)〃插入栈顶元素e{if(S.top-S.base>=S.stacksize){S.base=newint[S.stacksize+STACKINCREMENTJ;if(!S.base)coutvv"内存分配失

5、败"«endl;S.top=S.base+S.stacksize;S.stacksize+二STACKINCREMENT;}*S.top++二e;}voidClearStack(sqstack&s){s.top=s.base;cout«H栈己清空!"«endl;}voidPop(sqstack&S,int&e)〃若栈不空，用e返冋其值{if(S.top==S.base)cout«H该栈为空栈M«endl;c二*—S.top;//cout«e«"”；1intStackEmpty(sqstack&S)//返冋S的元素个数，及栈的长度{if(S.top==S.bas

6、e)return0;}voidconversion(intNum){//算法3.1//对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数inte;sqstackS;InitStack(S);//构造空栈while(Num){Push(S,Num%8);Num=Num/&}while(S.top!=S.base){Pop(S,e);printf(u%dM,e);}printf(uM);}//conversivoidmain(){intk;cout«H请输入您要转换的十进制的大小：”vvendl;cin»k;conversion(k);