數(shù)據(jù)結(jié)構(gòu)C語言 棧和隊(duì)列PPT課件

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

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

5、，可以使多個(gè)棧共享同一個(gè)數(shù)組空間。其結(jié)構(gòu)定義形式如下： typedef datatype int; #define maxsize 64 typedef struct datatype datamaxsize; int top1,top2; dstack;第12頁/共48頁2.棧的表示和實(shí)現(xiàn)2）鏈?zhǔn)綏ypedef struct node datatype data ；struct node * next ； * Linkstack ； anan- -10a1棧底base棧頂top空棧: top=base=NULL;棧的概述第13頁/共48頁棧的概述 2.棧的表示和實(shí)現(xiàn) 2）鏈?zhǔn)綏?進(jìn)棧： 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.棧的表示和實(shí)現(xiàn) 2）鏈?zhǔn)綏?出棧： 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.棧的表示和實(shí)現(xiàn) 2）鏈?zhǔn)綏?置空棧： 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)換 括號(hào)匹配的檢驗(yàn) 行編輯 迷宮問題 算術(shù)表達(dá)式求值返回第17頁/共48頁棧和遞歸的實(shí)現(xiàn) 一、遞歸的定義 遞歸：一個(gè)事件或?qū)ο蟮牟糠钟勺约航M成，或者按它自己來定義。 遞歸算法的組成： 遞推：將問題推到比原來問題簡單的問題上求解； 回歸：當(dāng)簡單問題得解后再回歸到原來的問題上。 常見遞歸算法： 直接遞歸：函數(shù)直接調(diào)用本身。 間接遞歸：函數(shù)在調(diào)用其它函數(shù)的過程中又調(diào)用其本身。第18頁/共48頁棧和遞歸的實(shí)現(xiàn) 二、常見的遞歸問題 1.漢諾塔問題 要求：將大小不同的n個(gè)盤子移動(dòng)到另外一根軸上，移動(dòng)過程中必須保證小的盤子在大的盤子的上方。 算法思想： 將放在下面的n-1個(gè)盤子從當(dāng)前軸移動(dòng)到目的

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

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

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

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

13、隊(duì)列）鏈隊(duì)列鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈隊(duì)列的基本運(yùn)算算法：鏈隊(duì)列的基本運(yùn)算算法：初始化：初始化：p62p62銷毀隊(duì)列：銷毀隊(duì)列：p62p62入隊(duì)：入隊(duì)：p62p62出隊(duì)：出隊(duì)：p62p62隊(duì) 列第28頁/共48頁p = (QNode* ) malloc ( sizeof(QNode) ) ；if ( ! p ) exit (OVERFLOW) ；p- -data = e ；p- -next = NULL ； /申請(qǐng)新結(jié)點(diǎn)Q.rear- -next = p ；Q.rear = p ； /插入在隊(duì)尾return OK ；InQueue ( LinkQueue *Q ，datatype e ) 第2

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

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

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

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

18、隊(duì)列。插入元素 J0 、J1 、J2 、J3 、J4 ； 刪除元素 J0 、J1 ； 插入元素 J5 、J6 ； maxsize = 6J0J1J2J3J4Q.rearQ.frontJ5J6Q.rear第38頁/共48頁01Q.frontQ.rear2345初始，Q.front = Q.rear = 0 ，空隊(duì)列。插入元素 J0 、J1 、J2 、J3 、J4 、J5 ； J0J1J2J3J4J5Q.rearQ.rearQ.rearQ.rearQ.rearQ.rearQ.front = Q.rear = 0 ，滿隊(duì)列。maxsize = 6問題:第39頁/共48頁故無法通過 front = rear = 0 來分辨隊(duì)空或隊(duì)滿。解決方案:特殊空間，規(guī)定 front 與rear 之間總空出一個(gè)空間。隊(duì)空: Q.front = Q.rear隊(duì)滿: Q.front = (Q.rear + 1) % maxsize 01Q.front2345J0J1J2J3J4Q.rear第40頁/共48頁01Q.frontQ.rear2345初始，Q.front = Q.rear = 0，空隊(duì)列。插入元素 J0 、J1 、J2 、J3 、J4 ；Q.front = (Q.rear + 1) % maxsize 隊(duì)滿刪除元素 J0 、J1 ； 插入元素 J5 、J6