栈的实现及进制转换

《栈的实现及进制转换》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、业务1512王俊钢实训报告（数据结构）课程项目：栈的实现及进制转换班级：1512姓名：王俊钢指导教师：张冰日期：2015年11月实验二栈和队列一、实验目的1、掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。二、实验内容1、顺序栈的实现和运算；2、栈的运用—十进制转八进制运算。三、实验要求1、学生用C++/C完成算法设计和程序设计

2、并上机调试通过；2、撰写实验报告，提供实验测试数据和实验结果；3、分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。四、实验准备1、掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用任务中正确选用它们；2、熟练掌握顺序栈和循环队列的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法，循环队列中队满和队空的描述方法。3、在学习顺序栈的基本操作实现算法时，应注意：在书上给出的结构定义是采用了一种动态管理方式（不够时，可以再分配），但在C语言中，用数组来存储顺序栈，是静态分配，即不能随机

3、分配空间，这点易引起大家的误解。五、实验步骤1、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化顺序栈；(2)给定一个元素，将此元素压入此栈中；(3)将栈顶一个元素弹出此栈六、实验参考代码1、顺序栈的实现和运算；#include#include#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;//-----栈的顺序存储表示-----#defineSTACK_INIT_S

4、IZE100//存储空间的初始分配量#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_SI

5、ZE;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);//存储分配失

6、败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--)p

7、rintf("%6d",*p);printf("");}//主函数voidmain(){SqStacks;intcord;ElemTypea;printf("第一次使用必须初始化！");do{printf("主菜单");printf("1初始化顺序栈");printf("2插入一个元素");printf("3删除栈顶元素");printf("4结束程序运行");printf("--------------------------------------------------------------------------

8、----");printf("请输入您的选择(1,2,3,4)");scanf("%d",&cord);printf("");switch(cord){ca