自学考试数据结构重点总结各章讲义精讲

自考数据结构重点

第一章概论

1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包含逻辑结构和存储

结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大

程度上取决于描述实际问题的数据结构。

2.数据是信息的载体°数据元素是数据的根本单位。一个数据元素可以由假设干个数据项组成，数据项是具有独立

含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。

3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。

数据结构一般包含以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算

①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。

数据的逻辑结构分类：线性结构和非线性结构

②数据元素及其关系在计算机内的存储方法，称为数据的存储结构(物理结构)。

数据的存储结构是逻辑结构用计算机言语的完成，它依赖于计算机言语。

③数据的运算。最常用的检索、插入、删除、更新、排序等。

4.数据的四种根本存储方法：顺序存储、链接存储、索引存储、散列存储

(1)顺序存储：通常借助程序设计言语的数组描述。

(2)链接存储：通常借助于程序言语的指针来描述。

(3)索引存储：索引表由假设干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。

(4)散列存储：该方法的根本思想是：依据元素的关键字直接计算出该元素的存储地址。

5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限

步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。

算法与程序的区别：程序必须依赖于计算机程序言语，而一个算法可用自然言语、计算机程序言语、数学言语或

约定的符号言语来描述。目前常用的描述算法言语有两类：类Pascal和类C。

6.评价算法的优劣：算法的"正确性”是首先要考虑的。此外，主要考虑如下三点：

①执行算法所消耗的时间，即时间复杂性；

②执行算法所消耗的存储空间，主要是辅助空间，即空间复杂性；

③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。

以上几点最主要的是时间复杂性，时间复杂度常用渐进时间复杂度表示。

7.算法求解问题的输入量称为问题的规模,用一个正整数n表示。

8.常见的时间复杂度按数量级递增排列依次为：常数阶0(1)、对数阶O(logzn)、线性阶0(n)、线性对数阶0(nlo&n)、

平方阶0行)立方阶0(/)、…、k次方阶0(吊)、指数阶0(2")和阶乘阶0(n!)。

9.一个算法的空间复杂度S(n)定义为该算法所消耗的存储空间，它是问题规模n的函数，它包含存储算法本身所占

的存储空间、算法的输入输出数据所占的存储空间和算法在运行过程中临时占用的存储空间。

第二章线性表

1.数据的运算是定义在逻辑结构上的，而运算的具体完成是在存储结构上进行的。

2.只要确定了线性表存储的起始位置，线性表中任意一个元素都可随机存取，所以顺序表是一种随机存取结构。

3.常见的线性表的根本运算：

(1)置空表InitList(L)构造一个空的线性表L。

(2)求表长ListLength(L)求线性表L中的结点个数，即求表长。

(3)GetNode(L,i)取线性表L中的第i个元素。

(DLocateNode(L,x)在L中查找第一个值为x的元素，并返回该元素在L中的位置。假设L中没有元素的值为x,

则返回0值。

(5)InsertList(L,i,x)在线性表L的第i个元素之前插入一个值为x的新元素，表L的长度加1。

(6)DeleteList(L,i)删除线性表L的第i个元素，删除后表L的长度减1。

4.顺序存储方法：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。

顺序表(SequentialList)：用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构，顺序表的特

点是逻辑上相邻的结点其物理位置亦相邻。

5.顺序表上完成的根本运算：

(1)插入：该算法的平均时间复杂度是0(n),即在顺序表上进行插入运算，平均要移动一半结点5/2)。

(2)删除：顺序表上做删除运算，平均要移动表中约一半的结点(nT)/2,平均时间复杂度也是0(n)。

6.采纳链式存储结构可以防止一再移动大量元素。一个单链表可由头指针唯一确定，因此单链表可以用头指针的名

字来命名。①生成结点变量的标准函数p=(ListNodeX)malloc(sizeof(ListNode))；〃函数malloc分

配一个类型为ListNode的结点变量的空间，并将其首地址放入指针变量p中②释放结点变量空间的标准函数

free(p)；//释放p所指的结点变量空间③结点重量的访问方法二：p->data和p->next

④指针变量p和结点变量Xp的关系：指针变量p的值一一结点地址，结点变量Xp的值一一结点内容

7,建立单链表：

(1)头插法建表：算法：p=(ListNodeX)malloc(sizeof(ListNode));①〃生成新结点

p->data=ch;②〃将读入的数据放入新结点的数据域中

p->next=head;(3)

head=p;④

hcnd."A|c|b|InI

户~T

S-L»|<l?||--------"J

将结点*S插到单俄表hcnd的头I.

(2)尾插法建表：算法：p=(ListNodeX)malloc(sizeof(ListNode));①〃生成新结点

p->data=ch;②〃将读入的数据放入新结点的数据域中

if(head==NULL)

head=p;〃新结点插入空表

else

rear->next=p;③〃将新结点插到Xr之后

rear=p;④〃尾指针指向新表尾

将新结点*5插到单链表head的尾上

(3)尾插法建带头结点的单链表：

头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点：

1.由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置

上操作一致,无须进行特别处理；

2.无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域空)，因此空表和非空

表的处理也就统一了。

头结点数据域的阴影表示该局部不存储信息。在有的应用

head头结点开始结点终端结点

n->i—中可用于存放表长等附加信息。

(n)中空表

闪

(b)空表

带头结点的单链表

具体算法：r=head;//尾指针初值也指向头结点

while((ch=getchar0)!='\n'){

s=(ListNodeX)malloc(sizeof(ListNode));〃生成新结点

s->data=ch;〃将读入的数据放入新结点的数据域中

r->next=s;

r=s;

)

r->next=NULL;〃终端结点的指针域置空，或空表的头结点指针域置空

以上三个算法的时间复杂度均为0(n)。

8.单链表上的查找带头结点)

(1)按结点序号查找：序号为0的是头结点。

算法：p=head;j=O;〃从头结点开始扫描

while(p->next&&j<i){〃顺指针向后扫描，直到p->next为NULL或i=j为止

p=p->next;

j++；

)

if(i==j)

returnp;〃找到了第i个结点

elsereturnNULL;〃当i<0或i>0时，找不到第i个结点

时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=0(n)

⑵按结点值查找:

具体算法：ListNodcXp=head->next;〃从开始结点比拟。表非空，p初始值指向开始结点

while(p&&p->data!=key)〃直到p为NULL或p->data为key为止

p=p->next;〃扫描下一结点

returnp;〃假设p=NULL,则查找失败，否则p指向值为key的结点

时间复杂度为：0(n)

9.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai与a,之间。

hend'

-―A||n|MI•••

1A

在单链表上插入结点示意图

s=(ListNodeX)malloc(sizeof(ListNode));②

s->data=x;(3)s->next=p->next@；p->next=s;⑤

算法的时间主要消耗在查找结点上，故时间复杂度亦为0(n)。

10.删除运算

hcnd'“，一—一

小11aJ4^•••

在单链表上删除结点示意图

r=p->next;②〃使r指向被删除的结点a：

p->next=r->next③;〃将a,从链上摘下

free(r);④〃释放结点a的空间给存储池

算法的时间复杂度也是0(n)»p指向被删除的前一个结点。

链表上完成的插入和删除运算，无须移动结点，仅需修改指针。

11.单循环链表一在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。推断空链表的条件是

head==head->next;

12.仅设尾指针的单循环链表：用尾指针rear表示的单循环链表对开始结点a,和终端结点a1,查找时间都是0(1)。而

表的操作常常是在表的首尾位置上进行，因此，有用中多采纳尾指针表示单循环链表。推断空链表的条件为

rear==rear->next;

♦(rear->next*renr

仅设尾指针的单循环链表

13.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方法稍作改变，即可使得表处理更加方便灵敏。假

设在尾指针表示的单循环链表上完成，则只需修改指针，无须遍历，其执行时间是0(1)。

两个单循环位表的位接操作示意图

具体算法：

LinkListConnect(LinkListA,LinkListB){〃假设A,B为非空循环链表的尾指针

LinkListp=A->next;〃①保存A表的头结点位置

A->next=B->next->ncxt;//②B表的开始结点链接到A表尾

free(B->next);〃③释放B表的头结点

B->next=p;〃④

returnB;〃返回新循环链表的尾指针

循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否

为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。

在单链表中，从一己知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单

循环链表中，从任一结点出发都可访问到表中全部结点，这一优点使某些运算在单循环链表上易于完成。

14.双向链表：双(向)链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指

向其直接前趋的指针域prior。

priordatanext①双链表由头指针head惟一确定的。

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

(a)结点结构(b)空的双循孙镇表③将头结点和尾结点链接起来，为双(向)循环链表。

—鼻

(c)」「空的双饰环链表

双链表示意图

15.双向链表的前插和删除本结点操作

①双链表的前插操作

双错表的前插操作

voidDInsertBefore(DListNodeXp,DataTypex){〃在带头结点的双链表中，将值为x的新结点插入Xp之前，设

pWNULL

DListNodeXs=malloc(sizeof(DListNode));〃①

s->data=x;//②

s->prior=p->prior;〃③

s->next=p;//(4)

p->prior->next=s"/⑤

p->prior=s;//@

)

②双链表上删除结点Xp自身的操作

①

voidDDe1eteNode(DListNodeXp)

{〃在带头结点的双链表中，删除结点Xp,设Xp为非终端结点

p->prior->next=p->next;//①

p->next->prior=p->prior;〃②

free(p);〃③

)

与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的

时间复杂度均为0(1)。

16.顺序表和链表比拟

时间性能：a、线性表：经常性的查找；b、链式存储结构：经常插入删除操作；

空间性能：a、对数据量大小事先能够了解的用线性表；b、数据量变化较大的用链式存储结构。

存储密度越大，存储空间的利用率越高。显然，顺序表的存储密度是1,链表的存储密度肯定小于1。

第三章栈和队列

1.栈称为后进先出(LastInFirstOut)的线性表，简称为LIFO表。

栈是运算受限的线性表，顺序栈也是用数组表示的。

进栈操作：进栈时，需要将S->top加1,①S->top==Stack$izeT表示栈满

②”上溢〃现象一当栈满时，再做进栈运算产生空间溢出的现象。

退栈操作：退栈时，需将S->top减1,①S->top〈0表示空栈

②"下溢"现象一当栈空时，做退栈运算产生的溢出现象。

下溢是正常现象，常用作程序操纵转移的条件。

空栈时栈顶指针不能是0,只能是-1。

当程序中同时使用两个栈时，可以将两个栈的栈底分别设在顺序存储空间的两端，让两个栈顶各自向中间延伸。当

一个栈中的元素较多而栈使用的空间超过共享空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者

的局部存储空间。

顺序枝<四，-栈公用个“他馆L般我为8人“”邮当Topl=Top2-l时，栈满

图_______®

Stackl中有栈空间岗

4个元素

§____

St.uk：3ik?

poshpop

2.为了克服顺序存储分配固定空间所产生的溢出和空间浪费问题。可采纳链式存储结构来存储栈。链栈是没有附加

头结点的运算受限的单链表。栈顶指针就是链表的头指针。

链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算

栈的一个重要应用是完成递归，直接调用自己或间接调用自己的函数。

3.同意删除的一端称为队头(Front),同意插入的一端称为队尾(Rear),当队列中没有元素时称为空队列，队列亦

称作先进先出(FirstInFirstOut)的线性表，简称为FIFO表。

嵯板不百国

(c)A出色(d)B、CH1队，队为空队列的顺序存储结构称为顺序队列，顺序队列实际上是一个受限的

顺序队列操作示意图线性表。

顺序队列的根本操作

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

②出队时：删去front所指的元素，然后将front加1并返回被删元素。

当头尾指针相等时，队列为空.

在非空队列里，头指针始终指向队头元素，而队尾指针始终指向队尾元素的下一位置。而栈顶指针指向栈顶元素。

4.循环队列：为充分利用数组空间，克服上溢，可将数组空间想象为一个环状空间，并称这种环状数组表示的队列

为循环队列。

循环队列中进行出队、入队操作时，头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界(QueueSize-1)

时，其加1操作的结果是指向向量的下界0,这种循环意义下的加1操作可以描述为：

①方法一：

if(i+l==QueueSize)//i表示front或rear

i=0;

else

i++；

②方法二一利用〃模运算〃

i=(i+l)%QueueSize；

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相

等。因此，无法通过条件Q.front==Q.rear来判别队列是“空"还是〃满"。

解决这个问题的方法至少有三种：

①另设一个标志位以区别队列是空还是满；

②设置一个计数器记录队列中元素的总数(即队列长度).

③少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，假设相等则认为队列

满即尾指针Q.rear所指的单元始终为空。

兀素入队操作世行中.个兀索人队循环队列

的北指Hrear将指向F个存储巾兀.

♦I入队O新开始O出队

5.循环队列的根本运算：

①置队空：Q->front=Q->rcar=0;

②判队空：returnQ->rear==Q->front;

③判队满：return(Q->rear+1)%QueueSize==Q->front;

④入队Q->dataQ->rear]=x;〃新元素插入队尾

Q->rear=(Q->rear+1)%QueueSize;

⑤出队temp=Q->dataQ->front];

Q->front=(Q->front+l)%QueueSize;〃循环意义下的头指针加1

returntemp;

⑥取队头元素returnQ->dataQ->front];

6.队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。

为了简化处理，在队头结点之前附加一个头结点，并设队头指针指向此结点。

*Q*Q-头,点一尾.点

Q-frontIAIQ-fror.i____：，I~H1b•••|A~|

Q-rear|八|

Q-*roar।

Q)空队列(b)非空队列

位队列示意图

链队列的根本运算：(带头结点)

(1)构造空队：Q->rear=Q->front；Q->rear->next=NULL;

(2)判队空：returnQ->rear==Q->front;

(3)入队：QueueNodeXp=(QueueNodeX)malloc(sizeof(QueueNode));〃申请新结点

p->data=x;p->next=NULL;

Q->rear->next=p;//Xp链到原队尾结点后

Q->rear=p;〃队尾指针指向新的尾

(4)出队：当队列长度大于1时，只需修改头结点指针，尾指针不变

s=Q->front->next;Q->front->next=s->next;

x=s->data;free(s);returnx;

当队列长度等于1时，不仅要修改头结点指针，还要修改尾指针

s=Q->front->next;Q->front->next=NULL;Q->rear==Q->front;

x=s->data;free(s);returnx;

(5)取队头元素：returnQ->front->next->data;因为有头结点，所以用了next

①和链栈类似，无须考虑判队满的运算及上溢。

②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点

时亦需修改尾指针，旦删去此结点后队列变空。

7.用计算机来处理计算算术表达式问题，首先要解决的问题是如何将人们习惯书写的中缀表达式转换成后缀表达式。

第四章多维数组和广义表

1.数组的顺序存储方法:一般采纳顺序存储方法表示数组。

(1)行优先顺序Qll,a⑵…,ain,321,322,•*,>32n,....，3ml,dm2,…，dmn

(2)列优先顺序an,a2i,—,a„i,ai2,a22,—,a„a,....，am,a2n，…,a®

Pascal和C言语是按行优先顺序存储的，而Fortran言语是按列优先顺序存储的.

2.为了节约存储空间，可以对矩阵中有许多值相同或值为零的元素的矩阵，采纳压缩存储。

特别矩阵是指相同值的元素或零元素在矩阵中的分布有肯定的规律。常见的有对称矩阵、三角矩阵。

(1)对称矩阵在一个n阶方阵A中，假设元素满足下述性质：a“=a」iOWi,jWnT

称为n阶对称矩阵，它的元素是关于主对角线对称的，所以只需要存储矩阵上三角或下三角元素即可，让两个

对称的元素共享一个存储空间。

矩阵元素以和数组元素sa[k]之间的关系是

k=iX(i+l)/2+ji2j0Wk〈n(n+l)/2T

k=jX(j+l)/2+ii<j0^k<n(n+l)/2-l

(2)三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。上三角矩阵是指它的下三角(不包含主角线)

中的元素均为常数c或零；下三角矩阵的主对角线上方均为常数c或零。一般情况，三角矩阵的常数c均为零。

三角矩阵的压缩存储：三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有nX(n+l)/2个，因此，

三角矩阵可压缩存储在一维数组san(n+l)/2+l］中，其中c存放在数组的最后一个元素中。

三角矩阵的压缩存储结构是随机存取结构。

3.稀疏矩阵:设矩阵鼠,中有s个非零元素，假设s远远小于矩阵元素的总数，则称A为稀疏矩阵。为了节约存储单

元，可用压缩存储方法只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还

必须存储非零元素所在的行、列位置，所以可用三元组(i,j,a“)来确定非零元素。

稀疏矩阵进行压缩存储通常有两类方法：顺序存储(三元组表)和链式存储(十字链表)。稀疏矩阵的压缩存储会失去

随机存取功能。

稀疏矩阵A和它的三元组表*a

4.广义表是线性表的推广，又称列表。

广义表是n(n2O)个元素a”a2,a,,a,,的有限序列。其中a：或者是原子或者是一个广义表。

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

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

③假设广义表Ls非空(n》l),则&是LS的表头，其余元素组成的表(a”a.)称为Ls的表尾。

④广义表具有递归和共享的性质

广义表的深度：一个表展开后所含括号的层数称为广义表的深度。

19.广义表是一种多层次的线性结构，实际上这就是一种树形结构。

任何一个非空广义表的表头可以是原子，也可以是子表，而其表尾必定是子表。

head=(a,b)=a,tail(a,b)=(b)对非空表A和(y),也可继续分解。

注意:广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为1的由

空表作元素的广义表，可以分解得到的表头和表尾均是空表()。

广义表是一种有层次的非线性结构，通常采纳链式存储结构，每个元素用一个结点表示，结点由3个域构成，其

中一个是tag标志位，用来区分结点是原子还是子表，当tag为零时结点是子表，第二个域为slink,用以存放子

表的地址；当tag为1时结点是原子，第二个域为data,用以存放元素值。

第五章树和二叉树

1.树的表示法：最常用的是树形图表示法；还有3种嵌套集合、凹形、广义表。

树结构的根本术语

⑴结点的度(Degree)

树中的一个结点拥有的子树数称为该结点的度(Degree)。一棵树的度是指该树中结点的最大度数。

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

除根结点之外的分支结点统称为内部结点。根结点又称为开始结点。

⑵①路径(path)假设树中存在一个结点序列k“…，k”使得k,是k.的双亲(lWi<j),则称该结点序列

是从h到k,的一条路径(Path)。

一个结点的祖先是从根结点到该结点路径上所经过的全部结点，而一个结点的子孙则是以该结点为根的子树

中的全部结点。

结点的层数(Level)从根起算：根的层数为1,其余结点的层数等于其双亲结点的层数加1。

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

树中结点的最大层数称为树的高度(Height)或深度(Depth)。

假设将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；

否则称为无序树(UnoderedTree)。假设不特别指明，一般商量的树都是有序树。

森林(Forest)是棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林;

反之，加上一个结点作树根，森林就变为一棵树。

3.二叉树与度数为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是假设该结点只有

一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。

二叉树的性质：

性质1二叉树第i层上的结点数目最多为2i(iNl)。例如5层的二叉树，第5层上的结点数目最多为2'=16

性质2深度为k的二叉树至多有2卜-1个结点(k》l)。例如深度为5的二叉树，至多有25-1=31个结点

性质3在任意一棵二叉树中，假设终端结点的个数为n。，度为2的结点数为窕，则nFm+1。例如一棵深度为4的二

叉树(a),其终端结点数n。为8,度为2的结点树为7,则8=7+1,nxm+l成立

(b)其终端结点数n。为6,度为2的结点树为5,则6=5+1,n0=m+l成立

(n)W义树0>)完全：叉树(c)非完全XW

特姝形态的二乂料

满二叉树：一棵深度为k且有2kT个结点的二又树称为满二

叉树。满二叉树的特点：

(1)每一层上的结点数都到达最大值。即对给定的高度，它是具有最多结点数的二叉树。

(2)满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。

完全二叉树：假设一棵深度为k的二叉树，其前k-1层是一棵满二叉树，而最下面一层上的结点都集中在该层最左

边的假设干位置上，则此二叉树称为完全二叉树。特点：

(1)满二叉树是完全二叉树，完全二叉树不肯定是满二叉树。

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

(3)在完全二叉树中，假设某个结点没有左孩子，则它肯定没有右孩子，即该结点必是叶结点。

性质4具有n个结点的完全二叉树的深度为。口ognj+l或Rog(n+D]

例，具有100个结点的完全二叉树的深度为：[IglOO1+1=7,2，=642=128^lULlglOOj=6,[1g(100+1)1=7

4.完全二叉树的编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结

点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子等结点的编号。编号从。开始

①假设i=0,则q,为根结点，无双亲；否则，q,的双亲编号为[(iT)/2」。

②假设2i+l〈n,则q,的左孩子的编号是2i+l；否则，q,无左孩子，即卬必定是叶子。

③假设2i+2<n,则5的右孩子的编号是2i+2；否则，q：无右孩子。

对于完全二叉树而言，使用顺序存储结构既简单又节约存储空间。但对于一般二叉树来说，采纳顺序存储时，为了

使用结点在数组中的相对位置来表示结点之间的逻辑关系，就必须增加一些虚结点使其成为完全二叉树的形式。

5.链式存储结构：二叉树的每个结点最多有两个孩子。用链接方法存储二叉树时，每个结点除了存储结点本身的数据

外，还应设置两个指针域Ichild和rchild,分别指向该结点的左孩子和右孩子。结点的结构为：I'\rI'1,dl

二叉链表是一种常用的二叉树存储结构。

建立二叉链表方法：a、按广义表方法，靠近左括号的结点是在左子树上，而逗号右边结点是在右子树上。

b、按完全二叉树的层次顺序建立结点。

具有n个结点的二叉链表中，共有2n个指针域。其中有nT个用来指示结点的左、右孩子，其余的n+1个为空。

二叉树遍历算法中的递归终止条件是二叉树为空。

递归工作栈中包含两项：一项为哪一项递归调用的语句编号，另一项则是指向根结点的指针。

已知一棵二叉树的前序和中序遍历序列或中序和后序遍历序列，可唯一确定一棵二叉树。具体方法如下：

首先依据前序或后序遍历序列确定二叉树的各子树的的根，然后依据中序遍历序列确定各子树根的左右子树。

6.线索二叉树：n个结点的二叉链表必定存在n+1个空指针域，可以利用这些空指针域，存放指向结点在某种遍历

次序下的前趋和后继结点的指针，这种指向前驱和后继结点的指针称为‘'线索"，这种加上线索的二叉链表称为线索

链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)»

线索链表的结点结构：

统制:中的结点量为：其中：ltag和rtag是增加的两个标志域，用来区分结点的左、右指针

lchild|ltag〔data|rtag|rc研域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。

J。：凝指向结点的右孩子的指针

左标志jfag1就封凝指向结点的左孩子的指针右标志rfag=

tl：娓指向结点的前趋的左线索rc地娓指向结点的后继的右线索

/1/101.017\

中印税索ta表

图中的实线表示指针，虚线表示线索。

线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。

7.二叉树的线索化：把对一棵二叉线索链表结构中全部结点的空指针域按照某种遍历次序加线索的过程称为线索

化。

和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树，线索化的算法时间复杂度

为0(n)。

(c)二叉线索链表

8.树、森林到二叉树的转换：树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。

将树转换成二叉树：①在全部兄弟结点之间加一道连线；②对每个结点，除了保存与其长子的连线外，去掉该结点

与其它孩子的连线。由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。

树到二叉树的转换树到二叉树的转换

第步：第二步：

在树中所有兄弟结点对每个结点,除了保

之间加一连线留।j式的氏r的连线外,

去掉该结点♦其他孩了的

连线

树到二叉树的转换

将一个森林转换为二叉树：

将森林中的每棵树转化成二叉树，然后再将二叉树的根节点看做兄弟连在一起,形成一棵二叉树

森林转化为二叉树森林转化为二叉树

第一步：

先招森林中的每棵

树变为二叉树

森林转化为二叉树boho

第二步：

将备二叉树的根结点视

为兄弟从左至右连在一

起，就形成了一棵一又

树

9.二叉树到树、森林的转换：

方法是：假设二叉树中结点x是双亲y的左孩子，则把x

的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉全部双亲到右孩子的连线。

义树到树、森林的转换bobo

10.树的存储结构：

1.双亲表示法：双亲链表表示法利用树中每个结点的双亲唯一性，

在存储结点信息的同时，为每个结点附设一个指向其双亲的指针

parent,惟一地表示任何一棵树。

(1)双亲链表表示法的完成

分析：E和F所在结点的双亲域是1,它们的双亲结点在向量中的位

置是1,即B是它们的双亲。

注意：①根无双亲，其parent域为-1。图6.17(a)

②双亲链表表示法中指针parent向上链接，合适求指定结MaxTreeSize-1

下标0123456789

点的双亲或祖先(包含根)；求指定结点的孩子或其它后代时，可能dntnABCDEFGIIIJ

2

要遍历整个数组。pnrcnl-100011333

2.孩子链表法：孩子链表表示法是为树中每个结点设置一个孩子链图6.17树转化为：叉树(a)所示乂树的&求链表T

表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。

图6.17树转化为义树(a)中树的孩子链表表示法

注意：①孩子结点的数据域仅存放了它们在向量空间的序号。

②与双亲链表表示法相反，孩子链表表示便于完成涉及孩子及其子孙的运算，但不便于完成与双亲有关的运算。

③将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。

3.孩子兄弟表示法：在存储结点信息的同时、附加两个分别指向该结点最左孩子和右邻兄弟的指针域，即可得树的

孩子兄弟链表表示。

注意：

这种存储结构的最大优点是：它和二叉树的二叉链

表表示完全一样•可利用二叉树的算法来完成对树的操

作。

11.树的遍历:

一般都只给出两种次序遍历树的方法：前序(先根次序)遍历和后序(后根次序)遍历。

①前序遍历一棵树等价于前序遍历该树对应的二叉树

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

对下面(a)图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFIGJII和

BDCA1FJGHE。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEF1GJH和BDCA1FJGHE«

①前序遍历森林等同于前序遍历该森林对应的二叉树

②后序遍历森林等同于中序遍历该森林对应的二叉树

12.从根结点到某结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度，树种全部叶子结点的带权路

径长度之和称为树的带权路径长度。带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。

哈夫曼树不肯定是二叉树。

哈夫曼树又称为最优树，是一类带权路径长度最短的粉。完全二叉树就是这种路径长度最短的二叉树。

①只有叶结点上的权值均相同时，完全二叉树肯定是最优二叉树，否则完全二叉树不肯定是最优二叉树。

②最优二叉树中，权越大的叶子离根越近。③最优二叉树的形态不唯一，WPL最小。

13.哈夫曼算法：

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

②n个叶子的哈夫曼树要经过nT次合并，产生nT个新结点。最终求得的哈夫曼树有2nT个结点。

③哈夫曼树是严格的二叉树，没有度数为1的分支结点。

14.哈夫曼编码：

数据压缩过程称为编码,反之，解压缩的过程称为解码。

设计一种长短不等的编码，则必须保证任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。

可以利用二叉树来设计二进制的前缀编码，其左分支表示字符0,右分支表示字符1,则以根结点到叶结点路径上的

分支字符组成的串作为该叶节点的字符编码。

因此设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作为权构造一棵哈夫曼树，由哈夫曼树求

得的编码就是哈夫曼编码。

译码过程是从树根结点出发，逐个读入电文中的二进制码。

第六章

1.图G由两个集合构成，顶点集合和边集合，也可以图G只有顶点而没有边。用尖括号表示图的有向边＜v“v」＞,有向

边又称为弧，起点称为弧尾，终点称为弧头。无向图的顶点对用圆括号表示(Vi,Vj)。

在无向图中，称Vi和V,相邻接，在有向图中称顶点y邻接到V“顶点V,邻接于V;

在无向图中，n的取值范围是0-n(n-l)/2,将具有n(nT)/2条边的无向图称为无向完全图。

在有向图中，n的取值范围是O-n(n-l),将具有n(n-1)条边的有向图称为有向完全图。

无向图中，顶点的度定义为以该顶点为一个端点的边的数目，有向图的度等于出度和入度之和。

在无向图中，任意两顶点都有路径，则称两顶点连通。假设图G中的任意两个顶点都连通，称G为连通图。无向

图的极X通子图称为连通重量，显然，任何连通图的连通重量只有一个，即其自身，而非连通的无向图有多个连通

重量。

在有向图中，图G中任意两顶点连通，称为强连通图，极X通子图称为强连通重量。

假设在一个图的每条边上标上某种数值，该数值称为该边的权。边上带权的图称为带权图，带权的连通图称为网络。

2.图的存储结构：邻接矩阵和邻接表表示法。图的顶点编号从0开始。

邻接矩阵表示法：3”打＞或刖,门)是边，则值为1,不是边则值为0。

无向图的邻接矩阵是按主对角线对称的。假设G是带权图，只要把1换成相应边上的权值即可，0的位置上可以不

动或将其换成无穷大表示。无向图的邻接矩阵表示法可以仅存储主对角线以下的元素，时间复杂度为0(一)

邻接表表示法：邻接表是图的一种链式存储结构。将无向图的邻接表称为边表，将有向图的邻接表称为出边表，

将邻接表的表头向量称为顶点表。假设无向图有n个顶点和e条边，则它的邻接表共有n个头结点和2e个表结点。

建立邻接表的时间复杂度是O(n+e)。图的邻接表表示不是唯一的，这是因为在每个顶点的邻接表中，各边结点的

链接次序可以是任意的，其具体链接次序与边的输入次序和生成算法有关。

3.图的遍历：遍历图的算法是求解图的连通性、图的拓扑排序等算法的根底。

图的遍历常用的是深度优先搜索遍历和广度优先搜索遍历两种方法。

深度优先搜索遍历(DFS)类似于前序(先根)遍历。按访问顶点的先后次序得到的顶点序列称为图的深度优先遍历序

列，或简称为DFS序列。共需要搜索/个矩阵元素，时间复杂度为邻接矩阵0(/)或邻接表O(n+e)。

广度优先搜索遍历(BFS)类似于树的按层次遍历，先被访问的顶点，其邻接点也先被访问，就是先进先出。

时间复杂度为邻接矩阵0(一)或邻接表0(n+e),空间复杂度都是0(n)。

4.生成树是连通图的包含图中全部顶点的一个极小连通子图，一个图的极小连通子图恰为一个无回路的连通图，也

就是说，假设图中任意添加一条边，就会出现回路，假设去掉任意一条边，都会使之成为非连通图。

因此，一个具有n个顶点的生成树有且仅有n-1条边，但有n-1条边的图不肯定是生成树，同一个图可以有不同

的生成树。

生成树定义为：假设从图的某顶点出发，可以系统的访问到图的全部顶点，则遍历时经过的边和图的全部顶点所

构成的子图，称为该图的生成树。

最小生成树：图的生成树不唯一，把权值最小的生成树称为最小生成树(MST)。

构造最小生成树的算法：普里姆Prim算法的时间复杂度为0(n2)与网中边数无关适于稠密图。

克鲁斯卡尔Kruskal算法的时间复杂度为0leloge),主要取决于边数，较合适于稀疏图。

5.最短路径：Dijkstra迪杰斯特拉算法，提出了按路径长度递增的顺序产生诸顶点的最短路径算法。

拓扑排序：子工程称为活动，顶点代表活动，有向边代表活动的先后关系。这样的有向无环图DAG称为顶点活动

网，简称为AOV网。将有向无环图G中全部顶点排成一个线性序列，假设＜u,v〉CE(G),则在线性序列u在v

之前，这种线性序列称为拓扑序列。由AOV网构造拓扑序列的过程称为拓扑排序。

检测的方法是：对有向图构造其顶点的拓扑序列，假设网中全部顶点都在他的拓扑序列中，则AOV网必定不存在

环。

AOV网的拓扑序列不是唯一的。

拓扑排序的描述思想：a、在有向图中选一个没有前趋(入度为零)的顶点，且输出之。b、从有向图中删除该顶点

及其与该顶点有关的全部边。c、重复上述步骤，直到全部顶点都已输出或图中剩余的顶点中没有前趋顶点为止。

d、输出剩余的无前趋结点。

拓扑排序实际上是对邻接表表示的图G进行遍历的过程。时间复杂度是0(n+e)。

第七章排序

1.如果待排序文件中存在多个关键字相同的记录，经过排序后，这些具有相同关键字的记录之间的相对次序保持不

变，该排序方法是稳定的；反之，则是不稳定的。

排序在内存中处理，不涉及数据的内外存交换，称为内部排序，反之为外部排序。内部排序又分为五类：插入、

选择、交换、归并和分配排序.

在排序过程中需进行两种操作：比拟两个关键字的大小、改变指向记录的指针或移动记录本身，而待排序记录的

存储形式一般有三种：顺序结构、链式结构和辅助表。

评价排序算法的标准：执行算法需要的时间，以及算法所需要的附加空间。还有算法本身的复杂度。

排序的时间开销，一般情况下可用算法中关键字的比拟次数和记录的移动次数来衡量。

2.插入排序：每次将一个待排序记录按其关键字大小插入到前面已排好序的文件中的适当位置。

直接插入排序：每次从无序区取出第一个元素把它插入到有序区的适当位置，使之成为新的有序区，经过n-1次

插入后完成。算法中R0］作用：保存Ri］副本，监视数组下标变量j是否越界。所以R0］称为哨兵。每次的比拟是从

后往前比拟的。

时间复杂度最好是0(n),最坏是0(/),所以是0(/)。空间复杂度0(1),所以是就地排序。是稳定的算法。

初始情况是有序区中只有一个元素R1］,无序区中R2..n］。

希尔排序(缩小增量排序)：算法不稳定。记录的总比拟次数和总移动次数都要比直接插入排序少得多，特别是当

n越大越明显。希尔排序的时间依赖于增量序列，最后一个增量必须是1,尽量防止增量互为倍数的情况。

下标1234567891c)

初始关键字36254827652543587632

I__________________________________________I

t1

［_______I

I_________________________________________I

I________________I

d=525254827323643587665

IlI