数据结构栈和队列.doc

《数据结构栈和队列.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验二栈和队列一、实验目的1、掌握栈的特点(先进后出FILO)及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。2、掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，队列顺序存储结构、链式存储结构和循环队列的实现，以便在实际问题背景下灵活应用。二、实验内容1、顺序栈的实现和运算；2、循环队列的实现和运算；3、栈的运用—十进制转八进制运算。三、实验要求1、学生用C++/C完成算法设计和程序设计并上机调试通过；2、撰写实验报告，提供实验测试数据和实

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

3、间，这点易引起大家的误解。五、实验步骤1、编程实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化顺序栈；(2)给定一个元素，将此元素压入此栈中；(3)将栈顶一个元素弹出此栈。2、编写一个程序实现循环队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：(1)初始化循环队列；(2)给定一个元素，将此元素插入此队列中；(3)将队头一个元素出队。3、栈的运用实例十进制转八进制。六、实验参考代码1、顺序栈的实现和运算；#include#includ

4、e#defineOK1#defineERROR0#defineOVERFLOW-2typedefintElemType;typedefintStatus;//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100//存储空间的初始分配量#defineSTACKINCREMENT10//存储空间的分配增量typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;//构造一个空栈S

5、StatusInitStack(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;}//入栈函数S

6、tatusPush(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;}//出栈函数St

7、atusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//输出顺序栈函数voidOutStack(SqStackS){int*p;if(S.top==S.base){printf("这是一个空栈！");}elsefor(p=S.top-1;p>=S.base;p--)printf("%6d",*p);printf("");}//主函数voidmain(){SqStacks;intcord

8、;ElemTypea;printf("第一次使用必须初始化！");do{printf("主菜单");printf("1初始化顺序栈");printf("2插入一个元素");printf("3删除栈顶元素");printf("4结束程序运行");printf("------------------------------------------------------------------------------");printf("请输入您的选择(1,2,3,4)");sc