安全生产责任制考核评分表1

第3章栈和队列•10/5/2023•精选ppt•2栈和队列是两种重要的数据结构。从数据元素的逻辑关系看，栈与队列是线性表，但从操作方式与种类看，它们与线性表有许多不同。栈与队列是操作受限的线性表。尽管它们与线性表有许多共同点，但也有不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。3.1

栈（Stack）•10/5/2023•精选ppt•43.1.1抽象数据类型栈的定义一、定义1、栈(Stack)是限定在表尾进行插入或删除操作的线性表。表尾端称栈顶(top)，表头端称栈底(bottom)2、特点：栈的修改是按后进先出(LIFO)的原则进行的。3.1

栈（Stack）•10/5/2023•精选ppt•6例：设栈的初始状态为空，容量为5。若入栈元素的顺序是1、2、3、4、5，则出栈元素的

顺序不可能是【

】。A.

12345

B.

34125

C.

24351

D.

543213.1

栈（Stack）•10/5/2023•精选ppt•7二、栈的抽象数据类型定义ADT

Stack{数据对象：D＝{ai

|

ai

∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai

>|

ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&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的元素个数，即栈的长度。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栈的表示和实现一、顺序栈1、定义：栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。2、初始化空栈时不限定栈的最大容量：先分配一个基本容量，需要时再逐渐扩大STACK_INIT_SIZE;

STACKINCREMENT3、设置栈底指针base，始终指向栈底。当base＝NULL，栈不存在当top＝base时，栈空toptoptop•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栈栈的应用举例队列抽象数据类型队列的定义链队列－队列的链式表示和实现循环队列－队列的顺序表示和实现3.2栈的应用举例•10/5/2023•精选ppt•19由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中的有用工具。3.2.1数制转换十进制数N和其它d进制数的转换是计算机计算的基本问题。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计算时从低位到高位顺序产生八进制数的各个数位显示时按从高位到低位的顺序输出•10/5/2023•精选ppt•203.2栈的应用举例•10/5/2023•精选ppt•21void

conversion(

){

InitStack(s);//构建空栈scanf(“%d”,N);

//输入一个非负十进制整数while(N)

{//N不等于零，循环push(s,N%8);

//N/8第一个余数进栈N=N/8;//整除运算}while(!StackEmpty(s))//输出存放在栈中//的八制数位{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行编辑程序一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定＃为退格符，以表示前一个字符无效，@为退行符，表示当前行所有字符均无效。例：在终端上用户输入为whli##ilr#e(s#*s)outcha@putchar(*s=#++);应为while(*s)putchar(*s++);3.2栈的应用举例•10/5/2023•精选ppt•24void

lineEdit(

){//利用字符栈S，从终端接收一行并传送至调用过程的数据区。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();//从终端接收下一个字符}将从栈底到栈顶的字符传送至调用过程的数据区;ClearStack(S);

//

重置S为空栈if(ch!=EOF）

ch=getchar(

);}DestroyStack(S);}第3章栈和队列•10/5/2023•精选ppt•26栈栈的应用举例队列抽象数据类型队列的定义链队列－队列的链式表示和实现循环队列－队列的顺序表示和实现3.4队列•10/5/2023•精选ppt•273.4.1抽象数据类型队列的定义一、定义：1、队列(queue)是一种先进先出(FIFO)的线性表。限定仅能在表头进行删除，表尾进行插入。队列的典型例子有操作系统中的作业排队和顾客服务部门的工作方式等。3.4队列•10/5/2023•精选ppt•28二、队列的抽象数据类型定义ADT

Queue{数据对象：D＝{ai

|

ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：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的元素个数，即队列的长度。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链队列－队列的链式表示和实现一、定义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定义－基本操作的算法实现

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循环队列－队列的顺序表示和实现一、定义用一组地址连续的存储单元依次存放从队列头到队列尾的元素，并附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。二、顺序队列↔循环队列P63

图3.12

图3.133.4队列•10/5/2023•精选ppt•403.4队列三、循环队列的问题和解决方法•10/5/2023•精选ppt•413.4队列•10/5/2023•精选ppt•42队列满和队列空：Q.front=Q.rear只凭上式，无法判断是队满还是队空。有两种解决方法：另设一个标志位以区分队空、队满。少用一个存储单元，队满条件front=rear+1;本书中算法用2）方法。3.4队列•10/5/2023•精选ppt•43四、循环队列的C语言表示#Define

MAXQSIZE

100

//最大队列长度

typedef

struct{QElemType

*base;//初始化的动态分配存储空间int

front;//头指针，若队列不空，指向头元素int

rear;//尾指针，若队列不空，指向队列尾元素//的下一个位置}SqQueue;3.4队列•10/5/2023•精选ppt•44五、循环队列的基本操作的算法描述

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的元素个数，即队列的长度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