28数据结构队列讲解.ppt

队列(queue);队列初始化，置空队列(empty);入队列insert(x);出队列delete(x);溢出;队列的应用;2.从A桶的下端开始,顺次将A桶中的每一个数据按其个位数字的 值放入相应编号的桶中(从桶的上端放入).;3. 将10个桶中的数据按桶编号的顺序(从小到大)由桶的下端再倒 回A桶中.;4. 从桶的下端开始,再将A桶中的每一个数据按其十位数字的值 放入相应编号的桶中(从桶的上端放入).;5.将10个桶中的数据按编号的顺序(从小到大)由桶的下端再倒回A 桶中.此时发现A桶中的数据从下到上已按从小到大顺序排好了.致 此完成对十位数的排序.;【例】集合的前N个元素：编一个程序，按递增次序生成集合M的最小的N个数，M的定义如下： (1)数1属于M； (2)如果X属于M，则Y=2*x+1和Z=3*x+1也属于M； (3)此外再没有别的数属于M。 【分析】 可以用两个队列a和b来存放新产生的数，然后通过比较大小决定是否输出，具体方法如下： (1)令fa和fb分别为队列a和队列b的头指针，它们的尾指针分别为ra和rb。初始时，X=1，fa=fb=ra=rb＝1； (2)将2*x+1和3*x+1分别放入队列a和队列b的队尾，尾指针加1。 即:a[r]←2*x+1，b[r]←3*x+1，r←r+1； (3)将队列a和队列b的头结点进行比较，可能有三种情况： (A)a[fa]b[fb] (B)a[fa]=b[fb] (C)a[fa]b[fb] 将比较的小者赋值X，取出数的队列的头指针相应加1。 (4)重复(2)，(3)直至取出第N项为止。;#includecstdio using namespace std; int a[1001],b[1001],x=1,fa=0,fb=0,ra=0,rb=0,total=1,n,i; main() { scanf(%d,n); while (total=n) { printf(%d ,x); a[ra++]=2*x+1; b[rb++]=3*x+1; if(a[fa]b[fb])x=b[fb++]; else if(a[fa]b[fb])x=a[fa++]; else { x=a[fa++]; fb++; } total++; } return 0; };【例】一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如: 阵列 4 10 0000000067 1000000500 2000000671 0000000089 有4个细胞。;编程计算由＊号所围成的下列图形的面积。面积的计算方法是统计＊号所围成的闭合曲线中水平线和垂直线交点的数目。如图围住了15个点，因此面积为15.;数学模型：二维数组gr[1..n,1..n] Gr[1,1]=0表示该位置是0 gr[2,5]=1表示该位置是＊ Gr[1,1]=2表示该位置是0，并且已经记过数;算法： 1.统计＊号的个数存入变量SUM中. 2.统计封闭曲线外部0的个数，在TAIL中。 3.n*n-sum-tail得到结果。;算法： 1.统计＊号的个数存入变量SUM中. 2.统计封闭曲线外部0的个数，在TAIL中。 2-1 从（1，1）点开始，找所有与它相邻的0，计数，标计为2，入队 2-2 出队（x,y）,从（x,y）点开始，找所有与它相邻的0，计数，标计为2，入队。 2-3 如果队为空则结束，否则转2-2 3.n*n-sum-tail得到结果。;1161 银行取款 1222 机器翻译 1159 细胞数字 1160 图形的面积