数据结构教程李春葆第4版知识点习题答案

第1章 绪 论

知识点归纳

一、数据结构概述

1.

数据结构的定义

（1）

基本概念

数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某

种特定的符号表示形式。

（2）

相关术语

① 数据元素

数据元素又称元素、节点、顶点、记录等。数据元素是数据的基本单位。有时候，一个数据元素可

以由若干个数据项组成。

② 数据项

数据项又称字段或域，它是具有独立含义的最小数据单位。

③ 数据对象

数据对象是性质相同的数据元素的集合，它是数据的子集。

（3）

数据结构的内容

① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。

② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。

③ 施加在数据上的操作，即数据的运算。

（4）

逻辑结构

数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无

关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。

（5）

存储结构

数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结

构在计算机中的存储方式，它是依赖于计算机语言的。一般只在高级语言（例如C／C++语言）的层次

上讨论存储结构。

数据的运算最终需在对应的存储结构上用算法实现。

总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算

在计算机中如何表示和实现”的学科。

（6）

数据结构的表示

对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构

中，同一运算的实现过程可能不同。

描述数据结构通常采用二元组表示：

B=（D，R）

其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：

D={d

i

| 1≤i≤n，n≥0}

R={r

j

| 1≤j≤m，m≥0}

其中d

i

表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D

是一个空集。r

j

表示集合R中的第j个关系，m为R中关系的个数，特别地，若m=0，则R是一个空集，表

明集合D中的数据元素间不存在任何关系，彼此是独立的，这和数学中集合的概念是一致的。

R中的一个关系r是序偶的集合，对于r中的任一序偶（x，y∈D），把x称作序偶的第一节

点，把y称作序偶的第二节点，称序偶的第一节点为第二节点的前驱节点，称第二节点为第一节点的后

继节点。若某个节点没有前驱节点，则称该节点为开始节点；若某个节点没有后继节点，则称该节点为

终端节点。

对于对称序偶，即∈R，且∈R（x，y∈D），可用圆括号代替尖括号，即（x，y）

∈R。

数据结构还可以利用图形形象地表示出来，图形中的每个节点对应一个数据元素，两节点之间的连

线对应关系中的一个序偶。

2.

逻辑结构类型

（1）

集合

集合是指数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

（2）

线性结构

线性结构是指该结构中的节点之间存在一对一的关系。其特点是开始节点和终端节点都是惟一的，

除了开始节点和终端节点以外，其余节点都有且仅有一个前驱，有且仅有一个后继。线性表就是一种典

型的线性结构。

（3）

树形结构

树形结构是指该结构中的节点之间存在一对多的关系。其特点是每个节点最多只有一个前驱，但可

以有多个后继，且终端节点可以有多个。二叉树就是一种典型的树形结构。

（4）

图形结构

图形结构是指该结构中的节点之间存在多对多的关系。其特点是每个节点的前驱和后继的个数都可

以是任意的。图形结构可能没有开始节点和终端节点，也可能有多个开始节点、终端节点。

树形结构和图形结构统称为非线性结构。

3.

存储结构类型

（1）

顺序存储结构

① 存储方式

该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元里，节点之间的逻辑关系由存储单

元的邻接关系来体现。通常顺序存储结构是借助于计算机程序设计语言的数组来描述的。

② 优点

a.

节省存储空间；

b.

可实现对节点的随机存取。

③ 缺点

不便于修改，对节点进行插入、删除运算时，可能要移动一系列的节点。

（2）

链式存储结构

① 存储方式

该结构不要求逻辑上相邻的节点在物理位置上也相邻，节点间的逻辑关系是由附加的指针字段表示

的。通常链式存储结构要借助于计算机程序设计语言的指针类型来描述。

② 优点

便于修改，在进行插入、删除运算时，仅需修改相应节点的指针域，不必移动节点。

③ 缺点

a.

与顺序存储方法相比，链式存储方法的主要缺点是存储空间的利用率较低；

b.

由于逻辑上相邻的节点在存储空间中不一定相邻，所以不能对节点进行随机存取。

（3）

索引存储结构

① 存储方式

该结构通常是在存储节点信息的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引

项的一般形式是：（关键字，地址），其中关键字惟一标识一个节点，地址是指向节点的指针。

② 优点

a．这种带有索引表的存储结构可以大大提高数据查找的速度；

b．可以对节点进行随机访问；

c．仍保持较高的数据修改运算效率。

③ 缺点

增加了索引表，降低了存储空间的利用率。

（4）

散列（或哈希）存储结构

① 存储方式

该结构的基本思想是根据节点的关键字通过哈希（或散列）函数直接计算出一个值，并将这个值作

为该节点的存储地址。

② 优点

查找速度快。

③ 缺点

哈希存储方法只存储节点的数据，不存储节点之间的逻辑关系。哈希存储方法一般只适合要求对数

据进行快速查找和插入的场合。

上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映像。

4.

数据类型和数据结构

（1）

数据类型

① C／C++语言的基本数据类型

a．int型

int型是整型，可以有三个限定词short、long和unsigned，分别对应短整数、长整数和无符号整数。

b．bool型

bool型是逻辑型，其取值只能是false（假）和true（真）。

c．float型

float型是单精度浮点型。

d．double型

double型是双精度浮点型。

e．char型

char型是字符型，用于存放单个字符。

② C／C++语言的指针类型

存放地址的变量称作指针变量。有关指针的两个操作是：

a.

定义了int i，则&i操作是取变量i的地址；

b.

定义了int*p（这里的p是指向一个整数的指针），则*p操作是取p指针所指的值，即取p所指地址

的内容。

③ C／C++语言的数组类型

数组是同一类型的一组有序数据元素的集合。

数组有一维数组和多维数组。数组名标识一个数组，下标指示一个数组元素在该数组中的顺序位

置。数组下标的最小值称为下界，在C／C++中数组下界总为0。数组下标的最大值称为上界，在C／

C++中数组上界为数组大小减1。

④ C／C++语言中的结构体类型

结构体由一组称作结构体成员的项组成，每个结构体成员都有自己的标识符。

⑤ C／C++语言中的共用体类型

共用体是把不同的成员组织为一个整体，在存储器中共享一段存储单元，但不同的成员以不同的方

式被解释。

⑥ C／C++语言中的自定义类型

C／C++语言中允许使用typedef关键字来指定一个新的数据类型名。

⑦ 引用运算符

C++语言中提供了一种引用运算符“&”，当建立引用时，程序用另一个已定义的变量或对象（目

标）的名字初始化它，从那时起，引用就作为目标的别名使用，对引用的改动实际就是对目标的改动。

引用常用于函数形参中，采用引用型形参时，在函数调用时会将形参的改变回传给实参。

（2）

抽象数据类型

① 抽象数据类型定义

抽象数据类型（ADT）指的是用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结

构和逻辑数据结构上的运算。

② 表示方法

其基本格式如下：

ADT抽象数据类型名

{

数据对象：数据对象的声明

数据关系：数据关系的声明

基本运算：基本运算的声明

}ADT抽象数据类型名

其中基本运算的声明格式为：

a.

基本运算名（参数表）：运算功能描述；

b.

基本运算有两种参数：赋值参数，只为运算提供输入值；引用参数，以&打头，除可提供输入

值外，还将返回运算结果。

③ 特征

抽象数据类型有两个重要特征：

a.

数据抽象：强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用

它的方法）；

b.

数据封装：是指将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细

节。

抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）如C++中的类来实现。

二、算法及其描述，

1.

算法概述

（1）

定义

数据元素之间的关系有逻辑关系和物理关系，对应的运算有逻辑结构上的运算（抽象运算）和具体

存储结构上的运算（运算实现）。算法是在具体存储结构上实现某个抽象运算。

算法是对特定问题的求解步骤的一种描述。.

（2）

特点

① 有穷性；

② 确定性；

③ 可行性；

④ 有输入；

⑤ 有输出。

程序可以无穷循环，不一定满足有穷性，但算法必须满足有穷性。

2.

算法描述

常用于描述算法的C／C++语言基本语句：

（1）

输入语句

scanf（格式控制字符串，输入项表）；

（2）

输出语句

printf（格式控制字符串，输出项表）；

（3）

赋值语句

变量名=表达式；

（4）

条 件 语 句

if（条件）语句；

或者

if（条件）语句1 else语句2；

（5）

循环语句

while（表达式）循环体语句；

do循环体语句；

while表达式；

或者

for（赋初值表达式1；条件表达式2；步长表达式3）循环体语句；

（6）

返回语句

return（返回表达式）；

（7）

定义函数语句

函数返回值类型 函数名（类型名形参1，类型名形参2，…）

函数返回值类型 函数名（类型名 形参1，类型名 形参2，…）

{

说明部分；

函数语句部分；

}

（8）

调用函数语句

函数名（实参1，实参2，…）；

三、算法分析

1.

算法设计的目标

（1）

正确性；

（2）

可使用性；

（3）

可读性；

（4）

健壮性；

（5）

高效率与低存储量需求。

2.

算法效率分析

通常有两种衡量算法效率的方法：事后统计法和事前分析估算法。一般采用事前分析估算法来分析

算法效率。

一个算法的执行时间可以由其中基本运算的执行次数来计量。

算法中基本运算执行次数T（n）是问题规模n的某个函数f（n），记作：

T（n）=O（f（n））

记号“O”读作“大O”（是Order的简写，意指数量级），它表示随问题规模n的增大，算法执行时间的

增长率和f（n）的增长率相同。各种不同数量级对应的值存在着如下关系：

O（1）

2

n）

2

n）

2

）

3

）

n

）

算法的时间复杂度（用f（n）表示）采用这种数量级的形式表示后，只需要分析算法中影响算法执

行时间的主要部分即可，不必对每一步都进行详细的分析。

一般情况下，计算一个算法的基本运算次数是相当困难的，甚至是不可能的（因为一个算法的不同

输入往往产生不同的运算次数，而一个算法的所有不同输入的数目可能十分庞大）。一种可行的方法是

计算算法的平均运算次数。

定义 设一个算法的输入规模为n，D

n

是所有输入的集合，任一输入I∈D

n

，P（I）是I出现的频率，

有

，T（I）是算法在输入I下所执行的基本运算次数，则该算法的期望时间复杂度为：

该算法的最坏时间复杂度为：

3.

算法存储空间分析

一个算法的存储量包括输入数据所占空间、程序本身所占空间和辅助变量所占空间。空间复杂度是

对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形

式给出，记作：

S（n）=O（g（n））

若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作。若所需存储量

依赖于特定的输入，则通常按最坏情况考虑。

对于递归算法，为了实现递归过程用到一个递归栈，所以需要根据递归深度得到算法的空间复杂

度。

四、数据结构+算法=程序

1.

程序和数据结构

著名的计算机科学家沃思（N．Wirth）指出，程序就是在数据的某些特定的表示方法和结构的基础

上，对抽象算法的具体表述，所以程序离不开数据结构。

程序是通过某种程序设计语言描述的，程序设计语言有实现数据结构和算法的机制，类型定义与对

象说明和语句是其主要部分。程序设计语言中的类型定义与对象说明实现数据结构；程序设计语言中语

句实现算法，描述了程序的行为。

2.

算法和程序

由程序设计语言描述的算法就是计算机程序。对求解一个问题而言，算法就是解题的方法，没有算

法，程序就成了无本之末，无源之水。算法在程序设计、软件开发甚至在整个计算机科学中的地位都是

极其重要的。

3.

算法和数据结构

通过分析算法的时间复杂度和空间复杂度等，可以得到好的算法，如图1-1所示。

图1-1 设计好算法的过程

存储结构对算法的影响主要在两方面：

（1）

存储结构的存储能力

如果存储结构存储能力强、存储信息多，算法将会较好设计。反之对于过于简单的存储

结构，可能就要设计一套比较复杂的算法。在这一点上，经常存在时间与空间的矛盾，因为存储能

力往往是与所使用的空间大小成正比的。

（2）

存储结构应与所选择的算法相适应

设计算法与选择合适的数据结构是程序设计中相辅相成的两方面，缺一不可。

算法通常是决定程序效率的关键，但一切算法最终都要在相应的数据结构上实现，许多算法的精髓

就是在于选择了合适的数据结构作为基础。在程序设计中，不但要注重算法设计，也要正确地选择数据

结构，这样往往能够事半功倍。

4.

数据结构的发展

早期的计算机主要应用于科学计算，随着计算机的发展和应用范围的拓宽，要求人们对计算机加工

处理的对象进行系统的研究，即研究数据的特性、数据之间存在的关系，以及如何有效地组织、管理存

储数据，从而提高计算机处理数据的效率。数据结构这门学科就是在这样的背景下逐渐形成和发展起来

的。

数据结构的概念最早由和于1966年提出，而对数据结构发展作出杰出贡献的是

和。

习题解答

1.

简述数据与数据元素的关系与区别。

答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。数据元素是数据的基本单

位，是数据的个体。数据与元素之间的关系是元素与集合之间的关系。

2.

数据结构和数据类型有什么区别？

答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，

即数据的逻辑结构、存储结构和数据的运算。而数据类型是一个值的集合和定义在这个集合上的一组运

算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组

成。

3.

设3个表示算法频度的函数f、g和h分别为：

f（n）=100n

3

+n

2

+1000

g（n）=25n

3

+5000n

2

h

（n）=n

1.5

+5000nlog

2

n

求它们对应的时间复杂度。

答 ：f（n）=100n

3

+n

2

+1000=O（n

3

），g（n）=25n

3

+5000n

2

=O（n

3

），

当n→∞时，√n>log

2

n，所以h（n）=n

1.5

+5000nlog

2

n= O（n

1.5

）。

4.

用C／C++语言描述下列算法，并给出算法的时间复杂度。

（1）

求一个n阶方阵的所有元素之和。

（2）

对于输入的任意三个整数，将它们按从小到大的顺序输出。

（3）

对于输入的任意n个整数，输出其中的最大和最小元素。

答：（1）算法如下：

本算法的时间复杂度为O（n

2

）。

（2）

算法如下：

本算法的时间复杂度为O（1）。

（3）

算法如下：

本算法的时间复杂度为O（n）。

5.

设n为正整数，给出下列各种算法关于n的时间复杂度。

（1）

（2）

（3）

答：（1）设while循环语句执行次数为T（n），则：

（2）

算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：

（3）

设while循环语句执行次数为T（n），则：