线性表应用2014.ppt

线性表？ 本期要点 线性表的设计技巧 用数组模拟动态链表 哈希 一、最佳游览路线 某游览区街道成网络状，东西向的街道是旅游街，只能由西向东走，并有一定的分值，南北向的街道是林荫道，既可从南向北走，也可从北向南走，没有分值，要求从某一路口开始游览，并在另一路口结束游览，使所走过的街道分值总和最大。其中1≤旅游街道数目≤100，1≤林荫道数目≤20001，-100≤分值≤100。 不记录无用信息 规模 ：100*20001=2000100 ？ 只能由西向东走，每一纵行至多只能通过一次，同一纵行可以通过林荫道自由到达，只需走分值最大的街道，所用空间为20001个shortint。 定义Pi为以i结尾的最优路径分值的总和，Ai表示第I纵行的最大分值 p0=0 求max(pi) 二、圆桌问题 圆桌上围坐着2n个人，其中n个是好人，n个是坏人。如果从第一个人开始数数，数到第m人，则立即处死该人。然后从被处死的人后重新数数，数到第m人处死…… 如何预先安排2n人位置，使得在处死n人之后，剩下的都是好人。 静态数组 for i:=1 to 2*n do b[i]:=0; for i:=1 to 2*n do a[i]:=i; k:=1; for i:=1 to n do begin k:=(k+m-1 ) mod (2*n-i+1); if k=0 then k:=2*n-i+1; b[a[k]]:=1; for j:=k to 2*n-i do a[j]:=a[j+1]; end; 用数组模拟链表 …… for i:=1 to 2*n do begin a[i].info:=i; a[i].next:=i mod (2*n)+1; end; k:=1; for i:=1 to n do begin for j:=1 to m-2 do k:=a[k].next; p:=a[k].next; b[a[p].info]:=1; a[k].next:=a[p].next; k:=a[k].next; end; 改进——直接定位法 解释 Group表示将原来的数据分为几段存储 每一段的开头记下amount值表示此段中现有元素的个数 随程序运行，amount不断减小 充分利用“可直接使用”的信息 充分利用“可直接使用”的信息 group:=2*n div m; for i:=1 to group do amount[i]:=m; if 2*n mod m 0 then begin inc(group); amount[group]:=2*n mod m; end; k:=0;j:=1; for i:=1 to n do begin p:=m; while k+pamount[j] do begin p:=p+k-amount[j];j:=j mod group+1;k:=0; end; b[a[(j-1)*m+p+k]]:=1; for l:=(j-1)*m+p+k to (j-1)*m+amount[j]-1 do a[l]:=a[l]+1; amount[j]:=amount[j]-1; k:=k+p-1; end; 三、寻找子串 从由01串构成的文件中，找出长度介于A和B之间出现次数最多的N个不同频率的子串，子串可以相互覆盖，输出结果必须按子串出现频率的降序排列，频率相同的子串按长度降序排列，频率和长度均相同的子串则按其对应数值降序排列。其中0＜A≤B≤12，0＜N≤20，输入文件可达到2MB。 分析 找出所有满足条件的子串，并统计各子串出现的频率； 把所有不同子串按要求排序输出。 选择二叉树结构 树中的每个点赋予一定的权值，表示该点对应的子串在文件中出现的频率，可以得到累加规律。例如当A=1，B=3时，某中间状态： 假设现在读到一个串为“011”，其中以“0”开头且长度为1到3的子串有三个：“0”、“01”、“011”，统计时应将这三个子串的频率加1，从图上可以直观地看到，这个操作相当于在对应的01路径上将各结点的频率加1 对应二叉树的结点最大为2^13-1＝8191，可以多次遍历，不难从中找出前N个频率最大的子串，然后按从大到小的顺序输出。 出现次数不是最多的字串被重复使用 采用数组存储 一个二维数组来表示矩