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

线性表的应用,1、 【问题描述】 线性表a和b分别表示两个线性表，它们的数据元素类型相同，现要将b中存在而a中不存在的数据元素插入到线性表a中。设线性表a的长度与线性表b的长度之和不超过线性表a允许的最大长度。 【参考程序】 proceduIre union(var a：list；b：list)； begin n：=length(a)； for i：=1 to length(b)do begin getlist(b，i，x)；取线性表b中第i位上的数给T k：=loclist(a，x)；返回z在线性表a中的位置 if k=0 then begin inslist(a，n+1，x)；将z插入线性表a的末尾 n：=n+1； end； end； end；,线性表的应用,2、 【问题描述】 已知线性表。和b中的数据元素按递增的顺序排列，现要求将a和b归并为一个新的线性表c，c中的数据元素仍按递增排列。 用数组实现 用链表实现,线性表的应用,3、 Joseph(约瑟夫)问题 【问题描述】 m只猴子要选大王，选举办法如下：所有猴子按1m编号围坐一圈，从第1号开始按 顺序1，2，n报数，凡报到竹的猴子退出到圈外，如此循环，直到圈内只剩下一只猴子时， 这只猴子就是大王。 m和咒由键盘输入，打印出最后剩下的那只猴子的编号。 运行示例： Input m，n：8 3 The monkey king is no7 用数组实现 【算法分析】 在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkeyEk=l表示第k只猴子仍在圈中，monkeyEk-=0则表示第k只猴子已经出圈。 程序采用模拟选举过程的方法，开始时将报数变量count置为1；用变量current表示当前报数的猴子的编号，初始时也置为1；变量。out记录出圈猴子数。当count=n时，对当前报数的猴子做出圈处理，即monkeycurrent：=O，count：=0,out：=out+1。然后继续往下报数，直到圈中只剩一只猴子为止(即out=m-1)。,用数组实现 【算法分析】 在组织数据时，也可以考虑只记录仍在圈中的猴子的情况。用一个线性表按编号由小到大依次记录圈中所有猴子的编号，每当有猴子出圈时，即从线性表中删除对应元素，表中元素减少一个。程序中用变量rest表示圈中剩余的猴子数，即线性表中元素的总数。 用单向循环链表实现 【算法分析】结点的数据域为猴子的编号，指针域指向下一个猴子。报数实际上是计数，只要设一个计数器就可以了。当计数器由0变化到n时，删除该结点，计数器回0继续计数(或者用求余运算)。直到链表中剩下一个结点。,线性表的应用,4、 一元多项式加减运算 【问题描述】 给定一个一元n次多项式p和一个一元m次多项式Q，求它们的和与差。 【算法分析】 选方法。遍历两个单链表根据指数和系数进行相应的加减，生成一个新链表系数为0的结点删除掉(或不生成这种结点)，输出该链表。,特殊线性结构栈,栈(stack)是一种特殊的线性表，这种线性表限定其只能在表尾进行插入或删除数据元素。,栈的存储方式,顺序存储：通常栈可以用顺序的方式存储，就是用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时设立指针top（称为栈顶指针）以指示栈顶元素的当前位置。 1.用记录方式实现： Type stack=record data:array1smaxsize of selement; top:0smaxsize; end; 2.用数组方式实现 Type atype=array1smaxsize of selement; Var stack:arraytype; top:integer;,栈的存储方式,链接存储：即链栈，目的是提高空间利用率，但编程复杂度提高了。 type link=node; node=record data:element; next:link; end; Var top:link;,栈基本操作的实现,顺序存储栈的操作 栈的初始化 Procedure inistack(var s:stack); begin s.top=0 end; 判断栈空 function sempty(s:stack):boolean; begin sempty:=(s.top=0) end; 入栈 Procedure push(var s:stack; x:selement); begin if s.top=smaxsize then writeln(overflow) else begin s.top:=s.top+1; s.datas.top end;,栈基本操作的实现,顺序存储栈的操作 出栈 Procedure pop(var s:stack); begin if sempty(s) then writeln(underflow) else s.top:=s.top-1; end; 取栈顶元素 function gettop(s:stack):selement; begin if sempty(s) then writeln(underflow) then gettop:=s.datas.top end;,栈基本操作的实现,链栈的基本操作 进栈算法 procedure push(hs:link; x:element); begin new(p); p.data:=x; p.next:=hs; hs:=p; end; 出栈 function pop(var hs:link):element; begin if hs=nil then writeln(underflow) else begin pop:=hs.data; p:=hs; hs:=hs.next; dispose(p) end end;,括号匹配,【问题描述】 假设一个表达式由英文字母(小写)、运算符(+，一，*，)和左右小(圆)括号构成，以“”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“yes”，否则返回“NO。假设表达式长度小于255，左圆括号少于20个。 【算法分析】 将输人的字符串存储在c中(var c：string255)。 定义一个栈用于存放表达式中从左往右的左圆括号(maXn=20)。 var s：array1maxnof char； top：integer； 顺序(从左往右)扫描表达式的每个字符ci，若是“(“则让它进栈；若遇到的是“)”，则让栈顶元素出栈；当栈发生“下溢或当表达式处理完毕而栈非空时，都表示不匹配，返回“NO”；否则表示匹配，返回“YES”。,栈与递归,递归调用的过程，实质上是不断调用子过程或子函数的过程，由于递归调用一次，所有子程序的变量(局部变量、变参等)、地址在计算机内部都是用特殊的管理方法栈(先进后出)来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。 递归实现的条件： 边界条件：是所描述问题的最简单情况，它本身不再使用递归的定义。如求N!，当n=0时，f(n)=1，不再使用f(n-1)来定义。 递归关系：使问题向边界条件转化的规则。递归定义必须能使问题的规模越来越简单。,【例】折半查找,【问题描述】 设有”个数已经按从大到小的顺序排列，现在从键盘上输入x，判断它是否在这”个数中，如果存在，则输出所在位置，否则输出“no”。 【算法分析】 该问题属于数据的查找问题，常用方法有顺序查找和折半查找，当行个数排好序时，用折半查找方法的速度会大大加快。折半查找算法如下： 设有n个数，存放在数组a中，待查找数为x，用t指向数据的高端，用w指向数据的低端，mid指向中间； 若x=amid，输出“yes”； 若xamid，则到数据前半段查找：t不变，w=mid-1，计算新的mid值，并进行新的一段查找； 若tw，则没有查找到，输出“no”。,练习 7,Joseph(约瑟夫)问题 【问题描述】 m只猴子要选大王，选举办法如下：所有猴子按1m编号围坐一圈，从第1号开始按顺序1，2，n报数，凡报到n的猴子退出到圈外，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。 m和n由键盘输入，打印出最后剩下的那只猴子的编号。 运行示例： Input m，n：8 3 The monkey king is no7 用数组实现 【算法分析】 在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkeyEk=l表示第k只猴子仍在圈中，monkeyEk-=0则表示第k只猴子已经出圈。 程序采用模拟选举过程的方法，开始时将报数变量count置为1；用变量current表示当前报数的猴子的编号，初始时也置为1；变量。out记录出圈猴子数。当count=n时，对当前报数的猴子做出圈处理，即monkeycurrent：=O，count：=0,out：=out+1。然后继续往下报数，直到圈中只剩一只猴子为止(即out=m-1)。,约瑟夫的新问题,约瑟夫的新问题 【问题描述】 将1m这m个自然数按由小到大的顺序沿顺时针方向围成一圈。以s为起点，先沿顺时针方向数到第n个数就出圈，然后沿逆时针方向数到第k个数再出圈；再沿顺时针方向数到第n个数就出圈，然后沿逆时针方向数到第k个数再出圈这样按顺时针方向和逆时针方向不断循环，直到全部数都出圈为止。请打印先后出圈的数的序列。 输入,m，s，n，k。m不超过1000。 输出：先后出圈的数的序列，每个数之间有1个空格。 样例输入：8 1 3 2 样例输出：3 l 5 2 7 4 6 8 (解释：先从1开始沿顺时针方向数到3，所以3先出圈；再从2开始沿逆时针方向数到1，所以1出圈；再从2开始沿顺时针方向数到5，所以5出圈，再从4开始沿逆时针方向数到2，所以2出圈),【算法分析】 解决这个问题可以有两种思路：第一种思路用数组来模拟，用一指针来指示当前的数字，这样就又有两种办法：一是可以给每一数字做一个标记，来判断它是否已经出圈，这样可以省去移动数组元素的过程，但指针须一个一个地移动，速度较慢。二是每次都把指针直接指向下一个要出圈的数字，并将其输出并删除，这样做需要大量地移动数组元素，造成耗时，这两种方法都需要注意对于指针出界的判断； 第二种思路是使用双向循环链表。这是最简单也是最有效的方法，既不用大量地移动数组元素，也不用判断数组出界，可以用最直接的模拟来实现。,练习 4,特殊线性结构队列,队列(queue)是另一种特殊的线性表，限定只能在表的一端进行插入，在表的另一端进行删除。,队列的存储方式,（1）顺序存储 type queue=record data:array11maxsize qelement; front,rear:0qmaxsize; end; (2)链接存储 type queueptr=queuenode； queuenode=record data：elemtp； next：queueptr； end； linkedquetp=record front，rear：queueptr； end；,队列的基本操作,、初始化iniqueue(q) procedure iniqueue(var q：queue)； begin qfront：=0； qrear：=0 end； 判队列空qempty(q)： function qempty(q：queue)：boolean； begin qempty=(qfront=qrear) end； 判队列满qfull(q)： function qempty(q：queue)：boolean； begin qfull：=(qrear=qmaxsize) end； 入队enqueue(q，x)： procedure enqueue(var q：queue；x：qelement)； begin if qfull(q) then writeln(overflow) else begin qrear：=qrear+1; qdataqrear：=x end； end；,队列的基本操作,出队delqueue(q，x) procedure delqueue(var q：queue；X：qelement)； begin if qempty(q) then writeln(underflow) else begin qfront：=qFront+1； x：=qdataqfront ; end； end； 取队头元素gethead(q) function gethead(q：queue)：qelement； Var m：0qmaxsize； begin if qempty(q) then writeln(underflow) else begin m：=qfront+1； gethead：=qdatam end； end； 求队列长度lenqueue(q) function lenqueue(q：queue)：integer； begin lenqueue：=qrear - qfront； end；,队列的基本操作,入队enqueue(q，x) procedure enqueue(var q：linkedquetp；x：elemtp)； begin new(qRearnext)； qrear：=qrearnext； qReardata：=x； qRearnext：=nil； end； 出队delqueue(q) procedure dequeue(var q：linkedquetp)； var P：queueptr； begin if qempty(q) then error(the queue is empty!) else begin P：=qfront； qfront：=qFrontnext； dispose(p)； end； end；,循环队列,在所表示的队列情况下，若另有元素a。需人队，这时rear=5，已满足“上溢”条件，无法实现人队操作，但实际上队列中有三个空位，这种现象称为“假溢出”。当“假溢出”时，应该将队列中现有元素向队头方向移动，这显然需要花费一定的时间。如何避免“假溢出”现象呢?设想把q1接在qm之后形成循环表，当删除a1之后插入am+1，时，不移动队列中现有元素，而直接把它加到q1的位置上去。这样实际上把