资源描述
第13讲:数据结构之队列,中缀表达式求值(zhong.pas)中缀表达式转换为后缀表达式(change.pas),一、概念,在一端进行插入（进队列），在另一端进行删除（出队列）的线性表。插入的一端称为队尾：closed;（指向队尾，最后一个元素）删除的一端称为队首：open(习惯指向队首的前一位置，空的位置),open,closed,队列数组a下标：1234567,队列空：open=closed;非空：openclosed,1、,定义：ConstmaxVarq:array1.maxofdatatype;open,closed:integer;,2、队列的基本运算队列的运算主要有两种：入队：procedureadd(x);出队：functiondel,1）、过程ADD(x)在队列q的尾端插入元素xprocedureADD(x：qtyper)；begin后移队尾指针并插入元素xclosed:=closed+1；qclosed：=x；end；ADD,2）、函数DEL取出q队列的队首元素functionDEL；beginopen:=open+1;del:=qopen；end；DEL,重要的用途：bfs（广度优先搜索算法）,【竞赛试题】已知队列（13，2，11，34，41，77，5，7，18，26，15），第一个进入队列的元素是13，则第五个出队列的元素是（）。(NOIP9)A）5B）41C）77D）13E）18设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5，e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该为（）。(NOIP8)A）2B）3C）4D）5,二、队列的应用,1、合并石子【问题描述：】小Ray在河边玩耍，无意中发现一些很漂亮的石子堆，于是他决定把这些石子搬回家。河滩上共有n堆石子，小Ray在把石子搬回家之前首先要把这n堆石子合并为一堆石子。已知小Ray每次可以选择其中的两堆石子合并为一堆，合并一次石子他要消耗的体力是两堆石子的数量和。请计算小Ray把n堆石子合并成一堆最少消耗的体力值是多少。【输入：】第一行：n（=30000）.第二行：那个用空格隔开的数，分别表示n堆石子的数量（每堆10000）。【输出：】n堆石子合并成一堆所消耗的最小体力值。说明:分别用队列和堆两种算法实现。【样例输入：】3124【样例输出：】10,opena:=1;openb:=1;closedb:=0;ans:=0;fori:=1ton-1dobeginsum:=aopena+aopena+1;f:=1;ifaopena+bopenbsumthenbeginsum:=aopena+bopenb;f:=2;end;ifbopenb+bopenb+1sumthenbeginsum:=bopenb+bopenb+1;f:=3;end;inc(closedb);bclosedb:=sum;inc(ans,sum);casefof1:inc(opena,2);2:begininc(opena);inc(openb);end;3:inc(openb,2);end;end;,算法：,将石子从小到大排序放入数组a；数组b，一次存放合并后的石子，同样是递增的的？,将石子从小到大排序放入数组a；,N=300001、快速排序算法。2、桶排序算法。,readln(n);fori:=1tondobeginread(k);inc(tk);end;k:=0;fori:=1to30000doforj:=1totidobegininc(k);ak:=i;end;an+1:=maxlongintdiv2;an+2:=maxlongintdiv2;fori:=1ton+2doti:=maxlongintdiv2;,【问题描述：】在n*n的棋盘上有一匹马在第x行第y列的格子上。棋盘上有些格子上有障碍物，马不能达到有障碍物的格子。已知马在棋盘中的走法按“日“字8个方向可走，如下图所示：,问：哪些格子能到达，到达这些格子的最小步数是多少。【输入：】第一行:n（n=100）,x,y(马的开始位置)。接下来n行为棋盘的描述：“-“为空格子，”+“表示该格子有障碍物。【输出：】n行，每行n个用空格隔开的数，表示马到达该格子的最少步数，如果无法到达则用-1表示。,2、马的遍历,422-+-,【样例输入：】,4321303223-111214,【样例输出：】,dx:array1.8ofinteger=(-1,-2,-2,-1,1,2,2,1);dy:array1.8ofinteger=(2,1,-1,-2,-2,-1,1,2);varcan:array-1.maxn+2,-1.maxn+2ofboolean;/加边界，方便判断是否出界dist:array1.maxn,1.maxnofinteger;/记录最少步数n,i,j,x0,y0:integer;procedureinit;vars:string;beginreadln(n,x0,y0);fillchar(can,sizeof(can),false);fori:=1tondobeginreadln(s);forj:=1tondocani,j:=sj=-;end;end;,procedurebfs;/广度优先搜索varq:array1.maxn*maxn,1.2ofinteger;open,closed,k,x,y,xx,yy:integer;beginfori:=1tondoforj:=1tondodisti,j:=-1;open:=0;closed:=1;distx0,y0:=0;q1,1:=x0;q1,2:=y0;whileopen=2),3）、交换：Tem=stemsp:=si;temsp+1:=si+1;temi:=0;temi+1:=0;,？,5、判重：fori=1tocloseddoifa1.str=tem最简单、最直接的判重方法。缺点：效率低，时间慢。,4、翻硬币（coin.pas）问题描述有N个硬币正面朝上排成一排（N=6），每次将5个硬币翻过来放在原位置，直到最后全部硬币翻成反面朝上为止。编程找出最少步数输入只有一个整数N（=5-i)then(m-i+5-i:正面朝上的个数)beginifm-i+5-i=0thenprint(step);正面朝上的个数为0时结束ifnot(bm-i+5-i)thenbegininc(closed);进队列bm-i+5-i:=true;aclosed.num:=m-i+5-i;正面朝上的个数aclosed.depth:=step;翻的次数end;end;end;end;,可以看出：除了6和8是特例外，其他满足：1）if(nmod5=0)thens=ndiv52)if(nmod5=1)or(nmod5=3)thens=ndiv5+13)if(nmod5=2)or(nmod5=4)thens=ndiv5+2或者：Ifnmod5=0thens=ndiv5Elses=ndiv5+(nmod5-1)mod2+1,设有一个N*N方格的迷宫，入口和出口分别在左上角和右上角。迷宫格子中分别放有0和1，0表示可通，1表示不能，迷宫走的规则如下图所示：即从某点开始，有八个方向可走，前进方格中数字为0时表示可通过，为1时表示不可通过，要另找路径。输入例子：（从文件中读取数据）80001101010110110010010010011010101000110011111010011101111000000入口：（1，1）；出口：（1，8）输出要求：最少步数，找出一条从入口（左上角）到出口（又上角）的路径(不能重复)。8(11)(22)(33)(34)(45)(36)(37)(28)(18),5、迷宫问题mg.pas,求最少步数:类似跳马问题。,typenode=recordrow,col:integer;depth:integer;end;Varq:array0.maxn*maxnofnode;/队列can:array0.maxn+1,0.maxn+1ofboolean;/边界；判重,procedurebfs;vark,x,y,xx,yy,step:integer;beginopen:=0;closed:=1;can1,1:=false;q1.row:=1;q1.col:=1;q1.depth:=0;whileopencloseddobegininc(open);x:=qopen.row;y:=qopen.col;step:=qopen.depth+1;fork:=1to8dobeginxx:=x+dxk;yy:=y+dyk;ifcanxx,yythenif(xx=1)and(yy=n)thenprint(step)elsebegincanxx,yy:=false;inc(closed);qclosed.row:=xx;qclosed.col:=yy;qclosed.depth:=step;end;end;end;print(-1);end;,Bfs：输出方案：,proceduredfs(i:integer);beginifqi.father0thendfs(qi.father);write(,qi.row,qi.col,);end;procedureprint(ans:integer);varj:integer;beginassign(output,fout);rewrite(output);ifans=-1thenwriteln(noanswer)elsebeginwriteln(ans);dfs(open);write(,1,n,);end;close(output);halt;end;,typenode=recordrow,col:integer;depth:integer;father:integer;end;,
展开阅读全文