栈和队列的基本操作的实现-数据结构实验.docx

《栈和队列的基本操作的实现-数据结构实验.docx》由会员分享，可在线阅读，更多相关《栈和队列的基本操作的实现-数据结构实验.docx（26页珍藏版）》请在优知文库上搜索。

1、实验报告May72015姓名：陈斌学号：E11314079专业：13计算机科学与技术数据结构第二次实验学号E11314079专业计算机科学与技术姓名陈斌实验日期2015.05.07教师签字成绩实验报告实验名称栈和队列的根本操作的实现【实验目的】1. 理解并掌握栈和队列的逻辑结构和存储结构；2. 理解栈和队列的相关根本运算；3. 编程对相关算法进行验证；4. 学会利用栈和队列解决实际问题。【实验内容】1.实现顺序栈的根本运算编写一个程序，实现顺序栈的各种根本运算，并在此根底上设计一个主程序完成如下功能:(1)初始化栈S;(2)判断栈S是否为空；依次进栈元素-1,2,10,-3,5；(4)判断栈S

2、是否为空；(5)输出栈长度：(6)输出从栈顶到栈底的元素：(7)输出出栈序列；(8)判断栈S是否为空。源代码：head.h:#include#include#include/malloc()#include/INT,MAX#include/EOF,NULL#include/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#include/cout,cin函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/OVERFL

3、OW在math.h中己定义为3typedefintStatus;typedefintBoolean;/布尔类型head2.h:#defineSTACKNnSIZE100#defineSTACKINCREMENT10typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;main.cpp:#defineSEIemTypeint#includehead.h#includehead2.hStatuslnitStack(SqStack&S)*构造一个空栈S*/S.base=(SEIemType*)malloc(STACK_INIT_

4、SIZE*sizeof(SEIemType);if(!S.base)eit(OVERFLOW);/存储分配失败*/S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;)StatusStackEmptyfSqStack&S)*假设栈S为空栈，那么返回TRUE,否那么返回FALSE*/if(S.top=S.base)returnTRUE;elsereturnFALSE;)intStackLengthfSqStack&S)*返回S的元素个数，即栈的长度*/returnS.top-S.base;)StatusGetTop(SqStack&S,SEIemT

5、yPe&e)*假设栈不空，那么用e返回S的栈顶元素，并返回OK；否那么返回ERRoR*/if(S.topS.base)e=*(S.top-l);returnOK;)elsereturnERROR;)StatusPushfSqStack&S,SEiemTyPee)*插入元素e为新的栈顶元素*/if(S.top-S.base=S.stacksize)/*栈满，追加存储空间*/(S.base=(SEIemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SEIemType);if(!S.base)eit(OVERFLOW);/*存储分配

6、失败*/S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;)*S.top+=e;returnOK;)StatusPop(SqStack&S,SElemTyPe&e)*假设栈不空，那么删除S的栈顶元素，用e返回其值，并返回0K；否那么返回ERROR*/if(S.top=S.base)returnERROR;e=*-S.top;returnOK;)StatusStackTraverse(SqStackS,Status(*visit)(SEIemType)*从栈顶到栈底依次对栈中每个元素调用函数ViSit()。*/*一旦ViSit()失败，那么

7、操作失败*/while(S.topS.base)visit(*-S.top);coutendl;return0K;)StatusVisitfSEIemTypec)coutc;returnOK;voidPrintMenuf)cout*欢送使用*11endl;CoUt叮.初始化栈s.endl;COUt”2.判断栈s是否为空Jendl;COUtv”3.依次进栈元素l,2,10,3,5Jendl;COUtV4.输出栈长度Jendl;COUt5.输出从栈顶到栈底的元素.endl;CoUt,6输出出栈序列Jendl;COUt”0.退出.,endl;COut*,)voidmain()SqStacks;SEI

8、emTypee;PrintMenuf);while(l)coutendl;CoUtnumber;switch(number)case 1:InitStackfs);CoUteC”顺序栈s初始化成功Jendl;break;case 2:if(StackEmpty(s)CoUt顺序栈s为空.endl;elseCoUt顺序栈s不为空Jendl;break;case 3:PUSh(S,-1);PUSh(S,2);PUSh(S,10);PUSh(S,-3);PUSh(S,5);CoUt”入栈成功Jendl;break;case 4:coutis的长度为:StackLength(s)endl;break;

9、case 5:8Ut”从栈顶到栈底的元素依次为广；StackTraverse(szvisit);break;case 6: cout”出栈序列为:“；while(!StackEmpty(s)POP(S,e);coute;)coutendl;break;case0:couttttt感谢使用!endl;cout斌斌Jvendl;exit(0);default:CoUt功能选择有误,请重新选择Jendl;)运行结果：2.实现链栈根本运算编写一个程序，实现链栈的各种根本运算，并在此根底上设计一个主程序完成如下功能:(1)初始化栈s；(2)判断栈S是否为空；(3)依次进栈元素10,-2,10,-3,15

10、,12；(4)判断栈S是否为空；(5)输出栈长度：(6)输出从栈顶到栈底的元素：(7)输出出栈序列；(8)判断栈S是否为空。源代码：head.h:#include#include#include/malloc()#include/INT,MAX#include/EOF,NULL#include/atoi()#include/eof()#include/floor(),ceil(),abs()#include/exit()#include/cout,cin函数结果状态代码#defineTRUE1#defineFALSEO#defineOK1#defineERRORO#defineINFEASIB

11、LE-1/OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBoolean;/布尔类型head2.h:typedefstructLNode(SElemTypedata;structLNode*next;LNode,*LinkStack;main.cpp:#defineSEIemTypeint#includehead.hftinclude,head2.hStatusInitLinkStacktLinkStack&L)1.=(LinkStack)malloc(sizeof(LNode);*产生头结点,并使S指向此头结点*/if(!L)/*存储分配失败*

12、/exit(OVERFLOW);1.-next=NULL;/*指针域为空*/returnOK;)StatusLinkStackEmptyfLinkStack&L)/*假设栈S为空栈，那么返回TRUE,否那么返回FALSE*/if(L-next=NULL)returnTRUE;elsereturnFALSE;)intLinkStackLengthtUnkStack&L)inti=0;1.inkStackp=L-next;while(p)+i；p=p-next;)returni;)StatusHeadInserttLinkStack&L,SEIemTyPee)1.inkStacks;s=(LinkStack)malloc(sizeof(LNode);*生成新结点*/s-data=e;/*给结点赋值*/s-net=L-next;/*插在表头*/1.-next=s;returnOK;)StatusDeleteFirst(LinkStack&L,SEIemType&e)1.inkStackp=L-next;if(p)e=p-data;1.-next=p-next;free(p);returnOK;)elsereturnERROR;)StatusLinkStackTraverse(LinkStack&LzStatus(*visit)(SEIemType)(1.inkStackp=L