宽度优先搜索.ppt

宽度优先搜索
本节知识要点:
队列及其应用
宽度优先搜索的一般方法
宽度优先搜索的优化方法
队列及其应用

队列是一种线性表型的数据结构,所有的数据在队列中顺次排列。

队列由队列中的各个元素组成。在队列的所有元素中,位于队列最前面的是队头元素,位于队列最后面的是队尾元素。
队头元素
队尾元素
队列可以抽象成如上图所示的形式,每一个方格代表一组数据,都是队列中的一个元素。一般把队头元素用head表示,队尾元素用tail表示。

复习:栈的出入顺序:先进后出
栈可以看成是一个筒,要拿出中间的某个物体(元素出栈)必须先拿出它上面的物体,它上面的物体又一定比它后放进去,因此是先进后出。
队列可以看成是栈去掉栈底形成的部分,因此如果把数据放入队列,它们就全掉出来了……
这样的话只要放进一个数,它就会掉出来,不会有比它后放入的数先被得到。
因此,队列是一个先进先出的序列。先进入队的元素一定先被从队列中正常取出。一般来说,正常的读取队列元素的过程均从队头开始向后依次读取队列中的元素,直到读到队尾元素为止。

(1)入队
元素由队尾进入队列,此时tail值加1,队列的长度加1,新加入的元素存在队列的tail位置。
(2)出队
元素由队头出队列,此时head值加1,队列的长度减少1,这一操作中,队列head位置的元素被取出。
上面两种操作为一般情况下的队列操作过程。一般在程序中用数组q表示队列,在数组q中,head指向的下标和tail指向的下标之间的部分是实际的队列,这中间的元素为队列中真正的元素。
队列的长度为tail-head+1,当这个值为0,即tail>head时,队列为空,里面没有任何元素。
(了解)
一般的队列为线性结构,而循环队列就是把直线型的队列弯成环形的。在循环队列的操作中,当指针指向数组的最后一个空间时,指针所指向的数组下标变为1,即再从q数组的第一个空间继续进行对立操作。循环队列一般在已知程序中出入队列的数据范围时使用,所开的队列数组大小即满足出入操作中入队列和出队列的元素数量的最大值。即若使用循环队列,务必保证队列中的数据不能被覆盖,即当队列中的元素没有出队时,它不能被转回来的入队元素所覆盖。
【例1】小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有 M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过 M−1,软件会将新单词存入一个未使用的内存单元;若内存中已存入 M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。
假设一篇英语文章的长度为 N个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。
输入文件共 2 行。每行中两个数之间用一个空格隔开。第一行为两个正整数 M和 N,代表内存容量和文章的长度。第二行为 N 个非负整数,按照文章的顺序,每个数(大小不超过 1000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。输出文件共1行,包含一个整数,为软件需要查词典的次数。
【输入输出样例 1】

3 7 5
1 2 1 5 4 4 1
【输入输出样例 2】

2 10 6
8 824 11 78 11 78 11 78 8 264
【数据范围】
对于 10%的数据有 M=1,N≤ 5。
对于 100%的数据有 0<M≤ 100,0<N≤ 1000。
分析:
根据题意,题目中主要对内存进行操作。因此可以把内存看作一个队列,按照题目要求模拟操作:
查找:将队列从头到尾扫描一遍
单词进入内存:元素入队
单词从内存中清空:元素出队
当查找不到单词的时候(队列中没有元素符合)时,需要查外存,此时需要计数。
注意清空元素只有在队列为满(元素数量为M)时才会发生,因此在每一次入队操作之前,先计算队列的元素个数。
int main()
{
int m,n,head,tail,ans=0,found;
int a[1001],q[1101];
cin>>m>>n;
for (int i=1;