1.2 基本概念和术语

1.2.1 基本概念和术语

本节将对一些常用的概念和术语进行介绍，这些概念和术语在以后的章节中会多次出现。

1. 数据

数据即信息的载体，是对客观事物的符号表示，凡能输入到计算机中并被计算机程序处理的符号都可称之为数据，如整数、实数、字符、文字、声音、图像等都是数据，如图1.3所示。

2. 数据元素

数据元素是数据的基本单位，它在计算机处理和程序设计中通常作为独立个体。数据元素一般由一个或多个数据项组成，一个数据元素包含多个数据项时，常称为记录、结点等。数据项也称为域、字段、属性、表目、顶点。

如表1-3所示，每个同学的信息即表中的一行，是一个数据元素。每个数据元素又包含若干个数据项，如专业、学号等。

3. 数据对象

数据对象是具有相同特征的数据元素的集合，是数据的一个子集，如一个整型数组、一个字符串数组都是一个数组对象。

例如要将表1-3中的学生信息按照学号大小进行排序，排序时比较的是各个数据元素中学号这一数据项的大小。此时整个表中的数据元素就是待处理的数据对象。

4. 数据结构

数据结构简称DS（Data Structure），是数据及数据元素的组织形式。任何数据都不是彼此孤立的，通常把相关联的数据按照一定的逻辑关系组织起来，这样就形成了一个数据结构。

数据结构包含两个方面的内容，一是数据对象，二是数据对象中数据元素之间内在的关系。数据结构通常有四类基本形式：集合结构，线性结构，树型结构，图形结构或网状结构。

（1）集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。各个数据元素是“平等”的，它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合。

【例1-4】电视机、冰箱等家用电器构成的就是一个集合结构，如图1.4所示。

（2）线性结构：线性结构中的数据元素之间是一对一的关系。

【例1-5】节气是中国古代订立的一种用来指导农事的补充历法，是汉族劳动人民长期经验的积累和智慧的结晶。春季的节气有立春、雨水、惊蛰、春分、清明、谷雨，这些节气一个接一个就是一种线性关系，如图1.5所示。

（3）树型结构：树形结构中的数据元素之间存在一种一对多的层次关系。

【例1-6】院系机构的组织就是一种树型结构，如图1.6所示。计科系和电子系的地位是“平等”的，电子系开设有信息工程、通信、微电子等专业，它们受电子系的“领导”。反过来看，无论是通信工程，还是微电子，都属于电子系，无论是计科系，还是电子系，都属于某学院，即树型结构中正关系是一对多，逆关系是一对一。

（4）图状结构：图状结构中的数据元素是多对多的关系。

【例1-7】在一个学生选课系统中，数据库的设计采用的就是网状结构，如图1.7所示。把S1学生和他的选课记录（选修的C1、C2两门课程的选课记录）链接起来，同样把S2、S3、S4学生和他们的选课记录链接起来，把C1课程和选修了C1课程的选课记录（有S1、S2、S3、S4学生选修了C1）链接起来，同样把C2、C3课程和选修了这些课程的选课记录链接起来，通过分析可以发现一个学生可以选修若干门课程，某一课程可以被若干同学选修，学生与课程之间是多对多的关系。

5. 数据类型

数据类型是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合，如整数类型、字符类型等。每一种数据类型都有自身特点的一组操作方法，即运算规则。JAVA中提供的基本的数据类型有int，double，long，float，short，byte，character，boolean。

由于集合中的元素的关系极为松散，可用其他数据结构来表示，所以本书不做专门介绍。

从数据类型和数据结构的概念可知，二者的关系非常密切。数据类型可以看作是简单的数据结构。数据的取值范围可以看作是数据元素的有限集合，而对数据进行操作的集合可以看作是数据元素之间关系的集合。

1.2.2 数据的逻辑结构

数据的逻辑结构（Logic Structure）是从具体问题抽象出来的数学模型，与数据在计算机中的具体存储没有关系。数据的逻辑结构独立于计算机，是数据本身所固有的特性。从逻辑上可以把数据结构分为线性结构和非线性结构，上述数据结构的定义就是数据的逻辑结构（Logic Structure），主要包括：集合、线性、树和图形结构，其中集合、树和图形结构都属于非线性结构。

数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系集，它反映了D中各数据元素之间的前驱后继关系，通常记为R，即一个数据结构可以表示成二元组B=(D,R)。

【例1-8】一年四季可表示成B1=(D1,R1)，其中

D1={春,夏,秋,冬}，R1={<春,夏>,<夏,秋>,<秋,冬>}；

序偶关系<春,夏>表示：春季之后的下一个季节是夏季，反过来夏季的前一个季节是春季，其他依此类推，通过关系集R1就可以描述出一年四季的更替顺序春、夏、秋、冬，同时我们可以发现在关系集R1中，夏季和秋季都有一个直接前驱和一个直接后继，春季作为一年之首是没有前驱的，但是有一个直接后继夏，冬季作为一年之尾没有后继，但是有一个前驱，所以二元组B1描述的是一个一对一关系的线性结构。

注意，<x,y>意为x和y之间存在"x领先于y"的次序关系。而(x,y)表示x和y之间没有次序上的关系。

【例1-9】某单位的管理关系可表示成B2=(D2,R2)，其中

D2={总经理，部门经理A，部门经理B，组长A，组长B，组长C，组长D，职工A，职工B，职工C，职工D，职工E，职工F，职工G，}

R2={<总经理, 部门经理A>,<总经理, 部门经理B>,<部门经理A, 组长A>，<部门经理A, 组长B>，<部门经理B, 组长C>，<部门经理B, 组长D>，<组长A，职工A>，<组长A，职工B>，<组长A，职工C>， <组长D，职工D>，<组长D，职工E>，<组长D，职工F>，<组长D，职工G>}；

通过分析关系集R2可知该单位人员的关系为：一个总经理管理若干部门经理，每个部门经理管理若干小组长，每个小组长管理若干职工。但是每个职工的直接领导，即组长，只有一个，每个组长的直接领导，即部门经理，只有一个，每个部分经理的直接领导总经理只有一个，即二元组描述的是一个一对多关系的树型结构，如图1.8所示。

【例1-10】A某的人际关系可以表示成B3=(D3,R3)，其中

D3={A某，B某，C某，D某，E某，F某，G某，H某}，

R3={<A某,B某>,<A某,C某>,<B某，D某>，<B某,，E某>,<B某，F某>,<C某，F某>，<C某，G某>,<E某，H某>，<F某，H某>}；

通过分析关系集R3可知A某的人际关系为：每个人可以有多个朋友，同一个人也可以是多个人共同的朋友。例如，F某既是B某的朋友，也是C某的朋友，即二元组描述的是一个多对多关系的图形结构，如图1.9所示。

上述数据结构的定义仅是对操作对象的一种数学描述，是从操作对象抽象出来的数学模型，结构定义的“关系”抽述的是数据元素之间的逻辑关系，所以称为逻辑结构。

1.2.3 数据的物理结构

我们讨论数据结构的目的是为了在计算机中实现对它的操作，因此还需要研究在计算机中如何表示和存储数据结构，即数据的物理结构（Physical Structure）。数据的物理结构又称存储结构，它的实现依赖于具体的计算机语言。数据存储结构有顺序和链式两种不同的方式，顺序存储的特点是数据元素在存储器的相对位置来体现数据元素相互间的逻辑关系，顺序存储结构通常用高级编程语言中的一维数组来描述或实现。

例如：一个有序的数字序列（25，34，48，57，63），25有一个直接后继34，如果该有序表用数组存储，通过图1.10可以发现相邻的25和34在存储器中的地址也是相邻的，即数据元素在存储器中的相对位置可以体现数据元素在有序表中的前驱和后继关系，整个数组在存储器中占用的是一片连续的存储空间。

链式存储结构是通过一组任意的存储单元来存储数据元素的，而这些存储单元可以是连续的，也可以是不连续的。为建立起数据元素之间的逻辑关系，对任一数据元素a，除了存放元素自身信息a之外，还需要存放与a有关系的其他元素的地址150，通过这个地址就可以找到下一个数据元素b，依此类推，可以发现字符序列（‘a’，‘b’，‘c’，‘d’，‘e’，‘f’）在存储器中的地址是不连续的。

在顺序存储结构的基础上，又可延伸出另外两种存储结构，即索引存储和散列存储。

索引存储就是在数据文件的基础上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。

散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量达到一一对应的目的。这样，查找时同样可以大大提高效率。

数据的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的逻辑结构，而算法的实现依赖于采用的存储结构。综上所述，数据结构主要描述的是数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算三个方面的内容，即数据的逻辑结构、存储结构和数据的操作集合。