《栈队列及其应用》PPT课件

《栈队列及其应用》PPT课件

ID:45482156

大小:319.84 KB

页数:24页

时间:2019-11-13

《栈队列及其应用》PPT课件_第1页
《栈队列及其应用》PPT课件_第2页
《栈队列及其应用》PPT课件_第3页
《栈队列及其应用》PPT课件_第4页
《栈队列及其应用》PPT课件_第5页
资源描述:

《《栈队列及其应用》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、线性表的应用1、【问题描述】线性表a和b分别表示两个线性表,它们的数据元素类型相同,现要将b中存在而a中不存在的数据元素插入到线性表a中。设线性表a的长度与线性表b的长度之和不超过线性表a允许的最大长度。【参考程序】proceduIreunion(vara:list;b:list);beginn:=length(a);fori:=1tolength(b)dobegingetlist(b,i,x);{取线性表b中第i位上的数给T}k:=loclist(a,x);{返回z在线性表a中的位置}ifk=0thenbegininslist(a,n+1,x);{将z插入线

2、性表a的末尾}n:=n+1;end;end;end;线性表的应用2、【问题描述】已知线性表。和b中的数据元素按递增的顺序排列,现要求将a和b归并为一个新的线性表c,c中的数据元素仍按递增排列。①用数组实现②用链表实现线性表的应用3、Joseph(约瑟夫)问题【问题描述】m只猴子要选大王,选举办法如下:所有猴子按1…m编号围坐一圈,从第1号开始按顺序1,2,…,n报数,凡报到竹的猴子退出到圈外,如此循环,直到圈内只剩下一只猴子时,这只猴子就是大王。m和咒由键盘输入,打印出最后剩下的那只猴子的编号。运行示例:Inputm,n:83Themonkeykingisno

3、.7①用数组实现【算法分析】在确定程序设计方法之前首先来考虑如何组织数据,由于要记录m只猴子的状态,可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号,元素的值表示猴子的状态,用monkeyEk]=l表示第k只猴子仍在圈中,monkeyEk-]=0则表示第k只猴子已经出圈。程序采用模拟选举过程的方法,开始时将报数变量count置为1;用变量current表示当前报数的猴子的编号,初始时也置为1;变量。out记录出圈猴子数。当count=n时,对当前报数的猴子做出圈处理,即monkey[current]:=O,count:=0,out:=out

4、+1。然后继续往下报数,直到圈中只剩一只猴子为止(即out=m-1)。②用数组实现【算法分析】在组织数据时,也可以考虑只记录仍在圈中的猴子的情况。用一个线性表按编号由小到大依次记录圈中所有猴子的编号,每当有猴子出圈时,即从线性表中删除对应元素,表中元素减少一个。程序中用变量rest表示圈中剩余的猴子数,即线性表中元素的总数。③用单向循环链表实现【算法分析】结点的数据域为猴子的编号,指针域指向下一个猴子。报数实际上是计数,只要设一个计数器就可以了。当计数器由0变化到n时,删除该结点,计数器回0继续计数(或者用求余运算)。直到链表中剩下一个结点。线性表的应用4、一

5、元多项式加减运算【问题描述】给定一个一元n次多项式p和一个一元m次多项式Q,求它们的和与差。【算法分析】选方法②。遍历两个单链表.根据指数和系数进行相应的加减,生成一个新链表系数为0的结点删除掉(或不生成这种结点),输出该链表。特殊线性结构——栈栈(stack)是一种特殊的线性表,这种线性表限定其只能在表尾进行插入或删除数据元素。栈顶栈底a1a2an…进栈出栈栈的存储方式顺序存储:通常栈可以用顺序的方式存储,就是用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时设立指针top(称为栈顶指针)以指示栈顶元素的当前位置。1.用记录方式实现:Typestack

6、=recorddata:array[1..smaxsize]ofselement;top:0..smaxsize;end;2.用数组方式实现Typeatype=array[1..smaxsize]ofselement;Varstack:arraytype;top:integer;栈的存储方式链接存储:即链栈,目的是提高空间利用率,但编程复杂度提高了。typelink=^node;node=recorddata:element;next:link;end;Vartop:link;栈基本操作的实现顺序存储栈的操作栈的初始化Procedureinistack(va

7、rs:stack);begins.top=0end;判断栈空functionsempty(s:stack):boolean;beginsempty:=(s.top=0)end;入栈Procedurepush(vars:stack;x:selement);beginifs.top=smaxsizethenwriteln(‘overflow’)elsebegins.top:=s.top+1;s.data[s.top]end;栈基本操作的实现顺序存储栈的操作出栈Procedurepop(vars:stack);beginifsempty(s)thenwrite

8、ln(‘underflow’)else

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。