【正文】 m data。 if ( pStop = = 0 )//棧為空 return ERROR。 else return FALSE。S ) ? 由方式一創(chuàng)建的棧，由于是通過系統(tǒng)自動分配的空間，因此銷毀也是由系統(tǒng)自動完成，可不用實現(xiàn)此函數(shù) ? 由方式二創(chuàng)建的棧，是在堆上進行分配的，要自己銷毀棧，而棧的銷毀方式與具體應(yīng)用要求有關(guān)。S) ? 方式二：聲明一個指向要創(chuàng)建的棧的指針 pS，采用動態(tài)分配內(nèi)存的方式創(chuàng)建棧 ,所建?？臻g在程序的堆區(qū)上 Status InitStack( PSeqStack *pPS ) { *pPS = (pSeqStack)malloc( sizeof( SeqStack ) )。 //棧頂指針， elem[0]為棧底 }SeqStack,*PSeqStack。S) 置棧空操作 ? StackEmpty(S) 判棧 S是否為 空 （ TRUE/FALSE） ? Push(amp。S, e) 入棧操作 ， 在棧 S頂部插入元素 e， 相當(dāng)于線性表的 INSERT(L, n+1, x) ? Pop(amp。 ? ?？諘r = = 0 ? 棧滿時 = = ARRMAX 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 9/51 順序存儲結(jié)構(gòu)上棧操作的實現(xiàn) ? 創(chuàng)建空棧 InitStack(amp。 if( (*pPS) = = NULL ) return OVERFLOW。這里舉的只是一個例子，便于大家理解 Status DestroyStack( PSeqStack *pPS ) { if( !pPS || !(*pPS) ) return ERROR。 } ？思考為何不采用 Status StackEmpty( SeqStack S )的聲明方式聲明函數(shù)頭 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 13/51 順序存儲結(jié)構(gòu)上棧操作的實現(xiàn) ? 入棧操作 Push(amp。 (pStop)。 SNode *next。 //如果輸入的棧不空，則銷毀此棧，由于銷毀工作與具體應(yīng)用 // 相關(guān)，不給出具體的操作過程 } (* pPS) = NULL。 ppNext = (* pPS)。 p = (* pPS)。 ? 關(guān)鍵點 ? 用較簡單的新問題來表示較復(fù)雜的原問題 ? 不能產(chǎn)生自己調(diào)用自己的無窮序列 ， 即必須有一個遞歸調(diào)用序列的 “ 出口” ， 來終止遞歸調(diào)用 。 … first( m , 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 result =1, i。 Push( S , i1 )。 hanoi( n1 , y , x , z )。 return。 else { = – 1。 = – 1。Q ) 銷毀隊列，釋放隊列所占用的內(nèi)存空間 ? EnQueue(amp。 QueuePtr rear。 int front。 }SqQueue。 ? 鏈隊列添加頭結(jié)點，并令頭指針指向頭結(jié)點 ? 空鏈隊列 ( == ) 隊頭指針 隊尾指針 . . . 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 40/51 基本操作－入隊列 ? EnQueue( amp。Q , amp。 =,=。 =,=。 = x 。 //問題規(guī)模 char x。 } 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 , n )。 } int first( int s , int t ) { int i。 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 24/51 遞歸算法的實現(xiàn)例子 ? 計算階乘 ? 階乘的函數(shù)定義 ? 算法實現(xiàn) int Fact( int n ) { int res = n。//修改棧頂指針，指向新的棧頂 free( p )。 //改變棧頂指針值，指向新的棧頂 return OK。 } pS pPS 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 19/51 鏈?zhǔn)酱鎯Y(jié)構(gòu)上棧操作的實現(xiàn) ? 入棧操作 Push(amp。 Typedef struct LNode { ElemType data。 return OK。 if ( pStop = = ARRMAX ) //?？臻g已滿 return ERROR。 free( *pPS )。 return OK。 return OK。e) 出棧函數(shù) ， 若 S不空 ， 則返回棧頂元素 ，