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