西安交通大学数据结构复习资料

精心整理

第一章绪论

1、数据结构的主要研究内容

①数据的逻辑结构一数据关系之间的逻辑关系

②数据的存储结构一数据的逻辑结构在计算机中的表示

2、数据逻辑结构的种类：集合、线性表、树和图的性质和特点。

。集合结构中的元素是各自独立的，元素之间没有联系

线性结构中的元素是一个接一个串联起来的，它有一个头元素和一个尾元素，

其余为中间元素；每个中间元素既有前驱元素，又有后继元素

在树结构中，树根结点只有后继结点，而没有前驱结点；除树根结点外，每个

结点都有唯---个前驱结点，又称为是父结点或双亲结点

在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结

点。

。树结构是图结构的特例，线性结构是树结构的特例。为了区别于线性结构，时

常把树结构和图结构称为非线性结构。

3、数据结构的二元组定义，能根据给出的二元组来判断数据的逻辑结构类型。

。集合结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G}

R={}

线性结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G}

R={<A,B>,<B,C>,<C,D>,<D,E>,<E,F>,<F,G>}

精心整理

。树结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G}

R={<A,B>,<A,C>,<A,D>,<C,E>,<C,F>,<D,G>}

图结构中的元素集合K和二元关系R分别为：

K={A,B,C,D,E,F,G}

R={〈A,B>,<A,C>,<A,G>,<D,G>,<D,F>,<C,E>,<C,F>,<G,F>}

4、了解数据的几种存储结构（物理结构）及它们各自的性质和特点。

（1）顺序的方法：将逻辑上相邻的元素存储到物理上相邻的存储位置.常用于线性

的数据结构.

（2）链式结构：给结点附加一个指针字段，指出其后继节点的位置，即存放结点的

存储单元分为两部分：

数据项指针项

（3）散列（hashing）结构：散列的方法是用结点的关键字值直接计算出结点的存

储地址。这个取值函数也称为散列函数。

5、数据的逻辑结构、存储结构和总的数据结构之间的关系

逻辑结构相同，但存储结构不同，则认为是不同的数据结构。如顺序表和链

表具有相同的逻辑结构，但存储结构分别为顺序结构和链表结构

6、算法的设计要求有那些，会结合实际的语言设计来说明这些要求

1）正确性：对于合法的输入产生符合要求的输出；

2）可读性：算法应该易读、便于交流，这也是保证算法正确性的前提；添加注释

也是一种增加可读性的办法；

3）健壮性：当输入非法时，算法还能做出适当的反应而不会崩溃，如输出错误信

息；算法中应该考虑适当的错误处理；

4)效率高且内存消耗小：效率高指运行时间短。存储指算法执行过程中所需的最大

存储空间。

7、了解时间复杂度的概念、时间复杂度的度量、时间复杂度的类型，能对实际的程

序分析它的时间复杂度。

算法的时间复杂度是一个算法运行时间的相对量度。

把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性,

用它来衡量一个算法的运行时间性能或称计算性能

平均复杂度(TheAverageCase)：所有可能输入.数据集的期望值.

最坏情况复杂度(TheWorstCase)：估算最坏情况下时间复杂度的一个上

界.这也是通常所指的复杂度.

最好复杂度(TheBestCase):在最理想输入情况下的时间复杂度。

第二章线性表

1、了解并掌握线性表的定义及性质

线性表是线性结构的一种表现形式，即是具有相同属性数据元素的一个有限序列，

序列中的元素是一个接一个在逻辑上是有序的，序列中元素的个数就是该线性表的

长度.

存在唯一的一个被称作“第一个”的数据元素

存在唯一的一个被称作“最后一个”的数据元素

除起点元素之外，集合中的每个数据元素均只有一个前驱

除终点元素之外，集合中每个数据元素均只有一个后继

起点元素只有后继没有前驱，终点元素只有前驱没有后继

。对于线性表中的数据元素和4来说，&一/是&的直接前驱，a是a-的直接

后继。

精心整理

♦：♦所有数据元素a在同一个线性表中必须是相同的数据类型。

2、熟悉顺序线性表（顺序存储的线性表）的存储方式及其表单元（简单数据类型和

记录数据类型）的定位和计算。

线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数

据元素。线性表的顺序存储结构具有以下两个基本特点：

（1）线性表中所有元素所占的存储空间是连续的；

（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的，即前驱元素一定

存储在后继元素的前面。

3、熟悉顺序线性表的插入、删除和查找的算法思想和程序

4、了解线性表链接存储的结构和特点

假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存

储结点，简称结点。

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值,

称为数据域（或称为信息域）；另一部分用于存放指针，称为指针域。其中指

针用于指向该结点的前一个或后一个结点，从而可以表示数据元素之间的逻辑

关系。

长度可以任意扩充，存储效率较高；

物理存储可以是不连续的；

数据元素的逻辑次序可以与其存储的物理次序不一致。

插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可

5、了解单链表、双向链表和循环链表的结构和特点

通过每个结点的指针域将n个结点按其逻辑顺序链接在一起的结点序列我们就称为

链表。如果这一链表中每个结点只有一个指针域，则称该链表为线性链表或单链表,

否则则称为双向链表。

双向链表是指线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其

直接前驱；另一个称为右指针，用以指向其直接后继。

循环链表。循环链表和单链表的差别仅在于链表中最后一个结点的指针域不为

“NULL”,而是指向头一个结点，成为一个由链指针链结的环。循环链表的特点：

只要知道表中任何一个结点的地址，就能查询到表中的任何一个结点。

6、了解单链表的结点的类型定义

在程序中，L为单链表的头指针，它指向表中第一个结点。若L为“空"（L=NULL）,

则所表示的线性表为“空”表，其长度为“零”。除了线性表第一个数据元素作为

该链表的头结点外，在某些线性链表存储结构中，还可在单链表第一个结点之前附

加一个同结构结点，称为附加头结点。头结点数据域可以不存储任何信息，也可以

存储如线性表的长度等类的附加信息；头结点指针域存储指向第一个结点的指针（即

第一个元素的存储位置）。那么，指向头结点的指针就是头指针。当头结点的指针域

为“空”时，单链表为空链表

8、熟悉单链表中结点的定位、插入、删除、查询的算法思想和操作程序

9、了解线性表的顺序与链式存储各自的优点、不足与它们适用场合。

若线性表的操作主要是查找和读取时，采用顺序存储结构为宜；若线性表的操作主

要是插入和删除时，采用链式存储结构为宜。

10、了解线性表的顺序与链式存储在不同操作场合下的时间复杂度指标

顺序表是随机存储结构，表中任一数据元素都可以通过计算直接得到地址进行存取,

时间复杂度为0（1）。在顺序表中进行插入和删除数据元素时，平均要移动近一半的

精心整理

元素，尤其是当每个数据元素包含的信息量较大时，移动元素所花费的时间就相当

可观。

动态链表是顺序存储结构，表中的任一结点都需要从头指针起顺链扫描才能取得，

时间复杂度为。（力（〃为表长）。但在动态链表中进行插入和删除结点时，不需要移

动结点，只需要修改指针。

第四章栈和队列

1、了解栈的定义及性质

栈（stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进

行插入和删除运算。

2、能给出在特定要求下的进出栈序列以及判断某些出栈序列出现的可能性

3、了解栈的顺序存储结构实现，栈顶指针的设置

4、了解栈的链接存储结构的实现、栈顶指针的更改

5、熟悉栈在顺序和链接存储结构下的进栈、出栈和读取栈顶元素的操作程序

6、了解递归算法的特点及递归算法的中止条件，会结合具体程序来分析递归程序的

合理性

7、了解队列的定义和它的顺序存储结构

队列（queue）简称队，它也是一种运算受限的线性表，其限制是仅允许在表

的一端进行插入，而在表的另一端进行删除。

我们把进行插入的一端称作队尾（rear）,进行删除的一端称作队首（front）。

向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从

队列中删除元素称为离队或出队，元素离队后，其后继元素就成为队首元素。

由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进

入的次序离队，所以又把队列称为先进先出表(firstinfirstout,简称

FIFO)o

8、了解队列特别是循环队列情况下，队列头指针和尾指针的设置

9、了解队列出现“假溢出”现象的原因及解决办法：循环队列的实现(循环头指针

和尾指针的计算、循环(和普通)队列长度的计算以及循环队列为空和满的判断方

法)

第五章树和二叉树

1、了解树的定义和树的基本术语：树和结点的度、分支结点和叶子结点、父母结点

和孩子结点、结点的层数和树的深度、有序树和无序树等

在树形表示法中，结点之间的关系是通过连线表示的，虽然每条连线上都不带有箭

头(即方向)，但它并不是无向的，而是有向的，其方向隐含为从上向下或从左向右,

即连线的上方或左边结点是下方或右边结点的前驱，下方或右边结点是上方或左边

结点的后继。

。结点的度：树中每个结点具有的非空子树数或者说后继结点数被定义为该结点

的度(degree)。

。树的度：一棵树上所有结点的度的最大值就是这棵树的度。

叶子结点：度为零的结点称叶子结点或终端结点。

分支结点：度非零的结点称为分支结点或称为非终端结点。

♦:♦孩子结点(child)：某结点子树的根或者说某个结点的后继被称为该结点的孩

子结点。

双亲结点(parent)：一个结点是它的那些子树的根的双亲结点。

。兄弟结点(sibling)：同一个双亲的孩子之间互为兄弟。

精心整理

♦：♦堂兄弟结点(cousins)：其双亲在同一层但不同的结点互为堂兄弟。

子孙结点：每个结点的所有子树中的结点被称为该结点的子孙结点

祖先结点：从整个(子)树的根结点到达该结点的路径上经过的所有分支结点

。结点层次:从根结点开始，根结点为第1层，根结点的孩子为第2层，依此

类推

1A.............第1层

2B3C4D….第2层

5E6FG7……...第3层

树的深度:树中结点的最大层次。

有序树：结点的子树从左到右有序安排。也即树T中各子树「，丁2,…，■的相对次

序是有意义的。在有序树中，改变了子树的相对次序就变成了另一棵树。

无序树：结点的子树顺序任意。

2、熟悉树的性质，并能根据这些性质进行相关推理和计算

。性质1:树中的结点数等于所有结点的度数加1。基

证明：根据定义：除根结点外，每个结点有一个分支指向。树的总分支数为：

。性质2：度为4的树中第］.层上至多有个结点(7^1)o

用数学归纳法证明：

对于7=1,""=火=1命题成立。

假设第A1层(7>1)命题成立，该层上有『个结点。

对于第2.层，最多结点数称•公产命题得证。

。性质3深度为h的k叉树金窘有个结点。

证明：利用性质2来证明，k叉树的最大结点数为每一层最大结点数之和，则

有:

当一棵4叉树上的结点数等于时，则称该树为满女叉树。

。性质4：具有〃个结点的A叉树的最小深度为：

分析：在结点数相同的k叉树中，每一层结点都满，或除最后一层外其余层都满的

树，其深度为最小。

h

证明：设k叉树的最小深度为h,贝)：尸-1<nvk-l

k-1~k-\

前hT层满的k叉树结点数〈nWh层都满的k叉树结点数，因此有：

上式可变换为：<n(k-l)+lW片

以〃为底取对数可得：h-l<logk(n(k-l)+1)Wh

即：logk(n(k-l)+1)Wh<logk(n(k-l)+1)+1

因〃只能为整数，所以：h=?logk(n(k-l)+l)?

因此得到具有n个结点的一般k叉树的最小深度为：21阳(n(kT)+l)?

注：?x?表示对x进行向上取整

3、熟悉二叉树的定义及基本性质，并能根据这些性质进行相关推理和计算。

二叉树(binarytree)是指树的度为2的有序树。它是一种树结构，在计算机领

域有着广泛地应用。

二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两

棵互不相交的分别称做根的左子树和右子树所组成的非空树，左子树和右子树

又同样都是一棵二叉树。

♦:♦性质1：在二叉树第i层上最多有个结点(i21)。

性质2：深度为k的二叉树，最多有2、1个结点(k21)。

性质3：若二叉树的叶子结点数为n。，度为2的结点有出个，则有：no=n2+l

精心整理

证明：(1)??由于在二叉树中，任一结点的度数小于或等于2,所以其结点总

数n为：

n=n0+Hi+n2

(n°:终端结点；m:单分支结点数，%:双分支结点数)

(2)设B为二叉树中总的分支数目，由于二叉树中除了根结点之外，其余结

点都有一个分支进入,而这些分支只能是由度数为1或2的结点所发出，所以：

B=a+2n2

于是得：n=ri,+2n2+1

(3)由⑴和⑵得：

n0+ni+n2=n,+2n2+1

所以n0=n2+1#证毕

性质4：对完全二叉树中编号为i的结点(lWiWn,n21,n为结点数)有：

(1)若iW?n/2?,即2iWn,则编号为i的结点为分支结点，否则为叶子结点。

表达式?x?表示对x进行向下取整。

(2)若n为奇数，则树中每个分支结点都既有左孩子，又有右孩子；若n为偶

数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点

左、右孩子都有。

(3)若编号为i的结点有左孩子，则左孩子结点的编号为2i；若编号为i的结

点有右孩子，则右孩子结点的编号为2i+l,即遵循对一般二叉树的编号规则。

(4)除树根结点外，若一个结点的编号为i,则它的双亲结点的编号为?n/2?,

也就是说，当i为偶数时，其双亲结点的编号为i/2,它是双亲结点的左孩子，当i

为奇数时，其双亲结点的编号为(iT)/2,它是双亲结点的右孩子。此点也适合于一

般二叉树。

性质5：具有n个(n>0)结点的完全二叉树的深度为?log2(n+l)?或?logzn?+l。

此性质可以从树的相应性质中直接导出，也可以进行如下证明。

证明：设所求完全二叉树的深度为h,由完全二叉树的定义可知，它的前

hT层都是满的，最后一层可以满，也可以不满，由此得到的如下不等式

2hl-l<n^2h-l.

可变换为：2i〈n+lW2h

取对数后得：h-l<log2(n+l)Wh

即：log2(n+l)^h<log2(n+l)+1

因h只能取整数，所以：h=?log2(n+l)?

完全二叉树的深度h和结点数n的关系，还可表示为：

2,ll^n<2h

取对数后得：hTWlog2n<h

即：log2n<h^log2n+l

因h只能取整数，所以：h=?log2n?+l

4、熟悉满二叉树、完全二叉树以及平衡二叉树等几种特殊的二叉树的性质、特点，

并能根据这些性质进行相关的推理和计算

满二叉树:叉树每层的结点数达到最大值。

第i层有个结点；全部分支结点度为2。

完全二叉树：除最后一层外，其余层均满；最后层或为满，或缺少右边若干连续结

点。

特点：

除最后一层，第i层有个结点;

叶子只可能出现在最后两层；

精心整理

♦：♦结点右子树深度为i时，左子树深度为i或i+L

理想平衡二叉树：在一棵二叉树中，若除最后一层外，其余层都是满的，而最后一

层上的结点可以任意分布，则称此树为理想平衡二叉树,简称理想平衡树或理想二叉

树。

显然，理想平衡树包含满二叉树和完全二叉树。完全二叉树中深度

h和结点数n之间的关系，在理想平衡树中同样成立，

5、了解二叉树的链接存储结构

根据二叉树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有

三个域：数据域和左、右指针域。其结点结构为：

Leftdataright

其中data表示值域，用于存储对应的数据元素，left和right分别表示左指针域和

右指针域，用以分别存储左孩子和右孩子结点的存贮位置（即指针）

链接存储的另一种方法是：在上面的结点结构中再增加一个parent指针域，

用来指向其双亲结点。这种存储结构既便于查找孩子结点，也便于查找双亲结

点，当然也带来存储空间的相应增加。

Ichilddataparentrchild

6、瓦苏二支树的4遍遍历方俣？能转存后二再扇^方展码出融树的遍历序列

（1）先序遍历：

若二叉树为空，则空操作；否则

①访问根结点；

②先序遍历左子树；

（先访问左子树根节点；再遍历左子树根节点的左子树，再遍历左子树根

节点的右子树；……直至遍历完所有左子树的节点｝

③先序遍历右子树。

（先访问右子树根节点；再遍历右子树根节点的左子树，再遍历右子树根

节点的右子树；……直至遍历完所有右子树的节点｝

（2）中序遍历：

若二叉树为空，则空操作；否则

①中序遍历左子树；

（遍历的过程与先根级的递归遍历类似）

②访问根结点；

③中序遍历右子树

（遍历过程与先根级的递归遍历相同）

（3）后序遍历：

若二叉树为空，则空操作；否则

①后序遍历左子树；

②后序遍历右子树。

③访问根结点；

（4）按层遍历二叉树：

①访问根结点；

②遍历左子树根结点；

③遍历右子树根结点。

6、熟悉树的遍历序列与树结构之间的关系，并能由特定的遍历序列来恢复树结构和

写出另外的遍历序列

7、熟悉树与二叉树的共性和差异之处

8、熟悉树的几种遍历算法

精心整理

9、能根据树的定义(包括结点类型的定义)编程实现树的一些基本运算

第六章二叉树的应用

1、了解二叉搜索树的定义，性质并能根据定义由给定序列构造二叉搜索树

二叉搜索树(BinanySearchingTree)又称做二叉排序树(BinarySorting

Tree),它或者是一棵空树，或者是一棵具有如下特性的非空二叉树。

(1)若它的左子树非空，则左子树上所有结点的关键字均小于树根结点的关键字;

(2)若它的右子树非空，则右子树上所有结点的关键字均大于树根结点的关键字;

(3)左、右子树本身又各是一棵二叉搜索树。

在一个二叉搜索树中，当每个结点的元素类型为简单类型时，则结点的关键

字就为该结点的值；当结点的元素类型为记录类型时，则结点的关键字为该结点的

某一个域的值。

。由二叉搜索树的定义可知，在一棵非空的二叉搜索树中，其结点的关键字是按

照左子树、根和右子树有序的，所以对它进行中序遍历得到的结点序列必然是

一个有序序列。

2、了解二叉搜索树应用于查找时的特性及指标

在二叉搜索树上进行查找的过程中，给定值item同树中结点比较的次数最少

为一次(即树根结点就是待查的结点)，最多为树的深度，所以平均查找次数

要小于等于树的深度。

若二叉搜索树是一棵理想平衡树或接近理想平衡树，则进行查找的时间复杂度

为0(log2n),

若为一棵单支树(这是最极端和最差的情况)，则其时间复杂度为0(n),

一般情况而言，其时间复杂度可大致可看做为O(logzn)。

由此可知，在二叉搜索树上查找比在集合或线性表上进行顺序查找的

时间复杂度0(n)要小得多，这正是构造二叉搜索树的优势所在。二叉搜索树查找的

递归算法的空间复杂度平均情况为O(logzn),最差情况为。(n),非递归算法的空间

复杂度为0(1)。

3、了解堆的定义和性质

堆(Heap)分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完

全二叉树。

(1)若树根结点存在左孩子，则树根结点的值小于等于左孩子结点的值；

(2)若树根结点存在右孩子，则树根结点的值小于等于右孩子结点的值；

(3)以左、右孩子为根的子树又同样各是一个堆。

大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。

若一棵完全二叉树是堆，则该树中以每个结点为根的子树也都是一个堆。

堆顶结点具有最小值(一一对应于小根堆)或最大值(一一对应于大根堆)。

4、能采用给定的数据序列来生成一个堆(大根堆或小根堆)

5、了解树的带权路径，以及哈夫曼树(最优二叉树)的概念和性质

(1)路径和路径长度

若在一棵树中存在着一个结点序列k1,k2,…,kj,使得ki是ki+1的双亲(lWi〈j),则称

此结点序列是从k1到kj的路径。也就是说，在二叉树中，一个结点到另一个结点之

间的分支构成这两个结点之间的路径。因树中每个结点只有一个双亲结点，所以它

也是这两个结点之间的惟一路径。从X到kj所经过的分支数称为这两点之间的路径

长度，它等于路径上的结点数减1。

(2)结点的权和带权路径长度

精心整理

在许多应用中，常常将树中的结点赋予一个有着某种意义的实数，我们

称此实数为该结点的权。结点的带权路径长度规定为从树根结点到该结点之间的路

径长度与该结点上权的乘积。

(3)树的带权路径长度

树的带权路径长度定义为树中所有叶子结点的带权路径长度之和，通常记为：

其中n表示叶子结点的数目，%和心分别表示叶子结点k.的权值和树根结点到ki之

间的路径长度。

。哈夫曼(Huffman)树又称作最优二叉树。它是n个带权叶子结点构成的所有二

叉树中，带权路径长度WPL最小的二叉树。

6、能根据给定的权值集合和结点集合构成具有n个结点的哈夫曼树

(1)根据与〃个权值｛仍,W2,…,％｝对应的〃个结点构成具有77棵二叉树的森林

£=｛「，心,…,北｝,其中每棵二叉树T,(lW?Wn)都只有一个权值为叼的根结点，其左、

右子树均为空；

(2)在森林尸中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且

置新树的根结点的权值为其左、右子树上根结点的权值之和；

(3)从月中删除构成新树的那两棵树，同时把新树加入月中；

(4)重复(2)和(3)步，直到尸中只含有一棵树为止，此树便是哈夫曼树

第七章图

1、了解图的定义以及基本性质

图中的每个顶点，都允许有任意个前驱和后继，即对每个顶点的前驱和后继个

数均不加以限制

♦：♦对于一个图G,若E是有序对的集合，则每个有序对对应图形中的一条有向边,

若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看

做为边的集合。这样图的二元组定义可叙述为：图由顶点集(vertexset)和

边集(edgeset)所组成。

针对图G,顶点集和边集可分别记为V(G)和E(G)。若顶点集为空，则边集必然为空,

若顶点集非空，则边集可空可不空，当边集为空时，图G中的顶点均为孤立顶点。

2、了解图的邻接矩阵、邻接表、逆邻接表和十字邻接表的定义及性质

邻接矩阵(adjacencymatrix)是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)

是具有n个顶点的图，顶点序号依次为0,1,2,…,nT,则G的邻接矩阵是具有如下

定义的n阶方阵。

?1,对于无向图，(匕，匕)或(%匕)?E(G)；

力"力=?对于有向图，〈匕，r??E(G)

?0,对应边不存在于E(G)中

从邻接矩阵中可查两个结点的之间是否存在通路，若两个结点的坐标的交叉其

值不为零并不是一个很大的值的话，则有通路，否则没有通路。若其值大于1

则为该通路的权值。

无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。

在有向图中，统计第7.行中1的个数可得顶点i的出度，统计第j列中1

的个数可得顶点j的入度。

在无向图中，统计第i行(列)中1的个数可得顶点i的度。

图的邻接矩阵的存储需要占用〃X〃个整数存储位置，所以其空间复杂度为

0(ri)o

精心整理