线性结构常识

1.数据(data)

数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、

字母、汉字、图形、图像、声音都称为数据。

2.数据元素(dataelement)

数据元素是组成数据的基本单位。

数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性

的项(字段)，故不是组成数据的最小单位。

4.数据结构(datastructure)

是指相互之间存在一种或多种特定关系的数据元素所组成的集合。详细来说，数据结

构包含三个方面的内容，即数据的规律结构，数据的存贮结构和对数据所施加的运算。数

据之间的相互关系称为规律结构

数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。

数据结构从规律结构角度通常分为四类基本结构：

一、集合结构中的数据元素除了同属于一种类型

外，别无其它关系。

二、线性结构结构中的数据元素之间存在一对一

的关系。

三、树型结构结构中的数据元素之间存在一对

多的关系。

四、图状结构或网状结构结构中的数据元素之间

存在多对多的关系。

数据结构在计算机中有两种不同的表示方法：

挨次表示和非挨次表示

由此得出两种不同的存储结构：

挨次存储结构和链式存储结构

挨次存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的规律关系。

链式存储结构：在每一个数据元素中增加一个存放地址的指针（Pointer）,用此指

针来表示数据元素之间的规律关系。

算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一

个或多个操作。

算法具有以下五个特性：

(1)有穷性

(2)确定性

(3)可行性

(4)输入

(5)输出

1.4.2算法设计的要求

评价一个好的算法有以下几个标准：

(1)正确性(Correctness)算法应满意详细问题的需求。

⑵可读性(Readability)算法应当好读。以有利于阅读者对程序的理解。

(3)健状性(Robustness)算法应具有容错处理。当输入非法数据时，算法应对其作出

反应，而不是产年莫名其妙的输出结果。

(4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中

所需要的最大存储空间。一般，这两者与问题的规模有关。

线性结构：

线性结构是具有以下特点的数据结构：

(1)存在唯一的一个被称作"第一个"的数据元素；

(2)存在唯一的一个被称作“最终一个"的数据元素；

(3)除第一个外，集合中的每个数据元素均有且只有一个直接前趋；

(4)除最终一个外，集合中的每个数据元素均有且只有一个直接后继。

线性表、栈、队列、串都是线性结构。

一、概念：

1.线性表：线性表是n个数据元素的有限序列。

2.线性表的长度：线性表中数据元素的个数n(nNO)称

为线性表的长度。

3.空表：长度为0的线性表称为空表。

4.位序：在非空数据表中数据元素ai是第i个数据元素,

称i为数据元素ai在线性表中的位序。

线性表中每个数据元素的详细含义，在不同状况下各不相同，但是同一线性表中的元

素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在序偶关系。

二,挨次表的特点：

以元素在计算机内的“物理位置"来表示线性表中数据元素之间的规律关系，也就是

存储位置相邻的数据元素就是规律关系相邻的数据元素。

由以上式子可看到，挨次表中每个数据元素的存储位置和挨次表的起始位置相差一个

和数据元素在线性表中的位序成正比的常数,所以只要确定了起始位置，表中任一个数据

元素可以随机存取，所以挨次结构是一种随机存取的存储结构

2.3线性表的链式表示和实现

挨次存储结构：

优点：可以随机存取表中任意元素。

缺点：在插入、删除元素时，需要大量移动元素。

链式存储结构

优点：在插入、删除元素时，不需要移动元素。

缺点：不能随机存取。

一、线性链表：

1.特点:

线性表的链式存储结构的特点是用一组任意的存储单元（可连续或不连续）存储线性

表的数据元素。

5）线性链表（单链表）：

由于上述由n个结点链接成的一个链表中的每个结点中只包含一个指针域，故又称作

线性链表或单链表。

6）头指针：

线性链表中，头指针指示链表的第一个结点（即第一个数据元素的存储映像）的存储

位置。

7）头结点：

有时我们在单链表的第一个结点之前附设一个结点，称之为头结点。着重争论带头结

点的链表。

8）非挨次存储结构或链式映像：

用链表表示数据结构时，数据间的规律关系是由结点中的指针指示的，这种存储结构

称为非挨次存储结构或链式映像。

即：指针为数据元素之间的规律关系的映像，则规律上相邻的两个数据元素其存储位

置不要求紧邻。

链表和挨次存储结构不同，它是一种动态结构。整个可用存储空间可为多个链表共享,

每个链表占用的空间不虚预先安排划定，而是可由系统需求即时生成。所以，建立链表的

过程就是一个动态生成的过程。也就是从"空表"的初始状态起，依次建立各元素结点，

并逐个插入链表

7.对链表的评价：

优点：

1）链表在空间的采用上合理；

2）插入、删除时不需要移动元素；

因此，许多场合下，链表是线性表的首选存储结构。

缺点：

在实现某些基本操作（比如求线性表长度）时，不如挨次表。

此外：

在链表中，数据元素在线性表中的"位序"概念已淡化，被元素在链表中的“位置"

代替了。

四.挨次表和链表的比较：

在本章介绍了线性表的规律结构及它的两种存储结构：挨次表和链表。通过对它们的

争论可知它们各有优缺点。

1.挨次存储的优点：

(1)方法简洁，各种高级语言中都有数组，简洁实现。

(2)不用为表示结点间的规律关系而增加额外的存储开销。

(3)挨次表具有按元素序号随机访问的特点。

2.挨次存储的缺点：

(1)在挨次表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的

挨次表效率低。

(2)需要预先安排足够大的存储空间，估量过大，可能会导致挨次表后部大量闲置；

预先安排过小，又会造成溢出。

3.链表的优缺点:

链表的优缺点恰好与挨次表相反。

4.在实际中怎样选取存储结构

通常有以下几点考虑：

1)基于存储的考虑

挨次表的存储空间是静态安排的，在程序执行之前必需明确规定它的存储规模，也就

是说事先对"MAXSIZE"要有合适的设定，过大造成铺张，过小造成溢出。

可见对线性表的长度或存储规模难以估量时，不宜采纳挨次表；

链表不用事先估量存储规模，但链表的存储密度较低，存储密度是指一个结点中数据

元素所占的存储单元和整个结点所占的存储单元之比。明显链式存储结构的存储密度是小

于1的。

)基于运算的考虑

在挨次表中按序号访问ai的时间性能是0(1),而链表中按序号访问的时间性能0(n),

所以假如常常做的运算是按序号访问数据元素，明显挨次表优于链表；

而在挨次表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且

表较长时，这一点是不应忽视的；

在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度

考虑明显后者优于前者。

3）基于环境的考虑

挨次表简洁实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来

讲前者简洁些，也是用户考虑的一个因素。

总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素打算。通常"较

稳定”的线性表选择挨次存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存

储。

简介：

栈和队列是两种重要的线性结构。

从数据结构角度看：

栈和队列也是线性表，其特别性在于栈和队列的基本操作是线性表操作的子集，它们

是操作受限的线性表，因此，可称为限定性的数据结构。

从数据类型角度看：

栈和队列是和线性表大不相同的两类重要的抽象数据类型。

-.术语与概念：

（1）栈（Stack）:

栈是限定只在表尾进行插入或删除操作的线性表。

(2)栈顶(top):栈的表尾称为栈顶。

(3)栈底(bottom):栈的表头称为栈底。

(4)栈的长度：栈中元素的个数称为栈的长度。

(5)空栈：不含元素的栈称为空栈，即长度为0的栈。

(6)进栈(Push):

在栈顶插入元素称为进栈(压栈、入栈X

(7)出栈(Pop):

删除栈顶元素称为出栈(退栈、弹栈\

二.栈的特点：

栈是“后进先出"的线性表。

"后进先出"LastInFirstOut（简称LIFO）或

"先进后出"FirstInLastOut（简称FILO\

栈的基本操作除了在栈顶插入、删除外，还有栈的初始化、判空、取栈顶元素等。

四.栈的表示和实现（挨次栈/链式栈）

1.栈的挨次表示：（挨次栈）

采用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top

指示栈顶元素在挨次栈中的位置。

说明：

•挨次栈也是采纳动态安排存储空间的方法。

•栈的初始化操作就是按设定的初始安排量进行第一次存储安排，base始终指向栈底

位置。

•假如base=NULL,表示栈结构不存在，即栈构造之前和销毁以后，base的值都是

NULL。

•top初值指向栈底，即top=base可作为栈空的标志。

•插入新的栈顶元素时，top增1,

・删除栈顶元素时，top减1,

•因此，非空栈的栈顶指针始终指向栈顶元素的下一个位置。

4.栈的链式表示：

用链式存储结构实现的栈称为链栈。

通常链栈用单链表表示，因此其结点结构与单链表的结构相同，在此用LinkStack表

示，即有：

typedefstructnode{

datatypedata;

structnode*next;

}StackNode,*LinkStack;

说明top为栈顶指针:LinkStacktop;

由于栈中的主要运算是在栈顶插入、删除，明显在链表的头部做栈顶是最便利的，而

且没有必要象单链表那样为了运算便利附加一个头结点。

二.括号匹配的检验

括号检验的方法可用"期盼的急迫程度"这个概念来描述。

三.行编辑程序

退格符"花’，以表示前一个字符无效；

退行符,以表示当前行中的字符均无效

可以设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后先作如下判别：

假如它不是退格符也不是退行符，则将该字符压入栈顶；假如是一个退格符,则从栈顶删

去一个字符；假如它是一个退行符，则将字符栈清为空栈。

-.概念与术语：

1.队列：

队列是只允许在表的一段进行插入，在另一端删除元素的线性表。

2.队头：

队列中允许删除元素的一端称为队头。

3.队尾：

队列中允许插入元素的一端称为队尾。

三.队列的链式表示和实现

1.链队列：

用链式表示的队列简称为链队列。

2.确定：

一个链队列需要两个分别指示队头和队尾的指针唯一确定。

为操作便利，我们给链队列添加一个头结点，并令头指针指向头结点。（如图3.10）

3.判空：

头指针和尾指针都指向头结点，为空链队列。

计算机上的非数值处理的对象基本上是字符串数据。

早期：常量

进展：变量

实际困难及对策：

硬件反映数值计算，要有效地实现字符串的处理，

就必需依据详细状况使用合适的存储结构。

本章争论：一些基本的串处理操作

几种不同的存储结构。

-.概念及术语：

串：

零个或多个字符组成的有限序列。

一般记为:s='ala2a3...an,(n>=0),

串名串的值；

ai可以是字母、数字、或其他字符；

注：单引号本身不属于串，其作用是为了区分字符串与变量名或数值常量。(举例说明)

串的长度：

串中字符的数目称为串的长度。

空串：

长度为零的串称为空串。

子串：

串中任意个连续的字符组成的子序列称为该串的子串。

主串：

包含子串的串相应的称为主串。

字符在串中的位置：

称字符在序列中的序号为该字符在串中的位置。

子串在主串中的位置：

以子串的第一个字符在主串中的位置来表示。

（举例说明）

两个串相等：

当且仅当两个串的值相等时，称为这两个串是相等的。

空格串：

由一个或多个空格组成的串称为空格串。

注：

"空格串"不等同于"空串"。用符号"①"来表示"空串"。

*串的规律结构和线性表极为相像

*串的数据对象约束为字符集

*串的基本操作和线性表有很大差别：

在线性表的基本操作中，大多以"单个元素”作为操作对象；

在串的基本操作中，通常以"串的整体”作为操作对象。

4.2串的表示和实现

--定长挨次存储表示：

1,定长挨次存储表示：

即：用一组地址连续的存储单元存储串值得字符序列。

在串的定长挨次存储结构中，依据预定义的大小，为每个定义的串变量安排一个固定

长度的存储区。

串的实际长度可在这予定义长度的范围内随便，超过予定义长度的串值则被舍去，称

之为"截断"。

4.时间简单度：

挨次存储结构中，实现串操作的原操作是"字符序列的复制"，操作的时间简单度基

于复制的字符序列的长度。

5.弊端：

由于采纳定长数组，假如字符串长度超过上界，就用截断法处理，使结果不正确。

6.解决方法：

不限定串长的最大值，即动态安排串值的存储空间。

可用堆安排存储表示。

二.堆安排存储表示

1.特点：

这种存储表示的持点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的

存储空间是在程序执行过程中动态安排而得。串操作仍是基于"字符序列的复制”进行的。

二维数组：

我们可以把二维数组看成是这样一个定长线性表：

它的每个数据元素也是一个定长线性表。例如。图5.1

数组一旦被定义，它的维数和维界就不再转变。因此，除了结构的初始化和销毁之外,

数组只有存取元素和修改元素值的操作。

-.采纳挨次存储结构：

一般不作插入或删除操作，因此,采纳挨次存储结构

二.存储挨次：

存储单元是一维的结构，数组是个多维的结构，用一组连续存储单元存放数组的数据

元素就有次序商定问题。

对二维数组可有两种存储方式

三.三个重要结论：

Q)列表的元素可以是子表，而子表的元素还可以是子表，…。

⑵列表可为其它列表所共享。

(3)列表可以是一个递归的表，即列表也可以是其本身的一个子表。

依据前述对表头、表尾的定义可知：

任何一个非空列表其表头可能是原子，也可能是列表，

而其表尾必定为列表。

一.简介：

树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树

是以分支关系定义的层次结构。

—.本章重点：

本章重点争论二叉树的存储结构及其各种操作，并争论树和森林与二叉树的转换关系，

最终介绍几个应用例子。

1.树/子树:

树(Tree)是n(n>0)个结点的有限集。

在任意一棵非空树中：

(1)有且仅有一个特定的称为根(Root)的结点；

⑵当n>I时，其余结点可分为m(m>0)个互不相交的有限集Tl,T2，…，Tm,其

中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

1.结点:

树的结点包含一个数据元素及若干指向其子树的分支。

2.结点的度：

结点拥有的子树数称为结点的度(Degree)。

3.叶子(或终端结点)

度为0的结点称为叶子(Leaf)或终端结点。

4.分支结点(或非终端结点)

度不为0的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结

5.树的度：

树的度是树内各结点的度的最大值。

6.孩子——双亲

结点的子树的根称为该结点的孩子(child),相应地，该结点称为孩子的双亲(Parent)。

7.兄弟

同一个双亲的孩子之间互称兄弟(sibling)

8.祖先

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

9.子孙

以某结点为根的子树中的任一结点都称为该结点的子孙。

10.结点的层次

结点的层次(level)从根开头定义起，根为第一层，根的孩子为其次层。若某结点在第j

层，则其子树的根就在第j+1层。

11.堂兄弟

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

12.树的深度

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

13.有序树——无序树

假如将树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树,

否则称为无序树。

在有序树中最左边的子树的根称为第一个孩子，最右边的称为最终一个孩子。

二叉树(BinaryTree)是另一种树型结构，它的特点是每个结点至多只有二棵子树(即二

叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分,其次序不能任意颠倒。

上述数据结构的递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左

子树和右子树的、互不相交的二叉树组成。由于这两棵子树亦是二叉树，则由二叉树的定

义，它们也可以是空树。由此，二叉树可以有五种基本形态，如图6.3所示。

图6.3二叉树的五种基本形态

(a)空二又树;(b)仅有根结点的二叉树;(c)右子树为空的二叉树;

(d)左、右子树均非空的二叉树Me)左子树为空的二叉树。

6.2.2二叉树的性质

性质1

在二叉树的第i层上至多有2i-l个结点(>1)。

性质2

深度为k的二叉树至多有2k-l个结点，(抡1)。

丽3

对任何一棵二叉树T,假如其终端结点数为nO，度为2的结点数为n2，则nO=n2+l0

满二叉树

定义：

一棵深度为k且有2k-l个结点的二叉树称为满二叉树。

特点：

每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号，商定编

号从根结点起，自上而下，自左至右。

完全二叉树

定义：

深度为k的，有n个结点的二又树，当且仅当其每一个结点都与深度为A的满二

叉树中编号从1至n的结点——对应时，称之为完全二又树。

特点：

(1)叶子结点只可能在层次最大的两层上消失；

(2)对任一结点，若其右分支下的子孙的最大层次为I,则其左分支下的子孙的最大层

次必为I或I+L

图6.4特殊形态的二叉树

(a)满二叉树；(b)完全二叉树，(0和(d)非完全二叉树。

完全二叉树的两个重要特性。

性质4

具有n个结点的完全二叉树的深度为

性质5

假如对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(14iwn),有

⑴假如i=1,则结点i是二叉树的根，无双亲；

假如i>l,则其双亲PARENT(i)是结点。

⑵假如2i>n,则结点i无左孩子(结点i为叶子结点);

否则其左孩子LCHILD(i)是结点2io

⑶假如2i+l>n,则结点i无右孩子；

否则其右孩子RCHILD(j)是结点2i+L

二叉树遍历方法：

先(根)序遍历，中(根)序遍历，后(根)序遍历。

算法描述：

1.先序遍历二叉树的操作定义为

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

⑴访问根结点：

(2)先序遍历左子树；

(3)先序遍历右子树。

2.中序遍历二叉树的操作定

3.后序遍历二叉树的操作定义

遍历二叉树的算法中的基本操作是访问结点，则不论按哪一种次序进行遍历，对含n

个结点的二叉树，其时间简单度均为O(n)o所需帮助空间为遍历过程中栈的最大容量，即

树的深度，最坏状况下为n,则空间简单度也为0(n)。

1.由先序序列和中序序列确定二叉树

先序序列：HDACBGFE

中序序列：ADCBHFEG

2.由后序序列和中序序列确定二叉树

后序序歹J：ABCDEFGH

中序序列：ADCBHFEG

3.无法依据先序序列和后序序列确定二叉树

6.6赫夫曼树及其应用

赫夫曼(Huffman)树，是一类带权路径长度最短的树，有着广泛的应用。

一.几个概念：

1.路政路径长度：

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支

数目称做路径长度。

2.树的路径长度：

树的路径长度是从树根到每一结点的路径长度之和。

3.结点的带权路径长度：

结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。

第7章图

♦在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直

接后继；

♦在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和

下一层中多个元素(即其孩子结点)相关，但只能和上一层中一个元素(即其双亲结点)相关；

♦在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相

关。

1.图的遍历：(TraversingGraph)

从图中某一顶点动身访遍图中其余顶点，且使每一个顶点仅被访问一次。这一过程就

叫做图的遍历。

2.图的遍历算法的地位：

图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

4.分类：

通常有两条遍历图的路径：深度优先搜寻和广度优先搜寻。它们对无向图和有向图都

适用。3.1深度优先搜寻

深度优先搜寻(Depth_firstSearch)遍历类似树的先根遍历，是树的先根遍历的推广

--深度优先搜寻过程描述：

假设初始状态是图中全部顶点未曾被访问。

深度优先搜寻可从图中某个顶点V动身，访问此顶点，然后依次从V的未被访问的邻

接点动身深度优先遍历图，直至图中全部和V有路径相通的顶点都被访问到。

若此时图中尚有顶点未被访问，则另选图中一个未曾放访问的顶点作起始点，重复上

述过程，直至图中全部顶点都被访问到为止。

7.3.2广度优先搜寻

广度优先搜寻(Breadth_FirtstSearch)遍历类似于树的按层次遍历的过程。

--广度优先搜寻过程描述：

假设从图中某顶点v动身，在访问了v之后依次访问v的各个未曾访问过的邻接点，

然后分别从这些邻接点动身依次访问它们的邻接点，并使"先被访问的顶点的邻接点"先

于"后被访问的顶点的邻接点"被访问，直至图中全部已被访问的顶点的邻接点都被访问

到。

若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上

述过程,直至图中全部顶点都被访问到为止。

9.1.2有序表的查找

-.折半查找：

1.折半查找过程：

先确定待查纪录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该纪录为止。

三.概念和术语：

冲突：

对不同的关键字可能得到同一哈希地址，即keylwkey2,而f(keyl)=f(key2),这种

现象称为冲突。

同义词：

具有相同哈希函数值的关键字对该哈希函数来说称作同义词。

通过选择合适哈希函数，冲突只能尽量削减，而不能完全避开。因此在构造哈希表时，

不仅要设定一个"好”的哈希函数，还需要设定一种处理冲突的方法。

哈希表/散列/散列地址：

依据设定的哈希函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续

的地址集(区间)上，并以关键字在地址集中的“象"作为纪录在表中的存储位置，这种表

称为哈希表，这一映象过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。

-."好”的哈希函数：

若对于关键字集合中的任一个关键字，经哈希函数映象到地址集合中任何一个地址的

概率是相等的，则称此类哈希函数为匀称的哈希函数。

就是使关键字经过哈希函数得到一个"随机的地址"，以便使一组关键字的哈希地址

匀称分布在整个地址区间中，从而削减冲突。

3.内部排序/外部排序：

由于待排序的纪录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为

两大类：

一类是内部排序，指的是待排序纪录存放在计算机随机存储器中进行的排序过程；

另一类是外部排序，指的是待排序纪录的数量很大，以致内存一次不能容纳全部纪录,

在排序过程中尚需对外存进行访问的排序过程。

—•描述：

直接插入排序是一种最简洁的排序方法，它的基本操作是将一个纪录插入到已排好序

的有序表中，从而得到一个新的、纪录数增1的有序表。

希尔排序，又称"缩小增量