[理學(xué)]數(shù)據(jù)結(jié)構(gòu)3第三章：棧和隊(duì)列(已修改)
2024-10-28 21:14 本頁(yè)面
【正文】 棧和隊(duì)列 主講教師：李長(zhǎng)云 班 級(jí)：信息系 教 室： 多媒體 數(shù)據(jù)結(jié)構(gòu) 棧的定義 ? 棧（ Stack）： – 是一種操作受限的線性表。它是線性表的一個(gè)重要特例。棧中元素的進(jìn)、出是按照后進(jìn)先出的原則進(jìn)行的，這是棧結(jié)構(gòu)的重要特征。因此，棧又稱后進(jìn)先出（ LIFO——Last In First Out） 的線性表，簡(jiǎn)稱為 LIFO表 ? 有關(guān)術(shù)語(yǔ) – 棧頂、棧底、進(jìn)棧、出棧、空棧 ? 棧是限制僅在表的一端進(jìn)行插入和刪除運(yùn)算的線性表。允許插入和刪除的一端稱為棧頂（ Top） ，即表尾。另一端稱為棧底 （ Bottom） ，即表頭。向棧里放入一個(gè)元素，稱為 ? 進(jìn)棧 ? 。從棧中取出一個(gè)元素，稱為 ? 出棧 ? 。當(dāng)棧中沒(méi)有元素時(shí)，稱為 ? 空棧 ? 。 棧的運(yùn)算 – 棧的基本運(yùn)算： （ 1）置空棧 SETNULL(S) （ 2）判?？?EMPTY（ S） （ 3）進(jìn)棧 PUSH（ S， x） （ 4）退棧 POS（ S） （ 5）取棧頂 TOP（ s） （ 6） 重置空棧 CLEAR（ S） – 棧有順序存儲(chǔ)和鏈接存儲(chǔ)兩種方式。 棧的示意圖 棧的順序存儲(chǔ)結(jié)構(gòu) ? 順序棧即棧的順序存儲(chǔ)結(jié)構(gòu)，是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素 ? 附設(shè)指針 top指示棧頂元素在順序棧中的位置。 top=0時(shí)，表示?？?。 ? 每當(dāng)插入一個(gè)新的棧頂元素， top增 1；每當(dāng)刪除棧頂元素時(shí)， top減 1。 圖例 順序棧的定義 // 棧的順序存儲(chǔ)表示 define STACK_INIT_SIZE 10 // 存儲(chǔ)空間初始分配量 define STACKINCREMENT 2 // 存儲(chǔ)空間分配增量 struct SqStack { SElemType *base。 // 在棧構(gòu)造之前和銷毀之后 ， base的值為 NULL SElemType *top。 // 棧頂指針 int stacksize。 // 當(dāng)前已分配的存儲(chǔ)空間 ， 以元素為單位 }。 // 順序棧 順序棧存儲(chǔ)結(jié)構(gòu) 順序棧的基本操作 Status InitStack(SqStack amp。S) { // 構(gòu)造一個(gè)空棧 S if(!(=(SElemType )malloc(STACK_INIT_SIZE*sizeof(SElemType)))) exit(OVERFLOW)。 // 存儲(chǔ)分配失敗 =。 =STACK_INIT_SIZE。 return OK。 } 構(gòu)造空棧圖例 順序棧的基本操作 Status DestroyStack(SqStack amp。S) { // 銷毀棧 S， S不再存在 free()。 =NULL。 =NULL。 =0。 return OK。 } 銷毀順序棧圖例 順序棧的基本操作 Status ClearStack(SqStack amp。S) { // 把 S置為空棧 =。 return OK。 } Status StackEmpty(SqStack S) { // 若棧 S為空棧 ， 則返回 TRUE， 否則返 FALSE if(==) return TRUE。 else return FALSE。 } 順序棧的基本操作 int StackLength(SqStack S) { // 返回 S的元素個(gè)數(shù) ， 即棧的長(zhǎng)度 return 。 } Status GetTop(SqStack S,SElemType amp。e) { // 若棧不空 ， 則用 e返回 S的棧頂元素 ， 并返回 OK；否則返回 ERROR if() { e=*()。 return OK。 } else return ERROR。 } 順序棧的基本操作 Status Push(SqStack amp。S,SElemType e) { // 插入元素 e為新的棧頂元素 if(=)// 棧滿 ， 追加存儲(chǔ)空間 {=(SElemType *)realloc(, (+STACKINCREMENT)*sizeo
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1