安全生产责任制考核评分表[1].ppt

《安全生产责任制考核评分表[1].ppt》由会员分享，可在线阅读，更多相关《安全生产责任制考核评分表[1].ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、安全生产责任制考核评分表1 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第第3章章 栈和队列栈和队列栈和队列是两种重要的数据结构。栈和队列是两种重要的数据结构。从数据元素的逻辑关系看，栈与队列是线从数据元素的逻辑关系看，栈与队列是线性表，但从操作方式与种类看，它们与线性表，但从操作方式与种类看，它们与线性表有许多不同。性表有许多不同。栈与队列是操作受限的线性表。栈与队列是操作受限的线性表。尽管它们与线性表有许多共同点，但也有尽管它们与线性表有许多共同点，但也有不

2、少特殊性。本章重点介绍这些特殊性，不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。并给出一些典型的应用实例。11/6/20222第第3章章 栈和队列栈和队列3.1栈栈3.2栈的应用举例栈的应用举例3.4队列队列 3.4.1抽象数据类型队列的定义抽象数据类型队列的定义 3.4.2链队列链队列 队列的链式表示和实现队列的链式表示和实现 3.4.3循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现11/6/202233.1 栈（栈（Stack）3.1.1抽象数据类型栈的定义抽象数据类型栈的定义一、定义一、定义1、栈、栈(Stack)是限定在表尾进行插入或删除操是限定在表尾进行插入

3、或删除操 作的线性表。表尾端称栈顶作的线性表。表尾端称栈顶(top)，表头端，表头端 称栈底称栈底(bottom)2、特点：栈的修改是按后进先出、特点：栈的修改是按后进先出(LIFO)的原的原 则进行的。则进行的。11/6/202243.1 栈（栈（Stack）11/6/202253.1 栈（栈（Stack）例：设栈的初始状态为空，容量为例：设栈的初始状态为空，容量为5。若入栈元。若入栈元素的顺序是素的顺序是1、2、3、4、5，则出栈元素的，则出栈元素的顺序不可能是【顺序不可能是【】。】。A.12345 B.34125 C.24351 D.5432111/6/202263.1 栈（栈（Stac

4、k）二、栈的抽象数据类型定义二、栈的抽象数据类型定义ADT Stack 数据对象：数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,aiD,i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。基本操作：基本操作：InitStack(&S)操作结果：构造一个空栈操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：栈操作结果：栈S被销毁。被销毁。11/6/202273.1 栈（栈（Stack）ClearStack(&S)初始条件：栈初始条件：栈S已存在。已存在。操

5、作结果：将操作结果：将S清为空栈。清为空栈。StackEmpty(S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：若栈操作结果：若栈S为空栈，则返回为空栈，则返回TRUE，否，否 则则FALSE。StackLength(S)初始条件：栈初始条件：栈S已存在。已存在。操作结果：返回操作结果：返回S的元素个数，即栈的长度。的元素个数，即栈的长度。11/6/202283.1 栈（栈（Stack）GetTop(S,&e)初始条件：栈初始条件：栈S已存在且非空。已存在且非空。操作结果：用操作结果：用e返回返回S的栈顶元素。的栈顶元素。Push(&S,e)初始条件：栈初始条件：栈S已存在。已存在。

6、操作结果：插入元素操作结果：插入元素e为新的栈顶元素。为新的栈顶元素。Pop(&S,&e)初始条件：栈初始条件：栈S已存在且非空。已存在且非空。操作结果：删除操作结果：删除S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。ADT Stack11/6/202293.1 栈（栈（Stack）3.1.2栈的表示和实现栈的表示和实现一、顺序栈一、顺序栈1、定义：栈的顺序存储结构是利用一组地址连续的存、定义：栈的顺序存储结构是利用一组地址连续的存 储单元依次存放自栈底到栈顶的数据元素，同时附储单元依次存放自栈底到栈顶的数据元素，同时附 设指针设指针top指示栈顶元素在顺序栈中的位置。指示栈顶元素在

7、顺序栈中的位置。2、初始化空栈时不限定栈的最大容量：先分配一个基初始化空栈时不限定栈的最大容量：先分配一个基 本容量，需要时再逐渐扩大本容量，需要时再逐渐扩大STACK_INIT_SIZE;STACKINCREMENT3、设置栈底指针设置栈底指针base，始终指向栈底。，始终指向栈底。当当baseNULL，栈不存在，栈不存在 当当topbase时，栈空时，栈空11/6/202210toptopbasebasebasebasetoptopbasebasetoptopbasebasetoptopA AA AB BC CD DE EA AB B空栈空栈 A进栈进栈E D C 出栈出栈 B C D E

8、 进栈进栈3.1 栈（栈（Stack）11/6/2022113.1 栈（栈（Stack）二、顺序栈的二、顺序栈的C语言定义语言定义顺序栈的类型定义如下：顺序栈的类型定义如下：#define STACK_INIT_SIZE 100/存储空间初始分配量存储空间初始分配量#define STACKINCREMENT 10;/存储空间分配增量存储空间分配增量 typedef struct SElemType *base;/在构造之前和销毁之后在构造之前和销毁之后base的值是的值是NULL SElemType *top;/栈顶指针栈顶指针 int Stacksize;/栈的当前可使用的最大容量栈的当前

9、可使用的最大容量.SqStack;11/6/2022123.1 栈（栈（Stack）三、顺序栈的应用三、顺序栈的应用1、初始化、初始化 Status InitStack(SqStack&S)/构造一个空栈构造一个空栈S S.base=(SelemType*)malloc(STACK_INIT_SIZE *sizeof(ElemType);if(!S.base)exit(OVERFLOW);/存储分配失败存储分配失败 S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;/InitStack 11/6/2022133.1 栈（栈（Stack）2、读

10、栈顶元素、读栈顶元素Status GetTop(SqStack S,SElemType&e)/若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回ok;/否则返回否则返回ERROR if(S.top=S.base)return ERROR;e=*(S.top-1);return OK;/GetTop11/6/2022143.1 栈（栈（Stack）3、插入元素、插入元素Status Push(SqStack&S,SElemType e)/插入元素插入元素e为新的栈顶元素为新的栈顶元素 if(S.top-s.base=S.stacksize)/栈满，追加存储空间栈满，追加

11、存储空间 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；/Push11/6/2022153.1 栈（栈（Stack）4、删除、删除Status Pop(SqStack&S,SElemType&e)/若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e返回返回 /其值其值,并返回

12、并返回OK；否则返回；否则返回ERROR if(S.top=S.base)return ERROR;e=*-S.top;return OK;/Pop 11/6/2022163.1 栈（栈（Stack）四、链栈四、链栈 栈的链式存储结构栈的链式存储结构称为链栈。它是运算称为链栈。它是运算受限的单链表，是线受限的单链表，是线性链表的特例。插入性链表的特例。插入和删除操作仅限制在和删除操作仅限制在表头位置上进行。表头位置上进行。data next sa an-1a a1 1a an栈顶栈顶栈底栈底11/6/202217第第3章章 栈和队列栈和队列3.1栈栈3.2栈的应用举例栈的应用举例3.4队列队列

13、 3.4.1抽象数据类型队列的定义抽象数据类型队列的定义 3.4.2链队列链队列 队列的链式表示和实现队列的链式表示和实现 3.4.3循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现11/6/2022183.2 栈的应用举例栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中的有用工具。为程序设计中的有用工具。3.2.1数制转换数制转换 十进制数十进制数N和其它和其它d进制数的转换是计算机计算进制数的转换是计算机计算的基本问题。的基本问题。11/6/2022193.2 栈的应用举例栈的应用举例 N=(N div d)*d+n

14、 mod d (其中其中:div为整除运算为整除运算,mod为求余运算为求余运算)例如例如(1348)10=(2504)8，其运算过程如下：其运算过程如下：N 1348 168 21 2 N div 8 168 21 2 0 N mod 8 4 0 5 2显示时按从高位到低位的显示时按从高位到低位的顺序输出顺序输出 计算时从低位到高位计算时从低位到高位顺序产生八进制数的各个数位顺序产生八进制数的各个数位11/6/2022203.2 栈的应用举例栈的应用举例void conversion()InitStack(s);/构建空栈构建空栈 scanf(“%d”,N);/输入一个非负十进制整数输入一个

15、非负十进制整数 while(N)/N不等于零，循环不等于零，循环 push(s,N%8);/N/8第一个余数进栈第一个余数进栈 N=N/8;/整除运算整除运算 while(!StackEmpty(s)/输出存放在栈中输出存放在栈中 /的八制数位的八制数位 Pop(s);printf(“%d”,e);/conversion11/6/2022213.2 栈的应用举例栈的应用举例3.2.3 括号匹配的检验括号匹配的检验算法思路：算法思路：1、构建空栈，如左括号则入栈；、构建空栈，如左括号则入栈；2、如右括号，则读栈顶元素。若与其匹配，则出、如右括号，则读栈顶元素。若与其匹配，则出栈；若不匹配，则返回

16、栈；若不匹配，则返回“不匹配不匹配”；3、判定栈是否为空，若栈不空，则返回、判定栈是否为空，若栈不空，则返回“不匹配不匹配”。例例1 ()例例2 ()11/6/2022223.2 栈的应用举例栈的应用举例3.2.3 行编辑程序行编辑程序 一个简单的行编辑程序的功能是：接受用户一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定为允许用户输入出错时可以及时更正。可以约定为退格符，以表示前一个字符无效，退格符，以表示前一个字符无效，为退行符，表为退行符，表示当前行所有字符均无效。示当前

17、行所有字符均无效。例：在终端上用户输入为例：在终端上用户输入为 whli#ilr#e(s#*s)应为应为 while(*s)outchaputchar(*s=#+);putchar(*s+);11/6/2022233.2 栈的应用举例栈的应用举例void lineEdit()/利用字符栈利用字符栈S，从终端接收一行并传送至调用过程的数据区。，从终端接收一行并传送至调用过程的数据区。InitStack(S);ch=getchar();/从终端接收第一个字符从终端接收第一个字符 while(ch!=EOF)/EOF为全文结束符为全文结束符 while(ch!=EOF&ch!=n)switch(ch

18、)case#:Pop(s,c);break;/仅当栈非空时退栈仅当栈非空时退栈 case :ClearStack(s);break;/重置重置S为空为空栈栈11/6/2022243.2 栈的应用举例栈的应用举例 default:Push(S,ch);break;/有效字符进有效字符进 /栈，未考虑栈满情形栈，未考虑栈满情形 ch=getchar();/从终端接收下一个字符从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区将从栈底到栈顶的字符传送至调用过程的数据区;ClearStack(S);/重置重置S为空栈为空栈 if(ch!=EOF）ch=getchar();DestroyS

19、tack(S);11/6/202225第第3章章 栈和队列栈和队列3.1栈栈3.2栈的应用举例栈的应用举例3.4队列队列 3.4.1抽象数据类型队列的定义抽象数据类型队列的定义 3.4.2链队列链队列 队列的链式表示和实现队列的链式表示和实现 3.4.3循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现11/6/2022263.4 队列队列3.4.1抽象数据类型队列的定义抽象数据类型队列的定义一、定义：一、定义：1、队列、队列(queue)是一种先进先出是一种先进先出(FIFO)的线性的线性 表。限定仅能在表头进行删除，表尾进表。限定仅能在表头进行删除，表尾进 行插入。行插入。队列的典型

20、例子有操作系统中的作业排队和顾队列的典型例子有操作系统中的作业排队和顾客服务部门的工作方式等。客服务部门的工作方式等。11/6/2022273.4 队列队列二、队列的抽象数据类型定义二、队列的抽象数据类型定义ADT Queue 数据对象：数据对象：Dai|aiElemSet,i=1,2,.,n,n0 数据关系：数据关系：R1|ai-1,ai D,i=2,.,n 约定其中约定其中a1 端为队列头，端为队列头，an 端为队列尾。端为队列尾。基本操作：基本操作：InitQueue(&Q)操作结果：构造一个空队列操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列初始条件：队列Q

21、已存在。已存在。操作结果：队列操作结果：队列Q被销毁，不再存在。被销毁，不再存在。11/6/2022283.4 队列队列 ClearQueue(&Q)初始条件：队列初始条件：队列Q已存在。已存在。操作结果：将操作结果：将Q清为空队列。清为空队列。QueueEmpty(Q)初始条件：队列初始条件：队列Q已存在。已存在。操作结果：若操作结果：若Q为空队列，则返回为空队列，则返回TRUE，否则返回否则返回FALSE。QueueLength(Q)初始条件：队列初始条件：队列Q已存在。已存在。操作结果：返回操作结果：返回Q的元素个数，即队列的长度。的元素个数，即队列的长度。11/6/2022293.4

22、队列队列 GetHead(Q,&e)初始条件：初始条件：Q为非空队列。为非空队列。操作结果：用操作结果：用e返回返回Q的队头元素。的队头元素。EnQueue(&Q,e)初始条件：队列初始条件：队列Q已存在。已存在。操作结果：插入元素操作结果：插入元素e为为Q的新的队尾元素。的新的队尾元素。DeQueue(&Q,&e)初始条件：初始条件：Q为非空队列。为非空队列。操作结果：删除操作结果：删除Q的队头元素，并用的队头元素，并用e返回其值。返回其值。ADT Queue11/6/2022303.4 队列队列3.4.2 链队列队列的链式表示和实现链队列队列的链式表示和实现一、定义一、定义1、用链表表示的

23、队列。一个链队列需要两个、用链表表示的队列。一个链队列需要两个分别指示队头和队尾的指针。队头在链头，分别指示队头和队尾的指针。队头在链头，队尾在链尾。队尾在链尾。2、链式队列在进队时无队满问题，但有队空、链式队列在进队时无队满问题，但有队空问题。问题。队空条件为队空条件为 front=rear。11/6/2022313.4 队列队列11/6/2022323.4 队列队列二、链队列的二、链队列的C语言定义语言定义typedef struct QNode/结点类型结点类型QElemType data;struct QNode*next;QNode,*QueuePtr;typedef struct/

24、链队列类型链队列类型QueuePtr front;/队头指针队头指针QueuePtr rear;/队尾指针队尾指针LinkQueue;11/6/2022333.4 队列队列11/6/2022343.4 队列队列三、链队列的三、链队列的ADT定义基本操作的算法实现定义基本操作的算法实现1、初始化、初始化Status InitQueue(LinkQueue&Q)/构造一个空队列构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;11/

25、6/2022353.4 队列队列2、销毁、销毁Status Destroyqueue(LinkQueue&Q)/队列队列Q存在则销毁存在则销毁Qwhile(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;11/6/2022363.4 队列队列3、插入、插入Status EnQueue(LinkQueue&Q,QElemType e)/队列队列Q存在存在,插入元素插入元素e为为Q的队尾元素的队尾元素p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-d

26、ata=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;11/6/2022373.4 队列队列4、删除、删除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;11/6/2022383.4 队列队列3.4

27、.3循环队列队列的顺序表示和实现循环队列队列的顺序表示和实现一、定义一、定义 用一组地址连续的存储单元依次存放从队列用一组地址连续的存储单元依次存放从队列头到队列尾的元素，并附设两个指针头到队列尾的元素，并附设两个指针front和和rear分别指示队列头元素和队列尾元素的位置。分别指示队列头元素和队列尾元素的位置。二、顺序队列二、顺序队列循循环队环队列列 P63 图图3.12 图图3.1311/6/2022393.4 队列队列11/6/2022403.4 队列队列三、循环队列的问题和解决方法三、循环队列的问题和解决方法11/6/2022413.4 队列队列队列满和队列空：队列满和队列空：Q.f

28、ront=Q.rear只凭上式，无法判断是队满还是队空。只凭上式，无法判断是队满还是队空。有两种解决方法：有两种解决方法：1）另设一个标志位以区分队空、队满。）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件）少用一个存储单元，队满条件 front=rear+1;本书中算法用本书中算法用2）方法。）方法。11/6/2022423.4 队列队列四、循环队列的四、循环队列的C语言表示语言表示#Define MAXQSIZE 100 /最大队列长度最大队列长度typedef struct QElemType*base;/初始化的动态分配存储空间初始化的动态分配存储空间int front

29、;/头指针，若队列不空，指向头元素头指针，若队列不空，指向头元素int rear;/尾指针，若队列不空，指向队列尾元素尾指针，若队列不空，指向队列尾元素 /的下一个位置的下一个位置SqQueue;11/6/2022433.4 队列队列五、循环队列的基本操作的算法描述五、循环队列的基本操作的算法描述1 1、初始化、初始化Status InitQueue（SqQueue&Q）/构造一个空队列构造一个空队列Q Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);Q.frontQ.rear0;re

30、turn OK;11/6/2022443.4 队列队列2、求队列长度、求队列长度int QueueLength（SqQueue Q）/返回返回Q的元素个数的元素个数，即队列的长度，即队列的长度 return（Q.rearQ.frontMAXQSIZE）MAXQSIZE；11/6/2022453.4 队列队列3、插入、插入Status EnQueue(SqQueue&Q,QElemType e)/插入元素插入元素e为为Q的新的队尾元素的新的队尾元素if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR；/队列满队列满Q.baseQ.rear=e;Q.rear=(Q.

31、rear+1)%MAXQSIZE;return OK;11/6/2022463.4 队列队列4、删除、删除Status DeQueue(SqQueue&Q,QElemType&e)/队列队列Q存在存在,删除删除Q的队头元素，用的队头元素，用e返回返回 /其其值，并返回值，并返回OK；否则返回；否则返回ERRORif(Q.rear=Q.front)return ERROR；/队列空队列空 e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;11/6/202247本章内容复习本章内容复习熟悉栈和队列的逻辑结构定义和特性，并熟悉栈和队列的逻辑

32、结构定义和特性，并在各种问题中灵活使用在各种问题中灵活使用熟练栈在两种存储结构（顺序存储结构和熟练栈在两种存储结构（顺序存储结构和链式存储结构）下的实现方法链式存储结构）下的实现方法熟练队列在两种存储结构（循环队列和链熟练队列在两种存储结构（循环队列和链队列）下的实现方法队列）下的实现方法11/6/202248作业作业1.设将整数设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为若入、出栈次序为Push(1),Pop(),Push(2),Pu

33、sh(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为则出栈的数字序列为 何何(这里这里Push(i)表示表示i进栈，进栈，Pop()表示出栈表示出栈)?(2)能否得到出栈序列能否得到出栈序列1423和和1432?并说明为什么不能并说明为什么不能 得到或者如何得到。得到或者如何得到。(3)请分析请分析 1，2，3，4 的的24种排列中，哪些序列是可种排列中，哪些序列是可 以通过相应的入出栈操作得到的？以通过相应的入出栈操作得到的？11/6/202249作业作业2.试编写算法，在顺序存储结构下实现堆栈的下列运算：试编写算法，在顺序存储结构下实现堆栈的下列运算：（1）i

34、nitstk(s)。初始化操作，建立一个空栈。初始化操作，建立一个空栈s；（2）emptystk(s)。判定栈是否为空；。判定栈是否为空；（3）pushstk(s)。如果栈。如果栈s不满，在栈顶插入不满，在栈顶插入x；（4）popstk(s)。如果栈。如果栈s不空，删除栈顶元素，并返回该元不空，删除栈顶元素，并返回该元素的值；素的值；（5）getstk(s)。如果栈。如果栈s不空，返回栈顶元素。不空，返回栈顶元素。3.试编写算法，实现链队列的下列操作算法：试编写算法，实现链队列的下列操作算法：（1）initlq(q)。初始化操作，建立一个空队。初始化操作，建立一个空队q；（2）emptylq(

35、q)。判定队。判定队q是否为空；是否为空；11/6/202250作业作业 （3）enterlq(q)。进队列；。进队列；（4）deletelq(q)。出队列。出队列。4.分别叙述栈和队列的特点，并指出它们的共同点。分别叙述栈和队列的特点，并指出它们的共同点。5.循环队列的优点是什么？如何判断它的空和满？假循环队列的优点是什么？如何判断它的空和满？假设循环队列只设设循环队列只设rear和和quelen来分别指示队尾元素来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。出队时需返回队头指针。6.讨论限制存取点的表的各种情况，并列举其应用场讨论限制存取点的表的各种情况，并列举其应用场合。合。11/6/202251