基级班讲稿线性表、栈

1、1数据结构线性表、栈、队列2对于程序设计来说： 编程语言是工具； 数据结构是基础； 算法设计是方法。程序=数据结构+算法3数据结构数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 数据结构的内涵“操作”的对象：数据。数据与数据间的关系。针对数据的基本操作。数据结构的形式定义 data _ structure=(D,S)D:数据元素的有限集；S:上关系的有限集；4数据结构相关概念数据(data) 计算机科学中指所有能输入到计算机中并被程序处理的符号总称。例如数值、字符

2、、图像、声音都属于数据的范畴。数据元素(data element) 是数据的基本单位 ，在程序中作为一个整体进行考虑。有时一个数据元素有若干数据项。数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。 通常，一个待求解问题中的数据元素属于一个数据对象。5数据结构：相互存在特定关系的数据元素集合。 数据元素间的关系称为结构，常见的结构有线性结构、树形结构和网状结构。数据类型：一个值的集合和定义在这个值上的一组操作的总称。6逻辑结构图例数据元素间的关系结构名特性数据元素属于或不属于集合集合结构松散；用其他结构代替数据元素一个对一个线性结构结构简单数据元素一个对多个树形结

3、构结构复杂数据元素多个对多个图结构结构复杂前述“关系”即结构(sructure)，指数据之间的逻辑关系，又称逻辑结构。7物理结构 1 顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 逻辑上关联的数据元素，物理存储结构中相邻。 2 链式结构 ：借助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系 。 逻辑上关联的数据元素，物理存储结构中不一定相邻。 用高级语言中的数据类型(数组、动态变量)来描述逻辑结构、物理结构密切相关算法的设计取决于所选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。8数据结构上的基本操作插入删除更新查找排序(线性结构)遍历9 线

4、性结构线性表、栈、队列、串、数组、广义表非线性结构树、图由n个数据元素的有限序列除头元素外，每个元素都有一个前趋除尾元素外，每个元素都有一个后继线性结构10线性表线性表是最常用且最简单的一种数据结构，它是由有限个数据元素组成的有序集合。每个数据元素有一个数据项或者含多个数据项。线性表具有如下结构特征：均匀性：即同一线性表的各数据元素的数据类型一致且数据项数相同。例如上表中，每一个数据元素（学生）包括姓名、学号、性别、年龄和健康状况五个数据项，每一个数据项的数据类型是相同的，姓名、性别和健康状况可采用字符串类型，学号和年龄可采用整数类型。；有序性：表中数据元素之间的相对位置是线性的，即存在唯一的

5、“第一个”和“最后一个”数据元素。除第一个和最后一个外，其它元素前面均只有一个数据元素（直接前趋）和后面均只有一个数据元素（直接后继）。例如，我们可以采用记录数组存储上表，数组下标反映了表中数据元素之间的线性关系。11线性表的两种存储方式1、顺序存储结构顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）十位移来访问每一个元素。2、链式存储结构 在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。采用动态指针。数组元素和动态变量的类型一般采用记录类型，数据域存储结点的值，指针域存储后

6、件的数组下标或地址。最后一个结点的指针域的值为0或nil。12数组的插入与删除1234567891011126.5数组的插入与删除均需要移动后面的元素插入：删除：12345678910111212345678910111212345678910111213链表的插入与删除无需移动任何元素14线性表的具体实现顺序存储结构用数组类型： list: array 1.maxlen of elemtp;链式存储结构 用指针类型 和 动态变量： pointer = nodetype ; nodetype = record data : elemtp ; next : pointer ; end;15顺序存

7、储与链式存储操作的对比顺序存储链式存储特点逻辑相邻的元素其物理位置也相邻逻辑相邻的元素其物理位置不一定相邻特点优点随机存取i 元素 o(1)查找X 和 第i元素需遍历整个链表 o(n)缺点缺点插入、删除需移动大量元素 o( n)插入、删除不需移动大量元素 o(1)优点缺点预先分配大空间不需预先分配空间优点缺点表容量难以扩充表容量扩充灵活优点优点操作简单操作较复杂缺点16 限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(last in first out )线性表 (LIFO结构) 栈顶表尾 栈底表头栈17通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放栈中的表目，并用一个

8、变量t指向当前栈顶（如下图）。18栈的实现（一）Const m=栈表目数的上限；Type stack=array1.m of stype； 栈类型Var s：stack；栈 top： integer； 栈顶指针栈sm1top19栈的实现（二）const m=栈表目数的上限； type stack=record elem: array1.m of elemtp; top:0.m; 栈顶指针 end; Var s：stack；栈TOP=0 表示栈空Top=m 表示栈满20栈的基本操作栈的基本操作包括四种初始化（init）、进栈（push）、出栈（pop）、读取栈顶元素（top）。211） 过程in

9、it(s,t) 初始化procedure init; begin t:=0; end;2)、过程push(x)往栈s中压入一个值为x的数据：procedure push (var s：stack； x：stype； var t：integer)； begin if t=m then writeln(overflow) 上溢 else begin tt+1；stx；end；else x入栈end；Push223）函数pop(s，t)从栈中弹出一个表目 function pop (var s：stack； var t：integer)：stype； begin if t=0 then writel

10、n (underflow) 下溢 else begin popst； tt-1； end；else 栈顶元素出栈 end；pop4）函数top(s，t)读栈顶元素 function top (s：stack； t：integer)：stype； begin if t=0 then writeln (stack empty) else topst； 返回栈顶元素 end；top23栈的应用1、（1998） 栈S初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是_

11、(A) 5,4,3,2,1 (B) 2,1 (C) 2,3 (D) 3,424以下哪一个不是栈的基本运算( ) (NOIP7)A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈一个栈的输入顺序为1、2、3、4、5，下列序列中可能是栈的输出序列是 ( )。 (A)54312 (B)2415 (C)21543 (D)1253若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1是n，则Pi是( ) (NOIP7)A)i B)n-1 C)n-i+1 D)不确定4、设有一个顺序栈S，元素S1, S2, S3, S4, S5, S6依次进栈，如果6个元

12、素的出栈顺序为S2, S3, S4, S6, S5, S1，则顺序栈的容量至少应为多少？ A）3 B) 4 C) 5 D) 65、向顺序栈中压入新元素时，应当（ ）。A先移动栈顶指针，再存入元素 B先存入元素，再移动栈顶指针C先后次序无关紧要 D同时进行25编程2 、出栈序列 问题描述：N个不同元素按一定的顺序入栈，求不同的出栈序列数目。例如：如果n=3，入栈的顺序为：1、2、3。那么共有5种出栈方法：1 2 33 2 11 3 22 1 32 3 126【问题分析】：设f（n）为n个元素的不同出栈序列数目。容易得出：f（1）=1；f（2）=2。第n个元素可以第i（1=i=n）个出栈，前面已出

13、栈有i-1个元素，出栈方法：f（i-1）；后面出栈n-I 个元素，出栈方法为：f（n-i）。所以有：F(n)= 约定： F(0)=1 F(i)=27var n,i,j:longint; f:array0.1000 of longint;begin read(n); f0:=1;f1:=1;f2:=2; for i:=3 to n do begin fi:=0; for j:=1 to i do fi:=fi+fj-1*fi-j; end; writeln(fn);end.281、表达式括号匹配(t1.pas)假设一个表达式有英文字母（小写）、运算符（+，*，/）和左右小（圆）括号构成，以“”作

14、为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。表达式长度小于255，左圆括号少于20个。【输入文件】 输入文件t1.in包括一行数据，即表达式，【输出文件】 输出文件t1.out包括一行，即“YES” 或“NO”。【样例输入1】2*(x+y)/(1-x)【样例输出1】 YES【样例输入2】 (25+x)*(a*(a+b+b)【样例输出2】 NO29var a:array1.300of char;栈 s:string;表达式 i,j,l,k,t,tt:integer; procedure try(ss:char); begin if

15、 t=0 then begin inc(t); at:=ss;exit;end; if (ss=)and(at=() then（左右括号配对，出栈） begin dec(t); exit; end; inc(t); at:=ss; end;30beginassign(input,stack.in);reset(input);assign(output,stack.out);rewrite(output); read(s); 读入表达式 l:=length(s); 表达式的长度 t:=0; 初始化栈为空 i:=1; 从第一个字符扫描表达式 while (i=l)and(si ) do begin

16、 if (si=()or(si=) then 如果遇到括号，进行判断 try(si); inc(i); end; if t=0 then writeln(YES)else writeln(NO);栈为空，区配 close(input); close(output);end.31栈的应用表达式求值输入一个表达式，该表达式含有“+”、“-”、“*”、“/”、“（”、“）”和操作数输入以结束。输出该表达式的值。分析：由于一个表达式含操作数、运算符和括号，因此只能采用字符串类型输入，而字符是不能进行数值计算的。在这种情况下，计算机又如何计算表达式的值呢。一般方法是：中缀表达式等价的后缀表达式计算后缀表

17、达式的值32中缀表达式和后缀表达式的特征中缀表达式：中缀表达式与通常的表达式一样，运算符位于两个操作之间，计算规则为先括号内、后括号外；无括号或同层括号内先*、/、后+、-；同级运算按由左至右顺序进行。为了计算方便，输入的中缀表达式串常以为结束标志。例如3*(52)+7后缀表达式：后缀表达式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。为了计算方便，以.为操作数的结束标志，以为后缀表达式的结束标志。例如3*（5-2）+7 对应的后缀表达式为 352-*7+。后缀表达式是简化运算顺序的一种表达式。33 中缀表达式的运算规则

18、比较多，包括优先级、左右次序和括号；尤其是括号可以改变优先顺序，这就只能在计算的每一步，用肉眼去扫描、观察和比较整个表达式中谁的优先级高，就先计算那部分。但用计算机去做就很麻烦，而且效率不高。所以，计算机科学中是把中缀表达式先转换成后缀表达式，在利用计算机来计算后缀表达式的值。后缀表达式又称“逆波兰式”，在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后顺序进行，整个计算过程仅需一遍扫描即可完成。中缀表达式转化成后缀表达式的规则是：只要将每个运算符移到它的两个运算对象的后面，再删去所有括号，便得到与之等价的后缀表达式34栈的应用-中缀转后缀输入一个中缀表达式，编

19、程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由（加）、（减）、（乘）、（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。以下是一个运行实例。输入：X+A*（Y-B）-Z/F输出：XAYB-*+ZF/-35设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号

20、#号，并在表达式的末尾加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级，此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。X+A*（Y-B）-Z

21、/F36以下程序中的数组f用来存放运算符之间的优先级关系，1()表示前面的运算符优先于后面的运算符，-1(-*/(ERROR#ERROR=P2P1X+A*（Y-B）-Z/F37上述算法还可用于求一个表达式的值和判断一个表达式是否有错等等。program ex2;const max=100; op_set:set of char=+,-,*,/;运算符集合 letter:set of char=A.Z;运算数集合var expression,result:string;中缀表达式，后缀表达式，字符串procedure scan(expression:string);本过程完成中缀的扫描及到后缀的

22、转换 var i,top1,top2:integer;操作数栈和操作符栈的栈顶指针 ovs:array 1.max of stringmax;操作数栈 ops:array 1.max of char;操作符栈 f:array#./,#./ of shortint;数组f用来存放运算符之间的优先级关系 38begin f+,+:=1; f+,-:=1; f+,*:=-1; f+,/:=-1; f+,(:=-1; f+,):=1; f+,#:=1; f-,+:=1; f-,-:=1; f-,*:=-1; f-,/:=-1; f-,(:=-1; f-,):=1; f-,#:=1; f*,+:=1;

23、f*,-:=1; f*,*:=1; f*,/:=1; f*,(:=-1; f*,):=1; f*,#:=1; f/,+:=1; f/,-:=1; f/,*:=1; f/,/:=1; f/,(:=-1; f/,):=1; f/,#:=1; f(,+:=-1;f(,-:=-1;f(,*:=-1; f(,/:=-1; f(,(:=-1; f(,):=0; f(,#:=2; f),+:=2; f),-:=2; f),*:=2; f),/:=2; f),(:=2; f,):=2; f,#):=2;f#,+:=-1;f#,-:=-1;f#,*:=-1; f#,/:=-1; f#,():=-1; f#,:=

24、2; f#,#:=0;expression:=expression+#;表达式的末尾放一个“#” ops1:=#; 操作符栈先放入一个“#” top1:=0;初始化操作数栈 top2:=1; 操作符栈中放入一个“#”39for i:=1 to length(expression) do在中缀表达式的长度范围内执行循环 begin if expressioni in letter 如果扫描到的中缀表达式的内容是操作数 then begin top1:=top1+1; ovstop1:=expressioni 操作数进栈 end else begin while fopstop2,expressi

25、oni=1 dobegin ovstop1-1:=ovstop1-1+ovstop1+opstop2; top1:=top1-1; top2:=top2-1 end; 若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级。if fopstop2,expressioni=0 then top2:=top2-1 else begin top2:=top2+1; opstop2:=expressioni end;若当前运

26、算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。end end; result:=ovs1 扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。end;40beginmain write(Input a expression:); readln(expression); scan(expression); writeln(The result is: ,result)end.测试输入：A*(X+Y)/(B-Z)输出：AXY+*BZ-/41将中缀表达式转换为等价的后缀表达式(2

27、)在中缀表达式中，运算符出现次序与计算顺序不一致，实际计算顺序不仅要看它的出现次序，还要受运算符的优先级和括号的影响。如果把一个中缀表达式中所有的计算顺序都按计算规则用嵌套括号的形式表示出来，其转换过程就要清楚的多。例如中缀表达式3*(52)+7可以改写成（(3*(52)+7）。这时可以看出，只要将每对括号中的运算符移到相应括号的后面，再删去所有括号，便得到与之等价的后缀表达式352*7+ 。为了将中缀表达式转换为等价的后缀表达式，需要从左至右扫描中缀表达式，并使用一个栈s2来存放中缀表达式中的开括号（和暂时不能参与计算的运算符，显然s2栈的元素类型为char。为了方便表达式值的计算，在转换后

28、的后缀表达式中，每一个操作数尾添加一个.。例如计算3*(52)+742具体算法如下： var a，e：string； 后缀表达式和中缀表达式 s2：array1.100of char； 栈，存放暂不参与计算的运算符 t，i：integer； 栈顶指针、中缀表达式的字符指针 w：char； begin 读中缀表达式e；a； 后缀表达式初始化为空 i1；t0； 从中缀表达式的第一个字符开始分析，栈空 while ei do 由左而右扫描处理中缀表达式的每一个字符 begin case eiof 09：begin 操作数进入后缀表达式 while ei in0.9 do begin aa+ei； i

29、i+1； end；while aa+；ii-1； 添加操作数的结尾标志 end；0943 ( ： push (s2（， t)； （入栈 ) ： begin s2栈中栈顶至(间的所有运算符相继出栈，进入后缀表达式 wpop(s2，t)； while w( do begin aa+w；wpop(s2，t)； end；while end；） +，-： begins2栈中，栈顶至(前的所有运算符相继出栈，进入后缀表达式，ei进入s2栈 if t0 then begin wtop (s2，t)； while w( do begin aa+w；wpop (s2，t)； if t=0 then break

30、else wtop (s2，t)； end；while end；then push (s2，ei，t)； end；+，- 44*，/： begins2栈中栈顶至第1个+或-前的所有运算符相继出栈，进入后缀表达式，ei进入s2栈 if t0 then begin wtop (s2，t)； while (w=*) or (w=/)do begin aa+w； wpop (s2，t)； if t=0 then break else wtop (s2，t)； end；while end；then push(s2，ei，t)； end；*，/ end；case ii+1； 准备扫描处理中缀表达式的下一个

31、字符 end；while while t0 do s2栈中的运算符相继出栈，进入后缀表达式 begin aa+pop (s2，t)； end；while aa+； 输出后缀表达式a； end； 算法结束45栈的应用2-计算后缀表达式所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。例如 3*（5-2）+7 对应的后缀表达式为 352-*7+ 其中为后缀表达式的结束标记，为操作数的结束符。 352-*7+ =33*7+ =97+ =16 输入： 后缀表达式A（假定A合乎文法，不需判错）；

32、输出： 表达式的值。46方法：利用栈结构算法分析：假设后缀的表达式为A，操作数和计算结果存放在栈S中，s的类型为integer。从左向右处理A中的每一个字符：如果遇到一个操作数，就送入栈s中；如果遇到一个运算符，就从栈s中取出栈顶的两个操作数进行计算，然后将计算结果重新压栈。直到最后一个运算符处理结束，这时栈s顶的元素即是计算结果。例如计算后缀表达式352-*7+的值47352-*7+48const m=100;type stack=array1.m of integer; 定义栈类型var s:stack; 栈 a:string; 后缀表达式，字符串 t,i,j,k,len:integer;

33、 t栈顶指针；i后缀表达式的字符指针；k、j操作数值procedure push(x:integer);进栈 begin t:=t+1; st:=x; end;function pop:integer;出栈 begin pop:=st; t:=t-1; end;49begin readln(a); 读入后缀表达式 len:=length(a); 后缀表达式的长度 i:=1; 后缀表达式字符指针初始化 t:=0; 栈初始化 while i=len do 处理后缀表达式，循环直至结束 begin case ai of 0.9:begin k:=0; while ai. do begin 从s中取出

34、一个完整的操作数k k:=10*k+ord(ai)-48; ord(0)=48 i:=i+1; end; push(k);把操作数k压栈 end; +:push(pop+pop); 从栈s中取出栈顶的两个数进行加法运算，然后将结果在压栈50 -:begin 从栈s中取出栈顶的两个数进行减法运算，然后将结果在压栈 j:=pop; push(pop-j); end; *:push(pop*pop); 从栈s中取出栈顶的两个数进行乘法运算，然后将结果在压栈 /:begin 从栈s中取出栈顶的两个数进行除法运算，然后将结果在压栈 j:=pop; push(pop div j); end;end;cas

35、e i:=i+1; end;while writeln(pop); 取出栈顶元素，即时表达式的最后结果end.51栈的其他应用之-数制转换将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)866/8=8 余 28/8=1 余 01/8=0 余 1结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：521)、用递归算法把任一给定的十进制正整数（=32000）转换成八进制数输出，程序如下：var m:integer;procedure tran(n:integer); 递归过

36、程 var k:integer; begin k:=n mod 8; n:=n div 8; if n0 then tran(n); write(k:1) end;begin 主程序 write(input m:); readln(m); write(m,=(); tran(m); writeln()8); readln;end.输入：m=765 下划线表示输入输出：765=（1375）853递归在计算机中的实现计算机执行递归算法时，是通过栈来实现的。具体说来，就是在（递归过程或递归函数）开始运行时，系统首先为递归建立一个栈，该栈的元素类型（数据域）包括值参、局部变量和返回地址；在每次执行递归

37、调用语句时之前，自动把本算法中所使用的值参和局部变量的当前值以及调用后的返回地址压栈（一般形象地称为“保存现场”，以便需要时“恢复现场”返回到某一状态），在每次递归调用结束后，又自动把栈顶元素（各个域）的值分别赋给相应的值参和局部变量（出栈），以便使它们恢复到调用前的值，接着无条件转向（返回）由返回地址所指定的位置继续执行算法。具体到上面的例1中，当遇到递归调用tran(n)时，系统首先为后面的递归调用建立一个含有3个域（值参n，局部变量k和一个返回地址）的栈；在每次执行递归调用tran(n)前，系统自动把n和k的当前值以及write(k:1)语句的开始位置（即调用结束后的返回地址）压栈；在每

38、次执行到最后的end语句（即一次递归调用结束）后，又自动把栈顶的与n和k对应的值分别赋给n和k（出栈），接着无条件转向write(k:1)语句的开始位置继续向下执行程序。54递归转换为非递归设P是一个递归算法，假定P中共有m个值参和局部变量，共有t处递归调用P的语句，则把P改写成一个非递归算法的一般规则为：定义一个栈S，用来保存每次递归调用前值参和局部变量的当前值以及调用后的返回地址。即S应该含有m+1个域，且S的深度必须足够大，使得递归过程中不会发生栈溢出。定义t+2个语句标号，其中用一个标号标在原算法中的第一条语句上，用另一个标号标在作返回处理的第一条语句上，其余t个标号标在t处递归调用的

39、返回地址，分别标在相应的语句上。把每一个递归调用语句改写成如下形式：把值参和局部变量的当前值以及调用后的返回地址压入栈；把值参所对应的实在参数表达式的值赋给值参变量；无条件转向原算法的第一条语句；在算法结束前增加返回处理，当栈非空时做：出栈；把原栈顶中前m个域的值分别赋给各对应的值参和局部变量；无条件转向由本次返回地址所指定的位置；增设一个同S栈的成分类型（元素）相同的变量，作为进出栈的缓冲变量，对于递归函数，还需要再增设一个保存函数值中间结果的临时变量，用这个变量替换函数体中的所有函数名，待函数结束之前，在把这个变量的值赋给函数名返回。在原算法的第一条语句之前，增加一条把栈置空的语句。对于递

40、归函数而言，若某条赋值语句中包含两处或多处递归调用（假设为n处），则应首先把它拆成n条赋值语句，使得每条赋值语句只包含一处递归调用，同时对增加的n-1条赋值语句，要增设n-1个局部变量，然后按以上六条规则转换成非递归函数。552)递归过程改写成非递归过程。procedure tran(n:integer); 非递归过程 label 1,2,3; 因为只有1处递归调用，所以定义t+2=3个标号 type node=record 定义栈的成分类型，因为值参和局部变量共2个，所以m+1=3个域 n:integer; 值参n 的域 k:integer; 局部变量k的域 r:integer; 返回地址的

41、域 end; stack=record 定义一个栈类型，包括数据域（一个数组）和一个栈顶指针域 vec:array1.7 of node; 32000以内的十进制正整数转换成八进制数，不会超过七位数，数组元素类型为node类型 top:integer; 栈顶指针 end; var s:stack; 定义栈变量 x:node; 进出栈的缓冲变量 k:integer; 原来的局部变量 procedure push(var s:stack;x:node); 进栈过程，注意s 一定要定义成变量型参数 begin 因为栈的变化要带出过程 if s.top=7 then begin write(up-ov

42、erflow);exit;end else begin s.top:=s.top+1;s.vecs.top:=x;end; end;56 procedure pop(var s:stack;var x:node); 出栈过程，都要定义成变量型参。一方面出栈的元素存放在x中要带出过程，另外栈顶指针也变化了，所以s也要定义成变量型参 begin if s.top=0 then begin write(down-overflow);exit;end else begin x:=s.vecs.top;s.top:=s.top-1;end; end; begin s.top:=0; 按照第6条 1:k:

43、=n mod 8; 按照第2条的红色语句 n:=n div 8; if n0 then begin 按照第3条，3个步骤，本题不需要第（2）小句 x.n:=n; x.k:=k; x.r:=2; push(s,x); （1） goto 1; （3） end; 2:write(k:1); 按照第2条的蓝色语句 3:if s.top0 then begin 按照第4条，3个步骤 pop(s,x); （1） n:=x.n; k:=x.k; （2） goto 2; （3） end; end; 建议：单步跟踪各个变量，观察理解过程57 小结思考 从以上可以看出，递归算法简单直观，是整个计算机算法和程序设计

44、领域一个非常重要的方面，必须熟练掌握和应用它。但计算机的执行过程比较复杂，需要用系统栈进行频繁的进出栈操作和转移操作。递归转化为非递归后，可以解决一些空间上不够的问题，但程序太复杂。所以，并不是一切递归问题都要设计成非递归算法。 586、求N阶乘（N！=1*2*3*N,N20）；用递归算法用非递归算法1）、用递归算法求N阶乘（N！=1*2*3*N,N0 then begin n:=atop; 做返回处理 top:=top-1; goto 2; 转向返回地址 end; f:=f1; 赋值 end;60注意 对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程

45、序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错 61队列 62队列 在日常生活中，无论是购物、订票或候车都有可能要排队。排队所遵循的原则是“先来先服务”，后来者总是加到队尾，排头者总是先离开队伍。 队列就是从日常生活中的排队现象抽象出来的。队列是一种先进先出(FIFO)的线性表允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。a1 a2 a3 a4 an 出队列入队列队列头队列尾队列的删除和插入分别称为出队和入队。 fr63队列的存储结构队列可以采用顺序存储结构和链式存储结构我们一般采用顺序存储结构来定义队列：Const m=队列元素的上限；

46、Type equeue=array1m of qtype； 队列的类型定义Var q：equeue； 队列r，f：integer； 队尾指针和队首指针队列空: r=f时,队列非空：r0) and (x0) and (yw;直至队空为止 end;77begin fillchar(pic,sizeof(pic),0); num:=0; fillchar(h,sizeof(h),0); assign(input,a.in);reset(input); assign(output,a.out);rewrite(output); readln(m,n); for i:=1 to m do 按照行，以字符

47、串的形式读入矩阵，如果读入的 是0,则相应矩阵数组元素置为0,否则，为1 begin readln(s); for j:=1 to n do if sj=0 then pici,j:=0 else pici,j:=1; end; for i:=1 to m do for j:=1 to n do if pici,j=1 then doing(i,j);在矩阵中寻找细胞 writeln(num); close(input); close(output);end.78广度优先搜索从初始结点开始，应用算符生成第一层结点，检查目标结点是否在其中出现，若没有，再用算符将第一层结点逐一扩展，得第二层结点，

48、逐一检查第二层中是否包含目标结点。若没有，依次扩展、检查直到发现目标结点为止。这就是所谓的广度优先搜索。用队列的数据结构来存储搜索过程中产生的结点，取队头元素扩展，产生的结点插入队尾。abcdefjk79算法框架 在广度优先搜索中，我们将扩展出的状态存贮在一个称为list的数组里，数组容量为listmax。list数组采用“先进先出”的队列结构，设两个指针open、closed，分别是队尾指针和队首指针。其中list1cloed-1 存贮已扩展状态（即这些状态的儿子状态已扩展出）；listclosedopen 存贮待扩展状态（即这些状态的儿子状态尚待扩展）。当open=closed时，则表示队

49、列空；当open=listmax时， 则表示队列满(见上图)。List数组的元素为状态。 type node=状态的数据类型 var list：array1listmaxof node ； 队列 closed，open：integer； 队首指针和队尾指针80广度优先搜索的算法流程如下： open1；closed0； 初始状态进入队列 listopen初始状态； while (closedopen)and(openlistmax)do begin 若队列非空且未溢出，则移出队首状态，扩展其子状态 closedclosed+1； expand(listclosed)； 扩展队首状态的所有子状态

50、end；while if openlistmax 若扩展出的状态数超出list表的容量上限 then输出内存溢出信息 else找到了初始状态所能到达的所有状态list1listopen；81采用广度优先搜索的试题一般有两种类型：求初始状态所能到达的所有状态求初始状态到某目标状态的最短路径试题要求不同，扩展子状态的方式(expand过程)也不同82在求初始状态所能到达的所有状态时，扩展子状态的方式(expand过程)如下 procedure expand(q：node)； 扩展q状态的所有子状态 var successor：node； begin for i取遍所有的算符 do if openl

51、istmax then 若队列未满 begin 算符i作用于q状态产生一个子状态successor； if successor满足约束条件 then begin openopen+1；listopensuccessor； 子状态successor 入队 end；then end；then end；expand 显然，初始状态可达的状态个数不应超过listmax个。若超过，则只能求出其中listmax个。 1、求初始状态所能到达的所有状态83我们在应用上述算法框架解题时，应考虑如下几个因素：定义状态，即如何描述求解过程中每一步的状况和状态间转换的方法；搜索范围，即如何设计算符的值域，即expan

52、d过程中循环变量的初值和终值；约束条件，即当前扩展出的子状态应满足什么条件方可进入队列；由于存储所有状态的队列采用了静态数组，因此广度优先搜索的空间效率比较低，容易发生内存溢出。为此我们不妨从以下几个方面考虑优化：不再生成以重合状态为根的子树。但判断所有子状态是否重复的代价相当大，一般在产生重复状态的概率较大时使用此方法。状态尽可能占用空间少，既易于扩展子状态的计算，又方便对重合状态的判断；队列可改用指针类型，以便及时释放无用状态，回收内存； 84求最短路径的广度优先搜索算法，在扩展状态时有如下不同之处：每个状态需要设立父指针father，因为每扩展出一个子状态succesor，需通过其fat

53、her指针确认其与listclosed的父子关系。为此，状态的数据类型可按如下方式定义 type node=recodestate：状态的数据类型；father：integer； 父指针，指向父状态在list队列中的下标 end；需判别扩展出的子状态succesor是否为目标状态。若是目标状态，则从succesor的father指针出发，递归输出初始状态至该状态的最短路径，并退出程序；如果产生重复子状态的概率很大，则在生成子状态succesor后判别其是否重复于已扩展状态(list1listclosed)：若不重复，succesor入队；否则由于重合在两表中的状态是位于successor的上层

54、或同一层，其路径代价必小于或等于succesor的路径代价，因此不再重复以successor为根的子树，避免了多余子状态的计算。但如果产生重复子状态的概率小，则不必进行重复判断，因为对所有子状态重复判断的代价是相当大的。2、计算初始状态到目标状态的最短路径85在求最短路径时，扩展子状态的方式(expand过程)如下procedure expand(q：node)； var successor：node； tot：integer； begin for i取遍算符的所有可能值 do if openlistmax then begin 算符i作用于qstate产生子状态successor； if s

55、uccessor满足约束条件then begin successorfatheclosed ； 设置子状态successor的父指针 if successor是目标状态then begin tot0； 路径代价初始化 print(successor)； 递归输出初始状态至状态successor的路径 输出路径代价tot-1； halt； 退出程序 end；then if successor.State与list1.statelistcloed.State各不相同 then begin 若产生重复子状态的概率小时，则避免使用该判断 openopen+1；listopensuccessor； 状态

56、successor入队 end；then end；then end；then end；expand86其中print的过程说明为： procedure print(q：node)； 递归输出初始状态至q状态的路径 begin if qfather=0 then begin 输出根状态q并累计路径代价 tottot+1； 输出qstate； endthen else begin 递归输出初始状态至目标状态q的路径并累计路径代价 print(listqfather)； tottot+1； 输出qstate end；else end；print87 从广度优先搜索的算法流程可以看出，若当队列空（cl

57、osed=open）时还未搜索到目标状态，则说明初始状态与目标状态之间根本不存在任何路径，失败退出；若当队列满（openmaxlist）时还未搜索到目标状态，则说明由于内存限制而无法找到目标状态。如果从初始状态到达最近的目标状态的长度为l，每一个状态可扩展的子状态的个数为m，则它必须在解答树上扩展完l-1层的所有状态，而不管目标状态位于哪条树枝上。在整个搜索过程中，扩展的状态数为(忽略由于不满足约束条件而不允许扩展的状态数，即以丰满的完全m叉树计算)。由此看出状态数基本上以指数增长，l愈长，搜索空间愈大，时间愈慢。88【例题12.3.2】最少步数问题描述在各种棋中，棋子的走法总是一定的，如中国象棋中马走“日”。有一位小学生就想如果马能有两种走法将增加其趣味性，因此，他规定马既能按“日”走，也能如象一样走“田”字。他的同桌平时喜欢下围棋，知道这件事后觉得很有趣，就想试一试，在一个（19*19）的围棋盘上任选两点A、B，A点放上黑子，B点放上白子，代表两匹马。棋子可以按“日”字走，也可以按“田”字走，俩人一个走黑马，一个走白马。谁用最少的步数走到左上角坐标为(1,1)的点时，谁获胜。现在他请你帮忙，给你A、B两点的坐标，想知道两个位置到（1,1）点的可能最少步数。样例输入：12 16 18 10输出：8 989题解 由于A、B两点