当前位置:首页 >> 学科竞赛 >>

day3简单数据结构


堆栈、队列、二叉树

长沙市一中 曹利国

怎样授数据结构知识课
?

?

?

?

把握数据结构的基本概念,要求学生领 会“数据”和“结构”的内涵 对问题不盲目地套某种数据结构,要学 会根据数据的特点构造出自己的结构 数据结构和算法是紧密联系,

没有离开 算法的数据结构 广泛地吸取新的知识点,掌握不同结构 构造后的时空效率及其他特点

几种主要的数据结构
? ? ? ?

离散结构 线性结构 树形结构 图结构

1.栈 ( Stack )及其应用
? 1。1 栈的概念 ? 只允许在一端插入和删除的表 ? 允许插入和删除 的一端称为栈顶 (top),另一端称 为栈底(bottom) ? 特点 后进先出 (LIFO)

进栈示例

出栈示例

栈的基本操作
1、初始化 2、进栈PUSH 3、出栈POP 4、取栈顶元素GetTop 5、判栈是否非空

1。2 栈的应用 NOIP2005试题:《等价表达式》 问题描述 明明进了中学之后,学到了代数表达式。有一 天,他碰到一个很麻烦的选择题。这个题目的题干 中首先给出了一个代数表达式,然后列出了若干选 项,每个选项也是一个代数表达式,题目的要求是 判断选项中哪些代数表达式是和题干中的表达式等 价的。 这个题目手算很麻烦,因为明明对计算机编程 很感兴趣,所以他想是不是可以用计算机来解决这 个问题。假设你是明明,能完成这个任务吗? 这个选择题中的每个表达式都满足下面的性质:

表达式只可能包含一个变量‘a’。 表达式中出现的数都是正整数,而且都小于10000。 表达式中可以包括四种运算‘+’(加),‘-’(减), ‘*’(乘),‘^’(乘幂),以及小括号‘(’,‘)’。 小括号的优先级最高,其次是‘^’,然后是‘*’,最后 是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先 级的运算从左到右进行。(注意:运算符‘+’,‘-’, ‘*’,‘^’以及小括号‘(’,‘)’都是英文字符) 幂指数只可能是1到10之间的正整数(包括1和10)。 表达式内部,头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子:
((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(aa)*a,1 + (a -1)^3,1^10^9……

输入文件 输入文件equal.in的第一行给出的是题干中的表达式。第二 行是一个整数n(2 <= n <= 26),表示选项的个数。后面n行, 每行包括一个选项中的表达式。这n个选项的标号分别是A,B, C,D…… 输入中的表达式的长度都不超过50个字符,而且保证选项中 总有表达式和题干中的表达式是等价的。 输出文件 输出文件equal.out包括一行,这一行包括一系列选项的标 号,表示哪些选项是和题干中的表达式等价的。选项的标号按照 字母顺序排列,而且之间没有空格。 样例输入 ( a + 1) ^2 3 (a-1)^2+4*a a + 1+ a a^2 + 2 * a * 1 + 1^2 + 10 -10 +a -a 样例输出 AC

关键:如何判断表达式等价?
方法1:展开表达式直接比对,显然不可取。 方法2:求表达式的值,比对表达式的值。但对于个体值 有可能出现等价的表达式其值相等。引入随机化思想,随 机产生几个a的值,当对每个随机产生的a值表达式值都相 等时视为表达式等价。 问题转换:如何求表达式的值。

利用栈实现表达式计算。对表达式运算符定义运 算优先级。 算法描述:

设立运算符栈和操作数栈,逐词读入表达式,并处 理: 1、若读入为操作数,则入栈; 2、若读入为运算符,则与栈顶运算符相比较: (1)若栈顶运算符优先级高于或等读入运算符, 反复执行下列操作,直到栈顶运算符优先级不高于 读入运算符: 弹出运算符,弹出两个操作数,计算并将结果 入操作数栈; (2)若栈顶运算符优先级低于读入运算符,则 将读入运算符入栈; 3、若遇到结束运算符,则计算结束。 4、检查栈状态,得到计算结果。

使用栈进行算术表达式求值
opnd
表达式:3 × ( 5 – 2 ) + 7 @ optr
结果便是 16 5+ –9 2 = 3 7 = 16 3 × 3 = 9!

2 5 3 7 16 3 9

– ( + ×

最长词链
?

?
? ?

一个词是由至少1个,至多75个小写英文字母(a..z)组成。当在 一张由一个或多个词组成的表中,每一个词(除第一个外)都 能由在其前一个词的词尾添加一个或多个字母而得到,则称此 表为一个链。 例如:

?
? ?

i in int integer
为一个含4个词的词链。

? ? ? ?

而表

input integer
不是词链。注意:所有含有一个词的表都是 链。 给定一个词按字典顺序由小到大排列的 表,找出表中的最长词链。表的大小最大达 到2M。

?

?

分析
?

这道题目,虽然测试数据大得惊人,但是难 度却并不大。主要的是要把握住表的特点: 词按字典顺序由小到大的排列,因此表中的 相邻的两个词语之间的关系只有两种——属 于同一词链或不属于同一词链,若它们不属 于同一词链,那么后一个单词所在的词链, 除这一个单词外的链(这个链可能为空)必 定为它在表中的前一个单词的词链的前缀。

? ? ?

举例:

i,in,int,integer,inter
在上面这个例子当中,最后一个单词inter所组 成的词链为i→in→int→inter,在这个链中,除 inter的外的链为i→in→int。而它的前一个单词 integer组成的词链为i→in→int→integer。其中 i→in→int就是i→in→int→integer中的前缀。 因此,可以利用堆栈这种数据结构来解决这一 问题。

?

算法框架
? ? ? ? ? ? ? ? ? ?

const MaxLen = 75;(单词的最大长度) type Twork = object Top,Max:Integer; (Top表示堆栈中元素的个数,Max表示最大词链的长度); Word,Ans:array[1..MaxLen]of String[MaxLen]; (栈中每一层记录的词) procedure Work; end;

?
? ? ? ? ?

procedure Twork.Work;
1.Top←0;Max←0; 2.Readln(St);读入一个词 3.While St<>’.’ Do While (Top>0) and (Pos(Word[Top],St)<>1 do Top←Top-1;{ 查找堆栈中的词判断哪些词语能够继续和目前的 这个词构成词链} 5.Top←Top+1; Word[Top]←St; 6.If Top>Max then 7. begin Max←Top; Ans←Word; end;更新Max的值 8.Readln(St);读入一个词 9.输出

? ? ? ? ?

2.队 (Queue)及其应用
2.1 队列 ( Queue )的概念

? 定义
– 队列是只允许在一端删除,在另一端插 入的顺序表 – 允许删除的一端叫做队头(front),允许 插入的一端叫做队尾(rear)。

? 特性
– 先进先出(FIFO, First In First Out)

队列的基本操作
1、构造一个队列 2、进队操作-----将新元素插入队尾 3、出队操作------队列头元素出队 4、取队列头元素 5、判定队列是否为空

队列的存储结构
?
?

顺序存储------循环队列 链式存储------链队

?

思考: 为什么要构造循环队列?

进队时队尾指针 rear = rear + 1,将新元素按 rear 指示位置加入。 ? 出队时队头指针 front = front + 1,再将下标为 front 的元素取出。 ? 思考:上图中,元素再进队,将如何?
?

出现“假上溢”现象
? ?

解决办法: 将存储数据元素的一维数组看成是头尾 相接的循环结构
即循环队列

?

循环队列的进队和出队
队头指针: front = (front + 1) % maxSize; 队尾指针: rear = (rear + 1) % maxSize; 队列初始化:front = rear = 0;

循环队列的队空队满问题
为了方便起见,约定: 初始化建空队时,令front=rear=0, ? 当队空时:front==rear ? 当队满时:front==rear 亦成立 ? 因此,只凭等式front=rear ? 无法判断队空还是队满。

有三种方法处理上述问题:
?

?

?

① 浪费一个单元。当使用MaxSize-1个单 元时即认为是队满, 此时 (rear+1) % MaxSize==front ② 设置一个布尔变量flag。当flag==flase 时为空,当flag==true时为满。 ③ 使用一个计数器记录队列中元素的个数。 如num,当num==0时队空, 当num==MaxSize时队满。

队列的链式存储结构

2.2 队列的应 用

问题1、 集合删数

问题描述: 一个集合有如下元素:1是集合元素;若P是集合的元素, 则2 * P +1,4*P+5也是集合的元素,取出此集合中最小的K 个元素,按从小到大的顺序组合成一个多位数,现要求从中 删除M个数位上的数字,使得剩下的数字最大,编程输出删除 前和删除后的多位数字。 注:不存在所有数被删除的情况` 输入格式: 输入的仅一行,K,M的值,K,M均小于等于30000。 输出格式: 输出为两行,第一行为删除前的数字,第二行为删除后 的数字。 样例输入: 5 4 样例输出: 137915 95

问题简述
问题由两个子问题组成: 1、 构造一个多位数:1是集合元素;若P是集合 的元素,则2 * P +1,4*P+5也是集合的元素,取出 此集合中最小的K个元素,按从小到大的顺序组合成 一个多位数 2、从多位数中删除M个数位上的数字,使得剩 下的数字最大

1、分析集合元素特点: 若P是集合的元素,则2 * P +1,4*P+5也是 集合的元素 ,即生成集合元素的函数是单调递增 的。 将2 * P +1与4*P+5产生的元素分成两个集 合,每次取两集合中最小的一个元素,显然只需 比较两集合中当前未被取走的第一个元素。 引入指针概念:设TOP1指向 2 * P +1当前 未被取走的第一个元素,TOP2指向4*P+5当前 未被取走的第一个元素。

比较TOP1,TOP2指向的元素,取最小的 一个,将取走元素队列的指针指向下一个元素。
例:生成5元素的集合数。 1 3 7 9 15 2 * P +1:3 7 15 19 4*P+5:9 17 33 41

a:=1; b:=1; p[1]:=1; For i:=2 to n do begin x:=p[a]*2+1; y:=p[b]*4+5; if x<=y then begin if x=y then inc(b); p[i]:=x; inc(a); end else begin p[i]:=y; inc(b); end; end;

2、分析
(1)贪心:高位越大越好; (2)因为数据很大,边取数字边处理, 处理原则是当前数留下,还是取代前面数 留下。 如:13751967 留下2位数 1 3 751 96 97

(3)当前数能否作为剩余序列的最高位? 能,则删除前面比自己小的数。 当前数是否取代前面留下的数的条件为: ①当当前数大于前面数时; ②总体保留位数(末删除数个数+末读入数 个数)大等于需留下的位数时; (4) 删除前面保留的数

算法伪代码:
? ? ? ?

?
? ?

?

?
? ? ?

设原数长度N,删除D位数 D := N - D;{留下数位数} Stack[0] := Chr(58);{字符9} Top := 1; For i := 1 to N do Begin 取出第i位数字C While (C > Stack[Top - 1]) And (Top + N - i > D) do Dec(Top);{如果当前位数字大于前面数字且已保 留数位个数与剩余数个数和大于需留下数位的个数,则 删除前面的数字} Stack[Top] := C; Inc(Top) End; For i := 1 to D do Write(Stack[i])

问题2:合并果子(NOIP2004提高组) 【问题描述】 在一个果园里,多多已经将所有的果子打了下来,而 且按果子的不同种类分成了不同的堆。多多决定把所有的 果子合成一堆。每一次合并,多多可以把两堆果子合并到 一起, 消耗的体力等于两堆果子的重量之和。可以看出,所 有的果子经过n-1次合并之后,就只剩下一堆了。多多在 合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家,所以多多在 合并果子时要尽可能地节省体力。假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务 是设计出合并的次序方案,使多多耗费的体力最少,并输 出这个最小的体力耗费值。

例如有3种果子,数目依次为1,2,9。可以先将1、 2堆合并,新堆数目为3,耗费体力为3。接着,将新堆 与原先的第三堆合并,又得到新的堆,数目为12,耗 费体力为12。 所以多多总共耗费体力=3+12=15。可以证明15 为最小的体力耗费值。

【输入格式】 输入包括两行,第一行是一个整数n(1<=n<=10000),表示果子的种类数。 第二行包含n个整数,用空格分隔,第i个整数ai(1<=ai<=20000)是第i种果子的数 目。 【输出格式】 输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保 证这个值小于2^31。

【输入样例】 3 129 【输出样例】 15

分析: 很明显,这道题是一道贪心的题目,可以证明,每次 取最小的两堆合并会使得最后的体力值最小。那么,这道 题的问题就在于怎么找最小的两堆果子了。 朴素方法:排序,合并,插入。 我们注意到,每次合并完果子会删掉两堆,并添加一 堆新的,如果采用线性表,时间复杂度将高达O(N^2), 对于N<=20000是不够的。 所以,我们考虑使用最小堆优化。

算法: 建立空堆; 读入数据,建立最小堆; 每次取两个堆顶元素合并,并插入合并后的数, 总共合并n-1次。

方法2:队列 朴素方法问题是时间浪费在每次的排序中,能 否根据本题特点进行改进呢? 构造两个队列old 和 new,old用来存储原有的 果子堆数,new用来存储每次合并得到的新果子堆 数,每次合并后累加耗费的体力即可。 要想得到最小的体力耗费值,则 old要按增序 排列,而NEW也是增序排列,很明显每次合并时 候是在old 和 new的首部,取两个最小值,合并之 后插入到 new尾部。 此种方法的好处是只需对old进行一次排序, 之后就不再需要排序,而是直接在old和 new的首 部取值就好了。

由于old的元素是从a[]中复制过来的,所 以我们可以对其进行插入排序,这样排序的 时间复杂度是 O(N*logN);但如果我们注意 观察的话,可以发现输入数据1<= ai<=20000,我们完全可以使用计数排序, 以空间换时间,使得时间复杂度降低到O(N)。 (fruit1.pas)

问题3
WINDOWS选自PKU2823

问题描述: 给你一个长度为N的数组,一个长为K 的滑动的窗体从最左移至最右端,你只能 见到窗口的K个数,每次窗体向右移动一位, 如下表:

你的任务是找出窗口在各位置时的max value,min value. 输入格式: 第1行n,k,第2行为长度为n的数组 输出格式: 2行,第1行每个位置的min value,第2行每个位置的 max value

样例: window.in 83 1 3 -1 -3 5 3 6 7 window.out -1 -3 -3 -3 3 3 335567 数据范围: 20%: n<=500; 50%: n<=100000; 100%: n<=1000000;

分析: 方法1:朴素算法 枚举WINDOWS左端位置,求得每个区间长度为K的 数中的最大值和最小值。效率为O(n*k)。 显然,在n次的k次中有许多的重复工作。 分析数据:以求区间最小值为例。

[ 1 3 -1 ] -3 5 3 6 7 q: {-1}, 最小值为-1 1 [ 3 -1 -3 ] 5 3 6 7 q:{-3} 新加入数小于-1,显然-1无用了,最小数为-3 1 3 [ -1 -3 5 ] 3 6 7 q:{-3,5 } 新加入数大于-3,保留,最小数为-3 1 3 -1 [ -3 5 3 ] 6 7 q:{-3,3} 新加入数小于5,显然5无用了,最小数为-3 1 3 -1 -3 [ 5 3 6 ] 7 q:{3,6} 新加入数大于3,保留,但-3已移出区间,删除,最 小 数为3 1 3 -1 -3 5 [ 3 6 7] q:{3,6,7} 新加入数大于6,保留,最 小数为3

总结操作过程:

把q序列看成一个队列,每次从尾部加入一个新的数, 如果它比队尾还小,则队尾的这个数不可能成为之后任何 一个区间的最小值, 删除队尾元素后入队,如果它比队 尾元素大,入队。同时,当队头留在队中的次数超过k时 队头数据出队,因为它不在下一个区间内了。这样,区间 的最小值总是当前队列的队头。依此类推,即可得解。

q序列为单调队列。它首先是一个队列,每一个时刻, 队列元素值是单调的,同时支持入队和出队,但是出队有 从队头出和队尾出两种。

方法2:单调队列,每个数都进队、出队一次,算法 效率为O(N)。 单调队列程序框架(以最小值为例) procedure work; {设原始数据存入q[i]中 } Var i,top,tail:longint; begin top:=1; tail:=1; queue[top]:=1; //队头指向q[i]中第一个数 for i:=2 to k do //前k个数的初始队列 begin while (top<=tail)and(q[queue[tail]]>=q[i]) do dec(tail);//队尾元素大于当前元素,出队 inc(tail); //当前元素入队 queue[tail]:=i; end;

min[1]:=q[queue[top]];//第1窗口最小值 for i:=2 to n-k+1 do //窗口左端位置 begin if queue[top]<i then inc(top);//如果队头 指向位置滑出窗口左端,队头出队 while (top<=tail)and(q[queue[tail]]>=q[i+k-1]) do dec(tail); );//队尾元素大于当前窗口右端元素, 出队 inc(tail); queue[tail]:=i+k-1;//当前窗口 右端元素入队 min[i]:=q[queue[top]];//取当前窗口最小 值 end;

二叉树
? ?

?

二叉树就是最多只有两个子节点的树 所有叶节点深度相同的二叉树为满二叉 树 深度为k且有n个节点的二叉树,当其每 一个节点都与深度为k的满二叉树中编号 从1至n的节点一一对应时,称之为完全 二叉树

多叉树转二叉树
用二叉树表示一棵树要比多叉树 简单些,而且多叉树都可以转换 成唯一的二叉树。 ? 对于多叉树中的每个节点,可以 用两个指针分别指向它的第一个 子节点和下一个相邻节点。
?

多叉转二叉的例子
5 5

在下图中, 每个节点的 左子节点为 它原来的第 一个子节点 ,右子节点 为它的第一 个兄弟节点

2

1

7

2

1

7

4

8

1

6

4

4

8

1

6

4

9

3 5 2

9

3

4
8 9

1
7 1

3

6 4

几类特殊的树形结构
? ? ? ?

二叉和N叉哈夫曼树 堆 二叉搜索(排序)树 并查集

哈夫曼树
?

哈夫曼树又称最优二叉树,是一种带权路径长度最 短的二叉树。所谓树的带权路径长度,就是树中所 有的叶结点的权值乘上其到根结点的路径长度(若 根结点为0层,叶结点到根结点的路径长度为叶结 点的层数)。树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个 权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树, 相应的叶结点的路径长度为Li(i=1,2,...n)。可以证 明哈夫曼树的WPL是最小的。

哈夫曼树
?

?

?

? ?

然而怎样构造一棵哈夫曼树呢?最具有一般规律的构造方 法就是哈夫曼算法。一般的数据结构的书中都可以找到其 描述: 一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n 棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵 二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均 为空。(为方便在计算机上实现算法,一般还要求以Ti的权 值Wi的升序排列。) 二、在F中选取两棵根结点权值最小的树作为新构造的 二叉树的左右子树,新二叉树的根结点的权值为其左右子 树的根结点的权值之和。 三、从F中删除这两棵树,并把这棵新的二叉树同样以 升序排列加入到集合F中。 四、重复二和三两步,直到集合F中只有一棵二叉树为 止。

构造二叉哈夫曼树
34 15

7 3 1 2
4

8

4

8

选取值最小的两个 根节点a和b。创建 一个新节点,其权 19 值就是a、b的权值 之和,左右子树分 9 10 别为a、b这两个节 点。 19 2. 重复1步骤,直至只 有一个根节点(即 所有节点都在同一 9 10 棵树中)。
1.

哈夫曼树应用
? ? ?

题目阐述:
以N进制编码方式对一个英文字串中的字符进行编码,每个不同的字符其编 码不同.使得由新的编码替代原串后总码长最小,且输入0,1,2,..., N-1构成的数字串后,依照该编码方式可以正确的对译出唯一的英文原串. 如: N=3 英文原串为 ABBCBADDACE 其对应的一种编码方式为 A:00 B:01 C:020 D:021 E:022 原串对译后的编码为000101020010002102100020 022 其码长为27 若输入编码串 0102002200 则对应的英文原串为 BCEA

? ? ? ? ? ? ? ? ? ? ?

哈夫曼树应用
? ? ? ? ? ? ?

?
?

假设英文原串中的字符存放于字符集S中,‖S‖= X,每个字 符在字串中出现的概率为W[i],L[i]为字符i的编码 长. 依题意得,对S集合中的不同字符进行N进制编码后要求 1)新字串的码长最短 WPL=∑W[i]*L[i] (i∈1..X) 使得在WPL是所有编码方式中的最小值 2)编码无二义性 任意一字符编码都不为其它字符编码的前缀 此题以哈夫曼树来解答是非常适宜的.N为此哈夫曼树的分叉数, S字符集里的元素即为此 N叉哈夫曼树的叶子,概率W[i]即为叶子结点的权重,从根 结点到各叶子结点的路径长即为该叶子结点的编码长L [i].由哈夫曼树的思想可以知道哈夫曼树的建立是一步到位 的贪心法,即权重越大的结点越靠近该树的根,这样,出现频率 越大的字符其编码就越短.

哈夫曼树应用
? ? ?

?
? ? ? ?

但具体应该怎样建立起此N叉哈夫曼树呢? 2叉哈夫曼树已经讲过,我们来看3叉。 N=3时又是怎样一种情况呢? 设 S={A,B,C,D,E} W=[7,4,2,5,3} 则按权重排序可得 S={A,D,B,E,C} W=[7,5,4,3,2]

哈夫曼树应用
? ? ? ? ? ? ? ? ? ? ?

那么此哈夫曼树的树形应为怎样呢? 不是 ? ? ? ? ? ? ? ?? ?? A ? ? ? ? D B E C

是以下的左图,还是右图,或是两者均 ? ? ? A ? ? ? ? ? ? D ? ? ? B ? ? ? ? ? E C

哈夫曼树应用
?

?

?

显然,要带权路径长WPL最短,那么, 此树的高度就应尽可能的小,由此可知 将此树建成 丰满N叉树是最合理的,于是我们尽量 使树每一层都为N个分枝. 这样,我们得到了初步算法。

哈夫曼树应用
?

? ? ?

类似2叉哈夫曼树,我们把每次取2个改 成每次取3个,对于 S={A,D,B,E,C} W=[7,5,4,3,2] 我们进行如下操作:

哈夫曼树应用

21

9

7

5

4

3

2

哈夫曼树应用
21 以0..N-1依次标记每个根结点的N 个分枝,则可以得到每个字符相对应的编 码: A:0 B:2 0 C:2 2 D:1 E:2 1

7 A

5 D 4 B 3 E

9

2 C

哈夫曼树应用
? ?

思考: 我们发现对于这种情况恰巧每层均为N 个分枝,但事实上并非所有的N叉哈夫 曼树都可得到每层N个分枝.例于当N =3,‖S‖=6时就不可能构成一棵每层 都为三个分枝的三叉树.如何来处理这 种情况呢 ?

哈夫曼树应用
?

? ? ? ? ?

最简单的处理方式就是添加若干出现概率为0的空字 符填补在N叉树的最下一层,这些权为0的虚结点并 无实际意义但却非常方全便于这棵N叉树的建立.空 字符的添加个数add的计算如下: Y=‖S‖ mod (n-1) add=0 (Y=1) add=1 (Y=0) add=N-Y (Y>1) 虚结点的加入使得权重最小的N-add个字符 构成了距根结点最远的分枝,使其它字符构成的N叉 树保持了丰满的N叉结构.

哈夫曼树应用
? ? ?

例: N=3 S={A,B,C,D,E,F} W=[1,2,3,4,5,6}
则 y:=6 mod (3-1)=0 -> add=1

于是构成N叉树如下: ? ? ? ? ? ? F E ? ? D

?为虚结点
? ? ? C

? ? ? ? ? B A ?

WPL=1*6+1*5+2*4+2*3 +3*2+3*1+3*0=33 对应编码为: A:221 B:220 C:21 D:20 E:1 F:0

哈夫曼树应用
?

由此可知,对于N叉二叉树我们也可以类 似处理。


? ?

堆是一种特殊的二叉树 它满足{V(左孩子)<V(根)>V(右孩子)}或 {V(左孩子)>V(根)<V(右孩子)}


?

我们如何建堆呢?如果需要O(N)去添加一 个元素,这就没有意义了,所以,我们 要用O(log2(N))把一个元素加进去。这样, 我们就可以在O(NlogN)的时间内建好堆。

堆(以小根堆为例)
1 3 6 1 3
7 6 3 1 1 7 3 6 8

2 5 5
7

5 2

3

建堆开始…… 建堆完毕

算法描述(建堆)
procedure build; for i:=1 to n do read(x); push(x); endf; endp;
begin inc(num); a[num]:=x; j:=x; i:=num; while a[i div 2]>a[i] do

swap(i,i div 2);
i:=i div 2; endw;

end;

堆——选择与维护
7 2 8 3 1 3 8
3 6 8 7 1 2 6 8 8 2 3 7

5
7

5

7 3

取出堆顶节点 二、调整 一、取出

算法描述(堆排序)
? ? ? ? ?

?

procedure sort; build; for i:=1 to n do writeln(a[1]); delete(1); endp;

类似于push,不过push是把小 元素向上换,delete是把最 小的删掉后,把最后一个元 素放上来,这样就变成了把 一个大元素向下放的过程, 具体方法请自己思考。

堆排序算法
? ? ? ? ? ?

?
? ?

PROC shift (var r:listtype; k,m:integer); i:=k.j:=2*I; x:=r[k].key;finish:=false t:=r[k]; while (j<=m) and not finish do [ if (j<m) and r[j].key>r[j+1].key) then j:=j+1; If x<=r[j].key then finish:=true Else [ r[i]:=r[j]; i:=j; j:=2*I ] ] r[i]:=t endP

? ? ? ? ?

PROC heapsort(var r:listtype); For i:=[n/2] downto 1 shift(r,I,n); For i:=n downto 2 do [ r[1]与r[i]交换; shift(r,1,i-1) ] endP

用堆优化dijstra算法
? ?

例题:最小序列问题。 给定一个N×N(N<=100)的正整数矩 阵。需要在矩阵中寻找一条从起始位置到 终止位置的路径(可沿上下左右四个方向), 并且要求路径中经过的所有数字,其相邻 数字之差的绝对值之和最小。

例题分析
这道题的基本算法很简单,只要用 Dijkstra算法求出从起始位置到终止位置的 最短路径即可。但这当中存在一个很大的问 题:N<=100。这就是说图中点的数目可能 多达10000个。此时复杂度为O(n2)的 Dijkstra算法就显得有些力不从心了。

例题分析
我们继续对算法进行分析。由于Dijstra算法通常采 用的是线性的数组结构,所以当我们每次寻找下一 条最短路径时,有两步需要进行: (1)找出一个不在最短路径起点集合内,并且到终点 距离最短的顶点i。这一步的复杂度显然为O(n)。 (2)修改从与i相邻的顶点到终点的路径长度。由于最 多只有4个点(四个方向)与i相邻,所以这一步的复杂 度为O(1)即常数
?

例题分析
这两步中,虽然第二步最多只改变了到4个点的路径长度,但是第一 步却还是需要枚举所有的数组元素,这显然很浪费时间。出于对第一步 进行改进的考虑,我们可以想到树结构中二叉堆的结构。堆结构的优点 是:根结点就是最优的结点,并且改变堆中某个结点的值以后,只需 O(log2n)的复杂度就可以完成堆化的过程(可分为从二叉树中自下而上和 自上而下两种堆化方法,并且复杂度都一样),使堆的结构发生改变后, 通过堆化仍然能够保留堆的性质。 如果我们采用二叉堆的结构存储距离,第一步就只需将根结点取出,并 且用堆中的另一结点代替后进行一次自上而下的堆化。因而第一步的复 杂度可降为O(log2n)。但是,此时的堆结构在进行第二步时暴露了很大的 缺点:无法预知i点的相邻点在堆中的位置。如果我们用对堆进行遍历来 寻找i的相邻点,第二步的复杂度又成为了O(n)。

?

例题分析
? ? ?

?

我们从这两种数据结构中不难发现这样规律:采用线性结构的数组,易 于进行第二步;采用树结构的二叉堆,做第一步时效果比较理想。 那么,我们是否可以将这两种数据结构进行结合,取长补短呢? 我们可以采用映射的方法,将线性结构中的元素与堆中间的结点一一对 应起来,若线性的数组中的元素发生变化,堆中相应的结点也接着变化 ,堆中的结点发生变化,数组中相应的元素也跟着变化。 将两种结构进行结合后,无论是第一步还是第二步,我们都不需对所有 元素进行遍历,只需进行常数次复杂度为O(log2n)的堆化操作。这样,整 个时间复杂度就成为了O(nlog2n),算法效率无疑得到了很大提高。

二叉搜索树
?

二叉查找树(Binary Search Tree),或者是 一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点 的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点 的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。

二叉搜索树
? ? ? ?

基本操作 1、查找元素 2、构造 3、删除

二叉排序树用于动态查找 查找
7
6

12
23

3
1 5 7

8
9

18

25
29

找到了!

二叉搜索树
? ?

查找相信大家都想得到。 根据性质只要每次查找时,符合则退出, 否则就在左孩子(查找值小于当前值) 或右孩子(查找值大于当前值)中继续 查找。

二叉搜索树的插入
在二叉搜索树上插入一个新元素,首先应搜索新元素的插 入位置。搜索插入位置要求在从根结点往下搜索的过程中,要 记录下当前元素的双亲结点,并以指针q指示。如果在搜索中遇 到相同关键字值的元素,则表明有重复元素,那么显示 “Duplicate”信息。搜索到达空子树时结束,表示二叉搜索树中 不包含待插入的新元素x,此时,指针q指向新元素插入后的双

亲结点。

二叉搜索树的插入
算法 构造一个新结点用以存放新元素x,设新结点由指针r指示。

如果原二叉搜索树是空树,则新结点*r 成为新二叉搜索树的根; 否则新结点*r将成为结点*q的孩子。如果新元素x的关键字值小

于q结点的关键字值,则*r将成为*q的左孩子,否则成为其右孩
子。

q 28 21

p 28 36 21

q p 36

25 (a) 28 21

33

25 (b) q 36 p 21 28

33

q 36 r

25 (c)

33

25 (d)

33

43

二叉搜索树的插入运算(X.Key=43) (a) p=Bt->Root; (b) q=p; p=p->Rchild; (c) q=p; p=p->Rchild; (d) r=NewNode2(x); q->Rchild=r

28 21 28 ? (a) 28 21 36 21 28 (b) 28 36 21 21 (c) 28 36 25 (d)

25 (e)

25 (f)

33

25

33 (g)

43

图8-3 二叉搜索树的构造过程 (a) 空树;(b) 插入28;(c) 插入21;(d) 插入25;(e) 插入36;(f) 插入33;(g) 插入43

二叉搜索树的删除
在二叉搜索树上删除一个结点也很方便。首先应搜索被删 除的元素。搜索删除元素的方法与插入元素的做法类似,要求 在从根结点往下搜索的过程中,记录下当前元素的双亲结点,

并用指针q指示。如果不存在该元素,那么显示“No element
with key”信息。如果存在待删除的结点,设其由指针p指示,则

删除结点*p的操作可分下面三种情况讨论。

二叉搜索树的删除
1)没有儿子,即为叶节点。直接把父节点的对应儿子指针设为 NULL,删除儿子节点就OK了。

2)只有一个儿子。那么把父节点的相应儿子指针指向儿子的独
生子,删除儿子节点也OK了。

二叉搜索树的删除
3)有两个儿子。这是最麻烦的情况,因为删除节点之后,还
要保证满足搜索二叉树的结构。其实也比较容易,我们可

以选择左儿子中的最大元素或者右儿子中的最小元素放到
待删除节点的位置,就可以保证结构的不变。当然,要记 得调整子树,毕竟又出现了节点删除。这里选择左儿子的 最大元素,将它放到待删节点的位置。左儿子的最大元素 其实很好找,只要顺着左儿子不断的去搜索右子树就可以

了,直到找到一个没有右子树的节点。那就是最大的了。

二叉搜索树的删除
10 3 8 2 1
Delete(5) Delete(15) Delete(2)

15 8 5 11 12 17

二叉搜索树
?

注意:二叉搜索树操作的时间复杂度最 好情况下(如无序数据)是O(NlogN), 但是如果是有序的,时间复杂度有可能 达到N^2,为了解决这个问题,人们提 出了不同的平衡方法。如Splay,AVL。

二叉搜索树的应用
?

试将一段英文中出现的单词按词典的顺 序打印出来,同时应注明每个单词在该 段文章中出现的次数。

例题分析
?

将一段英文中的单词按词典顺序打印的过程, 就是由 一个无序序列构造有序序列的过程,这个过程可以通 过构造二叉排序树实现。 设A={a1,a2,a3,...,an}为一组元素的集合, 则 按下列规则生成的二叉树就是一棵二叉排序树: (1)令a1为二叉树的根; (2)若a2<a1,则令a2为a1的左子树的根结点 ,否则,令a2为a1的右子树的根结点; (3)a3,a4,...,an递归重复步骤2。

例题分析
?

假设输入英文段落为: Everyone round you can hear you when you sperk 按算法构造的二叉排序树如图示。

二叉搜索树的应用
? ?

?

例题:寻找同名的学生。 某大学有三个系,每个系的学生名字单 独放在一个文本文件中,已知每个系的学 生人数不超过1000人。请编一程序,在这 所大学中寻找这样的名字,用该名字的人 数恰为M(M>0)。 注意:同一个系或系与系之间都有可能 出现同名现象。

?

二叉搜索树的应用
?

例题:寻找同名的学生。

[输入格式] ? 从键盘依次读入三个文本文件的文件名和M的值(每项占一行)。在每个文本文件中,一个学生的名字占一行(左边无空格), 姓名由3至10个大写英文字母组成,中间无空格。 [输出格式] ? 在屏幕上输出符合条件的名字,若有多个名字符合条件,须按字典顺序列出,每个名字占一行(左边无空格) [输入输出举例] ? 若有三个文件如下: ? math.txt computer.txt history.txt ? WANGLIN WANGQING WANGLIN ? ZHANGPIN LIHONG LINLING ? ZHAOPENG ZHAOPING WANGFAN ? WANGFAN ZHAOPENG ZHAOPIN ? LIUQING WANGLIN ? ZHAOPENG
? ? ? ? ?

输 入 math.txt computer.txt history.txt 3

输 出 WANGLIN ZHAOPENG

例题分析
?

这是一道比较简单的查找和统计问题。最容易想到的就使用一 个数组每一个出现的名字及出现的次数记录下来。这样每增加 一个节点,就要将当前节点与前面所有产生的节点进行比较。 这样最坏的情况下时间复杂度将达到3000*3000=9*10^6。 我们还会想到另一种方法,就使用单链表将名字从小大的连接 起来。这样,每新添一个节点,即从表头查找起,若找到相同 的则纪录下来,否则插入适当的位置。这样,时间复杂度会相 应的有所降低。对于查找,我们就不得不想到二叉排序树,如 果对此题构造一棵二叉排序树,对于每一个节点,左孩子存放 比父节点字串值小的字串,右孩子存放比父节点字串值大的字 串,,这样平均时间复杂度将降到O(log n)。

?

并查集

Disjoint Sets
?

? ? ?

?

并查集是一种树型的数据结构,用于处 理一些不相交集合的合并问题。 并查集的主要操作有 1-合并两个不相交集合 2-判断两个元素是否属于同一个集合 3-路径压缩

元素的合并图示
1 2 3 4 5

合并1和2

合并1和3
合并5和4 合并5和3

判断元素是否属于同一集合
?

用father[i]表示元素i的父亲结点,如刚 才那个图所示
1 faher[1]=1 faher[2]=1 faher[3]=1 2 3

5

faher[4]=5 faher[5]=3

4

判断元素是否属于同一集合
?

?

?

由此用某个元素所在树的根结点表示该 元素所在的集合 判断两个元素时候属于同一个集合的时 候,只需要判断他们所在树的根结点是 否一样即可 也就是说,当我们合并两个集合的时候, 只需要在两个根结点之间连边即可

并查集的操作
判断两个节点是否在同一个集合中 1 4 2. 合并两个集合
1.

2

5

3

10 8 8 77

6 10 维护并查集 并查集操作的关键 ——

11
判断5与 合并 10是否在同一个集合中 11和10所在的集合 第二步:合并 第二步:上调 第三步:上调 第一步:上溯

路径压缩
?

?

上述的做法是指就是将元素的父亲结点 指来指去的在指,当这课树是链的时候, 可见判断两个元素是否属于同一集合需 要O(N)的时间,于是路径压缩产生了作 用 路径压缩实际上是在找完根结点之后, 在递归回来的时候顺便把路径上元素的 父亲指针都指向根结点

路径压缩示意图
1 2 3 4 5

由此我们得到了一个复杂度只是O(1)的算法

程序清单
? ? ? ? ? ? ? ? ? ?

function getfather(v:integer):integer; begin if (father[v]=0) then getfather:=v else begin father[v]:=getfather(father[v]); getfather:=father[v]; end; end;

程序清单
? ? ? ? ? ?

?
? ?

function judge(x,y:integer):boolean; var fx,fy : integer; begin fx := getfaher(x); fy := gefather(y); If fx=fy then judge := exit(true) else judge := false; father[fx] := fy;{合并两个集合} end;

例1 亲戚
?

?

若某个家族人员过于庞大,要判断两个 是否是亲戚,确实还很不容易,现在给 出某个亲戚关系图,求任意给出的两个 人是否具有亲戚关系。 规定:x和y是亲戚,y和z是亲戚,那么x 和z也是亲戚。如果x,y是亲戚,那么x的 亲戚都是y的亲戚,y的亲戚也都是x的亲 戚。

例1 亲戚
? ?

?

?

?
?

数据输入: 第一行:三个整数n,m,p, (n<=5000,m<=5000,p<=5000),分别表示有n个 人,m个亲戚关系,询问p对亲戚关系。 以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表 示Ai和Bi具有亲戚关系。 接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有 亲戚关系。 数据输出: P行,每行一个’Yes’或’No’。表示第i个询问的答案 为“具有”或“不具有”亲戚关系。

例1 亲戚
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

样例: input.txt 653 12 15 34 52 13 14 23 56 output.txt Yes Yes No

例1 亲戚
? ?

这个题目是最基础的并查集问题 运用基本的并查集工具就可以解决了

例2 银河英雄传说(NOI2002)
?

?

公元五八○一年,地球居民迁移至金牛座α第 二行星,在那里发表银河联邦创立宣言,同年 改元为宇宙历元年,并开始向银河系深处拓展。 宇宙历七九九年,银河系的两大军事集团在巴 米利恩星域爆发战争。泰山压顶集团派宇宙舰 队司令莱因哈特率领十万余艘战舰出征,气吞 山河集团点名将杨威利组织麾下三万艘战舰迎 敌。

例2 银河英雄传说(NOI2002)
?

杨威利擅长排兵布阵,巧妙运用各种战术屡次以少胜 多,难免恣生骄气。在这次决战中,他将巴米利恩星 域战场划分成30000列,每列依次编号为1, 2, …, 30000。之后,他把自己的战舰也依次编号为1, 2, …, 30000,让第i号战舰处于第i列(i = 1, 2, …, 30000), 形成“一字长蛇阵”,诱敌深入。这是初始阵形。当 进犯之敌到达时,杨威利会多次发布合并指令,将大 部分战舰集中在某几列上,实施密集攻击。合并指令 为M i j,含义为让第i号战舰所在的整个战舰队列,作 为一个整体(头在前尾在后)接至第j号战舰所在的战 舰队列的尾部。显然战舰队列是由处于同一列的一个 或多个战舰组成的。合并指令的执行结果会使队列增 大。

例2 银河英雄传说(NOI2002)
?

?

然而,老谋深算的莱因哈特早已在战略上取得了主动。 在交战中,他可以通过庞大的情报网络随时监听杨威 利的舰队调动指令。 在杨威利发布指令调动舰队的同时,莱因哈特为了及 时了解当前杨威利的战舰分布情况,也会发出一些询 问指令:C i j。该指令意思是,询问电脑,杨威利的第

i号战舰与第j号战舰当前是否在同一列中,如果在同一 列中,那么它们之间布置有多少战舰。
? ?

作为一个资深的高级程序设计员,你被要求编写程序 分析杨威利的指令,以及回答莱因哈特的询问。 最终的决战已经展开,银河的历史又翻过了一页……

例2 银河英雄传说(NOI2002)
? ? ?

?

输入文件galaxy.in的第一行有一个整数T (1<=T<=500,000),表示总共有T条指令。 以下有T行,每行有一条指令。指令有两种格式: 1. M i j :i和j是两个整数(1<=i , j<=30000), 表示指令涉及的战舰编号。该指令是莱因哈特窃听到 的杨威利发布的舰队调动指令,并且保证第i号战舰与 第j号战舰不在同一列。 2. C i j :i和j是两个整数(1<=i , j<=30000), 表示指令涉及的战舰编号。该指令是莱因哈特发布的 询问指令。

例2 银河英雄传说(NOI2002)
? ?

?

输出文件为galaxy.out。你的程序应当依次对输入的 每一条指令进行分析和处理: 如果是杨威利发布的舰队调动指令,则表示舰队排 列发生了变化,你的程序要注意到这一点,但是不 要输出任何信息; 如果是莱因哈特发布的询问指令,你的程序要输 出一行,仅包含一个整数,表示在同一列上,第i号 战舰与第j号战舰之间布置的战舰数目。如果第i号战 舰与第j号战舰当前不在同一列上,则输出-1。

例2 银河英雄传说(NOI2002)
? ? ? ? ? ?

?
? ?

样例输入 4 M23 C12 M24 C42 样例输出 -1 1

例2 银河英雄传说 (NOI2002)
第一列 第二列 第三列 第四列 …… 初始时 1 2 3 4 ……

M23

1

3 2

4

……

C12

1号战舰与2号战舰不在同一列,因此输出-1

M24

1

4 3 2

……

C42

4号战舰与2号战舰之间仅布置了一艘战舰,编号为3,输出1

例2 银河英雄传说(NOI2002)
?

? ?

?
?

这一题需要增加两个域,一个表示该元 素所在集合中元素的总个数,用count表 示;另一个是在该集合中,这个元素之 前有多少个元素,用before表示。 初始的时候 father[i] := i; count[i] := 1; before[i] := 0;

例2 银河英雄传说(NOI2002)
? ? ? ? ?

?
? ? ? ? ? ? ? ?

路径压缩 Function getfather(v:longint):longint; var f:longint; begin if father[v]=v then getfather:=v else begin f:=getfather(father[v]); before[v]:=before[father[v]]+before[v];{这里是关键} father[v]:=f; getfather:=father[v]; end; end;

例2 银河英雄传说(NOI2002)
? ? ? ? ? ? ? ? ?

归并操作 Procedure merge(x,y:longint); var i,j:longint; begin i:=getfather(x); j:=getfather(y); father[i]:=j; before[i]:=before[i]+count[j]; count[j]:=count[j]+count[i];{做相应的修改} end;

例2 银河英雄传说(NOI2002)
?
? ? ? ? ?

询问操作
Procedure ask(x,y:longint); begin if getfather(x)<>getfather(y) then writeln(-1) else writeln(abs(before[x]-before[y])-1); end;

?

这一题中在量与量的处理中加入了一些附加的 信息,但只要你理清了并查集的基本思路,本 题也就通过上面三个简单的过程解决了。

例3 食物链(NOI2001)
?

?

? ? ?

动物王国中有三类动物A,B,C,这三类动物的 食物链构成了有趣的环形。A吃B, B吃C,C吃 A。 现有N个动物,以1-N编号。每个动物都是 A,B,C中的一种,但是我们并不知道它到底是 哪一种。 有人用两种说法对这N个动物所构成的食物链 关系进行描述: 第一种说法是“1 X Y”,表示X和Y是同类。 第二种说法是“2 X Y”,表示X吃Y。

例3 食物链(NOI2001)
?

? ? ? ?

此人对N个动物,用上述两种说法,一句接一句地说出 K句话,这K句话有的是真的,有的是假的。当一句话 满足下列三条之一时,这句话就是假话,否则就是真 话。 1-当前的话与前面的某些真的话冲突,就是假话; 2-当前的话中X或Y比N大,就是假话; 3-当前的话表示X吃X,就是假话。 你的任务是根据给定的N(1<=N<=50,000)和K句话 (0<=K<=100,000),输出假话的总数。

例3 食物链(NOI2001)
? ?

? ?

?
?

输入文件 第一行是两个整数N和K,以一个空格分隔。以 下K行每行是三个正整 D,X,Y,两数之间用 一个空格隔开,其中D表示说法的种类。 若D=1,则表示X和Y是同类。 若D=2,则表示X吃Y。 输出文件 只有一个整数,表示假话的数目。

例3 食物链(NOI2001)
输入文件 100 7 1 101 1 2 1 2 2 2 3 假话 真话 真话 对7句话的分析

2 3 3
1 1 3 2 3 1

假话
假话 真话

1 5 5

真话

例3 食物链(NOI2001)
?

?

很显然,对假话条件2、3的处理十分简单,只要在读 入数据时作两个条件判断即可解决,题目的主要任务 在于处理条件1。 从表面上看,条件1的处理似乎也没有什么难度:一 个动物无非就是A,B,C三类,而A,B,C之间的食物链关 系是一对一单向环形的,也就是说如果已知动物X所属 种类和X、Y之间的食物链关系,就一定可以确定出动 物Y的种类,同时某个动物具体属于哪一类并不影响本 题的结果,而只要求它与其他动物关系的相对位置正 确即可。

例3 食物链(NOI2001)
?

于是,我们不妨开3个数组A,B,C,分别 记录着三种类的成员,首先假设第一句 有效话中的动物X为A类,将其放入数组A, 倘若Y与X同类,则把Y也放入A;若Y被X 吃,则将Y放入B,如此反复操作所有的 有效话,就可以确定每个动物的种类, 并容易统计出假话的个数。

例3 食物链(NOI2001)
?

?

?

问题似乎已经圆满地解决了,但是,稍稍认真 思考就会发现,上面的这个算法存在着重大的 错误,是十分片面的。 对于一个未知属性的生物我们都采取的是定义 为A类型,这样子显然是错的。 可见,这个算法只能当每一句话都可直接与此 前已知的食物链建立明确关系的时候才能使用。

例3 食物链(NOI2001)
?

明确了上面这个关系,我们就不难从刚才的算法扩展 出另一种算法:对于目前关系未知的动物X,我们为他 新开辟一条食物链A2,B2,C2,显然,在这个新的组中, 动物X所在的种类也是随意的,于是假设它在A2组,这 样,所有与X的关系就可用与算法1同样的方式加入这 个组中,而这个组与原先的组A1,B1,C1的关系是不确 定的。如此反复,我们也可以得到组3、组4、组5……, 一旦有一句话牵涉到某两个组的成员之间的食物链关 系,我们就依据一定的换算规则将这两个组合并起来, 以保证关系网的完整性。

例3 食物链(NOI2001)
?

?

通过上面的分析,并查集在本题中的运 用已经呼之欲出。 一个集合有三类的元素,合并集合的时 候,需要对三类元素进行合并。

Parity(ceoi99)
?

?

?

有一个01序列,长度<=1000000000,现在有n条 信息,每条信息的形式是-a b even/odd。表示 第a位到第b位元素之间的元素总和是偶数/奇 数。 你的任务是对于这些给定的信息,输出第一个 不正确的信息所在位置-1。信息的数目不超过 5000。 如果信息全部正确,即可以找到一个满足要求 的01序列,那么输出n。

Parity(ceoi99)
? ? ? ? ? ? ? ? ? ? ? ? ?

输入文件 第一行一个整数m表示01序列的长度,第二行一个整数n表示信息 的数目。 接下来是n条信息 样例输入 10 5 1 2 even 3 4 odd 5 6 even 1 6 even 7 10 odd 样例输出 3{因为第4个信息是不正确的,所以输出3,表示从1到3条信息都 是正确的}

Parity(ceoi99)
?

?

?

?

从整个01序列肯定是无法入手的,因为 它的长度高达109。 从范围比较小的n入手。也就是说我们需 要对信息进行一些特殊的处理。 a b even/odd,那么将元素b指向a-1, 边的权值是even/odd。 下面我们由样例来说明一下这个处理方 法。

Parity(ceoi99)
0 2 4 6
0

1

0???

1 3 5 1

2 4 6 6

even odd even even

0

Parity(ceoi99)
?

?

?

?

显然在第4条信息加入的时候,6到0已经有值 存在,即(0+1+0)mod 2=1,这时添入6到0为 0显然是不对。 实现的时候不用开1-109的数组,因为出现的不 同元素最多有104而已,因此,开一个列表存 储元素即可。 算法的大致框架就是对于读入的信息不断地用 上述方法处理,由区间的递推性质可以得出矛 盾与否。 上述算法的实现就用到了并查集。

Disjoint Sets小结
?

?

?

先从问题的简单做法入手,构造出原始 模型。 如果原始模型是对于集合之间合并处理 问题,那么就可以使用并查集使得程序 变得高效。 并查集的路径压缩只有在元素之间的特 性存在递推关系时才可以使用。


相关文章:
数据结构(第3版)习题答案
【答】:数据结构涉及个方面的内容,即数据的逻辑结构、数据的存储结构和数据的...在为函数 f 提供一个上限函数 g 时,通常使用比较 简单的函数形式。比较典型的...
数据结构 第3章习题答案
数据结构3章习题答案_IT认证_资格考试/认证_教育专区。数据结构 ...线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。错,...
排队方式(交换)
day3简单数据结构 暂无评价 121页 2财富值 杨韧发展有限公司销售方案 3页 20财富值 小米手机6种刷机详细教程-... 27页 免费 概率 6页 免费如要投诉违规内容,...
数据结构课后习题3
数据结构课后习题3_理学_高等教育_教育专区。3.1 有 5 个元素,其进栈次序为:A、B、C、D、E,在各种可能的出栈次序中,以元素 C、 D 最先出栈(即 C 第一...
数据结构(第3版)习题答案2014-9
数据结构(第3版)习题答案2014-9_理学_高等教育_教育专区。 十二五普通高等教育...在为函数 f 提供一个上限函数 g 时,通常使用比较 简单的函数形式。比较典型的...
数据结构与算法第3章课后答案
数据结构与算法第3章课后答案_工学_高等教育_教育专区。数据结构与算法 课后答案 第3 章 特殊线性表——栈、队列和串 (2005-07-14) - 第 3 章 特殊线性表...
数据结构第3章作业
数据结构3章作业_IT认证_资格考试/认证_教育专区。数据结构作业 第3章 栈和队列作业 1 若用一个大小为 6 的数组来实现循环队列,且当 rear 和 front 的 ...
北语15春《数据结构》作业3及答案
北语15春《数据结构》作业3及答案_司法考试_资格考试/认证_教育专区。北语15春...A、插入、删除操作更简单 B、可以进行随机访问 C、可以省略表头指针或表尾指针...
数据结构上机题答案 3
数据结构上机题答案 3_IT认证_资格考试/认证_教育专区。数据结构 实验《数据结构》上机考题(A 卷) 试题:建立一个数据为整型的单链表 L,然后将该链表中数据域值...
数据结构练习3答案
数据结构练习()参考一、选择题 1.顺序查找法适合于存储结构为 A)哈希存储 C)压缩存储 至少比较___次。 A)9 A)n B)8 B)n/2 C)7 C) (n+1)/2 ...
更多相关标签:
通达信 day 数据结构 | 数据结构简单图 | 最简单的数据结构 | 数据结构简单吗 | 数据结构实验3 | discuz3.2数据库结构 | 数据结构实验报告3 | 严蔚敏数据结构视频3 |