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

《安全生产责任制考核评分表[1]》由会员分享，可在线阅读，更多相关《安全生产责任制考核评分表[1]（51页珍藏版）》请在金锄头文库上搜索。

1、第第3章章 栈和队列栈和队列3.1栈栈 3.1.1抽象数据类型栈的定义抽象数据类型栈的定义 3.1.2栈的表示和实现栈的表示和实现3.2栈的应用举例栈的应用举例3.4队列队列 3.4.1抽象数据类型队列的定义抽象数据类型队列的定义 3.4.2链队列链队列 队列的链式表示和实现队列的链式表示和实现 3.4.3循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现构术周郭荒跺年吱聂贝熔妻拜虎德断允工隙菇武擒成置求昔疾哨挞泳镜续安全生产责任制考核评分表1安全生产责任制考核评分表17/21/20241第第3章章 栈和队列栈和队列栈和队列是两种重要的数据结构。栈和队列是两种重要的数据结构。从数据元素的

2、逻辑关系看，栈与队列是线从数据元素的逻辑关系看，栈与队列是线性表，但从操作方式与种类看，它们与线性表，但从操作方式与种类看，它们与线性表有许多不同。性表有许多不同。栈与队列是操作受限的线性表。栈与队列是操作受限的线性表。尽管它们与线性表有许多共同点，但也有尽管它们与线性表有许多共同点，但也有不少特殊性。本章重点介绍这些特殊性，不少特殊性。本章重点介绍这些特殊性，并给出一些典型的应用实例。并给出一些典型的应用实例。膏楔砒己慑迈宾浦琐粮羌峰雄借谨衷赃燎润修窍棺顽请量墒险谨锚圾扔斟安全生产责任制考核评分表1安全生产责任制考核评分表17/21/20242第第3章章 栈和队列栈和队列3.1栈栈3.2栈的

3、应用举例栈的应用举例3.4队列队列 3.4.1抽象数据类型队列的定义抽象数据类型队列的定义 3.4.2链队列链队列 队列的链式表示和实现队列的链式表示和实现 3.4.3循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现浴鲸稼诈千衬犬矩宅糟家绢姚诣蛹省分勤孩斟虫畅介保邯皱剐侥视腹桶讣安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202433.1 栈（栈（Stack）3.1.1抽象数据类型栈的定义抽象数据类型栈的定义一、定义一、定义1、栈、栈( Stack )是限定在表尾进行插入或删除操是限定在表尾进行插入或删除操 作的线性表。表尾端称栈顶作的线性表。表尾端称栈顶(top)

4、，表头端，表头端 称栈底称栈底(bottom)2、特点：栈的修改是按后进先出、特点：栈的修改是按后进先出(LIFO)的原的原 则进行的。则进行的。霄琢茂朱酬诗糙抓币饥谎瘟叫昭弱堡蒲巷未技绢浸拥殷吹莹个凉递饼故烦安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202443.1 栈（栈（Stack）柬祭在微务帛内拴材谨刺貉轴完疗疟哪节狸诗牛莽盔娠硅仅答柴齐镜引敲安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202453.1 栈（栈（Stack）例：设栈的初始状态为空，容量为例：设栈的初始状态为空，容量为5。若入栈元。若入栈元素的顺序是素的顺序是1、2、3、4、5，则出

5、栈元素的，则出栈元素的顺序不可能是【顺序不可能是【 】。】。A. 12345 B. 34125 C. 24351 D. 54321衣栏偷辆奸午剖舀咆冗披迄捻沏工蔼匈稍尽俞腻老屎书谍奎蠢孵咸亡输不安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202463.1 栈（栈（Stack）二、栈的抽象数据类型定义二、栈的抽象数据类型定义ADT Stack 数据对象：数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系：R1 | ai-1, aiD, i=2,.,n 约定约定an 端为栈顶，端为栈顶，a1 端为栈底。端为栈底。 基本操作：基本操作：

6、InitStack(&S) 操作结果：构造一个空栈操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：栈操作结果：栈S被销毁。被销毁。蛙庞携硷福侍惰芦丧琅包修秤双犊缠僧焊死产豫页狐衬辐讲表疯阳潞虏属安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202473.1 栈（栈（Stack） ClearStack(&S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：将操作结果：将S清为空栈。清为空栈。 StackEmpty(S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：若栈操作结果：若栈S为空栈，则返

7、回为空栈，则返回TRUE，否，否 则则FALSE。 StackLength(S) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：返回操作结果：返回S的元素个数，即栈的长度。的元素个数，即栈的长度。皱眩拇两炙满蹿阔辆辗最禹中狸屿缅奎敢掸欲磨缸蕉纱昧询喝垣癣病陷辣安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202483.1 栈（栈（Stack） GetTop(S, &e) 初始条件：栈初始条件：栈S已存在且非空。已存在且非空。 操作结果：用操作结果：用e返回返回S的栈顶元素。的栈顶元素。 Push(&S, e) 初始条件：栈初始条件：栈S已存在。已存在。 操作结果：插入元

8、素操作结果：插入元素e为新的栈顶元素。为新的栈顶元素。 Pop(&S, &e) 初始条件：栈初始条件：栈S已存在且非空。已存在且非空。 操作结果：删除操作结果：删除S的栈顶元素，并用的栈顶元素，并用e返回其值。返回其值。 ADT Stack宙飘矿茁咙网煽落业挥挚命搏态最否去融市雄舅袒它滦怕抵爵杠贺郴恶空安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202493.1 栈（栈（Stack）3.1.2栈的表示和实现栈的表示和实现一、顺序栈一、顺序栈1、定义：栈的顺序存储结构是利用一组地址连续的存、定义：栈的顺序存储结构是利用一组地址连续的存 储单元依次存放自栈底到栈顶的数据元素，同时

9、附储单元依次存放自栈底到栈顶的数据元素，同时附 设指针设指针top指示栈顶元素在顺序栈中的位置。指示栈顶元素在顺序栈中的位置。2、初始化空栈时不限定栈的最大容量：先分配一个基初始化空栈时不限定栈的最大容量：先分配一个基 本容量，需要时再逐渐扩大本容量，需要时再逐渐扩大STACK_INIT_SIZE; STACKINCREMENT3、 设置栈底指针设置栈底指针base，始终指向栈底。，始终指向栈底。 当当baseNULL，栈不存在，栈不存在 当当topbase时，栈空时，栈空萧假舔绷类缎瘸哗食禽挖缅腰鲸酪列舶秒蜀相茧夺外宝箕牲绘巡孔捂柠镇安全生产责任制考核评分表1安全生产责任制考核评分表17/2

10、1/202410toptopbasebasebasebasetoptopbasebasetoptopbasebasetoptopA AA AB BC CD DE EA AB B空栈空栈 A进栈进栈E D C 出栈出栈 B C D E 进栈进栈3.1 栈（栈（Stack）皋潦讼领丽进领爱占先酝估骄括偿独医搂贺眷祁泼栗妥勤卸费昼廓磁沉搪安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024113.1 栈（栈（Stack）二、顺序栈的二、顺序栈的C语言定义语言定义顺序栈的类型定义如下：顺序栈的类型定义如下：#define STACK_INIT_SIZE 100 /存储空间初始分配量存

11、储空间初始分配量#define STACKINCREMENT 10; /存储空间分配增量存储空间分配增量 typedef struct SElemType *base;/在构造之前和销毁之后在构造之前和销毁之后base的值是的值是NULL SElemType *top; /栈顶指针栈顶指针 int Stacksize; /栈的当前可使用的最大容量栈的当前可使用的最大容量.SqStack;汀伯进恿札穴则丈祁梦郭读戒石命潭创善奄罐退汲属颜多泄叶挫忆雄诲淫安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024123.1 栈（栈（Stack）三、顺序栈的应用三、顺序栈的应用1、初始化、

12、初始化 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 痕肘褂赛丘坞生怂萤组短觉搭奴羡尽锹榨原架拆省戮鄂甭筒挺响功乔滋饵安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024133.1 栈（栈（Stack）2

13、、读栈顶元素、读栈顶元素Status GetTop(SqStack S,SElemType &e) /若栈不空，则用若栈不空，则用e返回返回S的栈顶元素，并返回的栈顶元素，并返回ok; /否则返回否则返回ERROR if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTop络富败溺温途厦岭瘦成硬河片旭碰勺梳配呆移妖琅继绑身瘟梨臣眠条堰蛤安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024143.1 栈（栈（Stack）3、插入元素、插入元素Status Push(SqStack &S,SElemType e)

14、 /插入元素插入元素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； /Push贪瑟雁碎相弱象公戴稿督而确故伏瓢卧水婿兵谍棋挡内临霄料

15、糖颁呢梅庆安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024153.1 栈（栈（Stack）4、删除、删除Status Pop(SqStack &S,SElemType &e) /若栈不空，则删除若栈不空，则删除S的栈顶元素，用的栈顶元素，用e返回返回 /其值其值,并返回并返回OK；否则返回；否则返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK; /Pop 瓷刀法淮蛹潜蜕锨哇自忿秃押氮浪卖胯茹被缆钾悲佑手冤荫海伤腆盔粘仙安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024163.1 栈（

16、栈（Stack）四、链栈四、链栈 栈的链式存储结构栈的链式存储结构称为链栈。它是运算称为链栈。它是运算受限的单链表，是线受限的单链表，是线性链表的特例。插入性链表的特例。插入和删除操作仅限制在和删除操作仅限制在表头位置上进行。表头位置上进行。data next sa an-1a a1 1a an栈顶栈顶栈底栈底雁宵楔臼杠贺茸窘侵肪琴陕蛋氨游阔馅疾外勿倘授亭循末侥拔讯采演吵棋安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202417第第3章章 栈和队列栈和队列3.1栈栈3.2栈的应用举例栈的应用举例3.4队列队列 3.4.1抽象数据类型队列的定义抽象数据类型队列的定义 3.4.2

17、链队列链队列 队列的链式表示和实现队列的链式表示和实现 3.4.3循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现括筏盆荐凡戎凉茅帮年槛梧沟皱相昨烹使洽孟夕皮隅张箔忽噬滋佳峡匈葱安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024183.2 栈的应用举例栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中的有用工具。为程序设计中的有用工具。3.2.1数制转换数制转换 十进制数十进制数N和其它和其它d进制数的转换是计算机计算进制数的转换是计算机计算的基本问题。的基本问题。赴小罕契欣前症泉俭熟丹尘惟淳椰我银控癸

18、铱攀漆余沪墟汲喷潜参拱哺贬安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024193.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显示时按从高位到低位的显示时按从高位到低位的顺序输出顺序输出 计算时从低位到高位计算时从低位到高位顺序产生八进制数的各个数位顺序产生八进制数的各个数位嘲亡岁贺徽惰午撰裙截企

19、砧央秆侵隧狙瓣私兆秧夹蚤痕峪卞喝按庚馋棋奏安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024203.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); prin

20、tf(“%d”,e); /conversion僻迹龋蚁袄汇虑联效矛现艾降溺倾夯矿错竟岭翌凡买踢伯峻西印脖似默咏安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024213.2 栈的应用举例栈的应用举例3.2.3 括号匹配的检验括号匹配的检验算法思路：算法思路：1、构建空栈，如左括号则入栈；、构建空栈，如左括号则入栈；2、如右括号，则读栈顶元素。若与其匹配，则出、如右括号，则读栈顶元素。若与其匹配，则出栈；若不匹配，则返回栈；若不匹配，则返回“不匹配不匹配”；3、判定栈是否为空，若栈不空，则返回、判定栈是否为空，若栈不空，则返回“不匹配不匹配”。例例1 ( ) 例例2 ( ) 猖

21、钾慧淘赦裹卷饰酿怂交磐转统牵荤蒸赐片渴理睛索晒某愚潦蛛嘛缺乙仲安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024223.2 栈的应用举例栈的应用举例3.2.3 行编辑程序行编辑程序 一个简单的行编辑程序的功能是：接受用户一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定为允许用户输入出错时可以及时更正。可以约定为退格符，以表示前一个字符无效，退格符，以表示前一个字符无效，为退行符，表为退行符，表示当前行所有字符均无效。示当前行所有字符均无效。 例：在终端上用户

22、输入为例：在终端上用户输入为 whli#ilr#e(s#*s) 应为应为 while(*s) outchaputchar(*s=#+); putchar(*s+); 牢蓖瞬张酶毖酝惜挛逝弟嘉绽奏某启溢刹盈评盒凡朗摇庇膛抑玛墩怕返踊安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024233.2 栈的应用举例栈的应用举例void lineEdit( ) /利用字符栈利用字符栈S，从终端接收一行并传送至调用过程的数据区。，从终端接收一行并传送至调用过程的数据区。 InitStack(S); ch=getchar( ); /从终端接收第一个字符从终端接收第一个字符 while(ch!

23、=EOF)/EOF为全文结束符为全文结束符 while(ch!=EOF & ch!=n) switch(ch) case # : Pop(s,c);break; / 仅当栈非空时退栈仅当栈非空时退栈 case : ClearStack(s);break;/ 重置重置S为空为空栈栈水拾汹肪岳帝廉参漫庶帽被或笨却丹甚暮香飞脚乱琉剑莽映捧闲磁欲球啼安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024243.2 栈的应用举例栈的应用举例 default : Push(S,ch); break;/ 有效字符进有效字符进 /栈，未考虑栈满情形栈，未考虑栈满情形 ch=getchar( )

24、; / 从终端接收下一个字符从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区将从栈底到栈顶的字符传送至调用过程的数据区; ClearStack(S); / 重置重置S为空栈为空栈 if(ch!=EOF） ch=getchar( ); DestroyStack(S); 珐籽伸嚏蟹瑟滔焉拧言贱面逮灯械椅绥铰译苦井烤横羡盘磷鞍蓝枪淋示召安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202425第第3章章 栈和队列栈和队列3.1栈栈3.2栈的应用举例栈的应用举例3.4队列队列 3.4.1抽象数据类型队列的定义抽象数据类型队列的定义 3.4.2链队列链队列 队列的链式表示

25、和实现队列的链式表示和实现 3.4.3循环队列循环队列队列的顺序表示和实现队列的顺序表示和实现搞鞭嵌宁舰追挎衔徽枢困韩胁乍拱吮芝巡毯蓄裙戚龄醋探狈帐钞柳哑皇尾安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024263.4 队列队列3.4.1抽象数据类型队列的定义抽象数据类型队列的定义一、定义：一、定义：1、队列、队列(queue)是一种先进先出是一种先进先出(FIFO)的线性的线性 表。限定仅能在表头进行删除，表尾进表。限定仅能在表头进行删除，表尾进 行插入。行插入。队列的典型例子有操作系统中的作业排队和顾队列的典型例子有操作系统中的作业排队和顾客服务部门的工作方式等。客服务

26、部门的工作方式等。刊历滴奇劝钒遣氯敢衙虾卵浆钨剧哎戈斋猴莽俞竹指是稀镰轮蝎缩龋厅狂安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024273.4 队列队列二、队列的抽象数据类型定义二、队列的抽象数据类型定义ADT Queue 数据对象：数据对象：Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系：R1 | ai-1, ai D, i=2,.,n 约定其中约定其中a1 端为队列头，端为队列头，an 端为队列尾。端为队列尾。 基本操作：基本操作： InitQueue(&Q) 操作结果：构造一个空队列操作结果：构造一个空队列Q。 DestroyQueu

27、e(&Q) 初始条件：队列初始条件：队列Q已存在。已存在。 操作结果：队列操作结果：队列Q被销毁，不再存在。被销毁，不再存在。诞针郝睹碴锚假弄铝辛剪禽组烂顾仅吉田获妒姚赤炽些拘颇钉殴凭惺针蒂安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024283.4 队列队列 ClearQueue(&Q) 初始条件：队列初始条件：队列Q已存在。已存在。 操作结果：将操作结果：将Q清为空队列。清为空队列。 QueueEmpty(Q) 初始条件：队列初始条件：队列Q已存在。已存在。 操作结果：若操作结果：若Q为空队列，则返回为空队列，则返回TRUE， 否则返回否则返回FALSE。 QueueL

28、ength(Q) 初始条件：队列初始条件：队列Q已存在。已存在。 操作结果：返回操作结果：返回Q的元素个数，即队列的长度。的元素个数，即队列的长度。林铣鱼汹访霉絮藕袄板欲秃剖积变摩晕挂在份所缝呕罗卧霖锨涛岩伤另峭安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024293.4 队列队列 GetHead(Q, &e) 初始条件：初始条件：Q为非空队列。为非空队列。 操作结果：用操作结果：用e返回返回Q的队头元素。的队头元素。 EnQueue(&Q, e) 初始条件：队列初始条件：队列Q已存在。已存在。 操作结果：插入元素操作结果：插入元素e为为Q的新的队尾元素。的新的队尾元素。

29、DeQueue(&Q, &e) 初始条件：初始条件：Q为非空队列。为非空队列。 操作结果：删除操作结果：删除Q的队头元素，并用的队头元素，并用e返回其值。返回其值。 ADT Queue疑娇盛酒得丙矽袒棕赶瑚谎乡棠租阁句斋窄卒伐燎挎挑辛蚂迁幅额碰箭榔安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024303.4 队列队列3.4.2 链队列队列的链式表示和实现链队列队列的链式表示和实现一、定义一、定义1、用链表表示的队列。一个链队列需要两个、用链表表示的队列。一个链队列需要两个分别指示队头和队尾的指针。队头在链头，分别指示队头和队尾的指针。队头在链头，队尾在链尾。队尾在链尾。2、

30、链式队列在进队时无队满问题，但有队空、链式队列在进队时无队满问题，但有队空问题。问题。 队空条件为队空条件为 front = rear。懂去鬃今商级买单表栖磺换宁脂迁脸丧憾掂硬百董吸没诵蚁狸寸铱摹实赫安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024313.4 队列队列俭尸户始潭开妆担蝉胚曹厕纪避浪乖连涡谎疟长阁曼幽柿饵流会玄许挨痈安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024323.4 队列队列二、链队列的二、链队列的C语言定义语言定义typedef struct QNode/结点类型结点类型QElemType data;struct QNode

31、*next;QNode,*QueuePtr;typedef struct/链队列类型链队列类型QueuePtr front;/队头指针队头指针QueuePtr rear;/队尾指针队尾指针LinkQueue;艾侨弱悦耘舌巩脑泥哩根橡匝卷遏抨节摧喀赎切牵凳腻悬命喜鲸界末农袱安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024333.4 队列队列嘴黍累陀韭牵莱噶沁枝缓逞楔袒随顶尔于饥证熔醛胶嘿贤嘎差咒彤绷蕴眼安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024343.4 队列队列三、链队列的三、链队列的ADT定义基本操作的算法实现定义基本操作的算法实现1、初始化

32、、初始化Status InitQueue(LinkQueue &Q) /构造一个空队列构造一个空队列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;return OK;疡桔斌匪稗免剧送拜安空篆氦架谱剐辉方臭锁悉脂宿套保初常杉掖峻圃匀安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024353.4 队列队列2、销毁、销毁Status Destroyqueue(LinkQueue &Q) /队列队列Q存在则销毁存在则销毁Qwhile(Q.front

33、)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return OK;例宽瞧楷炸柯求临间且睦梁贼留拟靖翟啼乎拜甥帧苫厅舞署置渊骗葬窒雀安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024363.4 队列队列3、插入、插入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

34、-next=p;Q.rear=p; return OK;坍工跺缴跳釉咳邵吠磋毖昏邵董捉水俱幌侧肖栏丹媚汰没奈筐复姨涝频僚安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024373.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;fr

35、ee(p); return OK;圭愤淡蒲狮疥靖还寓赦械窝猫韶汗鲁戌襄筏琢烃薪蒙掩懂日擎疲纵鼎命骨安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024383.4 队列队列3.4.3循环队列队列的顺序表示和实现循环队列队列的顺序表示和实现一、定义一、定义 用一组地址连续的存储单元依次存放从队列用一组地址连续的存储单元依次存放从队列头到队列尾的元素，并附设两个指针头到队列尾的元素，并附设两个指针front和和rear分别指示队列头元素和队列尾元素的位置。分别指示队列头元素和队列尾元素的位置。二、顺序队列二、顺序队列循循环队环队列列 P63 图图3.12 图图3.13犬鬃猎掺昂钻客

36、唉海垃肾圈烽涡银益吻肆碌钝叉啪捂尚诗型偏吴坯拎现癌安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024393.4 队列队列赣姨假弊跳逻散墩歇枚撵拙氨爷鬃喘稀屿侩徊凛僧炯插滋蓬众雌圃庐腕醛安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024403.4 队列队列三、循环队列的问题和解决方法三、循环队列的问题和解决方法栏猖线趣译蝉拷际蹈宴灯奋升杏舷研淌孕受烃拈辱豺级三旁毯帧彩眷咬好安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024413.4 队列队列队列满和队列空：队列满和队列空：Q.front=Q.rear只凭上式，无法判断是队满还是队空。只

37、凭上式，无法判断是队满还是队空。有两种解决方法：有两种解决方法：1）另设一个标志位以区分队空、队满。）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件）少用一个存储单元，队满条件 front=rear+1; 本书中算法用本书中算法用2）方法。）方法。终幅侩窝鸟孤先情首造只鲜闽炼击凳母闲四杨涪膀百罐易岛邓泪湘挛居官安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024423.4 队列队列四、循环队列的四、循环队列的C语言表示语言表示#Define MAXQSIZE 100 /最大队列长度最大队列长度typedef struct QElemType *base; /初

38、始化的动态分配存储空间初始化的动态分配存储空间int front; /头指针，若队列不空，指向头元素头指针，若队列不空，指向头元素int rear; /尾指针，若队列不空，指向队列尾元素尾指针，若队列不空，指向队列尾元素 /的下一个位置的下一个位置SqQueue;天延骚臣酮曲忽荔穗俱向户血往月锣先档吴半灭钮宜硫钾兄兑叙拈艘疆灸安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024433.4 队列队列五、循环队列的基本操作的算法描述五、循环队列的基本操作的算法描述1 1、初始化、初始化Status InitQueue（SqQueue &Q） /构造一个空队列构造一个空队列Q Q.

39、base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);Q.frontQ.rear0;return OK;肾讹纬袋呜根礁放黍瓤契墓燃獭跋亮庐利毁超妙献简母平椅磨焰况竿锚只安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024443.4 队列队列2、求队列长度、求队列长度int QueueLength（SqQueue Q） /返回返回Q的元素个数的元素个数 ，即队列的长度，即队列的长度 return （ Q.rearQ.frontMAXQSIZE ） MAXQSIZE ；雕鲁逊揣涡彦

40、带砧贤零生讶监泼寇膳已撂烤揽冯挞釜商咨恕使沙饱野舒谁安全生产责任制考核评分表1安全生产责任制考核评分表17/21/2024453.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.rear+1) %MAXQSIZE; return OK;宜邑猛就搏酿轨傅豹盔哲拓曳晾练仕簇惰攻窒炒赵碗侄艳抵界范毯坦玻帮安全生产责任制考核评分表1安全生产

41、责任制考核评分表17/21/2024463.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;娄洼商座吊焰吮穴怀碾穿绰盔丙姐力帆翅簿悄虱了运旁儡嘴哦堂峙逛立噬安全生产责任制考核评分表1安全生产责任制考核评分表1

42、7/21/202447本章内容复习本章内容复习熟悉栈和队列的逻辑结构定义和特性，并熟悉栈和队列的逻辑结构定义和特性，并在各种问题中灵活使用在各种问题中灵活使用熟练栈在两种存储结构（顺序存储结构和熟练栈在两种存储结构（顺序存储结构和链式存储结构）下的实现方法链式存储结构）下的实现方法熟练队列在两种存储结构（循环队列和链熟练队列在两种存储结构（循环队列和链队列）下的实现方法队列）下的实现方法陵谱嘲胞拳袋兽龙课陪拓披垮袜柴者隆碍欲鹿娶蛊寸碳战靳满恬关仿亮娱安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202448作业作业1. 设将整数设将整数1，2，3，4依次进栈，但只要出栈时栈非空

43、，则可依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为则出栈的数字序列为 何何(这里这里Push(i)表示表示i进栈，进栈，Pop( )表示出栈表示出栈)? (2) 能否得到出栈序列能否得到出栈序列1423和和1432?并说明为什么不能并说明为什么不能 得到或者如何得到。得到或者如何得到。 (3)请分析请分析 1，2 ，3 ，4 的的24

44、种排列中，哪些序列是可种排列中，哪些序列是可 以通过相应的入出栈操作得到的？以通过相应的入出栈操作得到的？诽妮示鄙凹充经逸吧烷摹费集泳潍泄刺篙恭邵滚员引毛驮健拳共糊较伶述安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202449作业作业2. 试编写算法，在顺序存储结构下实现堆栈的下列运算：试编写算法，在顺序存储结构下实现堆栈的下列运算： （1）initstk(s)。初始化操作，建立一个空栈。初始化操作，建立一个空栈s； （2）emptystk(s)。判定栈是否为空；。判定栈是否为空； （3）pushstk(s)。如果栈。如果栈s不满，在栈顶插入不满，在栈顶插入x； （4）pop

45、stk(s)。如果栈。如果栈s不空，删除栈顶元素，并返回该元不空，删除栈顶元素，并返回该元素的值；素的值； （5）getstk(s)。如果栈。如果栈s不空，返回栈顶元素。不空，返回栈顶元素。3. 试编写算法，实现链队列的下列操作算法：试编写算法，实现链队列的下列操作算法： （1）initlq(q)。初始化操作，建立一个空队。初始化操作，建立一个空队q； （2）emptylq(q)。判定队。判定队q是否为空；是否为空；芯虞得盯薪向讹咒喘废辰侗游桂蒋琳闭溅廊融夹斑蟹瑰擎壁双靶点洼淳溯安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202450作业作业 （3）enterlq(q)。进队

46、列；。进队列； （4）deletelq(q)。出队列。出队列。4. 分别叙述栈和队列的特点，并指出它们的共同点。分别叙述栈和队列的特点，并指出它们的共同点。5. 循环队列的优点是什么？如何判断它的空和满？假循环队列的优点是什么？如何判断它的空和满？假设循环队列只设设循环队列只设rear和和quelen来分别指示队尾元素来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队和出队算法，要求的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头指针。出队时需返回队头指针。6. 讨论限制存取点的表的各种情况，并列举其应用场讨论限制存取点的表的各种情况，并列举其应用场合。合。曳奄悯监抛蹲恍具寡嘿答银棚遭墅谩涯凶垒光谅倡丈篙京蕾波泞爵策鬃爸安全生产责任制考核评分表1安全生产责任制考核评分表17/21/202451