數(shù)據(jù)結(jié)構(gòu)講義(編輯修改稿)
2024-10-22 18:11 本頁面
【文章內(nèi)容簡介】 所占內(nèi)存空間 return OK。 } 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 21/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本運算 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本運算 ? 隊列的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 22/51 棧的應(yīng)用 數(shù)制轉(zhuǎn)換 ? 輸入任意非負十進制整數(shù)，打印輸出與其等值的八進制數(shù) ? 有轉(zhuǎn)換公式如下 N = ( N div d )*d + N mod d ( div為整除，除得結(jié)果含的小數(shù)直接舍去， mod為求余 ,d為進制，此時為 8 ) ? 例如將十進制數(shù) 1348轉(zhuǎn)成對應(yīng)的八進制數(shù) 2504 1348 = ( 1348 div 8 )*8 + 1348 mod 8 = 168*8 + 4 168 = ( 168 div 8 )*8 + 168 mod 8 = 21*8 + 0 21 = ( 21 div 8 )*8 + 21 mod 8 = 2*8 + 5 2 = ( 2 div 8 ) + 2 mod 8 = 0 + 2 ? 算法的特點是：先得到的結(jié)果最后輸出，后得到的結(jié)果應(yīng)該先輸出，才能輸出正確的轉(zhuǎn)換后的八進制數(shù)，存在明顯的先進后出的特性，可以使用棧來進行轉(zhuǎn)換。 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 23/51 棧的重要應(yīng)用 遞歸 ? 遞歸是棧的另一個重要應(yīng)用 ， 也是程序設(shè)計強有力的工具 。 ? 遞歸過程的特點：是程序設(shè)計的一個強有力的工具 ， 它具有結(jié)構(gòu)清晰 ，程序易編 、 易讀 、 易調(diào)試 ， 程序正確性易證明等優(yōu)點；但運行效率低 。 ? 基本原理：基本原理是重復(fù)地把問題轉(zhuǎn)化為與原問題相似的新問題 ， 直到問題可解決為止 。 ? 關(guān)鍵點 ? 用較簡單的新問題來表示較復(fù)雜的原問題 ? 不能產(chǎn)生自己調(diào)用自己的無窮序列 ， 即必須有一個遞歸調(diào)用序列的 “ 出口” ， 來終止遞歸調(diào)用 。 ? 實現(xiàn)：遞歸過程都是通過棧來實現(xiàn)的， 并且任何 遞歸算法均可通過棧改寫為非遞歸算法 。 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 24/51 遞歸算法的實現(xiàn)例子 ? 計算階乘 ? 階乘的函數(shù)定義 ? 算法實現(xiàn) int Fact( int n ) { int res = n。 if( n = 1 ) return 1。 return ( res*Fact( n1 ) )。 } Fact( n ) = 1 若 n = 0,1 n*fact(n1) 若 n 1 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 25/51 程序運行如何實現(xiàn)遞歸算法？ ? 函數(shù)調(diào)用時和調(diào)用返回時，系統(tǒng)中究竟發(fā)生了什么事？ ? 調(diào)用發(fā)生時 ?將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存 ?為被調(diào)用函數(shù)的局部變量分配存儲空間 ?將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口 ? 調(diào)用返回時 ?保存被調(diào)用函數(shù)的返回結(jié)果 ?釋放被調(diào)用函數(shù)占用的數(shù)據(jù)區(qū) ?依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù) ? 這些參數(shù)的保存都是在系統(tǒng)的工作棧中進行的 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 26/51 系統(tǒng)的工作棧 int first( int s , int t )。 int second( int d )。 int main() { int m,n。 … first( m , n )。 1:…...。 } int first( int s , int t ) { int i。 … second( i )。 2:… } int second( int d ) { int x,y。 … } |X0|m,n,… main m,n|10|i,… first i|20|x,y,… second 系統(tǒng)工作棧 實在參數(shù) | 返回地址 | 局部變量 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 27/51 系統(tǒng)的工作棧 int Fact( int n ) { int res = n。 if( n = 1 ) return 1。 1:return ( res*Fact( n1 ) )。 } 實在參數(shù) | 返回地址 | 局部變量 3|X0|3 Fact(3) 2|10|2 Fact(2) 1|11|1 Fact(1) 1 2 6 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 28/51 遞歸算法轉(zhuǎn)化成非遞歸算法 (用棧 ) 3|X0|… Fact(3) 2|10|3 Fact(2) 1|11|2 Fact(1) int Fact( int n ) { int result =1, i。 InitStack( S )。 Push( S , n )。 while( !empty( S ) ) { Pop( S , i )。 if( i = 1 ) { i = 1。 while( !empty( S ) ) { result = result *i。 Pop( S , i )。 } } else { Push( S , i )。 Push( S , i1 )。 } } return result。 } 3 2 1 2 3(fact) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 29/51 漢諾（ Hanoi)塔 ? 設(shè)： 有 X、 Y、 Z三個塔座，在 X上按直徑大小遞減次序依次插有 n個
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1