算法与数据结构课件-DSC3.ppt

1、S33.1 栈第三章. 栈和队列 （Chapter 3. Stack and Queue) 栈（stack）是插入和删除操作受限的线性表，是一种后进先出（Last In First Out - LIFO）的线性表。表头端称为栈底（bottom），表尾端称为栈顶（top），插入和删除都在栈顶进行。bottomtopS1S2S5S6S3S4S3S3S3S3S3PUSHPUSHPUSHPOPPUSHPUSHPUSH栈的基本操作：栈的基本操作：InistackClearGettopEmptyPushPop栈的实现：栈的实现：#define STACK_INIT_SIZE user_supply#def

2、ine STACKINCREMENT user_supplytypedef struct elemtype * bottom ; elemtype * top ; int stackzise ; sqstack ;顺序存储结构表示栈Fulltypedef strcut lnode elemtype data ; struct lnode * next ; * linkedstack;链式存储结构表示栈-链栈（Linked_stack）上溢（上溢（overflow）：）：若栈的容量已全部用完，再进行插入操作（PUSH），就会发生上溢错误。下溢（下溢（underflow）：）：若栈已空，再进行删除

3、操作（POP），就会发生下溢错误。3.2 栈的应用-表达式求值 任一表达式（expression）都是由操作数（operand）、操作符（operator）和界限符（delimiter）组成。 我们通常习惯使用中缀表达式（infix expression），但中缀表达式离不开括号（bracket)。若使用前缀表达式（prefix expression）或后缀表达式（ postfix expression）则不需要括号。利用栈，可以将中缀表达式变为前缀表达式或后缀表达式，再用栈进行运算即可得到表达式的值（value）。3.3 栈与递归递归（递归（recursive）：）：一个程序直接调用自己或通

4、过其它程序调用自己就称为递归。根据调用关系可分为直接递归（direct recursive）和间接递归（indirect recursive ）。第第 一一 次次 上上 机机 作作 业业 输入表达式字符串，以输入表达式字符串，以“=”表示结表示结束，束， 计算并输出表达式值。计算并输出表达式值。 操作数可操作数可以是整数或实数，操作符有以是整数或实数，操作符有 “+”、“-”、“*”、“/”、“”（乘方）和（乘方）和 “sin( )”（正弦）、（正弦）、“cos( )”（余弦）、（余弦）、“log( )”（对数）、（对数）、“ln( )”（自然对数）等函数。（自然对数）等函数。栈在程序的过程或

5、函数调用中的作用：过程一过程二过程三过程四断点三断点一断点二断点一断点二断点三stack调用子程序返回断点程序执行 递归是程序设计中一种强有力的工具。下面三种情况可用递归解决： 1、有些数学函数是递归定义的，对其求解可用递归； 2、有些数据结构具有递归特性，对其操作可用递归； 3、有些问题的解决方法用递归描述，对其求解也可用递归。 例：例： 求阶乘（factorial）： Fact(n) = 1 当 n = 0 nFact(n-1) 当 n 0 int Fact ( int n ) if ( ! n ) return 1 ; / 出口条件出口条件 return n * Fact ( n 1 )

6、 ; / 递归调用部分递归调用部分 例：例： 求 n 个数的最小值：int Min ( sqlist S, int n ) if ( n=1 ) return S 1 ; / 出口条件出口条件 x = Min ( S, n-1 ); if ( x S n ) return m ; return S n ; 1、河内塔问题的解决方法应用的就是分治法；例：例：程序设计常用方法之二：程序设计常用方法之二： 回溯法（回溯法（Backtracking） 回溯法是一种满足一定条件的穷举搜索法：在求解过程中，不断利用可供选择的规则扩展部分解，一旦当前的部分解不成立，就停止扩展，退回到上一个较小的部分解继续试

7、探，直到找到问题所有的解或无解为止。 1、地图染色（四色定理）问题：例：例：000102030405060002060601050302040 1 1 1 1 1 01 0 0 0 0 1 01 0 0 1 1 0 01 0 1 0 1 1 01 0 1 1 0 1 01 1 0 1 1 0 00 0 0 0 0 0 00 1 2 3 4 5 6R0132456void MapColor ( int R n n , int s n ) s 0 =1; / 00 区染区染 1 色色 i = 1 ; j = 1 ; / i 为区域号，为区域号，j 为染色号为染色号 while ( i n ) wh

8、ile ( j 4 ) & ( i n ) k = 0 ; / k 指示已染色区域号指示已染色区域号 while ( k i ) & (s k * R i k != j ) k+ ; / 判相邻区是否已染色且不同色判相邻区是否已染色且不同色 if ( k 4 ) j = s - - i + 1; ; / （回溯）变更栈顶区域的染色色数，用新颜色重试（回溯）变更栈顶区域的染色色数，用新颜色重试 43221 321 23214232134232113423210123456s：34221 2、过河问题：某人带了一条狗、一只鸡和一筐菜过河，因船小，每次只能带一样东西过河。若单独留下狗和鸡，则狗会吃鸡

9、；若单独留下鸡和菜，则鸡会吃菜。试问他如何过河？结果如下： 1、人+鸡过河； 2、人空手返回； 3、人+狗过河； 4、人+鸡返回； 5、人+菜过河； 6、人空手返回； 7、人+鸡过河。 前面说到的迷宫问题、八皇后问题、骑士遍历问题均可应用回溯法求解。作作 业业2. 试推导求解试推导求解 n 阶梵塔问题至少要执阶梵塔问题至少要执 行的移动操作行的移动操作 move 次数。次数。3. 一个简化的背包问题：一个背包能装一个简化的背包问题：一个背包能装总重量为总重量为 T，现有，现有 n 个物件，其重量分个物件，其重量分别为（别为（W1、W2、Wn）。问能否从）。问能否从这这 n 个物件中挑选若干个物

10、件放入背包个物件中挑选若干个物件放入背包中，使其总重量正好为中，使其总重量正好为 T ？若有解则给？若有解则给出全部解，否则输出无解。出全部解，否则输出无解。作作 业业4. 已知以字符型顺序表表示的表达已知以字符型顺序表表示的表达式含有三种扩号式含有三种扩号“（”、“）”、“”、“”、“”和和“”，它们可嵌，它们可嵌套使用，试写出算法判断给定表达套使用，试写出算法判断给定表达式中所含扩号是否正确配对出现。式中所含扩号是否正确配对出现。第第 二二 次次 上上 机机 作作 业业八皇后问题或骑士遍历问题任选一个。八皇后问题或骑士遍历问题任选一个。递归过程的模拟递归过程的模拟 以下的方法可对大多数递归

11、程序进行模拟： 1、定义记录 R，由返回地址、全部的参数和局部变量组成； 2、为每个返回地址定义一个标号# i（1in-1）； 3、为过程体开头定义一个标号#0，作为递归入口； 4、在结尾处定义标号#n，将所有变参出栈并退栈，过程结束； 5、在过程头定义R型栈S，并保存#n和参数等，以便过程结束；6、将每个递归调用语句用下面四个语句替换：A、将返回地址和实参进栈； B、GoTo #0； C、#i: 将变参赋值给局部变量； D、退栈操作。7、在所有递归出口处增加语句GoTo TOP(S,#i)，返回断点； 8、各参数和局部变量均使用栈顶记录中相应数据项代替； 9、将得到的上述算法优化，即可得到结

12、构清晰的非递归算法。 对有些具有尾递归的过程，由于尾递归后不需保留参数和局部变量，可直接用循环代替递归。例如：void RW ( int n ) void RW ( int n ) if ( ! n ) while ( ! n ) cin x ; cin x ; cout x ; cout x ; RW ( n 1) ; n = n 1; 3.3 队列 队列（queue）也是插入和删除操作受限的线性表，但是一种先进先出（ First In First Out - FIFO）的线性表。表头端称为队头（front），表尾端称为队尾（rear），插入在队尾进行，而删除则在队头进行。q3frontre

13、arq1q2q5q6q4q1q2q2EnqueueEnqueueEnqueueDequeueEnqueueDequeueEnqueueEnqueueq1队列的基本操作：队列的基本操作：IniqueueClearGetheadEmptyEnqueueDequeueFullSize队列的实现：队列的实现：链式存储结构表示队列typedef struct node elemtype data ; struct node * next ; * pointer;typedef struct pointer front, rear ; linkedqueue ;q1q2qiqnfrontrear顺序存储结

14、构表示队列#define MAXLEN user_supplytypedef struct elemtype elem MAXLEN ; int front , rear; queue;q3q1q2q5q6q4q1q2q2q1q7ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8OF012345ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8q1q2q3 q4 q5q6q7q

15、8循环队列 （circular queue） i = (i+1) % n 入队列入队列 rear+1，出队列，出队列 front+1, 元元素个数素个数 =（rear front + n ) % n满满空空?FRFRFRRRRRRR 判断循环队列满和空的三种方法：判断循环队列满和空的三种方法：1、设置标志信号（flag）- flag=0 表示空，flag=1 表示满： front 追上 rear 则 flag=0， rear 追上 front 则 flag=1；2、留下一个单元不使用，则 rear 永远也追不上 front；、只使用一个指针 front 和 元素个数 size，则可用 size 的值来判断队列的满和空。作作 业业5. 若栈的输入序列为若栈的输入序列为 1234，给出所有，给出所有可能的输出序列。可能的输出序列。6. 已知有两个栈已知有两个栈 S1 和和 S2 及其基本操及其基本操作作 Push(S , x)、Pop(S)、Full(S) 和和 Empty(S)，给出用此二栈实现队列操，给出用此二栈实现队列操作作Enqueue、Dequeue、Fullq 和和Emptyq的算法的算法