安全生產(chǎn)責(zé)任制考核評(píng)分表1研究報(bào)告

第3章棧和隊(duì)列11/7/20231棧抽象數(shù)據(jù)類型棧的定義棧的表示和實(shí)現(xiàn)棧的應(yīng)用舉例隊(duì)列抽象數(shù)據(jù)類型隊(duì)列的定義鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)第3章棧和隊(duì)列11/7/20232棧和隊(duì)列是兩種重要的數(shù)據(jù)結(jié)構(gòu)。從數(shù)據(jù)元素的邏輯關(guān)系看，棧與隊(duì)列是線性表，但從操作方式與種類看，它們與線性表有許多不同。棧與隊(duì)列是操作受限的線性表。盡管它們與線性表有許多共同點(diǎn)，但也有不少特殊性。本章重點(diǎn)介紹這些特殊性，并給出一些典型的應(yīng)用實(shí)例。第3章棧和隊(duì)列11/7/20233棧棧的應(yīng)用舉例隊(duì)列抽象數(shù)據(jù)類型隊(duì)列的定義鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)3.1

棧（Stack）11/7/202343.1.1抽象數(shù)據(jù)類型棧的定義一、定義1、棧(Stack)是限定在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱棧頂(top)，表頭端稱棧底(bottom)2、特點(diǎn)：棧的修改是按后進(jìn)先出(LIFO)的原則進(jìn)行的。3.1

棧（Stack）11/7/20236例：設(shè)棧的初始狀態(tài)為空，容量為5。若入棧元素的順序是1、2、3、4、5，則出棧元素的順序不可能是【】。A.

12345

B.

34125

C.

24351

D.

543213.1

棧（Stack）11/7/20237二、棧的抽象數(shù)據(jù)類型定義ADT

Stack{數(shù)據(jù)對(duì)象：D＝{ai|

ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai

>|

ai-1,ai∈D,i=2,...,n}約定an端為棧頂，a1端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。3.1

棧（Stack）11/7/20238ClearStack(&S)初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSE。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。3.1

棧（Stack）11/7/20239GetTop(S,

&e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S,&e)初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。}

ADT

Stack3.1

棧（Stack）11/7/2023103.1.2棧的表示和實(shí)現(xiàn)一、順序棧1、定義：棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。2、初始化空棧時(shí)不限定棧的最大容量：先分配一個(gè)基本容量，需要時(shí)再逐漸擴(kuò)大STACK_INIT_SIZE;

STACKINCREMENT3、設(shè)置棧底指針base，始終指向棧底。當(dāng)base＝NULL，棧不存在當(dāng)top＝base時(shí)，棧空top

basebasetopbasebasetop11/7/202311AABCtopEDBA空棧A進(jìn)棧E

D

C出棧B

C

D

E進(jìn)棧3.1

棧（Stack）3.1

棧（Stack）11/7/202312二、順序棧的C語(yǔ)言定義順序棧的類型定義如下：#define

STACK_INIT_SIZE100//存儲(chǔ)空間初始分配量#define

STACKINCREMENT

10;//存儲(chǔ)空間分配增量typedef

struct{SElemType

*base;//在構(gòu)造之前和銷毀之后base的值是NULLSElemType

*top;//棧頂指針int

Stacksize;//棧的當(dāng)前可使用的最大容量.}SqStack;3.1

棧（Stack）11/7/202313三、順序棧的應(yīng)用1、初始化Status

InitStack(SqStack

&S)

{//構(gòu)造一個(gè)空棧SS.base=(SelemType

*)malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗S.top=S.base;S.stacksize=STACK_INIT_SIZE;return

OK;}//InitStack3.1

棧（Stack）11/7/2023142、讀棧頂元素Status

GetTop(SqStack

S,SElemType

&e){//若棧不空，則用e返回S的棧頂元素，并返回ok;//否則返回ERRORif(S.top==S.base)

return

ERROR;e=*(S.top-1);return

OK;}

//GetTop3.1

棧（Stack）11/7/2023153、插入元素Status

Push(SqStack

&S,SElemType

e)

{//插入元素e為新的棧頂元素if(S.top-s.base>=S.stacksize){//棧滿，追加存儲(chǔ)空間S.base=(ElemType

*)realloc(S.base,(S.stacksize

+

STACKINCREMENT)

*sizeof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return

OK；}

//Push3.1

棧（Stack）11/7/2023164、刪除Status

Pop(SqStack

&S,SElemType

&e)

{//若棧不空，則刪除S的棧頂元素，用e返回//其值,并返回OK；否則返回ERRORif(S.top==S.base)return

ERROR;e=*--S.top;return

OK;}//Pop3.1

棧（Stack）四、鏈棧棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧。它是運(yùn)算受限的單鏈表，是線性鏈表的特例。插入和刪除操作僅限制在表頭位置上進(jìn)行。datanextsan-1a1an棧頂11/7/202317棧底第3章棧和隊(duì)列11/7/202318棧棧的應(yīng)用舉例隊(duì)列抽象數(shù)據(jù)類型隊(duì)列的定義鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)3.2棧的應(yīng)用舉例11/7/202319由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中的有用工具。3.2.1數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)計(jì)算的基本問(wèn)題。3.2棧的應(yīng)用舉例N=(N

div

d)*d+n

mod

d(其中:div為整除運(yùn)算,mod為求余運(yùn)算)

例如(1348)10=(2504)8，其運(yùn)算過(guò)程如下：NN

div

8N

mod

81348

168

21168

21

24

0

5202計(jì)算時(shí)從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位顯示時(shí)按從高位到低位的順序輸出11/7/2023203.2棧的應(yīng)用舉例11/7/202321void

conversion(

){

InitStack(s);scanf(“%d”,

N);//構(gòu)建空棧//輸入一個(gè)非負(fù)十進(jìn)制整數(shù)while(N)

{//N不等于零，循環(huán)push(s,N%8);

//N/8第一個(gè)余數(shù)進(jìn)棧N=N/8;//整除運(yùn)算}while(!StackEmpty(s))//輸出存放在棧中//的八制數(shù)位{Pop(s);printf(“%d”,e);}}//conversion3.2棧的應(yīng)用舉例11/7/2023223.2.3括號(hào)匹配的檢驗(yàn)算法思路：1、構(gòu)建空棧，如左括號(hào)則入棧；2、如右括號(hào)，則讀棧頂元素。若與其匹配，則出棧；若不匹配，則返回“不匹配”；3、判定棧是否為空，若棧不空，則返回“不匹配”。例1

[

(

[

]

[

]

)

]例2

[

(

[

]

[

]

)3.2棧的應(yīng)用舉例11/7/2023233.2.3行編輯程序一個(gè)簡(jiǎn)單的行編輯程序的功能是：接受用戶

從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。允許用戶輸入出錯(cuò)時(shí)可以及時(shí)更正?？梢约s定＃為退格符，以表示前一個(gè)字符無(wú)效，@為退行符，表示當(dāng)前行所有字符均無(wú)效。例：在終端上用戶輸入為whli##ilr#e(s#*s)outcha@putchar(*s=#++);應(yīng)為while(*s)putchar(*s++);3.2棧的應(yīng)用舉例11/7/202324void

lineEdit(

){//利用字符棧S，從終端接收一行并傳送至調(diào)用過(guò)程的數(shù)據(jù)區(qū)。InitStack(S);ch=getchar();//從終端接收第一個(gè)字符while(ch!=EOF){//EOF為全文結(jié)束符while(ch!=EOF

&&

ch!=‘\n’){switch(ch){case‘#’:Pop(s,c);break;//僅當(dāng)棧非空時(shí)退棧case‘@’:ClearStack(s);break;//重置S為空棧3.2棧的應(yīng)用舉例11/7/202325default:Push(S,ch);break;//有效字符進(jìn)//棧，未考慮棧滿情形}ch=getchar();//從終端接收下一個(gè)字符}將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū);ClearStack(S);

//

重置S為空棧if(ch!=EOF）

ch=getchar();}DestroyStack(S);}第3章棧和隊(duì)列11/7/202326棧棧的應(yīng)用舉例隊(duì)列抽象數(shù)據(jù)類型隊(duì)列的定義鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)3.4隊(duì)列11/7/2023273.4.1抽象數(shù)據(jù)類型隊(duì)列的定義一、定義：1、隊(duì)列(queue)是一種先進(jìn)先出(FIFO)的線性表。限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入。隊(duì)列的典型例子有操作系統(tǒng)中的作業(yè)排隊(duì)和顧客服務(wù)部門(mén)的工作方式等。3.4隊(duì)列11/7/202328二、隊(duì)列的抽象數(shù)據(jù)類型定義ADT

Queue{數(shù)據(jù)對(duì)象：D＝{ai

|

ai∈ElemSet,i=1,2,...,n,n≥0}數(shù)據(jù)關(guān)系：R1＝{<a

i-1,ai

>|

ai-1,ai∈D,i=2,...,n}約定其中a1

端為隊(duì)列頭，an

端為隊(duì)列尾?；静僮鳎篒nitQueue(&Q)操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(&Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。3.4隊(duì)列11/7/202329ClearQueue(&Q)初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。QueueEmpty(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件：隊(duì)列Q已存在。操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。3.4隊(duì)列11/7/202330GetHead(Q,

&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：用e返回Q的隊(duì)頭元素。

EnQueue(&Q,e)初始條件：隊(duì)列Q已存在。操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。

DeQueue(&Q,&e)初始條件：Q為非空隊(duì)列。操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。}

ADT

Queue3.4隊(duì)列11/7/2023313.4.2鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一、定義1、用鏈表表示的隊(duì)列。一個(gè)鏈隊(duì)列需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。2、鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。隊(duì)空條件為front==rear。3.4隊(duì)列11/7/2023323.4隊(duì)列11/7/202333二、鏈隊(duì)列的C語(yǔ)言定義typedef

struct

QNode{//結(jié)點(diǎn)類型

QElemType

data;struct

QNode

*next;}QNode,*QueuePtr;typedef

struct{//鏈隊(duì)列類型

QueuePtr

front;//隊(duì)頭指針

QueuePtr

rear;//隊(duì)尾指針}LinkQueue;3.4隊(duì)列11/7/2023343.4隊(duì)列11/7/202335三、鏈隊(duì)列的ADT定義－基本操作的算法實(shí)現(xiàn)

1、初始化Status

InitQueue(LinkQueue

&Q)

{//構(gòu)造一個(gè)空隊(duì)列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;return

OK;}3.4隊(duì)列11/7/2023362、銷毀Status

Destroyqueue(LinkQueue

&Q)

{//隊(duì)列Q存在則銷毀Qwhile(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}return

OK;}3.4隊(duì)列11/7/2023373、插入Status

EnQueue(LinkQueue

&Q,QElemType

e)

{//隊(duì)列Q存在,插入元素e為Q的隊(duì)尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return

OK;}3.4隊(duì)列11/7/2023384、刪除Status

DeQueue(LinkQueue

&Q,QElemType

&e)

{//Q為非空隊(duì)列,刪除Q的隊(duì)頭元素,并用e返回其值if(Q.front==Q.rear)return

ERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return

OK;}3.4隊(duì)列11/7/2023393.4.3循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)一、定義用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素，并附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置。二、順序隊(duì)列?循環(huán)隊(duì)列P63

圖3.12

圖3.133.4隊(duì)列11/7/2023403.4隊(duì)列三、循環(huán)隊(duì)列的問(wèn)題和解決方法11/7/2023413.4隊(duì)列11/7/202342隊(duì)列滿和隊(duì)列空：Q.front=Q.rear只憑上式，無(wú)法判斷是隊(duì)滿還是隊(duì)空。有兩種解決方法：另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)空、隊(duì)滿。少用一個(gè)存儲(chǔ)單元，隊(duì)滿條件front=rear+1;本書(shū)中算法用2）方法。3.4隊(duì)列11/7/202343四、循環(huán)隊(duì)列的C語(yǔ)言表示#Define

MAXQSIZE

100

//最大隊(duì)列長(zhǎng)度

typedef

struct{QElemType

*base;//初始化的動(dòng)態(tài)分配存儲(chǔ)空間int

front;//頭指針，若隊(duì)列不空，指向頭元素int

rear;//尾指針，若隊(duì)列不空，指向隊(duì)列尾元素//的下一個(gè)位置}SqQueue;3.4隊(duì)列11/7/202344五、循環(huán)隊(duì)列的基本操作的算法描述

1、初始化Status

InitQueue（SqQueue

&Q）{//構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front＝Q.rear＝0;return

OK;}3.4隊(duì)列11/7/2023452、求隊(duì)列長(zhǎng)度int

QueueLength（SqQueue

Q）{//返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度return

（

Q.rear－Q.front＋MAXQSIZE

）

％MAXQSIZE

；}3.4隊(duì)列11/7/2023463、插入Status

EnQueue(SqQueue

&Q,QElemType

e)

{//插入元素e為Q的新的隊(duì)尾元素if((Q.rear+1)%MAXQSIZE==Q.front)return

ERROR；//隊(duì)列滿Q.base[Q.rear]=e;Q.rear=(Q.rear+1)

%MAXQSIZE;return

OK;}3.4隊(duì)列11/7/202347//其值4、刪除Status

DeQueue(SqQueue

&Q,QElemType

&e)

{//隊(duì)列Q存在,刪除Q的隊(duì)頭元素，用e返回并返回OK；否則返回ERRORif(Q.rear==Q.front)return

ERROR；//隊(duì)列空

e=Q.base[Q.front];Q.