數(shù)據(jù)結(jié)構(gòu)講義(參考版)
2024-10-06 18:11本頁面
【正文】 ? 入隊前，先判 +1是否等于 ?+1 == ,若是則為隊滿 ? == ，為隊空 ? 設(shè)一個標(biāo)志位用來區(qū)別隊列是空還是滿 ? 初始化隊列時： =，標(biāo)志位為 FALSE ? 入隊后，使 =+1，則置標(biāo)志位為 TRUE ? 出隊后，將標(biāo)志位置為 FALSE ? 當(dāng) =, 且標(biāo)志位為 TRUE時，隊列滿 ? 當(dāng) =, 但標(biāo)志位為 FALSE時，隊列空 ? 其他為非空非滿 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 47/51 順序存儲方式 ? 計數(shù)變量 ? 初始化隊列時 c := 0。 }SqQueue。 int front。 ? 頭指針 ? 尾指針 define MAXQSIZE 100。Q , QElemType amp。 ? 鏈隊列添加頭結(jié)點，并令頭指針指向頭結(jié)點 ? 空鏈隊列 ( == ) 隊頭指針 隊尾指針 . . . 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 40/51 基本操作－入隊列 ? EnQueue( amp。 QueuePtr rear。 }QNode , *QueuePtr。e ) 用 e返回隊列的隊頭元素 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 38/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 39/51 鏈?zhǔn)酱鎯Ψ绞? typedef struct QNode { QElemType data。Q , amp。Q ) 銷毀隊列，釋放隊列所占用的內(nèi)存空間 ? EnQueue(amp。 ? 空隊列 ? 不含數(shù)據(jù)元素的隊列 ? 運算特性 ? 先進先出 (First In First OutFIFO) 2 3 4 1 1 1 2 2 front (head) rear (tail) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 36/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 37/51 隊列的基本操作 ? InitQueue( amp。 } } } 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 34/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本運算 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本運算 ? 隊列的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 35/51 基本概念和特性 ? 隊列（ queue） ? 限定僅在一端插入 ,另一端刪除的線性表。 =,=。 = – 1。 =,=。 = 1。 =,=。 else { = – 1。 while( !empty( S ) ) { Pop( S , temp2 )。 = z。 = x 。 return。 InitStack(S)。 //輔助塔編號 char z。 //問題規(guī)模 char x。 hanoi( n1 , y , x , z )。 move( x , n , z )。 ? 原問題為： hanoi(n， X， Y， Z) ? 化簡為： hanoi(n1， X， Z， Y) move(X， n， Z) //把 X上的 n號盤 移到 Z上 hanoi(n1， Y， X， Z) n1 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 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 )。 } 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個直徑各不相同的圓盤，各圓盤按直徑從小到大編為 1~n ? 要求： 將 X 塔上的 n個圓盤按規(guī)則移至 Z上，并仍按同樣順序疊排 ? 移動規(guī)則： ①每次只能移動一個圓盤；②移動的圓盤可以插在任一塔座上，但是在任一時刻都不能將大盤放在小盤上。 Push( S , i1 )。 Pop( S , i )。 if( i = 1 ) { i = 1。 Push( S , n )。 } 實在參數(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
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1