线性表应用2014

1、线性表？线性表？本期要点本期要点 线性表的设计技巧线性表的设计技巧 用数组模拟动态链表用数组模拟动态链表 哈希哈希一、最佳游览路线一、最佳游览路线 某游览区街道成网络状，东西向的街道是某游览区街道成网络状，东西向的街道是旅游街，只能由西向东走，并有一定的分旅游街，只能由西向东走，并有一定的分值，南北向的街道是林荫道，既可从南向值，南北向的街道是林荫道，既可从南向北走，也可从北向南走，没有分值，要求北走，也可从北向南走，没有分值，要求从某一路口开始游览，并在另一路口结束从某一路口开始游览，并在另一路口结束游览，使所走过的街道分值总和最大。其游览，使所走过的街道分值总和最大。其中中1旅游街道数目旅

2、游街道数目100，1林荫道数目林荫道数目20001，-100分值分值100。 不记录无用信息不记录无用信息 规模规模 ：100*20001=2000100 ？ 只能由西向东走，每一纵行至多只能通过一次，同只能由西向东走，每一纵行至多只能通过一次，同一纵行可以通过林荫道自由到达，只需走分值最大一纵行可以通过林荫道自由到达，只需走分值最大的街道，所用空间为的街道，所用空间为20001个个shortint。 定义定义Pi为以为以i结尾的最优路径分值的总和，结尾的最优路径分值的总和，Ai表示第表示第I纵行的最大分值纵行的最大分值 p0=0 求求max(pi)为负数）（非负数）iiiiiiAPAPAPP

3、i1110(二、圆桌问题二、圆桌问题 圆桌上围坐着圆桌上围坐着2n个人，其中个人，其中n个是好人，个是好人，n个是坏人。如果从第一个人开始数数，数个是坏人。如果从第一个人开始数数，数到第到第m人，则立即处死该人。然后从被处死人，则立即处死该人。然后从被处死的人后重新数数，数到第的人后重新数数，数到第m人处死人处死 如何预先安排如何预先安排2n人位置，使得在处死人位置，使得在处死n人之人之后，剩下的都是好人。后，剩下的都是好人。静态数组静态数组查找：直接计算删除：移动for i:=1 to 2*n do bi:=0;for i:=1 to 2*n do ai:=i;k:=1;for i:=1 t

4、o n do begin k:=(k+m-1 ) mod (2*n-i+1); if k=0 then k:=2*n-i+1; bak:=1; for j:=k to 2*n-i do aj:=aj+1; end;O(n2)用数组模拟链表用数组模拟链表for i:=1 to 2*n do begin :=i; ai.next:=i mod (2*n)+1; end;k:=1;for i:=1 to n do begin for j:=1 to m-2 do k:=ak.next; p:=ak.next; :=1; ak.next:=ap.next; k:=ak.n

5、ext; end;type node=record info,next:integer; end;var a:array1.maxn of node; 查找：顺序删除：不产生移动O(nm)改进改进直接定位法直接定位法动态数组顺序Amount：表示此段中现有元素的个数Group=4 将原来的数据分为4段存储解释解释 Group表示将原来的数据分为几段存储表示将原来的数据分为几段存储 每一段的开头记下每一段的开头记下amount值表示此段中现值表示此段中现有元素的个数有元素的个数 随程序运行，随程序运行，amount不断减小不断减小 充分利用充分利用“可直接使用可直接使用”的信息的信息充分利用充分

6、利用“可直接使用可直接使用”的信息的信息group:=2*n div m;for i:=1 to group do amounti:=m;if 2*n mod m 0 then begin inc(group); amountgroup:=2*n mod m; end;k:=0;j:=1;for i:=1 to n do begin p:=m; while k+pamountj do begin p:=p+k-amountj;j:=j mod group+1;k:=0; end; ba(j-1)*m+p+k:=1; for l:=(j-1)*m+p+k to (j-1)*m+amountj-1

7、 do al:=al+1; amountj:=amountj-1; k:=k+p-1; end;查找：快速删除：段内移动O(nm)三、寻找子串三、寻找子串 从由从由01串构成的文件中，找出长度介于串构成的文件中，找出长度介于A和和B之间出现次数最多的之间出现次数最多的N个不同频率的子串，个不同频率的子串，子串可以相互覆盖，输出结果必须按子串子串可以相互覆盖，输出结果必须按子串出现频率的降序排列，频率相同的子串按出现频率的降序排列，频率相同的子串按长度降序排列，频率和长度均相同的子串长度降序排列，频率和长度均相同的子串则按其对应数值降序排列。其中则按其对应数值降序排列。其中0AB12，0N20，

8、输入文件可达到，输入文件可达到2MB。分析分析找出所有满足条件的子串，并统计各子串找出所有满足条件的子串，并统计各子串出现的频率；出现的频率；把所有不同子串按要求排序输出。把所有不同子串按要求排序输出。选择二叉树结构选择二叉树结构 树中的每个点赋予一定的权值，表示该点树中的每个点赋予一定的权值，表示该点对应的子串在文件中出现的频率，可以得对应的子串在文件中出现的频率，可以得到累加规律。例如当到累加规律。例如当A=1，B=3时，某中间时，某中间状态：状态： 假设现在读到一个串为假设现在读到一个串为“011”，其中以，其中以“0”开头开头且长度为且长度为1到到3的子串有三个：的子串有三个：“0”、

9、“01”、“011”，统计时应将这三个子串的频率加，统计时应将这三个子串的频率加1，从，从图上可以直观地看到，这个操作相当于在对图上可以直观地看到，这个操作相当于在对应的应的01路径上将各结点的频率加路径上将各结点的频率加1 对应二叉树的结点最大为对应二叉树的结点最大为213-18191，可，可以多次遍历，不难从中找出前以多次遍历，不难从中找出前N个频率最大个频率最大的子串，然后按从大到小的顺序输出。的子串，然后按从大到小的顺序输出。 出现次数不是最多的字串被重复使用出现次数不是最多的字串被重复使用采用数组存储采用数组存储 一个二维数组来表示矩阵结构，一个二维数组来表示矩阵结构，x轴表示数据的

10、元轴表示数据的元素，素，y轴表示元素各种状态条件。数组内具体的值轴表示元素各种状态条件。数组内具体的值表示元素在当前状态条件下的表现，一般用数值表示元素在当前状态条件下的表现，一般用数值表示。表示。 每一个仅由每一个仅由0和和1组成的子串也可以当作二组成的子串也可以当作二进制数转化为十进制数来表示进制数转化为十进制数来表示 “10”、“010”和和“0010” 长度的差别长度的差别 设定了设定了“长度长度”座标座标 查找出频率最大的前查找出频率最大的前N个串个串 四、团队队列四、团队队列 在一个团队队列中每个元素属于一个团队。在一个团队队列中每个元素属于一个团队。当一个元素进入队列时，他首先从

11、队列的当一个元素进入队列时，他首先从队列的首部到尾部搜索检查是否他的队友已经在首部到尾部搜索检查是否他的队友已经在队列中。如果有的话，该元素进入队列排队列中。如果有的话，该元素进入队列排在他的队友的后面。如果没有，他进入队在他的队友的后面。如果没有，他进入队列排在队列尾部，成为最后一个新元素。列排在队列尾部，成为最后一个新元素。出队列如同正常的队列操作：按元素在团出队列如同正常的队列操作：按元素在团队队列中的顺序，从头到尾出队列。队队列中的顺序，从头到尾出队列。 模拟团队队列的过程。模拟团队队列的过程。输入输入 团队数目团队数目t（1=t0 then qteamr1.next:=r else

12、f:=r; r1:=belongx; enelse begin k:=teambelongx; qr.next:=qk.next; qk.next:=r; teambelongx:=r; end;出队出队writeln(qf.num);if (qf.next=0) or (belongqf.numbelongqqf.next.num) then teambelongqf.num:=0;f:=qf.next;五、五、10-20-30 52张不分花色。张不分花色。J、Q、K为为10，A为为1，其余，其余为点数。为点数。 从左到右从左到右7组。按序发牌组。按序发牌(组别、牌堆上下组别、牌堆上下) 每

13、组每组10-20-30： 前两张和最后一张前两张和最后一张 第一张和最后二张第一张和最后二张 最后三张最后三张 抽出并放入牌堆底部抽出并放入牌堆底部 全部抽走即全部抽走即“消失消失”7组均消失，获胜无牌发，失败平局输入输入/出样例出样例 2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1 10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2 4 3 2 10 8 10 6 8 9 5 8 10 5 3 5 4 6 9 9 1 7 6 3 5 10 10 8 10

14、 9 10 10 7 2 6 10 10 4 10 1 3 10 1 1 10 2 2 10 4 10 7 7 10 10 5 4 3 5 7 10 8 2 3 9 10 8 4 5 1 7 6 7 2 6 9 10 2 3 10 3 4 4 9 10 1 1 10 5 10 10 1 8 10 7 8 10 6 10 10 10 9 6 2 10 10 Win : 66 Loss: 82 Draw: 73状态查找及判重先考虑能定胜负的情况先考虑能定胜负的情况 模拟链表模拟链表 ？字符串？字符串type node=record info:longint; next:longint; front

15、:longint; end;Var q:array0.53 of node; team:array1.8,1.3 of longint; count,total:longint; for i:=1 to 52 do begin read(); qi.next:=i+1; qi.front:=i-1; end;q7.next:=1; q1.front:=7;for i:=1 to 7 do begin teami,1:=1; teami,2:=i;teami,3:=i end;team8,3:=52;team8,2:=8; team8,1:=52-7; 发牌发牌total:=tot

16、al+1;p1:=teamcount+1,2; p2:=teami,3;p3:=qp2.next;TeamiTeami+1Teamcount+1nextfrontp1p2p3teamcount+1,2:=qp1.next;p1.front:=p2;qp1.next:=p3; qp3.front:=p1; qp2.next:=p1; teami,3:=p1;inc(teami,1); dec(teamcount+1,1);输输抽牌抽牌p1:=qp.front;p2:=qp.next;p3:=teamcount+1,3; 120TeamiTeami+1Teamcount+1Teami-1qp1.n

17、ext:=p2; qp2.front:=p1; qp3.next:=p; qp.front:=p3;inc(teamcount+1,1); teamcount+1,3:=p; dec(teami,1);if k=1 then teami,2:=p2 else if k=0 then teami,3:=p1;p1p2p3p 对于频繁使用的查找，我们希望平均查找对于频繁使用的查找，我们希望平均查找长度接近于长度接近于0预先知道所查关键字在表中的位置预先知道所查关键字在表中的位置记录在表中位置和其关键字之间存在一记录在表中位置和其关键字之间存在一种确定的关系种确定的关系判重决策判重决策 哈希表：哈希

18、表：应用应用哈希函数哈希函数，由记录的关键字确，由记录的关键字确定记录在表中的地址，并将记录放入此地址，定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。这样构成的表叫哈希表。 哈希查找：哈希查找：又叫散列查找，利用又叫散列查找，利用哈希函数哈希函数进进行查找。行查找。 哈希表的数组是定长的，如果太大，则浪费，哈希表的数组是定长的，如果太大，则浪费，如果太小，体现不出效率。合适的数组大小如果太小，体现不出效率。合适的数组大小是哈希表的性能的关键。是哈希表的性能的关键。 哈希表的尺寸最好是一个质数。哈希表的尺寸最好是一个质数。哈希（哈希（hash）构造哈希函数的几种方法构造哈希函数的

19、几种方法 对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法若是非数字关键字，则需先对其进行数字化处理若是非数字关键字，则需先对其进行数字化处理1. 直接定址法直接定址法3. 平方取中法平方取中法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法1. 直接定址法直接定址法 构造：取关键字或关键字的某个线性函数构造：取关键字或关键字的某个线性函数作哈希函数作哈希函数 H(key) = key 或者或者 H(key) = a. key + b 特点特点 直接定址法所得地址集合与关键字集合大小相直接定址法所得地址集合与关键字集合大小相等，不会发生冲突等，不会发生冲突2. 除

20、留余数法除留余数法 构造：关键字被某个不大于构造：关键字被某个不大于hash表长（表长（m）的数的数p求余做哈希地址，即求余做哈希地址，即 H(key)=key % p p通常取小于通常取小于hash表长的最大素数表长的最大素数 特点特点 简单、常用简单、常用 p的选取很重要的选取很重要: p选的不好，容易产生同义词选的不好，容易产生同义词对对P要加一定的限制要加一定的限制3.随机数法随机数法 构造：取关键字的随机函数值作哈希地址构造：取关键字的随机函数值作哈希地址H(key)=random(key) 适于关键字长度不等的情况适于关键字长度不等的情况回到回到10-20-30 7组状态合一谋取高

21、效率（其实可看成组状态合一谋取高效率（其实可看成8组）组） 状态？状态？ 通过通过ABCDEFGH分割分割 2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1 10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2 A2 10 B6 10 C5 4 D10 5 E10 10 F4 4 G10 5 H10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1 10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8

22、2哈希函数哈希函数1999997%13*)inf.()(1.0lenqiioiqshash1000009%13*)inf.()(2.1lenqiioiqshash 为产生冲突的关键字寻找一个新的地址为产生冲突的关键字寻找一个新的地址Hi(key)， 求得一个地址序列求得一个地址序列 H0, H1, H2, , Hs 1 sm-1 其中：其中：H0 = H(key) H1 = (H(key) + d1 ) % m H2 = (H(key) + d2 ) % m Hi = ( H(key) + di ) % m i=1, 2, , s解决冲突解决冲突开放地址法开放地址法 线性探测：线性探测：di=

23、1,2,3,m-1 二次探测：二次探测：di=1,-1,2,-2,3,k增量增量diNoip初赛题初赛题广度优先搜索时，需要用到的数据结构是（广度优先搜索时，需要用到的数据结构是（ ）A链表链表 B队列队列 C栈栈 D散列表散列表 散列表的地址区间为散列表的地址区间为0-10,散列函数为散列函数为H(K)=K mod 11。采用开地址法的线性探查法处理冲突，并将。采用开地址法的线性探查法处理冲突，并将关键字序列关键字序列26，25，72，38，8，18，59存储到散存储到散列表中，这些元素存入散列表的顺序并不确定。列表中，这些元素存入散列表的顺序并不确定。假定之前散列表为空，则元素假定之前散列表为空，则元素59存放在散列表中存放在散列表中的可能地址有：的可能地址有：A)