栈的实现及进制转换

实训业务1512王报俊钢 告（数据结构）课程项目：栈的实现及进制转换班级： 1512姓名： 王俊钢—指导教师：张冰日期： 2015年11月实验二栈和队列一、实验目的1、 掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2、 掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。二、实验内容1、 顺序栈的实现和运算；2、栈的运用—十进制转八进制运算。三、实验要求1、 学生用C++/C完成算法设计和程序设计并上机调试通过；2、 撰写实验报告，提供实验测试数据和实验结果；3、 分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、实验准备1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用任务中正确选用它们；2、 熟练掌握顺序栈和循环队列的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法，循环队列中队满和队空的描述方法。3、 在学习顺序栈的基本操作实现算法时，应注意：在书上给出的结构定义是采用了一种动态管理方式(不够时，可以再分配)，但在C语言中，用数组来存储顺序栈，是静态分配，即不能随机分配空间，这点易引起大家的误解。五、实验步骤1、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：初始化顺序栈；给定一个元素，将此元素压入此栈中；将栈顶一个元素弹出此栈六、实验参考代码1、顺序栈的实现和运算；#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;// 栈的顺序存储表示 #defineSTACK_INIT_SIZE100//存储空间的初始分配量#defineSTACKINCREMENT10//存储空间的分配增量typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;//构造一个空栈SStatusInitStack(SqStack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//判栈S是否为空栈StatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;elsereturnERROR;}//入栈函数StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//PushStatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//输出顺序栈函数11voidOutStack(SqStackS){int*p;if(S.top==S.base){printf("这是一个空栈！")；elsefor(p=S.top-1;p>=S.base;p--)printf("%6d",*p);printf("\n");}//主函数voidmain(){SqStacks;intcord;ElemTypea;printf("第一次使用必须初始化！\n");do{printf("\n主菜单\n");printf("1初始化顺序栈");printf("2插入一个元素");printf("3删除栈顶元素");printf("4结束程序运行");printf("\n \n");printf("请输入您的选择(1,2,3,4)");scanf("%d",&cord);printf("\n");switch(cord){case1:InitStack(s);OutStack(s);break;case2:printf("请输入要插入的数据兀素：a=");scanf("%d",&a);Push(s,a);printf("%d进栈之后的栈：",a);OutStack(s);break;case3:Pop(s,a);printf("栈顶元素%d出栈之后的栈：",a);OutStack(s);break;case4:exit(0);}while(cord<=4);■ "C:\Users\wang\Desktop\Debug\■脈序噬的室现印运隼启怡第一次使用影页初垢仁!干乘甲i初始化顺序栈2插入Y元素3删除栈顶元素4结束程序运行低输九您的选择<:US3,Ml肢是一岭空栈！干采甲1初始化帧序栈2插玉一个元素3删除栈顶元素4结束程序运行5青输入您的选择£1”b3”4）捋:側拼音输人法全:□请输炭您的选择（1,2,40B'C:\LJsers\wang\Desktop\Debu頁手书I的矣现和运算exen；捋:側拼音输人法全:□请输炭您的选择（1,2,40B'C:\LJsers\wang\Desktop\Debu頁手书I的矣现和运算exen；第一燥使用必须初绐优!i!1初始化烦序栈2霜呢一个元素3删除栈顶元素4结克程序运行请输鳶您的选择（：U注4羽:L这是一个空栈!请输X您的选择<1>2>3,452主苹单1初始化狮序栈2麻人一个元素3删除栈顶元素4结克程序运行请输灰要拯入的数-M56777456777进栈之后的栈：-158777壬菜单1初始化顺序桟2満凡一个兀素3删除栈顶兀素4结克程序运讦鬥'C:\LIsers\w/ang\Destctcp\Debu9、販字桂的字现印运算、兀弟3删除顶元》4t.F1初页序*鬥'C:\LIsers\w/ang\Destctcp\Debu9、販字桂的字现印运算、兀弟3删除顶元》4t.F1初页序*Ji青输入您的选择€仃罠九小曲是一个空栈！千莽~年1初始化J帧序栈2插上个元素3册！|除栈顶元素4结束程序运行请输入您的诜择（1-2.3,4>3胡输入要捶/45677?遁戋!OO&^6777工荣单1初始化J帧序栈=KA-个元養？删除栈顶元養4结克程序运行*输入您的选择个林顶兀素45畀即主菜单1初始化顺序栈1>2”3,4>3出桟之后的栈：这是一个空桟!已插歟一个元表弐删除栈顶元素4结束程序运行lv情驗人竝僮揪「S•窖lv2、十进制转换八进制实验代码#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;//构造一个空栈SStatusInitStack(SqStack&S){S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;//判栈S是否为空栈StatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;elsereturnERROR;}//入栈函数StatusPush(SqStack&S,ElemTypee){if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}//出栈函数StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK