栈、队列及其应用.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)是一种特殊的线性表，这种线性表限定其只能在表尾进行插入或删除数据元素。栈顶栈顶栈底栈底a1a2an进栈进栈出栈出栈栈的存储方式顺序存储：通常栈可以用顺序的方式存储，就是用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时设立指针top（称为栈顶指针）以指示栈顶元素的当前位置。1.用记录方式实现：Type stack=record data:array1.smaxsize of selement;top:0.smaxsize;end;2.用数组方式实现Type atype=array1.smaxsize 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”。练习练习 7Joseph(约瑟夫约瑟夫)问题问题 【问题描述问题描述】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)是另一种特殊的线性表，限定只能在表的一端进行插入，在表的另一端进行删除。a1a2a3an出队列出队列入队列入队列队列的存储方式（1）顺序存储）顺序存储type queue=record data:array1.1maxsize qelement;front,rear:0.qmaxsize;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 beginqfront：=qFront+1；x：=qdataqfront;end；end；取队头元素gethead(q)function gethead(q：queue)：qelement；Var m：0qmaxsize；beginif 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的位置上去。这样实际上把队列看作一个环，这种队列称为循环队列。在循环队列中为了区分队空和队满两种情况，作这样的约定：少用一个元素空间，头指针指示的存储单元永远是空闲的，当头指针和尾指针指向同一元素时，作为空队，即。Front=rear时为空队；把尾指针从后面追上头指针时，作为队满的标志，即rear+1=front时队满。假定循环队列以顺时针方向伸长，那么，每加人一个元素，尾指针向顺时针方向移动一个位置，即real：=(rear+1)mod qmaxsize；每删除一个元素时，头指针也向顺时针方向移动一个位置(不发生溢出时)，即front：=(front+1)mod qmaxsize.舞伴问题【问题描述问题描述】假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。【算法分析算法分析】先人队的男士或女士是先出队配成舞伴。因此该问题具有典型的先进先出特性，可用先人队的男士或女士是先出队配成舞伴。因此该问题具有典型的先进先出特性，可用队列作为算法的数据结构。队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的名字，他(或她或她)将是下一轮舞曲开始时第一个可获得舞伴的人。将是下一轮舞曲开始时第一个可获得舞伴的人。样例输入：样例输入：4 2男男4人，女人，女2人人 样例输出：样例输出：1 1 2 2 3 1 4 2