數(shù)據(jù)結(jié)構(gòu)講義-預(yù)覽頁
【正文】 星期日 17/51 棧的鏈?zhǔn)酱鎯Ψ绞? ? 鏈?zhǔn)綏Ｅc單鏈表采用相同的存儲結(jié)構(gòu)，那么鏈?zhǔn)綏Ｊ欠褚哺鷨捂湵硪粯有枰粋€頭指針呢？ ? 頭指針的作用？ 不需要區(qū)別插入或刪除的是否是單鏈表的第一個結(jié)點，給插入和刪除帶來方便和統(tǒng)一的處理方式 ? 棧中結(jié)點的插入和刪除方式 插入和刪除操作只能在棧的棧頂進(jìn)行，類似于插入和刪除操作只能在單鏈表的表頭進(jìn)行，不涉及表中其它結(jié)點的插入和刪除問題 ? 結(jié)論 鏈?zhǔn)綏？梢圆灰^結(jié)點，不影響其入棧和出棧操作 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 18/51 鏈?zhǔn)酱鎯Y(jié)構(gòu)上棧操作的實現(xiàn) ? 創(chuàng)建空棧 InitStack(amp。 return OK。 p = (SNode*)malloc( sizeof(SNode) )。 (* pPS) = p。e) Status Pop (LinkStack *pPS , SElem *pE ) { SNode *p = NULL。 (* pPS) = (* pPS)pNext。 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 23/51 棧的重要應(yīng)用 遞歸 ? 遞歸是棧的另一個重要應(yīng)用 ， 也是程序設(shè)計強有力的工具 。 ? 實現(xiàn)：遞歸過程都是通過棧來實現(xiàn)的， 并且任何 遞歸算法均可通過棧改寫為非遞歸算法 。 } Fact( n ) = 1 若 n = 0,1 n*fact(n1) 若 n 1 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 25/51 程序運行如何實現(xiàn)遞歸算法？ ? 函數(shù)調(diào)用時和調(diào)用返回時，系統(tǒng)中究竟發(fā)生了什么事？ ? 調(diào)用發(fā)生時 ?將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存 ?為被調(diào)用函數(shù)的局部變量分配存儲空間 ?將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口 ? 調(diào)用返回時 ?保存被調(diào)用函數(shù)的返回結(jié)果 ?釋放被調(diào)用函數(shù)占用的數(shù)據(jù)區(qū) ?依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù) ? 這些參數(shù)的保存都是在系統(tǒng)的工作棧中進(jìn)行的 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 26/51 系統(tǒng)的工作棧 int first( int s , int t )。 1:…...。 … } |X0|m,n,… main m,n|10|i,… first i|20|x,y,… second 系統(tǒng)工作棧 實在參數(shù) | 返回地址 | 局部變量 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 27/51 系統(tǒng)的工作棧 int Fact( int n ) { int res = n。 InitStack( S )。 while( !empty( S ) ) { result = result *i。 } } return result。 else { hanoi( n1 , x , z , y )。 } } 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 32/51 漢諾（ Hanoi)塔 ? 非遞歸算法中入棧的數(shù)據(jù)結(jié)構(gòu) Typedef struct { int n。 //目標(biāo)塔編號 }DataType 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 33/51 漢諾（ Hanoi)塔 ? 對應(yīng)的非遞歸算法 void Hanoi( int n , char x , char y , char z ) { DataType temp, temp2。 } = n 。 Push( S , temp )。 temp,x = 。 temp,x = 。 temp,x = 。 ? 允許插入的一端叫隊列尾 ( rear),允許刪除的一端叫隊列頭 (front)。Q ， e) 入隊列操作，隊尾插入元素 e ? DeQueue( amp。 struct QNode *next。 }LinkQueue。e ) 隊列不空，則刪除 Q的隊頭元素，用 e返回其值 刪除元素類似于的單鏈表的表頭進(jìn)行刪除操作 ? 判斷隊列是否為空 ( =?= ) ? p = ?next(p指向待刪除的隊頭元素 )， e = p?data ? 改變指針域 ? ?next = p?next ?如果棧已空，則改變隊列尾指針 = (均指向頭結(jié)點 ) ? 釋放已刪除結(jié)點所占內(nèi)存空間 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 42/51 順序存儲方式 ? 采用一組連續(xù)的內(nèi)存單元來存儲隊列元素 ? 用兩個指針來指示隊頭和隊尾。 int rear。 ? 當(dāng)入隊時，計數(shù)變量＋ 1（ c = c+1 ） ? 當(dāng)出隊時，計數(shù)變量－ 1 （ c = c1） ? 當(dāng)計數(shù)變量＝ maxsize時，隊滿 ? 當(dāng)計數(shù)變量＝ 0時，隊空 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 48/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 多棧共享存儲空間 ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的鏈?zhǔn)酱鎯Ψ绞胶晚樞虼鎯Ψ绞郊捌渖系牟僮? ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 49/51 隊列的應(yīng)用 ? 操作系統(tǒng)中的進(jìn)程調(diào)度 ? 樹和二叉樹的層次遍歷 front 0 1 n rear 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 50/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 多棧共享存儲空間 ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的鏈?zhǔn)酱鎯Ψ绞胶晚樞虼鎯Ψ绞郊捌渖系牟僮? ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 51/51
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1