數(shù)據(jù)結構講義(文件)
【正文】 ? 本章小結 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 22/51 棧的應用 數(shù)制轉換 ? 輸入任意非負十進制整數(shù)，打印輸出與其等值的八進制數(shù) ? 有轉換公式如下 N = ( N div d )*d + N mod d ( div為整除，除得結果含的小數(shù)直接舍去， mod為求余 ,d為進制，此時為 8 ) ? 例如將十進制數(shù) 1348轉成對應的八進制數(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 ? 算法的特點是：先得到的結果最后輸出，后得到的結果應該先輸出，才能輸出正確的轉換后的八進制數(shù)，存在明顯的先進后出的特性，可以使用棧來進行轉換。 ? 關鍵點 ? 用較簡單的新問題來表示較復雜的原問題 ? 不能產生自己調用自己的無窮序列 ， 即必須有一個遞歸調用序列的 “ 出口” ， 來終止遞歸調用 。 return ( res*Fact( n1 ) )。 … first( m , n )。 2:… } int second( int d ) { int x,y。 } 實在參數(shù) | 返回地址 | 局部變量 3|X0|3 Fact(3) 2|10|2 Fact(2) 1|11|1 Fact(1) 1 2 6 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 28/51 遞歸算法轉化成非遞歸算法 (用棧 ) 3|X0|… Fact(3) 2|10|3 Fact(2) 1|11|2 Fact(1) int Fact( int n ) { int result =1, i。 if( i = 1 ) { i = 1。 Push( S , i1 )。 ? 原問題為： hanoi(n， X， Y， Z) ? 化簡為： hanoi(n1， X， Z， Y) move(X， n， Z) //把 X上的 n號盤 移到 Z上 hanoi(n1， Y， X， Z) n1 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 31/51 漢諾（ Hanoi)塔 ? 遞歸算法實現(xiàn) void Hanoi( int n , char x , char y , char z ) { if( n = = 1 ) move( x , 1 , z )。 hanoi( n1 , y , x , z )。 //輔助塔編號 char z。 return。 = z。 else { = – 1。 = 1。 = – 1。 } } } 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 34/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本運算 ? 棧的順序存儲方式和鏈式存儲方式及其上的操作 ? 棧的應用 ? 隊列的基本概念和特性 ? 隊列的基本運算 ? 隊列的順序存儲方式和鏈式存儲方式及其上的操作 ? 隊列的應用 ? 本章小結 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 35/51 基本概念和特性 ? 隊列（ queue） ? 限定僅在一端插入 ,另一端刪除的線性表。Q ) 銷毀隊列，釋放隊列所占用的內存空間 ? EnQueue(amp。e ) 用 e返回隊列的隊頭元素 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 38/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈式存儲方式及其上的操作 ? 棧的應用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的順序存儲方式和鏈式存儲方式及其上的操作 ? 隊列的應用 ? 本章小結 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 39/51 鏈式存儲方式 typedef struct QNode { QElemType data。 QueuePtr rear。Q , QElemType amp。 int front。 ? 入隊前，先判 +1是否等于 ?+1 == ,若是則為隊滿 ? == ，為隊空 ? 設一個標志位用來區(qū)別隊列是空還是滿 ? 初始化隊列時： =，標志位為 FALSE ? 入隊后，使 =+1，則置標志位為 TRUE ? 出隊后，將標志位置為 FALSE ? 當 =, 且標志位為 TRUE時，隊列滿 ? 當 =, 但標志位為 FALSE時，隊列空 ? 其他為非空非滿 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 47/51 順序存儲方式 ? 計數(shù)變量 ? 初始化隊列時 c := 0。 }SqQueue。 ? 頭指針 ? 尾指針 define MAXQSIZE 100。 ? 鏈隊列添加頭結點，并令頭指針指向頭結點 ? 空鏈隊列 ( == ) 隊頭指針 隊尾指針 . . . 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 40/51 基本操作－入隊列 ? EnQueue( amp。 }QNode , *QueuePtr。Q , amp。 ? 空隊列 ? 不含數(shù)據(jù)元素的隊列 ? 運算特性 ? 先進先出 (First In First OutFIFO) 2 3 4 1 1 1 2 2 front (head) rear (tail) 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 36/51 第三章 棧和隊列 ? 棧的基本概念和特性
環(huán)評公示相關推薦
鄂ICP備17016276號-1