数据结构-实验三-栈和队列及其应用.doc
《数据结构-实验三-栈和队列及其应用.doc》由会员分享,可在线阅读,更多相关《数据结构-实验三-栈和队列及其应用.doc(32页珍藏版)》请在咨信网上搜索。
1、实验编号:3 四川师大数据结构实验报告 2016年10月29日实验三 栈与队列及其应用_一 实验目得及要求(1) 掌握栈与队列这两种特殊得线性表,熟悉它们得特性,在实际问题背景下灵活运用它们;(2) 本实验训练得要点就是“栈”得观点及其典型用法;(3) 掌握问题求解得状态表示及其递归算法,以及由递归程序到非递归程序得转化方法。二 实验内容(1) 编程实现栈在两种存储结构中得基本操作(栈得初始化、判栈空、入栈、出栈等);(2) 应用栈得基本操作,实现数制转换(任意进制);(3) 编程实现队列在两种存储结构中得基本操作(队列得初始化、判队列空、入队列、出队列);(4) 利用栈实现任一个表达式中得语
2、法检查(括号得匹配)。(5) 利用栈实现表达式得求值。注:(1)(3)必做,(4)(5)选做。三 主要仪器设备及软件(1)PC机(2)Dev C+ ,Visual C+, VS2010等四 实验主要流程、基本操作或核心代码、算法片段(该部分如不够填写,请另加附页)(1) 编程实现栈在两种存储结构中得基本操作(栈得初始化、判栈空、入栈、出栈等);A、顺序储存: 代码部分:/Main、cpp:#includeSStack、hint main()SqStack S;SElemType e;int elect=1;InitStack(S);cout 已经创建一个存放字符型得栈 elect;cout e
3、ndl;switch (elect)case 1:cout e;Push(S, e);break;case 2: if(Pop(S, e)cout e is pop endl; elsecoutblankendl;break;case 3:if (StackEmpty(S)cout 栈空 endl;elsecout 栈未空 endl;break;case 4:GetTop(S, e);cout e is e endl; break;case 5:StackLength(S);break;case 0:break;DestroyStack(S);return OK;/SStack、cpp:#in
4、cludeSStack、h/输出菜单void Muse()cout 请选择功能: endl;cout 1、入栈 endl;cout 2、出栈 endl;cout 3、判栈空 endl;cout 4、返回栈顶部数据 endl;cout 5、栈长 endl;cout 0、退出系统 endl;cout = STACK_INIT_SIZE)S、base = (SElemType *)realloc(S、base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType);if (!S、base) exit(ERROR);S、top = S、base
5、+ S、stacksize;S、stacksize += STACKINCREMENT;*S、top+ = e;return OK;/出栈Status Pop(SqStack &S, SElemType &e)if (S、base = S、top)return ERROR;e = *-S、top; coutpop succeedendl;return OK;/判栈空Status StackEmpty(SqStack S)if (S、top = S、base)return ERROR;return OK;/销毁栈Status DestroyStack(SqStack &S)free(S、base
6、);S、top=NULL;S、stacksize = 0;cout 栈已销毁 endl;return OK;int StackLength(SqStack S)cout StackLength is S、top-S、base endl;return OK;/SStack、h:#include#includeusing namespace std;const int STACK_INIT_SIZE = 100;const int STACKINCREMENT = 10;const int ERROR = 0;const int OK = 1;typedef char SElemType;type
7、def int Status;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;Status InitStack(SqStack &S);/创建顺序存储得栈Status GetTop(SqStack S, SElemType &e);/得到栈顶数据Status Push(SqStack &S, SElemType &e);/入栈Status Pop(SqStack &S, SElemType &e);/出栈void Muse();/输出菜单界面Status StackEmpty(SqStack S);/判断栈
8、就是否为空Status DestroyStack(SqStack &S);/销毁栈int StackLength(SqStack S);/计算栈得长度 运行结果:B、 链式储存: 代码部分:/Main、cpp#includeLstack、hint main()Lq_Stack L;if(InintStack (L)coutbuild stack succeeddata=0;L-next=NULL;return OK;Status push (Lq_Stack &L,SElemType e)/入栈LqStack *p;p=(LqStack *)malloc(sizeof(LqStack);if(
9、!p) exit(ERROR);p-data=e;L-data+;p-next=L-next;L-next=p;return OK;Status pop (Lq_Stack &L,SElemType &e)/出栈LqStack *p;if(L-next=NULL) return ERROR;p=L-next;e=p-data;L-next=p-next;L-data-;free(p);return OK;Status GetTop(Lq_Stack L, SElemType &e)/得到栈顶数据if(L-next=NULL) return ERROR;e=L-next-data;return
10、OK;Status StackEmpty(Lq_Stack L)/判断栈就是否为空if(L-next=NULL)return ERROR;else return OK;int StackLength(Lq_Stack L)/计算栈得长度return L-data;Status DestroyStack(Lq_Stack &L)/销毁栈LqStack *p;while(!L)L=p;L=L-next;free(p);return OK;void Menu(Lq_Stack &L,SElemType e)/输出菜单选择执行得功能int select=1;while(select)coutendl;
11、cout请选择功能endl;cout1、入栈endl;cout2、出栈endl;cout3、得到顶部数据endl;cout4、判断栈就是否为空endl;cout5、输出栈得长度endl;cout0、退出程序endl;coutselect;switch (select)case 0:break;case 1:coute;if(push(L,e)coutpush succeedendl;else coutpush failedendl;break;case 2:if(pop(L,e)coutdata e is popendl;else coutpop failedendl;break;case 3
12、:if(GetTop(L,e)couthead data e is popendl;else coutGet failedendl;break;case 4:if(StackEmpty(L)coutstack is not NULLendl;else coutstack is NULLendl;break;case 5:coutthis stack length is StackLength(L)endl;break;/Lstack、h#include#includeusing namespace std;const int OK=1;const int ERROR=0;typedef int
13、 SElemType;typedef int Status;typedef struct LqStackSElemType data;struct LqStack *next;LqStack,*Lq_Stack;Status InintStack (Lq_Stack &L);/创建栈Status push (Lq_Stack &L,SElemType e);/入栈Status pop (Lq_Stack &L,SElemType &e);/出栈Status GetTop(Lq_Stack L, SElemType &e);/得到栈顶数据Status StackEmpty(Lq_Stack L)
14、;/判断栈就是否为空int StackLength(Lq_Stack L);/计算栈得长度Status DestroyStack(Lq_Stack &L);/销毁栈void Menu(Lq_Stack &L,SElemType e);/输出菜单选择执行得功能 运行结果:(2)应用栈得基本操作,实现数制转换(任意进制); 代码部分:/Main、cpp#includeSStack、hint main()int number;coutnumber;conversion(number);return 0;SStack、cpp#includeSStack、hStatus InitStack(SStack
15、 &S)/创建栈S、dase=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType);if (!S、dase) exit(ERROR);S、top=S、dase;S、stacksize=STACK_INIT_SIZE;return OK;Status push(SStack &S,ElemType e)/入栈if(S、top-S、dase = S、stacksize)/栈满追加空间S、dase=(ElemType *)realloc(S、dase,(STACK_INIT_SIZE+STACKINCREMENT) * sizeof(ElemTy
16、pe);if(!S、dase) exit(ERROR);S、top=S、dase+STACK_INIT_SIZE;S、stacksize+=STACKINCREMENT;*S、top+=e;return OK;Status pop(SStack &S,ElemType &e)/出栈if(S、top= S、dase) return ERROR;e=*-S、top;return OK;Status StackEmpty(SStack &S)/判断栈就是否为空if(S、dase=S、top) return ERROR;return OK;void conversion(int number)/转换为
17、e进制并输出SStack S;int N,e;if(InitStack(S)cout栈创建成功endl;coutN;while(N)push(S,N%number);N=N/number;while(StackEmpty(S)pop(S,e);coute;coutendl;/SStack、h#ifndef SSTACK_H#define SSTACK_H#include#includeusing namespace std;const int STACK_INIT_SIZE=100;const int STACKINCREMENT=10;const int OK=1;const int ERR
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 队列 及其 应用
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【天****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【天****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。