数据关系上的构造策略.ppt

1、数据关系上的构造策略,上海市控江中学 xxx,数据结构回顾,“数据结构算法程序”数据结构是相互之间存在一种或多种特定关系的数据元素的集合。对确定的问题选择一种合适的数据结构，加上设计一种好的算法，就是所谓的程序设计。,数据的逻辑结构,定义：用数学方法来描述问题中所涉及的操作对象及对象之间的关系，将操作对象抽象为数据元素，将对象之间的复杂关系用数学语言描述出来。 重要性：设计数学模型的基础是确定数据的逻辑结构，而算法又是用来解决数学模型的。要使得算法效率高，必须提高数据的逻辑结构中信息的利用效果。 基本的逻辑结构： 、集合集合中的数据元素之间只有“同属于一个集合”的关系 、线性结构“一对一”的关

2、系 、树形结构一对多”的关系 、图状（网状）结构“多对多”的关系。,数据的存储结构,如何实现对各个对象的操作，即各对象之间的关系在计算机中如何表示。数据的存储结构影响算法的效率。线性存储结构分 、顺序存储结构 、链式存储结构 非线性存储结构一般也是通过线性的存储方式存入计算机的（例如图的相邻矩阵和邻接表） ；,选择数据的逻辑结构的基本原则,在某些复杂的问题中，数据之间的关系相当复杂，可选用的逻辑结构可能不止一种。但选用哪种逻辑结构，直接影响算法效率。一般来讲，选择合理逻辑结构应充分考虑的两个因素 充分利用“可直接使用”的信息 不记录“无用”信息,选择逻辑结构的因素1： 充分利用“可直接使用”的

3、信息,“信息” 指的是元素与元素之间的关系。一般分为 “可直接使用”：只需直接拿来即可。 “不可直接使用”：可通过某些间接的方式，使之成为可以使用的信息，但其中转化的过程需要花费一定的时间。 由此可见，我们所需要的是尽量多的“可直接使用”的信息。这样的信息越多，算法的效率就会越高。,圆桌问题,圆桌上围坐着个人。其中个人是好人，另外个人是坏人。如果从第一个人开始数数，数到第个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第个人处死依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死个人之后，圆桌上围坐的剩余的个人全是好人。 输入：好人和坏人的人数n

4、（n32767）、步长m（m 32767 ）； 输出：2个大写字母，G表示好人，B表示坏人，50个字母为一行，不允许出现空白字符和空行。,例如n=5、m=3时，依次列出“处死5人”的操作：,该题实际上是在一个长度为2*n的圆排列上，以m为间隔进行n次出队操作。,普通解法线性表“查找”法,、用顺序存储结构实现。即使用数组记录当前圆排列中每个元素的初始位置，初始值为12n。可根据前一个出队元素的位置（即数组下标）直接定位，找到下一个出队元素的位置，然后删去，并将它后面的元素全部前移一次。,优点:“找点”时，可以由现在出队元素的位置直接计算并在数组中精确定位； 缺点:“去点”时都需要把它后面所有的元

5、素整体移动一次。“去点”时的元素移动就是信息由“不可直接使用”向“可直接使用”的转化过程，其时间复杂度为O(n)。由于出队元素有n个，因此程序的整体时间复杂度是O(n2)。,、用链式存储结构实现,用链表记录当前圆排列中每个元素的初始位置，初始值为1.2n。每出队一个元素后，只要将这个元素直接从链表中删去即可，然后指针后移(m-1)次，找到下一个出队元素。 n=5,m=3的初始链表,依次列出了“处死5人”的操作（为当前出队元素的链表位置）,优点：“去点”时只要修改应该被删除顶点的父指针的指向就可以了，毋需移动元素； 缺点：“找点”时需要移动(m-1)次定位指针； 所以应用链式存储结构，程序的整体

6、时间复杂度是O(nm)。,改进解法“直接定位法”,从哲学角度分析，“找点”和“去点”是存在于程序和数据结构中的一对矛盾： 应用顺序存储结构时，“找点”效率高而“去点”效率低； 应用链式存储结构时，“去点”效率高而“找点”效率低; 这都是由数据结构本身决定的，不会随人的主观意志存在或消失。这就表明“找点”和“去点”的时间复杂度不会同时降为O(1)。我们希望有这样一种数据结构，在实现“找点”和“去点”时，使复杂度降到尽量低。,总体思想：在较好地实现“直接定位”的基础上，尽量避免大量元素移动,Group段数； Amount段中现有元素个数。随程序运行，段内出队元素右方的元素左移，amount值不断减

7、小。,var n,m,i,j,k,l,p,g:longint; /*好人和坏人的人数为n，步长值为m，上次出列元素的段内位移为p，当前出列元素位于其右方第k个位置，即段内位移为k+p*/ t,amount:array 1.65535 of longint; /* 分段式数组为amount，其中第i段中的元素数为amounti，t为当前排列*/ ans:array1.65535of boolean; /*排列方案,其中ansi为第i个元素的出列标志*/ readln(n,m); /*读好人和坏人的人数n和步长值m*/ fillchar(amount,sizeof(amount),0); /*各段

8、为空*/ g1; /*从第1段开始构建分段式数组*/ for i1 to n+n do tii;inc(amountg); /*设置第i个位置序号，累计第g段的元素数*/ if amountg=m then inc(g) ;/*若第g段满，则新增一个段*/ j1;p0; /*起始段和段内位移初始化*/ fillchar(ans,sizeof(ans),false);/*初始时全“好人”*/,for i1 to n do /*依次出列n个元素*/ km; /*计算第i个出列元素所在的段号j和段内位移k+p*/ while k+pamountjdo kk+p-amountj;j(j mod g)+

9、1;p0 ;/*while */ anst(j-1)*m+k+ptrue; /*第(j-1)*m+k+p个元素作为“坏人”出列*/ for l(j-1)*m+k+p to(j-1)*m+amountj-1 do tltl+1; /*第j段k+p位置右方所有元素依次左移一个位置*/ pk+p-1; /*记下当前段的位移*/ amountjamountj-1 /*第j段的元素数-1*/ ;/*for*/ for i1 to n+n do /*输出排列方案*/ if ansi /*出队的是“坏人”，留下的是“好人”*/ then write(B) else write(G); if (i mod 5

10、0=0)and(in*2)then writeln/*50个数组成一行*/ /*for*/ .main,“直接定位法”较好的体现出“直接定位”的思想，而且由于将所有的顶点分为若干段之后，每次删除一个顶点后，需要移动的顶点数相对而言不是很多，这样就使程序效率大大提高，且m越大，这种效果越明显。 顺序存储结构在“去点”的问题上需要数据移动； 链式存储结构在“找点”的问题上需要指针移动， 因此线性表中的信息属于“不可直接使用”的信息。 分段式数组结合了链式存储结构与顺序存储结构，兼具了这两种存储结构的优点，将“不可直接使用”的信息转化成了“可直接使用”的信息，算法效率的提高自然在情理之中。,选择逻辑

11、结构的因素2： 不记录“无用”信息,一般情况下，数据结构愈复杂，可包含的信息量愈大。但并不意味着我们一定要使用复杂的数据结构。在某些时候，复杂的数据结构中容易混杂冗余信息。 数据结构内含的信息多自然是好事，但倘若其中“无用”（不需要）的信息太多，就只会增加我们思考分析和处理问题时的复杂程度，,寻找子串,从由01串构成的文件中，找出长度介于A和B之间出现次数最多的N个不同频率的子串，子串可以相互覆盖，输出结果必须按子串出现频率的降序排列，频率相同的子串按长度降序排列，频率和长度均相同的子串则按其对应数值降序排列。其中0AB12，0N20，输入文件可达到2MB。 输入：第1行为a b n，表明子串

12、的长度范围为a，b和不同频率的子串数n；从第2行开始为由01串构成的文件，以2为结束标志； 输出：n行，其中第i行的行首为第i大的频率，接下来按照长度递减、长度相同的子串按其对应数值递减的顺序给出该频率的子串，子串与子串之间用空格隔开。,完成以下两步操作,找出n个满足条件（长度介于A和B之间且出现次数最多）的子串，并统计各子串出现的频率； 把所有不同子串按降序要求（频率为第一关键字、长度为第二关键字、对应数值为第三关键字且降序）输出。 所有的子串及其频率的存储方式有两种 、采用二叉树结构 、采用矩阵结构,、采用二叉树结构,最上的为根顶点，定义每个顶点的左枝为0右枝为1，这样一个子串可以与这棵二

13、叉树中的一条路径一一对应,树中的每个点赋予一定的权值，表示该点对应的子串在文件中出现的频率，那么我们可以得到一些累加规律，例如当A=1，B=3时，某个中间状态对应的二叉树,假设现在读到一个串为“011”，其中以“0”开头且长度为1到3的子串有三个：“0”、“01”、“011”，统计时应将这三个子串的频率加1，这个操作相当于在对应的01路径上将各顶点的频率加1,鉴于对应二叉树的顶点很少（最大为213-18191），完全可以多次遍历，不难从中找出前N个频率最大的子串，然后按从大到小的顺序输出。,统计所有子串的频率,1、先构造一棵深度为b的空二叉树； 2、以第b位为尾，分别将长度为b、b-1、1，的

14、子串送入二叉树，统计出各子串的频率； 3、以第b+1位为尾，重复上述过程； 直至左移至串尾为止。,数据结构,const inputfile=contact.in;outfile= contact.out; /*输入文件名和输出文件名*/ tc:array1.13of integer=(1,2,4,8,16,32,64,128,256,512,1024,2048,4096);/*tci=2i-1*/ tz:array0.1 of byte=(0,1); /*字符转数值*/ type point=node; /*二叉树的指针类型*/ node=record /*顶点类型*/ l,r:point;

15、/* 左右指针(分别对应字符0和1*/ num:longint; /*权值,即顶点对应子串的频率*/ end; ar=string12; /*子串的类型*/ var t:array1.21 of longint; /*不同频率按降序要求排列成t*/ tch:array1.1024 of char; /*缓冲区*/ tree:point; /*二叉树的根*/ inf,outf:text; /*输入文件名和输出文件名*/ a,b,n,long,now,which,where:byte; /*长度范围为a,b,子串数为n, 当前子串长度为long,t序列的长度为now, 待查子串的长度为where，

16、频率的大小顺序为which*/ yu,m:integer; /* 二进制子串对应的十进制数为m，模为yu（=2b+1，使其长度不超过b）*/,输入数据，建立空树,proc maketree(floor:byte;var ppoint); /*从floor层出发,生成以p为根的空树*/ p.num0; /*权值为0*/ if floor=b /*若已生成b层,则左右指针均为空;否则扩展出左右儿子*/ then p.lnil;p.rnil /*then*/ else new(p.l);maketree(floor+1,p.l); new(p.r);maketree(floor+1,p.r) ;/*

17、else*/ ;/* maketree */ proc init; /* 输入信息，生成空树*/ readln(inf,a,b,n); /*输入子串的长度范围和不同频率的子串个数*/ new(tree); maketree(0,tree); /*生成以tree为根的空树*/ ;/* init*/,读入数据，建立二叉树,proc add(floor:byte;var p：point); /*以floor层的p顶点为根d的子树，每个顶点的权值+1*/ inc(p.num); /*p的权值+1*/ if floorlong /*若层数未超出子串长度*/ then if (m and tclong-f

18、loor)=0) /*若m的第long-floor个二进制位为0,则递归左子树;否则递归右子树*/ then add(floor+1,p.l) else add(floor+1,p.r); ;/* add */,读入数据，计算各子串频率,proc make; var ch:char; /*读入字符*/ i:byte; /*循环变量*/ long0; m0; /*子串的有效长度和初始值为零,*/ yutcb+1; /*子串对应数值必须模2b,使其长度不超过b*/ repeat read(inf,ch); /*读入字符*/ if ch=2 /*若文件已读完,则处理长度不足b的余串,回溯*/ the

19、n for ilong downto 1 do add(0,tree);dec(long) ;/*for*/ exit ;/*then*/ m(m*2+tzch) mod yu; /*生成当前有效子串*/ inc(long); /* 子串长度+1*/ if long=b /*若长度为b,则各顶点权值+1, 有效长度-1*/ thenadd(0,tree);dec(long); until false; ;/*make*/,从floor层的p顶点出发,计算子串频率降序的排列t,proc find(floor：byte;p：point); var i,j:byte; /*循环变量*/ if flo

20、or=a /*若层数不低于下限,则将p的权值插入t序列的合适位置;否则分别递归左右子树*/ thenjnow; /*从t的now位置出发,左寻p权值的插入位置j+1*/ while (j0) and (tjp.num)/*p权值应插入t位置后*/ then if nown then inc(now); /*t的长度+1*/ for inow-1 downto j+1 do ti+1ti; /*t中j+1位置开始的后缀右移一个位置, p权值插入空出的j+1位置*/ tj+1p.num;/*then*/ if floorb then find(floor+1,p.l);find(floor+1,p

21、.r) ; /*若层数小于上限,则分别递归左右子树*/ ;/*then*/ /*then*/ else find(floor+1,p.l);find(floor+1,p.r) ;/*else*/ ;/* find */,从floor层的p顶点(对应字串为ss)出发,输出长度为where、权值为twhich的所有子串,proc look_up(floor:byte;p：point;ss:ar); /*从floor层的p顶点(对应字串为ss)出发,输出长度为where、权值为twhich的所有子串*/ if(floor=where)and(p.num=twhich) /*若p顶点的层次和权值满足子

22、串的长度和频率要求，则输出*/ then write(outf, ,ss); if (floor=twhich) /*相同频率、相同长度的子串按其对应数值降序输出，即按照先右后左的顺序递归子树*/ then look_up(floor+1,p.r,ss+1); look_up(floor+1,p.l,ss+0) ;/*then*/ ;/* look_up */,按要求输出结果,proc print; now0;fillchar(t,sizeof(t),0); /*t序列初始化为空*/ find(0,tree); /*计算频率降序的t序列*/ assign(outf,outfile);rewri

23、te(outf); /*输出文件写准备*/ settextbuf(outf,tch); /*设置缓冲区*/ for which1 to n do /*按照降序枚举频率顺序*/ write(outf,twhich); /*输出第which大的频率*/ for whereb downto a do /*按照长度降序的要求枚举具有该频率的子串*/ look_up(1,tree.r,1); /*按照先右后左的顺序递归状态树，使得相同频率和长度的子串按照对应数值递减的顺序输出*/ look_up(1,tree.l,0) ; writeln(outf); /*换行*/ ;/*for*/ close(out

24、f); /*关闭输出文件*/ ;/* print */,主程序, assign(inf,inputfile);reset(inf);/*输入文件读准备*/ settextbuf(inf,tch); /*设置缓冲区*/ init; /* 输入信息，生成空树*/ make; /*依次读入数据，计算各子串的频率*/ close(inf); /*关闭输入文件*/ print; /*按要求输出结果*/ ./*main*/, “一对多”的关系有利于处理好数据； 规律性强。如果新代顶点与子代顶点之间的关系建立得好，那么就可以把庞大的元素安排得井井有条，按照一定的顺序逐层深入，解决当前元素的处理。 可操作性强

25、。在解题中只要建立好树的各种关系，其它的操作（如查找、打印）就迎刃而解了。 二叉树虽然结构相对较简单，但包含的有些信息仍然多余,、采用矩阵结构,用一个二维数组来表示矩阵结构，它有x、y两个方向，在实际操作中常用的表示方法是：x轴表示数据元素，y轴表示元素的各种状态条件。数组的元素值表示数据元素在当前状态条件下的变化情况，用数值描述表示,每一个仅由0和1组成的子串也可以当作二进制数转化为十进制数来表示。然而每个十进制数与01串之间并不是一一对应的关系，如“01”、“010”和“0010”它们对应的十进制数都是2，这是为什么呢？原来， 10、010和0010在二进制中表示的是同一个数（2），但属于

26、不同字串，因为这时“0” 代表一个字符，字串间存在长度的差别。为了把长度不同、对应十进制数相同的字串区分开来，又设定了“长度”座标，这样，一维数组变成了二维矩阵A，其中Ax，y 存储对应十进制数为x、长度为y的01串的频率,从表中可以查找出频率最大的前N个串，然后按要求输出。,数据结构,const inputfile=contact.in;outfile=contact.out; /*输入和输出文件名*/ tc:array1.13of integer /*tci=2i-1*/ =(1,2,4,8,16,32,64,128,256,512,1024,2048,4096); put:array1.

27、12of integer /*puti=2i-1*/ =(1,3,7,15,31,63,127,255,511,1023,2047,4095); tz:array0.1 of byte=(0,1); /*字符转数值*/ type ar=array0.4095 of longint; var t:array1.21 of longint; /*不同频率按降序要求排列成t*/ tk:array1.12 of ar; /*tkij存储长度为i、对应十进制数值为j的子串频率*/ tch:array1.1024 of char;/*缓存设置*/ inf,outf:text; /*输入文件变量和输出文件变

28、量*/ a,b,n,long,kind:byte; /*长度范围为a,b,子串数为n, 当前子串长度为long,t序列的长度为kind*/ yu:integer; /*对应十进制数的模为yu=2b，使其长度不超过b）*/ ar=string12; /*子串*/,读入信息、构造二维数组,proce init; var i:byte; /*循环变量*/ ch:char; /*读入字符*/ m:integer; /*子串对应的十进制数*/ readln(inf,a,b,n);/*输入子串的长度范围和不同频率的子串个数 */ for i1 to b do/*各长度的子串频率清零*/ new(tki);

29、fillchar(tki,sizeof(tki),0); m0;long0; /*二进制串对应的十进制数和长度清零*/ yutcb+1; /*子串对应数值必须模2b,使其长度不超过b*/ repeat read(inf,ch); /*读二进制数码*/ if ch=2 then exit; /*若文件已读完，则退出*/ m(m*2+tzch) mod yu; /*计算有效子串对应的十进制数*/ if longb then inc(long);/*有效子串的长度+1*/ for i1 to long do inc(tkim and puti);/*累加以前缀长度为i的有效子串的频率*/ until

30、 false; ;/*init*/,使用插入排序法计算子串频率降序的排列,proce sort; var i,j，k，ii:integer; /*循环变量*/ fillchar(t,sizeof(t),0);kind0; /*t序列初始化为空*/ for ia to b do /*枚举长度*/ for j0 to puti do /*枚举长度为i的子串对应的十进制数*/ kkind; /*从t的尾部出发，左寻频率tkij的插入位置*/ while (k0)and(tkijtk) do dec(k); if (ktk) then if kindn then inc(kind); /*若插入后的t

31、序列长度不超过上限，则从t的第k+1位置开始的后缀右移一个位置，将tkij插入第k+1位置*/ for iikind downto k+1 do tii+1tii; tk+1tkij ;/*then*/ ;/*for*/ ;/* sort */,按要求输出结果,proce print; var ii,i,j,l,p:integer; assign(outf,outfile);rewrite(outf); /*输出文件写准备*/ settextbuf(outf,tch); /*设置缓冲区*/ for ii1 to n do /*按降序枚举频率顺序*/ write(outf,tii); /*输出第

32、ii大的频率*/ for ib downto a do/*按照长度降序的要求枚举具有相同频率的子串*/ for jputi downto 0 do /*按照对应十进制数值降序的要求枚举相同频率、相同长度的子串*/ if tkij=tii /*若长度为i、对应数值为j的子串的频率为第ii大*/ thenwrite(outf, ); pj; /*输出数值j对应的二进制串*/ for l1 to i dowrite(outf,p div tci+1-l);pp mod tci+1-l;/*for*/ ;/*then*/ writeln(outf); /*换行*/ ;/*for*/ close(out

33、f); /*关闭输出文件*/ ;/* print */,主程序, assign(inf,inputfile);reset(inf); /*输入文件读准备*/ settextbuf(inf,tch); /*设置缓冲区*/ init; /*输入信息，二维数组清零*/ make; /*读入01串，构建二维数组 */ close(inf); /*关闭输入文件*/ sort; /* 计算子串频率降序的排列t*/ print; /*按要求输出结果*/ ./*main*/,两种数据结构比较,矩阵结构为数组的定位操作，而二叉树结构需要递归； 二叉树结构中记录的“无用”信息比矩阵结构多； 矩阵结构比二叉树结构简

34、洁，且结合了二进制计算，因此速度也快了许多。 既然采用矩阵结构已经足够，二叉树结构中的一些信息显然就成为了“无用”的信息。这些多余的“无用”信息，使我们在分析问题时难于发现规律，也很难找到高效的算法。这正如迷宫中的墙一样，越多越难走。“无用”的信息只会干扰问题的规律性，使我们难于找出解决问题的方法。,选择数据的存储结构的基本方法,存储结构可以直接影响时间复杂度的阶； 即便不影响时间复杂度的阶，也会起到类同于剪枝的优化效果,重点讨论数据的线性存储结构,1、非线性的数据关系一般也是要通过线性的存储方式存入计算机的。例如通过二维数组的相邻表存储图，用一维的记录数组存储树。 2、数据的线性存储结构分为

35、 顺序存储结构借助元素在存储器中的相对位置（即数组下标）来表示数据元素之间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系 这两种存储结构的不同，导致在具体使用时分别存在着优点和缺点。,记录一个nn的矩阵，矩阵中包含的非0元素为m个（mn2）。,顺序存储结构：使用一个nn的二维数组，将所有数据元素全部记录下来； 链式存储结构：使用一个包含m个顶点的链表，记录所有非0的m个数据元素。,合理采用顺序存储结构,1、顺序结构操作方便； 2、在程序实现的过程中更便于对程序进行调试和查找错误 3、在顶点数目相差不大的情况下采用顺序结构。因为指针占用空间，且编程复杂，运行时间较慢

36、。,必要时采用链式存储结构,地下城市 已知一个城市的地图，该地图包含空地和墙。但未给出你的初始位置。你需要通过一系列的移动（move（方向）指令，即走入指定方向上的相邻格）和探索（look(方向)指令，即询问指定方向上的相邻格是空地还是墙），以确定初始时所在的位置。题目的限制是： 不能移动到有墙的方格。 只能探索当前所在位置四个方向上的相邻方格。 在这两个限制条件下，要求我们在探索次数（不包括移动）尽可能少的前提下，最终报告出初始位置(x，y)（finish(x，y)指令）。 输入输出情况：第1行输入城市地图规模u和v;以下输入一个v*u的字符矩阵，自上而下、由左而右读入每个格子的信息，其中字

37、符o代表空地，w代表墙；第v+2行发出开始探索指令start。然后反复调用move（方向）和look(方向)指令。调用look(方向)指令后，若系统返回o，则表示该方向的相邻格为空地；若返回w， 则表示该方向的相邻格为墙。通过移动和探索过程得出初始位置(x，y)后，调用finish(x，y)指令向系统报告。,基本思路,先假设所有无墙的方格都可能是初始位置，即可能的解集为所有空地。然后在探索城市的过程中，使用排除法将那些不属于初始位置的空地从可能的解集中删去。显然，当解集中仅剩一块空地时，最终确定该空地即为真正的初始位置。,用链表can存储空地,由于运算量最大的操作是筛选初始位置的范围和选择探索

38、位置，其操作对象为当前未排除的空地，这只是庞大地图中很少的一部分，因此顺序存储结构明显不适宜。,链式存储结构仅存储需要遍历的数据。这样不仅充分发挥了链式存储结构的优点，而且由于不需单独对某一个数据进行提取，每次都是对所有数据进行判断，从而避免了链式结构的最大缺点,建立一条探索链表uk，将旅行者从解集中的空地（相对位置（0，0）出发、经过路径上所有观察到的相对位置和观察方向依次存入这条链表,初始时，（0，0）的4个相邻格进入链表uk； 对链表uk中的每一个顶点，依次搜索4个相邻方向。若当前顶点q的i（1i4）方向的相邻位置未观察，则按照q的相对位置计算链表can中每个顶点的绝对坐标，累计i方向的

39、空地总数d1和墙的总数d2： 若链表can中每个顶点的绝对位置i方向都是空格，则设定q的i方向的相邻位置已观察，该位置和i方向进入探索链表； 若链表can中每个顶点的绝对位置i方向都是墙，则设定q的i方向的相邻位置已观察；,算法流程,所有空地进入can链； （0，0）的四个相邻格进入uk链；(nowx,nowy）(0,0); While can链的顶点数1 do 搜索uk链的每个相对位置（px,py）：(change过程） If can中每个空地（x,y）相对（px,py）的格子（px+x,py+y）为墙 Then 设相对位置（px,py）为墙； If can中每个空地（x,y）相对（px,p

40、y）的格子（px+x,py+y）为空地 Then 设相对位置（px,py）为空地，（px,py）的4个相邻位置进入uk链（不重复） Else 取uk链的下一个相对位置； 搜索uk链的每个相对位置（px,py）：（ find(xx,yy)） 累计can中每个空地（x,y）相对（px,py）的格子（px+x,py+y）中墙的总数d1和空地总数d2，将d1-d2最小的相对位置记为（xx，yy），并从uk链中删除该相对位置； 使用宽度优先搜索方法寻找（xx，yy）至（nowx,nowy）的最短路径，按照这条路径确定移动和探索方案，并将can链中不符探索结果的方格删除；(path(nowx,nowy,x

41、x,yy); ) ；/*while*/,为什么要按照d1-d2最小的要求删除链表can中不属于初始位置的空地？,若can中的每块空地相对于探索链表中顶点p和观察方向i来说，有d1块空地和d2堵墙（d1,d2链表can中的空地数），则看到墙后可以从can中删去d1个不属于初始位置的空地；看到空地后，can中可被删除的顶点数为d2个。由于看见空地的概率为d1/(d1+d2)，看见墙的概率为d2/(d1+d2) ，所以从can中删去不属于初始位置的空地的概率为d2*d1/(d1+d2)+d1* d2/(d1+d2) )=2d1*d2/(d1+d2) （d1+d2为定值）。由此可以看出，d1与d2愈接

42、近，这个概率值愈大，即从从可能解集中删去的无用空地数愈多，选择当前观察位置和观察方向愈有价值。按照最小的要求排除，可以使每一次的探索尽量多的缩小初始位置的范围，使程序尽量减少对运气的依赖。,数据结构,uses undertpu; /*调用库函数*/ const c:array1.4,1.2 of shortint=(0,-1),(-1,0),(1,0),(0,1); /*i方向上的水平增量为ci,1,垂直增量为ci,2*/ d:array1.4 of char=(S,W,E,N); /*四个方向对应的字母*/ st1=under.inp; /*输入文件名*/ type aa=record /*

43、链顶点类型*/ x,y:shortint; /*坐标*/ next:integer; /*后继顶点的数组下标*/ end; arr=array0.10000 of aa; /*链表类型*/ var a:array1.100,1.100 of char; /*地下城市地图，其中ax,y=O表示(x,y)无墙，ax,y=W表示(x,y)有墙*/ z:array-100.100,-100.100 of char; /*已知信息组成的新地图,zx,y存储相对于当前起点(x,y)位置的状态：O(x,y)无墙；W(x,y)有墙；Q(x,y)未放入uk链；U(x,y)已放入uk链；p (x,y)已标记*/

44、uk,can:arr; /* 探索链表为uk，存储状态未知的相对位置，空地集合为can链，存储目前可能成为出发点位置*/ tail,rest,v,u:integer; /*uk链的尾指针为tail，can链的尾指针为rest，地图的列数和行数分别为u、v*/,主程序,readp; /*读入城市地图a*/ getready; /*探索前的准备*/ start; /*发出开始探索命令*/ while rest1 do/*反复移动探索，直至can链剩一个顶点为止*/ change; /*将已确定状态的相对位置从uk链中删除*/ find(nextx,nexty); /*寻找对运气的依赖度最小的下一步

45、相对位置(nextx,nexty)，并将其从uk链表中删除*/ path(nowx,nowy,nextx,nexty); /*使用宽度优先搜索方法寻找（nextx,nexty）至（nowx,nowy）的移动和探索方案，并将can链中不符探索结果的方格删除*/ ;/*while*/ ocan0.next;finish(cano.x,cano.y);/*找到出发位置，报告*/ ;/*main*/,readp过程：读入城市地图a,proc readp; var f:text; /*文件变量*/ i,j:integer; assign(f,st1);reset(f); /*输入文件读准备*/ read

46、ln(f,u,v); /*读城市地图的规模*/ for iv downto 1 do /*自上而下、由左而右读入城市地图信息*/ for j1 to u do read(f,aj,i); readln(f) ;/*for*/ close(f); /*关闭输入文件*/ ;/* readp */,对(xx,yy)的相邻格进行探索,proc changeUK(xx,yy:integer); var i,j:integer; for i1 to 4 do /*判断(xx,yy)的四个相邻方格*/ if zxx+ci,1,yy+ci,2=Q /*若(xx,yy)i方向上的相邻格未入uk链，则入队*/ t

47、hen zxx+ci,1,yy+ci,2 U; with uktaildo xxx+ci,1;yyy+ci,2; nexttail+1 ;/*with*/ inc(tail) ; /*队尾指针+1*/ ;/* changeUK */,Getready：探索前的准备工作,proc getready; var i,j:integer; nowx0;nowy0; /*设当前相对位置为（0，0）*/ fillchar(z,sizeof(z),Q); z0,0 O;/* （0，0）为无墙，其它位置未入uk*/ new(can);can0.next1; /* 所有空地置入can链表*/ for i1 to

48、 u do for j1 to v do if ai,j=O then inc(rest); with canrestdo xi;yj;nextrest+1 ;/*with*/ ;/*then*/ canrest.next0; /*can链尾的后继指针为空*/ new(uk);tail1;uk0.next1; /*uk链为空*/ changeUK(0,0); /*将起点相邻的四个方格放入uk链*/ ;/* getready */,Change：从uk链中删除已确定状态的相对位置,proc change; var px,py,i,j,d:integer; /*d为移后位置的可能状态，1有墙，2无

49、墙，3不确定*/ i0; while uki.nexttail do /*沿next指针取出uk链中的每一个相对位置(px,py)*/ pxukuki.next.x;pyukuki.next.y; d0;j0; /*移后位置的状态初始化，沿can链计算确定状态的方格*/ while (d0) do jcanj.next; if acanj.x+px,canj.y+py=W then dd or 1 /*记录该方格可能有墙*/ else dd or 2; /*记录该方格可能无墙*/ ;/*while*/,if d3 /*若can链中某空地相对(px,py)的方格状态已确定，则将相对位置(px,p

50、y)从uk链表中删除*/ then uki.nextukuki.next.next; if d=1 then zpx,pyW;/*移后位置可能有墙*/ if d=2 then zpx,pyO;changeUK(px,py) ; /*若移后位置可能无墙，则（px,py）的相邻格入uk队列*/ /*then*/ else iuki.next;/*若can链中的所有空地相对(px,py)的方格状态未确定，则取uk链的下一个相对位置*/ ;/*while*/ ;/* change */,find：寻找对运气的依赖度最小的相对位置(xx,yy)，并将其从uk链表中删除,proc find(var xx,

51、yy:integer); var min,px,py,d1,d2,i,j,o:integer; /*对运气的最小的依赖度为min*/ minmaxint;i0;/* 对运气的最小依赖度初始化,从uk链首开始搜索*/ while uki.nexttail do/*沿next指针取出uk链中的每一个相对位置(px,py)*/ pxukuki.next.x; pyukuki.next.y; d10;j0;,while canj.next0 do /*在can链表的每个空地相对于(px,py)的方格中，累计墙的总数d1和空地的总数d2*/ jcanj.next; if acanj.x+px,canj.

52、y+py=W then inc(d1) ;/*while*/ d2rest-d1; if abs(d1-d2)min /*若墙的总数和空地的总数目前最接近，则说明 (px,py)对运气的依赖度为最小，记下对运气的最小依赖度、相对位置和其在uk链中的位置* / then minabs(d1-d2); oi;xxpx;yypy ; iuki.next; /*搜索uk的下一个相对位置*/ ;/*while*/ uko.nextukuko.next.next;/*从uk链中删除依赖度运气最小的相对位置*/ ;/* find */,Path:使用宽度优先搜索方法寻找（x2,y2）至（x1,y1）的移动和

53、探索方案，并将can链中不符探索结果的顶点删除,proc path(x1,y1,x2,y2:integer); var p:arr; /*队列*/ s,t,k,l,i,j:integer; /*队首指针为s，队尾指针为t*/ p1.xx2;p1.yy2;p1.next0;s1;t1;/*起点(x2,y2)入队*/ while (ps.xx1) or (ps.yy1) do /*若未到达目标（x1,y1）,则搜索队首方格的四个相邻格*/ for k1 to 4 do/*队首四个相邻格中的空地入队p*/ if zps.x+ck,1,ps.y+ck,2=O then inc(t);pt.xps.x+

54、ck,1;pt.yps.y+ck,2; zpt.x,pt.y P; /*在地图上标记该相邻格*/ pt.nexts ; /*标记t的父指针*/ inc(s); /*出队*/ ;/*while*/,ls;jpl.next; /*由目标（x1,y1）出发，按照倒推方向移动*/ while j1 do /*若未倒推至队首,则搜索当前一步的移动方向i */ for i1 to 4 do if(pl.x+ci,1=pj.x)and(pl.y+ci,2=pj.y)then break; move(di); /*发出移动命令*/ lj;jpl.next ; /*倒推下一步前后位置对应队列的指针*/ nowx

55、pl.x;nowypl.y; /*寻找（pl.x，pl.y）的探索方向i*/ for i1 to 4 do if(pl.x+ci,1=p1.x)and(pl.y+ci,2=p1.y)then break; elook(di); /*发出探索命令,得到探索结果e*/ zx2,y2e; /*按照探索结果标记（x2,y2）的状态*/ if e=O then changeUK(x2,y2);/*若（x2,y2）为空地，则置入uk链*/ for i-u to u do /*还原地图*/ for j-v to v do if zi,j=P then zi,jO; j0; /* 删除can链中与探索结果不符

56、的元素*/ while canj.next0 do/*若未搜索到链尾，则取出当前相邻的两个链指针*/ kj;jcanj.next; if acanj.x+x2,canj.y+y2e /*若相对于canj的（x2,y2）位置的方格状态与探索结果不符，则删除canj*/ then dec(rest);cank.nextcanj.next;jk ;/*then*/ ;/*while*/ ;/* path */,几种常用数据结构的一般特点,科学组合多种数据结构,对于多数的问题，可以通过选择一种合理的逻辑结构和存储结构达到优化算法的目的。但是，有些问题选择单一的数据结构会顾此失彼。 为了达到取长补短的作

57、用，使不同的数据结构在算法中发挥出各自的优势，可以采用多种数据结构结合的方法。多种数据结构结合的方式一般有两种: 数据结构的“并联”; 数据结构的 “嵌套”。,数据结构的“并联”,将用多个数据结构应用于同一数据集合的方法叫做数据结构的并联，这种数据结构的结合方式不仅可以将多种存储结构的优点完全发挥了出来，而且还可以通过映射建立不同数据结构中元素间的对应关系。,顽皮的猴子,有N（1N30000）只顽皮的猴子挂在树上。每只猴子都有两只手，编号为1的猴子的尾巴挂在树枝上，其它猴子的尾巴都被别的猴子的某只手抓着。每一时刻，都有且只有一只猴子的某只手松开，从而可能会有一些猴子掉落至地面。 任务:给出一开始猴子们的情况和每一时刻松开手的情况(必须保证每只抓住其它猴子尾巴的手松开且仅松开一次)，要求计算每只猴子落地的时间。 输入：第1行为猴子数n，以下n-1行，其中第i+1行的格式为j ch，表明猴子j的ch手抓住第i+1只猴子（ch=l，为左手；ch=r，为右手）；第n+1行为时间t