pascal-第11讲-队列及应用

数据结构之队列王桐林寿光现代中学2009.8潍坊市2009信息学奥林匹克夏令营数据结构知识简单回顾数据结构（datastructure）是相互之间存在一种或多种特定关系的数据元素的集合。是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。

数据结构的内涵“操作”的对象：数据。数据与数据间的关系。针对数据的基本操作。数据结构的形式定义

data_structure=(D,S)D:数据元素的有限集；S:Ｄ上关系的有限集；逻辑结构图例数据元素间的关系结构名特性数据元素属于或不属于集合集合结构松散；用其他结构代替数据元素一个对一个线性结构结构简单数据元素一个对多个树形结构结构复杂数据元素多个对多个图结构结构复杂物理结构

1、顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中相邻。

——数组2、链式结构：借助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中不一定相邻。——指针（动态存储）逻辑结构、物理结构密切相关算法的设计取决于所选定的逻辑结构，算法的实现依赖于所采用的存储结构。线性表由n个数据元素的有限序列除头元素外，每个元素都有一个前趋除尾元素外，每个元素都有一个后继ABCD栈栈（堆栈）是一种受限的线性表。其所有的插入和删除操作均限定在线性表的一端进行，允许插入和删除的一端称为栈顶(表尾)，不允许插入和删除的一端称为栈底(表头)。栈又称为后进先出(LastInFirstOut，简称LIFO)表。栈与栈的顺序存储栈S顺序存储栈的实现（一）Constm=栈表目数的上限；Typestack=array[1..m]ofstype；{栈类型}Vars：stack；{栈}top：integer；{栈顶指针}

栈的实现（二）constm=栈表目数的上限；

typestack=recordelem:array[1..m]ofelemtp;top:0..m;{栈顶指针}end;Vars：stack；{栈}栈的基本操作初始化（init）、进栈（push）、出栈（pop）、读取栈顶元素（top）、判断栈是否为空或已满。。栈的典型应用表达式求值括号区配队列在日常生活中的排队现象：购物、订票、打饭、候车排队所遵循的原则是“先来先服务”，后来者总是加到队尾，排头者总是先离开队伍。队列就是从日常生活中的排队现象抽象出来的。队列的定义队列也是一种受限的线性表。它的所有插入都在队列的一端进行，所有删除都在另一端进行。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。队列的插入和删除我们称为入队和出队，新元素入队就成为新的队尾元素，删除元素后，其后继元素成为新的队首元素。

队列是一种先进先出(FIFO)的线性表front>=rear，则队列空;front<rear，则队列非空。队列的存储队列可以采用顺序存储结构和链式存储结构我们一般采用顺序存储结构来定义队列

——数组abcdrf空1、队列的顺序存储（1）借助记录类型来定义：constmaxn=xxxx;//队列的最大长度typequeue=record

data:array[1..maxn]ofqtype;//qtype表示队列元素的数据类型

front,rear:1..maxn//队首指针和队尾指针

end;varq:queue;（2）实际编程中可以直接定义成如下格式：constmaxn=xxxx;//队列的最大长度var

q:array[1..maxn]ofqtype;//队列front,rear:1..maxn;//队首指针和队尾指针2、队列的链式存储同栈一样，队列也可以采用链式存储。队列的基本操作初始化入队出队1、队列的初始化或置空将队首指针和队尾指针皆置为0。

proceduresetnull；front:=0;rear:=0end；fr

0123……2、入队add(x)，也称为进队首先判断队列q是否已满，若未满，则后移队尾指针，并在队列的尾端插入元素x。

procedureadd(x:qtype)；

beginifrear=maxnthenwriteln('queuefull!');haltend//队满

elsebeginrear:=rear+1；//后移队尾指针q[rear]:=x；//插入元素xend；

end；Arf3、出队del首先判断队列q是否已空，若未空，则后移队首指针，并取出队列q的队首元素。

functiondel；

beginiffront=rearthenwriteln('queueempty!');haltend//队空

elsebeginfront:=front+1;//后移队首指针del:=q[front]；//取出队首元素

end;end；bcdfr如果仅完成删除操作，则只需要后移队首指针（front:=front+1）即可。小练习①已知队列(13，2，11，34，41，77，5，7，18，26，15)，第一个进入队列的元素是13，则第五个出队列的元素是（

）。(NOIP9)A）5

B）41

C）77

D）13

E）18

小练习②设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该为（）。(NOIP8)A）2B）3C）4D）5溢出什么是溢出？假溢出由于队列只能在一端插入，在另一端删除，因此随着入队及出队运算的不断进行，就会出现一种有别于栈的情形：队列在数组中不断地向队尾方向移动，而在队首的前面产生一片不能利用的空闲存储区，最后会导致当尾指针指向数组最后一个位置（即r=max）而不能再加入元素时，存储空间的前部却有一片存储区无端浪费，这种现象称为“假溢出”。克服假溢出的方法有两种一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到max地址后，下一个地址就“翻转”为１。在结构上采用这种技巧来存储的队列称为循环队列。循环队列队列的应用例7-3细胞个数【试题描述】一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。【输入】整数m,n（第一行）m<50,n<80；矩阵(m行，n列)。【输出】细胞的个数。【样例输入】410

0234500067

1034560500

2045600671

0000000089【样例输出】40234500067

1034560500

2045600671

0000000089共4个细胞算法步骤：1、从文件中读入m*n矩阵，将其转换为0、1矩阵存入pic数组中；1表示细胞，0表示无细胞

2、沿pic数组矩阵从上到下，从左到右，找到遇到的第一个细胞；将细胞的位置入队h，并沿其上、下、左、右四个方向上搜索，如果遇到细胞(pic[I,j]=1)则将其位置入队，入队后的位置pic[I,j]数组置为0；

3、将h队的队头出队，沿其上、下、左、右四个方向上搜索，如果遇到细胞则将其位置入队，入队后的位置pic数组置为0；

4、重复3，直至h队空为止，则此时找出了一个细胞；

5、重复2，直至矩阵找不到细胞；

6、输出找到的细胞数。参考程序constdx:array[1..4]of-1..1=(-1,0,1,0);//横坐标:左，下，右，上dy:array[1..4]of-1..1=(0,1,0,-1);//纵坐标:左，下，右，上vars:string;a:array[1..50,1..80]of0..1;//存储矩阵的数组，0:无细胞；1：有细胞

m,n,i,j,num:integer;h:array[1..4000,1..2]ofbyte;//队列：存细胞的坐标，1：行；2：列proceduretry(p,q:integer);//处理坐标（p,q）的细胞

vari,t,w,x,y:integer;begininc(num);//细胞数量加1a[p,q]:=0;t:=1;//队头

w:=1;//队尾

h[1,1]:=p;h[1,2]:=q;//遇到的第一个细胞入队

repeatfori:=1to4do//沿细胞的上下左右四个方向搜索细胞

beginx:=h[t,1]+dx[i];y:=h[t,2]+dy[i];if(x>0)and(x<=m)and(y>0)and(y<=n)and(a[x,y]=1)thenbegininc(w);h[w,1]:=x;h[w,2]:=y;a[x,y]:=0;end;//为细胞的入队

end;inc(t);//队头指针加1，出队

untilt>w;//直至队空为止

end;beginfillchar(a,sizeof(a),0);//初始化数组

fillchar(h,sizeof(h),0);//初始化队列

num:=0;readln(m,n);fori:=1tomdo//读入矩阵

beginreadln(s);forj:=1tondoifs[j]='0'thena[i,j]:=0elsea[i,j]:=1;end;fori:=1tomdoforj:=1tondoifa[i,j]=1thentry(i,j);//在矩阵中寻找细胞

writeln(num);//输出细胞个数end.广度优先搜索算法（bfs）1、适合的题目类型：

1）、求从给定初始状态到目标状态最少需要的步数。

2）、给定初始状态，经过k步后能够到达哪些状态。2、利用的数据结构：队列。3、状态的最大值：决定队列的大小（非常重要）4、队列里需要记住哪些状态：一般使用记录数据类型。5、状态的转移：不能遗漏。6、状态的判重：避免重复进入队列。从初始结点开始，应用算符生成第一层结点，检查目标结点是否在其中出现，若没有，再用算符将第一层结点逐一扩展，得第二层结点，逐一检查第二层中是否包含目标结点。若没有，依次扩展、检查……直到发现目标结点为止。这就是所谓的广度优先搜索。abcdefjk用队列的数据结构来存储搜索过程中产生的结点，取队头元素扩展，产生的结点插入队尾。Bfs的基本框架：初始化；建立数据库（队列）；初始状态进入队列；f=0;队列的首指针；r=1;队列的尾指针(开始时指向初始状态)；q[1];初始结点;While（f<r）do{还有未扩展的结点，队列不空}BeginInc（f）；{移动队列的首指针：出队列}

记录f状态；

Fori=1tomethoddo{按规则扩展下一层新的子结点}Begin

生成新的结点;If新结点是目标结点then输出目标，搜索结束；

If新结点是以前没出现过then保存新结点(入队)；

EndEnd；【问题描述：】在n*n的棋盘上有一匹马在第x行第y列的格子上。棋盘上有些格子上有障碍物，马不能达到有障碍物的格子。已知马在棋盘中的走法按“日“字8个方向可走，如下图所示：问：哪些格子能到达，到达这些格子的最小步数是多少。【输入：】第一行:n（n<=100）,x,y

(马的开始位置)。接下来n行为棋盘的描述：“-“为空格子，”+“表示该格子有障碍物。【输出：】n行，每行n个用空格隔开的数，表示马到达该格子的最少步数，如果无法到达则用-1表示。2、马的遍历422----------+-----【样例输入：】4321303223-111214【样例输出：】０

const

dx:array[1..8]ofinteger=(-1,-2,-2,-1,1,2,2,1);dy:array[1..8]ofinteger=(2,1,-1,-2,-2,-1,1,2);varcan:array[-1..maxn+2,-1..maxn+2]ofboolean;//加边界，方便判断是否出界

dist:array[1..maxn,1..maxn]ofinteger;//记录最少步数

n,i,j,x0,y0:integer;procedureinit;//输入vars:string;beginreadln(n,x0,y0);fillchar(can,sizeof(can),false);//初始化fori:=1tondobeginreadln(s);forj:=1tondocan[i,j]:=s[j]='-';end;end;procedurebfs;//广度优先搜索

varq:array[1..maxn*m