PASCAL数据结构

1、u 内容提要本讲首先简要介绍了树的几种常见的存贮结构、森林和二叉树的相互转换。接着介绍了二叉排序树(通过对二叉排序树进一次中序遍历，即可将无序数据排列成有序序列)，堆及堆排序(堆排序使用的辅助空间较少，仅增加一个记录空间用于交换，同时关键字比较的次数和树形选择排序相当)。重点之一：阐述二叉排序树的概念，讨论二叉排序树的生成，二叉排序树的插入、删除，及二叉排序树的应用。重点之二：阐述堆的概念，讨论堆的存储、堆排序的基本思想，介绍堆排序的过程，堆的插入、删除操作，堆排序的应用。u 知识讲解和实例分析一、树和森林：1、树的存贮结构(1)、双亲表示法利用每个结点(除根结点外)只有唯一双亲的特点，用二维

2、数组来存贮一棵一般树。这种结构对于寻求某结点的双亲及求树的根结点等操作是很方便的，但用于求结点的孩子时比较麻烦，需要遍历整个数组。(2)、孩子表不法用多重链表来存贮一般树。在多重链表中，每个结点有多个指针域，每个指针域指向一棵子树的根结点，此时有两种结点结构：A、多重链表中的结点是同构的，则会浪费较多的存贮空间；B、多重链表中的结点是不同构的，虽然节约存贮空间，但操作不方便。(3)、孩子兄弟表示法最常用的存储方法是孩子兄弟表示法。即以二叉树链表作为树的链表。链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟结点。2、森林和二叉树的转换：(1)、森林转换为二叉树：如果 F=T1,T2,

3、，Tm是森林，则可按下列规则转换成二叉树 B=root,LB,RB(i)、若 F 为空，即 m=Q 则 B 为空树。(ii)、若 F 不为空，即 m 不为 0,则 B 的根即为森林中第一棵树的根；B 的左子树 LB 是从森林 F1=T11,T12T1m转换而成的二叉树；其右子树 RB 是从森林 F=T2,T3,Tm 并专换而成的二叉树。(2)、二叉树转换为森林：(i)、若 B 为空，则 F 为空。(ii)、若 B 非空，则 F 中第一棵树 T1 的根 ROOT(T1)即为二叉树 B 的根 root;T1 中根的子树森林 F1 是由 B 的左子树LB 转换而成的森林；F 中除 T1 之外，其余树

4、组成的森林 F=T2,T3,Tm是由 B 的右子树 RB 转换击成的森林。二、二叉排序树：1、二叉排序树的定义：二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：(1)、若它的左子树非空，则左子树上所有结点的值均小于根结点的值；(2)、若它的右子树非空，则右子树上所有结点的值均大于根结点的值；(3)、它的左、右子树也分别是二叉排序树。2、二叉排序树的查找：在二叉排序树 b 中查找 x 的过程为：(1)、若 b 是空树，则搜索失败；否则(2)、若 x 等于 b 的根结点的数据域的值，则查找成功；否则(3)、若 x 小于 b 的根结点的数据域的值，则搜索左子树；否则(4)、搜索右子树funct

5、ionsearch(b:btree;x:integer):btree;beginIf(b=nil)thensearch:=nilElsebeginIf(bA.data=x)thensearch:=b;If(xIf(xbA.data)thensearch:=search(bA.right,x);end;end;3、二叉排序树的生成：首先讨论向一棵二叉排序树 b 中插入一个结点 s 的算法，其过程为：(1)、若 b 是空树，则将 s 作为根结点插入；否则(2)、若 sA.data 等于 b 的根结点的数据域之值，则返回；否则(3)、若 sA.data 小于 b 的根结点的数据域之值，则把 s 结点

6、插入到左子树中；否则(4)、把 s 结点插入到右子树中。向一棵二叉排序树 b 中插入一个结点 s 的过程如下：procedureinsert(varb:btree;s:btree);beginif(b=nil)thenb:=selseif(sA.dataelseif(sA.databA.data)theninsert(bA.right,s)end;生成二叉排序树的过程是先有一个空树 b,然后逐个向该空树中插入结点实现的。因此根据用户输入的一系列正整数(一 1 表示结束)生成一棵二叉排序树的过程如下：procedurecreat(varb:btree);varx:integer;s:btree;

7、beginb:=nil;read(x);whilex=-1dobeginnew(s);sA.data:=x;sA.left:=nil;sA.right:=nil;insert(b,s);read(x);endend;4、二叉排序树的删除：删除二叉排序树 b 中一个数据域为 x 的结点的过程为：(1)、首先查找到数据域为 x 的结点 p(2)、若结点 p 没有左子树，则用右子树的根代替被删除的结点(3)、若结点 p 有左子树，则在其左子树中找到最右结点 r,将 p 的右子树置为 r 的右子树，再将 p 的左子树的根结点代替被删除的结点 p过程如下：proceduredelnode(varb:bt

8、ree;x:integer);varp,q,r,t:btree;beginp:=b;q:=nil;while(pnilandqA.datax)doif(xbeginq：=p;p:=pA.leftendelsebeginq:=p;p:=pA.rightend;if(p=nil)thenwriteln(notfind)elseif(pA.left=nil)thenif(q=nil)thent:=pA.rightelseif(qA.left=p)thenqA.left:=pA.rightelseqA.right:=pA.right;elsebeginr:=pA.left;while(pA.right

9、nil)dor:=rA.right;rA.right:=pA.right;if(q=nil)thent:=pA.leftelseif(qA.left=p)thenqA.left:=pA.leftelseqA.right:=pA.leftend;end;三、堆及其操作：1、堆的定义：堆是由 n 个关键字组成的序列K1,K2,，Kn,当且仅当满足下列关系时，称之为堆。KiK2i、KiK2i、KiK2i+1(称为最大堆)其中 1=1,2,，Ln/2堆可以看成是对一棵以 K1 为根的完全二叉树进行按广度优先遍历所得到的结点序列。按照堆的定义，在这棵完全二叉树中，任一结点的值都不大于(或不小于)它的两个

10、孩子结点的值(因为当 I5/2时完全二叉树的第 I 结点不存在孩子结点)，因此在堆中根结点 K1 是最小的，并且二叉树中任一子树都是一个堆。2、堆的存储：由于它是一棵完全二叉树，所以可以把它象完全二叉树一样简单地储存在数组中，根据完全二叉树的性质可以对于下标为 i 的结点，其子结点下标为 2i、2i+1o 所以对于最大堆来说，数组中元素的值满足：KiK2i、KiK2i+1、KiAi/23、堆排序的基本思想：对一组待排序的记录的关键字，首先把它们按堆的定义排列成一个序列(称为初始建堆)，同时也就找到了最小关键字，然后将最小关键字输出。对剩余的关键字再建堆，便得到次小的关键字，如此反复进行，直到全

11、部关键字有序为止，即完成了堆排序过程。(1)、将以 Ki 为根的子树建成堆(最小堆为例)：设有关键字集合K1,K2,，Kn,若对 I=L+1,L+2,，n 均满足堆的定义(其中 L=匚 n/2)，现在对 I=L 进行筛选建堆：Proceduresift(L,n:integer;VARheap:ARRAY1.nOFnode);VARI,j:integer;X:node;BeginI:=L;J:=2*I;X:=heapI;Whilejheapj.keyThenBeginHeapI:=heapj;子树结点上调I:=j;J:=2*I下沉一层endelsej:=n+1;跳出循环end;heapI:=xe

12、nd;(2)、堆排序过程：对一个已知的关键字序列K1,K2,，Kn,只要使上述算法中的变量 L 从n/2开始直到 L=1 为止,反复调用 sift(L,n,heap)算法就得到一个满足堆定义的对应关键字序列。即建成了堆，并找到了最小关键字。输出最小关键字之后，是否还需要对剩余的 n-1 个关键字从头开始重新建堆呢？不需要。因为输出最小关键字 K1 之后，它的左、右子树的根 K2 和 K3 仍具有堆的特性，所以把 Kn 放到 K1 位置，再次调用一次 sift(L,n-1,heap),便可得到剩余 n-1 个关键字的新堆，从而得到剩余 n-1 个关键字中的最小关键字。为了节省空间，我们可以把第一

13、次输出的最小关键字放在 Kn 的位置上，把第二次输出的最小关键字存放在 Kn-1的位置上，。如此反复执行 n-1 次，便完成了排序过程。Procedureheapsort(n:integer;VARheap:ARRAY1.nOFnode);VARI:integer;BeginForI:=(ndiv2)downto1doSift(I,n,heap);Whilen1dobiginHeap0:=heap1;Heap1:=heapn;Heapn:=heap0;N:=n-1;Sift(1,n,heap)endend;由上述算法可见，堆排序仅需一个记录大小的辅助空间供交换使用。堆排序的运行时间主要消耗在初

14、始建堆和调整时的反复筛选重新建堆上，对于 n 个关键字集合进行堆排序的时间复杂度为 O(nlog2n)。它适用于 n 较大的情况。4、最大堆的插入操作：根据最大堆的定义及性质可知，插入一个结点后还是一棵完全二叉树，所以该结点必插入在数组的最后，插入后，比较它和父结点的关系，若大于父结点则和其交换，再和上一层比较，这样一直做下去。过程如下：procedureinsert(x:integer);varI:integer;beginheapsize:=heapsize+1;I:=heapsize;While(I1)and(xheapIdiv2)doBeginHeapI:=heapIdiv2;I:=I

15、div2;End;HeapI:=xEnd;5、最大堆元素的删除操作：在最大堆中删除一个元素后，堆的容量减少 1,明显最后一个元素该取代被删除元素的位置，取代后还要考虑它和孩子的关系，若大于它的孩子则取代成功，否则它要和它的最大的孩子交换位置，再和新位置的孩子比较大小关系，这样一直做下去。删除 I 个元素的过程如下：proceduredelete(I:integer);varx:integer;beginx:=heapheapsize;heapsize:=heapsize-1;son:=2*I;while(son=heapsize)dobeginif(sonheapsonthenbreak;he

16、apI:=heapson;I:=son;Son:=2*I;End;HeapI:=x;End;u 举例及应用：1、已知图 a 中的二叉排序树的各个结点的值分别为 1 至 9,并且各自不相同，请标出各结点的值。解：该二叉树各结点的值如图 b 所示。图(a)图(b)2、设非空二叉排序树采用二叉链表储存结构，根结点的指针为 To 请写一算法，找出该二叉树中值最小的结点。算法分析：由二叉排序树的定义可以知道，非空二叉排序树中值最小的结点是二叉排序树最左边那个结点。因此，只须设置一个指针变量，首先令它指向二叉排序树的根结点，然后让它沿着它左子树方向一直找下去，直到某一时刻，该变量所指的结点的左子树为空，此

17、时，该结点就是二叉树中值最小的结点。Functionminnode(T)beginP:=tWhile(pA.leftnil)doP:=pAleftminnode:=pend3、已知序列(35,78,12,26,90,41,66,58),请写出对该序列采用堆排序方法进行升序排序时各趟的结果。L 从n/2开始直到 L=1 为止，反复调用 sift(L,n,heap)算法就得到一个满足堆定义的对应关键字序列。即建成了堆，并找到了最小关键字。输出最小关键字之后，把 Kn 放到 K1 位置，再次调用一次 sift(L,n-1,heap),便可得到剩余 n-1 个关键字的新堆，从而得到剩余 n-1 个关键

18、字中的最小关键字。如此反复执行 n-1 次，便完成了排序过程。程序清单：参照 sift(L,n,heap)及 heapsort(n,heap)u 习题：解：原始序列：35,第一趟后：26,第二趟后：12,第三趟后：12,第四趟后：12,第五趟后：26,第六趟后：12,第七趟后：12,7812267866585866265841263541263512412635412635419041665835411290354178903566789058667890586678905866789058667890算法分析：对于该序列，只要使变量1、将一段英文中出现的单词按词典的顺序打印出来，并统计出每个单词在文章中出现的次数。数据输入：任意的一段英文句子数据输出：先按词典的顺序打印出所有出现的单词，再输出每个单词出现的次数样例输入 1:Thisisabeautifulhouse.样例输出 1:abeautifulhouseisThisa：1beautiful:1house：1is：1This:12、我们知道给定一个 1 至 n 的 n 个数的任意序列，唯一确定一棵二叉排序树，但根据这棵二叉排序树，往往不能唯一确定 n