2023年自考数据结构重点总结最终修订

自考023３１数据结构重点总结(最终修订)第一章概论1．瑞士计算机科学家沃思提出:算法＋数据结构=程序。算法是对数据运算的描述,而数据结构涉及逻辑结构和存储结构。由此可见,程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法,而好的算法在很大限度上取决于描述实际问题的数据结构。２.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成,数据项是具有独立含义的最小标记单位。数据对象是具有相同性质的数据元素的集合。3.数据结构指的是数据元素之间的互相关系,即数据的组织形式。数据结构一般涉及以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算①数据的逻辑结构是从逻辑关系上描述数据,与数据元素的存储结构无关，是独立于计算机的。数据的逻辑结构分类:线性结构和非线性结构。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。②数据元素及其关系在计算机内的存储方式,称为数据的存储结构(物理结构）。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。③数据的运算。最常用的检索、插入、删除、更新、排序等。4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储(１）顺序存储:通常借助程序设计语言的数组描述。（2)链接存储:通常借助于程序语言的指针来描述。(３）索引存储:索引表由若干索引项组成。关键字是能唯一标记一个元素的一个或多个数据项的组合。（４）散列存储：该方法的基本思想是:根据元素的关键字直接计算出该元素的存储地址。５.算法必须满足５个准则:输入，0个或多个数据作为输入；输出,产生一个或多个输出；有穷性，算法执行有限步后结束;拟定性，每一条指令的含义都明确;可行性,算法是可行的。算法与程序的区别：程序必须依赖于计算机程序语言,而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Ｐascal和类Ｃ。6.评价算法的优劣：算法的"对的性"是一方面要考虑的。此外，重要考虑如下三点：ﻫ①执行算法所花费的时间,即时间复杂性;

②执行算法所花费的存储空间,重要是辅助空间，即空间复杂性；ﻫ③算法应易于理解、易于编程，易于调试等,即可读性和可操作性。以上几点最重要的是时间复杂性,时间复杂度常用渐进时间复杂度表达。7.算法求解问题的输入量称为问题的规模,用一个正整数n表达。8.常见的时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶0(lｏg2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶０(ｎ2)立方阶0(ｎ3）、…、k次方阶0（nk）、指数阶0(2n)和阶乘阶０(ｎ!)。9.一个算法的空间复杂度Ｓ(n)定义为该算法所花费的存储空间,它是问题规模ｎ的函数,它涉及存储算法自身所占的存储空间、算法的输入输出数据所占的存储空间和算法在运营过程中临时占用的存储空间。第二章线性表1.数据的运算是定义在逻辑结构上的,而运算的具体实现是在存储结构上进行的。

2.只要拟定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。3．常见的线性表的基本运算:(１)置空表InitList(L）构造一个空的线性表L。ﻫ（2)求表长ListLｅnｇtｈ（L)求线性表L中的结点个数，即求表长。

（３）GｅｔNode(L，i)取线性表L中的第ｉ个元素。ﻫ(4）ＬocａｔｅNｏde(L,ｘ)在L中查找第一个值为ｘ的元素，并返回该元素在L中的位置。若L中没有元素的值为x,则返回0值。

(5)InｓｅrtLｉst（L,i，ｘ）在线性表Ｌ的第i个元素之前插入一个值为x的新元素，表L的长度加１。

（6)DelｅteLｉst（Ｌ，i)删除线性表L的第i个元素，删除后表L的长度减1。4.顺序存储方法：把线性表的数据元素按逻辑顺序依次存放在一组地址连续的存储单元里的方法。顺序表(SequｅntｉaｌＬｉst）:用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻。顺序表中结点ai的存储地址:LOC（ai）=LＯC（a1)+（i-1）*c

1≤ｉ≤n，5.顺序表上实现的基本运算:（1）插入：该算法的平均时间复杂度是O（n）,即在顺序表上进行插入运算，平均要移动一半结点（n/2)。在第i个位置插入一个结点的移动次数为n-i+1(2)删除:顺序表上做删除运算,平均要移动表中约一半的结点（n-1）/２，平均时间复杂度也是O(n）。删除第i个结点移动次数为n-ｉ6.采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一拟定，因此单链表可以用头指针的名字来命名。①生成结点变量的标准函数p＝(ListＮode＊)malloｃ(siｚeof(ListＮodｅ));//函数ｍalloc分派一个类型为LｉstNｏde的结点变量的空间，并将其首地址放入指针变量p中②释放结点变量空间的标准函数freｅ(ｐ）;/／释放p所指的结点变量空间③结点分量的访问

方法二：ｐ－﹥daｔa和p-﹥next④指针变量p和结点变量*p的关系:指针变量p的值——结点地址,结点变量*ｐ的值——结点内容7.建立单链表:（１）头插法建表:算法：p=(LiｓtＮode*)mａlloc（sｉzｅof（ListNode));①/／生成新结点

p－>dａta=cｈ;②//将读入的数据放入新结点的数据域中

p->ｎexｔ＝heａd;③head=p;④

（２)尾插法建表：算法：p=（ＬiｓｔNodｅ*)maｌloc(ｓizeoｆ(ＬistNode));①//生成新结点ﻫ

p->ｄaｔa=cｈ;

②//将读入的数据放入新结点的数据域中

if(hｅaｄ==ＮULL)heａd＝p;//新结点插入空表

ｅlserear->ｎｅｘt=p;③//将新结点插到*r之后

rear=p;④/／尾指针指向新表尾(3）尾插法建带头结点的单链表：头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:ﻫ

⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊解决;

⒉无论链表是否为空,其头指针都是指向头结点的非空指针(空表中头结点的指针域空）,因此空表和非空表的解决也就统一了。头结点数据域的阴影表达该部分不存储信息。在有的应用中可用于存放表长等附加信息。ﻫ具体算法：r＝heaｄ;/／

尾指针初值也指向头结点

wｈｉlｅ(（ch=getchar())!=＇\n')｛ﻫ

s=(ＬistNｏｄｅ*)malloｃ(ｓizeｏf(ＬistNoｄe））;//生成新结点

s->data=ch;

／/将读入的数据放入新结点的数据域中ﻫ

r-＞next=ｓ;

r=s;}ﻫ

r->ｎext＝NUＬＬ;/／终端结点的指针域置空，或空表的头结点指针域置空以上三个算法的时间复杂度均为O(ｎ)。８.单链表上的查找:（带头结点)(1）按结点序号查找：序号为0的是头结点。算法：p＝hｅaｄ;j=0;／／从头结点开始扫描

while（ｐ－>ｎｅｘt&&j<i){//顺指针向后扫描,直到p－>nexｔ为NＵLＬ或i=ｊ为止ﻫ

p=ｐ-＞next;ﻫ

ｊ＋+;｝ﻫ

ｉｆ(i==ｊ)reｔurnp;//找到了第ｉ个结点ﻫ

elseｒｅtｕrnNＵＬL;//当ｉ<0或i>0时，找不到第i个结点

时间复杂度:在等概率假设下，平均时间复杂度为:为n／２=O（n)(2）按结点值查找:具体算法：ＬistNoｄｅ＊p=heａd－>ｎext；/／从开始结点比较。表非空，p初始值指向开始结点ﻫ

while（p&&p->dａtａ！=ｋey）//直到p为NUＬＬ或ｐ-＞ｄａta为key为止

p=p-＞ｎeｘt;／/扫描下一结点ﻫ

ｒetｕrｎp;//若p＝ＮUＬＬ,则查找失败，否则p指向值为key的结点时间复杂度为：O(n）9.插入运算:插入运算是将值为x的新结点插入到表的第i个结点的位置上,即插入到ai-1与ａi之间。

ﻫs=（LisｔNodｅ*)malloc（sizeoｆ(LisｔNoｄe)）;②s->datａ=x;③s->nexｔ=p－>neｘt;④p->ｎext=ｓ;⑤算法的时间重要花费在查找结点上,故时间复杂度亦为O（n)。ﻫ1０．删除运算

r=p->ｎｅｘt;②/／使r指向被删除的结点aip－>nｅxt=r－>next③;//将ai从链上摘下frｅe（ｒ）；④／/释放结点ai的空间给存储池算法的时间复杂度也是O（n).ｐ指向被删除的前一个结点。链表上实现的插入和删除运算,无须移动结点,仅需修改指针。11.单循环链表—在单链表中，将终端结点的指针域NUＬＬ改为指向表头结点或开始结点即可。判断空链表的条件是head=＝heaｄ->ｎｅｘt；１2.仅设尾指针的单循环链表:用尾指针rｅaｒ表达的单循环链表对开始结点a1和终端结点an查找时间都是O（１)。而表的操作经常是在表的首尾位置上进行，因此,实用中多采用尾指针表达单循环链表。判断空链表的条件为rear=＝rｅａr－>next;1３.循环链表：循环链表的特点是无须增长存储量，仅对表的链接方式稍作改变，即可使得表解决更加方便灵活。若在尾指针表达的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是Ｏ(1)。具体算法:ＬinｋLｉstＣonｎeｃt(ＬinkLｉstA,LinkLisｔB）

{//假设A,B为非空循环链表的尾指针LiｎｋListｐ=A-＞nｅxt;／／①保存Ａ表的头结点位置

A-＞ｎexｔ=B-＞next－>ｎｅxt；//②B表的开始结点链接到A表尾ﻫ

ｆrｅｅ(Ｂ－>next）;/／③释放B表的头结点ﻫ

B->nｅxｔ=p;／/④ﻫ

retｕrnB;//返回新循环链表的尾指针循环链表中没有NUＬＬ指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->nｅxt是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点出发,只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中,从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。14.双向链表:双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增长一个指向其直接前趋的指针域ｐｒior。①双链表由头指针hｅａd惟一拟定的。

②带头结点的双链表的某些运算变得方便。

③将头结点和尾结点链接起来，为双(向）循环链表。

15.双向链表的前插和删除本结点操作①双链表的前插操作vｏidＤIｎsertBefore(DListＮode＊p,ＤataTｙpex){//在带头结点的双链表中,将值为x的新结点插入*p之前,设p≠NULL

DLｉstＮｏde＊s＝mａlloc(sizeof(DLiｓtNode））;／／①ﻫ

s-＞ｄａta＝x;／／②ﻫ

s->prior=ｐ->prior;／/③ﻫ

s-＞next＝ｐ;//④

p-＞prior－＞next=s;//⑤

p－>prior=s；//⑥}ﻫ②双链表上删除结点*p自身的操作ﻫｖｏidＤDeｌeteNｏde(DLｉstNode*p)ﻫ

｛//在带头结点的双链表中，删除结点＊p,设＊p为非终端结点ﻫ

p->ｐｒior->ｎｅxt=p-＞neｘt；/／①ﻫ

ｐ－>nｅxt->prior＝ｐ->prior;//②

free（p）;}/／③

与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为Ｏ（1)。顺序表和链表比较时间性能：ａ、线性表:经常性的查找；b、链式存储结构：经常插入删除操作;空间性能:a、对数据量大小事先可以知道的用线性表;b、数据量变化较大的用链式存储结构。存储密度越大,存储空间的运用率越高。显然,顺序表的存储密度是１，链表的存储密度肯定小于１。第三章栈和队列１．栈称为后进先出（LastInＦｉrstOｕｔ）的线性表，简称为ＬIFO表。ﻫ栈是运算受限的线性表，顺序栈也是用数组表达的。ﻫ进栈操作：进栈时，需要将S-＞toｐ加1，①Ｓ-＞top＝=SｔackＳize－1表达栈满②"上溢"现象－－当栈满时,再做进栈运算产生空间溢出的现象。

退栈操作：退栈时,需将S-＞top减１,①S-＞tｏp＜０表达空栈②"下溢"现象--当栈空时，做退栈运算产生的溢出现象。

下溢是正常现象,常用作程序控制转移的条件。空栈时栈顶指针不能是0，只能是-1。两个栈共享同一存储空间:当程序中同时使用两个栈时，可以将两个栈的栈底分别设在顺序存储空间的两端,让两个栈顶各自向中间延伸。当一个栈中的元素较多而栈使用的空间超过共享空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。当Ｔop1=Tｏp2-1时，栈满

2．为了克服顺序存储分派固定空间所产生的溢出和空间浪费问题。可采用链式存储结构来存储栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。链栈中的结点是动态分派的,所以可以不考虑上溢,无须定义StaｃkFuｌl运算栈的一个重要应用是实现递归,直接调用自己或间接调用自己的函数。３.队列(Ｑueｕe）是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。允许删除的一端称为队头(Fｒont),允许插入的一端称为队尾（Reａr)，当队列中没有元素时称为空队列,队列亦称作先进先出（ＦirsｔInFｉrsｔOut）的线性表，简称为FＩFO表。队列的顺序存储结构称为顺序队列,顺序队列事实上是一个受限的线性表。

顺序队列的基本操作

①入队时：将新元素插入rear所指的位置,然后将rear加1。

②出队时：删去front所指的元素,然后将frｏnｔ加1并返回被删元素。当头尾指针相等时，队列为空。

在非空队列里，头指针始终指向队头元素，而队尾指针始终指向队尾元素的下一位置。而栈顶指针指向栈顶元素。循环队列：为充足运用数组空间，克服上溢，可将数组空间想象为一个环状空间,并称这种环状数组表达的队列为循环队列。循环队列中进行出队、入队操作时，头尾指针仍要加1,朝前移动。只但是当头尾指针指向向量上界(QuｅueSｉzｅ-1)时，其加1操作的结果是指向向量的下界0。这种循环意义下的加１操作可以描述为:①方法一：ﻫ

if（ｉ+1＝＝QuｅueＳｉze)i=0;//ｉ表达froｎt或reaｒﻫ

elｓｅｉ++;ﻫ②方法二-－运用"模运算＂ﻫ

i＝(i＋1)%ＱueuｅＳiｚｅ；循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针，导致队空和队满时头尾指针均相等。因此,无法通过条件Q.ｆｒont==Ｑ.reａr来判别队列是"空＂还是"满"。解决这个问题的方法至少有三种：ﻫ①另设一个标志位以区别队列是空还是满；ﻫ②设立一个计数器记录队列中元素的总数(即队列长度)。ﻫ③少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队列满即尾指针Q.rear所指的单元始终为空。 ５.循环队列的基本运算:①置队空:Q－>fronｔ=Q－>rear=0;②判队空:returｎQ－＞ｒeａr==Q－>front;③判队满:retｕrｎ(Ｑ->ｒeaｒ+1)%ＱueueＳizｅ==Q->frｏnｔ;④入队Q->data[Q->rear］＝x;

//新元素插入队尾ﻫQ-＞rｅar＝（Q->reaｒ+1）％QuｅuｅSize；

⑤出队ｔｅmp=Q->daｔa[Q-＞ｆrｏnt];ﻫＱ－＞front=(Ｑ->fｒont+１)%QueｕeSiｚe;

／/循环意义下的头指针加１

returｎtｅmｐ;⑥取队头元素returnQ－>dａｔa［Q－＞froｎt];队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。为了简化解决，在队头结点之前附加一个头结点，并设队头指针指向此结点。链队列的基本运算:(带头结点)(1)构造空队:Q->rｅａr＝Q->fｒonｔ;Q－>ｒeａｒ->nｅｘt=ＮUＬL;（2）判队空:returnQ－>reａr==Q->front;（３）入队：ＱueueNｏde*p=(QueｕeNoｄe*）ｍalloｃ（sizｅof(ＱｕeｕeNode)）;／/申请新结点

p-＞dａta=ｘ;

ｐ->nｅｘｔ=NULＬ;ﻫ

Q->ｒeａｒ->next=ｐ；

//＊ｐ链到原队尾结点后ﻫ

Q->rｅaｒ=p;

／／队尾指针指向新的尾（4）出队：当队列长度大于1时,只需修改头结点指针，尾指针不变

s=Q->fｒｏｎt->next；Q->fｒont－＞next=s->nｅxt；x＝s->datａ;fｒee(s);rｅｔuｒnｘ；当队列长度等于１时，不仅要修改头结点指针，还要修改尾指针s＝Q－>front-＞neｘt;Q->fｒont－>nｅｘｔ=ＮULＬ;Q－>rear=＝Ｑ－>ｆronｔ；x＝s－>data；frｅe（ｓ)；ｒeturnx；（5)取队头元素：returnQ->fｒont->ｎext->data;由于有头结点，所以用了ｎeｘｔ①和链栈类似,无须考虑判队满的运算及上溢。②在出队算法中,一般只需修改队头指针。但当原队中只有一个结点时,该结点既是队头也是队尾，故删去此结点时亦需修改尾指针,且删去此结点后队列变空。7.用计算机来解决计算算术表达式问题,一方面要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。第四章多维数组和广义表1.数组的顺序存储方式:一般采用顺序存储方法表达数组。(１)行优先顺序

ａ11,a1２,…，a1n,a21，a22,…，ａ2n,……，aｍ1,ａm2,…，aｍn（２）列优先顺序

ａ11,a２1，…,aｍ1，ａ12,a2２,…,am2，……，a1n，a2ｎ,…,aｍｎＰａscal和C语言是按行优先顺序存储的,而Forｔｒan语言是按列优先顺序存储的。按行优先顺序存储的二维数组Amn地址计算公式ﻫLＯC（aiｊ)＝LOC(ａ１1）+[(i-1)×n＋j-1]×ｄ（注:此公式下界为1,如下界为０,则公式变为[ｉ×n+j])按列优先顺序存储的二维数组Amｎ地址计算公式

LOＣ(aij）=LOC(a11)+[(j-1)×m＋i-1]×d(注：此公式下界为1，如下界为0，则公式变为［j×ｍ＋ｉ])按行优先顺序存储的三维数组Amｎp地址计算公式

LOC（aijk)=LＯＣ（a11１)+[(ｉ-1）×n×p+(j－1)×p+k-１]×d(注：此公式下界为1，如下界为0，则公式变为[i×n×ｐ+j×p＋k])2.为了节省存储空间,可以对矩阵中有许多值相同或值为零的元素的矩阵，采用压缩存储。特殊矩阵是指相同值的元素或零元素在矩阵中的分布有一定的规律。常见的有对称矩阵、三角矩阵。(1)对称矩阵在一个n阶方阵A中，若元素满足下述性质:

ａij=ａｊi0≤i,j≤n－1称为n阶对称矩阵，它的元素是关于主对角线对称的，所以只需要存储矩阵上三角或下三角元素即可,让两个对称的元素共享一个存储空间。矩阵元素aiｊ和数组元素sa【k】之间的关系是k=i×(ｉ+１)/2＋ji≥j0≤k<n（ｎ+1)/2-１k=j×(j＋1）/２+ii<ｊ0≤k<n(n+1)／2-1对称矩阵的地址计算公式：LOＣ(ａij）=LOC(ｓa[0])+[I×(I+1）/２+Ｊ]×d，其中Ｉ=ｍax（i,j)，Ｊ＝mｉn（i，j)（2）三角矩阵:以主对角线划分,三角矩阵有上三角和下三角两种。上三角矩阵是指它的下三角(不涉及主角线)中的元素均为常数c或零;下三角矩阵的主对角线上方均为常数ｃ或零。一般情况，三角矩阵的常数c均为零。三角矩阵的压缩存储:三角矩阵中的反复元素ｃ可共享一个存储空间，其余的元素正好有n×(ｎ+1)/２个,因此,三角矩阵可压缩存储在一维数组sa[n(ｎ+1)／２+１]中，其中c存放在数组的最后一个元素中。①上三角矩阵中ａｉｊ和sa［k]之间的相应关系k=i×(2n-i+１)/2＋j-i当i≤ｊk=n×（ｎ＋１)／２当i>ｊ②下三角矩阵中aij和sa[k］之间的相应关系k=i×(ｉ+1)/2＋j当i≥jk=n×(n+1）/2当ｉ<j三角矩阵的压缩存储结构是随机存取结构。３.稀疏矩阵:设矩阵Ａmn中有s个非零元素，若s远远小于矩阵元素的总数，则称A为稀疏矩阵。为了节省存储单元,可用压缩存储方法只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时,还必须存储非零元素所在的行、列位置,所以可用三元组(i,j，aij)来拟定非零元素。稀疏矩阵进行压缩存储通常有两类方法：顺序存储(三元组表)和链式存储(十字链表)。稀疏矩阵的压缩存储会失去随机存取功能。4．广义表是线性表的推广,又称列表。广义表是n(n≥0)个元素ａ1,a2,…,ai,…,ａn的有限序列。其中ａi或者是原子或者是一个广义表。

①广义表通常用圆括号括起来，用逗号分隔其中的元素。ﻫ

②为了区分原子和广义表，书写时用大写字母表达广义表,用小写字母表达原子。

③若广义表Ｌｓ非空(ｎ≥１)，则aｌ是LS的表头，其余元素组成的表(a1，a2，…，an)称为Ls的表尾。ﻫ

④广义表具有递归和共享的性质广义表的深度：一个表展开后所含括号的层数称为广义表的深度。１9.广义表是一种多层次的线性结构,事实上这就是一种树形结构。广义表的两个特殊的基本运算:取表头ｈeaｄ(Ls)和取表尾tail（Ls).任何一个非空广义表的表头可以是原子，也可以是子表,而其表尾必然是子表。ﻫ

head＝(a，b)=a，tａil(a，b)=（b)

对非空表Ａ和（y),也可继续分解。

注意:广义表(）和((）)不同。前者是长度为０的空表,对其不能做求表头和表尾的运算;而后者是长度为l的由空表作元素的广义表,可以分解得到的表头和表尾均是空表()。广义表是一种有层次的非线性结构,通常采用链式存储结构,每个元素用一个结点表达，结点由3个域构成,其中一个是tag标志位,用来区分结点是原子还是子表，当tａｇ为零时结点是子表，第二个域为slｉnk,用以存放子表的地址；当tａg为1时结点是原子，第二个域为ｄatａ，用以存放元素值。第五章树和二叉树1.树的表达法:最常用的是树形图表达法;尚有3种嵌套集合、凹形、广义表。树结构的基本术语

（1)结点的度(Degreｅ)

树中的一个结点拥有的子树数称为该结点的度(Dｅgｒｅe）。一棵树的度是指该树中结点的最大度数。ﻫ

度为零的结点称为叶子（Leaf)或终端结点。度不为零的结点称分支结点或非终端结点。ﻫ

除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。ﻫ（２)①途径（ｐatｈ）若树中存在一个结点序列ｋ1，ｋ２，…,kｉ,使得ｋｉ是ki+１的双亲（１≤i<j），则称该结点序列是从kl到kj的一条途径(Path)。ﻫ一个结点的祖先是从根结点到该结点途径上所通过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。

结点的层数（Leｖel)从根起算：根的层数为1,其余结点的层数等于其双亲结点的层数加１。ﻫ

双亲在同一层的结点互为堂兄弟。

树中结点的最大层数称为树的高度(Ｈeigｈt)或深度(Depth)。

若将树中每个结点的各子树当作是从左到右有顺序的（即不能互换）,则称该树为有序树（ＯrdeｒeｄTreｅ)；否则称为无序树（UnoｄeredTreｅ)。若不特别指明,一般讨论的树都是有序树。

森林(Forｅst)是ｍ（m≥0)棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根,就得到一个森林;反之，加上一个结点作树根,森林就变为一棵树。３.二叉树与度数为2的有序树不同：在有序树中,虽然一个结点的孩子之间是有左右顺序的，但是若该结点只有一个孩子,就无须区分其左右顺序。而在二叉树中,即使是一个孩子也有左右之分。二叉树的性质：性质1二叉树第i层上的结点数目最多为2i-１(i≥1)。例如5层的二叉树,第５层上的结点数目最多为24=16性质2深度为k的二叉树至多有２ｋ－1个结点（k≥1)。例如深度为5的二叉树，至多有25-1=31个结点性质３在任意－棵二叉树中，若终端结点的个数为n0,度为2的结点数为n２，则nｏ=n２+1。例如一棵深度为4的二叉树（a），其终端结点数n0为８,度为2的结点树为７,则８=7+1,ｎo=ｎ2+1成立(ｂ)其终端结点数ｎ0为6,度为2的结点树为５，则６＝５+1，no=n２+1成立满二叉树：一棵深度为k且有２k－1个结点的二又树称为满二叉树。满二叉树的特点:（1）每一层上的结点数都达成最大值。即对给定的高度,它是具有最多结点数的二叉树。（2)满二叉树中不存在度数为1的结点,每个分支结点均有两棵高度相同的子树,且树叶都在最下一层上。完全二叉树:若一棵深度为k的二叉树,其前ｋ-1层是一棵满二叉树,而最下面一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点:

(1）满二叉树是完全二叉树,完全二叉树不一定是满二叉树。

（2)在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。ﻫ

（3)在完全二叉树中,若某个结点没有左孩子,则它一定没有右孩子,即该结点必是叶结点。性质4

具有n个结点的完全二叉树的深度为。⌊lｏｇｎ⌋＋1或⌈ｌｏg(ｎ+1）⌉例，具有1００个结点的完全二叉树的深度为:⌊lg10０⌋+1=7,26＝6４27=１２8所以⌊lｇ1００⌋=6 ,⌈lg(１00＋1)⌉=７ﻩ4.完全二叉树的编号特点：完全二叉树中除最下面一层外,各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲,左、右孩子等结点的编号。编号从0开始①若i=0，则qｉ为根结点,无双亲;否则,ｑi的双亲编号为⌊（i-1）／2⌋。②若２i+1<n，则qｉ的左孩子的编号是2i＋1;否则,ｑｉ无左孩子,即ｑi必然是叶子。③若2i+2<n，则ｑｉ的右孩子的编号是2i+２;否则,ｑi无右孩子。对于完全二叉树而言，使用顺序存储结构既简朴又节省存储空间。但对于一般二叉树来说，采用顺序存储时,为了使用结点在数组中的相对位置来表达结点之间的逻辑关系，就必须增长一些虚结点使其成为完全二叉树的形式。5.链式存储结构:二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点自身的数据外，还应设立两个指针域lchilｄ和rｃｈilｄ,分别指向该结点的左孩子和右孩子。结点的结构为：二叉链表是一种常用的二叉树存储结构。建立二叉链表方法：ａ、按广义表方法，靠近左括号的结点是在左子树上,而逗号右边结点是在右子树上。b、按完全二叉树的层次顺序建立结点。具有ｎ个结点的二叉链表中,共有2ｎ个指针域。其中有n-1个用来指示结点的左、右孩子,其余的ｎ+1个为空。二叉树遍历算法中的递归终止条件是二叉树为空。中序遍历的递归算法定义：(1）遍历左子树；(2)访问根结点；(3)遍历右子树。先序遍历的递归算法定义:(1)访问根结点;(２）遍历左子树;（3）遍历右子树。后序遍历得递归算法定义：（１)遍历左子树；(2）遍历右子树；(3)访问根结点。递归工作栈中涉及两项：一项是递归调用的语句编号,另一项则是指向根结点的指针。已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列,可唯一拟定一棵二叉树。具体方法如下：一方面根据前序或后序遍历序列拟定二叉树的各子树的的根,然后根据中序遍历序列拟定各子树根的左右子树。6.线索二叉树：ｎ个结点的二叉链表必然存在ｎ+1个空指针域，可以运用这些空指针域,存放指向结点在某种遍历顺序下的前趋和后继结点的指针，这种指向前驱和后继结点的指针称为＂线索＂，这种加上线索的二叉链表称为线索链表,相应的二叉树称为线索二叉树(Threaded

BinaｒyＴｒｅｅ）。线索链表的结点结构:其中:ｌｔag和ｒtag是增长的两个标志域,用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。

ﻫ

ﻫﻫ

图中的实线表达指针,虚线表达线索。线索二叉树中,一个结点是叶结点的充要条件为:左、右标志均是1。7．二叉树的线索化:把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历顺序加线索的过程称为线索化。和中序遍历算法同样,递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树，线索化的算法时间复杂度为O(ｎ)。8．树、森林到二叉树的转换：树中每个结点最多只有一个最左边的孩子（长子)和一个右邻的兄弟。将树转换成二叉树：①在所有兄弟结点之间加一道连线;②对每个结点,除了保存与其长子的连线外,去掉该结点与其它孩子的连线。由于树根没有兄弟,故树转化为二叉树后，二叉树的根结点的右子树必为空。将一个森林转换为二叉树:将森林中的每棵树转化成二叉树,然后再将二叉树的根节点看做兄弟连在一起，形成一棵二叉树

9．二叉树到树、森林的转换：方式是:若二叉树中结点ｘ是双亲y的左孩子，则把ｘ的右孩子,右孩子的右孩子,…,都与ｙ用连线连起来,最后去掉所有双亲到右孩子的连线。１0.树的存储结构：1.双亲表达法:双亲链表表达法运用树中每个结点的双亲唯一性，在存储结点信息的同时，为每个结点附设一个指向其双亲的指针parenｔ，惟一地表达任何-棵树。(１)双亲链表表达法的实现分析:E和F所在结点的双亲域是１，它们的双亲结点在向量中的位置是1，即B是它们的双亲。ﻫ

注意:①根无双亲，其ｐａrent域为－１。

②双亲链表表达法中指针paｒｅnt向上链接，适合求指定结点的双亲或祖先(涉及根）;求指定结点的孩子或其它后代时，也许要遍历整个数组。2．孩子链表法:孩子链表表达法是为树中每个结点设立一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。注意:①孩子结点的数据域仅存放了它们在向量空间的序号。ﻫ

②与双亲链表表达法相反,孩子链表表达便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。

③将双亲链表表达法和孩子链表表达法结合起来,可形成双亲孩子链表表达法。3.孩子兄弟表达法：在存储结点信息的同时,附加两个分别指向该结点最左孩子和右邻兄弟的指针域，即可得树的孩子兄弟链表表达。注意：ﻫ

这种存储结构的最大优点是：它和二叉树的二叉链表表达完全同样。可运用二叉树的算法来实现对树的操作。

１１.树的遍历：一般都只给出两种顺序遍历树的方法:前序(先根顺序)遍历和后序(后根顺序)遍历。①前序遍历一棵树等价于前序遍历该树相应的二叉树

②后序遍历一棵树等价于中序遍历该树相应的二叉树。

对下面(a）图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABＣＤEFIGJH和ＢDCAIFJGHＥ。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFIGJH和BＤCＡIFJGＨE。前序遍历森林等同于前序遍历该森林相应的二叉树后序遍历森林等同于中序遍历该森林相应的二叉树12.从根结点到某结点之间的途径长度与该结点上权的乘积称为该结点的带权途径长度,树种所有叶子结点的带权途径长度之和称为树的带权途径长度。带权途径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。哈夫曼树不一定是二叉树。哈夫曼树又称为最优树,是一类带权途径长度最短的树。完全二叉树就是这种途径长度最短的二叉树。①只有叶结点上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。

②最优二叉树中,权越大的叶子离根越近。③最优二叉树的形态不唯一，WＰL最小。１３.哈夫曼算法:基本思想是：(1）根据给定的n个权值wl,w２，…,wn构成n棵二叉树的森林F=｛Ｔ1,T2,…,Tn}，其中每棵二叉树Ｔi中都只有一个权值为wi的根结点,其左右子树均空。

(２)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵),将这两棵树合并成一棵新树,为了保证新树仍是二叉树,需要增长一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左,谁右无关紧要）,将这两个孩子的权值之和作为新树根的权值。

(3)对新的森林F反复(2)，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。

注意:①初始森林中的n棵二叉树,每棵树有一个孤立的结点，它们既是根,又是叶子ﻫ

②ｎ个叶子的哈夫曼树要通过n-1次合并,产生n－1个新结点。最终求得的哈夫曼树中共有2ｎ-1个结点。ﻫ

③哈夫曼树是严格的二叉树，没有度数为1的分支结点。1４.哈夫曼编码:数据压缩过程称为编码，反之,解压缩的过程称为解码。设计一种长短不等的编码，则必须保证任一字符的编码都不是另一个字符编码的前缀,这种编码称为前缀编码。可以运用二叉树来设计二进制的前缀编码，其左分支表达字符0,右分支表达字符1，则以根结点到叶结点途径上的分支字符组成的串作为该叶节点的字符编码。因此设计电文总长最短的二进制前缀编码,就是以ｎ种字符出现的频率作为权构造一棵哈夫曼树,由哈夫曼树求得的编码就是哈夫曼编码。译码过程是从树根结点出发,逐个读入电文中的二进制码。第六章图1.图G由两个集合构成，顶点集合和边集合,也可以图G只有顶点而没有边。用尖括号表达图的有向边＜vi,vj>,有向边又称为弧,起点称为弧尾,终点称为弧头。无向图的顶点对用圆括号表达（vｉ，vｊ)。在无向图中，称ｖi和vｊ相邻接，在有向图中称顶点vi邻接到vj，顶点vｊ邻接于vi在无向图中,n的取值范围是0－n(n-１)/2，将具有n(n－1）/2条边的无向图称为无向完全图。在有向图中,n的取值范围是0-n(n-1)，将具有n(n-1)条边的有向图称为有向完全图。无向图中,顶点的度定义为以该顶点为一个端点的边的数目，有向图的度等于出度和入度之和。在无向图中,任意两顶点都有途径,则称两顶点连通。若图G中的任意两个顶点都连通，称Ｇ为连通图。无向图的极大连通子图称为连通分量，显然，任何连通图的连通分量只有一个,即其自身，而非连通的无向图有多个连通分量。在有向图中,图G中任意两顶点连通，称为强连通图，极大连通子图称为强连通分量。若在一个图的每条边上标上某种数值，该数值称为该边的权。边上带权的图称为带权图,带权的连通图称为网络。2.图的存储结构：邻接矩阵和邻接表表达法。图的顶点编号从0开始。邻接矩阵表达法：<vi,vj>或（vi,vj)是边，则值为1，不是边则值为０。无向图的邻接矩阵是按主对角线对称的。若G是带权图，只要把1换成相应边上的权值即可,０的位置上可以不动或将其换成无穷大表达。无向图的邻接矩阵表达法可以仅存储主对角线以下的元素,时间复杂度为Ｏ(n2）邻接表表达法:邻接表是图的一种链式存储结构。将无向图的邻接表称为边表,将有向图的邻接表称为出边表，将邻接表的表头向量称为顶点表。若无向图有n个顶点和e条边，则它的邻接表共有n个头结点和２e个表结点。建立邻接表的时间复杂度是Ｏ(ｎ+e）。图的邻接表表达不是唯一的,这是由于在每个顶点的邻接表中,各边结点的链接顺序可以是任意的,其具体链接顺序与边的输入顺序和生成算法有关。3．图的遍历:遍历图的算法是求解图的连通性、图的拓扑排序等算法的基础。图的遍历常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。深度优先搜索遍历(DFS)类似于前序(先根)遍历。按访问顶点的先后顺序得到的顶点序列称为图的深度优先遍历序列,或简称为DFＳ序列。共需要搜索n2个矩阵元素，时间复杂度为邻接矩阵O(n2)或邻接表O(ｎ＋e）。广度优先搜索遍历(ＢＦS)类似于树的按层次遍历,先被访问的顶点,其邻接点也先被访问，就是先进先出。时间复杂度为邻接矩阵O(n2）或邻接表Ｏ（n+e)，空间复杂度都是O(n）。4．生成树是连通图的包含图中所有顶点的一个极小连通子图，一个图的极小连通子图恰为一个无回路的连通图，也就是说，若图中任意添加一条边，就会出现回路，若去掉任意一条边，都会使之成为非连通图。因此,一个具有n个顶点的生成树有且仅有n-1条边,但有n-1条边的图不一定是生成树，同一个图可以有不同的生成树。生成树定义为：若从图的某顶点出发，可以系统的访问到图的所有顶点，则遍历时通过的边和图的所有顶点所构成的子图,称为该图的生成树。最小生成树：图的生成树不唯一，把权值最小的生成树称为最小生成树(MST）。构造最小生成树的算法：普里姆Prim算法的时间复杂度为O(ｎ２）与网中边数无关适于稠密图。克鲁斯卡尔Ｋruskal算法的时间复杂度为Ｏ（elogｅ),重要取决于边数,较适合于稀疏图。5.最短途径：Dｉｊｋｓtrａ迪杰斯特拉算法，提出了按途径长度递增的顺序产生诸顶点的最短途径算法。拓扑排序:子工程称为活动,顶点代表活动，有向边代表活动的先后关系。这样的有向无环图DAG称为顶点活动网,简称为AＯＶ网。将有向无环图G中所有顶点排成一个线性序列,若<ｕ，ｖ＞∈E（Ｇ）,则在线性序列u在ｖ之前,这种线性序列称为拓扑序列。由AOＶ网构造拓扑序列的过程称为拓扑排序。检测的方法是:对有向图构造其顶点的拓扑序列，若网中所有顶点都在他的拓扑序列中,则ＡOV网必然不存在环。ＡOV网的拓扑序列不是唯一的。拓扑排序的描述思想:a、在有向图中选一个没有前趋(入度为零)的顶点,且输出之。ｂ、从有向图中删除该顶点及其与该顶点有关的所有边。c、反复上述环节,直到所有顶点都已输出或图中剩余的顶点中没有前趋顶点为止。ｄ、输出剩余的无前趋结点。拓扑排序事实上是对邻接表表达的图Ｇ进行遍历的过程。时间复杂度是Ｏ(n+ｅ)。第七章排序１.假如待排序文献中存在多个关键字相同的记录,通过排序后,这些具有相同关键字的记录之间的相对顺序保持不变,该排序方法是稳定的；反之，则是不稳定的。排序在内存中解决,不涉及数据的内外存互换，称为内部排序，反之为外部排序。内部排序又分为五类：插入、选择、互换、归并和分派排序。在排序过程中需进行两种操作:比较两个关键字的大小、改变指向记录的指针或移动记录自身，而待排序记录的存储形式一般有三种:顺序结构、链式结构和辅助表。评价排序算法的标准：执行算法需要的时间,以及算法所需要的附加空间。尚有算法自身的复杂度。排序的时间开销,一般情况下可用算法中关键字的比较次数和记录的移动次数来衡量。2.插入排序:每次将一个待排序记录按其关键字大小插入到前面已排好序的文献中的适当位置。直接插入排序：每次从无序区取出第一个元素把它插入到有序区的适当位置,使之成为新的有序区，通过ｎ-1次插入后完毕。算法中R[0］作用：保存R[ｉ]副本，监视数组下标变量j是否越界。所以Ｒ[0］称为哨兵。每次的比较是从后往前比较的。时间复杂度最佳是O(n)，最坏是O(n2)，所以是Ｏ(n2)。空间复杂度O(1)，所以是就地排序。是稳定的算法。初始情况是有序区中只有一个元素R［１]，无序区中Ｒ［２..n]。希尔排序(缩小增量排序):算法不稳定。记录的总比较次数和总移动次数都要比直接插入排序少得多，特别是当ｎ越大越明显。希尔排序的时间依赖于增量序列，最后一个增量必须是1，尽量避免增量互为倍数的情况。3．互换排序：两两比较待排序记录的关键字,假如发现两个记录的顺序相反时即进行互换,直到没有反序位置。冒泡排序(起泡排序)：通过相邻元素之间比较和互换,使较小移向顶部,从后往前两两比较。时间复杂度最佳是O(ｎ)，最坏是O（n2），所以是Ｏ（n２)。是稳定的排序算法。快速排序（划分互换排序):是冒泡排序的改善。比较和互换从两端向中间进行。一趟快速排序环节:设两个指针i和j,初值分别为loｗ和ｈｉgｈ,基准为x＝R[i］,一方面从j位置开始向前搜索第一个小于基准x.key的记录存入ｉ所指位置上,ｉ自增1,然后从i所指位置向后搜索找到第一个大于基准x.key的记录存入j所指位置上,ｊ自减1，反复直至i=j为止。快速排序是不稳定的。有非常好的时间复杂度，优于其他各种排序算法,O(nlog２ｎ)，但是当记录关键字有序或基本有序时复杂度反而大了使之转变成冒泡排序为Ｏ(n2)。快速排序是递归的,需要一个栈空间,空间复杂度O（log2n)。4.选择排序：每一趟在待排序的记录中选出关键字最小的记录，依次存放在已排序好的记录序列的最后。直接选择排序:初始时，R[1..n]为无序区,Ｒ[1]为空;第一趟是在R[1..n]中选出最小的记录与R[1]互换,Ｒ［1］为有序区；第二趟是在R[2.．n］中选出最小的记录与R[2］互换,R［1．.２]为有序区。时间复杂度Ｏ(n2)，是不稳定的。初始情况是有序区为空，无序区中R[1..n］,第一趟从Ｒ[1..n］选择最小记录与Ｒ［1]互换。堆排序：是对直接选择排序的改善，是一种树形选择排序。基本思想：在排序过程中，将记录数组R[1..n]当作是一棵完全二叉树的顺序存储结构,运用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大或最小记录。每一趟排序：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将他和无序区中最后一个记录互换。堆排序是一个不断建堆的过程。构造堆的过程:R[1]作为二叉树的根，Ｒ[2.．n]依次逐层从左到右顺序排列，构成一棵完全二叉树,任意结点Ｒ[ｉ]的左孩子是R[2i],右孩子是R[2ｉ+1]，双亲是R⌊ｉ/2⌋,此称为筛选法。从⌊ｎ/２⌋开始。每一趟的时间复杂度是O(loｇ2n),整个堆排序的时间复杂度是Ｏ（nloｇ2n）。５.归并排序：一方面将待排序文献当作n个长度为1的有序子文献，把这些子文献两两归并,得到⌈n/2⌉个长度为2的有序子文献，然后再将他们两两归并，如此反复，直到得到一个长度为ｎ的有序文献，此称为二路归并排序。每一趟归并排序的时间复杂度是O（n)，所以总的时间复杂度是O(nlog２ｎ)。6.分派排序:前面方法都至少需要进行⌈nlogn⌉次比较,而分派排序将时间复杂度降为O(n）。箱排序(桶排序)：基数排序：是对箱排序的改善和推广。箱排序只合用于关键字取值范围较小的情况,否则所需箱子数目太多。每个分量也许取值的个数rｄ称为基数，基数的选择和关键字的分解因关键字的类型而异。d趟箱排序。基数排序中,没有进行关键字的比较和记录的移动,而只是扫描链表和进行指针赋值，所以排序的时间重要用在修改指针上，初始化链表时间为Ｏ(ｎ)。7.内部排序方法分析比较：本章除基数排序外,都是在顺序表上实现的。时间复杂度空间复杂度稳定性插入直接插入O(n2)O(1)稳定希尔排序O(nlｏｇ２n）或Ｏ(n1.25)O（１）不稳定互换冒泡排序Ｏ(n２)O(１）稳定快速排序O(nｌog2n）O（loｇ2n)不稳定选择直接选择Ｏ(n２)O(1)不稳定堆排序O(nlog2n)O（1)不稳定归并排序归并排序O(nｌｏg2ｎ）O(n)稳定分派排序基数排序O(d*（rｄ+n）)ｒd是基数,d是关键字位数．n是元素个数Ｏ(ｒｄ+n)稳定箱排序选取排序方法时需要考虑的重要因素：a、待排序的记录个数，b、记录自身的大小和存储结构,ｃ、关键字的分布情况,d、对排序稳定性的规定,ｅ、时间和空间复杂度要等排序方法的选取：a、若待排序的一组记录数目n较小(如ｎ≤５0)时，可采用插入排序或选择排序；b、n较大时，则应采用快速排序、堆排序或归并排序；c、若待排序记录按关键字基本有序时,则宜选用直接插入排序或冒泡排序；d、当n很大，并且关键字位数较少时,采用链式基数排序较好；ｅ、关键字比较次数与记录的初始排列顺序无关的排序方法是选择排序。一般的排序方法都可以在顺序结构上实现,当记录自身信息量较大时，可采用链式存储结构。插入、归并、基数排序易于在链表上实现；快速排序和堆排序可以提取关键字建立索引表,然后对索引表进行排序。第八章：查找1.查找又称检索，是数据解决中经常使用的一种重要运算。查找也分为内查找和外查找。运算查找的重要操作是关键字的比较，因此把查找过程中的平均比较次数（也称为平均查找长度)作为衡量算法效率优劣的标准。2.顺序表的查找:顺序查找和二分查找顺序查找又称线性查找:查找成功的平均查找长度（n＋1)/2，即约为表长的一半。假如查找成功和不成功机会相等,那么平均查找长度3（n+1)／4。优点是简朴，对表的结构无任何规定，无论是顺序存储和链式存储、无论是否有序，都同样合用,缺陷是效率低。对于有序表来说,该算法的平均查找长度是（n+1)/2。二分查找（折半查找):规定查找对象的线性表必须是顺序存储结构的有序表。查找过程是递归的。树中每个子树的根节点相应当前查找区间的中位记录Ｒ［mid]，它的左子树和右子树分别相应区间的左子表和右子表,通常将此树称为二叉鉴定树。由于二分查找是在有序表上进行的，所以其相应的鉴定树必然是一棵二叉排序树。二叉鉴定树一定是二叉排序树,二叉排序树又称为二叉查找树。从鉴定树上可见，关键字比较的次数恰好为该结点在树中的层数。因此,二分查找算法在查找成功时进行关键字比较的次数最多不超过鉴定树的深度。查找成功时的平均查找长度（n＋1)/nlｏg２(n+1）-１,当n很大时,可近似用ｌoｇ２(ｎ+1)－1表达。由于鉴定树度数小于2的结点只也许在最下面的两层,所以n个结点的鉴定树的深度和ｎ个结点的完全二叉树的深度相同,即为⌈ｌog2(ｎ+1)⌉。可见，二分查找的最坏性能和平均性能相称接近。二叉鉴定树的输出：每次以⌊(low＋ｈigｈ）/2⌋为根建树。3.索引顺序查找(分块查找）:是一种介于顺序查找和二分查找之间的查找方法。规定分块有序,前一块的最大关键字小于后一块的最小关键字,抽取各块中的最大关键字及其起始位置构成索引表。分块查找的基本思想是：一方面查找索引表,可用二分查找或顺序查找,然后在拟定的块中进行顺序查找。平均查找长度：二分查找lo