數(shù)據(jù)結(jié)構(gòu)與算法第三章清華大學(xué)出版社趙玉蘭

1、2棧（棧（stack）u只允許在表的一端進(jìn)行插只允許在表的一端進(jìn)行插入和刪除的線性表入和刪除的線性表u允許插入和刪除的一端稱允許插入和刪除的一端稱為棧頂（為棧頂（top），另一端稱），另一端稱為棧底（為棧底（bottom）u不含元素的棧稱為空棧不含元素的棧稱為空棧 u插入：進(jìn)棧，入棧插入：進(jìn)棧，入棧 刪除：出棧，退棧刪除：出棧，退棧u特點(diǎn)特點(diǎn)后進(jìn)先出（后進(jìn)先出（lifo）先進(jìn)后出（先進(jìn)后出（filo）3問題問題u有三個(gè)元素按有三個(gè)元素按 a1, a2, a3 的次序依次進(jìn)棧，其出棧的次序依次進(jìn)棧，其出棧次序有幾種可能？次序有幾種可能？出棧次序：出棧次序： a1，a2，a3 a1，a3，a2 a

2、2，a1，a3 a2，a3，a1 a3，a2，a1注意：注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒有限定插入和刪除操作進(jìn)行的時(shí)間。制，并沒有限定插入和刪除操作進(jìn)行的時(shí)間。4棧的抽象數(shù)據(jù)類型棧的抽象數(shù)據(jù)類型adt stack data 數(shù)據(jù)項(xiàng)列表數(shù)據(jù)項(xiàng)列表 top：棧頂位置：棧頂位置 operations constructor process：創(chuàng)建一個(gè)空棧：創(chuàng)建一個(gè)空棧 isempty process：判斷棧是否為空：判斷棧是否為空 output：如果棧為空，則返回：如果棧為空，則返回true，否則返回，否則返回false gettop proc

3、ess：取棧頂元素：取棧頂元素 output：返回棧頂元素：返回棧頂元素5 length process：求棧中元素個(gè)數(shù)：求棧中元素個(gè)數(shù) output：返回棧中元素的個(gè)數(shù)：返回棧中元素的個(gè)數(shù) push input：要添加的數(shù)據(jù)元素：要添加的數(shù)據(jù)元素 process：向棧中添加元素：向棧中添加元素x，即進(jìn)棧，即進(jìn)棧 pop process：刪除棧頂元素，即出棧：刪除棧頂元素，即出棧 output：返回棧頂元素：返回棧頂元素 clear process：刪除棧中所有元素并置新的棧頂：刪除棧中所有元素并置新的棧頂 /stack6順序棧順序棧順序棧的定義順序棧的定義如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？如何改

4、造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？ 0 1 2 3 4 5 6附設(shè)指針附設(shè)指針top指示棧頂元指示棧頂元素在數(shù)組中的位置。素在數(shù)組中的位置。 top確定用數(shù)組的哪確定用數(shù)組的哪一端表示棧底。一端表示棧底。a1a2a37順序棧的基本操作順序棧的基本操作出棧：先出棧出棧：先出棧 top再減再減1進(jìn)棧：進(jìn)棧：top先加先加1 再進(jìn)棧再進(jìn)棧?？眨簵？眨簍op= -1 0 1 2 3 4 5 6 7 8a1topa2topa3top棧滿：棧滿：top=maxstacksize-1top top8const int maxstacksize=50; /棧中能容納最大元素個(gè)數(shù)棧中能容納最大元素個(gè)數(shù)class seqs

5、tack datatype stacklistmaxstacksize; int top; public: stack (); /構(gòu)造函數(shù)，初始化構(gòu)造函數(shù)，初始化top bool isempty (); /判斷棧的狀態(tài)是否為空判斷棧的狀態(tài)是否為空 bool isfull (); datatype gettop (); /取棧頂元素取棧頂元素 void push (const datatype x); /入棧入棧 datatype pop (); /出棧出棧 void clear (); /棧清空棧清空;/ seqstack9順序棧的操作的實(shí)現(xiàn)順序棧的操作的實(shí)現(xiàn)u構(gòu)造函數(shù)，初始化一個(gè)空棧構(gòu)造函數(shù)

6、，初始化一個(gè)空棧 stack ( ) stacklist = new datatypemaxstacksize; top=-1; / stack10u判斷棧是否為空判斷棧是否為空 bool isempty ( ) if (top=-1) return true; else return false; / isempty11u判斷棧是否已滿判斷棧是否已滿 bool isfull( ) if (top=maxstacksize-1) return true; else return false; / isfull12u取棧頂元素取棧頂元素 datatype gettop( ) if (isempt

7、y( ) cout”?？?！?？?！”endl; return nulldata; return stacklisttop; 13u向棧頂壓入元素向棧頂壓入元素 void push (datatype x) if (isfull( ) cout”棧滿！棧滿！”endl; else stacklist+top = x; / push14u刪除棧頂元素刪除棧頂元素 datatype pop( ) if (isempty( ) cout”?？?！?？?！”next=null; /創(chuàng)建頭結(jié)點(diǎn)創(chuàng)建頭結(jié)點(diǎn) void push (datatype data);18 datatype pop ( ); datatyp

8、e gettop ( ); void clear ( ) top-next=null; bool isempty ( ) return top -next= = null; ;/ linkstack19類中操作算法的描述類中操作算法的描述u入棧操作入棧操作 void push (datatype item ) p=new stacknode ( item); p-next=top-next; top-next=p; /push20u出棧操作出棧操作 datatype pop ( ) if ( top-next!=null ) p=top-next; retvalue=p-data; /暫存棧頂

9、數(shù)據(jù)暫存棧頂數(shù)據(jù) top -next=p-next; /修改棧頂指針修改棧頂指針 delete p; /釋放，返回?cái)?shù)據(jù)釋放，返回?cái)?shù)據(jù) return retvalue; else /?？盏那闆r?？盏那闆r cout”the stack is empty!”next!=null) return top-next-data; else /棧空的情況?？盏那闆r cout”the stack is empty!”1時(shí)，先把塔時(shí)，先把塔 a 上的上的 n-1 個(gè)圓盤移到塔個(gè)圓盤移到塔 b，然后將，然后將 n 號(hào)盤從塔號(hào)盤從塔 a 移到塔移到塔 c，再將，再將 n-1 個(gè)圓盤從塔個(gè)圓盤從塔 b移到塔移到塔c。

10、即把求解即把求解 n 個(gè)圓盤的個(gè)圓盤的hanoi問題轉(zhuǎn)化為求解問題轉(zhuǎn)化為求解 n-1 個(gè)圓盤個(gè)圓盤的的 hanoi 問題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤問題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的的 hanoi 問題。問題。3132u解決漢諾塔問題的算法解決漢諾塔問題的算法 main( ) int n; coutn; hanoi( n ,a,b,c ); void hanoi (int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 33

11、遞歸過程和運(yùn)行時(shí)棧遞歸過程和運(yùn)行時(shí)棧遞歸函數(shù)的運(yùn)行軌跡遞歸函數(shù)的運(yùn)行軌跡u描述方法描述方法1）寫出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語句，并用箭頭表示語）寫出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語句，并用箭頭表示語句的執(zhí)行次序；句的執(zhí)行次序；2）對(duì)函數(shù)的每個(gè)遞歸調(diào)用，寫出相應(yīng)的函數(shù)調(diào)用，從調(diào)）對(duì)函數(shù)的每個(gè)遞歸調(diào)用，寫出相應(yīng)的函數(shù)調(diào)用，從調(diào)用處畫一條箭頭指向被調(diào)用函數(shù)入口，表示調(diào)用路線，用處畫一條箭頭指向被調(diào)用函數(shù)入口，表示調(diào)用路線，從被調(diào)用函數(shù)末尾處畫一條箭頭指向調(diào)用語句的下面，從被調(diào)用函數(shù)末尾處畫一條箭頭指向調(diào)用語句的下面，表示返回路線；表示返回路線；3）在返回路線上標(biāo)出本層調(diào)用所得的函數(shù)值。）在返回路線上標(biāo)出本層調(diào)

12、用所得的函數(shù)值。 34un=3 時(shí)漢諾塔遞歸算法的運(yùn)行軌跡時(shí)漢諾塔遞歸算法的運(yùn)行軌跡hanoi ( 3, a, b, c）move ( a, 3, c )hanoi ( 2, a, c, b）hanoi ( 2, a, c, b）hanoi ( 3, a, b, c）hanoi ( 1, a, b, c）遞歸第三層遞歸第三層遞歸第二層遞歸第二層遞歸第一層遞歸第一層move ( a, 1, c )hanoi ( 1, c, a, b）move ( c, 1, b )hanoi ( 1, b, c, a）move ( b, 1, a )hanoi ( 1, a, b, c）move ( a, 1,

13、 c )hanoi ( 1, a, b, c）move ( a, 2, b )hanoi ( 1, c, a, b）hanoi ( 2, b, a, c）hanoi ( 1, b, c, a）move ( b, 2, c )hanoi ( 1, a, b, c）hanoi ( 2, b, a, c）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)35遞歸函數(shù)的內(nèi)部執(zhí)行過程遞歸函數(shù)的內(nèi)部執(zhí)行過程u當(dāng)一個(gè)函數(shù)在運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)當(dāng)一個(gè)函數(shù)在運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需要將實(shí)參和返回值地行被調(diào)用函數(shù)之前，系統(tǒng)需要將實(shí)

14、參和返回值地址等數(shù)據(jù)傳遞給被調(diào)函數(shù)，當(dāng)函數(shù)調(diào)用時(shí)，這些址等數(shù)據(jù)傳遞給被調(diào)函數(shù)，當(dāng)函數(shù)調(diào)用時(shí)，這些數(shù)據(jù)與局部變量一起構(gòu)成一條數(shù)據(jù)與局部變量一起構(gòu)成一條“工作記錄工作記錄”，被，被壓入系統(tǒng)提供的棧（運(yùn)行時(shí)棧）。壓入系統(tǒng)提供的棧（運(yùn)行時(shí)棧）。u當(dāng)被調(diào)函數(shù)返回時(shí)，按照返回地址執(zhí)行調(diào)用函數(shù)當(dāng)被調(diào)函數(shù)返回時(shí)，按照返回地址執(zhí)行調(diào)用函數(shù)中下一條指令，同時(shí)釋放棧中相應(yīng)的工作記錄。中下一條指令，同時(shí)釋放棧中相應(yīng)的工作記錄。36主程序主程序call proc1rproc1proc2proc3scall proc2tcall proc3系統(tǒng)運(yùn)行時(shí)棧系統(tǒng)運(yùn)行時(shí)棧局部變量局部變量返回地址返回地址實(shí)際參數(shù)實(shí)際參數(shù)工作記錄工

15、作記錄37u遞歸調(diào)用的內(nèi)部執(zhí)行過程遞歸調(diào)用的內(nèi)部執(zhí)行過程運(yùn)行開始時(shí)，首先為遞歸調(diào)用建立一個(gè)系統(tǒng)運(yùn)行時(shí)棧；運(yùn)行開始時(shí)，首先為遞歸調(diào)用建立一個(gè)系統(tǒng)運(yùn)行時(shí)棧；每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址等組成的工作記錄量的當(dāng)前值以及調(diào)用后的返回地址等組成的工作記錄壓入棧中；壓入棧中；每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。指定的位置繼續(xù)執(zhí)行。38un=3 時(shí)漢諾

16、塔遞歸算法的部分執(zhí)行過程時(shí)漢諾塔遞歸算法的部分執(zhí)行過程 main() hanoi ( 3,a,b,c ); void hanoi(int n,char x,char y,char z) if (n=1) move (1,x,z); else hanoi (n-1,x,z,y); move (n,x,z); hanoi (n-1,y,x,z); 0123456789abc321返回返回地址地址zyxn 3abc 01cab82acb61abc61239遞歸總結(jié)遞歸總結(jié)u遞歸是重要的設(shè)計(jì)和編程工具，使許多算法變得遞歸是重要的設(shè)計(jì)和編程工具，使許多算法變得簡單，易于設(shè)計(jì)和實(shí)現(xiàn)。簡單，易于設(shè)計(jì)和實(shí)現(xiàn)。

17、 優(yōu)點(diǎn)優(yōu)點(diǎn)u遞歸使算法的時(shí)間復(fù)雜度和空間復(fù)雜度同時(shí)增大，遞歸使算法的時(shí)間復(fù)雜度和空間復(fù)雜度同時(shí)增大，有時(shí)會(huì)導(dǎo)致效率急劇惡化，或者溢出系統(tǒng)棧。有時(shí)會(huì)導(dǎo)致效率急劇惡化，或者溢出系統(tǒng)棧。 缺點(diǎn)缺點(diǎn)u使用遞歸時(shí)應(yīng)該權(quán)衡效率和設(shè)計(jì)的關(guān)系。在有足使用遞歸時(shí)應(yīng)該權(quán)衡效率和設(shè)計(jì)的關(guān)系。在有足夠的空間并且時(shí)間要求不高的情況下可以使用遞夠的空間并且時(shí)間要求不高的情況下可以使用遞歸。歸。40定義定義u隊(duì)列（隊(duì)列（queue）是只允許在表的一端進(jìn)行刪除，而）是只允許在表的一端進(jìn)行刪除，而在另一端進(jìn)行插入的線性表。在另一端進(jìn)行插入的線性表。允許刪除的一端叫做隊(duì)頭（允許刪除的一端叫做隊(duì)頭（front）允許插入的一端叫做隊(duì)

18、尾（允許插入的一端叫做隊(duì)尾（rear）u特點(diǎn)特點(diǎn)先進(jìn)先出（先進(jìn)先出（fifo，first in first out）a1 a2 a3. an 入隊(duì)入隊(duì)出隊(duì)出隊(duì)frontrear41adt隊(duì)列的定義隊(duì)列的定義adt queue data 數(shù)據(jù)項(xiàng)列表數(shù)據(jù)項(xiàng)列表 front：隊(duì)列中第一個(gè)元素的位置：隊(duì)列中第一個(gè)元素的位置 rear：隊(duì)列中最后一個(gè)元素的位置：隊(duì)列中最后一個(gè)元素的位置 operations constructor process：初始化隊(duì)首和隊(duì)尾：初始化隊(duì)首和隊(duì)尾 isempty process：判斷是否為空隊(duì)列：判斷是否為空隊(duì)列 output：若隊(duì)列空，返回：若隊(duì)列空，返回true，

19、否則返回，否則返回false42 length process：求隊(duì)列中元素個(gè)數(shù)：求隊(duì)列中元素個(gè)數(shù) output：返回隊(duì)列的元素個(gè)數(shù)：返回隊(duì)列的元素個(gè)數(shù) front process：取出隊(duì)頭元素：取出隊(duì)頭元素 output：返回隊(duì)頭元素：返回隊(duì)頭元素 enter input：要進(jìn)入隊(duì)列的元素：要進(jìn)入隊(duì)列的元素 process：在隊(duì)尾插入新的元素：在隊(duì)尾插入新的元素 leave process：刪除隊(duì)頭元素：刪除隊(duì)頭元素 output：返回隊(duì)頭元素：返回隊(duì)頭元素 clearqueue process：刪除隊(duì)列中所有元素并設(shè)置初始狀態(tài)：刪除隊(duì)列中所有元素并設(shè)置初始狀態(tài)/queue43順序隊(duì)列順序隊(duì)

20、列順序隊(duì)列的定義順序隊(duì)列的定義const int maxqsize=50;class seqqueue int front, rear; datatype queuelistmaxqsize; public: seqqueue();/構(gòu)造函數(shù)構(gòu)造函數(shù),初始化數(shù)據(jù)成員初始化數(shù)據(jù)成員 void enter(datatype item); datatype leave(); void clear(); datatype front(); int length(); bool isempty(); bool isfull(); ;/ seqqueue44順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)順序隊(duì)列的進(jìn)隊(duì)和出隊(duì) u設(shè)兩

21、個(gè)指針設(shè)兩個(gè)指針 front 和和 rear（初始（初始 frontrear0）ufront 指向隊(duì)頭元素，出隊(duì)時(shí)先取出，再指向隊(duì)頭元素，出隊(duì)時(shí)先取出，再 front+1urear 指向隊(duì)尾元素的下一個(gè)位置，進(jìn)隊(duì)時(shí)先將新元素加入，指向隊(duì)尾元素的下一個(gè)位置，進(jìn)隊(duì)時(shí)先將新元素加入，再再 rear+1u隊(duì)空條件：隊(duì)空條件：front=rear，此時(shí)不能出隊(duì)，此時(shí)不能出隊(duì)u隊(duì)滿條件：隊(duì)滿條件：rear=maxqsize，此時(shí)不能進(jìn)隊(duì)，此時(shí)不能進(jìn)隊(duì)圖3.10 頭尾指針和隊(duì)列中元素的變化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear54

22、3210d5d6rearfront(a) 空隊(duì)列(b) d1,d2,d3入隊(duì)(c) d4,d5,d6入隊(duì)(d) d1,d2,d3,d4出隊(duì)45u存在問題存在問題 rear=maxqsize時(shí)，再有元素進(jìn)隊(duì)時(shí)，再有元素進(jìn)隊(duì)發(fā)生溢出發(fā)生溢出l當(dāng)當(dāng)front= 0真溢出真溢出l當(dāng)當(dāng)front 0假溢出假溢出u解決假溢出的方案解決假溢出的方案固定隊(duì)頭，出隊(duì)時(shí)，剩余元素均向前固定隊(duì)頭，出隊(duì)時(shí)，剩余元素均向前移動(dòng)移動(dòng)固定隊(duì)尾，入隊(duì)時(shí)，剩余元素均向前固定隊(duì)尾，入隊(duì)時(shí)，剩余元素均向前移動(dòng)移動(dòng)循環(huán)隊(duì)列：把隊(duì)列設(shè)想成環(huán)形，讓循環(huán)隊(duì)列：把隊(duì)列設(shè)想成環(huán)形，讓 0 接在接在 maxqsize-1 后后更好更好圖3.10

23、 頭尾指針和隊(duì)列中元素的變化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空隊(duì)列(b) d1,d2,d3入隊(duì)(c) d4,d5,d6入隊(duì)(d) d1,d2,d3,d4出隊(duì)圖3.10 頭尾指針和隊(duì)列中元素的變化rear543210543210d1d2d3543210d1d2d3d4d5d6frontfrontrearrear543210d5d6rearfront(a) 空隊(duì)列(b) d1,d2,d3入隊(duì)(c) d4,d5,d6入隊(duì)(d) d1,d2,d3,d4出隊(duì)46循環(huán)隊(duì)列循環(huán)隊(duì)

24、列u也是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)也是隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)u實(shí)現(xiàn)實(shí)現(xiàn)利用利用“模?！边\(yùn)算運(yùn)算入隊(duì)入隊(duì)lqueuelistrear=item; rear=(rear+1)%maxqsize; 出隊(duì)出隊(duì)litem=queuelistfront; front=(front+1)% maxqsize; 01frontrear.maxqsize-147u仍然存在問題仍然存在問題如何判斷隊(duì)列是如何判斷隊(duì)列是“空空”還是還是“滿滿”？3.11循環(huán)隊(duì)列示意圖(a)一般情況 (b)隊(duì)滿時(shí) 4 5 32 1 0 front rear (c)隊(duì)空時(shí) 45 3 21 0 d1 d2 d3 d4 d5 d6 frontrear

25、453 2 1 0front rear d1 d2 d3 隊(duì)空：隊(duì)空：front=rear隊(duì)滿：隊(duì)滿：front=rear48u三種處理方法三種處理方法給隊(duì)列設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿給隊(duì)列設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿給隊(duì)列增加一個(gè)統(tǒng)計(jì)元素個(gè)數(shù)的變量給隊(duì)列增加一個(gè)統(tǒng)計(jì)元素個(gè)數(shù)的變量 count，當(dāng)，當(dāng)count=maxqsize 時(shí)隊(duì)滿；時(shí)隊(duì)滿；count=0 時(shí)隊(duì)空時(shí)隊(duì)空少用一個(gè)變量，約定少用一個(gè)變量，約定 rear+1 等于等于 front（從后面趕上隊(duì)（從后面趕上隊(duì)頭指針）為隊(duì)滿的情況頭指針）為隊(duì)滿的情況l隊(duì)滿條件：隊(duì)滿條件：( rear+1 ) % maxqsize=fron

26、tl隊(duì)空條件：隊(duì)空條件： frontrear49u循環(huán)隊(duì)列類的操作算法描述循環(huán)隊(duì)列類的操作算法描述構(gòu)造函數(shù)，初始化一個(gè)空隊(duì)列構(gòu)造函數(shù)，初始化一個(gè)空隊(duì)列 seqqueue () front=rear=0; / seqqueue入隊(duì)操作入隊(duì)操作 void enter (datatype item) if ( (rear+1)%maxqsize=front ) /判斷是否隊(duì)滿判斷是否隊(duì)滿 cout”隊(duì)列已滿，不能入隊(duì)！隊(duì)列已滿，不能入隊(duì)！”endl; else queuelistrear=item; rear=(rear+1)%maxqsize; / enter50出隊(duì)操作出隊(duì)操作 datatype

27、 leave() if ( front=rear ) /判斷是否隊(duì)空判斷是否隊(duì)空 cout”隊(duì)列已空，不能出隊(duì)隊(duì)列已空，不能出隊(duì)”next = nullfront圖圖 3.13 鏈隊(duì)列鏈隊(duì)列a1a2a3a4 rear53u鏈隊(duì)列描述鏈隊(duì)列描述 class qnode /鏈隊(duì)結(jié)點(diǎn)的類鏈隊(duì)結(jié)點(diǎn)的類 datatype data; qnode *next; public: qnode(datatype item=nulldata) data= item; next=null; friend class linkqueue; ; / qnode54class linkqueue qnnode *fron

28、t, *rear; public: linkqueue() rear =front=new qnode(); void enter (datatype item ); datatype leave(); datatype front(); void clear () front-next = rear-next = null; bool isempty () return front next= null; ; / linkqueue 55u鏈隊(duì)列基本操作的算法描述鏈隊(duì)列基本操作的算法描述入隊(duì)操作入隊(duì)操作 void enter ( datatype item ) rear-next = new

29、 qnode ( item); rear=rear-next; /enter56出隊(duì)操作出隊(duì)操作 datatype leave( ) if (!isempty ( ) ) /判隊(duì)不空判隊(duì)不空 p = front-next; datatype retvalue = p-data;/保存隊(duì)頭的值保存隊(duì)頭的值 front-next = p-next; delete p; if ( front-next=null ) /刪除隊(duì)列中唯一結(jié)點(diǎn)后，重新設(shè)置刪除隊(duì)列中唯一結(jié)點(diǎn)后，重新設(shè)置rear rear=front; return retvalue; else cout” 隊(duì)列空隊(duì)列空!”next-data

30、; else cout”隊(duì)列空，無隊(duì)頭元素！隊(duì)列空，無隊(duì)頭元素！”0 時(shí)重復(fù)（時(shí)重復(fù)（1），（），（2） （1）若）若n0，則將，則將 n % r 壓入棧壓入棧 s 中，執(zhí)行（中，執(zhí)行（2）；）； 若若n0，將棧，將棧 s 的內(nèi)容依次出棧，算法結(jié)束。的內(nèi)容依次出棧，算法結(jié)束。（2）用）用 n/r 代替代替 n61u算法描述算法描述 void conversion ( int n，int r ) seqstack s; int x; while ( n ) s.push (n % r ); n=n / r ; while (! s.isempty ( ) x=s.pop ( ) ; coutx

31、; /while /conversion62應(yīng)用應(yīng)用2：表達(dá)式求值：表達(dá)式求值u表達(dá)式表達(dá)式表達(dá)式由操作數(shù)（表達(dá)式由操作數(shù)（operand）、運(yùn)算符（）、運(yùn)算符（operator）和）和分界符（分界符（delimiter）組成）組成l操作數(shù)：變量或常數(shù)操作數(shù)：變量或常數(shù)l運(yùn)算符：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符運(yùn)算符：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符l分界符：括號(hào)分界符：括號(hào)表達(dá)式的表示方法表達(dá)式的表示方法l前綴表達(dá)式前綴表達(dá)式l中綴表達(dá)式中綴表達(dá)式l后綴表達(dá)式后綴表達(dá)式63u后綴表達(dá)式（逆波蘭式）求值后綴表達(dá)式（逆波蘭式）求值后綴表達(dá)式不含括號(hào)后綴表達(dá)式不含括號(hào)運(yùn)算符放在兩個(gè)操作數(shù)后面運(yùn)

32、算符放在兩個(gè)操作數(shù)后面例例l中綴表達(dá)式中綴表達(dá)式 2 + ( 3 * 8 4 ) / 5l后綴表達(dá)式后綴表達(dá)式 2 3 8 * 4 - 5 / +所有的求值計(jì)算皆按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向所有的求值計(jì)算皆按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行右進(jìn)行比中綴表達(dá)式的計(jì)算簡單比中綴表達(dá)式的計(jì)算簡單64算法思想算法思想l設(shè)一個(gè)棧；設(shè)一個(gè)棧；l順序掃描后綴表達(dá)式的每一項(xiàng)，根據(jù)其類型做如下順序掃描后綴表達(dá)式的每一項(xiàng)，根據(jù)其類型做如下處理：處理：p如果該項(xiàng)是操作數(shù)，則將其壓入棧頂；如果該項(xiàng)是操作數(shù)，則將其壓入棧頂；p如果該項(xiàng)是運(yùn)算符如果該項(xiàng)是運(yùn)算符 ，則連續(xù)從棧頂退出兩個(gè)操，則連續(xù)從棧頂退出兩個(gè)操作數(shù)作數(shù)

33、 x 和和 y，形成運(yùn)算指令，形成運(yùn)算指令 x y，并將結(jié)果重新，并將結(jié)果重新壓入棧頂。壓入棧頂。l表達(dá)式所有項(xiàng)掃描并處理完后（以符號(hào)表達(dá)式所有項(xiàng)掃描并處理完后（以符號(hào)“=”為結(jié)為結(jié)束），棧頂存放的就是計(jì)算結(jié)果。束），棧頂存放的就是計(jì)算結(jié)果。65棧棧輸入輸入操作序列操作序列 a b c d + e f / pushabcdc dpushpushpop, pop, pushpushpop, pop, pushb (c d)pop, pop, pusha+ b (c d)efe/fpushpushpop, pop, pushpop, pop, pusha+b (c-d) e/f66u中綴表達(dá)式的計(jì)

34、算中綴表達(dá)式的計(jì)算中綴表達(dá)式的計(jì)算次序中綴表達(dá)式的計(jì)算次序l根據(jù)運(yùn)算符優(yōu)先級(jí)由高到低的順序進(jìn)行運(yùn)算根據(jù)運(yùn)算符優(yōu)先級(jí)由高到低的順序進(jìn)行運(yùn)算l有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層括號(hào)，由內(nèi)向外進(jìn)行括號(hào)，由內(nèi)向外進(jìn)行l(wèi)乘方連續(xù)出現(xiàn)時(shí)先算最右面的乘方連續(xù)出現(xiàn)時(shí)先算最右面的計(jì)算方法計(jì)算方法1l按中綴表達(dá)式的順序計(jì)算（本書）按中綴表達(dá)式的順序計(jì)算（本書）計(jì)算方法計(jì)算方法2l先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式l再進(jìn)行后綴表達(dá)式求值再進(jìn)行后綴表達(dá)式求值67計(jì)算方法計(jì)算方法1l根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任根據(jù)上述三條運(yùn)

35、算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的運(yùn)算符意相繼出現(xiàn)的運(yùn)算符 1和和 2，都要比較優(yōu)先關(guān)系，都要比較優(yōu)先關(guān)系l運(yùn)算符間的優(yōu)先關(guān)系見下表運(yùn)算符間的優(yōu)先關(guān)系見下表 2 1 * * / + / + ( )( ) # # * * / / + + （ ） # # = = =68l算法思想算法思想p設(shè)定兩棧：操作數(shù)棧設(shè)定兩棧：操作數(shù)棧 opnd，運(yùn)算符棧，運(yùn)算符棧 optrp棧初始化：設(shè)操作數(shù)棧棧初始化：設(shè)操作數(shù)棧 opnd 為空；運(yùn)算符棧為空；運(yùn)算符棧 optr 的棧底元素為表達(dá)式起始符的棧底元素為表達(dá)式起始符 #；p依次讀入字符：是操作數(shù)則入依次讀入字符：是操作數(shù)則入opnd棧，是運(yùn)算符則棧，是

36、運(yùn)算符則要判斷（設(shè)要判斷（設(shè)optr 的棧頂元素為的棧頂元素為 1 ，當(dāng)前讀入的運(yùn)，當(dāng)前讀入的運(yùn)算符為算符為 2 ）： 1）if 1 2，則退棧、計(jì)算，結(jié)果壓入，則退棧、計(jì)算，結(jié)果壓入 opnd棧；棧；p重復(fù)，直至讀入字符和重復(fù)，直至讀入字符和optr的棧頂元素均為的棧頂元素均為 #，此時(shí)此時(shí)opnd 的棧頂即為計(jì)算結(jié)果的棧頂即為計(jì)算結(jié)果69optropndinputoperate3*(7-2)#push(opnd,3) #*(7-2)#3#push(optr,*)#,*3(7-2)#push(optr,()#,*, (37-2)#push(opnd,7)#,*, (3,7-2)#push(o

37、ptr,-)#,*, (, -3,72)#push(opnd,2)#,*, (, -3,7,2)#operate(7-2)#,*, (3,5)#pop(optr)#,*3,5#operate(3*5)#15#gettop(opnd)70l算法描述算法描述void evaluateexpression( operandtype &result) /s1為操作對(duì)象棧，為操作對(duì)象棧，s2為運(yùn)算符棧，為運(yùn)算符棧，op為運(yùn)算符集合為運(yùn)算符集合 seqstack s1,s2; s2.push(#); c=getchar(); while (c!=#) & (s2.gettop()!=#)

38、if (!in(c,op) s1.push(c); c=getchar(); 71 else switch (compare (s2.gettop(), c) case : temat=s2.pop(); b=s1.pop(); a=s1.pop(); result= operate(a,temat,b); s1.push(result); c=getchar();break; /switch /while result=s1.gettop(); /evaluateexpression72計(jì)算方法計(jì)算方法2將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式l設(shè)置一個(gè)棧，棧底元素為表達(dá)式起

39、始符設(shè)置一個(gè)棧，棧底元素為表達(dá)式起始符 #；l依次讀入中綴表達(dá)式的每一字符，是操作數(shù)則直接依次讀入中綴表達(dá)式的每一字符，是操作數(shù)則直接輸出，是運(yùn)算符則要判斷（設(shè)棧頂元素為輸出，是運(yùn)算符則要判斷（設(shè)棧頂元素為 1 ，當(dāng)前，當(dāng)前讀入的運(yùn)算符為讀入的運(yùn)算符為 2 ）：1）if 1 2， 則退棧，并輸出；則退棧，并輸出；3）if 1= 2 且不為且不為#， 則退棧，但不輸出，若退則退棧，但不輸出，若退出的是出的是 ( 則讀入下一字符則讀入下一字符 ；l重復(fù)，直至讀入字符和棧頂元素均為重復(fù)，直至讀入字符和棧頂元素均為 #，算法結(jié)，算法結(jié)束，此時(shí)輸出序列即為后綴表達(dá)式束，此時(shí)輸出序列即為后綴表達(dá)式73應(yīng)用

40、應(yīng)用3：迷宮求解問題：迷宮求解問題 入口入口出口出口74u基本思想基本思想從入口出發(fā)，沿某一方向向前探索從入口出發(fā)，沿某一方向向前探索l若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入路徑，繼續(xù)前進(jìn)；，則納入路徑，繼續(xù)前進(jìn)；l若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則換方向繼續(xù)探索，則換方向繼續(xù)探索;若四周若四周“均無通路均無通路”，則沿原路退回到前一位置，換，則沿原路退回到前一位置，換方向繼續(xù)探索方向繼續(xù)探索75u迷宮求解問題的迷宮求解問題的遞歸遞歸算法算法算法中用到的數(shù)據(jù)結(jié)構(gòu)算法中用到的數(shù)據(jù)結(jié)構(gòu)lint mazem+2p+2：表示迷宮：表示迷宮pm表示行數(shù)，表示行數(shù)，p表示列數(shù)表示列數(shù)p第第0、m+

41、1行，第行，第0、p+1 列是迷宮的圍墻列是迷宮的圍墻pmazeij=1時(shí)，表示該位置是墻壁，不能通行時(shí)，表示該位置是墻壁，不能通行mazeij=0時(shí)，表示該位置是通路時(shí)，表示該位置是通路lint markm+2p+2：標(biāo)志矩陣：標(biāo)志矩陣p初始為初始為0，當(dāng)某一位置，當(dāng)某一位置ij走過時(shí)，置走過時(shí)，置 markij=176loffsets move4：表示方向：表示方向struct offsets int a, b; char *d; moveq.dmoveq.amoveq.be(東東)01s(南南)10w(西西)0-1n(北北)-10n(北北)i-1, jw(西西)i, j-1當(dāng)前位置當(dāng)前位

42、置i, je(東東)i, j+1s(南南) i+1, j77遞歸函數(shù)遞歸函數(shù)int seekpath (int x, int y) int i,g,h; char *d; if ( x=m & y=p ) return 1; for (i=0; i4; i+) g=x+movei.a; h=y+movei.b; d=movei.dir; if ( !mazegh & !markgh ) markgh=1; if ( seekpath(g,h) ) cout“(“g“,”h“),”“direction”dir“,”; return 1; if ( x=1&y=1 ) cout“no pathvin maze”endl; return 0;78遞歸函數(shù)的主程序遞歸函數(shù)的主程序const