數(shù)據(jù)結構講義-全文預覽
【正文】 ? 棧的基本操作 ? 棧的順序存儲方式和鏈式存儲方式及其上的操作 ? 棧的應用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的順序存儲方式和鏈式存儲方式及其上的操作 ? 隊列的應用 ? 本章小結 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 37/51 隊列的基本操作 ? InitQueue( amp。 =,=。 =,=。 =,=。 while( !empty( S ) ) { Pop( S , temp2 )。 = x 。 InitStack(S)。 //問題規(guī)模 char x。 move( x , n , z )。 } 3 2 1 2 3(fact) 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 29/51 漢諾（ Hanoi)塔 ? 設： 有 X、 Y、 Z三個塔座，在 X上按直徑大小遞減次序依次插有 n個直徑各不相同的圓盤，各圓盤按直徑從小到大編為 1~n ? 要求： 將 X 塔上的 n個圓盤按規(guī)則移至 Z上，并仍按同樣順序疊排 ? 移動規(guī)則： ①每次只能移動一個圓盤；②移動的圓盤可以插在任一塔座上，但是在任一時刻都不能將大盤放在小盤上。 Pop( S , i )。 Push( S , n )。 if( n = 1 ) return 1。 } int first( int s , int t ) { int i。 int second( int d )。 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 24/51 遞歸算法的實現(xiàn)例子 ? 計算階乘 ? 階乘的函數(shù)定義 ? 算法實現(xiàn) int Fact( int n ) { int res = n。 ? 遞歸過程的特點：是程序設計的一個強有力的工具 ， 它具有結構清晰 ，程序易編 、 易讀 、 易調試 ， 程序正確性易證明等優(yōu)點；但運行效率低 。//修改棧頂指針，指向新的棧頂 free( p )。 if( ! pPS || !(* pPS) || !pE ) return ERROR。 //改變棧頂指針值，指向新的棧頂 return OK。//為新加入的結點分配存儲空間 if( !p ) return ERROR。 } pS pPS 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 19/51 鏈式存儲結構上棧操作的實現(xiàn) ? 入棧操作 Push(amp。S) Status InitStack( LinkStack *pPS ) { if( ! pPS ) return ERROR。 Typedef struct LNode { ElemType data。 return OK。 return OK。e) Status Pop ( PSeqStack pS , SElem *pE ) { if( !pS ) return ERROR。 if ( pStop = = ARRMAX ) //棧空間已滿 return ERROR。 if( (*pS)top = = 0 ) return TRUE。 free( *pPS )。 } pPS pS Elem[ARRMAX] top NULL 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 11/51 順序存儲結構上棧操作的實現(xiàn) ? 銷毀棧 DestroyStack( amp。 return OK。 } ARRMAX 棧底 棧頂 X 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 10/51 順序存儲結構上棧操作的實現(xiàn) ? 創(chuàng)建空棧 InitStack(amp。 return OK。//存儲數(shù)據(jù)元素的數(shù)組 int top。e) 出棧函數(shù) ， 若 S不空 ， 則返回棧頂元素 ， 并刪除棧頂元素；否則返回 空元素 NULL。S ) 銷毀棧 S ? ClearStack(amp。S) 初始化操作，設定一個空棧 S ? DestroyStack( amp。S,amp。 //N為一自定義的常數(shù)，表示棧的大小 typedef struct { SElemType elem[ARRMAX ]。S) ? 方式一：聲明 SeqStack的變量 S，由系統(tǒng)自動分析內存空間，所建?？臻g在程序的堆棧區(qū)上 Status InitStack( PSeqStack pS ) { pStop = 0。S )。 (*pPS)top = 0。pS )。 if( (*pPS)top != 0 )//棧不為空，這里定義為不能銷毀棧 return ERROR。 } 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日星期日 12/51 順序存儲結構上棧操作的實現(xiàn) ? 判斷棧 S是否為 空 StackEmpty(S) Status StackEmpty( PSeqStack *pS ) { if( !pS ) return ERROR。S, e) Status Push (PSeqStack pS , SElem e) { if( !pS ) return ERROR。S , amp。 *pE = pSelem[ pStop ] 。 *pE = pSelem[ pStop 1 ]。 } SNode ,*LinkStack。 pS pS NULL 電子科大科 園 培訓中心 數(shù)據(jù)結構 2022年 10月 23日
環(huán)評公示相關推薦
鄂ICP備17016276號-1