《數據結構C語言 棧和隊列PPT課件》由會員分享，可在線閱讀，更多相關《數據結構C語言 棧和隊列PPT課件（48頁珍藏版）》請在裝配圖網上搜索。

1、第三章 棧和隊列棧和隊列是兩種重要的線性結構棧和隊列是操作受限的線性表出進排隊買票漢諾塔進出第1頁/共48頁第三章 棧和隊列 1.棧的概述 2.棧的應用 3.棧和遞歸的實現 4.隊列 5.隊列的應用第2頁/共48頁棧的概述1.棧的定義棧是限定僅在表尾進行插入或刪除操作的線性表。通常，表頭端稱為棧底，表尾端稱為棧頂。出棧進棧a1為棧底元素an為棧頂元素按a1、a2、an順序進棧按an、 a2、a1順序出棧棧稱為后進先出線性表(LIFO)a1a2an. . .表頭表尾棧底棧頂第3頁/共48頁1.棧的定義主要基本操作包括:InitStack ( &S ) 初始化StackEmpty ( S ) 判空

2、GetTop ( S，&e ) 取棧頂Push (&S，x ) 入棧Pop (&S, &e) 出棧棧的概述第4頁/共48頁2. 棧的表示和實現 順序棧 ；鏈式棧 。 1） 順序棧ABCbasetop棧底指針base棧頂指針top棧容量順序棧類型數據結構的表示：typedef struct dataType * base； dataType * top ； int stacksize ； SqStack ；棧的概述第5頁/共48頁空棧ABCbasetop棧中有三個元素ABCbasetopDE滿棧top = base第6頁/共48頁 用數組來描述棧的結構 ： typedef struct data

3、type datamaxsize; int top; int base; seqstack; seqstack *s;第7頁/共48頁例1 棧的初始化top = baseInitStack（seqstack &s） stop0; sbase0;第8頁/共48頁例2 判斷?？誸op = baseInt StackEmpty（seqstack s） if（stopsbase） return true； else return false；第9頁/共48頁例3 在棧中插入元素 Atop = baseAbasetop = top + 1datatype Push(seqstack *s, dataty

4、pe x) if (s-top=maxsize) printf(“overflow”); return NULL; else s-datas-top=x; s-top+; return true; 第10頁/共48頁例4 刪除棧頂元素 AbaseAtoptop=top-1 datatype Pop(seqstack &s,datatype x) if (StackEmpty(s) printf(“underflow”); return NULL; else s-top-; x=s-datas-top; return(x); 第11頁/共48頁棧的概述 當需要使用多個棧時，在數組空間允許的情況下

5、，可以使多個棧共享同一個數組空間。其結構定義形式如下： typedef datatype int; #define maxsize 64 typedef struct datatype datamaxsize; int top1,top2; dstack;第12頁/共48頁2.棧的表示和實現2）鏈式棧typedef struct node datatype data ；struct node * next ； * Linkstack ； anan- -10a1棧底base棧頂top空棧: top=base=NULL;棧的概述第13頁/共48頁棧的概述 2.棧的表示和實現 2）鏈式棧 進棧： l

6、inkstack *PushLinkStack(linkstack *top,datatype w) linkstack *p; p=(linkstack*)malloc(sizeof(linkstack); p-data=w; p-next=top; top=p; return p; 第14頁/共48頁棧的概述 2.棧的表示和實現 2）鏈式棧 出棧： dataType PopLinkStack(linkstack *top,datatype x) linkstack *p; if (top=NULL) printf(“空棧！”);return NULL; else x=top-data; p

7、=top; top=top-next; free(p); return x; 第15頁/共48頁棧的概述 2.棧的表示和實現 2）鏈式棧 置空棧： void InitStack(linkstack *S) S=NULL; 判空棧： Int StackEmpty(linkstack *S) if(S=NULL) return 1; else return 0; 取棧頂元素： datatype StackTop(linkstack *S) if(StackEmpty(S) Error(“空棧！”);retrun NULL; return S-data;返回第16頁/共48頁棧的應用 常見的棧應用問

8、題： 數制轉換 括號匹配的檢驗 行編輯 迷宮問題 算術表達式求值返回第17頁/共48頁棧和遞歸的實現 一、遞歸的定義 遞歸：一個事件或對象的部分由自己組成，或者按它自己來定義。 遞歸算法的組成： 遞推：將問題推到比原來問題簡單的問題上求解； 回歸：當簡單問題得解后再回歸到原來的問題上。 常見遞歸算法： 直接遞歸：函數直接調用本身。 間接遞歸：函數在調用其它函數的過程中又調用其本身。第18頁/共48頁棧和遞歸的實現 二、常見的遞歸問題 1.漢諾塔問題 要求：將大小不同的n個盤子移動到另外一根軸上，移動過程中必須保證小的盤子在大的盤子的上方。 算法思想： 將放在下面的n-1個盤子從當前軸移動到目的

9、軸上；（即遞歸過程） 將最小的1個盤子移動到目的軸上。 p 5558第19頁/共48頁棧和遞歸的實現 二、常見的遞歸問題 2.八皇后問題 要求：在88的棋盤上放置八顆棋子，任意兩顆不能在同一行或同一列或同一對角線上。 算法思想： 先在棋盤中確定一個棋子的位置； 在剩下可以下子的位置里面再確定一個棋子的位置，要求位置滿足上述規(guī)則； 如果此時棋子還沒有放完，則繼續(xù)上述第二步直到所有棋子放完位置； 如果棋子順利放完，則該算法成功；反之， 則要回溯，改變上一顆棋子的位置，直到所有 棋子均成功放置為止。第20頁/共48頁棧和遞歸的實現 二、遞歸的實現 1.遞歸的基本條件： 待解決的問題可以轉化為與原始問

10、題解決方法相同的另一個問題來處理； 具有終止遞歸的條件。 2.遞歸的調用機制： 遞歸調用之前，將算法所有參數、局部變量的當前值和調用后的返回地址等壓入遞歸工作棧； 執(zhí)行遞歸調用； 每次遞歸結束后，將棧定元素彈出，分別賦給相應的參數和變量。第21頁/共48頁棧和遞歸的實現 說明： 遞歸函數比非遞歸函數更容易理解； 但遞歸函數的時間復雜度和空間復雜度都高于相應的非遞歸函數； 遞歸的層次不能太深，否則會影響機器運行的速度。返回第22頁/共48頁隊 列隊列是一種先進先出(FIFO)的線性表。隊列只允許在一端進行插入，而在另一端進行刪除。出隊列入隊列a1 a2 a3 an 隊頭隊尾1. 隊列的定義第23

11、頁/共48頁1.隊列的定義 主要基本操作包括:InitQueue（&Q） 構造空隊列DestroyQueue（&Q） 隊列銷毀QueueEmpty(linkqueue *q) 判隊空ClearQueue（&Q） 隊列清空GetHead ( Q，&e ) 取頭元素EnQueue (&Q，e ) 隊列插入DeQueue (&Q，&e ) 隊頭刪除 隊 列第24頁/共48頁1.隊列的定義 特殊的隊列：雙端隊列 可以在隊列兩邊同時進行插入和刪除操作輸出受限的雙端隊列 有一個端點只允許插入輸入受限的雙端隊列 有一個端點只允許輸出隊 列第25頁/共48頁2 隊列的表示和實現 鏈隊列；順序隊列；循環(huán)隊列1）

12、鏈隊列鏈式存儲結構 必須具備指示隊頭和隊尾的指針(頭指針、尾指針)。a1a20anfrontrearQ.frontQ.rear0空隊列隊 列第26頁/共48頁2 隊列的表示和實現隊列的表示和實現1）鏈隊列）鏈隊列鏈式存儲結構鏈式存儲結構 鏈隊列的結構類型定義：鏈隊列的結構類型定義： typedef struct QNode datatype data; struct QNode *next; QNode, *QueuePtr; typedef struct QNode *front, *rear; linkqueue; 隊 列第27頁/共48頁2 2 隊列的表示和實現隊列的表示和實現1 1）鏈

13、隊列）鏈隊列鏈式存儲結構鏈式存儲結構鏈隊列的基本運算算法：鏈隊列的基本運算算法：初始化：初始化：p62p62銷毀隊列：銷毀隊列：p62p62入隊：入隊：p62p62出隊：出隊：p62p62隊 列第28頁/共48頁p = (QNode* ) malloc ( sizeof(QNode) ) ；if ( ! p ) exit (OVERFLOW) ；p- -data = e ；p- -next = NULL ； /申請新結點Q.rear- -next = p ；Q.rear = p ； /插入在隊尾return OK ；InQueue ( LinkQueue *Q ，datatype e ) 第2

14、9頁/共48頁sunpzhoujin0 xin Q.front Q.rear0Q.rear例題1：入隊操作：第30頁/共48頁例題：出隊操作if ( Q.front = Q.rear ) return ERROR ；p = Q.front- -next ；e = p- -data ；/取第一個結點free ( p ) ；return OK ；Status DeQueue ( LinkQueue *Q, dataType &e) Q.front- -next = p- -next ； /刪除第一個結點if ( Q.rear = p ) Q.rear = Q.front ；/若需要刪除的隊頭結點就

15、是尾結點第31頁/共48頁zhoujin0 xin SQ.frontQ.rear pe = p - - data = zhou pe = p - - data = jin pe = p - - data = xinQ.rear0例題2：出隊操作第32頁/共48頁用一組地址連續(xù)的存儲單元依次存放隊頭到隊尾的元素。指針 front 、rear 分別指示隊頭和隊尾下一個元素。令 front = rear = 0 表示空隊列，rear=MAXSIZE 表示隊滿。每插入一新元素，rear 增 1，每刪除一元素，front 增 1。2） 順序隊列順序存儲結構Q.rearQ.front543210隊尾隊頭A

16、BCD第33頁/共48頁2） 順序隊列順序存儲結構 順序隊列的類型描述： #define maxsize 66 Typedef struct datatype datamaxsize; int front,rear; sequeue; Sequeue *q;第34頁/共48頁2） 順序隊列順序存儲結構 順序隊列的基本操作： 初始化 刪除 插入第35頁/共48頁插入、刪除操作過程：543210Q.rearQ.front隊尾隊頭插入元素 J1；J1Q.rear插入元素 J2 、J3 ；J2J3Q.rear刪除元素 J1 、J2 ；Q.front插入元素 J4 、J5 、J6 ；J4J5J6Q.re

17、ar此時，隊滿，無法再插入新的元素，但實際隊列中的可用空間并未真的被占滿。第36頁/共48頁3）循環(huán)隊列順序存儲結構將順序隊列改造為一個環(huán)狀的空間。01maxsize - - 1Q.frontQ.rear指針 front 、rear 分別指示隊頭和隊尾下一個元素。令 front = rear = 0 表示空隊列。每插入一新元素，rear = (rear + 1) % maxsize， 每刪除一元素，front = (front + 1) % maxsize 。/ % : 求余第37頁/共48頁插入、刪除操作01Q.frontQ.rear2345初始，Q.front = Q.rear = 0，空

18、隊列。插入元素 J0 、J1 、J2 、J3 、J4 ； 刪除元素 J0 、J1 ； 插入元素 J5 、J6 ； maxsize = 6J0J1J2J3J4Q.rearQ.frontJ5J6Q.rear第38頁/共48頁01Q.frontQ.rear2345初始，Q.front = Q.rear = 0 ，空隊列。插入元素 J0 、J1 、J2 、J3 、J4 、J5 ； J0J1J2J3J4J5Q.rearQ.rearQ.rearQ.rearQ.rearQ.rearQ.front = Q.rear = 0 ，滿隊列。maxsize = 6問題:第39頁/共48頁故無法通過 front = r

19、ear = 0 來分辨隊空或隊滿。解決方案:特殊空間，規(guī)定 front 與rear 之間總空出一個空間。隊空: Q.front = Q.rear隊滿: Q.front = (Q.rear + 1) % maxsize 01Q.front2345J0J1J2J3J4Q.rear第40頁/共48頁01Q.frontQ.rear2345初始，Q.front = Q.rear = 0，空隊列。插入元素 J0 、J1 、J2 、J3 、J4 ；Q.front = (Q.rear + 1) % maxsize 隊滿刪除元素 J0 、J1 ； 插入元素 J5 、J6 ；Q.front = (Q.rear +

20、 1) % maxsize 隊滿maxsize = 6J0J1J2J3J4Q.rearQ.frontJ5J6Q.rear第41頁/共48頁3 3）循環(huán)隊列順序結構基本操作算法： 初始化（置空隊）：p64 求隊列長度：p64 入隊：p65 出隊：p65第42頁/共48頁 4）循環(huán)隊列鏈式存儲結構 空隊列： 基本操作：插入 刪除隊首結點隊尾結點第43頁/共48頁 5）優(yōu)先隊列 1.也是一種隊列 2.特征：插入元素的順序是以優(yōu)先級為依據的。 3.主要應用：堆排序返回第44頁/共48頁隊列的應用 1.解決設備速度不匹配問題：利用隊列先進先出的特性，設置緩沖隊列； 2.舞伴問題：先入隊的男士和女士先配成

21、舞伴； 3.離散事件模擬：p6569返回第45頁/共48頁作 業(yè) 若依次輸入數據元素序列a,b,c,d,e,f,g進棧，出棧操作可以和入棧操作間隔進行。則下列哪些元素序列可以由出棧序列得到： A）d,e,c,f,b,g,a B）f,e,g,d,a,c,b C）e,f,d,g,b,c,a D）c,d,b,e,f,a,g第46頁/共48頁 上機實驗：鏈棧的建立及出棧 內容與要求： 建立鏈棧并進行元素的出棧，實現鏈棧的建立及出棧的基本操作； 使用函數initiate()實現鏈棧的初始化； 使用函數pushls()實現鏈棧的入棧； 使用函數popls()實現鏈棧的出棧。第47頁/共48頁感謝您的觀看！第48頁/共48頁