第三章棧和隊(duì)列(編輯修改稿)
2025-08-28 12:51 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ( ) { C( ) { … … C( )。 B( )。 … … } } 遞歸算法的編寫(xiě) 1） 將問(wèn)題用遞歸的方式描述 （ 定義 ） 2） 根據(jù)問(wèn)題的遞歸描述 （ 定義 ） 編寫(xiě)遞歸算法 問(wèn)題的遞歸描述 （ 定義 ） 遞歸定義包括兩項(xiàng) 基本項(xiàng) （ 終止項(xiàng) ） ：描述遞歸終止時(shí)問(wèn)題的求解； 遞歸項(xiàng)：將問(wèn)題分解為與原問(wèn)題性質(zhì)相同 ， 但規(guī)模較小的問(wèn)題； 例 階乘函數(shù) n!= 1* 2* 3* 4 * (n1)* n n!遞歸定義 n!= 1 當(dāng) n=1 時(shí) n!= n (n1)! 當(dāng) n 1 時(shí) 用 (n1)!定義 n! 計(jì)算 5的階乘（ 5！ =5X4X3X2X1） int f(int n) { if ( n = = 1) return (1)。 else return ( n * f(n1))。 } f(1) f(2) f(3) f(4) f(5) top 1 f(1)=1 2*f(1) f(2)=2*f(1) 3*f(2) f(3)=3*f(2) 4*f(3) f(4)=4*f(3) 5*f(4) f(5)=5*f(4) 例 1 階乘函數(shù) void print(int w) { int i。 if ( w!=0) { print(w1)。 for(i=1。i=w。++i) printf(“%3d,”,w)。 printf(“/n”)。 } } 運(yùn)行結(jié)果： 1， 2， 2， 3， 3， 3， 例 2 遞歸的執(zhí)行情況分析 遞歸調(diào)用執(zhí)行情況如下： 主程序 (1) print(w) w=3。 3 print(2)。 （ 1） w=3 top (2) 輸出： 3, 3, 3 w 2 print(1)。 （ 2） w=2 （ 1） w=3 top (3) 輸出： 2, 2 w 1 print(0)。 （ 3） w=1 （ 2） w=2 （ 1） w=3 top (4)輸出： 1 w 0 （ 4） w=0 （ 3） w=1 （ 2） w=2 （ 1） w=3 top w (2) 2 (1) 3 (4)輸出： (3) 1 (2) 2 (1) 3 top 3 (1 ) 3 返回 (3) 1 (2) 2 (1) 3 (4) 0 結(jié)束 { print(w1)。 for(i=1。i=w。++i) printf(“%3d,”,w)。 printf(“/n”)。 } 隊(duì)列 隊(duì)列的概念 循環(huán)隊(duì)列 ——隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 隊(duì)列的概念 ? 什么是隊(duì)列 ? ? 隊(duì)列 是限定僅能在一端進(jìn)行刪除，另一端進(jìn)行插入的線性表。 a0 a1 a2 a3 a4 入隊(duì) 隊(duì)頭 隊(duì)尾 出隊(duì) 隊(duì)列的示意圖 允許刪除的一端稱為 隊(duì)頭 ，允許插入的一端稱為 隊(duì)尾 隊(duì)列的長(zhǎng)度 ：隊(duì)列中元素的個(gè)數(shù) 隊(duì)列的特點(diǎn) 先進(jìn)先出 (FIFO) ? 隊(duì)列的基本操作 InitQueue(Q) 將 Q置為一個(gè)空隊(duì)列 QueueEmpty(Q) 若 Q為空隊(duì)列返回 TRUE， 否則 FALSE QueueLen(Q) 返回隊(duì)列 Q中元素個(gè)數(shù) ， 即隊(duì)的長(zhǎng)度 GetHead(Q) 返回 Q的隊(duì)頭元素 EnQueue(Q,e) 插入元素 e為隊(duì) Q的新隊(duì)尾元素 DeQueue(Q,e) 刪除 Q的隊(duì)頭元素 ， 并用 e返回其值 隊(duì)列的順序存儲(chǔ)和循環(huán)隊(duì)列 ?用一個(gè)數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列的順序存儲(chǔ) ?隊(duì)頭指針 front指向隊(duì)頭元素實(shí)際位置的 前一個(gè) 位置 ?隊(duì)尾指針 rear指向隊(duì)尾元素在隊(duì)列中的實(shí)際位置 隊(duì)列順序結(jié)構(gòu)的 C語(yǔ)言描述： typedef struct{ Elemtype elem[maxsize]。 int front。 int rear。 }SqQueue。 SqQueue *Q。 ? 實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn) elem[M] front=1 rear=1 1 2 3 4 5 0 隊(duì)空 1 2 3 4 5 0 front J1,J2,J3入隊(duì) J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入隊(duì) J4 J5 J6 front 設(shè)兩個(gè)指針 front,rear,約定： rear指示隊(duì)尾元素； front指示隊(duì)頭元素前一位置
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1