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

2019/6/20,1,第3章 栈和队列,3.1栈 3.1.1抽象数据类型栈的定义 3.1.2栈的表示和实现 3.2栈的应用举例 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列 队列的链式表示和实现 3.4.3循环队列队列的顺序表示和实现,2019/6/20,2,第3章 栈和队列,栈和队列是两种重要的数据结构。 从数据元素的逻辑关系看，栈与队列是线性表，但从操作方式与种类看，它们与线性表有许多不同。 栈与队列是操作受限的线性表。 尽管它们与线性表有许多共同点，但也有不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。,2019/6/20,3,第3章 栈和队列,3.1栈 3.2栈的应用举例 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列 队列的链式表示和实现 3.4.3循环队列队列的顺序表示和实现,2019/6/20,4,3.1 栈（Stack）,3.1.1抽象数据类型栈的定义 一、定义 1、栈( Stack )是限定在表尾进行插入或删除操 作的线性表。表尾端称栈顶(top) ，表头端 称栈底(bottom) 2、特点：栈的修改是按后进先出(LIFO)的原 则进行的。,2019/6/20,5,3.1 栈（Stack）,2019/6/20,6,3.1 栈（Stack）,例：设栈的初始状态为空，容量为5。若入栈元素的顺序是1、2、3、4、5，则出栈元素的顺序不可能是【 】。 A. 12345 B. 34125 C. 24351 D. 54321,2019/6/20,7,3.1 栈（Stack）,二、栈的抽象数据类型定义 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被销毁。,2019/6/20,8,3.1 栈（Stack）,ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否 则FALSE。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。,2019/6/20,9,3.1 栈（Stack）,GetTop(S, &e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(&S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(&S, &e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 ADT Stack,2019/6/20,3.1 栈（Stack）,3.1.2栈的表示和实现 一、顺序栈 1、定义：栈的顺序存储结构是利用一组地址连续的存 储单元依次存放自栈底到栈顶的数据元素，同时附 设指针top指示栈顶元素在顺序栈中的位置。 2、初始化空栈时不限定栈的最大容量：先分配一个基 本容量，需要时再逐渐扩大 STACK_INIT_SIZE; STACKINCREMENT 3、 设置栈底指针base，始终指向栈底。 当baseNULL，栈不存在 当topbase时，栈空,2019/6/20,11,空栈,A进栈,E D C 出栈,B C D E 进栈,3.1 栈（Stack）,2019/6/20,12,3.1 栈（Stack）,二、顺序栈的C语言定义 顺序栈的类型定义如下： #define STACK_INIT_SIZE 100 /存储空间初始分配量 #define STACKINCREMENT 10; /存储空间分配增量 typedef struct SElemType *base;/在构造之前和销毁之后base的值是NULL SElemType *top; /栈顶指针 int Stacksize; /栈的当前可使用的最大容量. SqStack;,2019/6/20,13,3.1 栈（Stack）,三、顺序栈的应用 1、初始化 Status InitStack(SqStack /InitStack,2019/6/20,14,3.1 栈（Stack）,2、读栈顶元素 Status GetTop(SqStack S,SElemType /GetTop,2019/6/20,15,3.1 栈（Stack）,3、插入元素 Status Push(SqStack return OK； /Push,2019/6/20,16,3.1 栈（Stack）,4、删除 Status Pop(SqStack /Pop,2019/6/20,17,3.1 栈（Stack）,四、链栈 栈的链式存储结构 称为链栈。它是运算 受限的单链表，是线 性链表的特例。插入 和删除操作仅限制在 表头位置上进行。,栈顶,栈底,2019/6/20,18,第3章 栈和队列,3.1栈 3.2栈的应用举例 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列 队列的链式表示和实现 3.4.3循环队列队列的顺序表示和实现,2019/6/20,19,3.2 栈的应用举例,由于栈结构具有的后进先出的固有特性，致使栈成 为程序设计中的有用工具。 3.2.1数制转换 十进制数N和其它d进制数的转换是计算机计算的基本问题。,2019/6/20,20,3.2 栈的应用举例,N=(N div d)*d+n 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,显示时按从高位到低位的 顺序输出,计算时从低位到高位 顺序产生八进制数的各个数位,2019/6/20,21,3.2 栈的应用举例,void 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); /conversion,2019/6/20,22,3.2 栈的应用举例,3.2.3 括号匹配的检验 算法思路： 1、构建空栈，如左括号则入栈； 2、如右括号，则读栈顶元素。若与其匹配，则出栈；若不匹配，则返回“不匹配”； 3、判定栈是否为空，若栈不空，则返回“不匹配”。 例1 ( ) 例2 ( ),2019/6/20,23,3.2 栈的应用举例,3.2.3 行编辑程序 一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定为退格符，以表示前一个字符无效，为退行符，表示当前行所有字符均无效。 例：在终端上用户输入为 whli#ilr#e(s#*s) 应为 while(*s) outchaputchar(*s=#+); putchar(*s+);,2019/6/20,24,3.2 栈的应用举例,void lineEdit( ) /利用字符栈S，从终端接收一行并传送至调用过程的数据区。 InitStack(S); ch=getchar( ); /从终端接收第一个字符 while(ch!=EOF)/EOF为全文结束符 while(ch!=EOF / 重置S为空栈,2019/6/20,25,3.2 栈的应用举例,default : Push(S,ch); break;/ 有效字符进 /栈，未考虑栈满情形 ch=getchar( ); / 从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区; ClearStack(S); / 重置S为空栈 if(ch!=EOF） ch=getchar( ); DestroyStack(S);,2019/6/20,26,第3章 栈和队列,3.1栈 3.2栈的应用举例 3.4队列 3.4.1抽象数据类型队列的定义 3.4.2链队列 队列的链式表示和实现 3.4.3循环队列队列的顺序表示和实现,2019/6/20,27,3.4 队列,3.4.1抽象数据类型队列的定义 一、定义： 1、队列(queue)是一种先进先出(FIFO)的线性 表。限定仅能在表头进行删除，表尾进 行插入。 队列的典型例子有操作系统中的作业排队和顾 客服务部门的工作方式等。,2019/6/20,28,3.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已存在。 操作结果：队列Q被销毁，不再存在。,2019/6/20,29,3.4 队列,ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE， 否则返回FALSE。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。,2019/6/20,30,3.4 队列,GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。 EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。 ADT Queue,2019/6/20,31,3.4 队列,3.4.2 链队列队列的链式表示和实现 一、定义 1、用链表表示的队列。一个链队列需要两个分别指示队头和队尾的指针。队头在链头，队尾在链尾。 2、链式队列在进队时无队满问题，但有队空问题。 队空条件为 front = rear。,2019/6/20,32,3.4 队列,2019/6/20,33,3.4 队列,二、链队列的C语言定义 typedef struct QNode/结点类型 QElemType data; struct QNode *next; QNode,*QueuePtr; typedef struct/链队列类型 QueuePtr front;/队头指针 QueuePtr rear;/队尾指针 LinkQueue;,2019/6/20,34,3.4 队列,2019/6/20,35,3.4 队列,三、链队列的ADT定义基本操作的算法实现 1、初始化 Status InitQueue(LinkQueue ,2019/6/20,36,3.4 队列,2、销毁 Status Destroyqueue(LinkQueue ,2019/6/20,37,3.4 队列,3、插入 Status EnQueue(LinkQueue ,2019/6/20,38,3.4 队列,4、删除 Status DeQueue(LinkQueue ,2019/6/20,39,3.4 队列,3.4.3循环队列队列的顺序表示和实现 一、定义 用一组地址连续的存储单元依次存放从队列头到队列尾的元素，并附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。 二、顺序队列循环队列 P63 图3.12 图3.13,2019/6/20,40,3.4 队列,2019/6/20,41,3.4 队列,三、循环队列的问题和解决方法,2019/6/20,42,3.4 队列,队列满和队列空：Q.front=Q.rear 只凭上式，无法判断是队满还是队空。 有两种解决方法： 1）另设一个标志位以区分队空、队满。 2）少用一个存储单元，队满条件 front=rear+1; 本书中算法用2）方法。,2019/6/20,43,3.4 队列,四、循环队列的C语言表示 #Define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; /初始化的动态分配存储空间 int front; /头指针，若队列不空，指向头元素 int rear; /尾指针，若队列不空，指向队列尾元素 /的下一个位置 SqQueue;,2019/6/20,44,3.4 队列,五、循环队列的基本操作的算法描述 1、初始化 Status InitQueue（SqQueue ,2019/6/20,45,3.4 队列,2、求队列长度 int QueueLength（SqQueue Q） /返回Q的元素个数 ，即队列的长度 return （ Q.rearQ.frontMAXQSIZE ） MAXQSIZE ； ,2019/6/20,46,3.4 队列,3、插入 Status EnQueue(SqQueue ,2019/6/20,47,3.4 队列,4、删除 Status DeQueue(SqQueue ,2019/6/20,48,本章内容复习,熟悉栈和队列的逻辑结构定义和特性，并在各种问题中灵活使用 熟练栈在两种存储结构（顺序存储结构和链式存储结构）下的实现方法 熟练队列在两种存储结构（循环队列和链队列）下的实现方法,2019/6/20,49,作业,1. 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3