广东省汕头市高中信息技术信息学竞赛班数据结构专项培训教程07树

信息学奥林匹克教程(数据结构篇)《信息学奥林匹克教程(数据结构篇) 奥赛经典高级教程系列(奥赛经典高级教程系列)》内容简介为了进一步推广、普及计算机技术，提高竞赛水平，在原来编写的一套《信息学奥林匹克教程》（基础篇·提高篇·语言篇）的基础了，我们又编写了这本《数据结构篇》。

《数据结构篇》主要帮助学生全面地掌握数据结构知识与应用技巧，相对于其他数据结构书不同之处就在于增加了一些针对性的例题和习题，着眼点是提高数据结构的应用方法与技巧，是一本具有实战意义的教材。

从逻辑角度看，数据可归结为三种基本结构：线性结构、树结构和图结构；从存储角度看，数据可归结为四种基本结构：顺序结构、链接结构、索引结构和散列结构。

每一种逻辑结构可根据不同需要采用不同的存储结构，或者不同的存储结构的组合。

数据的逻辑结构和存储结构确定后，再结合指定运算的算法，就容易利用一种程序设计语言编写出程序。

通过数据结构的学习，能够大大提高程序设计能力和水平。

《数据结构篇》是为广大信息学爱好者学习数据结构而精心编著的一本教材。

本书内容比较全面，着重于实用与实战，在算法分析上简明扼要，细致清晰，便于自学。

全书共分十章：第一章为概论，它为学习以后的各章做准备；第二章至第五章为线性结构；第六章和第七章分别为树结构和图结构，分别讨论了每一种逻辑结构所对应的存储结构和相应的算法；第八章和第九章分别为查找与排序，它包含了数据处理中主要使用的几种查找和内排序方法；最后一章为读者提供了检测知识的模拟试题及解答。

作者简介向期中，长郡中学特级教师，湖南省计算机学会理事，国际金牌教练，国家教育部计算机课程咨询委员会委员。

对中小学计算机教育事业有一种执着的追求，参加工作20年来，一直以“当一流教师，办一流教育，出一流人才”为自己的工作目标，对中小学计算机教学和青少年信息学奥林匹克竞赛的辅导倾注了全部热情和心血。

在信息学奥林匹克竞赛培训中把“先做人，后成才”的育人理念贯穿到整个奥赛培训的始终，学生在愉快的学习中取得了一个个辉煌的成绩：在近几年的信息学奥林匹克竞赛中，辅导的学生有100多人获湖南省一等奖，11人次进入国家集训队，3人进入国家代表队，3人获国际金牌。

集合与记录类型§6.1 集合类型§6.1.1 集合类型的定义集合是同类型对象的一个汇集，它是指同类型对象汇集在一起构成的数据结构。

集合的每一个对象称为集合的元素。

集合元素必须是有序简单数据类型，集合元素的类型称为集合的基类型。

集合的一般形式为：TYPE <类型标识符> = set of <基类型>;基类型可以是整型、字符型、布尔型、枚举型、子界型等，但不能是实型或结构类型。

例如：TYPE letter = set of ‘A’.. ‘Z’;var ch1, ch2 : letter;也可以直接写成：var ch1, ch2 : set of ‘A’.. ‘Z’;在Pascal中集合是用一组括在方括号中的元素来表示，元素之间用逗号分隔。

如：[A, B , C , D] 是四个枚举量的集合[ 1 .. 20 ] 表示1到20的所有整数的集合[ ‘0’ ] 是单元素集[ ] 表示空集一个集合类型变量的取值，可以是基类型中所有元素按不同的组合而构成的子集。

例如，上面说明变量ch1的类型是letter，它可以是下列的组合：[‘A’ .. ‘Z’] 全集[‘A’, ‘B’, ‘Q’] 任一子集[‘A’ .. ‘C’ , ‘X’ ..‘Z’ ][‘A’ ] 单元素集[ ] 空集空集与所有的集合类型都兼容。

§6.1.2 集合类型的运算ch1:=[ [‘A’ .. ‘C’]];是合法的集合赋值。

对集合除可以进行赋值运算外，还可以进行以下运算：·交（*）运算：两集合之交 S1*S2 为一集合，所得元素由S1、S2中相同的元素组成。

如： [ 0..7 ] * [ 0..4 ] = [ 0..4 ]·并（+）运算：两集合之并 S1+S2 为一集合，所得元素由S1、S2中所有相同的元素组成。

如： [ 0..7 ] + [ 0..4 ] = [ 0..7 ][ 0 , 1 ] + [ 1 , 4 , 6 ] = [ 0 , 1 , 4 , 6 ]·差（-）运算：两集合之差 S1-S2 为一集合，所得元素由只存在于S1而不在S2的那些元素组成。

信息技术竞‎赛培训教程‎目录第二部分数据结构（一）――栈（二）――队列（三）――链表（四）――迭代与递推‎（五）――递归（六）――搜索与回溯‎（七）――树与二叉树‎（八）――排序算法（九）――查找算法（十）――图论基础知‎识●●广度优先搜‎索●●广度优先搜‎索第二部分算法和数据‎结构（一）――栈说到学习和‎掌握数据结‎构，很容易让人‎想到的就是‎其最本的数‎据结构模式‎：栈、队这一讲，我们就来谈‎谈“栈”。

“栈”的应用很广‎泛，大家在PA‎S CAL程‎序设计中，常遇的一种‎错误就是“栈”超界，那么，“栈”为何物呢？栈是只能在‎某一端插入‎和删除的特‎殊线性表。

用桶堆积物‎品，先堆进来的‎压在底下，随后一件一‎件往堆。

取走时，只能从上面‎一件一件取‎。

堆和取都在‎顶部进行，底部一般是‎不动的。

栈就是一种‎类似桶堆积‎物品的数据‎结构，进行删除和‎插入的一端‎称栈顶，另一堆称栈‎底。

插入一般称‎为进栈（PUSH），删除则称为‎退栈（POP）。

栈也称为后‎进先出表（LIFO 表‎）。

一个栈可以‎用定长为Ｎ‎的数组Ｓ来‎表示，用一个栈指‎针TOP指‎向栈顶。

若TOP＝0，表示栈空，TOP=N时栈满。

进栈时TO‎P加１。

退栈时TO‎P减１。

当TOP<0时为下溢‎。

栈指针在运‎算中永远指‎向栈顶。

1、进栈（PUSH）算法①若TOP≥ｎ时，则给出溢出‎信息，作出错处理‎（进栈前首先‎检查栈是否‎已满，满则溢出；不满则作②）；②置TOP=TOP+1（栈指针加１‎，指向进栈地‎址）；③S(TOP)=X，结束（X为新进栈‎的元素）；2、退栈（POP）算法①若TOP≤0，则给出下溢‎信息，作出错处理‎(退栈前先检‎查是否已为‎空栈，空则下溢；不空则作②)；②X=S(SOP)，（退栈后的元‎素赋给X）；③TOP=TOP-1，结束（栈指针减１‎，指向栈顶）。

进栈、出栈的Pa‎s cal实‎现过程程序‎：CONST‎n=100;TYPEstack‎=ARRAY‎[1..n] OF integ‎e r;PROCE‎D URE PUSH(VAR s:stack‎;VAR top,x:integ‎e r);{入栈}BEGIN‎IF top=n THENwrite‎l n('overf‎l ow')ELSE BEGIN‎top:=top+1;s[top]:=x;END;END;PROCE‎D URE POP(VAR s:stack‎;VAR y,top:integ‎e r);{出栈}BEGIN‎IF top=0 THEN write‎l n('under‎f low') ELSE BEGIN‎y:=s[top];top:=top-1;ENDEND;对于出栈运‎算中的“下溢”，程序中仅给‎出了一个标‎志信息，而在实际应‎用中，下溢可用来‎作为控制程‎序转移的判‎断标志，是十分有用‎的。

数组【引例】输入20个数，将它们按从大到小的次序排序后输出。

讨论：如果按我们前面学的知识，我们应设20个变量来存储这20个数，如果要排序的数不是20个，而是100个，那我们就应设100个变量？没这么笨吧，我们有更好的办法解决。

§5.1 一维数组数组是由固定数量．．．．的相同类型．．．．的元素按一定顺序排列而成。

只有一个下标类型的数组称为一维数组。

1．数组类型定义和说明类型定义的一般形式为：TYPE <类型标识符> = ARRAY [下标类型] OF <基类型>；数组说明：VAR <数组名> ：<数组类型标识符>；数组名是由用户定义的标识符，下标类型可以是子界类型或枚举类型，下标规定了数组元素的个数和排列次序。

基类型表示数组中每个元素的类型，它可以是任何数据类型，但同一数组中的元素类型必须相同。

如：typeA = array [1..20] of integer;B = array [0..50] of char;Varx , y : A;a : B;其中x 、y 被说明为A 类型数据，即均为拥有20个元素的数组，下标从1到20，元素类型为整型；a 被说明为B 类型数据，即拥有51个元素的数组，下标从0到50，元素类型为字符型。

★ 数组也可以直接在说明部分说明数组的类型，如：var x , y : array [1..20] of integer;a : array [0..50] of char;数组中的每个元素都是变量，每个元素在数组中有固定的位置，可以用数组名及方括号括起的下标．．来表示。

如a 数组中的第5个元素可表示为：a [4]数组元素的运算和变量相同，如：readln (a[4]); x[3]:=x[3]+y[1];2．数组元素的赋值和引用如为一个数组A[1..10] 赋值，可用下列语句实现：for i:=1 to 10 do read (A[i]);如果两个数组类型相同，如数组x 和y ，可用赋值语句： x:=y ；把y 的10个元素值赋给x 的相应元素，它等效于： for i:=1 to 20 do x[i]:=y[i]; 但要给数组元素赋同一个值，不能这样赋值：x:=0;0 1 2 3 4 5 6 7 …… 50 a 下标而应该用如下语句：for i:=1 to 20 do x[i]:=0;【例1】求100以内的所有素数。

图§8.1 图的基本概念图： 图是数据结构G ＝(V ，E)，其中V 是结点的有穷非空集合，结点的偶对为边，E 是边的集合。

图中的结点又称为顶点。

无向图与有向图：如果图中每条边都是没有方向的，则称为无向图；无向图中的边表示图中顶点的无序对，即（u , v ）和（v , u ）表示同一条边。

如图8.1.1为一个无向图，它的顶点集和边集分别为： V （G 1）＝{ 1 , 2 , 3 , 4 , 5 }E （G 1）＝{(1, 2) , (1, 4) , (2, 3) , (2, 5) , (3, 4) , (3, 5)} 如果图中每条边都是有方向的，则称其为有向图；有向图的边表示图中顶点的有序偶对；在有向图中，箭头表示边的方向。

如图8.1.2为一个有向图，该图的顶点集和边集分别为：V （G 2）＝{ 1 , 2 , 3 , 4 }E （G 2）＝{(1, 2) , (1, 3) , (2, 4) , (3, 2) , (4, 3)} 度、入度、出度：在一个有向图中，把以结点V 为终点的弧的数目称为V 的入度；把以结点V 为始点的弧的数目称为V 的出度。

入度和出度之和为该的结点的度。

如图8.1.2中，顶点V 3的入度为2，出度为1，度为3。

路径 、路径长度： 图中从V S 到V P 的一条路径是指一串由顶点所成的连续序列V S , V i1 ,V i2 ,……, V in , V P ，且其中 (V P , V i1) , (V i1 ,V i2) , ……, (V in , V P ) 都是E 上的边。

路径上所包含边的数目称为路径长度。

简单路径、简单回路：如果一条路径的顶点序列中，顶点不重复出现，则称此路径为简单路径。

起点和终点相同的路径称为 回路或环。

除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路。

连通图、强连通图：在无向图G 1中，若从顶点V t 到V s 有路径，则称V t 和V s 是连通的。

树§7.1 树的概念【定义】 树（Tree ）是n （n>0）个结点的有限集合T,它满足如下两个条件： (1) 有且仅有一个特定的称为根（Root ）的结点； (2) 其余的结点可分为m （m ≥0）个互不相交的有限集合,其中每一个集合又都是一颗树,并称为根的子树（Sub Tree ）。

【基本术语】k树的结点包含一个数据元素及若干指向其子树的分支。

结点拥有的子树数称为结点的度（degree ）。

如图7.1,A 的度为3,C 的度为1,F 的度为0。

度为0的结点称为叶子（leaf ）或终端结点。

例如K 、L 、F 、G 、M 、I 、J 。

度不为0的结点称为分支结点或非终端结点。

除根结点外,分支结点也称为内部结点。

树的度是树内各结点的度的最大值,如图7.1中树的度为3。

结点的子树的根称为该结点的孩子（Child ）,该结点称为孩子的双亲（parent ）。

如图7.1.1,B 为A 的子树的根,则B 是A 的孩子,而A 则是B 的双亲。

同一个双亲的孩子之间互称为兄弟（sibling ）,例如B 、C 、D 互为兄弟。

将这些关系进一步推广,可认为D 是M 的祖父。

结点的祖先是从根到该结点所经分支上的所有结点。

例如,M 的祖先为A 、D 、H 。

反之,结点的子树中的任一结点都称为该结点的子孙,如B 的为E 、F 、K 、L 。

5. 结点的层次（level ）是从根开始定义起,根为第一层,根的孩子为第二层。

若某结点在第x 层,则其子树的根就在x+1层。

树中结点的最大层次称为树的高度或深度（depth ）。

如图7.1的树的深度为4。

6. 如果将树中的结点的各子树看成从左到右是有次序的（即不能互换）,则称该树为有序树,否则称为无序树。

如图7.1.2。

7. 森林（forest ）是m （m ≥0）棵互不相交的树的集合。

§7.2 二叉树§7.2.1 二叉树的定义 二叉树（binary tree ）是一种树型结构,它的每个结点至多只有二棵子树（即二叉树中不存在度大于2结点）,并且,二叉树的子树有左右之分,其次序不能任意颠倒。

§2 线性表§2.1 线性表的定义及其基本运算线性表是n个数据元素（结点）a1，a2，……，a n组成的有限序列。

其中数据元素的个数n 定义为表的长度。

当n=0时称为空表。

线性表的常用的运算：（1）置空表。

（2）求线性表L的长度。

（3）取表中的第i个结点（4）按值查找。

（5）插入：在表L的第i个位置上插入新的结点X。

（6）删除：删除表L的第i个结点。

线性表可采用两种存储结构：顺序存储和链式存储。

§2.2 线性表的顺序存储结构它的特点是逻辑上相邻的结点其物理位置亦相邻，下标可以看成是结点的相对地址。

·运算：1) 插入用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将表中位置n,n-1,...,i上的结点依次后移到位置 n+1,n,...,i+1上,腾出第 i个位置，然后在该位置上插入新结点x。

仅当插入位置 i=n+1时，才无须移动结点，直接将 x插入表的末尾。

2）删除在顺序表上实现删除运算也必须移动结点，才能反映出结点间逻辑关系的变化。

仅当i=n，才能简单地删除终端结点，无须移动结点；3）取表S中的第i个结点: 直接以 S[i]表示4) 查找须顺序取出表中元素逐一比较·顺序表有如下优缺点：优点：（1）无须为表示结点间的逻辑关系而增加额外的存储空间；（2）可以方便地随机存取表中的任一结点。

缺点：（1）插入和删除运算不方便，除表尾的位置外，在表的其它位置上进行插入和删除操作都必须移动大量的结点，其效率较低；（2）由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表变化较大时，难以确定合适的存规模，若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用，若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。

§2.3 线性表的链式存储结构从链接方式上可分为：单链表、循环链表和双链表。

2002年汕头市信息学竞赛集训资料2002.8题一、两头蛇数趣解（有待转化为PASCAL 程序——问题在于：数的类型与范围）问题1：有一个自然数N,在它的首尾两端添上一个1,由于1是自然数之首,便形成一个“两头蛇数”1N1。

如果“两头蛇数”1N1正好是原自然数N 的99倍,问N 是多少?这是八十年代末在<<美国游戏数学>>杂志上刊出的一个简单而有趣的问题。

当时,它曾激起了广大青少年爱好者的广泛兴趣,并掀起一股研究“两头蛇数”热潮。

分析:设所求的自然数N 是M 位数,因为1N1=99×N,所以然10m+1+10N+1=99N 从而8901...100891101=+=+m N于是,采用试探除法,从101,1001,……。

,逐次添加零,直到有自然数100…01(M 个0)能除尽89为止,其商为所求的数N 。

编程思路：因要反复进行试探法运算,宜用WHILE 循环。

变量a 存放被除数,k 存放除数89,b 存放每次相除的商,c 存放每次相除的余数；当余数c=0则退出循环。

这样,不难得到程序一:program tt; var k,c:longint; a,b:extended; begin k:=89; a:=100; write('n='); c:=1; while c<>0 dobeginb:=int((a+1) / k) ;c:=trunc(a+1-k*b);if c=0 then writeln(b:30:0); a:=a*10;end;{while}end.题二、巧除伪币在n 枚硬币中,有1枚伪币,已知该伪币比其它硬币稍重,试用最少次数在天平上称量出这枚伪币。

[分析]乍一看,此题似乎用二分法在天平上区分该伪币的方法比较好。

比如有81枚,可以第一次在天平的两端各放40枚,以后再各称20枚、10枚、5枚、2枚、1枚,这样最坏的情况需称6次,但6次是不是最少次数呢?如果从另一个角度看这个问题,将81等分成三分,则第一次右在天平两端分别放27枚,以后再按各称9枚,3枚,1枚,最多4次就可找出伪币,即用天平称量的办法在81枚硬币中找这枚伪币最少需称量4次。

信息技术竞赛培训教程信息技术竞赛培训教程目录第二部分数据结构（一）栈（二）队列（三）链表（四）迭代与递推（五）递归（六）搜索与回溯（七）树与二叉树（八）排序算法（九）查找算法（十）图论基础知识l l 广度优先搜索l l 广度优先搜索第二部分算法和数据结构（一）栈说到学习和掌握数据结构，很容易让人想到的就是其最本的数据结构模式栈、队这一讲，我们就来谈谈“栈”。

“栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么，“栈”为何物呢栈是只能在某一端插入和删除的特殊线性表。

用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。

取走时，只能从上面一件一件取。

堆和取都在顶部进行，底部一般是不动的。

栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。

插入一般称为进栈（PUSH），删除则称为退栈（POP）。

栈也称为后进先出表（LIFO表）。

一个栈可以用定长为Ｎ的数组Ｓ来表示，用一个栈指针TOP指向栈顶。

若TOP＝0，表示栈空，TOPN时栈满。

进栈时TOP加１。

退栈时TOP减１。

当TOP then exit; if s[i] in [ * , / ] and symbol[p] in [ * , / ] then exit; can false; end; begin write String ; readlns; s s ; i 1; p 0; while i 9 ; t copys, j, i - j; valt, number[p], code; repeat if s[i] then {右括号处理} begin while symbol[p] do pop; decp; number[p] number[p 1]; end else begin {根据标志函数值作运算符入栈或出栈运算处理} while can do pop; push; end; inci; until i lengths or s[i - 1] ; end; write Result , number[0]; readln; end. 练习题1、读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。