栈队列及其应用(精)

• ②用数组实现 • 【算法分析】 • 在组织数据时，也可以考虑只记录仍在圈中的猴子的情况。用一个
线性表按编号由小到大依次记录圈中所有猴子的编号，每当有猴子出 圈时，即从线性表中删除对应元素，表中元素减少一个。程序中用变 量rest表示圈中剩余的猴子数，即线性表中元素的总数。
• ③用单向循环链表实现 • 【算法分析】结点的数据域为猴子的编号，指针域指向下一个猴子。
可利用含m个元素的数组monkey来实现。利用元素下标代表猴子的编号，元素的值 表示猴子的状态，用monkeyEk]=l表示第k只猴子仍在圈中，monkeyEk-]=0则表示第 k只猴子已经出圈。 • 程序采用模拟选举过程的方法，开始时将报数变量count置为1；用变量current表示 当前报数的猴子的编号，初始时也置为1；变量。out记录出圈猴子数。当count=n时， 对当前报数的猴子做出圈处理，即monkey[current]：=O，count：=0,out：=out+1。 然后继续往下报数，直到圈中只剩一只猴子为止(即out=m-1)。
• begin if s.top=smaxsize then writeln(‘overflow’)
•
else begin s.top:=s.top+1; s.data[s.top]
end;
栈基本操作的实现
• 顺序存储栈的操作
ห้องสมุดไป่ตู้• 出栈
• Procedure pop(var s:stack);
• begin if sempty(s) then writeln(‘underflow’)
只猴子时， • 这只猴子就是大王。 • m和咒由键盘输入，打印出最后剩下的那只猴子的编号。 • 运行示例： • Input m，n：8 3 • The monkey king is no．7 • ①用数组实现 • 【算法分析】 • 在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，
报数实际上是计数，只要设一个计数器就可以了。当计数器由0变化 到n时，删除该结点，计数器回0继续计数(或者用求余运算)。直到链 表中剩下一个结点。
线性表的应用
• 4、 一元多项式加减运算
• 【问题描述】 • 给定一个一元n次多项式p和一个一元m次多项式Q，求它们的和与
差。
• 【算法分析】 • 选方法②。遍历两个单链表．根据指数和系数进行相应的加减，生
线性表的应用
• 2、 【问题描述】
• 已知线性表。和b中的数据元素按递增的顺序排列，现 要求将a和b归并为一个新的线性表c，c中的数据元素仍 按递增排列。
• ①用数组实现 • ②用链表实现
线性表的应用
• 3、 Joseph(约瑟夫)问题
• 【问题描述】 • m只猴子要选大王，选举办法如下：所有猴子按1…m编号围坐一圈，从第1号开始按 • 顺序1，2，…，n报数，凡报到竹的猴子退出到圈外，如此循环，直到圈内只剩下一
• 1.用记录方式实现：
• Type stack=record
•
data:array[1..smaxsize] of selement;
•
top:0..smaxsize;
•
end;
• 2.用数组方式实现
• Type atype=array[1..smaxsize] of selement;
• Var stack:arraytype;
线性表的应用
• 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；
• 链栈的基本操作
• 进栈算法
• procedure push(hs:link; x:element);
• begin
•
new(p); p^.data:=x; p^.next:=hs; hs:=p;
•
top:integer;
栈的存储方式
• 链接存储：即链栈，目的是提高空间利用 率，但编程复杂度提高了。
• type link=^node;
•
node=record
•
data:element;
•
next:link;
•
end;
• Var top:link;
栈基本操作的实现
• 顺序存储栈的操作
• 栈的初始化
成一个新链表系数为0的结点删除掉(或不生成这种结点)，输出该链 表。
特殊线性结构——栈
• 栈(stack)是一种特殊的线性表，这种线 性表限定其只能在表尾进行插入或删除数 据元素。
进栈 出栈
栈顶 an
…
栈底
a2
a1
栈的存储方式
• 顺序存储：通常栈可以用顺序的方式存储，就是用一组连 续的存储单元依次存放自栈底到栈顶的数据元素，同时设 立指针top（称为栈顶指针）以指示栈顶元素的当前位置。
• 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);
•
else s.top:=s.top-1; end;
• 取栈顶元素
• function gettop(s:stack):selement;
• begin
•
if sempty(s) then writeln(‘underflow’)
•
then gettop:=s.data[s.top]
• end;
栈基本操作的实现