chapter3：棧、隊列(已修改)
2024-10-15 21:59 本頁面
【正文】 Chapter 3:棧、隊列 第三章 棧和隊列 棧 抽象數(shù)據(jù)類型棧的定義 棧的表示和實現(xiàn) 棧的應(yīng)用舉例 數(shù)制轉(zhuǎn)換 括號匹配的檢驗 行編輯程序 迷宮求解 表達式求值 167。 棧 167。 棧的邏輯結(jié)構(gòu) 限定僅在表的一端進行插入與刪除的線性表。也稱作FILO先進后出 （ First In Last Out） 的線性表 。 ? ADT Stack{ ? 數(shù)據(jù)對象 :D={ai|ai( ElemSet,i=1,2,...,n,n=0} ? 數(shù)據(jù)關(guān)系 :R1={ai1,ai|ai1,ai( D,i=2,...,n} ? 基本操作 : ? InitStack(amp。S) 構(gòu)造一個空棧 S ? DestroyStack(amp。S) 棧 S存在則棧 S被銷毀 ? ClearStack(amp。S) 棧 S存在則清為空棧 棧的抽象數(shù)據(jù)類型定義： ? StackEmpty(S) 棧 S存在則返回 TRUE,否則 FALSE ? StackLength(S) 棧 S存在則返回 S的元素個數(shù) ,即棧的長度 ? GetTop(S,amp。e) 棧 S存在且非空則返回 S的棧頂元素 ? Push(amp。S,e) 棧 S存在則插入元素 e為新的棧頂元素 ? Pop(amp。S,amp。e) 棧 S存在且非空則刪除 S的棧頂元素并用 e返回其值 ? StackTraverse(S,visit())棧 S存在且非空則從棧底到棧頂依次對 S的每個數(shù)據(jù)元素調(diào)用函數(shù) visit()一旦visit()失敗 ,則操作失敗 ? }ADT Stack 棧的實例 1火車扳道站 棧事例 2中斷處理 中斷 1打斷過程 0，中斷 2打斷中斷 1，中斷 3打斷中斷 2 0 過程 0開始 中斷處理 過程 1 中斷處理 過程 2 中斷處理 過程 3 斷點 1 斷點 2 斷點 3 167。 棧的順序?qū)崿F(xiàn) 用一組連續(xù)的存貯空間存放棧元素 top base 順序棧的類 C語言定義 ? typedef struct{ ? SElemType *base。 ? SElemType *top。 //設(shè)棧頂棧底兩指針的目的是便于判斷棧是否為空 ? int StackSize。 //棧的當(dāng)前可使用的最大容量 . ? }SqStack。 二、基本操作實現(xiàn) ? Status InitStack(SqStack amp。S) { ? =(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType))。 ? if(!)exit(OVERFLOW)。 ? =。 ? =STACK_INI_SIZE。 ? return OK。 ? }//IniStack ? Status ClearStack(SqStack amp。S)。 { ? =。 ? } //ClearStack ? Status StackEmpty(SqStack S)。 { ? if(==) return TRUE。 ? else return FALSE。 ? } //StackEmpty ? Status GetTop(SqStack S,SElemType amp。e)。 { ? if(==) return ERROR。 ? e=*()。 ? return OK。 ? } //GetTop ? Status Push(SqStack amp。S,SElemType e)。 { ? if( =) { ? =(ElemType *) realloc(, ? ( + STACKINCREMENT) * sizeof(ElemType))。 ? if(!)exit(OVERFLOW)。 ? =+。 ? +=STACKINCREMENT。 ? } ? *++=e。 ? return OK。 ? } //Push ? Status Pop(SqStack amp。S,SElemType amp。e)。 { ? if(==) ? return ERROR。 ? e=*。 ? return OK。 ? }//Pop ? 我們要了解的是，在順序棧中有“上溢”和“下溢”的概念。順序棧好比一個盒子，我們在里頭放了一疊書，當(dāng)我們要用書的話只能從第一本開始拿 ,那么當(dāng)我們把書本放到這個棧中超過盒子的頂部時就放不下了，這時就是 上溢 ,上溢 也就是棧
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1