第1章习题解答
1.1 什么是数据结构？一个数据结构结构的二元组定义形式是什么样的？举例解释其 含义。
[解答]
概括地说，数据结构是互相有关联的数据元素的集合。也就是说，数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的，因此数据结构可以用一个二元组来表示。例如，B=（D，R），其中D是某一数据元素的集合，R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系，它表示的可能是数据元素之间客观存在的某种联系，也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系，因此，称之为数据的逻辑结构。例如，一个农历节气表，就构成了一个数据结构，其数据元素是一年的农历二十四节气，数据元素之间的关系是节气的时间先后关系。又如，一个某年级学生的成绩排序表，也是一个数据结构，其数据元素是包含成绩项的该年级的学生记录，数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理，必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中，即要把抽象出来的数据元素集合D和数据元素之间的关系存储到计算机的存储器中，称之为数据的物理结构或存储结构，它是数据的逻辑结构在计算机中的表示。
1.2 假设R是集合M上的一个关系，R的定义是什么？对实际问题而言，其含义是 什么？
[解答]
如果R是对集合M自身的笛卡尔积所取的一个子集，那么我们就说“R是集合M上的一个关系”。对实际问题而言，它表示的是集合M中元素的某种相关性。例如，对于参加一个羽毛球比赛的运动员集合，可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合，可以用一个二元关系表示出各门课程之间的先修和后续关系等等。
1.3 设有集合M={d1,d2,d3,d4,d5}上的一个关
R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)}，试说明关系
R具有什么样的性质。
[解答]
从二元关系的基本性质容易验证，该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(di,di)这样的元素，所以它是反自反的。
因为关系R中没有(元素di,dj)和(dj,di)同时存在的情况，所以它是反对称的。 关系R 的传递性表现在：
有元素(d1,d2),(d2,d4)，同时有元素(d1,d4), 有元素(d1,d2),(d2,d5)，同时有元素(d1,d5), 有元素(d1,d3),(d3,d5)，同时有元素(d1,d5)， 有元素(d1,d4),(d4,d5)，同时有元素(d1,d5)， 有元素(d2,d4),(d4,d5)，同时有元素(d2,d5)。
1.4 什么是线性结构？什么是非线性结构？举例说明。 [解答]
1
线性结构与非线性结构是针对数据的逻辑结构而言的。它们的主要区别是：线性结构表示的是数据元素之间一对一的关系，而非线性结构表示的是数据元素之间一对多或多对多的关系。线性结构具有以下特点：
① 存在唯一的没有前驱、只有一个直接后继的“头”元素； ② 存在唯一的没有后继、只有一个直接前驱的“尾”元素；
③ 除了“头”元素和“尾”元素之外，集合中的每个元素有且只有一个直接前驱、 有且只有一个直接后继。
由以上特点可以看出，线性结构中的数据元素之间存在一对一的关系，结构中的数据 元素依照它们的逻辑关系可以排成一个有“头”、有“尾”的序列。例如，前面所说的农历节气表，就是一个线性结构，它是一个从“春分”开始，然后是“雨水”，…，最后是“大寒”。这样一个序列。
除线性结构以外的结构称为非线性结构。在非线性结构中，各数据元素的关系不一定 保持一个线性序列，每个数据元素可能与零个或多个数据元素有联系。也就是说，非线性结构中的数据元素之间存在一对多或者是多对多的关系。
例如，一个学校的教学组织关系可以构成一个有明显层次的数据结构：学校下属有若干学院，每个学院下设若干个系，每个系有多个研究所和教研组，有若干的学生班，这个一对多的关系的抽象就是非线性结构。
又如，对一个销售系统的各个连锁店及相互之间的联系的抽象是一个非线性结构，这个数据结构中的数据元素是各连锁店，数据元素之间的关系是各连锁店之间的联系，因为各连锁店之间都可以有联系，显然各连锁店之间的联系是多对多的联系。也就是说，每一个连锁店都可以与其余多个连锁店发生联系。这个结构也是非线性结构。
1.5 数据的存储结构有哪几种？其中最常用的有哪几种？说明它们的特点。 [解答]
数据存储结构也称物理结构，它是数据的逻辑结构在计算机中的表示。数据的存储结构有顺序存储、链式存储、索引存储、散列存储四种方式。其中最常用的存储结构有顺序存储和链式存储两种。
在顺序存储方式中，要开辟一块连续的存储空间来存放数据结构；对每个数据元素给以等长的数据单元，结构中的数据元素按照它们之间的逻辑顺序依次存放于连续的内存单元中。顺序存储方式的特点是除了存储数据元素以外，不必耗费另外的空间，数据元素之间的关系是由数据元素在存储器中的邻接关系来表示的。由于数据元素在存储器中的物理顺序和它们之间的逻辑顺序一致，因此这种存储方式是非常直观的一种存储方式。
在链式存储方式中，数据元素可以存放在不连续的内存单元中，数据元素在存储器中的物理存放顺序可以和逻辑顺序不一致，数据元素之间的逻辑关系是通过指示数据元素存储地址的指针来表示的。因此，每个数据元素除了存储自身以外，同时还要存储指示其后件(或前件)的存储地址的指针，它们构成一个结点。也就是说，在链式存储方式中每个数据元素的存储映象是一个结点，它包括存储数据元素的数据域(也称作值域)和存储指针的指针域两 部分，通过各结点的指针把各数据元素按照它们的逻辑关系链成一条“链”，从而清晰的表示了数据元素之间的逻辑关系。链式存储的明显优点是存储空间的利用比较灵活，数据元素的增减操作比较方便。
除了上述两种常用的存储方式以外，还有索引存储和散列存储方式。 在索引存储方式中，按照某种性质把一个大表的元素划分成若干个子表，使每个子表中的元素具有相同的性质。存储时以子表为单位存放，同时建立一个索引表，索引表中的每个索引项对应一个子表，指出该子表的起始地址、长度和子表的性质，这样能够给查找等操作
2
带来很大的方便。显然，在该存储方式下数据元素之间的逻辑关系是通过数据元素在索引表中的位置得以反映的。
在散列存储方式中，通过数据元素的关键字值来确定数据元素的存储位置，因而可以直接通过计算查找到相应的数据元素。使得它比通过“比较”查找有更高的效率。
1.6 设数据元素的集合为D={a1,a2,a3,a4,a5,a6}，请分别画出与以下各关系R对应
的数据结构B=(D,R)的结构示意图，并指出它属于哪类结构。 (1) R={(a3,a4),(a4,a5),(a1,a2),(a2,a3),(a5,a6)} (2) R={(a3,a2),(a2,a4),(a3,a1),(a2,a5),(a2,a6)} (3) R={(ai+1,ai)︱i=5,4,3,2,1} (4) R={(ai,aj)︱i>j} (5) R={ }
[解答]
(1) 为线性结构，其图形表示如图1-1 (a) 所示。 (2) 为非线性结构，其图形表示如图1-1 (b) 所示。 (3) 为线性结构，其图形表示如图1-1(c) 所示。 (4) 非线性结构，其图形表示如图1-1(d) 所示。
(5) 集合结构，除了同属一个集合外，数据元素间无其他关系。
(a) (c)
(b) (d)
图 1-1
1.7 什么是抽象数据类型？ 抽象数据类型和面向对象的程序设计方法有什么关系？ [解答]
抽象数据类型是指用以表示应用问题的一个数据模型以及定义在该模型上的一组操作。它与一般的数据类型的概念在本质上是一致的，都是对数据类型的数学特性的抽象，其目的是可以使程序设计者，在程序设计中更专注于数据的逻辑特性，而不必关心抽象数据类型实现的具体细节。但抽象数据类型比一般数据类型的抽象层次更高、范畴更广，它不局限于计算机系统中已定义和实现的数据类型，通常它是由用户根据实际问题的需要而定义，且通过计算机系统中已经定义的数据类型来表示和实现。因此，它是基于一般数据类型的更高层次上的一种数据抽象。
抽象数据类型的概念是由于程序设计方法和技术的发展而提出来的。为了更好的提高软件模块的可复用性和可扩充性，现代程序设计方法强调以数据为基础来构建软件系统，更加
3
强调“封装”和“信息隐蔽”策略。面向对象的程序设计方法正是符合这种要求的方法。“类”是面向对象的程序设计方法中的核心概念，它是数据抽象的结果，类不但体现了封装和信息隐蔽的原则，而且具有继承性，因而为模块的复用提供了很好的条件。抽象数据类型具有封装和信息隐蔽的特点，可以做到使用与实现分离。由此可见，抽象数据类型与面向对象的方法的思想是一致的，从抽象数据类型出发来进行面向对象的程序设计，会使程序设计更加顺理成章。
1.8 完成以下问题：
2
(1) 设计二次多项式ax+bx+c的一种抽象数据类型，其数据部分为多项式的三个系数 项a、b、c；操作部分包括：初始化数据成员a、b、c，实现两个多项式相加，给定x求多
2
项式的值，求方程ax+bx+c=0的两个实根，按照ax**2+bx+c的格式输出二次多项式。
(2) 假定数据成员a、b、c定义如下：
typedef struct { float a,b,c ; }Quadratic ;
请写出上述各操作的具体实现。 [解答]
(1) 对题中的二次多项式抽象数据类型可以作以下定义： ADT Quadratic
{数据：
一元二次多项式的二次项系数a，一次项系数b，常数项c；其结构类型为：Quadratic 操作：
// 初始化一元二次多项式
Quadratic *InitQuadratic (flaot aa, float bb, float cc) ；
Quadratic *Add (Quadratic *f1, Quadratic *f2 ) ； // 两个多项式相加
float Value (Quadratic *f, float x) ； // 计算一元二次多项式的值 int Root (quadratic *f, float& r1, float& r2) ； // 求一元二次方程的两个实根 void print (Quadratic *f) ； // 按指定格式输出多项式 }
(2) 数据成员定义和指定的操作的实现如下： 数据成员定义： typedef struct { float a, b, c ； } Quadratic；
数据成员初始化：
Quadratic *InitQuadratic (flaot aa, float bb, float cc ) { Quadratic *f ；
f->a=aa；f->b=bb；f->c=cc ； return f ； }
4
两个二次多项式相加：
Quadratic *Add ( Quadratic *f1, Quadratic *f2 ) { Quadratic *f ；
f->a=f1->a + f2->a ； f->b=f1->b + f2->b ； f->c=f1->c + f2->c ； return f ； }
由给定的x，求二次多项式的值： float Value (Quadratic *f, float x ) { return (f->a*x*x+f->b*x+f->c ) ； }
求一元二次方程的实根：
int Root (quadratic f, float *r1, float *r2 ) {float d ;
if (f->a==0) return –1 ； d=f->b*f->b-4*f->a*f->c ； if (d>=0)
{ r1=(-f->b+sqrt(d))/(2*f->a) ；
r2=(-f->b-sqrt(d))/(2*f->a) ；
return 1 ； }
else return 0 ； }
按照要求的形式输出二次多项式： void print (Quadratic *f )
{ if (f.a) printf (〞%f x**2〞, f.a ) ； if (f.b )
{ if (f.b>0 ) printf (〞+%f x 〞, f.b ) ； else printf (〞%f x 〞, f.b ) ；
} if (f.c )
{ if (f.c>0 ) printf (〞+%f 〞, f.c ) ； else printf (〞%f 〞, f.c ) ；
}
printf (〞\\n ) ； }
1.9 算法的基本特征是什么？算法分析主要针对哪些方面？ [解答]
5