算法與數(shù)據(jù)結(jié)構(gòu)課件_DSC3

1、S33.1 棧第三章. 棧和隊列 （Chapter 3. Stack and Queue) 棧（stack）是插入和刪除操作受限的線性表，是一種后進先出（Last In First Out - LIFO）的線性表。表頭端稱為棧底（bottom），表尾端稱為棧頂（top），插入和刪除都在棧頂進行。bottomtopS1S2S5S6S3S4S3S3S3S3S3PUSHPUSHPUSHPOPPUSHPUSHPUSH棧的基本操作：棧的基本操作：InistackClearGettopEmptyPushPop棧的實現(xiàn)：棧的實現(xiàn)：#define STACK_INIT_SIZE user_supply#def

2、ine STACKINCREMENT user_supplytypedef struct elemtype * bottom ; elemtype * top ; int stackzise ; sqstack ;順序存儲結(jié)構(gòu)表示棧Fulltypedef strcut lnode elemtype data ; struct lnode * next ; * linkedstack;鏈式存儲結(jié)構(gòu)表示棧-鏈棧（Linked_stack）上溢（上溢（overflow）：）：若棧的容量已全部用完，再進行插入操作（PUSH），就會發(fā)生上溢錯誤。下溢（下溢（underflow）：）：若棧已空，再進行刪除

3、操作（POP），就會發(fā)生下溢錯誤。3.2 棧的應(yīng)用-表達式求值 任一表達式（expression）都是由操作數(shù)（operand）、操作符（operator）和界限符（delimiter）組成。 我們通常習慣使用中綴表達式（infix expression），但中綴表達式離不開括號（bracket)。若使用前綴表達式（prefix expression）或后綴表達式（ postfix expression）則不需要括號。利用棧，可以將中綴表達式變?yōu)榍熬Y表達式或后綴表達式，再用棧進行運算即可得到表達式的值（value）。3.3 棧與遞歸遞歸（遞歸（recursive）：）：一個程序直接調(diào)用自己或通

4、過其它程序調(diào)用自己就稱為遞歸。根據(jù)調(diào)用關(guān)系可分為直接遞歸（direct recursive）和間接遞歸（indirect recursive ）。第第 一一 次次 上上 機機 作作 業(yè)業(yè) 輸入表達式字符串，以輸入表達式字符串，以“=”表示結(jié)表示結(jié)束，束， 計算并輸出表達式值。計算并輸出表達式值。 操作數(shù)可操作數(shù)可以是整數(shù)或?qū)崝?shù)，操作符有以是整數(shù)或?qū)崝?shù)，操作符有 “+”、“-”、“*”、“/”、“”（乘方）和（乘方）和 “sin( )”（正弦）、（正弦）、“cos( )”（余弦）、（余弦）、“l(fā)og( )”（對數(shù)）、（對數(shù)）、“l(fā)n( )”（自然對數(shù)）等函數(shù)。（自然對數(shù)）等函數(shù)。棧在程序的過程或

5、函數(shù)調(diào)用中的作用：過程一過程二過程三過程四斷點三斷點一斷點二斷點一斷點二斷點三stack調(diào)用子程序返回斷點程序執(zhí)行 遞歸是程序設(shè)計中一種強有力的工具。下面三種情況可用遞歸解決： 1、有些數(shù)學(xué)函數(shù)是遞歸定義的，對其求解可用遞歸； 2、有些數(shù)據(jù)結(jié)構(gòu)具有遞歸特性，對其操作可用遞歸； 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、 ; / 遞歸調(diào)用部分遞歸調(diào)用部分 例：例： 求 n 個數(shù)的最小值：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、河內(nèi)塔問題的解決方法應(yīng)用的就是分治法；例：例：程序設(shè)計常用方法之二：程序設(shè)計常用方法之二： 回溯法（回溯法（Backtracking） 回溯法是一種滿足一定條件的窮舉搜索法：在求解過程中，不斷利用可供選擇的規(guī)則擴展部分解，一旦當前的部分解不成立，就停止擴展，退回到上一個較小的部分解繼續(xù)試

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 區(qū)染區(qū)染 1 色色 i = 1 ; j = 1 ; / i 為區(qū)域號，為區(qū)域號，j 為染色號為染色號 while ( i n ) wh

8、ile ( j 4 ) & ( i n ) k = 0 ; / k 指示已染色區(qū)域號指示已染色區(qū)域號 while ( k i ) & (s k * R i k != j ) k+ ; / 判相鄰區(qū)是否已染色且不同色判相鄰區(qū)是否已染色且不同色 if ( k 4 ) j = s - - i + 1; ; / （回溯）變更棧頂區(qū)域的染色色數(shù)，用新顏色重試（回溯）變更棧頂區(qū)域的染色色數(shù)，用新顏色重試 43221 321 23214232134232113423210123456s：34221 2、過河問題：某人帶了一條狗、一只雞和一筐菜過河，因船小，每次只能帶一樣?xùn)|西過河。若單獨留下狗和雞，則狗會吃雞

9、；若單獨留下雞和菜，則雞會吃菜。試問他如何過河？結(jié)果如下： 1、人+雞過河； 2、人空手返回； 3、人+狗過河； 4、人+雞返回； 5、人+菜過河； 6、人空手返回； 7、人+雞過河。 前面說到的迷宮問題、八皇后問題、騎士遍歷問題均可應(yīng)用回溯法求解。作作 業(yè)業(yè)2. 試推導(dǎo)求解試推導(dǎo)求解 n 階梵塔問題至少要執(zhí)階梵塔問題至少要執(zhí) 行的移動操作行的移動操作 move 次數(shù)。次數(shù)。3. 一個簡化的背包問題：一個背包能裝一個簡化的背包問題：一個背包能裝總重量為總重量為 T，現(xiàn)有，現(xiàn)有 n 個物件，其重量分個物件，其重量分別為（別為（W1、W2、Wn）。問能否從）。問能否從這這 n 個物件中挑選若干個物

10、件放入背包個物件中挑選若干個物件放入背包中，使其總重量正好為中，使其總重量正好為 T ？若有解則給？若有解則給出全部解，否則輸出無解。出全部解，否則輸出無解。作作 業(yè)業(yè)4. 已知以字符型順序表表示的表達已知以字符型順序表表示的表達式含有三種擴號式含有三種擴號“（”、“）”、“”、“”、“”和和“”，它們可嵌，它們可嵌套使用，試寫出算法判斷給定表達套使用，試寫出算法判斷給定表達式中所含擴號是否正確配對出現(xiàn)。式中所含擴號是否正確配對出現(xiàn)。第第 二二 次次 上上 機機 作作 業(yè)業(yè)八皇后問題或騎士遍歷問題任選一個。八皇后問題或騎士遍歷問題任選一個。遞歸過程的模擬遞歸過程的模擬 以下的方法可對大多數(shù)遞歸

11、程序進行模擬： 1、定義記錄 R，由返回地址、全部的參數(shù)和局部變量組成； 2、為每個返回地址定義一個標號# i（1in-1）； 3、為過程體開頭定義一個標號#0，作為遞歸入口； 4、在結(jié)尾處定義標號#n，將所有變參出棧并退棧，過程結(jié)束； 5、在過程頭定義R型棧S，并保存#n和參數(shù)等，以便過程結(jié)束；6、將每個遞歸調(diào)用語句用下面四個語句替換：A、將返回地址和實參進棧； B、GoTo #0； C、#i: 將變參賦值給局部變量； D、退棧操作。7、在所有遞歸出口處增加語句GoTo TOP(S,#i)，返回斷點； 8、各參數(shù)和局部變量均使用棧頂記錄中相應(yīng)數(shù)據(jù)項代替； 9、將得到的上述算法優(yōu)化，即可得到結(jié)

12、構(gòu)清晰的非遞歸算法。 對有些具有尾遞歸的過程，由于尾遞歸后不需保留參數(shù)和局部變量，可直接用循環(huán)代替遞歸。例如：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隊列的實現(xiàn)：隊列的實現(xiàn)：鏈式存儲結(jié)構(gòu)表示隊列typedef struct node elemtype data ; struct node * next ; * pointer;typedef struct pointer front, rear ; linkedqueue ;q1q2qiqnfrontrear順序存儲結(jié)

14、構(gòu)表示隊列#define MAXLEN user_supplytypedef struct elemtype elem MAXLEN ; int front , rear; queue;q3q1q2q5q6q4q1q2q2q1q7ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8OF012345ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8q1q2q3 q4 q5q6q7q8循環(huán)隊列 （circular queue） i = (i+1) % n 入隊列入隊列 rear+1，出隊列，出隊列 front+1, 元元素個數(shù)素個數(shù) =（rear front + n ) % n滿滿空空?FRFRFRRRRRRR 判斷循環(huán)隊列滿和空的三種方法：判斷循環(huán)隊列滿和空的三種方法：1、設(shè)置標志信號（flag）- flag=0 表示空，flag=1 表示滿： front 追上 rear 則 flag=0， rear 追上 front 則 flag=1；2、留下一個單元不使用，則 rear 永遠也追不上 front；、只使用一個