數(shù)據(jù)結(jié)構(gòu)課件(c語言)(4)(已修改)
2024-10-31 19:48 本頁面
【正文】 第 3章 棧和隊(duì)列 1 第 3章 棧和隊(duì)列 棧 隊(duì)列 第 3章 棧和隊(duì)列 2 棧 （ Stack） 是限定只能在 表尾 進(jìn)行插入和刪除操作的 線性表 。其中 ， 允許進(jìn)行插入和刪除操作的一端稱為 棧頂 （ Stack top） ；不允許進(jìn)行插入和刪除操作的一端稱為 棧底 （ Stack bottom） 。 當(dāng)需要插入新的數(shù)據(jù)元素時(shí) ， 應(yīng)把新的數(shù)據(jù)元素放在棧頂元素的上面 ， 這一操作為 入棧 push操作 ；當(dāng)需要從棧中刪除一個(gè)數(shù)據(jù)元素時(shí) ， 只能把棧頂元素刪除 ， 這一操作為 出棧 pop操作 。 因此棧又可稱為 后進(jìn)先出 （ Last In First Out） 型線性表 ，即 LIFO結(jié)構(gòu) 不含元素的棧稱 空棧 棧 棧的定義 第 3章 棧和隊(duì)列 an a1 a2 ……... bottom top ... 出棧 進(jìn)棧 棧 s=(a1,a2,……,an) 棧頂（ top)：允許插入和刪除的一端； 棧底（ bottom):不允許插入和刪除的一端。 第 3章 棧和隊(duì)列 ? 棧的基本操作 ? (1)InitStack(*S):初始化操作，創(chuàng)建一個(gè) 空棧 S返回 。 ? (2) StackEmpty(*S) :判斷棧 S是否為空，若 S為空棧返回為 1，否則返回為 0。 ? (3)Clear Stack(*S): 清空棧 S。 ? (4)LenStack(*S): 求棧 S中數(shù)據(jù)元素的個(gè)數(shù)，即棧 S的長度。 ? (5)Push (*S,item) :在棧 S的頂部插入一個(gè)新元素 item， item成為新的棧頂元素，棧中增加一個(gè)元素。 ? (6)Pop(*S) :棧 S的頂部元素從棧中刪除，棧中減少一個(gè)元素。 ? (7)GetTop(*S) :獲取棧頂元素的值， 且將其作為結(jié)果返回 ，棧不變化。 第 3章 棧和隊(duì)列 5 棧的順序存儲(chǔ) ? 棧是一種特殊的線性表，因此線性表的存儲(chǔ)結(jié)構(gòu)對(duì)棧也是適用的， 棧也有兩種存儲(chǔ)方式 :順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ) ，只是操作與普通線性表不同而已。 ? 棧的順序存儲(chǔ)結(jié)構(gòu)也可稱為 順序棧 ，棧中的數(shù)據(jù)元素用一個(gè)預(yù)設(shè)的足夠長度的一維數(shù)組來實(shí)現(xiàn)： elemtype data[MAXSIZE]，棧底位置可以設(shè)置在數(shù)組的任一位置，為了操作方便， 通常將數(shù)組的第一個(gè)數(shù)據(jù)元素即下標(biāo)為 0的數(shù)據(jù)元素所在的位置設(shè)為棧底 ，而棧頂是隨著插入和刪除而變化的，用整型變量 top記錄棧頂元素在數(shù)組中的下標(biāo)值 ，指明棧頂?shù)奈恢谩? 第 3章 棧和隊(duì)列 6 ? 順序棧的類型描述如下 : ? define MAXSIZE maxlen ? typedef char elemtype。 //字符棧 ? typedef struct ? { ? elemtype data[MAXSIZE]。 /*0為棧底位置 */ ? int top。 /*棧頂元素的下標(biāo) */ ? }SqStack。 ? 空棧 時(shí) top=1 第 3章 棧和隊(duì)列 第 3章 棧和隊(duì)列 8 ? (1)初始化一個(gè)空棧 InitStack(*S): ? 算法說明 : ? 創(chuàng)建一個(gè)空棧，只需將該順序棧的棧頂指針設(shè)為 1即可。 ? 算法實(shí)現(xiàn) : ? SeqStack *InitStack(SeqStack *S) ? { ? S=( SeqStack*)malloc(sizeof(SeqStack))。 ? Stop=1。 ? return(S)。 ? } 第 3章 棧和隊(duì)列 9 (2)入棧 Push (*S,item) : ? Push(SeqStack *S,item) ? { ? if (Stop= = MAXSIZE 1) /*棧滿，入棧操作失敗 */ ? { ? printf(Stack overflow)。 ? return(0)。 ? } ? else ? { ? Sdata[++Stop]=item。 /*棧頂指針增 1后，將 item入棧 */ return(1)。 ? } ? } 第 3章 棧和隊(duì)列 10 ? (3)出棧 Pop(*S) : ? elemtype Pop(SeqStack *S) { ? if(Stop= =1) /*棧空，出棧操作失敗 */ ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1