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

数据关系上 的 构造策略 上海市控江中学 xxx 数据结构回 顾 “数据结构算法程序”数据结构 是相互之间存在一种或多种特定关 系的数据元素的集合。对确定的问 题选择一种合适的数据结构，加上 设计一种好的算法，就是所谓的程 序设计。 数据的逻辑结构 定义：用数学方法来描述问题中所涉及的操作对象 及对象之间的关系，将操作对象抽象为数据元素，将对象 之间的复杂关系用数学语言描述出来。 重要性：设计数学模型的基础是确定数据的逻辑结 构，而算法又是用来解决数学模型的。要使得算法效率高 ，必须提高数据的逻辑结构中信息的利用效果。 基本的逻辑结构： 、集合集合中的数据元素之间只有“同属于 一个集合”的关系 、线性结构“一对一”的关系 、树形结构一对多”的关系 、图状（网状）结构“多对多”的关系。 数据的存储结构 如何实现对各个对象的操作，即各对象 之间的关系在计算机中如何表示。数据 的存储结构影响算法的效率。线性存储 结构分 、顺序存储结构 、链式存储结构 非线性存储结构一般也是通过线性的存 储方式存入计算机的（例如图的相邻矩 阵和邻接表） ； 选择数据的逻辑结构的基本 原则 在某些复杂的问题中，数据之间的关系相当 复杂，可选用的逻辑结构可能不止一种。但 选用哪种逻辑结构，直接影响算法效率。一 般来讲，选择合理逻辑结构应充分考虑的两 个因素 充分利用“可直接使用”的信息 不记录“无用”信息 选择逻辑结构的因素1： 充分利用“可直接使用”的信 息 “信息” 指的是元素与元素之间的关系。一 般分为 “可直接使用”：只需直接拿来即可。 “不可直接使用”：可通过某些间接的方 式，使之成为可以使用的信息，但其中转化 的过程需要花费一定的时间。 由此可见，我们所需要的是尽量多的“可直 接使用”的信息。这样的信息越多，算法的 效率就会越高。 圆桌问题 圆桌上围坐着个人。其中个人是好人，另外个人是坏 人。如果从第一个人开始数数，数到第个人，则立即 处死该人；然后从被处死的人之后开始数数，再将数 到的第个人处死依此方法不断处死围坐在圆桌上 的人。试问预先应如何安排这些好人与坏人的座位， 能使得在处死个人之后，圆桌上围坐的剩余的个人全 是好人。 输入：好人和坏人的人数n（n32767）、步长m（m 32767 ）； 输出：2个大写字母，G表示好人，B表示坏 人，50个字母为一行，不允许出现空白字符和空行。 例如n=5、m=3时，依次列出“处死5人” 的操作： 该题实际上是在一个长度为2*n的圆排列上，以m 为间隔进行n次出队操作。 普通解法线性表“查找” 法 、用顺序存储结构实现。即使用数组记录当前圆排列中每个 元素的初始位置，初始值为12n。可根据前一个出队元素的位 置（即数组下标）直接定位，找到下一个出队元素的位置，然 后删去，并将它后面的元素全部前移一次。 优点:“找点”时，可以由现在出队元素的 位置直接计算并在数组中精确定位； 缺点:“去点”时都需要把它后面所有的元 素整体移动一次。“去点”时的元素移动就是 信息由“不可直接使用”向“可直接使用”的 转化过程，其时间复杂度为O(n)。由于出队元 素有n个，因此程序的整体时间复杂度是O(n2) 。 、用链式存储结构实现 用链表记录当前圆排列 中每个元素的初始位置 ，初始值为12n。每 出队一个元素后，只要 将这个元素直接从链表 中删去即可，然后指针 后移(m-1)次，找到下 一个出队元素。 n=5,m=3的初始链表 依次列出了“处死5人”的操作（ 为当前出队元素的链表位置） 优点：“去点”时只要修改应该被删除顶点 的父指针的指向就可以了，毋需移动元素； 缺点：“找点”时需要移动(m-1)次定位指针 ； 所以应用链式存储结构，程序的整体时间复杂 度是O(nm)。 改进解法“直接定位法” 从哲学角度分析，“找点”和“去点”是存在于 程序和数据结构中的一对矛盾： 应用顺序存储结构时，“找点”效率高而“去点 ”效率低； 应用链式存储结构时，“去点”效率高而“找点 ”效率低; 这都是由数据结构本身决定的，不会随人的主观意 志存在或消失。这就表明“找点”和“去点”的时 间复杂度不会同时降为O(1)。我们希望有这样一种 数据结构，在实现“找点”和“去点”时，使复杂 度降到尽量低。 总体思想：在较好地实现“直接 定位”的基础上，尽量避免大量 元素移动 Group段数； Amount段中现有元素个数。随程序运行，段内出 队元素右方的元素左移，amount值不断减小。 var n,m,i,j,k,l,p,g:longint; /*好人和坏人的人数为n，步长值 为m，上次出列元素的段内位移为p，当前出列元素位于其右方第k 个位置，即段内位移为k+p*/ t,amount:array 165535 of longint; /* 分段式数组为 amount，其中第i段中的元素数为amounti，t为当前排列*/ ans:array165535of boolean; /*排列方案,其中ansi为 第i个元素的出列标志*/ readln(n,m); /*读好人和坏人的人数n和步长值m*/ fillchar(amount,sizeof(amount),0); /*各段为空*/ 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)+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 50=0)and(i0) and (tjp.num)/*p权值应插入t位置后*/ then if now=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);rewrite(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(outf); /*关闭输出文件*/ ;/* print */ 主程序 assign(inf,inputfile);reset(inf);/*输入文件读准备*/ settextbuf(inf,tch); /*设置缓冲区*/ init; /* 输入信息，生成空树*/ make; /*依次读入数据，计算各子串的频率*/ close(inf); /*关闭输入文件*/ print; /*按要求输出结果*/ ./*main*/ “一对多”的关系有利于处理好数据； 规律性强。如果新代顶点与子代顶点之间的关 系建立得好，那么就可以把庞大的元素安排得井井有 条，按照一定的顺序逐层深入，解决当前元素的处理 。 可操作性强。在解题中只要建立好树的各种关 系，其它的操作（如查找、打印）就迎刃而解了。 二叉树虽然结构相对较简单，但包含的有些信息仍然 多余 、采用矩阵结构 用一个二维数组来表示矩阵结构，它有x、y两个方向 ，在实际操作中常用的表示方法是：x轴表示数据元素 ，y轴表示元素的各种状态条件。数组的元素值表示数 据元素在当前状态条件下的变化情况，用数值描述表 示 每一个仅由0和1组成的子串也可以当作二进制数转化为十进制数 来表示。然而每个十进制数与01串之间并不是一一对应的关系， 如“01”、“010”和“0010”它们对应的十进制数都是2，这是 为什么呢？原来， 10、010和0010在二进制中表示的是同一个数 （2），但属于不同字串，因为这时“0” 代表一个字符，字串间 存在长度的差别。为了把长度不同、对应十进制数相同的字串区 分开来，又设定了“长度”座标，这样，一维数组变成了二维矩 阵A，其中Ax，y 存储对应十进制数为x、长度为y的01串的频率 从表中可以查找出频率最大的前从表中可以查找出频率最大的前N N个串，然后按要求输出。个串，然后按要求输出。 数据结构 const inputfile=contact.in;outfile=contact.out; /*输入和输出文件名*/ tc:array113of integer /*tci=2i-1*/ =(1,2,4,8,16,32,64,128,256,512,1024,2048,4096); put:array112of integer /*puti=2i-1*/ =(1,3,7,15,31,63,127,255,511,1023,2047,4095); tz:array01 of byte=(0,1); /*字符转数值*/ type ar=array04095 of longint; var t:array121 of longint; /*不同频率按降序要求排列成t*/ tk:array112 of ar; /*tkij存储长度为i、对应十进制数值为j 的子串频率*/ tch:array11024 of char;/*缓存设置*/ inf,outf:text; /*输入文件变量和输出文件变量*/ 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);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 long0)and(tkijtk) do dec(k); if (ktk) then if kind1 do 搜索uk链的每个相对位置（px,py）：(change过程） If can中每个空地（x,y）相对（px,py）的格子（px+x,py+y ）为墙 Then 设相对位置（px,py）为墙； If can中每个空地（x,y）相对（px,py）的格子（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,xx,yy); ) ；/*while*/ 为什么要按照d1-d2最小的要求 删除链表can中不属于初始位置的空 地？ 若can中的每块空地相对于探索链表中顶点p和观察方向i来说 ，有d1块空地和d2堵墙（d1,d21 do/*反复移动探索，直至can链剩一个顶 点为止*/ change; /*将已确定状态的相对位置从uk链中删除*/ find(nextx,nexty); /*寻找对运气的依赖度最小的下一 步相对位置(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); /*输入文件读准备*/ readln(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链，则入队*/ then 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 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 无墙，3不确定*/ i0; while uki.next0 do /*在can链表的每个空地相对 于(px,py)的方格中，累计墙的总数d1和空地的总数d2*/ jcanj.next; if acanj.x+px,canj.y+py=W then inc(d1) ;/*while*/ d2rest-d1; if abs(d1-d2)x1) or (ps.y1 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 ; /*倒推下一步前后位置对应队列的指针*/ nowxpl.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链中与探索结果不符的元素*/ while canj.nexte /*若相对于canj的（x2,y2）位置的方格 状态与探索结果不符，则删除canj*/ then dec(rest);cank.nextcanj.next;jk ;/*then*/ ;/*while*/ ;/* path */ 几种常用数据结构的一般特 点 结构类别所需 空间 操作 速度 体现元素 间联系 应用 范围 特点和适用范围 矩阵结构多较快多广随机存取，适用于递推和动 态规划 链 式 结 构 单链 表 少快少窄顺向搜索线性序列，不便回 扫 双向 链表 少较慢稍多较广便于查找线性序列中元素间 的前后联系 树型结构多一般多较广体现元素间“一对多”的联 系，一般采用递归手段 科学组合多种数据结构 对于多数的问题，可以通过选择一种合理的逻辑 结构和存储结构达到优化算法的目的。但是，有些问 题选择单一的数据结构会顾此失彼。 为了达到取长补短的作用，使不同的数据结构在 算法中发挥出各自的优势，可以采用多种数据结构结 合的方法。多种数据结构结合的方式一般有两种: 数据结构的“并联”; 数据结构的 “嵌套”。 数据结构的“并联” 将用多个数据结构应用于同一数据集合 的方法叫做数据结构的并联，这种数据 结构的结合方式不仅可以将多种存储结 构的优点完全发挥了出来，而且还可以 通过映射建立不同数据结构中元素间的 对应关系。 顽皮的猴子 有N（1N30000）只顽皮的猴子挂在树上。每只猴子都有 两只手，编号为1的猴子的尾巴挂在树枝上，其它猴子的尾巴 都被别的猴子的某只手抓着。每一时刻，都有且只有一只猴 子的某只手松开，从而可能会有一些猴子掉落至地面。 任务:给出一开始猴子们的情况和每一时刻松开手的情况(必 须保证每只抓住其它猴子尾巴的手松开且仅松开一次)，要求 计算每只猴子落地的时间。 输入：第1行为猴子数n，以下n-1行，其中第i+1行的格式 为j ch，表明猴子j的ch手抓住第i+1只猴子（ch=l ，为左手；ch=r，为右手）；第n+1行为时间t；最后含t 行，其中第n+1+i行的格式为j ch，表明在时刻i猴子j松 开ch手（ch=l，为左手；ch=r，为右手）； 输出：k行(最终有k个猴子落地)，每行的格式为猴子序 号 落地时间。 4 把猴子抽象成顶点，猴子的手 抽象成边，则猴子们的连接情 况构成一个连通图（图（a） ）题目就转化成一个连通图不 断去边、求每个点离开编号为 1的点所在的连通分量的时间 。 猴子1在时刻1松开左手，猴子3 在时刻2松开左手、时刻4松开 右手，猴子1在时刻3松开右手( 相当于猴子1和猴子3同时松开 右手) 。(图(b)中顶点旁的数 字给出了对应猴子落地的时间 。 3 3 2 1 把删边的顺序倒过来，问题转化为从一个 无边的图不断添边，求每个点进入编号为1 的点所在的连通分量的时间 把每个连通分量组成一个集合， 如果撇开集合中各元素相对位置 的计算，则添边对集合的查询和 合并，这是一个典型的并查集算 法的模型。 用并查集维护 当并查集中某个集合加入编 号为1的点所在的集合时，需 要把这个集合中的所有元素 的时间记录一下(图（a）)。 但并查集不支持“枚举集合 元素”的功能，怎么办？ 给每个并查集分配一个链表， 记录这个集合中所有的元素，( 图(b)。这样，能够方便的枚 举集合中的元素、合并并查集 。 数据结构type point=node; /*并查集的链表指针类型*/ node=record /*链顶点类型*/ v:longint; /*猴子序号*/ next:point /*后继指针*/ end; var n,i,j,k,t:longint; /*猴子数为n*/ ch:char; /*左（l）右(r)手标志*/ p:point; tree,m:array 130000,13 of longint; /*初始时猴子间的连接情况 为tree，添边过程中生成的树为m。其中i顶点的左儿子为treei,1（ mi,1)，右儿子为treei,2（mi,2)，父顶点为treei,3 (mi,3) */ e:array 130000,12 of longint; /*松手情况，其中第i时刻松 手猴子的编号为ei,1，松开手为ei,2(1左手，2右手)*/ open,closed:array 130000 of point; /*猴子i所在并查集的首指 针为openi，尾指针为closedi*/ time:array160000of longint; /*答案，其中猴子i的落地时间为 timei*/ readln(n); /*读猴子数*/ j0; for i2 to n do /*依次读入每个猴子的连接情况*/ readln(j,ch,ch); /*第i只猴子被猴子j的ch手抓住*/ if ch=lthen treej,1i else treej,2i;/*根据左右手确定i为j的 左儿子还是右儿子*/ treei,3j ; /*j为i的父顶点*/ readln(t); /*读时间数*/ for i1 to t do /*依次读入每个时刻的松手情况*/ readln(j,ch,ch); /*猴子j在时刻i松开ch手*/ ei,1j；if ch=l then ei,21 else ei,22 ; /*记录时刻i松手 的猴子编号和左右手标志*/ fillchar(m,sizeof(m),0); fillchar(time,sizeof(time),0); /*初始时树空 ，每个猴子的落地时间为0 */ for i1 to n do /*为每个猴子建立并查集*/ new(openi);openi.vi;openi.nextnil;closediopeni ; for it downto 1 do /*倒推时间，将每个时刻断开的边连上*/ ktreeei,1,ei,2;mei,1,ei,2k;mk,3ei,1; jei,1; /*从父顶点出发沿父指针追溯祖先顶点*/ while mj,3nil do timep.vi;pp.next /*while*/ ;/*then*/ closedj.nextopenk; /*将猴子k所在的并查集并入猴子j所 在的并查集*/ if closedk0 then writeln(i, ,timei).main 数据结构并联方式的利弊 数据结构支持的操作分为两类： 询问操作：顾名思义，就是获取该数据结构 记录的某些信息的操作，而并没有改动数据结构里的 元素及其相互关系。 维护操作：跟询问操作相反，在保持数据结 构性质的基础上改动数据结构中元素或元素间相互关 系的操作，称为维护操作。 对于这两类操作，数据结构的并联方式有利有弊。优 点是并联而成的新数据结构，可以支持组成它的数据 结构的所有操作；缺点是维护操作新数据结构的时间 ，一般为各个被并联数据结构的维护操作的时间叠加 ，这是制约计算时间的一个瓶颈。 数据结构的并联过程中， 有时需要通过映射建立不 同数据结构中元素间的对 应关系。 预备知识： 计算单源最短路问题 所谓单源是指一个出发顶点， 单源最短路问题指的是该顶点 至所有可达顶点的最短路径问 题。 Dijkstra算法 思维方向：每次延长最短路时选择权最小的边，并调整最短路 外每个结点至出发结点的路长 步骤：把图中所有结点分为两组，每一个结点对应一个距离值 ： 第一组：包括已确定最短路径的结点，结点对应的距离值是由 v0到此结点的最短路径长度； 第二组：包括尚未确定最短路径的结点，结点对应的距离值 是v0经由第一组结点（中间结点）至此结点的最短路径长度； 我们按最短路径长度递增的顺序把第二组的结点加到第一组 中去，直至v0可达的所有结点都包含于第一组。在这个过程中 ，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第 二组任何结点的路径长度。 初始时v0进入第一组，v0的距离值为0；第二组包含其它所有 结点，这些结点对应的距离值这样确定（设vi为第二组中的结点 ） 然后每次从第二组的结点中选一个其距离值为最小的 结点vm加到第一组中。每往第一组加入一个结点vm， 就要对第二组的各结点的距离值作一次修正（设vi为 第二组的结点, （vm，vi）为图中的边）： 若加进vm做中间结点使得v0至vi的路径长度更短（ 即vi的距离值vm的距离值+Wmi），则要修改vi的距 离（vi的距离值vm的距离值+Wmi）。修改后再选距 离值最小的一个结点加入到第一组中，。如此进行 下去，直至第一组囊括图的所有结点或再无可加入第 一组的结点存在。显然，这种从第二组的结点中选距 离值最小的结点扩展是一种贪心策略。 0 5 10 5 8 14 77 13 9 9 8 圆内的数字为距离值。绿色的结点为第一组的结 点，灰色的结点为第二组的结点 Dijkstra算法的执行速度取决于优先队列的数据结构 1、用一维数组来实现优先队列Q=V-S：算法运行时间 为O(V2+E)=O(V2)。 2、用二叉堆来实现优先队列Q：算法运行时间为 O(V+E)lgV)。通常情况下，边数|E|都不小于顶点数 |V|，所以运行时间又可以简化为O(ElgV)。 3、用Fibonacci堆来实现优先队列Q：算法运行时间 为O(VlgV+E)。但实现相当繁琐，在较短的时间里基 本上不大可能写出程序并调试好。另外，Fibonacci 堆算法中隐含的系数相当大，程序的实际运行效果并 不理想，目前该堆的理论价值远大于实用价值，因此 不适宜于限时编程的条件。 该算法的条件是该图所有边的权值非负，因此约 定：对于每条边(u,v)E，w(u,v)0。 最小序列 给定一个NN（N100）的正整数矩阵。需 要在矩阵中寻找一条从起始位置到终止位置 的路径(可沿上下左右四个方向)，并且要求 路径中经过的所有数字，其相邻数字之差的 绝对值之和最小。 输入：第1行为整数矩阵规模n；以下为n*n 的正整数矩阵；第n+2行为起点位置（x1,y1 ）和终点位置（x2,y2）； 输出：第1行为最短路长度；第2行依次给 出最短路经过的数字。 Dijkstra算法每次寻找一条最短路径时，需要两个步骤： 使用贪心策略，找一个不在最短路径起点集合内、并且到 终点距离最短的顶点i。数组这一步的时间复杂度为O(n)；二叉 堆的时间复杂度为O(1) 。 进行松弛操作，修改从与i相邻的顶点到终点的路径长度 。由于最多只有4个点(四个方向)与i相邻，所以数组这一步的复 杂度为O(1)，但二叉堆由于无法预知i点的相邻点在堆中的位置 ，因此时间复杂度升至O(n)。 解决方案：采用映射的方法，将线性结构中的元素与堆中的 顶点一一对应起来，若线性的数组中的元素发生变化，堆中相应 的顶点也随之变化；堆中的顶点发生变化，数组中相应的元素也 随之变化。 将两种结构进行并联后的时间复杂度为O(nlog2n)（ 进行n次复杂度为O(log2n)的堆化操作） 数据结构const b:array14,12 of shortint=(1,0),(0,1),(-1,0),(0,-1); /*i方向的水平 增量为bi,1,垂直增量为bi,2*/ type arr=array0101,0101 of integer; /*整数矩阵类型*/ htype=record /*堆的顶点类型*/ w:integer; /*距离值，即(x,y)到终点的最短路长度*/ x,y:byte; /*当前位置*/ end; var a,d:array0101,0101 of byte; /*a为整数矩阵，d为决策矩阵,其中 (i,j) 应选择di,j方向往下走*/ h:array010001 of htype;/*二叉堆，其中hi的左儿子为hi*2，右 儿子为hi*2+1*/ pos:arr; /*pos为映射数组，其中posi,j表示从整数矩阵中(i,j)位 置到终点的距离在堆h中的存储位置 */ x1,y1,x2,y2,n:byte;/*整数矩阵的规模为n，起点位置为(x1,y1), 终点 位置为(x2,y2)*/ t:integer; /*堆长*/ 读入信息 proc readp; var f:text; /*文件变量*/ st:string; /* 输入文件名串*/ i,j:byte; new(pos); /*为映射数组申请内存*/ write(File name:); /*输入文件读准备*/ readln(st);assign(f,st);reset(f); readln(f,n); /*读整数矩阵*/ for i1 to n do for j1 to n do read(f,ai,j); readln(f,x1,y1,x2,y2); /*读起点位置和终点位置*/ close(f); /*关闭输入文件*/ ;/* readp */ 堆操作 proc swap(i,j:integer); /*交换堆中的顶点i和顶点j*/ var k:htype; khi;hihj;hjk; /*交换距离*/ poshi.x,hi.yi;poshj.x,hj.yj; /*交换映射数组指向的堆位置*/ ;/* swap */ proc heap1(i:integer); /*从i顶点向下进行堆化*/ var j:integer; while i*21)and(hi div 2.whi.w)do swap(i div 2,i);ii div 2 ; /*若顶点i 的距离值小于其父，则与其父交换，继续向上堆化*/ ;/* heap2*/ proc make; /*使用dijkstra算法+堆结构，计算起始点到目标 点的最短路*/ var xx,yy,i,j:byte; fo:text; /*输出文件变量*/ h10001.w9999; /*设定各位置到终点的距离为*/ for i1 to n do for j1 to n do posi,j10001; h0.w0; for i1 to n do /*为避免移至界外，在矩阵四周加一圈， 圈上格子的距离值为0*/ posi,00;pos0,i0;posi,n+10;posn+1,i0 ; with h1 dow0;xx2;yy2 ;/* 将终点设为堆顶元素*/ posx2,y21;t1; repeat for i1 to 4 do /*搜索四个方向，调整堆顶相邻点的距离值*/ xxh1.x+bi,1; /*计算堆顶元素i方向的相邻格（xx,yy）*/ yyh1.y+bi,2; if hposxx,yy.w=9999/*若相邻格（xx,yy）至终点的距离未求出，则相邻 格和距离值进入堆尾*/ theninc(t); /*堆长+1*/ with ht do /*相邻格的距离值和坐标进入堆尾*/ wh1.w+abs(ah1.x,h1.y-axx,yy);xxx;yyy; posxx,yyt; /*记下相邻格在堆中的地址和移动方向*/ dxx,yyi; heap2(t) ; /*从堆尾出发向上堆化*/ else if h1.w+abs(ah1.x,h1.y-axx,yy)x2)or(y11：区间a，(a+b)div 2为 T的左儿子 ，区间(a+b)div 2，b为T的右儿子。 若区间长度L=1：T为一个叶子顶点，表示区间a， a+1。 区间1，10的线段树表示如图 数据结构 Type Tnode=Treenode； /*指向顶点的指针*/ Treenode=record /*顶点类型*/ B，E：integer；/*区间*/ C：integer； /*覆盖B，E的线段数*/ LSON，RSON：Tnode；/*指向左右子树的指针*/ end； 其中B和E表示了该区间为B，E；C为一个计数器，通常记录覆 盖到此区间的线段条数；LSON和RSON分别指向左右子树的根。 为了简化数据结构和方便计算，也可以采用静态数组B， E，C，LSON，RSON存储线段树。设线段树的子树根为v 。Bv，Ev就是v所表示区间的左右边界；Cv仍然用来作计 数器；LSONv，RSONv分别为v的左儿子和右儿子的数组下标 。 建立线段树T（a，b） 设一个全局变量n，来记录一共用到了多少顶点。开始n=0 。 PROC BUILD(a，b)；/*建立区间a,b对应的线段树*/ nn+1；vn；Bva；Evb；Cv0；/*代表 区间a，b的变量初始化*/ if b-a1 /*若该区间存在，则分别给左右儿子编号， 并递归左右子区间*/ then LSONvn+1；BUILD(a，int(a+b)/2)； RSONvn+1；BUILD(int(a+b)/2)+1，b) /* then */ ; /*BUILD*/ 将区间c，d插入线段树T(a，b) 设线段树T(a，b)的根编号为v。如果c，d完全覆盖了v顶点代表 的区间a，b，那么显然该顶点上的基数（即覆盖线段数）加1； 否则，如果c，d不跨越区间中点，就只对左树或者右树上进行插 入。如果c，d跨越区间中点，则在左树和右树上都要进行插入。 注意观察插入的路径，一条待插入区间在某一个顶点上进行“跨越 ”，此后两棵子树上都要向下插入，但是这种跨越不可能多次发生 。插入区间的时间复杂度是O(log2n)。 PROC INSERT(c，d，v)；/*将区间c，d插入以v为根的线段树*/ if（cBv）and（Evd） /*若区间c，d覆盖v顶点代 表的区间，则覆盖该区间的线段个数+1；否则，若c，d不跨越区 间中点，就只对左树或右树上进行插入；若c，d跨越区间中点， 则在左树和右树上都要进行插入*/ then CvCv+1 else If cint(Bv+Ev)/2) then INSERT(c，d；RSONv) ；/* else */ ; /* INSERT */ 将区间c，d从线段树T(a，b)中 删除 设线段树T(a，b)的根编号为v。在线段上树删除一个区间与插入的 方法几乎是完全类似的。特别注意：只有曾经插入过的区间才能够 进行删除。这样才能保证线段树的维护是正确的。 PROC DELETE(c，d，v)；/*将区间c，d从v顶点代表的区间中删 除*/ if cBv and Evd /*若区间c，d覆盖v顶点代表的区间 ，则覆盖该区间的线段个数-1；若c，d不跨越区间中点，就只对 左树或右树上进行删除；否则在左树和右树上都要进行删除*/ then CvCv-1 else if cint(Bv+Ev)/2) then DELETE(c，d；RSONv) ；/*else*/ ;/* DELETE */ 线段树的动态维护 线段树的作用主要体现在可以方便地动态维护其某些特征 。例如，增加一个数据域 Mv，存储以v为根的子树上线段并 集的长度 只要每次插入或删除线段区间时，更新已访问顶点的M值（不 妨称之为UPDATA操作），就可以在插入和删除的同时维持好M 。求整个线段树的并集长度时，只要访问MROOT的值。这在 许多动态维护的题目中是非常有用的，它使得每次操作的维护 费用只有log2n。 类似的，还有求并区间的个数等等。这里不再深入列举。 预备知识2：平衡树 有序性：每一个顶点x都满足：该顶点左子树中的每一 个元素都小于x，而其右子树中的每一个元素都大于x。 平衡性：左子节点与右子节点对称，即任何节点的两个 儿子子树的高度差别尽可能小（差别为1为高度平衡树AVL） 节点的平衡性特征：平衡因子右子树的高度-左子 树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡 的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并 需要重新平衡这个树。 平衡办法： 在不破坏左小右大特性的前提下旋转。 数据结构 Type treeType=record /*平衡树的顶点类型*/ key, prior, sum, s:longint;/*关键字、平衡 因子、子树规模和关键字频率*/ l, r:longint;/*左右指针*/ end; Var tree:array020*maxnof treeType;/*平衡树*/ 以t顶点为基准左旋 proc leftRotate(var t:longint); var k:longint; ktreet.r; /*t的右儿子左旋至根位置*/ treet.rtreek.l;treek.lt; treek.sumtreet.sum; /*重新设定以k为根的平衡树和k的 左子树的规模*/ treet.sumtreetreet.l.sum + treetreet.r.sum + treet.s; tk; /*返回子树的根*/ ;/* leftRotate */ 以t顶点为基准右旋 proc proc rightRotate(varrightRotate(var t:longintt:long