2022年数据结构实验三资料 .pdf
数据结构实验报告三实验名：栈的基本操作院系：物理与电子工程系姓名：黄锐（2009122105）班级：20091221 日期：2010-10-13 请在下次上机前以附件形式提交到yuan_ 一、上机实验的问题和要求：设计算法，入栈和出栈的操作。具体实现要求：1写出栈的入栈和出栈算法。2 写一个程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M 向 N 进制（2 或 8 或 16）的转换。（1）采用顺序存储结构实现栈。（2）采用链表结构实现栈。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）关于链表实现栈操作，内存空间利用比较充分，你插入一个，他就给你分配一个内存空间，这样相对顺序表实现栈比较合理。三、源程序及注释：1.采用顺序存储结构实现栈：#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10 typedef struct int*base;int*top;int stacksize;SqStack;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -/初始化得到一个空栈/void InitStack(SqStack&s)s.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int);if(!s.base)exit(0);s.top=s.base;s.stacksize=STACK_INIT_SIZE;/向栈里插入一个数/int StackInter(SqStack&s,int e)if(s.top-s.base=s.stacksize)s.base=(int*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(int);if(!s.base)exit(0);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return 1;/把栈顶元素删除，并把值赋给e,实现退栈/int StackPop(SqStack&s,int&e)if(s.top=s.base)return 0;e=*-s.top;*s.top=0;return 1;main()SqStack p;int q=0,n,j,date20,o;printf(请输入一个十进制的数和要转换的目标进制:n);cinno;InitStack(p);/入栈/while(n)StackInter(p,n%o);n/=o;q+;cout转换后的数为:;/出栈输出结果/for(j=0;jq;j+)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -if(StackPop(p,datej)switch(datej)case 10:coutA;break;case 11:coutB;break;case 12:coutC;break;case 13:coutD;break;case 14:coutE;break;case 15:coutF;break;default:coutdatej;else cout退栈失败!endl;coutendl;free(p.base);2.采用链表结构实现栈:#include#include#include typedef struct Sqt int date;struct Sqt*prior;/指向前一个栈元素Sqt;typedef struct Sqt*base;Sqt*top;/int stacksize;/栈当前分配的长度/int nowsize;/栈元素的当前长度SqStack;/初始化得到一个空栈/void InitStack(SqStack&s)s.base=(Sqt*)malloc(sizeof(Sqt);if(!s.base)exit(0);s.top=s.base;/向栈里插入一个数/int StackInter(SqStack&s,int e)Sqt*p;s.top-date=e;p=(Sqt*)malloc(sizeof(Sqt);/new Sqt();名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -if(!p)exit(0);p-prior=s.top;s.top=p;return 1;/把栈顶元素删除，并把值赋给e,实现退栈/int StackPop(SqStack&s,int&e)Sqt*p;if(s.top=s.base)cout该栈已为空栈!prior-date;s.top-prior-date=0;p=s.top;s.top=s.top-prior;free(p);/删除一个，就释放一个return 1;main()SqStack p;int q=0,n,j,date20,o;printf(请输入一个十进制的数和要转换的目标进制:n);cinno;InitStack(p);/入栈/while(n)StackInter(p,n%o);n/=o;q+;cout转换后的数为:;/出栈输出结果/for(j=0;jq;j+)if(StackPop(p,datej)/如果是 16 进制就以字母的形式显示出来/switch(datej)case 10:coutA;break;case 11:coutB;break;case 12:coutC;break;case 13:coutD;break;case 14:coutE;break;case 15:coutF;break;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -default:coutdatej;else cout退栈失败!endl;coutendl;free(p.base);/释放 malloc()在堆中申请的内存空间四、运行输出结果：1.采用顺序存储结构实现结果：2.采用链表结构实现栈结果：五、调试和运行程序过程中产生的问题及采取的措施：出现函数引用和传值方面的问题。把void InitStack(SqStack&s)中的参数改成引用（取别名）。六、对算法的程序的讨论、分析，改进设想，其它经验教训：名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -七、对实验方式、组织、设备、题目的意见和建议：名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -
