數(shù)據(jù)結(jié)構(gòu)講義(已修改)
2024-10-12 18:11 本頁面
【正文】 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 1/51 數(shù)據(jù)結(jié)構(gòu) （ C語言版） －嚴(yán)蔚敏 吳偉民－ －清華大學(xué)出版社－ 授課老師： 李 綱 電子郵箱： 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 2/51 第三章 棧和隊(duì)列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 棧的應(yīng)用 ? 隊(duì)列的基本概念和特性 ? 隊(duì)列的基本操作 ? 隊(duì)列的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 隊(duì)列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 3/51 棧的基本概念 ? 棧（ stack） 插入 和 刪除 操作限定在 表尾 進(jìn)行的線性表 ? 棧頂 (top) 表中進(jìn)行插入和刪除操作的一端 ? 棧底 (bottom) 表中的另一端 ? 空棧 不含任何數(shù)據(jù)元素的棧 (stack) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 4/51 棧的操作特點(diǎn) ? 后進(jìn)先出 (Last In First OutLIFO) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 5/51 第三章 棧和隊(duì)列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 棧的應(yīng)用 ? 隊(duì)列的基本概念和特性 ? 隊(duì)列的基本操作 ? 隊(duì)列的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 隊(duì)列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 6/51 棧的基本運(yùn)算 ? InitStack(amp。S) 初始化操作，設(shè)定一個(gè)空棧 S ? DestroyStack( amp。S ) 銷毀棧 S ? ClearStack(amp。S) 置?？詹僮? ? StackEmpty(S) 判棧 S是否為 空 （ TRUE/FALSE） ? Push(amp。S, e) 入棧操作 ， 在棧 S頂部插入元素 e， 相當(dāng)于線性表的 INSERT(L, n+1, x) ? Pop(amp。S,amp。e) 出棧函數(shù) ， 若 S不空 ， 則返回棧頂元素 ， 并刪除棧頂元素；否則返回 空元素 NULL。 相當(dāng)于線性表的 DELET(L, n) ? GetTop(S,amp。e) 取棧頂元素函數(shù) ， 與 POP(S)的差別在不刪除棧頂元素 ， 相當(dāng)于線性表的 GET(L, n) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 7/51 第三章 棧和隊(duì)列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 棧的應(yīng)用 ? 隊(duì)列的基本概念和特性 ? 隊(duì)列的基本操作 ? 隊(duì)列的順序存儲方式和鏈?zhǔn)酱鎯Ψ绞郊捌渖系牟僮? ? 隊(duì)列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 8/51 順序存儲方式實(shí)現(xiàn)－使用數(shù)組 define ARRMAX = N。 //N為一自定義的常數(shù)，表示棧的大小 typedef struct { SElemType elem[ARRMAX ]。//存儲數(shù)據(jù)元素的數(shù)組 int top。 //棧頂指針， elem[0]為棧底 }SeqStack,*PSeqStack。 ? ?？諘r(shí) = = 0 ? 棧滿時(shí) = = ARRMAX 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 9/51 順序存儲結(jié)構(gòu)上棧操作的實(shí)現(xiàn) ? 創(chuàng)建空棧 InitStack(amp。S) ? 方式一：聲明 SeqStack的變量 S，由系統(tǒng)自動(dòng)分析內(nèi)存空間，所建?？臻g在程序的堆棧區(qū)上 Status InitStack( PSeqStack pS ) { pStop = 0。 return OK。 } void main() { SeqStack S。 InitStack( amp。S )。 } ARRMAX 棧底 棧頂 X 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 10/51 順序存儲結(jié)構(gòu)上棧操作的實(shí)現(xiàn) ? 創(chuàng)建空棧 InitStack(amp。S) ? 方式二：聲明一個(gè)指向要?jiǎng)?chuàng)建的棧的指針 pS，采用動(dòng)態(tài)分配內(nèi)存的方式創(chuàng)建棧 ,所建?？臻g在程序的堆區(qū)上 Status InitStack( PSeqStack *pPS ) { *pPS = (pSeqStack)malloc( sizeof( SeqStack ) )。 if( (*pPS) = = NULL ) return OVERFLOW。 (*pPS)top = 0。 return OK。 } void main() { PSeqStack *pS pS = NULL。 InitStack( amp。pS )。 } pPS pS Elem[ARRMAX] top NULL 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 11/51 順序存儲結(jié)構(gòu)上棧操作的實(shí)現(xiàn) ? 銷毀棧 DestroyStack( amp。S ) ? 由方式一創(chuàng)建的棧，由于是通過系統(tǒng)自動(dòng)分配的空間，因此銷毀也是由系統(tǒng)自動(dòng)完成，可不用實(shí)現(xiàn)此函數(shù) ? 由方式二創(chuàng)建的棧，是在堆上進(jìn)行分配的，要自己銷毀棧，而棧的銷毀方式與具體應(yīng)用要求有關(guān)。這里舉的只是一個(gè)例子，便于大家理解 Status DestroyStack( PSeqStack *pPS ) { if( !pPS || !(*pPS) ) return ERROR。 if( (*pPS)top != 0 )//棧不為空，這里定義為不能銷毀棧 return ERROR。 free( *pPS )。 *pPS = NULL。 return OK。 } 電子科大科 園 培訓(xùn)中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 12/51 順序存儲結(jié)構(gòu)上棧操作的實(shí)現(xiàn) ? 判斷棧 S是否為 空 StackEmpty(S)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1