數(shù)據(jù)結(jié)構(gòu)講義-wenkub.com
2024-10-02 18:11 本頁面
【正文】 ? 棧滿條件： = MAXQSIZE ? 棧空條件： = 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 43/51 順序存儲方式 ? 順序存儲方式的缺點 Job 1 Job 2 Job 3 Job 4 Job 5 Job 6 Job 7 ?1 0 1 2 3 4 5 6 ? append Job 1 ? append Job 2 ? append Job 3 ? serve Job 1 ? append Job 4 ? append Job 5 ? append Job 6 ? serve Job 2 ? append Job 7 ? append Job 8 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 44/51 順序存儲方式 解決的方法 (循環(huán)隊列 ) [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] Job 1 Job 2 Job 3 Job 4 Job 5 Job 6 ? append Job 1 ? append Job 2 ? append Job 3 ? serve Job 1 ? append Job 4 ? append Job 5 ? append Job 6 ? serve Job 2 ? append Job 7 7 ? append Job 8 Job 8 = 3 =3 加入新元素： rear++ 加入 job 移去隊列頭的元素 ，然后 front “++” empty or full ? 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 45/51 順序存儲方式 ? 隊列空還是滿的判斷 ? 在隊列中預留一個空位 ? 設定一個標志 ? 設置一個數(shù)字計數(shù)器 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 46/51 順序存儲方式 ? 在隊列中預留一個空位 ? 犧牲一個元素空間，來區(qū)別隊空或隊滿。 typedef struct //數(shù)組方式定義順序隊列 { QElem elem[MAXSIZE]。Q , QElemType e ) 隊列中加入新的元素 插入元素 e為 Q的新的隊尾元素 (類似于在單鏈表的表尾插入 ) ? 為新插入的元素 e生成一個新的隊列結(jié)點 *p ? 賦值 p?data = e ? 更改指針域 ? p?next = ?next (NULL) ? ?next = p ? = p 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 41/51 基本操作－出隊列 ? DeQueue( LinkQueue amp。 typedef struct { QueuePtr front。e) 刪除隊列頭的元素，用 e返回其值 ? QueueEmpty( Q ) 判定隊列是否為空 (TRUE/FALSE) ? GetHead( Q , amp。Q ) 初始化操作，設置一個空隊列 ? DestroyQueue( amp。 Push( S , temp )。 Push( S , temp )。 Push( S , temp )。 if( = = 1 ) move( , )。 temp,y = y 。 if( n = = 1 ) { move(x,z) 。 //起始塔編號 char y。 // ?hanoi( 1 , x , y , z )。 X Y Z 1 n 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 30/51 漢諾（ Hanoi)塔 ? 算法思想 ? 當 n=1： 只需 將該圓盤從 X移 到 Z即可 ? 當 n1：若能將壓在 n號盤上的 n1個圓盤按規(guī)則移至 Y， 然后把 n號盤從 X移到 Z上， 最后再將 Y上的 n1個 圓盤按規(guī)則移至 Z上。 } } else { Push( S , i )。 while( !empty( S ) ) { Pop( S , i )。 1:return ( res*Fact( n1 ) )。 … second( i )。 int main() { int m,n。 if( n = 1 ) return 1。 ? 基本原理：基本原理是重復地把問題轉(zhuǎn)化為與原問題相似的新問題 ， 直到問題可解決為止 。 //釋放出棧結(jié)點所占內(nèi)存空間 return OK。 *pE = (* pPS)data。 } 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 20/51 鏈式存儲結(jié)構(gòu)上棧操作的實現(xiàn) ? 出棧操作 Pop(amp。 pdata = e。S, e) Status Push (LinkStack *pPS , SElem e) { SNode *p = NULL。 if( * pPS ) { DestroyLinkStack( pPS )。 struct LNode *next。 } 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 16/51 棧的鏈式存儲方式 typedef struct { SElem data。 } 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 15/51 順序存儲結(jié)構(gòu)上棧操作的實現(xiàn) ? 取棧頂元素 GetTop(S,amp。 if ( pStop = = 0 )//棧為空 return ERROR。 else { pSelem[ pStop ] = e； ++(pStop)
環(huán)評公示相關推薦
鄂ICP備17016276號-1