安全生產(chǎn)責(zé)任制考核評(píng)分表

2023/1/31第3章棧和隊(duì)列3.1棧抽象數(shù)據(jù)類型棧的定義棧的表示和實(shí)現(xiàn)3.2棧的應(yīng)用舉例3.4隊(duì)列抽象數(shù)據(jù)類型隊(duì)列的定義鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)2023/1/32第3章棧和隊(duì)列棧和隊(duì)列是兩種重要的數(shù)據(jù)結(jié)構(gòu)。從數(shù)據(jù)元素的邏輯關(guān)系看，棧與隊(duì)列是線性表，但從操作方式與種類看，它們與線性表有許多不同。棧與隊(duì)列是操作受限的線性表。盡管它們與線性表有許多共同點(diǎn)，但也有不少特殊性。本章重點(diǎn)介紹這些特殊性，并給出一些典型的應(yīng)用實(shí)例。2023/1/33第3章棧和隊(duì)列3.1棧3.2棧的應(yīng)用舉例3.4隊(duì)列抽象數(shù)據(jù)類型隊(duì)列的定義鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)2023/1/343.1棧（Stack）抽象數(shù)據(jù)類型棧的定義一、定義1、棧(Stack)是限定在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱棧頂(top)，表頭端稱棧底(bottom)2、特點(diǎn)：棧的修改是按后進(jìn)先出(LIFO)的原則進(jìn)行的。2023/1/353.1棧（Stack）2023/1/363.1棧（Stack）例：設(shè)棧的初始狀態(tài)為空，容量為5。若入棧元素的順序是1、2、3、4、5，則出棧元素的順序不可能是【】。

A.12345B.34125C.24351D.543212023/1/373.1棧（Stack）二、棧的抽象數(shù)據(jù)類型定義ADTStack{

數(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

端為棧底?；静僮鳎?/p>

InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧S。

DestroyStack(&S)

初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。2023/1/383.1棧（Stack）

ClearStack(&S)

初始條件：棧S已存在。操作結(jié)果：將S清為空棧。

StackEmpty(S)

初始條件：棧S已存在。操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSE。

StackLength(S)

初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。2023/1/393.1棧（Stack）

GetTop(S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。

Push(&S,e)

初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。

Pop(&S,&e)

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

}ADTStack2023/1/3103.1棧（Stack）棧的表示和實(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í)，棧空2023/1/311topbasebasetopbasetopbasetopAABCDEAB空棧

A進(jìn)棧EDC出棧

BCDE進(jìn)棧3.1棧（Stack）2023/1/3123.1棧（Stack）二、順序棧的C語(yǔ)言定義順序棧的類型定義如下：#defineSTACK_INIT_SIZE100//存儲(chǔ)空間初始分配量#defineSTACKINCREMENT10;//存儲(chǔ)空間分配增量

typedefstruct{SElemType*base;//在構(gòu)造之前和銷毀之后base的值是NULLSElemType*top;//棧頂指針

intStacksize;//棧的當(dāng)前可使用的最大容量.}SqStack;2023/1/3133.1棧（Stack）三、順序棧的應(yīng)用1、初始化

StatusInitStack(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;returnOK;}//InitStack2023/1/3143.1棧（Stack）2、讀棧頂元素StatusGetTop(SqStackS,SElemType&e){//若棧不空，則用e返回S的棧頂元素，并返回ok;//否則返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}//GetTop2023/1/3153.1棧（Stack）3、插入元素StatusPush(SqStack&S,SElemTypee){//插入元素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;returnOK；

}//Push2023/1/3163.1棧（Stack）4、刪除StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，用e返回

//其值,并返回OK；否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}//Pop2023/1/3173.1棧（Stack）四、鏈棧棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧。它是運(yùn)算受限的單鏈表，是線性鏈表的特例。插入和刪除操作僅限制在表頭位置上進(jìn)行。data

next

san-1a1an棧頂棧底2023/1/318第3章棧和隊(duì)列3.1棧3.2棧的應(yīng)用舉例3.4隊(duì)列抽象數(shù)據(jù)類型隊(duì)列的定義鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)2023/1/3193.2棧的應(yīng)用舉例

由于棧結(jié)構(gòu)具有的后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中的有用工具。數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其它d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)計(jì)算的基本問題。2023/1/3203.2棧的應(yīng)用舉例

N=(Ndivd)*d+nmodd(其中:div為整除運(yùn)算,mod為求余運(yùn)算)

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

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

{

InitStack(s);//構(gòu)建空棧

scanf(“%d”,N);//輸入一個(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);

}

}//conversion2023/1/3223.2棧的應(yīng)用舉例3.2.3括號(hào)匹配的檢驗(yàn)算法思路：1、構(gòu)建空棧，如左括號(hào)則入棧；2、如右括號(hào)，則讀棧頂元素。若與其匹配，則出棧；若不匹配，則返回“不匹配”；3、判定棧是否為空，若棧不空，則返回“不匹配”。例1[([][])]例2[([][])2023/1/3233.2棧的應(yīng)用舉例3.2.3行編輯程序一個(gè)簡(jiǎn)單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。允許用戶輸入出錯(cuò)時(shí)可以及時(shí)更正。可以約定＃為退格符，以表示前一個(gè)字符無(wú)效，@為退行符，表示當(dāng)前行所有字符均無(wú)效。

例：在終端上用戶輸入為

whli##ilr#e(s#*s)應(yīng)為while(*s)outcha@putchar(*s=#++);putchar(*s++);

2023/1/3243.2棧的應(yīng)用舉例voidlineEdit(){//利用字符棧S，從終端接收一行并傳送至調(diào)用過程的數(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為空棧2023/1/3253.2棧的應(yīng)用舉例

default:Push(S,ch);break;//有效字符進(jìn)

//棧，未考慮棧滿情形

}ch=getchar();//從終端接收下一個(gè)字符

}

將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū);ClearStack(S);//重置S為空棧

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

數(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}

約定其中a1端為隊(duì)列頭，an

端為隊(duì)列尾?；静僮鳎?/p>

InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。

DestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。操作結(jié)果：隊(duì)列Q被銷毀，不再存在。2023/1/3293.4隊(duì)列

ClearQueue(&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)度。2023/1/3303.4隊(duì)列

GetHead(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返回其值。

}ADTQueue2023/1/3313.4隊(duì)列3.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ì)滿問題，但有隊(duì)空問題。隊(duì)空條件為front==rear。2023/1/3323.4隊(duì)列2023/1/3333.4隊(duì)列二、鏈隊(duì)列的C語(yǔ)言定義typedefstructQNode{//結(jié)點(diǎn)類型

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//鏈隊(duì)列類型

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

QueuePtrrear;//隊(duì)尾指針}LinkQueue;2023/1/3343.4隊(duì)列2023/1/3353.4隊(duì)列三、鏈隊(duì)列的ADT定義－基本操作的算法實(shí)現(xiàn)1、初始化StatusInitQueue(LinkQueue&Q){//構(gòu)造一個(gè)空隊(duì)列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}2023/1/3363.4隊(duì)列2、銷毀StatusDestroyqueue(LinkQueue&Q){//隊(duì)列Q存在則銷毀Qwhile(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}2023/1/3373.4隊(duì)列3、插入StatusEnQueue(LinkQueue&Q,QElemTypee){

//隊(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;returnOK;}2023/1/3383.4隊(duì)列4、刪除StatusDeQueue(LinkQueue&Q,QElemType&e){

//Q為非空隊(duì)列,刪除Q的隊(duì)頭元素,并用e返回其值

if(Q.front==Q.rear)returnERROR;

p=Q.front->next;

e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;

free(p);returnOK;}2023/1/3393.4隊(duì)列循環(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.132023/1/3403.4隊(duì)列2023/1/3413.4隊(duì)列三、循環(huán)隊(duì)列的問題和解決方法2023/1/3423.4隊(duì)列隊(duì)列滿和隊(duì)列空：Q.front=Q.rear只憑上式，無(wú)法判斷是隊(duì)滿還是隊(duì)空。有兩種解決方法：

1）另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)空、隊(duì)滿。

2）少用一個(gè)存儲(chǔ)單元，隊(duì)滿條件

front=rear+1;

本書中算法用2）方法。2023/1/3433.4隊(duì)列四、循環(huán)隊(duì)列的C語(yǔ)言表示#DefineMAXQSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{

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

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

intrear;//尾指針，若隊(duì)列不空，指向隊(duì)列尾元素

//的下一個(gè)位置}SqQueue;2023/1/3443.4隊(duì)列五、循環(huán)隊(duì)列的基本操作的算法描述1、初始化StatusInitQueue（SqQueue&Q）{

//構(gòu)造一個(gè)空隊(duì)列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front＝Q.rear＝0;returnOK;}2023/1/3453.4隊(duì)列2、求隊(duì)列長(zhǎng)度intQueueLength（SqQueueQ）{

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

return（Q.rear－Q.front＋MAXQSIZE）％MAXQSIZE

；}2023/1/3463.4隊(duì)列3、插入StatusEnQueue(SqQueue&Q,QElemTypee){

//插入元素e為Q的新的隊(duì)尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR；//隊(duì)列滿

Q.base[Q.rear]=e;

Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}2023/1/3473.4隊(duì)列4、刪除StatusDeQueue(SqQueue&Q,QElemType&e){

//隊(duì)列Q存在,刪除Q的隊(duì)頭元素，用e返回//其值，并返回OK；否則返回ERROR

if(Q.rear==Q.front)returnERROR；//隊(duì)列空

e=Q.base[Q.fro