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

201447 指针与引用 指针与引用 ■◆数传递 ■概念 零指针传 ◆指针从本质上讲就是存放变量地址的一个变县 在逻携上是独立的，它可以披改变，包括基 所指向的地址的改变和其指向的地址中所存放 的数据的改变。 。引用是一个别名，它在逻辑上不是独立的， 它 的存在具有依附性，所以引用必须在一开女 科翼宋能版文的（百瑞宝致精 被初始化：而且其引用的对像在其整个生命 个变量) 指针与引用 指针与引用 ·总结 ◆相同点： ■编译的角度 乡都是地址的振意) 指针指向一峡内存，它的内毫是所指内存的地址；而引用侧是菜块内存的别 ◆程序在编泽时分别将指针和引用添加到符号表 符号表上记录的是变量名及变量所对应地 ◆不同点1 上 。指针变量在符号表上对应的地址值为指针 产指针是一个实体，而引用仅量个别名： 引用只能在定义时被初始化一次，之后不可变：抛针可变：引用“从一而络 变量的地址值，而引用在符号表上对应的地址 ,指针河以“见异息迁”， 值为引用对象的地址值。符号表生成后就不会 引用没有c。 指针有const,cons的指针不可度，（具体指有nt nsta种形式，而const int这a有 指引本身即名不可 再改，因此指针可以改变其指向的对象（指针 以改变，这是当然的，所以不需要这种形式，后者指引用所的值不可以改 海》 变量中的值可以改)，而引用对象则不能修放 引用不能为空，指针可以为空： 28of引用”得到的是所指向的变量对像的大小，而“s2Eof指针”得到 的是指针本鼻的大小： 指针和引用的户增+漫算童义不一样； 引用量类型安全的，而物针不是引用比指针多了类世查 83.1栈 数据结构 ■定义和运算 ◆栈—仅在表的一端插、副的操作受限)线性表 擂入—进（入）找、膝一—出（退）找 Ch.3栈和队列 ◆栈顶—一插副的一端 ◆栈底一另一端 计算机学院 肖明军 结构特征一“后进先出” 修改原则：退烛者总是量近入找者 Email:xiaomj@ustc.edu.cn 服务原则：后来者先服务（山FO瘦） 例a1,a2,·.·,an 入栈 http://staff.ustc.edu.cn/-xiaomj Cn,0n-1,···,a1 出栈

2014/4/7 1 指针与引用 概念 指针从本质上讲就是存放变量地址 的一个变量 ，在逻辑上是独立的，它可以被改变，包括其 所指向的地址的改变和其指向的地址中所存放 的 的变 数据 改 。 引用是一个别名，它在逻辑上不是独立的，它 的存在具有依附性，所以引用必须在一开始就 被初始化，而且其引用的对象在其整个生命周 期中是不能被改变的（自始至终只能依附于同 一个变量）。 指针与引用  参数传递  指针传递参数本质上是值传递的方式，它所传递 的是一个地址值。值 传递过程中，被调函数的形式参数作为被调函数的局部变量处理，即 在栈中开辟了内存空间以存放由主调函数放进来的实参的值，从而成 为了实 参的一个副本。值传递的特点是被调函数对形式参数的任何操 作都是作为局部变量进行，不会影响主调函数的实参变量的值。（这 里是在说实参指针本身的地址值不会变）  在引用传递过程中，被调函数的形式参数虽然 也作为局部变量在栈中 开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的 地址。被调函数对形参的任何操作都被处理成间接寻址，即通过栈中 存放 的地址访问主调函数中的实参变量。正因为如此，被调函数对形 参做的任何操作都影响了主调函数中的实参变量。  引用传递和指针传递是不同的，虽然它们都是在 被调函数栈空间上的 一个局部变量，但是任何对于引用参数的处理都会通过一个间接寻址 的方式操作到主调函数中的相关变量。而对于指针传递的参数，如果 改变被调函数中的指针地址，它将影响不到主调函数的相关变量。如 果想通过指针参数传递来改变主调函数中的相关变量，那就得使用指 向指针的指针，或者指针引用。 指针与引用 编译的角度 程序在编译时分别将指针和引用添加到符号表 上，符号表上记录的是变量名及变量所对应地 址。指针变量在符号表上对应 的地址值为指针 变量的地址值，而引用在符号表上对应的地址 值为引用对象的地址值。符号表生成后就不会 再改，因此指针可以改变其指向的对象（指针 变量中的值 可以改），而引用对象则不能修改 。 指针与引用  总结  相同点：  都是地址的概念；  指针指向一块内存，它的内容是所指内存 的地址；而引用则是某块内存的别 名。  不同点：  指针是一个实体，而引用仅是个别名；  引用只能在定义时被初始化 次 引用只能在定义时被初始化一次，之后不可 变；指针可变；引用“从 而终 一 ”，指针可以“见异思迁”；  引用没有const，指针有const，const的指针不可变；（具体指没有int& const a这种形式，而const int& a是有 的， 前者指引用本身即别名不可 以改变，这是当然的，所以不需要这种形式，后者指引用所指的值不可以改 变）  引用不能为空，指针可以为空；  “sizeof 引用”得到的是所指向的变量(对象)的大小，而“sizeof 指针”得到 的是指针本身的大小；  指针和引用的自增(++)运算意义不一样；  引用是类型安全的，而指针不是 (引用比指针多了类型检查 数据结构 Ch.3 栈和队列 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj §3.1 栈 定义和运算 栈 —— 仅在表的一端插、删的(操作受限)线性表 插入——进（入）栈、删除——出（退）栈 栈顶 —— 插删的一端 栈底 —— 另一端 6 栈底 另 端 结构特征 --“后进先出” 修改原则：退栈者总是最近入栈者 服务原则：后来者先服务 （LIFO表） 例： 入栈 出栈 n a 2 a 1 a

2014/47 s3.1栈 s3.1.1顺序找 Note:后入栈者先出栈，但不排除后者未进找， 底相对固定 先入栈者先出栈。 。可设在向量的任一端 Top指针为下标类型（整型量） #define StackSize 100 typedef struct{ DataType data[StackSize]; 基本运算：①判栈空②入栈③出栈④判栈 满⑤读找顶⑥置空栈 int top; )SegStack; s3.1.1顺序栈 §3.1.1顺序栈 ■设栈底在向量低端data0],则： 设如指向当省钱须元 ◆入找：top+1 出栈：top-1 ◆栈空：top<0 具县具县 栈满：top=StackSize-1 ◆上溢：满时入栈 ◆下溢：空时出栈（不一定是错误） Note:top指针不是指物理地址，与C的指针变量 含义不同。可理解为相对地址，是指示元素的所 在位置 §3.1.1顺序栈 83.1.1顺序栈 ■实现： 入栈 ◆初始化（置空栈） void Push(SeqStack &S,DataType x){ void InitStack(SeqStack&S)(l必须引用 if(StackFull(S)) Error("overflow"); S.data[++s.top]F5;∥指针先加1，后x入钱 S.top=-1;} ◆判栈空 出栈 int StacEmpty(SeqStack&s)(l亦可用非引用 DataType Pop(SeqStack &S){ return S.top<0;) if(StackEmpty(S》Error("UnderFlow;I下港 ◆判栈满 return S.data[S.top-小：士返回项后指针减1 int StackFull (SeqStack &S)( 。读栈顶 return S.top==StackSize-1;) ■两个找共享空间 2

2014/4/7 2 §3.1 栈 Note:后入栈者先出栈，但不排除后者未进栈， 先入栈者先出栈。 2 1 ,,, n a aa  7 基本运算：① 判栈空 ②入栈 ③出栈 ④判栈 满 ⑤读栈顶 ⑥置空栈 §3.1.1 顺序栈 底相对固定 可设在向量的任一端 Top指针为下标类型 (整型量) #define StackSize 100 8 typedef struct { DataType data[StackSize]; int top; }SeqStack; 设栈底在向量低端data[0]，则： 入栈 ：top+1 出栈：top-1 栈空：top<0 §3.1.1 顺序栈 栈空：top<0 栈满：top=StackSize-1 上溢：满时入栈 下溢：空时出栈(不一定是错误) 9 §3.1.1 顺序栈 10 Note：top指针不是指物理地址，与C的指针变量 含义不同。可理解为相对地址，是指示元素的所 在位置 § 3.1.1 顺序栈 实现： 初始化 （置空栈） void InitStack(SeqStack &S) { //必须引用 S.top=-1; }  判栈空 11 int StacEmpty(SeqStack &S) { //亦可用非引用 return S.top<0;}  判栈满 int StackFull (SeqStack &S) { return S.top==StackSize-1;} § 3.1.1 顺序栈 入栈 void Push(SeqStack &S, DataType x) { if(StackFull(S)) Error(“overflow”); S.data[++S.top]=s; // 指针先加1，后x入栈 } 出栈 12 DataType Pop(SeqStack &S) { if(StackEmpty(S)) Error(“UnderFlow”); //下溢 return S.data[S.top--]; //返回栈顶后指针减1 } 读栈顶  两个栈共享空间

201447 §3.1.2链栈 s3.1.2链栈 ■只在表头操作，故头指针即为op,无需头结点 void InitStack(LinkStack &S){ S.top=Null; 定义 typedef struct snode{ int StackEmpty (LinkStack &S){ DataType data; return S.top==NULL; struct snode'next; }StackNode; void Push(LinkStack &S,DataType x){ typedef struct( StackNode 'p=(StackNode")malloc(sizeof(StackNode)); StackNode 'top; p>data=x; }LinkStack; p>next=s.top; s.top=p; ■链找动态分配结点，无需考虑上溢 s3.1.2链找 §3.2队列 DataType Pop(LinkStack &S){ 1,定义 DataType x; ◆队列：运算受限的线性表，一端插入（队尾），另一端」 StackNode 'p=S.top; 除（队头）。 if(StackEmpty(S》 ◆结构特征： Error"underflow":∥下溢 x=p>data; ,先进先出，先来先服务，FFO表 S.top=p->next; ◆例子：排队现象 free(p); 操作： return x粉 入队播入)序列：a1···an 出队除序列：a1···an 83.2队列 83.2队列 2顺序队列一队列的顺序存储结构 ◆上滋：队满时入队 ◆空队列：front=rear;初值为0 ◆下滋：队空是出队（不一定是错误，可能是转移控 ◆入队：插入rear位置，然后加1 制条件)】 ◆出队：去front)所指元素，然后加1 ◆伪上滋：队非满但不能插入 ,头指针什ot物向实际队头元素 原因：{，「只不城 ,尾指针er指向实际队属元赛的下一个位量 例如：入，出，入，出， AB C 尽管任一时制，队中量多只有1个元凛，但无论事先定义 deet: 地 多大的空间，均会产生指针越界 6123 (eA 3

2014/4/7 3 § 3.1.2 链栈 只在表头操作，故头指针即为top，无需头结点 定义 typedef struct snode { DataType data; t t d* t 13 struct snode *next; } StackNode; typedef struct { StackNode *top; } LinkStack; 链栈动态分配结点，无需考虑上溢 § 3.1.2 链栈  void InitStack(LinkStack &S) { S.top=Null; }  int StackEmpty (LinkStack &S) { return S.top==NULL; } 14  void Push(LinkStack &S, DataType x) { StackNode *p=(StackNode*) malloc (sizeof(StackNode)); p->data=x; p->next=s.top; s.top=p; } § 3.1.2 链栈  DataType Pop(LinkStack &S) { DataType x; StackNode *p=S.top; if(StackEmpty(S)) Error (“underflow”); // 下溢 x=p->data; 15 x p S.top=p->next; free(p); return x; } §3.2 队列 1. 定义 队列：运算受限的线性表，一端插入(队尾)，另一端删 除(队头)。 结构特征： 先进先出，先来先服务，FIFO表 16 例子：排队现象 操作： 入队(插入)序列： 出队(删除)序列： § 3.2 队列 2. 顺序队列 —— 队列的顺序存储结构 空队列：front = rear； 初值为0 入队：插入rear位置，然后加1 出队：删去front所指元素，然后加1 头指针 front 指向实际队头元素 17 指向实际队头元素 尾指针 rear 指向实际队尾元素的下一个位置 § 3.2 队列 上溢：队满时入队 下溢：队空是出队 (不一定是错误，可能是转移控 制条件) 伪上溢：队非满但不能插入 原因：f，r 只增不减 18 例如：入，出，入，出，…… 尽管任一时刻，队中最多只有1个元素，但无论事先定义 多大的空间，均会产生指针越界

20147 §3.2队列 s32队列 ◆怎样消除伪上溢？ ◆边界问题 队满和队空时，ront=rear,如何区分？解决方法 ①设一布尔量以示区分 ,r在须环定义下的加1助作 留一个结点不用。约定 越界时，今其指向下界0 入队前，测试尾指针+1（循环定义下）是否等于头指 i=(t1=QueueSize)?0:#1;∥i为frontl或rear 针。若相等测为满 可用模运算前化： ③使用个计数围，记录队列长度（用此法） =(i+1)%QueueSize: #define QueueSize 100 。循环队列： typedef struct{ int front; 实用顺序队列多为循 int rear; int count; 环队列 DataType data [QueueSize]; CirQueue; §3.2队列 §3.2队列 ◆操作实现 入队 置空队 void EnQueue(CirQueue &Q,DataType x){ void InitQueue (CirQueue &Q){ if (QueueFull (Q)) Q.front =Q.rear =0: Error("overflow");//上溢 Q.count++: Q.count=0;∥队空 Q.data[Q.rear]=x;∥入 Q.rear=(Q.rear+1)%QueueSize;∥指针加t 判队空 int QueueEmpty (CirQueue &Q){ 出队 return Q.count==0; DataType DeQueue (CirQueue &Q){ if(QueueEmpty(Q) Erro rhow":/下溢，不一定是蜡 int QueueFull (CirQueue &Q){ temp=Q.data[.fron return Q.count ==QueueSize; Q.count--; Q.front=(Q.front+1)%QueueSize; return temp; 83.2队列 83.2队列 3. 链队列 void InitQueue (LinkQueue &Q){ Q.front=Q.rear=NULL;有头结点是不同 仅限于在表头和尾插侧的单链表 不带头节点 int QEmpty (LinkQueue&Q)(l凭上溢，故不判满队 typedef struct qnode( return o.front=NULL;∥头愿指针均为空，有头轴点时f=r DataType data; struct qnode 'next: void EnQueue (LinkQueue &Q,DataType x){ }QNode; (a空队列 QNode 'p =(QNode")malloc(sizeof(QNode)); p->data=x:p->next=NULL;∥新结点作为新的队见 计(Q.Empy(Q)）∥若有头结点无需判此项 typedef struct Q fron Q.front-=Q.rear=p∥入空队 QNode 'front; se{∥滑入非空队凰，有无头结点均要徽此项 QNode 'rear; Q.rear->next=p;∥“p链到眼具轴点之后， }LinkQueue; Q.rear=p:∥指向新属p

2014/4/7 4 § 3.2 队列 怎样消除伪上溢？ 重复利用已删除的结点空间，将向量视为首尾相接的环。 这种用循环向量实现的队列称为循环队列。 f，r在循环定义下的加1动作： 越界时，令其指向下界0 i = (i+1==QueueSize) ? 0:i+1; // i为front或rear 19 可用模运算简化： i=(i+1)%QueueSize; 循环队列： 实用顺序队列多为循 环队列 § 3.2 队列 边界问题 队满和队空时，front=rear，如何区分？解决方法： ① 设一布尔量以示区分 ② 留一个结点不用。约定 入队前，测试尾指针+1 (循环定义下) 是否等于头指 针。若相等则为满 20 ③ 使用1个计数器，记录队列长度 （用此法） #define QueueSize 100 typedef struct { int front; int rear; int count; DataType data [QueueSize]; } CirQueue; § 3.2 队列 操作实现 置空队 void InitQueue (CirQueue &Q) { Q.front = Q.rear = 0; Q.count = 0; // 队空 } 判队空 21 int QueueEmpty (CirQueue &Q) { return Q.count == 0; } 判队满 int QueueFull (CirQueue &Q) { return Q.count ==QueueSize; } § 3.2 队列 入队 void EnQueue (CirQueue &Q, DataType x) { if (QueueFull (Q) ) Error(“overflow”); //上溢 Q.count++; Q.data [Q.rear] = x; // 插入 Q.rear = (Q.rear+1)%QueueSize; // 尾指针加1 } 22 出队 DataType DeQueue (CirQueue &Q) { if(QueueEmpty (Q) ) Error (“underflow”); //下溢，不一定是错 temp = Q.data[Q.front]; Q.count--; Q.front= (Q.front+1)%QueueSize; return temp; } § 3.2 队列 3. 链队列 仅限于在表头和尾插删的单链表 typedef struct qnode{ DataType data; struct qnode *next; *Q 不带头节点： 23 }QNode; typedef struct { QNode *front; QNode *rear; } LinkQueue; （a） 空队列 1a n a § 3.2 队列 void InitQueue (LinkQueue &Q) { Q.front = Q.rear = NULL; //有头结点是不同 } int QEmpty (LinkQueue &Q) { //无上溢，故不判满队 return Q.front == NULL; // 头尾指针均为空，有头结点时 f = r } void EnQueue (LinkQueue &Q, DataType x) { 24 QNode *p = (QNode*) malloc( sizeof(QNode) ); p->data = x; p->next = NULL; // 新结点作为新的队尾 if (Q.Empty(Q) ) // 若有头结点无需判此项 Q.front = Q.rear = p; // 插入空队 else { // 插入非空队尾，有无头结点均要做此项 Q.rear->next = p; // *p链到原尾结点之后。 Q.rear = p; // 指向新尾*p } }

201447 §3.2队列 §3.3栈和队列的应用 DataType DeQueue(LinkQueue &Q){ S3.3.1找的应用 if QEmpty(Q)) 1数据转换 Eror('underflow;下港 问题：一非负十进制整数N→基为B的B进制数 p=Q.front;;∥指向队头 例： x=p->data; 280=88+480=34 2810=34 720=1·4+0-42+2-4+0-P=1021 Q.front=p->next∥队头摘下 f(Q.rear=p)∥原队中只有一个结点，去后队变空 规辣：N= 0≤≤B-1 (3.1) Q.rear=NULL; 其中山表示B进制数的第位敷字 free(p); 十进制数N可用长度为oga N门+1位B进制数表示为 return x; b1ogaN1…b2bbo s3.3.1栈的应用 §3.3.1栈的应用 ◆如何确定：？ 例蜘：V=353点6741 令.N则(3.1)式为： N=bB+-1B卡+b1B+玩 =(B1+b-B-”+…+2B+)B+ (3.2) (3.2)式整除B,则余数为bn商为括号内的和式。故(3.2)式 6 可表达为： N=(N/B)·B+N%B∥“为整除 ◆算法思想： 01 0 1 ①障求余数：N%B÷咖 雪整珠求商：WB,令此为新的N,量复①求b,反复至某N为0时的桌 8=1 44 空程 58-7 68-6 上述过程依次求出的B进制各位为（从低位至高位）：，们，·， N8-444 4448-55 55/86 6/80 用转保存，退找输出，而-1，-·，2，，即为所求。 N3553 为44 N55 N-0 s3.3.1栈的应用 s3.3.1栈的应用 实现 typedef int DataTyper 2栈与递归 void MultiBaseOutput (int N,int B){ ∥N为非负十进制整数，B为基 int SeqStack S:序s ◆递归是一种强有力的数学工具，可使问 InitStack(SM置空找 题的描述和求解变得简洁与清晰 R心sN将4Xar while(N{l从右向左产生色，i=0,1, N=N/B: 递归：若一函数、过程或数据结构定义 的内部又直接或间接使用定义本身，则 while(IStackEmpty(S》(∥t钱s非空 称它们是递归的，或递归定义的 i=Pop(S); printf(“%d”,店 时间复杂度O(logN门 5

2014/4/7 5 § 3.2 队列 DataType DeQueue (LinkQueue &Q) { if ( QEmpty(Q) ) Error (“underflow”); //下溢 p = Q.front; // 指向队头 x = p->data; 25 Q.front = p->next; // 队头摘下 if (Q.rear == p) // 原队中只有一个结点，删去后队变空 Q.rear = NULL; free (p) ; return x; } § 3.3 栈和队列的应用 § 3.3.1 栈的应用 1.数据转换  问题： 一非负十进制整数N 基为B的B进制数 例： 26 规律： （3.1） 其中 表示B进制数的第 i 位数字 十进制数N可用长度为 位B进制数表示为 bi §3.3.1 栈的应用 如何确定 ？ 令 ，则（3.1）式为： （3.2） (3.2)式整除B，则余数为 ，商为括号内的和式。故 (3.2)式 可表达为： 27 // “/”为整除 算法思想： ① 模除求余数： ② 整除求商：N/B，令此为新的N，重复①求 ，反复至某N为0时结束 上述过程依次求出的B进制各位为(从低位至高位): 用栈保存，退栈输出 即为所求。 § 3.3.1 栈的应用 例如： 28 § 3.3.1 栈的应用  实现 typedef int DataType； void MultiBaseOutput (int N, int B) { // N为非负十进制整数， B为基 int i; SeqStack S; //顺序栈S InitStack(S); //置空栈 while (N) { //从右向左产生bi , i=0,1, …, j push(S, N%B); // 将 bi 入栈 29 N=N/B; } while( !StackEmpty(S)) { // 栈S非空 i = Pop(S); printf(“%d”,i); } } 时间复杂度 § 3.3.1 栈的应用 2.栈与递归 递归是一种强有力的数学工具，可使问 题的描述和求解变得简洁与清晰 递归：若一函数、过程或数据结构定义 30 递归：若 函数、过程或数据结构定义 的内部又直接或间接使用定义本身，则 称它们是递归的，或递归定义的

20147 §3.31栈的应用 §3.3.1栈的应用 ,递归算法设计（分治法）分解、求、想合 例2： step1:将原问题分解为个或多个规模文小，但与原 有能问■速事上不色当归定义的，包可过分桥，轴维社迪归的虚义。 问题特性类似的子问题（递归步鼎）∥解子问题 写一个就地生成n个元素a1,·,aa-1,an全排列(n叫的填法，要求算法 为调用语句 step2:确定一个或多个无须分解，可直接求解的最小子 线止时保持a1,,am-1,an原状 问题（终结条件）∥归纳基础 解：设A0n-刂基类型为char,“就地(in place)"不允许使用A以外的数组 例1： 1 =0 n! 道归蜂结条件 ①生成a1,…,an-1an金排列分 >n个子问厘 n(n-1)n>0 递归步漂年领情比小 个元素的今津判十联个元者 wt子问遇a,“,an1 intF(intn)(/设n为非负整数 …,24 ar-1 //A[m-1]An] if (n==0) …a 2e2IHA回l else ∥A)HAnl return n'F(n-);分算为个，e, /ACE]AT] §3.3.1栈的应用 §3.3.1栈的应用 雪道归终结分支 算法时间分析： 当=1时，一个元素全排列只有一种，即为本身。实际上无须进 O(2”)0;-){ 时刻不能将大盘压在小 Swap(A可，Anj:∥交换Qn和ai内客，为用 Permute(A,n-1片∥求A0.n-1)全排列 Swap(A0,A[njh:I交换 用1栈的应用 s33.1栈的应用 分解 设n>1 递归的内部实现 原问厘：将n片从X移到Z,Y为辅助塔，可分解为： ①调用 将上面n-1个盘从X移至Y,Z为轴助盘 调用一个西数时，系统将为调用青者构造一个活动记录，并将其压 将nth片从X移至Z 入找的顶，然后 海序控权转整到被调用西，若故调用西数 在找顶也要为其分空间，形成 将Y上n-1个盘子移至Z,X为轴助盘 际上所有的速归或非归西散这样实现的 ②终结条件 香动销构 都变量 n=1时，直接将编号为1的盘子从X移到z 活动记景：◆数表的内容为实◆ void Hanoi (int n,char x,char y,char z){ 返址为西数调用语向的下一指冷的位夏 ∥n个盘子从X移至Z,Y为辅助 i计(n=1)move(X.1,Z:∥将1号盘子从X移至Z,打=m-一) alse t =- 局部 Hanoi(n-1,x之y:原X,辅，目Y 返址 move (x,n,z); 活动记录 Hanoi(n-1,y,x,2:潭Y,轴X,目Z 参数表 =0g Activation Frame(话动结构) 35 6

2014/4/7 6 § 3.3.1 栈的应用 递归算法设计（分治法）分解、求解、组合 step1： 将原问题分解为一个或多个规模更小，但与原 问题特性类似的子问题 (递归步骤) // 解子问题 为调用语句 step2：确定一个或多个无须分解，可直接求解的最小子 问题 (终结条件) // 归纳基础 例 1： 31 int F (int n) { //设n为非负整 数 if (n==0) return 1; else return n*F(n-1) ; } //递归终结条件 //递归步骤 (n-1)!规模比n!小1 至少有一个直接求解的最小子问题， 保证递归终止，否则无限循环 分解为一个子问题，若F(n)是解n!，则 F(n-1)可解(n-1)! § 3.3.1 栈的应用 例2： 有些问题表面上不是递归定义的，但可通过分析，抽象出递归的定义。 写一个就地生成n个元素 全排列 (n!) 的算法，要求算法 终止时保持 原状 解：设 A[0 ..n-1] 基类型为char,“就地 (in place)”不允许使用 A 以外的数组 分解 32 ① 生成 全排列 n个子问题 分解 § 3.3.1 栈的应用 ② 递归终结分支 当 n=1 时， 一个元素全排列只有一种，即为本身。实际上无须进 一步递归，可直接打印输出A # define N 8 // A[0..7] void permute (char A[], int n) { //外部调用时令 n=7 if(n==0) i t (A) // 打印A[0 7] 33 print (A); // 打印A[0..7] else { Permute(A,n-1); //求A[0..n-1]的全部排列。1st子问题不用交换 for (i=n-1; i>0; i--) { Swap(A[i], A[n]); // 交换 和 内容，说明为引用 Permute(A,n-1); // 求A[0..n-1] 全排列 Swap(A[i],A[n]); //交换 } } } § 3.3.1 栈的应用 算法时间分析： 所以实验时，n不能太大 例3：n阶Hanoi塔问题 将X上的圆盘移到Z上，要求按 同样次序排列，且满足： 34 1.每次只能移动一片 2.圆盘可插在X，Y，Z任一塔 座上 3.任一时刻不能将大盘压在小 盘上 § 3.3.1 栈的应用 ① 分解 设 n>1 原问题：将n片从X移到Z，Y为辅助塔，可分解为： I. 将上面n-1 个盘从X移至Y，Z为辅助盘 II. 将 nth 片从X移至 Z III. 将Y上n-1个盘子移至Z，X为辅助盘 ② 终结条件 n = 1时，直接将编号为1的盘子从 X 移到Z //子问题特征属性与原问 //题相同规模小1，参数不 //同 35 n 1时，直接将编号为1的盘子从 X 移到Z void Hanoi (int n, char x, char y, char z ) { // n个盘子从 X 移至 Z，Y 为辅助 if ( n==1 ) move(X,1,Z); // 将1号盘子从 X 移至 Z, 打印 else { Hanoi (n-1,x,z,y); //源X，辅Z，目Y move (x,n,z); Hanoi (n-1,y,x,z); //源Y，辅X，目Z } } § 3.3.1 栈的应用  递归的内部实现 ① 调用 调用一个函数时，系统将为调用者构造一个活动记录，并将其压 入栈的顶，然后将程序控制权转移到被调用函数。若被调用函数 有局部变量，则在栈顶也要为其分配空间，形成一个活动结构。 实际上所有的递归或非递归函数都是这样实现的 活动结构： 局部变量 活动记录 参数表的内容为实参 36 ： 返址为函数调用语句的下一指令的位置

20147 §3.31栈的应用 §3.3.1栈的应用 ②返回 酸数表 Ret 12 当被调用函执行完毕时，系统将活动结构遇栈，并根 执行返回指令 据退找返回地址将程序控制权转移给调用者罐续执行 F(2) Ret 12 RetL2:temp-*1:从F(0)返回 例：F(4为例 Ret 12 void main(void){ 改写： F() Ret 12 int int F(int n) n-F(所：调用引E博 int temp; Ret Ret LI一 if (ne return I:通自滑间】 用F) else *0l=1是递归终结条件，故执行F(0)引起返回(return1) 用打起入等 Ret LI:置值语句的地址 temp =n*F(n-1): 退找国，返回到F(1)的RetL2处，继续执行temp=11: RetL2:计算乘法的地址 Ret L2 return temp;转 按着执行return temp又引起☑退找，返回到F(2)的Ret 为筒单起见，银设局部变量不入找 L2处，执行temp=2*1,. 3 典型的堆找钠结构如图所示，推钱中存放的是与每个函数对应的维找航。 虽数圆用发生时，新的找航被压入维找 当函致返回时，相应的堆程 航从堆找中出 函数调用示例 Argument n 西数： 偏移为正 Int func(int a,int b){ 函致的实参 int retVal =a+b; Argument1 ◆return retval: 2 Return address 1 依夏前一个堆钱额 Previous frame pointer 所需款居 int main(int argc,char argvo) Ret-add 维找额指计 ebp Local variable 1 int result func(1,2): retVal printf("Hello World n 偏移为负 Local variable 2 Local variable 3 正数的局常变堂 eturn 0; ■EIP指令指针、EBP基址指针、ESP指针维找指针 Local variable n Call DST:SP=SP-2,(SP+1,SP)=IP,IP=IP+Ds RET EXP:IP=(SP+1,SP),SP=SP+2,SP=SP+D, 典型的雌找蘭结构 s3.3.1找的应用 s33.1栈的应用 ◆递归算法的正确性 若P是递归过程，则不可能独立于P来证明被调过程（亦自身） 初学者很难相信递归程序的正确性 是否正确。因此，我们只能假设过程P内部所有递归的调 原因：一个函数尚未完成（即对本函敷的正确性还未确 用是正确的（不考忠其内部实现细节），才能由此证明P的 信时又调用了自身，放对递归函数正确性缺乏 正确性。其理论依据是数学归纳法： ()证明渗数满足递归络结条件时函数或过程正确（相当于归 例：非递归函数或过程 纳基础。 P{ 假设Q正确的情况下，证明了P正确 (2)假设过程函数内部的所有递归调用语句正确（相当于归纳 旦证明了被调过程Q是正确的， 假设)，由此证明过程正确或函数是正确的（相当于归纳步 我们就对的正确性深信不】 由于P、Q各自独立，独立于P来证明 Q的正确性很容易，这大是对自己 州：函内的归调用句的数应比商歌本身的◆数更 写非递归程序较有信心的缘做 较近增归条件◆，这排材能物保增归是可终止的 7

2014/4/7 7 § 3.3.1 栈的应用 ② 返回 当被调用函数执行完毕时，系统将活动结构退栈，并根 据退栈返回地址将程序控制权转移给调用者继续执行 例： F(4)为例 void main(void) { int n; n = F(4); //调用引起压栈 改写： int F (int n) { int temp; if (n==0) 37 } Ret L1 if (n==0) return 1; //返回语句引 起退栈 else { //调用F(n-1) 引起入栈 temp = n*F(n-1); return temp; // 退栈 } Ret L2 Ret L1: 赋值语句的地址 Ret L2: 计算乘法的地址 为简单起见，假设局部变量不入栈 § 3.3.1 栈的应用 执行返回指令 Ret L2: temp=1*1; //从F(0）返回 38 0! = 1 是递归终结条件，故执行F(0)引起返回(return 1) 退栈 , 返回到F(1)的Ret L2处，继续执行temp = 1*1； 按着执行return temp又引起 退栈，返回到F(2)的Ret L2处，执行temp = 2*1，… * 典型的堆栈帧结构如图所示。堆栈中存放的是与每个函数对应的堆栈帧。 当函数调用发生时，新的堆栈帧被压入堆栈；当函数返回时，相应的堆栈 帧从堆栈中弹出。 典型的堆栈帧结构 函数调用示例  函数：  int func(int a, int b){  int retVal = a + b;  return retVal;  } 2 1 R t dd … Stack frame  int main(int argc, char* argv[])  {  int result = func(1, 2);  printf("Hello World!\n");  return 0;  }  EIP(指令指针)、EBP(基址指针)、ESP指针(堆栈指针)  Call DST: SP=SP-2, (SP+1,SP)=IP, IP=IP+D16  RET EXP: IP=(SP+1,SP), SP=SP+2, SP=SP+D16 Ret-add ebp retVal … § 3.3.1 栈的应用 递归算法的正确性 初学者很难相信递归程序的正确性 原因：一个函数尚未完成 (即对本函数的正确性还未确 信) 时又调用了自身，故对递归函数正确性缺乏 信心 例：非递归函数或过程 41 假设Q正确的情况下，证明了P正确， 则一旦证明了被调过程Q是正确的， 我们就对P的正确性深信不疑！ 由于P、Q各自独立，独立于P来证明 Q的正确性很容易，这大概是对自己 写非递归程序较有信心的缘故 § 3.3.1 栈的应用 若P是递归过程，则不可能独立于P来证明被调过程 (亦自身) 是否正确。因此，我们只能假设过程P内部所有递归的调 用是正确的 (不考虑其内部实现细节)，才能由此证明P的 正确性。其理论依据是数学归纳法： (1) 证明参数满足递归终结条件时函数或过程正确 (相当于归 纳基础)。 42 (2)假设过程函数内部的所有递归调用语句正确 (相当于归纳 假设)，由此证明过程正确或函数是正确的 (相当于归纳步 骤) Note: 函数内的递归调用语句的参数应比函数本身的参数更 接近递归终结条件参数，这样才能确保递归是可终止的

2014/47 §3.3.1栈的应用 算符间的优先关系 3.表达式求值 算符优先法： 先乘除，后加碱；从左到右计算；先括号内后括 号外 4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 操作数(operand:变量、常量，进OPND栈 操作符(operator):算术、关系、逻辑运算符，进 OPTR栈 界限符(delimiter)#,（,） Precede:判定运算符楼的找顶运算符6，与读入的运算符B,之间 的优先关系的函数 0 perate:进行二元运算：8b的函数 OperandType EvaluateExpression() (InitStack(OPTR):Push(OPTR,'#) 对算术表达式3*(7-2)求值 InitStack(OPND):c-getchar(: While(e-'w GetTop(OPTR)!-' tlne,OP)Push(OPND,c片c=gcha(OH∥不是运算将进找 步骤OPTR我OPND栈输入字符 主要操作 else 3*(7,2)# Push(OPND,'3) switch(Precede(GetTop(OPTR).c)) 3 *(7-2)# Push(OPTR,'*) ca:∥退械并将远算销果入枝 6 #8(: 33 2)# Push(OPND.2) Pop(OPTR,theta);Pop(OPND.b):Pop(OPND.a): Push(OPND.Operate(a,theta.b)): break: 7 372 Operate(7,2) default:printf(-Expression error!");return(ERROR): 8 35 POP(OPTR) ∥witch ∥whale 33 Operate(3,*,5) return GetTop(OPNDk 15 Return(GetTop(OPND)) §3.3.2队列的应用 83.3.2队列的应用 例：周末舞会，男、女各排成一队，跳舞时，依次从男、 for(i=0;i<num;i++){ 女队的头上各出一人配成舞伴，若两队人数不同，较长的 P=dancer[i]; 队中未配对者等下一轮舞曲 if (P.sex=='M' typedef struct{ EnQueue(Mdancers,PY∥入男队 else char name[20]; EnQueue(Fdancers,P片∥入女队 char sex;:∥M-男，F-女巴 }Person; printf("The dancing partners are:Inin"): typedef person DataType;将队列定义中的最据类过改为Person while (!QueueEmpty(Fdancers)&&IQueueEmpty(Mdancers)){ Ⅱ男女队列均非空 void DancePartners (Person dancer[],int num){ P=DeQueue(Fdancers:∥女士出队 int i;Person P; printf("%s ,P.name时∥女士姓名 CirQueue Mdancers,Fdancers; P=DeQueue(Mdancers};男士出队 InitQueue(Mdancers)∥男士队列 printf("%sIn",P.name); InitQueue(Fdancers); 8

2014/4/7 8 § 3.3.1 栈的应用 3.表达式求值 算符优先法: 先乘除，后加碱；从左到右计算；先括号内后括 号外 43 4+2*3-10/5 = 4+6-10/5 = 10-10/5 =10-2 = 8 操作数(operand): 变量、常量，进OPND栈 操作符(operator): 算术、关系、逻辑运算符，进 OPTR栈 界限符(delimiter): #，（，） 算符间的优先关系: θ1 θ2 +- */ ( ) # + > > > - >>> * >>>><>> / >>>><>> ( >>> >> # ’: // 退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); break; default: printf(“Expression error!”); return(ERROR); } // switch } // while return GetTop(OPND); } // EvaluateExpression 对算术表达式3*(7-2)求值 步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 3 * ( 7 - 2 ) # Push(OPND,’3’) 2 # 3 * ( 7 - 2 ) # Push(OPTR,’*’) 3 # * 3 ( 7 - 2 ) # Push(OPTR,’(’) 4 # * ( 3 7 - 2 ) # Push(OPND,’7’) 5 # * ( 3 7 - 2 ) # Push(OPTR,’-’) 6 # * ( - 3 7 2 ) # Push(OPND,’2’) 7 # * ( - 3 7 2 ) # Operate(‘7’,’-‘,’2’) 8 # * ( 3 5 ) # POP(OPTR) 9 # * 3 5 # Operate(‘3’,’*’,’5’) 10 # 15 # Return(GetTop(OPND)) §3.3.2 队列的应用 例：周末舞会，男、女各排成一队，跳舞时，依次从男、 女队的头上各出一人配成舞伴，若两队人数不同，较长的 队中未配对者等下一轮舞曲 typedef struct { char name[20]; char sex; // M—男，F—女 47 } Person; typedef person DataType; //将队列定义中的数据类型改为Person void DancePartners（Person dancer[ ], int num）{ int i; Person P; CirQueue Mdancers, Fdancers; InitQueue(Mdancers); // 男士队列 InitQueue(Fdancers); §3.3.2 队列的应用 for( i=0; i<num; i++ ) { P = dancer[ i ]; if (P.sex == ‘M’) EnQueue (Mdancers, P); // 入男队 else EnQueue (Fdancers, P); // 入女队 } 48 printf (“The dancing partners are:\n\n”); while (!QueueEmpty(Fdancers) && !QueueEmpty(Mdancers)) { // 男女队列均非空 P=DeQueue(Fdancers); // 女士出队 printf(“%s ”, P.name); // 女士姓名 P=DeQueue(Mdancers); //男士出队 printf(“%s\n”, P.name); }

201447 §3.3.2队列的应用 f(!QueueEmpty(Fdancers)》(女队非空，输出剩余人数及队头者名字 printf("n There are %d women waiting for the next round.n",Fdancers.count:)I/count是队列属性，长度 P=QueueFront(Fdancers)片∥取队头 printf("%s will be the first to get a partner.In",P.name); 】else( ∥男队类型处理 时间复杂度：O 9

2014/4/7 9 §3.3.2 队列的应用 if (!QueueEmpty(Fdancers)) { //女队非空，输出剩余人数及队头者名字 printf(“\n There are %d women waiting for the next round.\n”, Fdancers.count);// count是队列属性，长度 P=QueueFront(Fdancers); // 取队头 printf (“%s will be the first to get a partner.\n”, P.name); } else{ 49 } else{ // 男队类型处理 } } 时间复杂度：O(n)