备战NOIP2010提高组初赛复习-数据结构

1、 备战2提0高1组0初赛复习数据结构篇 # #FORTRAN语言仅定早期的程序设计主要偏重于数值计算领域，采用的数据结构相对简单。例如义了数组(包括多维数组)和复数两种结构型数据，这两种数据类型足以应付当时多数的科学计算问题。但是随着现代科技的发展，计算机逐渐应用于数据处理和非数值计算问题，从客观事物中抽象出的数据日益显现出多样化的特征，简单的数据类型已远远不能满足需要，各数据元素之间的复杂联系已经不是普通的数学方程式所能表达的了。在这种背景下，一种专门研究数据之间结构关系的 #学科数据结构便应运而生。数据结构专门研究各种数据的表示、数据的类型以及它们之间关系的集合，其研究范围主要包括各种数据

2、结构的性质，即它们的逻辑结构、物理结构以及施于其上的操作。数据结构的类型种类繁多，可以从不同的角度来划分：若从数据元素的值在使用时具有不可分割的性质或者是它可以由更基本的成份组成这个角度来划分，数据结构可以分成简单类型和构造类型两大类；如果从数据所占据的内存空间在程序执行期间是否发生变化这个角度来划分，数据结构又可以分成静态结构和动态结构两大类；如果从数据结点后继关系的多少和是否具有层次性的角度划分，数据结构还可以分 #成线性结构和非线性结构两大类。简单类型整型、实型、字符型、布尔型静态数据类型构造类型数组、记录、集合、字符串文件、指针动态数据的类型线性结构数组、栈、队列、链表、串非线性结构树

3、、图PASCAL就通常高级程序设计语言都提供了各种简单类型和静态构造类型的数据结构。例如提供了叮种类型的定义。这皿种类型中除了文件和指针属于动态结构的构造类型外，其余口 #叮均属于简单类型和静态构造类型。在上表的数据结构中，像数组、栈、串和队列等数据结构属于线性数据结构，而树和图属于非线性数据结构。线性数据结构易于表示各结点之间的联系，其存储方式相对简单；非线性数据结构往往能比较形象地反映各结点之间的层次关系。无论是线 #性结构或非线性结构，若采用数组方式存储，则属于静态数据类型；若采用指针类型存储，则属于动态数据类型。考虑到篇幅限制和读者大多具备pascal语言或c语言的基础，本书侧重讲解

4、线性结构和非线性结构两种。数据结构和算法有着密切的联系，简洁有效的算法很大程度上出自于对数据结构的正确选从问题中抽象出的数据多半是结构类取。奥林匹克信息学竞赛的试题大都属于非数值计算问题，型的，因此，对于参与这项活动的学生来说，学好、用好数据结构尤为重要。为此。我们在本书中详尽地介绍了数据结构的有关概念和基本操作，同时辅之于一些实例，围绕编程实际展开讨论， 尽可能多给读者一点启示。第一章顺序存储结构的线性表线性表是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素有一个数据项或者含多个数据项。例如26个英文字母表(A,B,Z)是一个线性表，11）也是一个线性表，表

5、中含8个数表中每一个数据元素由单个字母组成数据项。又如（图据元素，每一个数据元素由n个选手在该项目的竞赛成绩组成。、学生项目、学生1学生j学生n项目总分项目1项目iXxiji=1项目8选手总分sumSumx=xjiji=1（图11）线性表具有如下结构特征：均匀性：即同一线性表的各数据元素的数据类型一致且数据项数相同；有序性：表中数据元素之间的相对位置是线性的，即存在唯一的“第一个”和“最后一个”数据元素。除第一个和最后一个外，其它元素前面均只有一个数据元素（直接前趋）和后面均只有一个数据元素（直接后继）。按照表中数据元素的存储方式分顺序存储结构和链式存储结构二类线性表。顺序存储结构是指用一组地

6、址连续的存贮单元依次存储线性表的元素，通常用数组实现；而在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。其实现既可采用静态数组，亦可采用动态指针。为了扩大用户空间和更多地体现链式存储结构的便利，实践中大都采用动态链表形式。为此，本书在讲解顺序存储结构的线性表时采用数组类型，在讲解链式存储结构的线性表采用指针类型。另外，根据存取方式的限制和表元素类型的限制，还存在几种特殊类型的线性表：栈、队列、串，它们一般采用顺序存储结构11数组若数组元素不再有分表长为（d1-c1）*（d2-c2），1个元素的地址）十位移来我们称有限个同类型数据元素的序列为数组，它是一种定长的线性表。量，该

7、序列叫一维数组；若数据元素为数组，则称该元素为多维数组。例如varA：arraycDdofatype；B：arraycDd,cDdofbtype；1122A为一维数组，表长为（dc+1）,元素类型为atype；B为二维数组，元素类型为btype。一维数组和多维数组的元素个数由其类型说明或变量说明静态确定，执行中不能增减其内存空间。一、数组的顺序存储结构数组的物理实现是一块连续的存储空间，它是按首址（表中第访问每一个元素的。设cDiDd）；loc（ai）A表中元素i的内存地皿loc(bi,j)B表中口i,j)元素的内存地址(ciDd,jOdD；loc(ai)=loc(ac)+(ic)*llaty

8、pe类型的长度；aa首址位移lbbtype类型的长度；loc(bi，j)=loc(bc，c)+(d-c+1)*(i-c)+(j-c)*l.122212b首址位移一维数组按照下标递增的顺序访问表中元素acDac+1DDad二维数组按照先行后列的顺序访问表中元素bc,cDbc,c+1DDbc,12121Dbd,d12在数组中,数据元素的下标间接反映了数据元素的存储地址。dDD2bi-1,dD2bi,cDD2而计算机内存是随机存取的装bd,1d-12置,所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了,数组中任意一个元素的存取时间都相等。从这个意义上讲,数组的存储结构是一个随机存取的结

9、构。二、数组在顺序存储结构下的插入与删除设数组定义为Constm二数组的长度上限；Typevtype二array1Dmofelementype；varn：integer；v：vtype；数组类型数组的实际长度数组按上述定义，v为一个长度为n的数组v=v1,v2,vn,元素类型为elementype。 # #1、插入操作现要在数组的第i1个元素vil与第i个元素vi之间插入一个新元素b,插入后将得 #到一个长度为插入前后两数组的元素vj与vj满足如下关系n+1的新数组v=v1,vn,vn+1 # #vj1ji-1vj=bj二ivj-1i1jn1 #ii个元显然,若插入运算在数组未尾（即在个元素即

10、可。但是,在一般情况下,如果插入运算在第个元素及其之后的所有元素都必须移动。移动从最后一个元素（即vn后插入新元素）进行，则只要在数组末尾增加一i（1DiDn）个元素之前进行，则原来第vn）开始，直到第 素之间共ni+1个元素依次向后移动一个位置，然后将新元素插入第i项：procedureinsert(b：elementype；i：integer；beginifndmvarn：integer；varv：vtype)；上溢thenwriteln(overflow)elseif(in+1)thenwriteln(without)elsebeginforj：=ndowntoidovj+1Dvj；vi

11、Dvn向后移动一个位置 viDb；ndn+1；end；elseb插入i位置，v数组的长度+1end；insert执行insert过程的时间复杂度:数组中一半的元素。对顺序存储的数组作一次插入运算，平均起来，大约需要移动2、删除操作现要删除数组v中的第i个元素，其长度变为n1。显然删除前后两数组元素vjvjvj+1使得删除后的v数组变为v=v1,v2,vnl,vj和vj满足下列关系1ji-1ijn一1 proceduredelet(i：integer；varn：integer；beginif(in)thenwriteln(without)elsebeginforj：=iton1dovjdvj+1

12、；ndn1；end；elseend；deletvarv：vtype)；vi+1Dvn向前移动一个位置v数组的长度1同样，为了删除数组中第i000,则原来第i个元素之后的所有元素必须依次向前移动一个位置。如果要删除数组最后一个元素，则很简单，不需要移动数组元素；如果要删除数组的第一个元素，则很复杂，必须将数组中的所有元素依次向前移动一个位置。在一般情况下，要删除第个元素，需要将数组中第i+1到第n共ni个元素依次向前移动一个位置。执行delet过程的时间复杂度：对顺序存储的数组作一次删除，平均起来，大约需要移动表中一半的元素。综上所述，数组的顺序分配，其结构比较简单，便于随机访问数组中的任一元素

13、。但是如果数组要保持线性表特征的话（由下标指明元素间的有序性），其增删操作的效率比较低。特别当数组很大时，插入与删除运算颇为费时。因此，比较小的数组或元素不常变动（很少进行插入与删除运算）的数组可用作线性表，而对于大的线性表或元素经常变动的线性表，可以采用链式存储结构。三、数组的应用实例1、在编程时（使用任一种高级语言，不一定是Pascal)如果需要从磁盘文件中输入一个很大的二维数组（例如1000*1000的double型数组）按行读（即外层循环是关于行的）与按列读（即外层循环是关于列的）相比，在输入效率上（。）A.没有区别B.有一些区别，但机器处理速度很快，可忽略不计C.按行读的方式要高一些

14、D.按列读的方式要高一些E.取决于数组的存储方式。12栈栈是一种线性表，对它的插入和删除都限制在表的同一端进行。这一端叫做栈的“顶”，另一端则叫做栈的“底”。根据栈的定义，每次删除的总是当前“最年轻”的表目，即最后插入的表目，而最先插入的表后进先出表”(LIFOlastinput目则被放在栈的底部，要到最后才能删除。因此，栈又被称为“firstoutput）。仿佛食堂里的一叠盘子，每次只许一个一个地往上堆，一个一个地往下取。通常栈可以用顺序的方式存储，向当前栈顶。假设栈中表目数的上限为义栈：Const分配一块连续的存储区域存放栈中的表目，m,所有表目都具有同一类型并用一个变量t指stype,则

15、可以用下列方式定m=栈表目数的上限；Typestack=array1Dmofstype；Vars：stack；t：integer；mtu1(图121)栈类型栈栈顶指针栈的基本运算过程，一往栈中压入一个值为的表目procedurepush(vars：stack；x：stype；vart：integer)；beginift=mthenwriteln(overflow)上溢elsebegintdt+1；stUx；end；elsex入栈end；Push、函数,一从栈中弹出一个表目functionpop(vars：stack；vart：beginift=0thenwriteln(underflow)el

16、sebeginpopdst；tdend；popinteger)：stype；t-1；end；else下溢栈顶元素出栈函数，一读栈顶元素functiontop(s：stack；t：integer)：stype；beginift=0thenwriteln(stackempty)返回栈顶元素）的数据结构。elsetopdst；end；top二、栈的应用递归过程和函数调用时，处理参数和返回地址，通常使用一种称为（2.设栈S的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a那么栈容量至少应该是（）。AD6BD5CD4DD3ED23.某个车站呈狭长形，宽度只能容下一台车，

17、并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进出，进，进，进，出，出，进，进，进，出,出”。假设车辆入站的顺序为1，2，3，则车辆出站的顺序为（。）A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2E.1,4,3,7,54.地面上有标号为A、B、C的3根细柱,在A柱上放有10个直径相同中间有孔的圆盘,从上到下次依次编号为1,2,3,，将A柱上的部分盘子经过B柱移入C柱，也可以在B柱上暂存。A叮列BDODODCDDOODU链表EDD如果B柱上的操作记录为：“进，进，出，进，进，出，出，进，进，出，进，出，出”。那么，在C柱上，

18、从下到上的盘子的编号叮）。C.243176A.243657B.241257E.214375D.2436755.设栈S的初始状态为空，元素a,b,c,d,e依次入栈，以下出栈序列不可能出现的有（）（不定项）。A.a,b,c,e,dB.b,c,a,e,dC.a,e,c,b,dD.d,c,e,b,a6.表达式a*(b+c)-d的后缀表达式是：A)abcd*+-B)abc+*d-C)abc*+d-D)-+*abcd1D3队列一、队列的基本概念队列是不同于栈的另一种线性表。在日常生活中，无论是购物、订票或候车都有可能要排队。排队所遵循的原则是“先来先服务”日常生活中的排队现象抽象出来的。，后来者总是加到

19、队尾，排头者总是先离开队伍。队列就是从所谓队列，就是允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针指向队尾元素，即总是指向最后被插入的元素；允许删除的一端称为队首，通常也用一个队首指针指向排头元素的前面。初始时。 # abcdbcdBcd1e1 一个队列显然，在队列这种数据结构中，被删除，因此队列又称为“先进先出与栈相似，队列的顺序存储空间可以用一维数组Constm=队列元素的上限；队列的类型定义队列队尾指针和队首指针删除一个元素插入一个元素（图131）最先插入在元素将是最先被删除；反之最后插入的元素将最后”（FIFOfirstinfirstout）的

20、线性表。q1Dm模拟：Typeequeue=array1mofqtype；Varq：equeue；r，f：integer； # Q：1m（图312）二、队列的基本运算队列的运算主要有两种1、过程ADD(q,x,r)在队列procedureADD(varq：q的尾端插入元素xequeue；x：qtype；varr：integer）；beginifr=mthenwriteln(overflow)elsebeginrDr+1；qrDx；end；elseend；ADD后移队尾指针并插入元素上溢x2、过程DEL(q,y,f,r)取出q队列的队首元素yprocedureDEL(varq：equeue；va

21、ry：qtype；beginiff=rthenwriteln(underflow)elsebeginfDf+1；yDqf；end；elseend；DELvarf：integer)；后移队首指针并取出队首元素下溢 # #由于队列只能在一端插入,在另一端删除,因此随着入队及出队运算的不断进行,种有别于栈的情形：队列在数组中不断地向队尾方向移动,闲存储区,最后会导致当尾指针指向数组最后一个位置（即的前部却有一片存储区无端浪费,这种现象称为“就会出现一假溢出而在队首的前面产生一片不能利用的空r=m）而不能再加入元素时，存储空间”。例如： # #mmmrDmAm 1fDf，rD321初始时队列空f=r=

22、0加入三个元素f=0r=3删除三个元素队列空f=r=3fD321加入m-3个元素队列满r=mf=3 #（图133）三、循环队列及其运算所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间供队列循环使用，循环队列的定义如队列。 # 只要存储空间第一个位置空闲，便采用首尾相接的循环队列结构f=r=m。当存储空间的最后一个位置已被使用而要进行入队运算时，可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。后，可以有效地解决假溢出的问题，避免数据元素的移动。对循环队列操作有以下几种状态：初始时队列空，队首指针和队尾指针均指向存储空间的最后一个位置，即入队运算时，尾

23、指针进一，即rdr+1；ifr=m+1thenrd1；这两条语句可用一条语句替代：rd（r+1）modm；出队运算时，首指针进一，即fdf+1；iff=m+1thenfd1；这两条语句可用一条语句替代：fd（f+1）modm；队列空时有f=r。队列满时有f=（r+1）modm。（为了区分队列空和队列满，改用“队尾指针追上队首指针”这一特征作为队列满标志。这种处理方法的缺点是浪费队列空间的一个存储单元）循环队列的运算有两种：1、过程ADD2（q,x,r）在循环队列q中插入一个新元素xprocedureADD（varq：equeue；x：qtype；varr：integer）；begintd（r+

24、1）modm；计算插入位置ift=fthenwriteln（full）队列满新元素X插入队尾elsebeginrDt；qrDx；end；elseend；ADD2TOC o 1-5 h z2过程DEL2(q,y,f)从循环队列q中取出队首元素yprocedureDEL(varq：equeue；vary：qtype；varf：inteqer)；beginiff=rthenwriteln(empty)队列空elsebeginfD(f+1)modm；yDqf；取出队首元素end；elseend；DEL2四、队列的应用举例1.设栈S和队列Q的初始状态为空,元素e,e,e,e,e,e依次通过栈123456

25、S,一个元素出栈后即进入队列Q,若出队的顺序为e,e,e,e,e,e,则栈243651S的容量至少应该为（）。A)2B)3C)4D)514串但实际中我们经常要对一串元素进行操前面介绍的线性表的操作都是对一个元素进行处理的，作。如信息检查系统、文字编辑系统、自然语言翻译系统以及音乐分析程序等等，都是以字符串数据作为处理对象的。随着非数值的广泛应用，字符串的处理将显得越来越重要。一、串的基本概念串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这个串的长度。长度为 #零的串称为空串，它不包含任何字符。x1长度为2的0123长度为3的数0长度为0的空0包含一个空白字符（长度为通常用撇将字

26、符串括起来。例如1）的非空串 # #假设si和s2是两个串：s1=a1ans2=bibm #其中ai、bi代表字符（0DmDn）。如果存在整数i(0DiDn-m),使得 bj=ai+jj=1Dms1包含串s2。同时成立，则称s2是si000,0000中所能包含的字符依赖于具体机器的字符集,按字符的字符集中的次序可以规定字符的大 #小。目前世界上最为广泛的字符集是ASCII（美国信息变换标准码）和EBCDIC（扩充的二进制编l0码、十进制信息码)，它们都规定数字字符09的字符集是顺序排列的，字母字符AZ(az的字符集也是顺序排列的，因此用ord函数计算字符在字符集中的序号就有ord(a)ord(

27、b)ord(z)ord(0)ord(1)ord(q)并且对所有数字i(0WiW9)满足i=ord(i)-ord(0)通常可对两个字符chi和ch2作比较，所谓chlvch2的含义就是指ord(chl)vord(ch2)，必要时可以将串按其构成的字符用字符顺序排列，从而定义两个串的大小。例如aabox0121232程序中使用的串可以分成两种l、串常数串常数具有固定的串值，即可以用直接量表示，用以原样输出，亦可以给串常数命名，以便反复使用时书写和修改方便。例如constobject=datastructure；命名串常数writeln(overflow)原样输出串常数2、串变量串变量的取值是可以改

28、变的，但必须用名字来识别，说明串变量的方法与其它变量相似。例如vars：string30；上面定义了一个串变量s,s最多能容纳30个字符，且顺序存在一个字符数组中，类似于vars:array030ofchar；其中s0记载了s的实际长度。若string类型中省略长度标记，则串长上限为255个字符。二、串的基本运算PASCAL中提供了一些串运算的库函数，我们将作以简单的介绍1、连接运算函数concat(sl，s2，sn)其中值参s1,，sn为string类型，函数值为string类型。若连接后的串长大于255，则自动截断超出部分。2、求子串函数copy(s，i，l)其中值参s为string类型，

29、i和1为integer类型。函数返回s串中第i个字符开始、长度为1的子串(string类型)。若i大于s的长度，则回送一个空串；若l大于第i个字符开始的余串长度，则仅回送余串。3、删子串过程de1ete(vars，i，1)其中变量参数s为string类型，值参i、l为ingteger类型。该过程删去s中第i个字符开始的长度为l的子串，并返回剩余串s。若i大于原串s的长度，则不删任何字符；若l大于第i个字符开始的余串长度，则删去余串。ii4、插入子串过程变量参数置处，并返回插入后的结果insert（si，vars，i）string类型，值参s。若插入后si为string类型。该过程将s的串长大于

30、si子串插入空串255个字符，则截断超出部分。s的第i个字符位5、求串长函数length（s）值参s为string类型。该函数返回s串的实际长度值（integer类型）。pos（si，值参si和s2为string类型。若si是类型）；若si非s2的一个子串，则返回6、搜索子串位置函数s2）s2的一个子串，则返回si中第1个字符在s2串中的位置integer0。7、数值转换为数串过程值参x为integer类型或str（x，real类型，变量参数vars)Is为string类型。该过程将返回数值x对应的数串s。8、数串转换为数值过程值参s为string类型，变量参数试将s串转换成数值val（s，v

31、arv，varc）v为integer类型或v。若转换成功，则c为0,并返回对应的数值real类型，变量参数v；否则integer类型。该过程c为无效字符的序数。9、字符的大写转换函数值参ch为char类型。该函数返回upcase（ch）ch字符的大写皿char类型）三、串的应用实例1.字符串“ababacbab”和字符串“abcba”的最长公共子串是（）。A.abcbaB.cbaC.abcD.abE.bcba2.设字符串A29S=“Olympic”,S的非空字串的数目叮B28C16）。D17E第二章链式存储结构的线性表第一章所讨论的线性表的顺序存储结构具有存储数据元素方便的特点,构比较简单。但

32、是也存在着一些固有的缺点：1在作插入或删除运算时需要移动大量元素；2在给长度变化较大的线性表预先分配存储空间时,必须按最大空间分配,造成内存的无端浪费；3表的容量难以扩充；线性表的链或存储结构即能够方便地进行插入与删除操作而不必移动大量元素,配内存,可以方便地扩充表空间。因此,这种存储结构是线性表的一种有效表示方法。且插入与删除的算法结又无需预先分 21单链表 # 一、单链表的基本概念在链式存储结构的线性表中，数据元素的存储空间一般是不连续的。为了能够完整地表示线性表的逻辑结构，每一个数据元素的表示必须由两部分信息组成1数据元素的值；2数据元素在线性表中的逻辑位置；这两部分信息构成线性链表的一

33、个结点。因此，链式存储结构的线性表由若干个结点组成，每个结点有两个域：一个是数据域，用以存放数据元素的值；另一个是指针域，用以存放后件的存储地址。人们一般借助于高级语言的“指针”数据类型来描述这种数据结构。TypePointer=Dnodetype；nodetype=recorddata：elementype；数据域next：pointer；指针域end；varhead：pointer；head为表的首指针，指向链表的第一个结点。有时在链表的第一个结点前附设一个结点，该结点在单链表中每个结点的存储地址可以任意分配，即表中元素的存储位置可以不连续且是无序的，而它们的逻辑顺序由链表中的中p指针指向

34、a的结点，则iDDdata=a.,pDDnextMnext指针确定：假设线性表pDDnext指针指向值为data=a。i+1aa采用单链表的存储结构，其1na的结点(pDDnextnil)。换句话说i+1称为“哨兵”，head指向“哨兵”。整个链表的存取必须从head指针出发，沿每个结点的next指针顺序进行，最后一个结点的nnext指针为“空”(nil)。因此又称这种链式存储结构为单链表。例如存储地址数据域指针域1li437qian1313sun119wangnil25wu37head31zhao73137zheng1943zhou25二、单链表的操作1、动态建立单链表设线性表aa。试建立其

35、单链表的存储结构，其中1nProcedurecreat-Link(varhead：pointer)；beginheaddnil；fori：=ndownto1dobeginnew(p)；pDDdatada；ipDDnextdhead；headdp；end；fornew(p)；pDDnextdhead；headdp；end；creak_linkhead指向单链表的“哨兵”。建立一个空表生成一个值为a的结点i将新结点插入单链表第1个结点之前加“哨兵”2、插入操作在单链表的第i个结点前插入元素x。head为指向“哨兵”的首指针pocedureinsert_Link(x：elemenetype；i：in

36、teger；beginnew(s)；sDDdatadx；pdhead；jd0；while(pnil)and(ji-1)dobeginpdpDDnext；jdj+1；end；whileifpnilthenbeginsDDnextdpDDnext；pDDnextds；endthenelsewriteln(without)；end；insert_Linkvarhead：pointer）；生成值为x的结点p指向“哨兵”寻找单链表中第i1个结点第i1个结点后插入元素xi表长3、删除操作设head为指向“哨兵”的首指针。删除单链表的第i个结点。Proceduredelet_Link(i：integre；v

37、arhead：pointer)；beginpdhead；jd0；while(pDDnextnil)and(ji1)dobeginpdpDDnext；jdj+1；end；whileifpDDnext=nilthenwriteln(without)elsebeginp指向“哨兵”寻找第i1ODOpi表长删除第iODOqqdpDDnext；pDDnextdpDDnextDDnext；dispose(q)；end；elseend；delet_Link4、读取单链表元素设head为指向“哨兵”的首指针。读取单链表中第i个数据元素。functionget_Link（i：integer；varhead：Po

38、inter）：elementype；beginpDheadDDnext；jD1；p指向表中第1个结点while(pnil)and(ji)do顺next指针往后寻找第i个结点pbeginpDpDDnext；jDj+1；end；whileifp=nili表长thenwriteln(without)elseget_LinkDpDDdata；取得表中第i个结点值end；get_Link三、单链表的应用举例2D2双向循环链表以上讨论的线性单链表的结点中，只有一个指示后件的指针域只能顺next指针扩后寻查其它结点。若要寻查某结点的直接前趋，则需从“哨兵”next。因此，从某结点出发，head出发，另外，对

39、于空表与第一个结点的处理必须单独考虑，使得空表与非空表的运行不统一。为了克服单链表的这个缺点，我们引入了另一种链接方式双向循环链表。一、双向链表顾名思义，在双向链表的结点中有两个指针域，其一指向直接后继（）；另一个指向直接前趋（），u述如下：Typedupointer=Dnode；node=recorddata：elementype；数据域priou，next：dupointer；前趋指针，后继指针end；varda：dupointer；双向链表的“哨兵”“哨兵”的priou域为空（nil）,后继指针next指向链表的第一个结点，data域为空或者设置特定的值。在双向链表中插入或删除结点，需同

40、时修改两个方向的指针二、双向循环链表所谓双向循环链表，除了具备双向链表的特征外，还具有下述特点：.双向循环链表中，“哨兵”的域为任意或者根据需要设置，域指向线性表的第一个结点，域指向线性表的最后一个结点，哨兵指针指向“哨兵”；.双向循环链表中最后一个结点的域指向“哨兵”，即在双同循环链表中，所有结点的指针构造了一个环状链； # #显然，双向循环链表的定义与双向链表一致。对双向循环链表来说，有如下几种操作：1、构造双向循环链表lala为双向循环假设线性表中有n个数据元素a,a。试建立其双向循环链表存贮结构，1n链表的哨兵：procedurecreat_dulist(varla：dupointer

41、)；begin建立空表建立双向循环链表new(la)；laDDnextdla；laDDpriouDla；qDla；fori：=1tondobeginnew(p)；pDDdataDa；qDDnextDp；ipDDpriouDq；qDp；end；for qDDnextUla；laDDpriouUend；creat_dulistq；首尾相接叮读取双向循环链表中第i个结点的地址在la为“哨兵”的双向循环链表中，确定第长皿，则返回哨兵指针la：functionget_dulist（i，la）：beginpUlaDDnext；jU1；while（pla）and（ji）dobeginpUpDDnext；if

42、i个结点的地址。若dupointer；end；j=ithenget_dulistUelseget_dulistUget_dulistpnil；i表长，返回nil；若i=03、插入操作双向循环链表的哨兵指针为从第叮结点开始搜索jUj+1；end；whilex：procedureinsert_dulist(x：elementype；i：integer；varla：dupointer)；beginla。在该链表的第i个元素之前插入元素生成新结点new(s)；sDDdataUx；pUqet_dulist(i,la)；ifpnilthenbegins,寻找双向循环链表中的第i个结点pend；pDDpri

43、ouDDnextUs；在结点p前插入结点sDDpriouUpDDpriou；pDDpriouUs；sDDnextUp；end；thenselsewritein(without)；insert_dulist4、删除操作双向循环链表的哨兵为la。删除该链表中的第proceduredelet_dulist(i：integer；beginpUget_dulist(i，la)；ifpnilthenbeginpDDpriouDDnextUpDDnext；pDDendelsewriteln(without)；end；delet_dulisti个结点varla：qdupointer)；寻找双向循环链表中的第i

44、个结点ppnextDDpriouUpDDpriou；disPose(p)；从双向循环链表中删除结点三双向循环链表的应用实例1.在带尾指针（链表指针clist指向尾结点）的非空循环单链表中每个结点都以next字段的指针 指向下一个节点。假定其中已经有2个以上的结点。下面哪些说法是正确的：A）如果p指向一个待插入的新结点，在头部插入一个元素的语句序列为：pnext:=clistnext;clistnext:=p;B）如果p指向一个待插入的新结点，在尾部插入一个元素的语句序列为：pA.next:=clist;clistA.next:=p;C）在头部删除一个结点的语句序列为：p:=clistA.nex

45、t;clistA.next:=clistA.nextA.next;dispose（p）;D）在尾部删除一个结点的语句序列为。p:=clist;clist:=clistA.next;dispose（p）;第三章非线性结构（1）树前两章讨论的线性表（包括栈、队列、与串）属于线性结构。在这种结构中，不管其存储方式如何，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件（除第一个元素外）和一个后件（除最后一个元素外）。在实际生活中，可以用线性结构描述数据元素之间逻辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，因此在这类问题中，数据元素间的逻辑关系不能用线性结构明确、方便地

46、描述出来。例如某学校试图将学生成绩表中的百分制成绩转换成五个等级，其中成绩0D59分为不及格，60D69分为及格，70D79分为中，如何将他们的成绩转换成五级分制。一张简单的表，已经不能用线性结构来表示。80D89分为良，90D100分为优。现有n个学生的百分制成绩，（图31）揭示了一个百分制成绩的判定转换过程。对于这样因为表中数据元素可能有两个后件，它们之间的关系已经不是线性的了。 # #3至少存在一个结点（数据元素）有多于一个前件或后件的数据结构称为非线性结构。（图1）中所示的表是一个非线性结构。由该图可以看出，虽然每一个结点可能有多个后件，但它们的前件却只有一个（第一个结点无前件）。这种

47、非线性结构称为树，树表示了数据元素之间的层次关系，而这种层次关系仿佛像一棵倒长的树。下面讨论树的基本概念，其中重点讨论的是二叉树。 31树的基本概念及其存储结构一、树的概念树是一种常见的非线性的数据结构。树的递归定义如下：树是n（nO）个结点的有限集，这个集合满足以下条件：有且仅有一个结点没有前件（父亲结点），该结点称为树的根；除根外，其余的每个结点都有且仅有一个前件；除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）由上述定义可知，树结构没有封闭的回路。 # #其中除根结点外，有后件的结点（图3D1

48、1（b）中，r为根起点，w，h，e，f，s，m，o,n,j,u为叶结点；从根r到结点的唯一路径为rcti。一个结点的子树数目称为该结点的度。在（图311（b）中，结点i度为3,结点t的度为2,结点b的度为1。显然,所有树叶的度为0。所有结点中最大的度称为该树的度。(图3D11（b）中的树的度为3。在树中，一个结点包含一个元素以及所有指向其子树的分支，称为分支结点。而没有后件的结点称为树叶。由树的定义可知，树叶本身也是其父结点的子树。如 #树是分层次的。结点所在的层次是从根算起的。根结点在第一层,根的后件在第二层,其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。（图311

49、(b)中的 #树共有五层。在树中,父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度,亦称高度。（图3D11（b）中树的深度为5。 3D1（b）去掉根结点r,其原来的三所谓森林,是指若干棵互不相交的树的集合。如（图棵子树T,T,T的集合T,T,T就为森林。abcabc所谓有序树是指树中同层结点从左而右排列,其次序不容互换,这样的树称为有序树。二、树的表示方法和存储结构 # #树的表示方法很多。例如（图示法：先将根结点放入一对圆括号中,3D11）采用的就是自然界的树形表示法,常用的还有括号表然后把它的子树按由左而右的顺序放入括号中,而对子树也采 用同样方法处理：同层子树之间用逗号隔

50、开，最后用闭括号括起来。同层子树与它的根结点用圆括号括起来，ODD3D11（b）可写成如下形式（r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）所n（n为树的度）个指而树的存储结构有多种，其中使用较多的是链式存储结构。由于树中结点可以有多个元素，以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和针域共n+1个域组成，其表示方法如下：Constnl的度；Type例如DDtreetype=Dnode；node=recorddata：datatype；next：array1Dnoftreetype；end；结点类型数据域指向各儿子的指针域Varro

51、ot：treetype；3D11（b）的树，其多重链表为根结点指针显然，取树的度作为每个结点的链域数（即指向儿子结点的指针数造成存储空间的大量浪费。因为可能有很多结点中存在空链域。容易验证，为K的树中必存在n*（k1）+1个空链域，因此需要寻找一种恰当的树形式，相同、又要尽可能减少存储空间的浪费，方便运算。下面将要看到，用二叉树来表示树，就能达到这个目的。）虽使各种算法简化，但会一棵具有n个结点且度即要使每个结点的结构一、二叉树的基本概念和基本性质3D2二叉树1、二叉树的基本概念二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，右之分D次序不能任意颠倒）。下面给出二叉树的递

52、归定义：二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：有一个特定的结点称为根；余下的结点分为互不相交的子集L和R,其中R是根的左子树；且其子树有左L是根的右子树；L和R又是二叉树； 由上述定义可以看出，二叉树和树是两个不同的概念：树的每一个结点可以有任意多个后件，且子树可以不分次序（除有序树外）；而二叉树中每个结点的后件不能超过2且子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。前面引入的有关树的一些基本术语对二叉树仍然适用。（图321）列出二叉树的五种基本形态：满二叉树和完全二叉树是二叉树的两个特殊形态：满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰

53、有两棵非空子树，则此二叉树称作满二叉树。（例如图（3D22（a）可以验证具有个结点。完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于n个叶结点的满二叉树共有2，并且最下面一层的结点2n-1都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如（图2（b）3D22、二叉树的基本性质下面介绍地叉树的三个主要性质性质1：在二叉树的第iDD1）层上，最多有2i个结点 #证明数学归纳法i=1时只有一个根结点，即2i=2o=1,结论成立； #假设第k（i=k）层上最多有2k-i个结点;考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-i个结点，而每一个结点的度数最大为2，因此在第

54、k+1层上最多有2D2k-i=2（k+i）-i=2i,结论成立。综上所述，性质1成立。性质2：在深度为k（kD1）的二叉树中最多有2k-1个结点。证明由性质1，在二叉树第i层上最多有2i个结点，因此深度为k的二叉树最多有 # #2二2k一1个结点。i=i 性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。证明设n二叉树的叶结点数；n二叉树中度为1的结点数；01数；n=n+n+n（1）012由于二叉树中除了根结点外，其余每个结点都有且仅有一个分支进入。设n二叉树中度为2的结点2B为进入分支的总数，因此n=B+1又由于所有的进入分支是由度为1和度为将（3）代入（比较（1）和（即叶子数比度为B

55、=n+2n122)得出n=n+2n+1124)，得出n=n+1022的结点数多1（2）2的结点射出的，因此又有（3）（4）二、树或森林转换成二叉树1、普通有序树转换成二叉树我们在31中曾讲过，在用多重链表示普通树时，会浪费存储空间。另外，由于树中各结点的度各不相同，因此对树中各结点的搜索比较困难。在实际应用中，往往将普通树转化成二叉树，这种处理是极其有利的。假设所讨论的普通树为有序树T,则将其转化成二叉树T的规则如下：T中的结点与T中的结点一一对应；T中某结点N的第一个儿子结点为N,则在1T中N为对应结点N的左儿子结点；1T中某结点N的第一个儿子结点N以后的其它子结点，在1T中被依次链接成一串

56、开始于的右儿子结点；由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，将（图323（a）所示的普通有序树转换成二叉树然后从最左的儿子开始依次连接该结点的全部儿子。（图323（b）例如(3.2-3) # 2、森林转换为二叉树设森林F=T,T由m棵互不相交的普遍有序树组成。我们可以按下述规则将森林F转换成一1m棵二叉树B=root，LB，RB:若FOODm=O）,则BDOD；若FOODmD0),则B的根root即为森林中第一棵树的根root(T“B的左子树的根结点的子树森林F=T,T,T转换而成的二叉树；其右子树RB是从森林111

57、121kT,T转换成的二叉树。3mLB是从T1F=T，22例如 # #由此可见，森林转换成二叉树的方法为将各棵树的根相连；将森林中的每棵树转换成相应的二叉树；以第一棵树为轴心，顺时针粗略地旋转9Oo；三、二叉树的存储结构二叉树的存储结构有两种形式1、顺序存储结构编号的方法是从根结点开始编将每个结点依次存放在一维数组中，用数组下标指示结点编号，号1，然后由左而右进行连续编号。每个结点的信息包括数据值：data父结点编号：prt左儿子结点编号：lch右儿子结点编号：rch满二叉树和完全二叉树一般采用顺序存储结构Constm二树中结点数上限；Typenode=recorddata：datatype；

58、prt,lch,rch：ODm；end；treetype=array1Dmofnode；VarTree：treetype；结点类型数据值父结点、左儿子、右儿子编号二叉树的顺序表类型二叉树 # 例如采用数组tree存储二叉树 (a)(b)(图3.2-5)下面我们将普通有序树转换成二叉树，并使用顺序存储结构入信息含n行，其中第i行（1DiDn）的元素依次为结点i的数据值a。以后各元素为结点i的儿子序列，以i结点i为叶子。例如（图3DDDDDDD）的多叉树对应的输入信息为r2340a560b70c89100w0 x11120f0s0t13140u0d150e0i1617180j0h0m0o0h0转换

59、过程如下：fillchar（tree，sizeof（tree），0）；iD1；whileiDndobegin读结点i的数据值ai；treeiDdataDai；读结点i的第一个儿子序号j；ifj0thenbegintreeiDlchDj；treejDprtDi；pDj；Tree存储转换结果。普通有序树的输0结束。若a后仅含一个0，则说明i二叉树初始化从结点1开始输入若多叉树信息末输入处理完,则重复若结点j非叶子结点j作为结点i的左儿子从结点j出发转换其它兄弟结点 repeat读结点i的下一个儿子序号ifj0thenbegintreeprchDj；treejprtDp；pDj；end；thenj；

60、untilj=0；end；theni+1；换行；while3DDDDDDDdataiDend；例如（图结点j作为结点p的右儿子直至处理完结点i的所有儿子信息准备输入结点i+1的儿子信息tree数组如下：123456789101112131415161718r，020a153b，274c，380w，206X，5110f,300s，409t，81310u，900d，61512e，1100i，91614j，1300h，1100m，130170，16018n，1700）的多叉树经上述转换运算后得出的prtlchrch2、链式存储结构对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种