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

《安全生产责任制考核评分表[1]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列－队列的链式表示和实现3.4.3循环队列－队列的顺序表示和实现8/27/20211第3章栈和队列栈和队列是两种重要的数据结构。从数据元素的逻辑关系看，栈与队列是线性表，但从操作方式与种类看，它们与线性表有许多不同。栈与队列是操作受限的线性表。尽管它们与线性表有许多共同点，但也有不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。8/27/20212第3章栈和队列3.1栈3.2栈的应用举例3.4队列3.4.1抽象数

2、据类型队列的定义3.4.2链队列－队列的链式表示和实现3.4.3循环队列－队列的顺序表示和实现8/27/202133.1栈（Stack）3.1.1抽象数据类型栈的定义一、定义1、栈(Stack)是限定在表尾进行插入或删除操作的线性表。表尾端称栈顶(top)，表头端称栈底(bottom)2、特点：栈的修改是按后进先出(LIFO)的原则进行的。8/27/202143.1栈（Stack）8/27/202153.1栈（Stack）例：设栈的初始状态为空，容量为5。若入栈元素的顺序是1、2、3、4、5，则出栈元素的顺序不可能是【】。A.12345B.34125C.24351D.54

3、3218/27/202163.1栈（Stack）二、栈的抽象数据类型定义ADTStack{数据对象：D＝{ai

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

5、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。8/27/202173.1栈（Stack）ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。StackEmpty(S)初始条件：栈S已存在。

6、操作结果：若栈S为空栈，则返回TRUE，否则FALSE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。8/27/202183.1栈（Stack）GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack8/27/202193.1栈（Stack）3.1.2栈的表示和实现一、顺序栈1、定义：栈的顺序存储结构是利用一组地址连

7、续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。2、初始化空栈时不限定栈的最大容量：先分配一个基本容量，需要时再逐渐扩大STACK_INIT_SIZE;STACKINCREMENT3、设置栈底指针base，始终指向栈底。当base＝NULL，栈不存在当top＝base时，栈空8/27/202110topbasebasetopbasetopbasetopAABCDEAB空栈A进栈EDC出栈BCDE进栈3.1栈（Stack）8/27/2021113.1栈（Stack）二、顺序栈的C语言定义顺序栈的类型定义如下：#defineSTAC

8、K_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//在构造之前和销毁之后base的值是NULLSElemType*top;//栈顶指针intStacksize;//栈的当前可使用的最大容量.}SqStack;8/27/2021123.1栈（Stack）三、顺序栈的应用1、初始化StatusInitStack(SqStack&S){//构造一个空栈SS.base=(SelemType*)malloc(STACK_INIT_SIZE*sizeof(E

9、lemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack8/27/2021133.1栈（Stack）2、读栈顶元素StatusGetTop(SqStackS,SElemType&e){//若栈不空，则用e返回S的栈顶元素，并返回ok;//否则返回ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}//GetTop