中国科学技术大学：《数据结构及其算法》课程教学资源（课件讲稿）第3章 栈和队列

数据结构 栈和队列 第三章 栈和队列 主讲：张昱 重点：栈和队列的基本特征，表示与 yuzhang@ustc.edu 实现 0551-3603804 难点：递归、循环队列 1/52 2/52 第三章 栈和队列 3.1栈 3.1找 。定义 特囊的线性表：操作变限 3.2栈的应用举例 是展宽仅在兼愿进杜墙入戴喷操作的腹性表 3.3栈与递归的实现 九许桶入求测除的一墙琳为楼顶(op),另一墙称为机毫(bottom) ■逻辑特征 出栈 一进栈 3.4队列 后进先出在.FO) 栈顶 3.5离散事件模拟 ■ADT Stack 南地化空栈、判前栈空、判前栈满 联顶vs.GetElem(L,l,&e) 入找vs.ListInsert&L,l,e) vs.ListDelete(&L,i,&e) a 3/50 4/50 ADT Stack 数据对象：D-f间EE目emSet,.1,2,“nn≥0 GetElem(L,i,&e) 数据关系：R-R1R1-长41>1aeD,23.…n GerTop(S.&e p 基本操作：。 初%条件：栈$己存在且非空 Initstack(&s】 蜂作结架：用：S中钱顶元 操作结果：构造一个空的栈S 初始条件：钱s已存在Listinsert(&L,ie Push(&s.e DestroyStack(&S) 初始条件：钱8已存在 操作结果：插入元素e为新的栈顶元素 操作结果：销吸钱S Pop(&S,&e ClearStack(&S) 初条件：钱s已存在且菲孕ListDelete(&L,i&e 初始条件：钱S已存在 操作结果：利除S的栈顶元素，并用e返回其值 操作结果：将栈S重置为空栈 Stack Traverse(S.visit()) StackEmpty(S 初始条件：栈S已存在且非空 初始条件，钱s已存在 操作结果：从钱底到钱顶依次对s的每个数据元素调用函数() 操作结果：若S为空找，则题回TRUE,否测返回FALSE 旦t()失数，则轻作失毁 StackLength(S) ADT Stack 初始条件：钱S已存在 操作结果：返国栈S中数据元素的个数 5/50 图 6/50 图 1

1 1/52 数据结构——栈和队列 主讲：张昱 yuzhang@ustc.edu 0551-3603804 2/52 重点：栈和队列的基本特征，表示与 实现 难点：递归、循环队列 第三章 栈和队列 3/50 第三章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 3.5 离散事件模拟 4/50 3.1 栈 „ 定义 特殊的线性表：操作受限 是限定仅在表尾进行插入或删除操作的线性表 允许插入或删除的一端称为栈顶(top),另一端称为栈底(bottom) „ 逻辑特征 后进先出(LIFO) „ ADT Stack 初始化空栈、判断栈空、判断栈满 取栈顶 vs. GetElem(L, i, &e) 入栈 vs. ListInsert(&L, i, e) 出栈 vs. ListDelete(&L, i, &e) 出栈 进栈 an . . . . a1 栈顶 栈底 5/50 6/50 GetElem(L, i, &e) ListInsert(&L, i, e) ListDelete(&L, i, &e)

3.1栈-顺序栈-类型定义 3.1栈-顺序栈-基本操作的实现 。题序想 ·顺序找 。基本操作的实现 。类型定义 注意t即的含义—的定 。战项的初始化：S.top=S.base #define STACK_INIT_SIzE1O0/∥存情空间的初地分配量 空，S.base==5.top ,找满：5.top-S.base>=S.stacksize #define STACKINCREMENT10/∥存情空间的分配增量 。入栈：S.top++=e,出找：e=*-S.top typedef struct( ElemType *base; 川提度指针 ElemType *top:∥线顶指针（拉亚元意的下一个位置） int stacksize; top- ∥当前分配的存伸容量 top >SqStack; base base- 空栈 a进栈 b进栈 7/50 回 钩定：op指向找顶元的下一个位 图 3.1栈-顺序栈-基本操作的实现 3.1栈赞钱的表示与实现 ,顺序栈 ■链栈 ·无栈满问题（除非分配不出内存），空间可扩充 top ,栈顶一链表的表头 。可以不必引入头结，点 hase has o柳一N一□一□一…一囚 e进栈 ∫进栈溢出 e出栈 约定：top指向栈顶元素所在的结点 约定：top指向找顶元素的下一个位量 9/50 图 10/50 图 3.2栈的应用举例 3.2栈的应用举例-数制转换 ,数制转换 ■数制转换：将十进制数N转换成其他d进制数 ■括号匹配的检验 ,算法思想：N=(N div d)Xd+N mod d ■行编辑程庄 1)保存余数N%d 2)N=N/d, ■迷宫求解 3)若N==0结束，否则继续1)。 ■表达式求值 保存的余数从先到后依次表示转换后的d进制数的 低位到高位，而输出是由高位到低位的，因此必须 定义先进后出的线性表栈来保存：当全部的余 数求出后，通过逐个出栈输出d进制数。 11/50 图 12/50 图 2

2 7/50 3.1 栈–顺序栈-类型定义 „ 顺序栈 „ 类型定义 注意top的含义——约定 #define STACK_INIT_SIZE 100// 存储空间的初始分配量 #define STACKINCREMENT 10// 存储空间的分配增量 typedef struct{ ElemType *base; // 栈底指针 ElemType *top; // 栈顶指针(栈顶元素的下一个位置) int stacksize; // 当前分配的存储容量 }SqStack; 8/50 3.1 栈–顺序栈-基本操作的实现 „ 顺序栈 „ 基本操作的实现 „ 栈顶的初始化：S.top = S.base „ 栈空：S.base == S.top „ 栈满：S.top - S.base >= S.stacksize „ 入栈：*S.top ++ = e，出栈：e = *--S.top base 空栈 a 进栈 b 进栈 a top base top base top a b 约定：top指向栈顶元素的下一个位置 9/50 3.1 栈–顺序栈-基本操作的实现 base e 进栈 f 进栈溢出 e出栈 e d c b a top base top base top 约定：top指向栈顶元素的下一个位置 e d c b a „ 顺序栈 d c b a 10/50 3.1 栈–链栈的表示与实现 约定：top指向栈顶元素所在的结点 „ 链栈 „ 无栈满问题(除非分配不出内存), 空间可扩充 „ 栈顶----链表的表头 „ 可以不必引入头结点 top N ^ 11/50 3.2 栈的应用举例 „ 数制转换 „ 括号匹配的检验 „ 行编辑程序 „ 迷宫求解 „ 表达式求值 12/50 3.2 栈的应用举例-数制转换 „ 数制转换: 将十进制数N转换成其他d进制数 „ 算法思想：N = ( N div d )×d + N mod d 1) 保存余数N%d 2) N=N/d， 3) 若N==0结束，否则继续1)。 保存的余数从先到后依次表示转换后的d 进制数的 低位到高位，而输出是由高位到低位的，因此必须 定义先进后出的线性表——栈来保存；当全部的余 数求出后，通过逐个出栈输出d进制数

3.2栈的应用举例-数制转换 3.2栈的应用举例-行编辑程序 行铺舞程序(P49) ■数制转换 。处理规则：造#通一格：漫@退一行 。算法（算法3.1P48) 算法题想：引入校，保存终增输入的一行字符（理行处理）： 出一次 void conversion(int N,int d) 透©逼一行清法 InitStack(S); while(N){Push(S,N%/od);N=N/d; 化5 while(!StackEmpty(S)){ 3)ch!=EOF Pop(S,e); 3.1)ch!=EOF &ch!='\n' 3.1.1)ch为#，Pop5,c.轴3.1.4) printf(e); 3.1.2)dh为@'， C1ear5ac(S,转3.1.4) 3.1.3)dh为其恤：Push(s,h),被3.1.4) 3.1.4)再读入享符h,雕读3.1) 3。实小，) 3.2)处理完 13/50 囵 14/50 回图 3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 ,表达式求值(P52) ,问题描述 。表达式的表示 ·只包含+，*，/四个双目运算符，且算符本身 不具有二义性： ,中缀表达式(a+b)*c-d*(e-a) 。三个算术四则运算的规则 ,前级表达式*+abc*d-ea (波兰式) 先乘雕，后加减 ,后缀表达式ab士c*deae*。 (逆波兰式) ·从左算到右 。先括号内，后括号外 →算符间的优先关系（算符的优先级和结合性）（表3.1） 分支站点是算特 。#:表达式的开始符和结束符 ·只有(==)，'#==#， 叶子结点是操作数 ,假设输入的是一个合法的表达式。 15/50 回 16/50 图 3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 ·算法思短 ·输入：前缀表达式串（被兰式） 输入：中氧表达式率 输出：表达式值 输出：表达式值 ,入OPTR和OPWD两个线 例：-*+abc*d-ea 钓始OPTR有一元膏”，OPND为空 ,通到算蒋时，由于远算对象还来读到，放前存 入一半将 um(GetTop(OPND)) 是算特，Push(OPND,C) 爱老整清音茶法入的竹逃系对 (OPTR),比款率c的优壳关事 管存的算将个最不国定，需要引入款播结构保存 ·针对上例：在进行算一个运算前，需智存， Pop(OPTR,x) ·敢据结构的操作塘点：后进先出→机 t>cr Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a); 。管存的运算对象个数不国定，需要引入最端结构保存 x=Operate(a,theta,b); 。针对上例：在迹行第一个+运算前，馨智存a,b,c Push(OPND,x); 。敷霜辅构的操作将点：后进光出→投 。整能害入亭特处夏。 17/50 图 ·不衡共比模料特种儿点来蜡合出，只要幕林的选界对白 整齐全，即可计算！18/50

3 13/50 3.2 栈的应用举例-数制转换 „ 数制转换 „ 算法(算法3.1 P48) void conversion(int N, int d){ InitStack(S); while(N) { Push(S, N%d); N=N/d; } while(!StackEmpty(S)) { Pop(S, e); printf(e); } } 14/50 3.2 栈的应用举例-行编辑程序 „ 行编辑程序(P49) „ 处理规则：遇‘#’退一格；遇‘@’退一行 „ 算法思想：引入栈，保存终端输入的一行字符（逐行处理）； 遇‘#’退一格——出栈一次 遇‘@’退一行——清栈 „ 步骤： 1）初始化栈S 2）读入字符ch 3）ch!=EOF 3.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.3）ch为其他： Push (S, ch) , 转3.1.4) 3.1.4）再读入字符ch，继续3.1) 3.2) 处理完一行，清空栈 3.3) 如ch!=EOF，读入字符ch，继续3) 15/50 3.2 栈的应用举例-表达式求值 „ 表达式求值(P52) „ 表达式的表示 „ 中缀表达式 (a+b)*c-d*(e-a) „ 前缀表达式 -*+abc*d-ea (波兰式) „ 后缀表达式 ab+c*dea-*- (逆波兰式) - * * + a b c d - e a 分支结点是算符 叶子结点是操作数 16/50 3.2 栈的应用举例-表达式求值 „ 问题描述 „ 只包含+, -, *, / 四个双目运算符，且算符本身 不具有二义性； „ 三个算术四则运算的规则 „ 先乘除,后加减 „ 从左算到右 „ 先括号内,后括号外 Î算符间的优先关系（算符的优先级和结合性）(表3.1) „ #: 表达式的开始符和结束符 „ 只有 '('==')'，'#'=='#'； „ 假设输入的是一个合法的表达式。 17/50 3.2 栈的应用举例-表达式求值 „ 算法思想 输入：中缀表达式串 输出：表达式值 „ 引入OPTR和OPND两个栈 „ 初始OPTR有一元素‘#’，OPND为空 „ 读入一字符c c==‘#’：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); „ 继续读入字符处理。 18/50 3.2 栈的应用举例-表达式求值 „ 输入：前缀表达式串(波兰式) 输出：表达式值 例： -*+abc*d-ea „ 遇到算符时，由于运算对象还未读到，故暂存 „ 遇到运算对象时，需要判断当前最近读入的算符的运算对象 是否齐全，若齐全则计算否则暂存 „ 暂存的算符个数不固定，需要引入数据结构保存 „ 针对上例：在进行第一个运算前，需暂存-,* „ 数据结构的操作特点：后进先出-Æ栈 „ 暂存的运算对象个数不固定，需要引入数据结构保存 „ 针对上例：在进行第一个+运算前，需暂存a,b,c „ 数据结构的操作特点：后进先出-Æ栈 „ 不需要比较算符的优先级和结合性，只要算符的运算对象已 经齐全，即可计算！

3.2栈的应用举例-表达式求值 3.2栈的应用举例-表达式求值 OpndType EvaluatePostExpr(OKII氧设表达文是合法的 ·输入：后领表达式申（逆波兰式） InitStack(OPND);c=getchar(); 输出：表达式值 while (cl#) if (!IsOP(c))Push(OPND,c); 。例：ab+c*dea-* else( 。退到进算时桌时，由于算将在后，故前存该进算对康 Pop(OPND,b);Pop(OPND,a); 逼到算符时，立即计算 Push(OPND,doop(a,c,b)); 。前存的运算时章个数不园定，营要引入款据站构保存 。上侧中：在进行第一个运算前，嚼督存和，b c=getchar(); 。数据结构的操作特点：后选先出~蝇作数技 。不需要比校算将的优先银塘合性 result GetTop(OPND);DestroyStack(OPND); 退到算符时，直接从操作数找中弹出所需的操作数进行计 return result; 算：计算后再将计算帅录入栽 19/50 回 2D/50 图 3.2栈的应用举例-表达式转换 栈的概念运用 。表达式的不同表示之间的相互转换 ■问题1：习题桌3.6P23 。逆波兰式)波兰式 。轴入序列：123…H ,如：ab+c*dea-*.-*+abc*d-ea ■轴出序列P1P2户3…P ·共同点 ,证明，不存在i<j<k使得P,<P<P 。运算对津的次序一票 ·证（反证法）：假设存在<<k,使，<P,< ,不需要指号区分优光最和纳合性 ?<k”n最先出找，P最后出找 ·某算符在所有算特中的女序决定丁它的计算欲序 由鞭设如即，是三个敢中最大的 ,转换的思想 :入提序列是按值道增的 a。黄材保线为病保年健 :若某个值大的先出找。花中还有比它小的值，这些值将按值道常 。逆波兰式)中鞭表达式 的次序依次输出 即即先出，P和部比，小，录后着出，P的值应该是最小的 ,如：ab+c*dea-*.→(a+b)*c-d*(e-a) 图 这与服设相矛看。 21/50 22/50 图 3.3栈与递归的实现 3.3栈与递归的实现 ,递归的定义 递归 递推 ·递归(recursion):直接或间接地调用自身， 。递归的规则 int fact1(int n) int fact2(int n) 开始 。递归终止条件 if(n<0)return-1; 如：nl=(n-11*n if(n<0)return-1; else if(n==0)return 1; fact=1;i=1; 01=1 return n*fact1(n-1); ile(i<=n) ·递推：从已知的初始条件出 r 发，恶次递推出最后要求的值，结 fact *=;++ 如：01=1,1=0I*1=1 2 2!=11*2=2 23/50 可图 24/50 图 4

4 19/50 3.2 栈的应用举例-表达式求值 OpndType EvaluatePostExpr(){ //假设表达式是合法的 InitStack(OPND); c=getchar(); while (c!=‘#’) { if ( !IsOP(c) ) Push(OPND, c) ; else{ Pop(OPND, b); Pop(OPND, a); Push(OPND, doOp(a,c,b)); } c=getchar(); } result = GetTop(OPND); DestroyStack(OPND); return result; } 20/50 3.2 栈的应用举例-表达式求值 „ 输入：后缀表达式串(逆波兰式) 输出：表达式值 „ 例： ab+c*dea-*- „ 遇到运算对象时，由于算符在后，故暂存该运算对象 „ 遇到算符时，立即计算 „ 暂存的运算对象个数不固定，需要引入数据结构保存 „ 上例中：在进行第一个运算前，需暂存a,b „ 数据结构的操作特点：后进先出-Æ操作数栈 „ 不需要比较算符的优先级和结合性 „ 遇到算符时，直接从操作数栈中弹出所需的操作数进行计 算；计算后再将计算结果入栈 21/50 3.2 栈的应用举例-表达式转换 „ 表达式的不同表示之间的相互转换 „ 逆波兰式Æ波兰式 „ 如： ab+c*dea-*- Æ -*+abc*d-ea „ 共同点 „ 运算对象的次序一致 „ 不需要括号区分优先级和结合性 „ 某算符在所有算符中的次序决定了它的计算次序 „ 转换的思想 „ 参照逆波兰式的计算过程，将计算转换为待计算的算符和运 算对象的串的拼接 „ 逆波兰式Æ中缀表达式 „ 如： ab+c*dea-*- Æ (a+b)*c-d*(e-a) 22/50 栈的概念运用 „ 问题1：习题集3.6 P23 „ 输入序列：1 2 3 … n „ 输出序列：p1 p2 p3 … pn „ 证明：不存在i<j<k, 使得pj < pk < pi „ 证(反证法)：假设存在i<j<k, 使pj < pk < pi ∵ i<j<k ∴ pi 最先出栈，pk最后出栈 由假设知pi 是三个数中最大的 ∵入栈序列是按值递增的 ∴若某个值大的先出栈，栈中还有比它小的值，这些值将按值递减 的次序依次输出 即pi 先输出，pj 和pk都比pi 小，pk最后输出，pk的值应该是最小的 这与假设相矛盾。 23/50 3.3 栈与递归的实现 „ 递归的定义 „ 递归(recursion)：直接或间接地调用自身. „ 递归的规则 „ 递归终止条件 如: n! = (n-1)! *n 0! = 1 „ 递推：从已知的初始条件出 发，逐次递推出最后要求的值。 如：0!=1, 1!= 0!*1 = 1 2! = 1! *2 = 2 …… 24/50 3.3 栈与递归的实现 递归 int fact1(int n) { if (n<0) return -1; else if (n==0) return 1; return n*fact1(n-1); } 递推 int fact2(int n) { if (n<0) return -1; fact=1; i=1; while (i<=n) { fact *= i; i++; } }

3.3栈与递归的实现 3.3栈与递归的实现 ,递归与递推的关系 ,递归的对象：一个对象部分地包含它自己， 递归算法的执行过程分递推与回归两个阶段。 或用它自已给自己定义。如莱些数据结构的 定义 ,在递推阶段，把较复杂的问题（规模为）的求 战性表的另男一种定义（归纳定义）： 解推到比原问题简单一些的问题（规模小于） 。基本步：若元素个数为0，则称为空表 的求解。 ,归纳步：若元素个敢大于0，则有且仅有一个第一 ,在回归阶段，当获得最简单的情况后，逐级返 个无素（表头），剩余元素形成一个表〔表)· 回，依次获得稍复杂问愿的解。 ,递归的过程：一个过程直接或间接地调用自 遂推是递归的一个阶段，递归包含着递推。 己 如：0的阶乘是1，n(n>0)的阶乘等于n乘上(n-1) 的阶乘 25/50 回 26/50 图 3.3栈与递归的实现 3.3栈与递归的实现-阶桑函数 ■递归的应用 ■定义是递归的 ·递归定义：如阶来、Fibonacci数列等 1, 当n=0时 ,数据结构：如表、树、二叉树等 n!= ,问题求解：如Hanoi塔 n*(n-I)1, 当n≥1时 求解阶乘函数的递归算法 long fact long n) if(n==0)return 1; /递归结来条件 else return n fact (n-1); /递归的规则 27/50 圆 28/50 图 3.3栈与递归的实现阶乘函数 3.3栈与递归的实现数据结构 主程序main():fact(4) 。数据结构是递归的-一表 ·空表 fact(4):计算4*fact(3) ·非空表：（表头元素+除表头元素以外的剩余元素） 递参 6 。查找夜L中是否有元意值ε fact3):计算3*act2 结 LinkList search(LinkList L,ElemType e) 归调用 传 回归求位 //L为不带头结点的单陶非狮环链表 fact2:计算2*fact(1 返回 1 if (L==NULL)return NULL; fact:计算1*fact(0 else if L->data==e return L; else return search(L->next,e); fact0):直接定值为1 29/50 图 30/50 图

5 25/50 3.3 栈与递归的实现 „ 递归与递推的关系 递归算法的执行过程分递推与回归两个阶段。 „ 在递推阶段，把较复杂的问题（规模为n）的求 解推到比原问题简单一些的问题（规模小于n） 的求解。 „ 在回归阶段，当获得最简单的情况后，逐级返 回，依次获得稍复杂问题的解。 递推是递归的一个阶段，递归包含着递推。 26/50 3.3 栈与递归的实现 „ 递归的对象：一个对象部分地包含它自己， 或用它自己给自己定义。如某些数据结构的 定义 线性表的另一种定义(归纳定义): „ 基本步：若元素个数为0，则称为空表 „ 归纳步：若元素个数大于0，则有且仅有一个第一 个元素(表头)，剩余元素形成一个表(表尾) 。 „ 递归的过程：一个过程直接或间接地调用自 己 如：0的阶乘是1，n(n>0)的阶乘等于n乘上(n-1) 的阶乘 27/50 3.3 栈与递归的实现 „ 递归的应用 „ 递归定义：如阶乘、Fibonacci数列等 „ 数据结构：如表、树、二叉树等 „ 问题求解：如Hanoi塔 28/50 3.3 栈与递归的实现–阶乘函数 „ 定义是递归的 ⎩ ⎨ ⎧ ∗ − ≥ = = 当 时 当 时 ( 1)!, 1 1, 0 ! n n n n n 求解阶乘函数的递归算法 long fact ( long n ) { if ( n == 0 ) return 1; //递归结束条件 else return n * fact (n-1); //递归的规则 } 29/50 3.3 栈与递归的实现–阶乘函数 主程序 main( ): fact(4) 参 数 传 递 递 归 调 用 结 果 返 回 回 归 求 值 fact(4): fact(3): fact(2): fact(1): fact(0): 1 直接定值为1 计算 4*fact(3) 计算 3*fact(2) 计算 2*fact(1) 计算 1*fact(0) 1 2 6 24 30/50 3.3 栈与递归的实现–数据结构 „ 数据结构是递归的--表 „ 空表 „ 非空表: (表头元素+除表头元素以外的剩余元素) „ 查找表L中是否有元素值e LinkList search(LinkList L, ElemType e) // L为不带头结点的单向非循环链表 { if ( L==NULL ) return NULL; else if ( L->data==e ) return L; else return search(L->next, e); }

3.3栈与递归的实现-Hanoi塔 3.3栈与递归的实现-递归实现 ■问题求解是递归的一Hanoi塔 ■调用函数与被调用函数一系统工作栈 void hanoi(int n,char a,char b,char c) n-圆盘数a-源塔座 ·执行被调用函数前 b-中介塔座c目标塔座 。现场保护：实在参数、远回地址 ■搬动方法 。为被调用函数的局部变量分配存储区 ■n=1,a->c 。将控制转移到被调函数的入口 ,从被调用函数返回调用函数前 。保存被调西数的计算结果 ■注意 。释放被调函数的数据区 用递归调用的结果， ,现场恢复：返国 不关注结果如何 获得的嘲节 32/50 图 3.3栈与递归的实现-递归实现 3.,3栈与递归的实现递归/回湖 ■递归过程与递归工作栈 。递归与回湖一N皇后问题 实陈的系就中，一兼统一处理递归调用布非递归调用 。回溯是按照某种条件往前试探搜案，若前进中 。递归工作栈 遭到失败则回过头来另择通路继续搜索. ,活动记录（栈帧stack frame) ,N皇后问题 实在参数、局部变量、上一层的远回地址 在n行m列的国际象棋拱盘上，若两个皇后 ·每进入一层递归，产生一个新的工作记录入栈 位于同一行、同一列或同一对角线上，则称 ·每退出一层递归，就从栈顶弹出一个工作记录 为它们为互相攻击。 ·当前执行层的工作记录必是找顶记录 n皇后问题是指： ■例子：P57 hanoi(3,a,b,c) 找到这n个皇后的互不攻击的布局 33/50 图 34/50 图 3.3栈与递归的实现-N皇后问题 3.3栈与递归的实现-N皇后问题 k=i+j 0#次对角线 -1#次对角线 ·基本思略 2#次时角战 依次为每一行确定读行里后的合法位置 0 3#次对角线 ,安放第i行直后时，需要在列的方向从0到l 4#次对角线 5#次时角线 沈探(j■0，，n-1) 6#次对角线 ,在第j列安放一个皇后 ·如果在列、主对角线、次对角线方向有其它皇 -0#主时角战 后，则出现攻击，撒消在第列安放的皇后： 3☒X☒ 1#主对角战 ,2#主对角线 如果没有出现攻击，在第j列安放的皇后不动 3#主对角线 递归安放第+1行业后 n+i-j- ,4#主对角战 5种主时角战 。如果第1行不能安放直后，则田满到第i1行，从 35750 6#主对角线 图 下一个列G+1愧埃兹每 图 6

6 31/50 3.3 栈与递归的实现–Hanoi塔 „ 问题求解是递归的—Hanoi塔 void hanoi(int n, char a, char b, char c) n-圆盘数 a-源塔座 b-中介塔座 c-目标塔座 „ 搬动方法 „ n=1, a->c „ n>1: hanoi(n-1, a, c, b) a->c hanoi(n-1, b, a, c) „ 注意 用递归调用的结果， 不关注该结果如何 获得的细节 32/50 3.3 栈与递归的实现–递归实现 „ 调用函数与被调用函数---系统工作栈 „ 执行被调用函数前 „ 现场保护：实在参数、返回地址 „ 为被调用函数的局部变量分配存储区 „ 将控制转移到被调函数的入口 „ 从被调用函数返回调用函数前 „ 保存被调函数的计算结果 „ 释放被调函数的数据区 „ 现场恢复：返回 33/50 3.3 栈与递归的实现–递归实现 „ 递归过程与递归工作栈 实际的系统中，一般统一处理递归调用和非递归调用 „ 递归工作栈 „ 活动记录(栈帧stack frame) 实在参数、局部变量、上一层的返回地址 „ 每进入一层递归，产生一个新的工作记录入栈 „ 每退出一层递归，就从栈顶弹出一个工作记录 „ 当前执行层的工作记录必是栈顶记录 „ 例子：P57 hanoi(3,a,b,c) 34/50 3.3 栈与递归的实现–递归/回溯 „ 递归与回溯—N皇后问题 „ 回溯是按照某种条件往前试探搜索,若前进中 遭到失败,则回过头来另择通路继续搜索. „ N皇后问题 在n行n列的国际象棋棋盘上，若两个皇后 位于同一行、同一列或同一对角线上，则称 为它们为互相攻击。 n皇后问题是指： 找到这 n 个皇后的互不攻击的布局 35/50 3.3 栈与递归的实现–N皇后问题 ♛ ♛ ♛ ♛ 1#主对角线 0 1 2 3 0 1 2 3 k = i+j k = n+i-j-1 0#主对角线 2#主对角线 4#主对角线 6#主对角线 3#主对角线 5#主对角线 1#次对角线 3#次对角线 0#次对角线 2#次对角线 4#次对角线 6#次对角线 5#次对角线 36/50 3.3 栈与递归的实现–N皇后问题 „ 基本思路 依次为每一行确定该行皇后的合法位置 „ 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) „ 在第 j 列安放一个皇后 „ 如果在列、主对角线、次对角线方向有其它皇 后，则出现攻击，撤消在第 j 列安放的皇后： „ 如果没有出现攻击，在第 j 列安放的皇后不动 递归安放第 i+1行皇后 „ 如果第 i 行不能安放皇后，则回溯到第 i-1 行，从 下一个列(j+1)继续试探

3.3栈与递归的实现-N皇后问题 3.3栈与递归的实现-N皇后问题 ·数据结构设计 ,数据结构设计 :标识每一列是否巴整安放了重后 。标汉每一列是否已经安放了皇后 线性表，表长为N —顺序表col,表长为N ,标议各条主对角战是否已经安放了复后 标识各条主对角线是否已经安放了直后 一线性表，表长为2N-1 一顺序表md,表长为2N-1 ,标识各条次对角线是香已经安放了重后 线性表，表长为2N-1 ,桥识各条次对角线是否已经安放了重后 。记录当前各行的皇后在第几列一布局状况 —顺序表sd,表长为2N-1 一线性表，表长为N ,花录当前各行的皇后在第几列一布局状况 。存储结构的选择 -顺序表q,表长为N 表长田定，有随机歌的要求—顺序表 回 38/50 图 3.3栈与递归的实现-N皇后问题 3.4队列 ,算法 ■定义 colljl-1; Queen(int i,int n){ colljl 特珠的线性表：操作受限 &&!mdln+i-j-1] mdln+i-j-1l-1; (int j=0;j%t,a∈D,2,3,…n} GetHead(Q.&e 基本操作： 切蹈条件：风列Q已存在且垂空 InitQueue(&Q) 操作结果：用：返回Q中队头元素 操作结果：构造一个空队列Q 切路条件：队列Q已存在Listinsert(&L,山c EnQueue(&Q.eD DestroyQueue(&Q) 初始条件：队列Q已存在 操作结果：插入元素•为Q的新的队尾元素 操作结果：销级队列Q ClearQueue(&Q) 初始条种：队列Q已存在且非空ListDelete(&L,i&e】 初始条件：队列Q已存在 操作结果：副除Q的队头元素，并用。返国其值 操作结果：将队列Q重置为空队列 Queue Traverse(Q.visit() 初始条件：队列Q已存在且非空 QueueEmpty(QD 初需桑件：队列Q己存在 操作结果：从队头到队尾依次对Q的每个数据元素调用函数0， 操作结果：若Q为空队列，则返回TRE,否则返回FALSE 旦0失，则操作失 ADT Queue. QueueLength(Q) 初始条件：队列Q已存在 操作结果：返回队列Q中数据元素的个 41/50 图 42/50 回 7

7 37/50 3.3 栈与递归的实现–N皇后问题 „ 数据结构设计 „ 标识每一列是否已经安放了皇后 ——线性表，表长为N „ 标识各条主对角线是否已经安放了皇后 ——线性表，表长为2N-1 „ 标识各条次对角线是否已经安放了皇后 ——线性表，表长为2N-1 „ 记录当前各行的皇后在第几列—布局状况 ——线性表，表长为N „ 存储结构的选择 表长固定，有随机存取的要求——顺序表 38/50 3.3 栈与递归的实现–N皇后问题 „ 数据结构设计 „ 标识每一列是否已经安放了皇后 ——顺序表col，表长为N „ 标识各条主对角线是否已经安放了皇后 ——顺序表md，表长为2N-1 „ 标识各条次对角线是否已经安放了皇后 ——顺序表sd，表长为2N-1 „ 记录当前各行的皇后在第几列—布局状况 ——顺序表q，表长为N 39/50 3.3 栈与递归的实现–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 列的皇后; } } } !col[j] && !md[n+i-j-1] && !sd[i+j] col[j]= 1; md[n+i-j-1]=1; sd[i+j]=1; q[i] = j; 输出q col[j]= 0; md[n+i-j-1]=0; sd[i+j]=0; q[i] = 0; 40/50 3.4 队列 „ 定义 特殊的线性表：操作受限 只允许在一端进行插入，而在另一端删除元素 允许插入的一端为队尾(rear),允许删除的一端为队头(head) „ 双端队列：限定插入和删除操作在表的两端进行 „ 逻辑特征：先进先出(FIFO) „ ADT Queue：初始化空队、入队、出队、判断队空、判断 队满、取队头 队头 出队 入队 a1 a2 a3 … … an 队尾 41/50 42/50 GetElem(L, i, &e) ListInsert(&L, i, e) ListDelete(&L, i, &e)

栈与队列的概念运用 3.4队列-链队列的表示与实现 ■问题2：设栈S和队列Q的初态均为空， ■链队列 将元素1,2,3,4,5,6依次入栈S,一元素 ,约定与类型定义：Q.front和Q.rear的含义 出栈后即进入队列Q,若这6个元素出队 typedef struct QNodef ElemType data: 次序是4,6,5,3,2,1，则栈S至少应能容纳多 struct QNode "next; 少个元素？ }QNode,*QueuePtr: 答案：5 typedef struct{ QueuePtr frot;P队头指针，指向头元素 QueuePtr rear;队思指针，指向队尾元素 654321 ·123564 }LinkQueue; 43/50 回 44/50 图 3.4队列-链队列的表示与实现 3.4队列-循环队列 ■链队列 ·循环队列 出队 入队 ,基本操作的实现 ·队列的顺序存储 Q.front 队尾 ·无队满问题（除非分影不出内存），空间可扩充 ,的定与类型定义：Q.ront和Q.rear的含义 Q.rear ,引入头结点（一定需要吗？） #define MAXQSIZE100P量大队列长度/ typedef struct ElemType base;P存情空间 4a□ int front:;”头指针，指向队列的头元素y int rear;P尾指针， 指向队见元案的下一个位量 Q.front }SqQueue;P非增量式的空间分配1 Q.rear 。副除：遵免大量的移动争头指针增1 45/50 图 46/50 图 3.4队列-循环队列 3.4队列-循环队列 ,队列的顺序存储出队 循环队列 入队 Q.front 队尾 ·假上滋的解决办法 ,盖本操作的实现 Q.rear 把顺序队列看成首尾相接的环（钟表）一循环队列 .初始化空队：Q.front=Q.rear=0; 基本操作的实现 :入队：判断是否队满：非队满时，Q.rear位置放新插 入的元素，Q.rear++ 入队：，Q.rear=(Q.rear+1%MAXQSIZE 出队：判断是否队空，非队空时，Q.ront位量为特测 出队：，Q.front=(Q.front+-1)%MAXQSIZE 除的元廉，Q.front-++ 队空条件，Q.front==Q.rear ,队空条件，Q.front==Q.rear 由于出队Q.ront道上了Q.rear ,队满条件，Q.rear==MAXQSIZE 队满条件：Q.front==Q.rear 问题：假上滋 由于入队Q.rear遭上了Q.front 47/50 图 问惠：队空和队清的质条件一样 图 8

8 43/50 栈与队列的概念运用 „ 问题2：设栈S和队列Q的初态均为空， 将元素1, 2, 3, 4, 5, 6依次入栈S，一元素 出栈后即进入队列Q，若这6个元素出队 次序是4,6,5,3,2,1，则栈S至少应能容纳多 少个元素？ 6 5 4 3 2 1 1 2 3 5 6 4 1 2 3 45 6 答案：5 44/50 3.4 队列–链队列的表示与实现 „ 链队列 „ 约定与类型定义：Q.front和Q.rear的含义 typedef struct QNode{ ElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; /* 队头指针，指向头元素*/ QueuePtr rear; /* 队尾指针，指向队尾元素*/ }LinkQueue; 45/50 3.4 队列–链队列的表示与实现 „ 链队列 „ 基本操作的实现 „ 无队满问题(除非分配不出内存), 空间可扩充 „ 引入头结点(一定需要吗？) topa1 a2 an ^ Q.front Q.rear 46/50 3.4 队列–循环队列 „ 循环队列 „ 队列的顺序存储 „ 约定与类型定义：Q.front和Q.rear的含义 #define MAXQSIZE 100 /* 最大队列长度 */ typedef struct{ ElemType *base; /* 存储空间 */ int front; /* 头指针，指向队列的头元素 */ int rear; /* 尾指针， 指向队尾元素的下一个位置 */ }SqQueue; /* 非增量式的空间分配 */ „ 删除：避免大量的移动Î头指针增1 Q.front 出队 入队 a1 a2 a3 … … an Q.rear 队尾 47/50 3.4 队列–循环队列 „ 队列的顺序存储 „ 基本操作的实现 „ 初始化空队：Q.front=Q.rear=0; „ 入队：判断是否队满；非队满时，Q.rear位置放新插 入的元素，Q.rear++ „ 出队：判断是否队空，非队空时，Q.front位置为待删 除的元素，Q.front++ „ 队空条件：Q.front == Q.rear „ 队满条件：Q.rear == MAXQSIZE 问题：假上溢 Q.front 出队 入队 a1 a2 a3 … … an Q.rear 队尾 48/50 3.4 队列–循环队列 „ 循环队列 „ 假上溢的解决办法 把顺序队列看成首尾相接的环(钟表)-循环队列 „ 基本操作的实现 „ 入队：……，Q.rear = ( Q.rear+1)%MAXQSIZE „ 出队：……，Q.front = ( Q.front+1)%MAXQSIZE „ 队空条件：Q.front == Q.rear 由于出队Q.front追上了Q.rear „ 队满条件：Q.front == Q.rear 由于入队Q.rear追上了Q.front 问题：队空和队满的判断条件一样

3.4队列-循环队列 3.4队列-循环队列 ,循环队列 。区分队空和队满的方法 ,约定：Q.front和Q.rear(队尾的下一个)的含义 有堆护】，设标志位（上次的更新动作）：0-创建/则除，1-插入 ,队空：Q.front==Q.rear一蜘何区分队空泰队满？门 的代价？引入队列长度 ,队满：Q.front==Q.rear 。少用一个元素空间： 插入前判断Q.front==(Q.rear+1)%MAXQSIZE Q.front 1 4 Q.rear Q.front 1 Q0进a 0 Q.rear 6 49/50 回 50/50 7 图 3.4队列-循环队列 3.5离散事件模拟 ,难点 连续的存单元的上下界：[d1,d2] 问题描述P65 计算一关中客户在银行逗留的平均时间 ,初始化空队：Q.front=Q.rear=d1; ■数据结构设计 ,队空：Q.front=-=Q.rear ·四个窗口一四个队列 .队满：Q.front==(Q.rear-d1+1)%(d2-d1+1)+d1 。客户 ■入队：前提：队列不满 到达时刻 ·离开时刘办理业务所需的时间，等特时间) Q.base[Q.rear]e; ·喜件表：事件驱动 Q.rear =(Q.rear-d1+1)%(d2-d1+1)+d1; ■出队：前提：队列不空 华所合元少的队、产生 e Q.base[Q.front]; .客护高开件（区分个窗） 。事件：事件类型、事件发生时刻 Q.front =(Q.front-d1+1)%(d2-d1+1)+d1 51/50 固 52/50 图 9

9 49/50 3.4 队列–循环队列 „ 循环队列 „ 约定：Q.front和Q.rear(队尾的下一个)的含义 „ 队空：Q.front==Q.rear „ 队满：Q.front==Q.rear 0 1 7 2 3 4 5 6 Q.front Q.rear 0 1 7 2 3 4 5 6 Q.front Q.rear a1 a2 a3 a4 a5 如何区分队空和队满？ 0 1 7 2 3 4 5 6 Q.front Q.rear a1 a2 a3 a4 a5 a6 a7 a8 50/50 3.4 队列–循环队列 „ 区分队空和队满的方法 „ 设标志位(上次的更新动作)：0-创建/删除，1-插入 „ 引入队列长度 „ 少用一个元素空间： 插入前判断 Q.front==(Q.rear+1)%MAXQSIZE 0 1 7 2 3 4 5 6 Q.front Q.rear 0 1 7 2 3 4 5 6 Q.front Q.rear a1 a2 a3 a4 a5 a6 a7 有维护 的代价 51/50 3.4 队列–循环队列 „ 难点 连续的存储单元的上下界：[d1,d2] „ 初始化空队：Q.front = Q.rear = d1; „ 队空：Q.front==Q.rear „ 队满：Q.front==(Q.rear-d1+1)%(d2-d1+1)+d1 „ 入队： 前提：队列不满 Q.base[Q.rear] = e; Q.rear = (Q.rear-d1+1)%(d2-d1+1)+d1; „ 出队：前提：队列不空 e = Q.base[Q.front]; Q.front = (Q. front-d1+1)%(d2-d1+1)+d1 52/50 3.5 离散事件模拟 „ 问题描述 P65 计算一天中客户在银行逗留的平均时间 „ 数据结构设计 „ 四个窗口---- 四个队列 „ 客户 „ 到达时刻 „ 离开时刻(办理业务所需的时间，等待时间) „ 事件表：事件驱动 „ 客户到达事件：入队(选择所含元素最少的队列)、产生离 开事件插入到事件表中 „ 客户离开事件(区分是哪个窗口) „ 事件：事件类型、事件发生时刻