安全生產責任制考核評分表1

第3章棧和隊列?10/5/2023?精選ppt?2棧和隊列是兩種重要的數(shù)據(jù)結構。從數(shù)據(jù)元素的邏輯關系看，棧與隊列是線性表，但從操作方式與種類看，它們與線性表有許多不同。棧與隊列是操作受限的線性表。盡管它們與線性表有許多共同點，但也有不少特殊性。本章重點介紹這些特殊性，并給出一些典型的應用實例。3.1

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

棧（Stack）?10/5/2023?精選ppt?6例：設棧的初始狀態(tài)為空，容量為5。若入棧元素的順序是1、2、3、4、5，則出棧元素的

順序不可能是【

】。A.

12345

B.

34125

C.

24351

D.

543213.1

棧（Stack）?10/5/2023?精選ppt?7二、棧的抽象數(shù)據(jù)類型定義ADT

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

|

ai

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

>|

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

棧（Stack）?10/5/2023?精選ppt?8ClearStack(&S)初始條件：棧S已存在。

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

棧（Stack）?10/5/2023?精選ppt?9GetTop(S,

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

ADT

Stack3.1

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

STACKINCREMENT3、設置棧底指針base，始終指向棧底。當base＝NULL，棧不存在當top＝base時，?？誸optoptop?10/5/2023?精選ppt?11topEDCBBbasebaseAbaseA

base

A空棧A進棧B

C

D

E進棧E

D

C出棧3.1

棧（Stack）3.1

棧（Stack）?10/5/2023?精選ppt?12二、順序棧的C語言定義

順序棧的類型定義如下：#define

STACK_INIT_SIZE100//存儲空間初始分配量#define

STACKINCREMENT

10;//存儲空間分配增量typedef

struct{SElemType

*base;//在構造之前和銷毀之后base的值是NULLSElemType

*top;//棧頂指針int

Stacksize;//棧的當前可使用的最大容量.}SqStack;3.1

棧（Stack）?10/5/2023?精選ppt?13三、順序棧的應用1、初始化Status

InitStack(SqStack

&S)

{//構造一個空棧SS.base=(SelemType

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

S.stacksize=STACK_INIT_SIZE;return

OK;}//InitStack3.1

棧（Stack）?10/5/2023?精選ppt?142、讀棧頂元素Status

GetTop(SqStack

S,SElemType

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

return

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

//GetTop3.1

棧（Stack）?10/5/2023?精選ppt?153、插入元素Status

Push(SqStack

&S,SElemType

e)

{//插入元素e為新的棧頂元素if(S.top-s.base>=S.stacksize){//棧滿，追加存儲空間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）?10/5/2023?精選ppt?164、刪除Status

Pop(SqStack

&S,SElemType

&e)

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

ERROR;e=*--S.top;returnOK;}//Pop3.1

棧（Stack）四、鏈棧棧的鏈式存儲結構稱為鏈棧。它是運算受限的單鏈表，是線性鏈表的特例。插入和刪除操作僅限制在表頭位置上進行。datanextsan-1a1an棧頂?10/5/2023?精選ppt?17棧底第3章棧和隊列?10/5/2023?精選ppt?18棧棧的應用舉例隊列抽象數(shù)據(jù)類型隊列的定義鏈隊列－隊列的鏈式表示和實現(xiàn)循環(huán)隊列－隊列的順序表示和實現(xiàn)3.2棧的應用舉例?10/5/2023?精選ppt?19由于棧結構具有的后進先出的固有特性，致使棧成為程序設計中的有用工具。3.2.1數(shù)制轉換十進制數(shù)N和其它d進制數(shù)的轉換是計算機計算的基本問題。3.2棧的應用舉例N=(N

div

d)*d+n

mod

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

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

div

8N

mod

81348

168

21168

21

24

0

5202計算時從低位到高位順序產生八進制數(shù)的各個數(shù)位顯示時按從高位到低位的順序輸出?10/5/2023?精選ppt?203.2棧的應用舉例?10/5/2023?精選ppt?21void

conversion(

){

InitStack(s);//構建空棧scanf(“%d”,N);

//輸入一個非負十進制整數(shù)while(N)

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

//N/8第一個余數(shù)進棧N=N/8;//整除運算}while(!StackEmpty(s))//輸出存放在棧中//的八制數(shù)位{Pop(s);printf(“%d”,e);}}//conversion3.2棧的應用舉例?10/5/2023?精選ppt?223.2.3括號匹配的檢驗算法思路：1、構建空棧，如左括號則入棧；2、如右括號，則讀棧頂元素。若與其匹配，則出棧；若不匹配，則返回“不匹配”；3、判定棧是否為空，若棧不空，則返回“不匹配”。例1

[

(

[

]

[

]

)

]例2

[

(

[

]

[

]

)3.2棧的應用舉例?10/5/2023?精選ppt?233.2.3行編輯程序一個簡單的行編輯程序的功能是：接受用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。允許用戶輸入出錯時可以及時更正?？梢约s定＃為退格符，以表示前一個字符無效，@為退行符，表示當前行所有字符均無效。例：在終端上用戶輸入為whli##ilr#e(s#*s)outcha@putchar(*s=#++);應為while(*s)putchar(*s++);3.2棧的應用舉例?10/5/2023?精選ppt?24void

lineEdit(

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

&&

ch!=‘\n’){switch(ch){case‘#’:Pop(s,c);break;//僅當棧非空時退棧case‘@’:ClearStack(s);break;//重置S為空棧3.2棧的應用舉例?10/5/2023?精選ppt?25default:Push(S,ch);break;//有效字符進//棧，未考慮棧滿情形}ch=getchar();//從終端接收下一個字符}將從棧底到棧頂?shù)淖址麄魉椭琳{用過程的數(shù)據(jù)區(qū);ClearStack(S);

//

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

ch=getchar(

);}DestroyStack(S);}第3章棧和隊列?10/5/2023?精選ppt?26棧棧的應用舉例隊列抽象數(shù)據(jù)類型隊列的定義鏈隊列－隊列的鏈式表示和實現(xiàn)循環(huán)隊列－隊列的順序表示和實現(xiàn)3.4隊列?10/5/2023?精選ppt?273.4.1抽象數(shù)據(jù)類型隊列的定義一、定義：1、隊列(queue)是一種先進先出(FIFO)的線性表。限定僅能在表頭進行刪除，表尾進行插入。隊列的典型例子有操作系統(tǒng)中的作業(yè)排隊和顧客服務部門的工作方式等。3.4隊列?10/5/2023?精選ppt?28二、隊列的抽象數(shù)據(jù)類型定義ADT

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

|

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

i-1,ai

>|

ai-1,ai

∈D,i=2,...,n}約定其中a1端為隊列頭，an

端為隊列尾。基本操作：InitQueue(&Q)操作結果：構造一個空隊列Q。DestroyQueue(&Q)初始條件：隊列Q已存在。操作結果：隊列Q被銷毀，不再存在。3.4隊列?10/5/2023?精選ppt?29ClearQueue(&Q)初始條件：隊列Q已存在。

操作結果：將Q清為空隊列。QueueEmpty(Q)初始條件：隊列Q已存在。操作結果：若Q為空隊列，則返回TRUE，否則返回FALSE。QueueLength(Q)初始條件：隊列Q已存在。操作結果：返回Q的元素個數(shù)，即隊列的長度。3.4隊列?10/5/2023?精選ppt?30GetHead(Q,

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

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

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

ADT

Queue3.4隊列?10/5/2023?精選ppt?313.4.2鏈隊列－隊列的鏈式表示和實現(xiàn)一、定義1、用鏈表表示的隊列。一個鏈隊列需要兩個分別指示隊頭和隊尾的指針。隊頭在鏈頭，隊尾在鏈尾。2、鏈式隊列在進隊時無隊滿問題，但有隊空問題。隊空條件為front==rear。3.4隊列?10/5/2023?精選ppt?323.4隊列?10/5/2023?精選ppt?33二、鏈隊列的C語言定義typedef

struct

QNode{//結點類型

QElemType

data;struct

QNode

*next;}QNode,*QueuePtr;typedef

struct{//鏈隊列類型

QueuePtr

front;//隊頭指針

QueuePtr

rear;//隊尾指針}LinkQueue;3.4隊列?10/5/2023?精選ppt?343.4隊列?10/5/2023?精選ppt?35三、鏈隊列的ADT定義－基本操作的算法實現(xiàn)

1、初始化Status

InitQueue(LinkQueue

&Q)

{//構造一個空隊列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}3.4隊列?10/5/2023?精選ppt?362、銷毀Status

Destroyqueue(LinkQueue

&Q)

{//隊列Q存在則銷毀Qwhile(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}3.4隊列?10/5/2023?精選ppt?373、插入Status

EnQueue(LinkQueue

&Q,QElemType

e)

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

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}3.4隊列?10/5/2023?精選ppt?384、刪除Status

DeQueue(LinkQueue

&Q,QElemType

&e)

{//Q為非空隊列,刪除Q的隊頭元素,并用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隊列?10/5/2023?精選ppt?393.4.3循環(huán)隊列－隊列的順序表示和實現(xiàn)一、定義用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素，并附設兩個指針front和rear分別指示隊列頭元素和隊列尾元素的位置。二、順序隊列?循環(huán)隊列P63

圖3.12

圖3.133.4隊列?10/5/2023?精選ppt?403.4隊列三、循環(huán)隊列的問題和解決方法?10/5/2023?精選ppt?413.4隊列?10/5/2023?精選ppt?42隊列滿和隊列空：Q.front=Q.rear只憑上式，無法判斷是隊滿還是隊空。有兩種解決方法：另設一個標志位以區(qū)分隊空、隊滿。少用一個存儲單元，隊滿條件front=rear+1;本書中算法用2）方法。3.4隊列?10/5/2023?精選ppt?43四、循環(huán)隊列的C語言表示#Define

MAXQSIZE

100

//最大隊列長度

typedef

struct{QElemType

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

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

rear;//尾指針，若隊列不空，指向隊列尾元素//的下一個位置}SqQueue;3.4隊列?10/5/2023?精選ppt?44五、循環(huán)隊列的基本操作的算法描述

1、初始化Status

InitQueue（SqQueue

&Q）{//構造一個空隊列QQ.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front＝Q.rear＝0;returnOK;}3.4隊列?10/5/2023?精選ppt?452、求隊列長度int

QueueLength（SqQueue

Q）{//返回Q的元素個數(shù)，即隊列的長度return

（

Q.rear－Q.front＋MAXQSIZE

）

％MAXQSIZE

；}3.4隊列?10/5/2023?精選ppt?463、插入Status

EnQueue(SqQueue

&Q,QElemType

e)

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

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

%MAXQSIZE;returnOK;}3.4隊列?10/5/2023?精選ppt?47//其值4、刪除Status

DeQueue(SqQueue

&Q,QElemType

&e)

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

ERROR；//隊列空

e=Q.base[Q.fron