您当前的位置:www.7366.com > www.7366.com > www.7366.com
队空前提 : front = rear (初始化时:front = rear ) 队满

发布日期: 2019-09-14     浏览历史次数:

  数据布局课程的内容 1 五 队列P37 ? 队列的定义: 队列(queue)也是一种特殊的线性表。所有插入操做限 定正在一端进行,所有删除操做限制正在另一端进行。 答应进行插入操做的一端称为队尾,答应删除操做 的另一端则称为队首。 它的次要特点是:先辈队的数据元素将先出队。 1. 定义 2. 逻辑布局 3. 存储布局 4. 运算法则 5. 实现体例 2 1. 定 义 只能正在表的一端进行插入运算,正在表的另 一端进行删除运算的线性表 (头删尾插) 取同线性表不异,仍为一对一关系。 挨次队或链队,以轮回挨次队更常见。 2. 逻辑布局 3. 存储布局 4. 运算法则 只能正在队首和队尾运算,且拜候结点时依 照先辈先出(FIFO)的准绳。 5. 实现体例 环节是控制入队和出队操做,具体实现违拗序 队或链队的分歧而分歧。 根基操做有:入队或出队,建空队列,判队空或 队满等操做。 3 队列 (Queue)是仅正在表尾进行插入操做,正在表头进行删除 操做的线性表。 表尾即 an 端,称为 队尾 ; 表头即 a1 端,称为队头。 它是一种先辈先出(FIFO)的线性表。 例如:队列 Q= (a1 , a2 , a3 队头 , ……….,an-1 , an ) 队尾 插入元素称为入队;删除元素称为出队。 ?队列的存储布局为链队或挨次队 (常用轮回挨次队) 4 若是给定一个队列Q:(Data1,Data2,Data3,…,Datan),若是队 列中元素是按a1,a2,a3,…,an的次序进队,如图3-17所示: 则从这个队列中取出所有 元素的出队次序为: 出队 front a1,a2,a3,…,an 。换言之, 队列中元素的进队过 程取出队过程是按 “先辈先出”的法则进 行的,这是队列布局 rear a1 a2 ... an?1 an 图3-17 队列 的主要特征。所以, 入队 队列又称为 先辈先出 FIFO(first_in_first_out)的线挨次队列 所谓挨次队列就是利用挨次存储分派体例暗示的队列。和挨次栈一样,挨次队列也可 以操纵ANSI C言语中的一维数组来实现。别的,正在队列操做过程中,队头元素和 队尾元素将不竭地变更。为确定队头元素和队尾元素的,我们设置两个指 示变量:front和rear。 此中:front用于存放队头的,rear用于存放队尾的。 为描述算法便利起见,设:暗示队列的数组长度为maxsize,正在这里商定如下三点: ① 成立队列时,队列初始(空)形态设置为front=0和rear=0。当front=rear时暗示队列 为空。 ② 正在队列未满的环境下,正在队列中插入一个新的队尾元素后,rear加1, rear老是代 表队尾元素的下一个,即下一个新元素进队的插人。 ③ 正在队列未空的环境下,正在每次删除一个队头元素后,front加1 “上溢”错误:当rear=maxsize-1(队满)时进行入队操做; “下溢”错误:当rear=front(队空)时进行出队操做; 6 typedef struct { elemtype int int queue[maxsize]; front; rear; 挨次队示企图 front queue 0 . . . . . } seqqueue; q a1 a2 rear (队尾.) . a3 a4 7 99 挨次队示企图 会商: Q ① 空队列的特征? 商定:front=rear ② 队列会满吗? 很可能会,由于数组前 端空间无法。因而 数组该当有长度。 front queue 0 . . (队首) . . . a1 a2 a3 a4 rear (队尾.) . 99 ③ 如何实现入队和 出队操做? 入队(尾部插入):queue[rear]=e; rear++; 出队(头部删除):x=queue[front]; front++; 有 缺 陷 假溢 出 8 队列 问:什么叫“假溢出” ?若何处理? 答:正在挨次队中,当尾指针曾经到了数组 的rear=M ,不克不及再有入队操做, 但其实数组中还有空front0 ,这 就叫“假溢出”。 避免“假溢出”问题的两个法子: 1) 一个元素出队后,将整个队列向队头端挪动一个,使队头元素 一直占领第一个数组元素queue[0].换言之,使front老是为0. 2) 将挨次队列想像成为一个环形的空间,即queue[0]接正在queue[M-1] 之后,构成一个闭合的环,从而形成一个轮回队列 采用轮回队列 Circular Queue 9 正在轮回队列中进行出队、入队操做时,头尾指针仍要加1,朝前 挪动。只不外当头尾指针指向数组(maxsize-1)时,其加1 操做的成果是指向数组的下界0。 这种轮回意义下的加1操做能够描述为: if(i+1 == maxsize) i=0; else i++; 操纵模运算可简化为: i=(i+1)%maxsize 明显,由于轮回队列元素的空间能够被操纵,除非数组空 间实的被队列元素全数占用,不然不会上溢。因而,除一 些简单的使用外,实正适用的挨次队列是轮回队列。 10 挨次队列 0 front 1 2 轮回队列(臆制) M-1 0 3 rear . . a1 a2 a3 rear a3 a2 1 a1 2 front M-1 3 新问题:正在轮回队列中,空队特征是front=rear;队满时 也会有front=rear;判决前提将呈现二义性! 处理方案有三: ① 加设标记位,让删除动做使其为1,插入动做使其为0,则可识别当 前front=rear ② 利用一个计数器记实队列中元素个数(即队列长度); ③ 报酬华侈一个单位,令队满特征为front=(rear+1)%M; 11 选用空闲单位法:即front和rear之一指向实元素,另一 指向空闲单位。 队空前提 : front = rear (初始化时:front = rear ) 队满前提: front = (rear+1) % maxsize 队列长度:L=( maxsize +rear-front)% maxsize 1 J2 J3 2 0 front J1 J5 J4 3 问1:左图中队列长度L=? L=5 问2: 正在具有M个单位的 轮回队列中,队满时共有 几多个元素? M-1个 5 rear 4 12 若是商定:轮回队列的初始空形态为front=0和rear=0, 则front= =rear为轮回队列为空的标记, 若是商定入队前,测试尾指针正在轮回意义下加1后能否等 于头指针,若相等则认为队满(留意:rear所指的单 元一直为空),则(rear+1)%maxsize= =front为判断 轮回队列为满的前提。 因为轮回队列是一个首尾相连的环形布局,所以每当正在 轮回队列中插人一个新的队尾元素后,rear加1的操做 为:(rear+1)%maxsize 删除一个队头元素后,front加1的操做为: front=(front+1)%maxsize(相当于以maxsize为模) 13 例1: 一轮回队列如下图所示,若先删除4个元素,接着再 插入4个元素,请问队头和队尾指针别离指向哪个? front front 1 2 J2 J3 J4 J5 front J8 J9 front 0 J1 3 front J7 J6 J5 rear rear 解:由图可知,队头和队尾指针的初态别离为front=0 和rear=5。maxsize=6 删除4个元素后front=4;再插入4个元素后,r=(5+4)%6=3 14 5 4 front 例2 :数组Q[n]用来暗示一个轮回队列,f 为当前队列头元 素的前一,r 为队尾元素的。假定队列中元素的个 数小于n,计较队列中元素的公式为: (A) r-f (B)(n+f-r)% n (C)n+r-f (D) (n+r-f)% n 阐发 : 4种公式哪种合理? 当 r ≥f 时(A)合理; 当 r f 时(C)合理; √ 分析2种环境,以(D) 的表达最为合理 例3:正在一个轮回队列中,若商定队首指针指向队首元素 的前一个。那么,从轮回队列中删除一个元素时,其 操做是 先 挪动队首指针 ,后 取出元素 。 15 ? 七 链队列 用链表暗示的队列称为链队列,如图1.18所示。由 于队列的操做老是正在队头取队尾两头进行的,因 此链队列该当设置两个指针,一个指针指向队列 头,称为队头指针front。一个指针指向列尾, 称为队尾指针rear。别的,为定义计较机算法方 便起见,能够给链队附加一个表头结点,并令队 头指针front指向表头结点,故链队列为空的条 件是front=rear。即队头指针取队尾指针都指向 表头结点。 16 链队列示企图 rear Q front p a1 (队首) a2 a3 ^ (队尾) 会商: ① 空队列的特征? front=rear front rear ^ ② 队列会满吗?一般不会,由于删除时有free动做。除非内存不脚! ③ 如何实现入队和出队操做? 入队(尾部插入):rear-next=S; rear=S; 出队(头部删除):front-next=p-next; 17 问:为什么要设想队列?它有什么奇特用处? 答: 1. 离散事务的模仿(模仿事务发生的先后挨次); 2. 操做系统中多道功课的处置(一个CPU施行多个 功课); 3. 简化法式设想。 18 会商(本章小结) 线性表、栈取队的异同点 不异点: 逻辑布局不异,都是线性的;都能够用挨次存 储或链表存储;栈和队列是两种特殊的线性表,即受 限的线性表(只是对插入、删除运算加以)。 分歧点: ① 运算法则分歧,线性表为随机存取,而栈是只答应 正在一端进行插入和删除运算,因此是后进先出表LIFO; 队列是只答应正在一端进行插入、另一端进行删除运算, 因此是先辈先出表FIFO。 ② 用处分歧,线性表比力通用;仓库用于函数挪用、 递归和简化设想等;队列用于离散事务模仿、多道做 业处置和简化设想等。 19




友情链接:

Copyright 2019-2022 http://www.bjhjpm.com.cn 版权所有 未经协议授权禁止转载