數(shù)據(jù)結構之棧對列串課件(已修改)
2025-09-11 09:01 本頁面
【正文】 數(shù)據(jù)結構 第 三 章 棧 對列 串 ?要 求 熟練掌握以下內容： 堆棧的特征 、 基本運算并能設計簡單算法 隊列 、 循環(huán)隊列的特征 、 基本運算并能設計簡單算法 串的定義和應用 了解以下內容： 線性表運算時間復雜性分析 堆棧 、 隊列實際應用 堆棧 (Stack) ?堆棧也簡稱為棧，是限定在表的一端進行插入或刪除操作的線性表。 ?進行插入或刪除操作的一段稱為棧頂（ top），另一端稱為棧底（ bottom）。 ?插入元素又稱為入棧（ push），刪除元素操作稱為出棧（ pop）。 ?不含元素的棧稱為空棧。 ?堆棧元素的插入和刪除只在棧頂進行，總是后進去的元素先出來，所以堆棧又稱為后進先出線性表或 LIFO（ LastInFirstOut）表。 堆棧的表示 ?堆棧的最簡單的表示方法是采用一維數(shù)組，為形象起見，一般在圖中將堆棧畫成豎直的 。 ?設數(shù)組名為 STACK，其下標的下界為 1，上界為 n。 ?一般需用一個變量 top記錄當前棧頂?shù)南聵酥?，top也叫做棧指針。 ?本例中 top=4 top A D C B 4 7 5 3 2 1 6 STACK 棧的基本運算 ?進棧 push(s,x) ?出棧 pop(s) ?取棧頂元素 gettop(s) ?判斷棧空 emptystack(s) ?置空棧 setstacknull ?求棧的長度 stacklen(s) ?棧的遍歷 stacktraverse(s) 1. 入棧（ push） ?入棧的主要操作是先將棧頂指針加 1； ?然后將入棧元素放到棧頂指針所指示下標值的位置上。 ?設用下標從 1到 n的數(shù)組 ST表示堆棧，入棧的元素值為 G，則可得到入棧函數(shù)如下： 棧的順序存儲結構 ?用一個一維數(shù)組作棧，加一個指針。 其定義如下： define maxsize 允許的最大元素個數(shù) Typedef struct { elementtype elenents[maxsize]。 Int top。 } stacktype。 入棧函數(shù) int push (stacktype s, elementtype x) { if (==maxsize1) { printf(“棧溢出 !\n”)。 /*棧滿 */ return(1) } s. top++。 []=x。 return(0)。 } 2. 出棧（ Pop） ?出棧運算時，先將棧頂?shù)脑刂蒂x給某個變量，以備后面的運算應用； ?然后棧頂指針減 1，將棧頂位置下移。 ?假設已指定的變量為 *p，則出棧的函數(shù)如下： 出棧 函數(shù) Int pop (stacktype s, elementtype *p) { if (== 1) printf(“空棧 !\n”)。 /*棧為空 */ p=[]。 。 return(0)。 } 例 ?一個雙向棧是將兩個棧用一個數(shù)組構成，它們的棧底分別設在數(shù)組的兩端。寫出以數(shù)組高端為底的棧的入棧和出棧的算法。 ………… A B C D b a S c 1 2 3 4 5 6 n 2 n 1 n t op1 t op2 ………… 例 ?這個棧的棧頂指針 top2是按相反的方向移動的 ， 因此 ,在操作時要判斷： 入棧時： top21=top1 ？ 出棧時： top2=n+1 ? 入棧算法 void push (S, int n, top1, top2, G) { if (top21==top1) printf(“溢出 !\n”)。 else { top2=top21。 S[top2]=G。 /*插入新元素 */ } } 出棧算法 void pop (S, int n, top1, top2, x) { if (top2==n+1) printf(“下溢出 !\n”)。 else { x=S[top2]。 top2=top2+1。 } } 棧的鏈式存儲結構 ?用一頭結點單鏈表的第一個元素，頭結點的指針表示棧頂，若一進棧序列 a,b,c, 其鏈式結構如下： head c b a ^ ?其結構定義如下： typedef struct node { elementtype data。 Struct node *next。 }stacklnode。 進棧 ? Int push(stacklnode *head,elementtype x) {stacklnode *p。 If ((p==malloc(sizeof(struct node)))==null Printf(“沒有空間” ) ； Pdata=x。 Pnext=headnext。 Headnext=p。 Return(0)。 } 出棧 Int pop(stacklnode *head,elementtype *x) {stacklnode *p。 p=headnext。 if (p==null) printf (“棧已空 ” )。 headnext=pnext。 /*刪除 P*/ *x=pdata。 free(p) Return(0)。 } 堆棧的應用 ? 1. 堆棧在函數(shù)調用中的應用 : 設有三個函數(shù) A1，A2， A3，這三個函數(shù)有如下的調用關系：函數(shù) A1在其函數(shù)體的某處 r調用函數(shù) A2，函數(shù) A2又在其函數(shù)體某處 t調用函數(shù) A3，函數(shù) A3不調用其他函數(shù)。 r t A1 A2 A3 ?函數(shù)嵌套調用A1調用 A2， A2調用 A3時的返回地址在堆棧中的情況如右圖所示。 top r
醫(yī)療健康相關推薦
鄂ICP備17016276號-1