栈和队列的基本操作的实现-数据结构实验.docx
实验报告May72015姓名：陈斌学号：E11314079专业：13计算机科学与技术数据结构第二次实验学号E11314079专业计算机科学与技术姓名陈斌实验日期2015.05.07教师签字成绩实验报告实验名称栈和队列的根本操作的实现【实验目的】1. 理解并掌握栈和队列的逻辑结构和存储结构；2. 理解栈和队列的相关根本运算；3. 编程对相关算法进行验证；4. 学会利用栈和队列解决实际问题。【实验内容】1.实现顺序栈的根本运算编写一个程序，实现顺序栈的各种根本运算，并在此根底上设计一个主程序完成如下功能:(1)初始化栈S;(2)判断栈S是否为空；依次进栈元素-1,2,10,-3,5；(4)判断栈S是否为空；(5)输出栈长度：(6)输出从栈顶到栈底的元素：(7)输出出栈序列；(8)判断栈S是否为空。源代码：head.h:#include<string.h>#include<ctype.h>#include<malloc.h>/malloc()#include<limits.h>/INT,MAX#include<stdio.h>/EOF,NULL#include<stdlib.h>/atoi()#include<io.h>/eof()#include<math.h>/floor(),ceil(),abs()#include<process.h>/exit()#include<iostream.h>/cout,cin函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1/OVERFLOW在math.h中己定义为3typedefintStatus;typedefintBoolean;/布尔类型head2.h:#defineSTACKNnSIZE100#defineSTACKINCREMENT10typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;main.cpp:#defineSEIemTypeint#include"head.h"#include"head2.h"StatuslnitStack(SqStack&S)*构造一个空栈S*/S.base=(SEIemType*)malloc(STACK_INIT_SIZE*sizeof(SEIemType);if(!S.base)e×it(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,SEIemTyPe&e)*假设栈不空，那么用e返回S的栈顶元素，并返回OK；否那么返回ERRoR*/if(S.top>S.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)e×it(OVERFLOW);/*存储分配失败*/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()失败，那么操作失败*/while(S.top>S.base)visit(*-S.top);cout<<endl;return0K;)StatusVisitfSEIemTypec)cout<<c<<""returnOK;voidPrintMenuf)cout<*欢送使用*11<<endl;CoUt<<叮.初始化栈s."<<endl;COUt<<”2.判断栈s是否为空J<<endl;COUt<v”3.依次进栈元素l,2,10,3,5J<<endl;COUtV<"4.输出栈长度J<<endl;COUt<<"5.输出从栈顶到栈底的元素."<<endl;CoUt<<,6输出出栈序列J<<endl;COUt<<”0.退出.,<<endl;COut<<*,)voidmain()SqStacks;SEIemTypee;PrintMenuf);while(l)cout<<endl;CoUt<<”选择需要执行的功能:"；intnumber;cin>>number;switch(number)case 1:InitStackfs);CoUteC”顺序栈s初始化成功J<<endl;break;case 2:if(StackEmpty(s)CoUt<<"顺序栈s为空."<<endl;elseCoUt<<"顺序栈s不为空J<<endl;break;case 3:PUSh(S,-1);PUSh(S,2);PUSh(S,10);PUSh(S,-3);PUSh(S,5);CoUt«”入栈成功J<<endl;break;case 4:cout<<"is的长度为:"<<StackLength(s)<<endl;break;case 5:8Ut<<”从栈顶到栈底的元素依次为广；StackTraverse(szvisit);break;case 6: cout<<”出栈序列为:“；while(!StackEmpty(s)POP(S,e);cout<<e<<"")cout<<endl;break;case0:cout<<"tttt感谢使用!"<<endl;cout<<"tttttDesignedBy->斌斌Jv'<<endl;exit(0);default:CoUt<<"功能选择有误,请重新选择J<<endl;)运行结果：2.实现链栈根本运算编写一个程序，实现链栈的各种根本运算，并在此根底上设计一个主程序完成如下功能:(1)初始化栈s；(2)判断栈S是否为空；(3)依次进栈元素10,-2,10,-3,15,12；(4)判断栈S是否为空；(5)输出栈长度：(6)输出从栈顶到栈底的元素：(7)输出出栈序列；(8)判断栈S是否为空。源代码：head.h:#include<string.h>#include<ctype.h>#include<malloc.h>/malloc()#include<limits.h>/INT,MAX#include<stdio.h>/EOF,NULL#include<stdlib.h>/atoi()#include<io.h>/eof()#include<math.h>/floor(),ceil(),abs()#include<process.h>/exit()#include<iostream.h>/cout,cin函数结果状态代码#defineTRUE1#defineFALSEO#defineOK1#defineERRORO#defineINFEASIBLE-1/OVERFLOW在math.h中已定义为3typedefintStatus;typedefintBoolean;/布尔类型head2.h:typedefstructLNode(SElemTypedata;structLNode*next;LNode,*LinkStack;main.cpp:#defineSEIemTypeint#include"head.h"ftinclude,head2.h"StatusInitLinkStacktLinkStack&L)1.=(LinkStack)malloc(sizeof(LNode);*产生头结点,并使S指向此头结点*/if(!L)/*存储分配失败*/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->ne×t=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
