数据结构课件3-2

1、第三章栈和队列通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。 线性表 栈 队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈和队列是两种常用的数据类型3.1 栈的类型定义3.2 栈类型的实现3.3 栈的应用举例3.4 队列的类型定义3.5 队列类型的实现栈（stack）定义 栈是只能在一端插入和删除的线性表特性：后进先出（LIFO）或 先进后出（FILO）设栈s=（a1，a2，. . . ,ai，. . . ，an），其中

2、a1是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。 a1 a2 . an进栈出栈栈顶栈底3.1 栈的类型定义 ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop

3、(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit() InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。StackEmpty(S)初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。StackLength(S)初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。a1a2an ClearStac

4、k(&S)初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。a1a2ane Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。a1a2anan-1 设数组S是一个顺序栈，栈的最大容量stacksize=4 ，初始状态top=0 10S42310basestop=xtop=top+1top 10 25 30S42310topbasetop=top-1x=stop栈空10进栈30出栈S42310Top=0top栈满 top=stacksize

5、 10 25 30 40S42310top=4base3.2栈类型的实现顺序栈链栈 a1 a2 top1.顺序栈：一维数组sM 用顺序存储结构表示的栈。 顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABC

6、DEFtoptoptoptoptoptop栈空/- 栈的顺序存储表示 - #define STACK_INIT_SIZE 100; / 存储空间的初始分配量 #define STACKINCREMENT 10; / 存储空间的分配增量 typedef struct SElemType *base; / 栈底指针 SElemType *top; / 栈顶指针(栈顶元素的下一个位置) int stacksize; / 当前分配的存储容量 SqStack; 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。1）和顺序表一样采用增量式的空间分配；2）操作和栈顶相关：插入操作（入栈）：将待插元

7、素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。3）约定：top指向栈顶元素的下一个位置（便于表示空栈）。4）栈顶的初始化：S.top = S.base(在上述3)约定下的空栈形式)，5）栈空：S.base = S.top， 栈满：S.top - S.base = S.stacksize6）入栈：*S.top + = e， 出栈：e = *-S.top注意：4), 5), 6)步受3)制约。约定不同，相应的判定和处理也不一样。如假设to

8、p就指向栈顶元素，此时4),5),6)如何？基本操作的实现base空栈a 进栈b 进栈atopbasetopbasetopab约定：top指向栈顶元素的下一个位置basee 进栈f 进栈溢出e出栈edcbatopbasetopbasetopedcbadcba Status InitStack (SqStack &S)/ 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base; S.stacksize = STA

9、CK_INIT_SIZE; return OK;取栈顶元素GetTop_Sq算法设计参数：顺序栈S、取得的栈顶元素&e分析：由于top指向栈顶元素的下一个位置，因此实际的栈顶元素的位置应是top -1；栈非空时，此操作有效。算法Status GetTop_Sq(SqStack S, ElemType &e)/* 判断栈是否为空 */if ( S.base = S.top) return ERROR;e = *( S.top -1);return OK;入栈操作Push_Sq算法设计参数：顺序栈&S、插入元素e分析：插入位置为栈顶元素的下一个，无须判断位置的合法性；上溢即栈满的条件需要判断，由于

10、是增量式分配，故栈满时需要重新申请空间; Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /栈满，追加存储空间 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemType); if (!S.base) exit (OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.to

11、p+ = e; T(n) = O(1) return OK;出栈操作Pop_Sq算法设计参数：顺序栈&S、删除的栈顶元素&e分析：在栈非空时，删除栈顶元素Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除S的栈顶元素， / 用e返回其值，并返回OK； / 否则返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; /* 注意与GetTop( )的区别*/ return OK; T(n) = O(1) 在一个程序中同时使用两个栈0M-1栈1底栈1顶栈2底栈2顶栈顶指针链栈a1an注意: 链栈中指针

12、的方向an-1与链表类似，只是链表的头指针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头结点。 用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。无栈满问题(除非分配不出内存), 空间可扩充栈顶-链表的表头3.3 栈的应用举例例一、 数制转换例二、 括号匹配的检验例三、 行编辑程序问题例四、 迷宫求解例五、 表达式求值例六、 实现递归 例一、 数制转换 算法基于原理： N = (N div d)d + N mod d 多进制输出：例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732

13、 1）将N%d的结果保存，2）N=N/d，3）若N=0结束，否则继续1）。保存的余数从先到后依次表示转换后的d 进制数的低位到高位，而输出是由高位到低位的，因此必须定义先进后出的线性表栈来保存；当全部的余数求出后，通过逐个出栈输出d进制数。 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!

14、StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion例二、 括号匹配的检验假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 （）)均为不正确的格式。则 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。 从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，结束。在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8到来的是“不速之客”；直到结

15、束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。Status matching(string& exp) int state = 1; while (i=Length(exp) & state) switch of expi case 左括弧:Push(S,expi); i+; break; case”)”: if(NOT StackEmpty(S)

16、&GetTop(S)=“(“ Pop(S,e); ii+; else state = 0; break; if (StackEmpty(S)&state) return OK; .例三、行编辑程序问题如何实现？“每接受一个字符即存入存储器” ? 并不恰当！处理规则：遇#退一格；遇退一行算法思想：引入栈，保存终端输入的一行字符（逐行处理）；遇#退一格出栈一次遇退一行清栈步骤：1）初始化栈S2）读入字符ch3）ch!=EOF3.1) ch!=EOF & ch!=n 3.1.1）ch为#：Pop(S, c), 转3.1.4)3.1.2）ch为： ClearStack (S) , 转3.1.4)3.1

17、.3）ch为其他： Push (S, ch) , 转3.1.4)3.1.4）再读入字符ch，继续3.1)3.2) 处理完一行，清空栈3.3) 如ch!=EOF，读入字符ch，继续3) 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“”为退行符。 在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时 可以及时更正。合理的作法是：假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);则实际有效的是下列两行： while (*s) putchar(*s+); while (ch != EOF

18、 & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 ClearStack(S); / 重置S为空栈if (ch != EOF) ch = get char();while (ch != EOF) /EOF为全文结束符将从栈底到栈顶的字符传送至调用过程的数据区；例四、 迷宫求解通常用的是“穷举求解”的方法求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入

19、路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。问题：找从“入口”到“出口”的路径（所经过的通道方块）分析：方块的表示坐标，当前的状态（障碍、未走的通路、已走的通路）；已走的路径：路径中各方块的位置及在路径中的序号;从各方块出发已探索的方向，注意不能重复（可约定按东、南、西、北的方向顺次探索）；从当前方块无路可走时，将已走路径回退一个方块，继续探索其他未走的方向栈存储已走的通道块设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位

20、置； 否则 while (栈不空）；求迷宫中一条从入口到出口的路径的算法： 若栈不空且栈顶位置尚有其他方向未被探索，则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通，则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；若栈空，则表明迷宫没有通路。 限于二元运算符的表达式定义: 表达式 := (操作数) + (运算符) + (操作数) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数例五、 表达式求值只包含+, -, *, / 四个双目运算符，且算符本

21、身不具有二义性；三个运算规则运算符优先关系（考虑算符本身的优先级和结合性）；只有 (=)，#=#；假设输入的是一个合法的表达式。问题描述引入OPTR和OPND两个栈初始：OPTR有一个元素#，OPND为空读入一字符cc=#：return(GetTop(OPND)c非运算符：Push(OPND,c)c运算符：t=GetTop(OPTR)，比较t和c的优先关系tc：Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); x=Operate(a, theta, b); Push(OPND, x);继续读入字符处理。 算法思想 表达式的三种标识方法：设 Exp =

22、S1 + OP + S2则称 OP + S1 + S2 为前缀表示法(波兰式) S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法(逆波兰式) 例如: Exp = a b + (c d / e) f前缀式: + a b c / d e f中缀式: a b + c d / e f后缀式: a b c d e / f + 结论:1）操作数之间的相对次序不变;2）运算符的相对次序不同;3）中缀式丢失了括弧信息， 致使运算的次序不确定;4)前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式; 5)后缀式的运算规则为: 运算符在式中出现的

23、顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式。运算符： * / * + - （ ） 界限符： ；以表达式 A*B + CD 为例说明利用栈的求值过程。 优先级： 4 3 3 2 2 1 1 0操作数变量：A B C DA*B + C/D;top2top1初态;(a)OSNSBA*;(b)NSOST1;(c)T1=A*BNSOSDCT1/+;(d)NSOS(g)NSOST2=C/DT2T1+;(e)NSOST3;(f)T3=T2+T1NSOS思想：从左到右扫描表达式，若当前读入的是操作数，则进操作数（NS）栈，若读入的符号是运算符，应进行判断

24、：若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。2.若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。3. 若读入的是“；”，且运算符栈顶的符号也是“；”时，则表达式处理结束。从操作数栈弹出表达式结果。例 计算 2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-3

25、6*操作数运算符6-18操作数运算符12表达式的不同表示之间的相互转换逆波兰式波兰式如：abcd+*e*+ +a*b+cde共同点运算对象的次序一致不需要括号区分优先级和结合性某算符在所有算符中的次序决定了它的计算次序转换的思想参照逆波兰式的计算过程，将计算转换为待计算的算符和运算对象的串的拼接逆波兰式中缀表达式如： abcd+*e*+ a+b*(c+d)*e 输入：表达式符号序列表达式求值算法：输出：表达式值 y初始化栈 NS、OSPush (OS, “;” , top2)；t=0; /表示扫描下一个符号while (t 2) IF t=0 THEN read W; IF W 为操作数 TH

26、EN Push( NS, W, top1)ELSE p=OStop2; /读运算符栈栈顶元素，存入p .IF (Wp)or(W=“(“) THENPush (OS, W, top2); t=0; ELSE IF (p=“;” ）and (W=“ ;”) THEN Pop (NS, y,top1); t=2; /处理过程结束ELSE IF (p=“(“ )and (w=“）”）THENELSE Pop(NS,x,top1);Pop(NS,z,top1);Pop(OS,p,top2）；x=z x;Push(NS ,x ,top1);t=1; /t=1,当前的符号下次重新考虑 输出 y;return

27、; Pop(OS ,p,top2); t=0; 练习1：A+B*C-D/E；top1初态;(a)top2OSNSBA+;(b)OS*C NST1=B*CA+;(c)NSOST1T2;(d)NSOST2=A+T1EDT2/-;(e)NSOST3T2-;(f)T3=D/ENSOS(g)NSOST4；T4=T2-T3(h) 练习：A-B/C+D*E；top2初态;(a)OSNSBA;(b)OS/C NSA;(c)NSOST1T1=B/CA;(d)NSOST1 DE+*T2T1A+;(e)NSOST2=D*ET2T3+;(f)T3=A-T1NSOST4=T2+T3(g)NSOST4；(h)优先级相同时

28、，应先处理栈中数据错在哪？ 练习2：若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的一个出栈次序是（ ）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3d练习3：用一维数组设计栈，初态是栈空，top=0。现有输入序列是 a、b、c、d，经过 push、push、pop、push、pop、push操作后，输出序列是（ ），栈顶指针是（ ）b、c2如何从后缀式求值？先找运算符， 再找操作数例如： a b c d e / f +abd/ec-d/e(c-d/e)f如何从原表达式求得后缀式？ 每个运算符的运算次序要由它之后的一个运算符来定，在

29、后缀式中，优先数高的运算符领先于优先数低的运算符。分析 “原表达式” 和 “后缀式”中的运算符:原表达式: a + b c d / e f 后缀式: a b c + d e / f 从原表达式求得后缀式的规律为：1) 设立操作数栈；2) 设表达式的结束符为“#”， 予设运算符栈的栈底为“#”；3) 若当前字符是操作数， 则直接发送给后缀式。4) 若当前运算符的优先数高于栈顶运算符，则进栈；5) 否则，退出栈顶运算符发送给后缀式； 6) “(” 对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为：void transform(char suf

30、fix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; while (!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); else if ( ch!= # ) p+; ch = *p; else Pop(S, ch); Pass(Suffix, ch); / while / CrtExptree switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) Pass( Suffix, c);

31、Pop(S, c) break; defult : while(Gettop(S, c) & ( precede(c,ch) Pass( Suffix, c); Pop(S, c); if ( ch!= # ) Push( S, ch); break; / switch 1、栈（stack）定义 栈是只能在一端插入和删除的线性表特性：后进先出（LIFO）或 先进后出（FILO）设栈s=（a1，a2，. . . ,ai，. . . ，an），其中a1是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删

32、除的一端。 a1 a2 . an进栈出栈栈顶栈底内容回顾2、栈的类型定义 ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT Stack内容回顾InitStack(&S) DestroyStack(&S)StackLength(S) StackEmpty(S)GetTop(S, &e) ClearStack(&S)Push(&S, e) Pop(&S, &e)StackTravers(S, visit()3、栈类型的实现顺序栈链栈内

33、容回顾 a1 a2 top顺序栈一维数组SM，即用顺序存储结构表示的栈顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。栈顶指针链栈a1an注意: 链栈中指针的方向an-1与链表类似，只是链表的头指针即为栈顶指针。因其操作均在栈顶进行，故可以不引入头结点。 用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。无栈满问题(除非分配不出内存), 空间可扩充栈顶-链表的表头4、栈的应用举例例一、 数制转换例二、 括号匹配的检验例三、 行编辑程序问题例四、 迷宫求解例五、 表达式求值例六、

34、 实现递归例六、实现递归直接或间接地调用自身的函数，称为递归函数。递归表现为：在该函数的所有可能执行路径中，存在一条由于调用自身或其它函数所导致的环路路径；为确保函数最终在有限的时间内执行完毕，必须在环路中存在一个出口，即当某种条件成立时，不必执行环路，而直接执行一条通向结束的非环路线。开始结束形成了 环递归定义直接调用int f(int x) int y,z; . z=f(x); return (2*z); f 函数调用 f函数int f1(int x) int y,z; . z=f2( y); return (2*z); int f2(int t) int a,c; . c=f1(a);

35、return (3+c); 间接调用递归应用的特点对于一个问题，当问题规模很大时，往往难于直接求解，此时： 将大问题分解成若干小问题 考虑如何利用这些小问题的解构成大问题的解这种分解、合成的方法就是递归求解中的递归方法；另外，递归应用要注意避免陷入死循环，递归必须有出口，即要确立递归的结束条件，给出此时的直接求解方法。 以求4的阶乘为例：4！=4*3！3! =3* 2!2! =2* 1!1! =1*0！4! =4*3*2*12! =2*13! =3*2*1下推回代例如：写一函数求n! 1 (n=0)n! = n * (n-1)！ (n1)1! =1*10! =1 float fac ( int

36、 n) float f; if(n0) printf(“n0,data error!n”); else if(n=0) f=1; else f=fac(n-1)* n ; return f; 例如：写一函数求n! 1 (n=0)n! = n(n-1)！ (n 1)以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1*fac(0)fac(4) =4*3*2*1fac(2) =2*1fac(3) =3*2*1下推回代fac(1) =1*1fac(0)=1利用栈实现递归调用主程序(1)输出f(4); 4 f (4);（1）n=4

37、top(2) s=4*f(3)n3 f (3);（2）n=3 （1）n=4 top(3) s=3*f(2)n2 f (2);（3）n=2 （2）n=3 （1）n=4 top(4)s=2*f(1)n1（4）n=1 （3）n=2 （2）n=3 （1）n=4 tops s=3*2*1;(2) 3(1) 4top s=2*1(3) 2(2) 3(1) 4top s=4*3*2*1 (1 ) 4top返回(3) 2(2) 3(1) 4top(4) 1结束输出24将所有的实在参数、返回地址等信息传递给被调用函数保存；为被调用函数的局部变量分配存储区；将控制转移到被调用函数的入口。 当在一个函数的运行期间调

38、用另一个函数时，在运行该被调用函数之前，需先完成三项任务：递归的实现 保存被调函数的计算结果；释放被调函数的数据区；依照被调函数保存的返回地址将控制转移到调用函数。从被调用函数返回调用函数之前，应该完成下列三项任务：多个函数嵌套调用的规则是：此时的内存管理实行“栈式管理”后调用先返回 ！例如：void main( ) void a( ) void b( ) a( ); b( ); /main / a / bmain的数据区函数a的数据区函数b的数据区 递归工作栈：递归过程执行过程中占用的 数据区。递归工作记录：每一层的递归参数合成 一个记录。当前活动记录：栈顶记录指示当前层的 执行情况。当前环

39、境指针：递归工作栈的栈顶指针。递归函数执行的过程可视为同一函数进行嵌套调用：例 递归的执行情况分析 void print(int w) int i; if ( w!=0) print(w-1); for(i=1;icn1:hanoi(n-1, a, c, b)a-chanoi(n-1, b, a, c)注意用递归调用的结果，不关注该结果如何获得的细节执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示n x y z 返回地址 解决方法：n=1时，直接把圆盘从A移到Cn1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆

40、盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n/ 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1 if (n=1)2 move(x, 1, z); / 将编号为的圆盘从x移到z3 else 4 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔5 move(x, n, z); / 将编号为n的圆盘从x移到z6 hanoi(n-1, y, x, z);

41、/ 将y上编号为至n-1的 /圆盘移到z, x作辅助塔7 8 8 3 a b c返址 n x y z5 2 a c b5 1 a b c7 1 c a bvoid hanoi (int n, char x, char y, char z) 1 if (n=1)2 move(x, 1, z); 3 else 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 8 回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都

42、相等，回文字符串：“madam im adam”雾锁山头山锁雾，天连水尾水连天 蜜蜂酿蜂蜜 黄山落叶松叶落山黄 递归与回溯N皇后问题 在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列或同一对角线上，则称它们为互相攻击。n皇后问题是指： 找到这 n 个皇后的互不攻击的布局1#主对角线0 1 2 3 0123k = i+jk = n+i-j-10#主对角线2#主对角线4#主对角线6#主对角线3#主对角线5#主对角线1#次对角线3#次对角线0#次对角线2#次对角线4#次对角线6#次对角线5#次对角线基本思路依次为每一行确定该行皇后的合法位置安放第 i 行皇后时，需要在列的方向从 0 到 n-

43、1 试探 ( j = 0, , n-1 )在第 j 列安放一个皇后如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后：如果没有出现攻击，在第 j 列安放的皇后不动递归安放第 i+1行皇后如果第 i 行不能安放皇后，则回溯到第 i-1 行，从下一个列(j+1)继续试探数据结构设计标识每一列是否已经安放了皇后线性表，表长为N标识各条主对角线是否已经安放了皇后 线性表，表长为2N-1标识各条次对角线是否已经安放了皇后 线性表，表长为2N-1记录当前各行的皇后在第几列布局状况 线性表，表长为N存储结构的选择表长固定，有随机存取的要求顺序表存储结构标识每一列是否已经安放了

44、皇后数组col，表长为N标识各条主对角线是否已经安放了皇后 数组md，表长为2N-1标识各条次对角线是否已经安放了皇后 数组sd，表长为2N-1记录当前各行的皇后在第几列布局状况 数组q，表长为N算法void Queen( int i, int n ) for ( int j = 0; j n; j+ ) if ( 第 i 行第 j 列没有攻击 ) 在第 i 行第 j 列安放皇后; if ( i = n-1 ) 输出一个布局; else Queen ( i+1, n ); 撤消第 i 行第 j 列的皇后; !colj & !mdn+i-j-1 & !sdi+jcolj= 1;mdn+i-j-1

45、=1; sdi+j=1;qi = j;输出qcolj= 0;mdn+i-j-1=0; sdi+j=0;qi = 0;练习题：1、请写出下面程序的运行结果。#include “stdlib.h”void p(int w) int i; if (w!=0)1 printf(“%3d”,w)2 p(w-1);3 p(w-1); main print(3);1 2 3运行结果：32112112 1 3运行结果：12131212、编写一个程序计算2阶Fibonacci数列： 0 n=0Fib(n)= 1 n=1 Fib(n-1)+Fib(n-2) 其它 ADT Queue 数据对象： Dai | aiE

46、lemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾基本操作：3.4 队列的类型定义 ADT Queue定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO)队头Q.front入队 出队a1a2a3anQ.rear队尾队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue

47、(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。 操作结果：队列Q被销毁， 不再存在。 QueueEmpty(Q)初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。a1a2an ClearQueue

48、(&Q)初始条件：队列Q已存在。 操作结果：将Q清为空队列。 EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。a1a2ane DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。a1a2an 线性队列实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=

49、rear=-1空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront存在问题设数组维数为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出真溢出当front-1,rear=M-1时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列3.5 队列类型的实现链队列链式映象循环队列顺序映象 typedef struct QNode / 结点类型 QElemType data; struct QNode *n

50、ext; QNode, *QueuePtr;链队列链式映象typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队xfrontreary入队xyfrontrearx出队xyfrontrear空队frontreary出队入队算法JD *ldcr(JD *rear,int x) JD *p; p=(J

51、D *)malloc(sizeof(JD); p-data=x; p-next=NULL; rear-next=p; return(p);出队算法int ldsc(JD *front,JD *rear) JD *s; int x; if(front=rear) return(-1); s=front-next; front-next=s-next; if(s-next=NULL) rear=front; x=s-data; free(s); return(x); Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (Que

52、uePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; St

53、atus DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-11frontrear.实现：利

54、用“模”运算入队： rear=(rear+1)%M; sqrear=x;出队： front=(front+1)%M; x=sqfront;队满、队空判定条件#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;循环队列顺序映象012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfr

55、ont初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear如何区分队空和队满？区分队空和队满的方法设标志位(上次的更新动作)：0-创建/删除，1-插入引入队列长度少用一个元素空间：插入前判断 Q.front=(Q.rear+1)%MAXQSIZE01723456Q.frontQ.rear01723456Q.frontQ.reara1a2a3a4a5a6a7有维护的代价难点连续的存储单元的上下界：d1,d2初始化空队：Q.front = Q.rear = d1;队空： Q.front=Q.rear队满： Q.front=(Q.rear-d1+1)%

56、(d2-d1+1)+d1入队： 前提：队列不满 Q.baseQ.rear = e; Q.rear = (Q.rear-d1+1)%(d2-d1+1)+d1;出队：前提：队列不空 e = Q.baseQ.front; Q.front = (Q. front-d1+1)%(d2-d1+1)+d1入队算法：void en_cycque(int sq, int front, int rear, int x) if(rear+1)%M)=front) printf(overflow); else rear=(rear+1)%M; sqrear=x; 出队算法：int dl_cycque(int sq,

57、int front, int rear, int *q) if(front=rear) return(0); else front=(front+1)%M; *q=sqfront; return(1); Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemType e) / 插入元素e为Q的新的队尾元素 if