数据结构基础

数据结构基础

数据结构基础全文共101页，当前为第1页。《数据结构》概念

数据结构研究计算机非数值计算问题中的数据对象以及它们之间的关系和操作算法，具体主要包含三个方面的内容：①数据的逻辑结构--数据关系之间的逻辑关系②数据的存储结构--数据的逻辑结构在计算机中的表示③操作算法----插入、删除、修改、查询、排序等

程序=数据结构+算法

数据结构基础全文共101页，当前为第2页。其中，数据的逻辑结构：集合线性结构-----表、栈、队列非线性结构-----树、图数据的存储结构：

顺序存储结构-----数组链式存储结构-----指针。数据结构基础全文共101页，当前为第3页。数据结构主要强调两个方面的内容：①数据之间的关系，即数据之间的逻辑结构和存储结构；②针对这些关系的基本操作。类与数据结构之间的对应关系:数据结构基础全文共101页，当前为第4页。1.栈(Stack)及其应用1。1栈的概念只允许在一端插入和删除的表允许插入和删除的一端称为栈顶

(top)，另一端称为栈底(bottom)特点后进先出(LIFO)数据结构基础全文共101页，当前为第5页。进栈示例

数据结构基础全文共101页，当前为第6页。出栈示例数据结构基础全文共101页，当前为第7页。栈的基本操作1、初始化2、进栈PUSH3、出栈POP4、取栈顶元素GetTop5、判栈是否非空数据结构基础全文共101页，当前为第8页。1。2栈的应用NOIP2005试题：《等价表达式》问题描述明明进了中学之后，学到了代数表达式。有一天，他碰到一个很麻烦的选择题。这个题目的题干中首先给出了一个代数表达式，然后列出了若干选项，每个选项也是一个代数表达式，题目的要求是判断选项中哪些代数表达式是和题干中的表达式等价的。这个题目手算很麻烦，因为明明对计算机编程很感兴趣，所以他想是不是可以用计算机来解决这个问题。假设你是明明，能完成这个任务吗？这个选择题中的每个表达式都满足下面的性质：

数据结构基础全文共101页，当前为第9页。

表达式只可能包含一个变量‘a’。表达式中出现的数都是正整数，而且都小于10000。表达式中可以包括四种运算‘+’（加），‘-’（减），‘*’（乘），‘^’（乘幂），以及小括号‘(’，‘)’。小括号的优先级最高，其次是‘^’，然后是‘*’，最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运算从左到右进行。（注意：运算符‘+’，‘-’，‘*’，‘^’以及小括号‘(’，‘)’都是英文字符）幂指数只可能是1到10之间的正整数（包括1和10）。表达式内部，头部或者尾部都可能有一些多余的空格。下面是一些合理的表达式的例子：((a^1)^2)^3，a*a+a-a，((a+a))，9999+(a-a)*a，1+(a-1)^3，1^10^9……数据结构基础全文共101页，当前为第10页。输入文件输入文件equal.in的第一行给出的是题干中的表达式。第二行是一个整数n（2<=n<=26），表示选项的个数。后面n行，每行包括一个选项中的表达式。这n个选项的标号分别是A，B，C，D……

输入中的表达式的长度都不超过50个字符，而且保证选项中总有表达式和题干中的表达式是等价的。输出文件输出文件equal.out包括一行，这一行包括一系列选项的标号，表示哪些选项是和题干中的表达式等价的。选项的标号按照字母顺序排列，而且之间没有空格。样例输入(a+1)^23(a-1)^2+4*aa+1+aa^2+2*a*1+1^2+10-10+a-a样例输出AC数据结构基础全文共101页，当前为第11页。关键：如何判断表达式等价？方法1：展开表达式直接比对，显然不可取。方法2：求表达式的值，比对表达式的值。但对于个体值有可能出现等价的表达式其值相等。引入随机化思想，随机产生几个a的值，当对每个随机产生的a值表达式值都相等时视为表达式等价。问题转换：如何求表达式的值。利用栈实现表达式计算。对表达式运算符定义运算优先级。算法描述：数据结构基础全文共101页，当前为第12页。设立运算符栈和操作数栈，逐词读入表达式，并处理：1、若读入为操作数，则入栈；2、若读入为运算符，则与栈顶运算符相比较：（1）若栈顶运算符优先级高于或等读入运算符，反复执行下列操作，直到栈顶运算符优先级不高于读入运算符：弹出运算符，弹出两个操作数，计算并将结果入操作数栈；（2）若栈顶运算符优先级低于读入运算符，则将读入运算符入栈；

3、若遇到结束运算符，则计算结束。4、检查栈状态，得到计算结果。程序表达：阅读equal.pas数据结构基础全文共101页，当前为第13页。2.1队列(

Queue)的概念定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)2.队(Queue)及其应用数据结构基础全文共101页，当前为第14页。队列的基本操作1、构造一个队列2、进队操作-----将新元素插入队尾3、出队操作------队列头元素出队4、取队列头元素5、判定队列是否为空数据结构基础全文共101页，当前为第15页。队列的存储结构顺序存储------循环队列链式存储------链队思考:为什么要构造循环队列?

数据结构基础全文共101页，当前为第16页。

进队时队尾指针rear=rear+1，将新元素按

rear

指示位置加入。出队时队头指针front=front+1，再将下标为front的元素取出。

思考：上图中，元素再进队，将如何？数据结构基础全文共101页，当前为第17页。出现“假上溢”现象

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

数据结构基础全文共101页，当前为第18页。循环队列的进队和出队队头指针:front=(front+1)%maxSize;队尾指针:rear=(rear+1)%maxSize;队列初始化：front=rear=0;数据结构基础全文共101页，当前为第19页。循环队列的队空队满问题为了方便起见，约定：初始化建空队时，令front=rear=0,

当队空时：front==rear

当队满时：front==rear亦成立

因此，只凭等式front=rear

无法判断队空还是队满。

数据结构基础全文共101页，当前为第20页。有三种方法处理上述问题：

①浪费一个单元。当使用MaxSize-1个单元时即认为是队满,此时

(rear+1)%MaxSize==front②设置一个布尔变量flag。当flag==flase时为空，当flag==true时为满。③使用一个计数器记录队列中元素的个数。如num，当num==0时队空，当num==MaxSize时队满。数据结构基础全文共101页，当前为第21页。队列的链式存储结构数据结构基础全文共101页，当前为第22页。2.2队列的应用WINDOWS选自PKU2823问题描述：给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：数据结构基础全文共101页，当前为第23页。你的任务是找出窗口在各位置时的maxvalue,minvalue.输入格式：第1行n,k,第2行为长度为n的数组输出格式：2行，第1行每个位置的minvalue,第2行每个位置的maxvalue数据结构基础全文共101页，当前为第24页。样例：window.in8313-1-35367window.out-1-3-3-333335567数据范围：20%：n<=500;50%:n<=100000;100%:n<=1000000;数据结构基础全文共101页，当前为第25页。分析：方法1：朴素算法枚举WINDOWS左端位置，求得每个区间长度为K的数中的最大值和最小值。效率为O(n*k)。显然，在n次的k次中有许多的重复工作。分析数据：以求区间最小值为例。[13-1]-35367q:{-1},最小值为-11[3-1-3]5367q:{-3}新加入数小于-1,显然-1无用了，最小数为-313[-1-35]367q:{-3，5}新加入数大于-3，保留，最小数为-313-1[-353]67q:{-3，3}新加入数小于5,显然5无用了，最小数为-313-1-3[536]7q:{3，6}新加入数大于3，保留，但-3已移出区间，删除，最小数为313-1-35[367]q:{3，6，7}新加入数大于6，保留，最小数为-3

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

q序列为单调队列。它首先是一个队列，每一个时刻，队列元素值是单调的，同时支持入队和出队，但是出队有从队头出和队尾出两种。数据结构基础全文共101页，当前为第27页。方法2：单调队列，每个数都进队、出队一次，算法效率为O(N)。

procedurework; {设原始数据存入q[i]中}Vari,top,tail:longint;

begin top:=1;tail:=1; queue[top]:=1;//队头指向q[i]中第一个数

fori:=2tokdo//前k个数的初始队列

begin while(top<=tail)and(q[queue[tail]]>=q[i])dodec(tail);//队尾元素大于当前元素，出队

inc(tail); //当前元素入队

queue[tail]:=i; end;

单调队列程序框架（以最小值为例）数据结构基础全文共101页，当前为第28页。min[1]:=q[queue[top]];//第1窗口最小值

fori:=2ton-k+1do//窗口左端位置

beginifqueue[top]<itheninc(top);//如果队头指向位置滑出窗口左端，队头出队

while(top<=tail)and(q[queue[tail]]>=q[i+k-1])dodec(tail); );//队尾元素大于当前窗口右端元素，出队

inc(tail); queue[tail]:=i+k-1;//当前窗口右端元素入队

min[i]:=q[queue[top]];//取当前窗口最小值

end; end;

数据结构基础全文共101页，当前为第29页。

3.二叉树

3.1二叉树的定义

二叉树是一类特殊的树.(1)二叉树中的每个结点至多只有两棵子树,即二叉树中不存在度大于二的结点.(2)二叉树的由三个基本单元构成:根结点,左子树,右子树.(3)二叉树的左右子树有次序之分,顺序不能颠倒.二叉树的基本形态:数据结构基础全文共101页，当前为第30页。3.2二叉树的遍历

问题的提出：在二叉树的一些应用中，为了在树中查找具有某种特征的结点，或者对树中的全部结点逐一进行处理。这样就提出了一个遍历二叉树的问题，即如何按某条搜索路径寻访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义很广，可以是对结点进行处理，如输出结点的信息等等。因此对二叉树而言：可以有三条搜索路径：（1）先上后下的按层次搜索（2）先左子树，后右子树的遍历（3）先右子树，后左子树的遍历数据结构基础全文共101页，当前为第31页。遍历二叉树二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L：遍历左子树

D：访问根结点

R：遍历右子树

有六种遍历方法：

DLR，LDR，LRD，

DRL，RDL，RLD

约定先左后右,有三种遍历方法：DLR、LDR、LRD

，分别称为

先序遍历（先根遍历）、中序遍历（中根遍历）、后序遍历（后根遍历）

A

F

G

E

D

C

B数据结构基础全文共101页，当前为第32页。

先序遍历（DLR）若二叉树非空

（1）访问根结点；（2）先序遍历左子树；

（3）先序遍历右子树；

先序遍历序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B例：先序遍历右图所示的二叉树（1）访问根结点A

（2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树数据结构基础全文共101页，当前为第33页。中序遍历（LDR）若二叉树非空

（1）中序遍历左子树

（2）访问根结点（3）中序遍历右子树

中序遍历序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍历右图所示的二叉树（1）中序遍历左子树：即按LDR的顺序遍历左子树（2）访问根结点A

（3）中序遍历右子树：即按LDR的顺序遍历右子树数据结构基础全文共101页，当前为第34页。后序遍历（LRD）若二叉树非空

（1）后序遍历左子树

（2）后序遍历右子树（3）访问根结点

后序遍历序列：D,G,E,B,F,C,A例：后序遍历右图所示的二叉树（1）后序遍历左子树：即按LRD的顺序遍历左子树（2）后序遍历右子树：即按LRD的顺序遍历右子树（3）访问根结点A

A

F

G

E

D

C

B数据结构基础全文共101页，当前为第35页。

e

d

c

b

f

a

+

*

/

-

-后序遍历序列：abcd-*+ef/-表达式的逆波兰表示（后缀表达式）中序遍历序列：a+b*c-d-e/f中缀表达式先序遍历序列：-+a*b-cd/ef表达式的波兰表示（前缀表达式）例：先序遍历、中序遍历、后序遍历下图所示的二叉树数据结构基础全文共101页，当前为第36页。

问题1、求先序排列给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。数据结构基础全文共101页，当前为第37页。[分析]我们知道一个后序排列的最后一个字符即为这棵树的根结点,而这个字符在中序排列中的位置n,n左边即为其左子树,n右边即为其右子树.并且由于中序遍历我们是先遍历左子树,然后根结点,再遍历右子树,而后序遍历我们是先遍历左子树,再遍历右子树,最后根结点.所以中序编历和后序遍历的第1到n-1位同为当前根结点的左子树,而中序遍历的第n+1到length(st)和后序遍历的第n到length(st)-1位同为当前根结点的右子树.根据先序遍历的规则,我们就先递归处理左子树,然后递归处理右子树,每次输出当前的根结点,即为先序排列.数据结构基础全文共101页，当前为第38页。程序步骤：1、

后序最右端即为根结点，输出；2、

在中序中找到根结点位置S，则该根结点的左边即为左子树，右边即为右子树，且后序中1-s为左子树，s至串长-1为右子树；3、

以中序与后序的1~s串，递归转1，则得到左子树的先序结果；4、

以中序的s+1~L-S,后序的S~L-S为串，递归转1，则得到右子树的先序结果5、

递归过程如图。数据结构基础全文共101页，当前为第39页。

procedurefind(a,b:string);{a为中序串,b为后序串}vars,l:integer;beginL:=length(b);ifL=1thenwrite(b)elsebeginwrite(b[L]);{输出根结点}s:=pos(b[L],a);{寻找根结点在中序排列中的位置}ifs-1>0thenfind(copy(a,1,s-1),copy(b,1,s-1));{处理左子树}ifL-s>0thenfind(copy(a,s+1,L-s),copy(b,s,L-s));{处理右子树}end;end;

数据结构基础全文共101页，当前为第40页。问题2、后缀表达式

所谓后缀表达式，是我们通常用的中缀表达式的另一种形式。中缀表达式的运算符的位置是在它所要计算的两个表达式之间的，而后缀表达式则是在其后面。比如有一个中缀表达式如下：

(<表达式1>)<运算符>(<表达式2>)

要将其转成后缀表达式，则要先递归地将<表达式1>和<表达式2>转成后缀表达式，然后将其变成

<表达式1><表达式2><运算符>

我们一般不习惯这样的表示方式，但好在我们可以用栈轻松处理掉它。具体方法是：从左到右扫描整个表达式，当我们扫描到数时，将其加入栈中，当我们扫描到运算符时，取出两个栈顶元素，计算出结果后重新加入栈中。这样最终栈中只会剩下一个元素，该元素就是整个表达式的计算结果。数据结构基础全文共101页，当前为第41页。

现在假设我们有的不是栈而是队列，我们也希望能用相同的操作方式处理一个表达式。唯一不同的是，队列每次加入元素是在队尾，而取出元素是在队头，所以就不适用在原先的后缀表达式上了。我们需要找到另一种表达式使得其适合于队列用相同的方法处理并得出相同的结果。InputFormat

输入文件第一行包含一个整数N，表示总共有N个后缀表达式需要处理。以下N行每行有一个后缀表达式，其中数用小写字母表示，运算符用大写字母表示。OutputFormat

输出文件共有N行，对于每个后缀表达式，输出适合于队列的另一种形式。数据结构基础全文共101页，当前为第42页。SampleInput1xyPwzIMSampleOutputzwyxIPMDataLimit对于50%的数据，所有后缀表达式的长度不超过1000；对于100%的数据，有1≤N≤20，所有后缀表达式的长度不超过10000。数据结构基础全文共101页，当前为第43页。分析：右图表达式树的后辍表达式为abcd-*+ef/-后辍表达式的栈处理过程：（1）abcd入栈，遇-，栈顶cd出栈运算后入栈；(2)abc-d，遇*，b*(c-d)入栈；(3)ab*(c-d)，遇+，a+b*(c-d)入栈；ef入栈；(4)a+b*(c-d)ef，遇/，e/f入栈；(5)a+b*(c-d)e/f，遇-，a+b*(c-d)-e/f题意简述：将适用于栈的普通后缀表达式，转化为适用于队列的符号置后的表达式。-+/a*efbc-d数据结构基础全文共101页，当前为第44页。如何写成队的处理的后辍表达式呢？队：先进先出对表达式a+b*(c-d)-e/f(1）cd遇-形成c-d后入队能够继续下面的运算队后辍为cdb-bc-d遇*形成b*(c-d)后入队能够继续下面的运算队后辍为cdb-a*efab*(c-d)ef,遇+形成a+b*(c-d)后入队能够继续下面的运算队后辍为cdb-a*ef/efa+b*(c-d),遇/形成e/f后入队能够继续下面的运算队后辍为cdb-a*ef/-a+b*(c-d)e/f,遇-形成a+b*(c-d)-e/f入队得表达式值勤a+b*(c-d)-e/f故：符合队运算的后辍表示式为：cdb-a*ef+/-

数据结构基础全文共101页，当前为第45页。算法：1、根据后辍表达式，转化为表达式树；2、从表达式树的底层开始逐层向根结点按顺序输出结点值。程序实现：Expression.dpr

观察队的处理过程与表达式树关系，发现是最底层开始逐层向根结点按顺序推进，后辍表达式顺序为表达式树的从下至上从左至右形式。数据结构基础全文共101页，当前为第46页。3.4哈夫曼树与哈夫曼编码

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度和。

哈夫曼编码：根据哈夫曼树进行编码。

数据结构基础全文共101页，当前为第47页。ABCHIDEFG75249WPL(T)=7×

2+5×

2+2×

3+4×

3+9×

2=60树中所有叶子结点的带权路径长度之和表示

WPL(T)=wklk(对所有叶子结点)nk=1数据结构基础全文共101页，当前为第48页。ABCHIDEFG74952WPL(T)=7×4+9×

4+5×

3+4×

2+2×

1=89

数据结构基础全文共101页，当前为第49页。构造哈夫曼树1.根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;数据结构基础全文共101页，当前为第50页。2.在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;3.从F中删去这两棵树，同时将刚生成的新树加入到F中;4.重复(2)和(3)两步，直至F中只含一棵树为止。数据结构基础全文共101页，当前为第51页。练习:已知权值W={5,6,2,7,8}75628767713852761)2)3)528数据结构基础全文共101页，当前为第52页。4)5)6713852715671328852715WPL=2×3+5×3+6×2+7×2+8×2=63次序数据结构基础全文共101页，当前为第53页。特点：1、有n个叶子结点2、没有度为1的结点3、总的结点数为2n-14、形态不唯一数据结构基础全文共101页，当前为第54页。哈夫曼编码

利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。数据结构基础全文共101页，当前为第55页。A B C D E6 7 2 5 9例：假设有5个符号以及它们的频率：求前缀编码。数据结构基础全文共101页，当前为第56页。95271667132901010011000110010111前缀编码1、依据频率建立哈夫曼树2、对边编号3、求出叶子结点的路径4、得到字符编码A B C D E6 7 2 5 900 01 100 101 11数据结构基础全文共101页，当前为第57页。3.4二叉堆

以最小堆为例：堆是一个序列{k1,k2,…,kn}，采用顺序方式存储这个序列它满足下面的条件：

ki≤k2i并且ki≤k2i+1，当i=1,2,…,n/2

将这个序列的每一个元素ki看成是一颗有n个结点的完全二叉树的第i个结点，其中k1是该二叉树的根结点。

二叉堆是一种特殊的堆，二叉堆是完全二元树或者是近似完全二元树。二叉堆满足堆特性：父结点的键值总是大于或等于任何一个子节点的键值称为最大堆，或父结点的键值总是小于或等于任何一个子节点的键值称为最小堆。数据结构基础全文共101页，当前为第58页。

堆的基本运算：插入：要在堆中插入一个元素，只要将它放置在堆的末尾（即一个叶子节点下），调整堆。删除根：把最后一个元素放到根位置，这样就变成了把一个大元素向下放的过程。数据结构基础全文共101页，当前为第59页。数据插入堆：procedureTHeap.Push(constKey:TData);var i:TIndex;begin Inc(Size); Data[Size]:=Key; i:=Size; whilei>1do begin ifCompare(Data[ishr1],Data[i])<=0thenBreak;//如果结点值大于父结点值，退出

Swap(Data[ishr1],Data[i]);//否则，交换结点值

i:=ishr1;//位置上移一层

end;end;数据结构基础全文共101页，当前为第60页。删除堆结点：functionTHeap.Pop:TData;var i,j:TIndex;begin Swap(Data[1],Data[Size]);//根结点和尾结点交换

Result:=Data[Size];//获取根结点值

Dec(Size);//删除结点

i:=1;//根结点下沉

whileishl1<=Sizedo begin j:=ishl1; if(j<Size)and(Compare(Data[j+1],Data[j])<0)thenInc(j);//选择左右儿子中小的位置

ifCompare(Data[i],Data[j])<=0thenBreak;//如果当前结点已经小等于儿子结点，结束

Swap(Data[i],Data[j]); i:=j; end;end;数据结构基础全文共101页，当前为第61页。程序中的比较函数和交换过程functionTHeap.Compare(constA,B:TData):TData;begin Result:=A-B;end;procedureTHeap.Swap(varA,B:TData);var T:TData;begin T:=A; A:=B; B:=T;end;数据结构基础全文共101页，当前为第62页。堆排序方法就是利用这一点来选择最小元素。

一个序列和相应的完全二叉树：

这个序列不是一个堆。堆排序的关键问题是如何将待排序记录的排序码建成一个堆。

调整：使父节点小等于儿子。数据结构基础全文共101页，当前为第63页。从图可以看到，在n=9个元素组成的序列和它相对应的完全二叉树中，序号为9，8，7，6，5的结点没有儿子，以它们为根的子树显然满足堆的条件。因为在有n=9个结点的完全二叉树中，第4=n/2，3,2,1个结点都有儿子，一般情况下，以它们为根结点的子树不会满足堆的条件，所以，要使该序列变换成一个堆，必须从这些结点处进行调整。数据结构基础全文共101页，当前为第64页。

调整是从序号为4(=n/2),的结点开始，然后对序号为3，2，1的结点依次进行。依次使以第4个结点为根的子树变成堆，直到以第1个结点为根的整个完全二叉树具有堆的性质，则建堆完成。建堆过程如下图所示数据结构基础全文共101页，当前为第65页。数据结构基础全文共101页，当前为第66页。算法效率为：O(log(N))数据结构基础全文共101页，当前为第67页。堆的应用问题1:合并果子(NOIP2004提高组)【问题描述】

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。数据结构基础全文共101页，当前为第68页。

例如有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。数据结构基础全文共101页，当前为第69页。【输入样例】3129【输出样例】15数据结构基础全文共101页，当前为第70页。分析：很明显，这道题是一道贪心的题目，可以证明，每次取最小的两堆合并会使得最后的体力值最小。那么，这道题的问题就在于怎么找最小的两堆果子了。朴素方法：排序，合并，插入。

我们注意到，每次合并完果子会删掉两堆，并添加一堆新的，如果采用线性表，时间复杂度将高达O（N^2），对于N<=20000是不够的。所以，我们考虑使用最小堆优化。数据结构基础全文共101页，当前为第71页。算法：建立空堆；读入数据，建立最小堆；每次取两个堆顶元素合并，并插入合并后的数，总共合并n-1次。数据结构基础全文共101页，当前为第72页。方法2：队列朴素方法问题是时间浪费在每次的排序中，能否根据本题特点进行改进呢？构造两个队列old和new，old用来存储原有的果子堆数，new用来存储每次合并得到的新果子堆数，每次合并后累加耗费的体力即可。要想得到最小的体力耗费值，则old要按增序排列，很明显每次合并时候是在old和new的首部，取两个最小值，合并之后插入到new尾部。此种方法的好处是只需对old进行一次排序，之后就不再需要排序，而是直接在old和new的首部取值就好了。由于old的元素是从a[]中复制过来的，所以我们可以对其进行插入排序，这样排序的时间复杂度是O(N*logN)；但如果我们注意观察的话，可以发现输入数据1<＝ai<=20000，我们完全可以使用基数排序，以空间换时间，使得时间复杂度降低到O(N)。（fruit1.pas）数据结构基础全文共101页，当前为第73页。问题2：芒果(mango)【题目描述】

有n个牛头人，他们很无聊，决定玩游戏。他们排成了一队，然后顺序来到一堆准备好的芒果前面，首先从中取出Ai个，然后将剩下的芒果恰好平均分成Bi堆，从中取出一堆，剩余合并成一堆给后来人取；如果当前已经没有芒果了，牛头人会当他已经取过了。当n个牛头人都取一次之后，他们惊奇地发现芒果恰好被分光啦。因为某种关系，对于每只牛头人都有m种决策，他会随机从中取出一种可行的决策。现在他们想知道一开始的时候可能有多少芒果，于是他们找到了你，你能告诉他们吗？这个数字可能很大，所以你只需要告诉他们第k小的可能的芒果数。如果出现数芒果过程不同但答案相同，我们认为它仅仅是一组解。数据结构基础全文共101页，当前为第74页。【输入格式】输入数据的第一行包括3个正整数n,m,k，分别如题目中所描述。接下来有m行，每行有2个正整数，表示Ai和Bi。其中Bi一定大于1。【输出格式】输出一个数表示第k小的芒果数。如果不存在则输出“-1”。【样例输入】3241322【样例输出】 6【样例说明】

前4小的可能芒果数是1，2，4，6。【数据规模】

对于30%的数据，答案不超过10000； 对于100%的数据，n不超过100，m不超过10，A和B不超过100，k不超过10000。对于所有的n超过10的数据，Bi的值至少为5。数据保证答案一定在10^16之内！数据结构基础全文共101页，当前为第75页。分析：由于最后的状态比较明确为芒果取完，因此，从最后的状态倒推到初始状态比较容易解决问题。

1、设X表示取到第K个牛头人的芒果数，Y表示取到第K+1个牛头人的芒果数，按题意，顺推得：y=((x-a[k])divb[k])*(b[k]-1),如果倒推，则X=(Y*B[K])DIV(B[K]-1)+a[k]；

2、按题意，最后状态是芒果取完，则从0开始倒推选择芒果数，每次枚举所有可行的选择，设F[X]表示倒推了多少层的芒果数为X值，则

F[J]+1当F[X]=0，则由F[J]层推得

F[X]=min(F[X],F[J]+1)当F[X]<>0，表示有多种方案，选最小的

3、从芒果值为0开始逐层倒推每层可行的芒果值，输出第K小的可行的芒果值。读mango.pas数据结构基础全文共101页，当前为第76页。

上述算法问题，答案值限制在1000000内。方法2：因为如果堆空则可不取，该状态等同于只有第一个人用了同样的决策取并将堆取空的状态，这样该状态也就是答案之一，扩展k次，枚举所有答案，将答案Qsort一遍，输出第k小值。这就是该题的朴素算法。

数据结构基础全文共101页，当前为第77页。方法3：每次只要从已知答案中选出最小的且已扩展次数最少的答案，若它还可以继续扩展就计算出新答案，这样只要扩展k次即可。这就需要动态对数据进行维护，显然使用堆，可以提高算法的效率。读mango1.pas

数据结构基础全文共101页，当前为第78页。3.5二叉查找树

二叉查找树（BinarySearchTree），或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉查找树。

数据结构基础全文共101页，当前为第79页。图例如，由关键字值序列（62,15,68,46,65,12,57,79,35）构成的一棵二叉排序树如图所示。数据结构基础全文共101页，当前为第80页。

如果对上述二叉排序树进行中根遍历可以得到一个关键字有序序列（12,15,35,46,57,62,65,68,79），这是二叉排序树的一个重要特征，也正是由此将其称为“二叉排序树”。数据结构基础全文共101页，当前为第81页。二叉查找树基本操作1、插入2、查找3、删除数据结构基础全文共101页，当前为第82页。插入从根节点开始如果添加元素的关键字比当前节点大就到右儿子，否则到左儿子重复，直到到达一个叶子节点这样我们就找到了所要添加元素的父亲节点，只要根据新节点与父亲节点关键字的大小，插为父节点的左（右）儿子，这样就完成了插入。二叉搜索树的插入运算(X.Key=43)数据结构基础全文共101页，当前为第83页。二叉搜索树的构造过程

(a)空树；(b)插入28；(c)插入21；(d)插入25；(e)插入36；(f)插入33；(g)插入43数据结构基础全文共101页，当前为第84页。查找从根节点开始，如果查找元素的关键字比当前节点大就到右儿子，否则到左儿子重复，直到找到所需的节点。查找最小值从根节点开始不断找该节点的左儿子，直到一个点没有左儿子为止。该点即为树中最小值。（查找最大值相反）数据结构基础全文共101页，当前为第85页。删除分四种情况讨论，确保从二叉树中删除一个结点后，不会影响二叉排序树的性质：（1）若要删除的结点为叶子结点，可以直接进行删除。（2）若要删除结点有右子树，但无左子树，可用其右子树的根结点取代要删除结点的位置。（3）若要删除结点有左子树，但无右子树，可用其左子树的根结点取代要删除结点的位置，与步骤⑵类似。（4）若要删除结点的左右子树均非空，则首先找到要删除结点的右子树中关键字值最小的结点（即子树中最左结点），利用上面的方法将该结点从右子树中删除，并用它取代要删除结点的位置，这样处理的结果一定能够保证删除结点后二叉树的性质不变。数据结构基础全文共101页，当前为第86页。查找树的应用问题：郁闷的出纳员（Cashier）NOI2003？DescriptionOIER公司是一家大型专业化软件公司，有着数以万计的员工。作为一名出纳员，我的任务之一便是统计每位员工的工资。这本来是一份不错的工作，但是令人郁闷的是，我们的老板反复无常，经常调整员工的工资。如果他心情好，就可能把每位员工的工资加上一个相同的量。反之，如果心情不好，就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。数据结构基础全文共101页，当前为第87页。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，他并不问具体某位员工的工资情况，而是问现在工资第k多的员工拿多少工资。每当这时，我就不得不对数万个员工进行一次漫长的排序，然后告诉他答案。数据结构基础全文共101页，当前为第88页。

好了，现在你已经对我的工作了解不少了。正如你猜的那样，我想请你编一个工资统计程序。怎么样，不是很困难吧？InputFormat

第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。接下来的n行，每行表示一条命令。命令可以是以下四种之一：名称格式作用I命令I_k新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。A命令A_k把每位员工的工资加上kS命令S_k把每位员工的工资扣除kF命令F_k查询第k多的工资

_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个非负整数，F命令中的k是一个正整数。在初始时，可以认为公司里一个员工也没有。数据结构基础全文共101页，当前为第89页。OutputFormat

输出文件的行数为F命令的条数加一。 对于每条F命令，你的程序要输出一行，仅包含一个整数，为当前工资第k多的员工所拿的工资数，如果k大于目前员工的数目，则输出-1。 输出文件的最后一行包含一个整数，为离开公司的员工的总数。SampleInput910I60I70S50F2I30S15A5F1F2数据结构基础全文共101页，当前为第90页。SampleOutput1020-12DataLimitI命令的条数不超过100000

A命令和S命令的总条数不超过100

F命令的条数不超过100000

每次工资调整的调整量不超过1000

新员工的工资不超过100000数据结构基础全文共101页，当前为第91页。分析：

显而易见，这是一道模拟题，若单纯用线性表进行处理，易超时，所以自然联想到此题的关键在于数据结构的选择和设计。二叉排序树支持插入、查找、删除操作。创建一棵带权二叉排序树，满足对于每个节点，它的权值大于左子树中任意节点的权值，且小于右子树中任意节点的权值。本题需要解决以下几个问题：

1、删除：每次只要把最小值和工资下限比较，故每次删除的是树中的最小值，删除操作比较简单；

数据结构基础全文共101页，当前为第92页。2、所有的数加上或减去一个数:

假如每次对于A，S命令都给整棵树重新赋值，显然是不行的，因为树的节点最多有1000000个且有200个A，S命令所以极易超时，所以我们不得不另辟蹊径。这题的主要问题在于不断有数据被插入，假如一开始给定的数是固定的，且不会有数插入，那么我们就可很容易地想出一种解决同加同减的办法。设变量sum记录加减的变化，不论加还是减，都在