《數(shù)據(jù)結(jié)構(gòu)C語言 棧和隊列PPT課件》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言 棧和隊列PPT課件（48頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、GetTop ( S，&e ) 取棧頂Push (&S，x ) 入棧Pop (&S, &e) 出棧棧的概述第4頁/共48頁2. 棧的表示和實現(xiàn) 順序棧 ；鏈式棧 。 1） 順序棧ABCbasetop棧底指針base棧頂指針top棧容量順序棧類型數(shù)據(jù)結(jié)構(gòu)的表示：typedef struct dataType * base； dataType * top ； int stacksize ； SqStack ；棧的概述第5頁/共48頁空棧ABCbasetop棧中有三個元素ABCbasetopDE滿棧top = base第6頁/共48頁 用數(shù)組來描述棧的結(jié)構(gòu) ： 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 判斷棧空top = 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頁棧的概述 當(dāng)需要使用多個棧時，在數(shù)組空間允許的情況下

5、，可以使多個棧共享同一個數(shù)組空間。其結(jié)構(gòu)定義形式如下： typedef datatype int; #define maxsize 64 typedef struct datatype datamaxsize; int top1,top2; dstack;第12頁/共48頁2.棧的表示和實現(xiàn)2）鏈式棧typedef struct node datatype data ；struct node * next ； * Linkstack ； anan- -10a1棧底base棧頂top空棧: top=base=NULL;棧的概述第13頁/共48頁棧的概述 2.棧的表示和實現(xiàn) 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.棧的表示和實現(xiàn) 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.棧的表示和實現(xiàn) 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頁棧的應(yīng)用 常見的棧應(yīng)用問

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

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

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

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

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

13、隊列）鏈隊列鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)鏈隊列的基本運算算法：鏈隊列的基本運算算法：初始化：初始化：p62p62銷毀隊列：銷毀隊列：p62p62入隊：入隊：p62p62出隊：出隊：p62p62隊 列第28頁/共48頁p = (QNode* ) malloc ( sizeof(QNode) ) ；if ( ! p ) exit (OVERFLOW) ；p- -data = e ；p- -next = NULL ； /申請新結(jié)點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 ；/取第一個結(jié)點free ( p ) ；return OK ；Status DeQueue ( LinkQueue *Q, dataType &e) Q.front- -next = p- -next ； /刪除第一個結(jié)點if ( Q.rear = p ) Q.rear = Q.front ；/若需要刪除的隊頭結(jié)點就

15、是尾結(jié)點第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） 順序隊列順序存儲結(jié)構(gòu)Q.rearQ.front543210隊尾隊頭A

16、BCD第33頁/共48頁2） 順序隊列順序存儲結(jié)構(gòu) 順序隊列的類型描述： #define maxsize 66 Typedef struct datatype datamaxsize; int front,rear; sequeue; Sequeue *q;第34頁/共48頁2） 順序隊列順序存儲結(jié)構(gòu) 順序隊列的基本操作： 初始化 刪除 插入第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)隊列順序存儲結(jié)構(gòu)將順序隊列改造為一個環(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)隊列順序結(jié)構(gòu)基本操作算法： 初始化（置空隊）：p64 求隊列長度：p64 入隊：p65 出隊：p65第42頁/共48頁 4）循環(huán)隊列鏈式存儲結(jié)構(gòu) 空隊列： 基本操作：插入 刪除隊首結(jié)點隊尾結(jié)點第43頁/共48頁 5）優(yōu)先隊列 1.也是一種隊列 2.特征：插入元素的順序是以優(yōu)先級為依據(jù)的。 3.主要應(yīng)用：堆排序返回第44頁/共48頁隊列的應(yīng)用 1.解決設(shè)備速度不匹配問題：利用隊列先進先出的特性，設(shè)置緩沖隊列； 2.舞伴問題：先入隊的男士和女士先配成

21、舞伴； 3.離散事件模擬：p6569返回第45頁/共48頁作 業(yè) 若依次輸入數(shù)據(jù)元素序列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頁 上機實驗：鏈棧的建立及出棧 內(nèi)容與要求： 建立鏈棧并進行元素的出棧，實現(xiàn)鏈棧的建立及出棧的基本操作； 使用函數(shù)initiate()實現(xiàn)鏈棧的初始化； 使用函數(shù)pushls()實現(xiàn)鏈棧的入棧； 使用函數(shù)popls()實現(xiàn)鏈棧的出棧。第47頁/共48頁感謝您的觀看！第48頁/共48頁