棧和隊列ppt課件(編輯修改稿)
2025-05-26 02:45 本頁面
【文章內(nèi)容簡介】 遞歸的要點： 1. 由系統(tǒng)提供一個信息棧，保留函數(shù)調(diào)用時的相關信息（調(diào)用時的信息、返回地址、局部變量）； 2. 每執(zhí)行遞歸調(diào)用語句時，將有關信息送入棧，轉(zhuǎn)入函數(shù)入口； 3. 每當執(zhí)行到返回語句時，保存 計算結(jié)果 ，釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)，彈出 返回地址 返回。 2022/5/26 37 多個函數(shù)嵌套調(diào)用的規(guī)則是： 此時的內(nèi)存管理實行 “棧式管理” 后調(diào)用先返回 ！ 例如： void main( ){ void a( ){ void b( ){ … … … a( )。 b( )。 … … }//main }// a }// b Main的數(shù)據(jù)區(qū) 函數(shù) a的數(shù)據(jù)區(qū) 函數(shù) b的數(shù)據(jù)區(qū) 2022/5/26 38 { n=3。 p= fac (n)。 printf(p)。 } main ( ) { …… f= fac(n1) *3。 return( f )。 } fac (3 ) { …… f= fac(n1) *2。 return( f )。 } fac (2 ) { …… f= fac(n1) *1。 return( f )。 } fac (1 ) { …… f= 1。 return( f )。 } fac (0 ) { n=3。 p= fac (n)。 } main ( ) { …… f= fac(n1) *3。 } fac (3 ) { …… f= fac(n1) *2。 } fac (2 ) { …… f= fac(n1) *1。 } fac (1 ) { …… f= 1。 return( f )。 } fac (0 ) fac(3) fac(2) fac(1) fac(0) RET RET RET RET n 地址 3 L 3 L 3 L 3 L 3 L 3 L 3 L n 地址 3 L1 3 L1 3 L1 3 L1 3 L1 n 地址 2 L2 2 L2 2 L2 n 地址 1 L3 2022/5/26 40 例 2 Hanoi 塔問題 a b c 2022/5/26 41 例 2 Hanoi 塔問題 a b c 2022/5/26 42 例 2 Hanoi 塔問題 a b c 2022/5/26 43 例 2 Hanoi 塔問題 a b c 2022/5/26 44 void hanoi (int n, char x, char y, char z) { // 將塔座 x上按直徑由小到大且至上而下編號為 1至 n // 的 n個圓盤按規(guī)則搬到塔座 z上， y可用作輔助塔座。 1 if (n==1) 2 move(x, 1, z)。 // 將編號為１的圓盤從 x移到 z 3 else { 4 hanoi(n1, x, z, y)。 // 將 x上編號為１至 n1的 //圓盤移到 y, z作輔助塔 5 move(x, n, z)。 // 將編號為 n的圓盤從 x移到 z 6 hanoi(n1, y, x, z)。 // 將 y上編號為１至 n1的 //圓盤移到 z, x作輔助塔 7 } 8 } 2022/5/26 45 void hanoi (int n, char x, char y, char z) 1{ 2 if (n==1) 3 move(x, 1, z)。 4 else { 5 hanoi(n1, x, z, y)。 6 move(x, n, z)。 7 hanoi(n1, y, x, z)。 8 } 9 } 0 3 a b c 返址 n x y z 6 2 a c b 6 1 a b c 8 1 c a b 2022/5/26 46 隊列 2022/5/26 47 抽象數(shù)據(jù)類型隊列的定義 隊列：是一種 先進先出 的線性表，它的操作只能在表的兩端進行。 隊尾 隊首 a1 a2 a3 …… an1 an 2022/5/26 48 ADT Queue { 數(shù)據(jù)對象： D＝ {ai | ai∈ ElemSet, i=1,2,...,n, n≥0} 數(shù)據(jù)關系： R1＝ { a i1,ai | ai1, ai ∈ D, i=2,...,n} 約定其中 a1 端為 隊列頭 ， an 端為 隊列尾 基本操作： } ADT Queue 隊列的抽象數(shù)據(jù)類型 2022/5/26 49 隊列的基本操作： InitQueue(amp。Q) //創(chuàng)建空隊列 Q DestroyQueue(amp。Q) //銷毀隊列 Q QueueLength(Q) //求隊列長度 GetHead(Q, amp。e) //取隊首元素 ClearQueue(amp。Q) //隊列置空 DelQueue(amp。Q, amp。e) //出隊 EnQueue(amp。Q, e) //入隊 2022/5/26 50 QueueEmpty(Q) 初始條件
教學課件相關推薦
鄂ICP備17016276號-1