【正文】 下一頁 第 3單元 線性數(shù)據(jù)結構 （二） 主講：劉志強 西安交通大學 計算機教學實驗中心 計算機軟件基礎 Fundamentals of Computer software 下一頁 上一頁 停止放映 第 2/89 頁 思考問題 日常生活中諸如排隊、只有一個出入口的站臺這類線性表在計算機中如何存放和處理？ 它們的特點與一般線性表有哪些異同？怎樣在算法中體現(xiàn)出處理的差異來。 字符串和數(shù)組也是一種線性表，它們的處理與一般線性表的處理又有哪些異同？ 下一頁 上一頁 停止放映 第 3/89 頁 教學目標 掌握 棧、隊列、數(shù)組、串結構的有關 概念、邏輯結構、物理結構及有關操作。 下一頁 上一頁 停止放映 第 4/89 頁 教學主要內容 ? 棧、隊列、數(shù)組、串的 : – 有關 概念 – 邏輯結構及特點 – 存儲結構 – 有關 操作 下一頁 上一頁 停止放映 第 5/89 頁 本章涉及內容 第 1章的 棧和隊列 (P32~P46) 串和數(shù)組 (P47~P55) 下一頁 上一頁 停止放映 第 6/89 頁 一、棧結構 棧的定義 棧的基本運算 棧的順序存儲結構 多棧共享問題 棧的鏈式存儲結構 棧的應用 下一頁 上一頁 停止放映 第 7/89 頁 棧的定義 堆棧 (Stack) – 棧是允許在同一端進行插入和刪除操作的特殊線性表。 – 允許進行插入和刪除操作的一端稱為 棧頂 (top)，另一端為 棧底(bottom)；棧底固定，而棧頂浮動； – 棧中元素個數(shù)為零時稱為空棧。 – 棧結構也稱為后進先出表（ LIFO）。 下一頁 上一頁 停止放映 第 8/89 頁 棧有關概念 棧上溢 棧空間是有限的，若棧已滿，在進行入棧操作時，就要產生上溢。 棧下溢 若?？?，再要執(zhí)行出棧操作，則會發(fā)生下溢。 棧頂指針 在棧操作過程中，有一個專門的棧指針（習慣上稱它為 TOP），指出棧頂元素所在的位置。 ?？盏臈l件 ： top = 0 棧滿的條件 ： top = MAXSIZE 下一頁 上一頁 停止放映 第 9/89 頁 棧的基本運算 Setnull（ Stack） 置棧為空； Empty（ Stack） 判定棧是否為空； Push（ Stack， x） 進棧操作，在棧頂插入元素； Pop（ Stack） 出棧操作，刪除棧頂元素； Gettop（ Stack） 取棧頂元素 下一頁 上一頁 停止放映 第 10/89 頁 棧的順序存儲結構 棧的順序存儲結構實際上是一維數(shù)組 。 棧的順序存儲結構稱為順序棧 。 棧的操作只能在一端進行；即棧頂位置隨進棧和出棧而變化 。 順序棧的 C語言描述為： define MAXSIZE n int stack[MAXSIZE]。 int top = 1。 下一頁 上一頁 停止放映 第 11/89 頁 棧操作舉例 a1 a2 …… a n 棧底 棧頂 MAXSIZE TOP 1. top=0 A B C 2. (空棧 ) top=3 (A、 B、 C進棧 ） A B 3. top=2 (C出棧） 4. A B C D E F top=MAXSIZE (棧滿） 下一頁 上一頁 停止放映 第 12/89 頁 例 110 有三個元素的進棧序列是 1， 2， 3。寫出可能的出棧序列 。 出棧序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x 下一頁 上一頁 停止放映 第 13/89 頁 算法 18 進棧算法 ? 算法步驟 : – step1 判別棧滿否，若滿，則顯示棧溢出信息，停止執(zhí)行；否則，執(zhí)行 step 2； – Step2 棧頂指針 top上移 (加 1)； – Step3 在 top所指的位置插入元素 x。 下一頁 上一頁 停止放映 第 14/89 頁 算法 18 進棧算法程序 push（ int x） { if（ top = = MAXSIZE 1） { printf（ ? 棧上溢 ！ \n”） 。 exit （ 1） 。 } else { top + +； /* 棧指針加 1 */ stack [ top ] = x ； /* 元素 x進棧 */ } } 示例 下一頁 上一頁 停止放映 第 15/89 頁 算法 19 出棧算法 ? 算法步驟 : – step1 判別棧是否為空；若空，則輸出 棧下溢信息，并停止執(zhí)行；否則， 執(zhí)行 step2； – step2 彈出（刪除）棧頂元素； – step3 棧頂指針 top下移 (減 1)。 下一頁 上一頁 停止放映 第 16/89 頁 算法 19 出棧算法程序 pop（ ） { int x。 if( top = = 1） { printf(“ 棧下溢 \n”)。 exit(1)。 } else { x = stack [ top ]； top ； /* 棧頂指針 減 1*/ } return x ； } 示例 下一頁 上一頁 停止放映 第 17/89 頁 多棧共享問題 ? 多棧共享是充分利用?？臻g的一種策略。具體作法是： – 對兩棧共享情況來說，將兩個棧底分別設在兩端， 兩個棧頂指針 top1和 top2相對中間位置動態(tài)移動，兩個棧之間的分界線是不定的。 top1 =0 top2=MAXSIZE 空棧 top1 top2 棧 棧 2均有若干元素 top1 top2 棧滿的情況 a. b. c. 下一頁 上一頁 停止放映 第 18/89 頁 棧的鏈式存儲結構 由前面介紹的鏈表結構可知，鏈結構操作靈活。對棧結構也是一樣的。 順序棧最多可用于 2個棧的共享，對于更多的棧就難于表達了。 對于最大空間需要量事先不知的情況，就不能使用順序棧了。這時，就需要采用鏈棧。 下一頁 上一頁 停止放映 第 19/89 頁 鏈棧存儲結構 ? 鏈棧存儲結構的 C語言描述： struct snode { int data。 struct snode *link。 }。 typedeef struct snode SNODE 。 ? 鏈棧為空的條件： top = NULL ? 鏈棧為滿的條件 : t = NULL t 為申請的結點 ,為 NULL表示失敗 . 下一頁 上一頁 停止放映 第 20/89 頁 鏈棧示意圖 a1 a2 a3 ^ 棧底 top 棧頂 …... ai 下一頁 上一頁 停止放映 第 21/89 頁 算法 110 進棧操作 算法 110操作步驟 : step1 申請一個鏈棧結點 ,若 t=NULL,則表示鏈滿 。否則 ,執(zhí)行 step2 。 step2 在 top所指結點之前插入新結點 ,并將 top指向新申請的結點 t。 下一頁 上一頁 停止放映 第 22/89 頁 算法 110 進棧操作程序 push(SNODE *top , int x) { SNODE *t。 t=(SNODE * )malloc(sizeof(SNODE))。