《数据结构与算法 C语言版》—— 1.2数据结构的发展概况

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第1章，第1.3节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.3基本概念与术语

计算机科学是研究信息表示和处理的科学，信息在计算机内是用数据表示的。直观地说，数据是用于描述客观事物的数值、字符以及一切可以输入到计算机中并由计算机程序加以处理的符号的集合，是计算机操作的对象的总称。
数据元素是数据的基本单位，它是数据中的一个“个体”，如整数“5”、字符“N”等。有时，一个数据元素可由若干数据项组成，例如，描述一个学生的信息为一个数据元素，学生信息中的每一项(如姓名、学号等)为一个数据项。数据项是数据的不可分割的最小单位。
数据对象是具有相同性质的数据元素的集合，是数据的一个子集。数据元素是数据对象的实例。例如，整数数据对象是集合{0，±1，±2，±3，…}。
数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合。根据数据元素之间关系的不同，数据通常有以下四类基本的结构。
1)集合结构：在集合结构中，数据元素之间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。
2)线性结构：该结构中的数据元素之间存在着一对一的关系。
3)树形结构：该结构中的数据元素之间存在着一对多的关系。
4)图形结构：该结构中的数据元素之间存在着多对多的关系。由于集合结构是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它。图13为上述四类基本结构的关系图。

由数据结构的概念可知，数据结构有三个要素：一是数据元素的集合，二是数据元素之间关系的集合，三是定义在其上的操作。在形式上，数据结构可定义为一个二元组：

Data_Structures=(D，S)

其中:D是数据元素的有限集，S是D上关系的有限集。
数据结构包括数据的逻辑结构和物理结构。数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系来表示，与数据的存储无关；数据的物理结构是逻辑结构在计算机中的表示和实现，故又称“存储结构”。
数据结构在计算机中的表示，包括数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制的一位，叫做位(bit)。在计算机中，可以用由若干位组合起来的一个位串表示一个数据元素(如用一个字长的位串表示一个整数，用8位二进制数表示一个字符等)。
数据元素之间的关系在计算机中有四种不同的表示方法，下面分别介绍。
(1)顺序存储方法
该方法把逻辑上相邻的元素存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，该结构通常是借助于计算机程序设计语言(例如C、C++)的数组来描述的。
顺序存储方法的主要优点是节省存储空间，因为分配给数据的存储单元完全用于存放数据(不考虑C、C++语言中数组需指定最大存储空间大小的情况)，结点之间的逻辑关系不占用额外的存储空间。采用这种方法，可实现对数据的随机存储。但顺序存储方法的主要缺点是不便于修改，对数据进行插入、删除操作时，可能要移动一系列数据。
(2)链式存储方法
该方法不要求逻辑上相邻的元素在物理位置上也相邻，元素之间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，该结构通常是借助于计算机程序设计语言(例如C、C++)的指针类型来描述的。
链式存储方法的主要优点是便于修改，在进行插入、删除操作时，仅需要修改指向相应数据元素的指针，而不必移动数据元素。但与顺序存储方法相比，其主要缺点是存储空间的利用率较低，因为分配给数据的存储单元有一部分用来存储数据元素之间的逻辑关系了。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。
(3)索引存储方法
该方法通常在存储数据元素的同时，还建立附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是：(关键字，地址)，关键字唯一标识一个数据元素，地址作为指向该数据元素的指针。这种带有索引表的存储结构可大大提高数据查找的速度。
线性结构中采用索引存储方法后，可对数据元素进行随机存取。在进行插入、删除操作时，只需移动存储在索引表中对应数据元素的存储地址，而不必移动数据元素本身，所以仍能保持较高的数据修改运算效率。索引存储方法的缺点是增加了索引表，降低了存储空间的利用率。
(4)哈希(或散列)存储方法
该方法的基本思想是根据数据元素的关键字，通过哈希函数直接计算出一个值，并将这个值作为该数据元素的存储地址。
哈希存储方法的优点是查找速度快，只要给出待查找数据元素的关键字，就可以立即计算出该数据元素的存储地址。但与前三种存储方法不同的是，哈希存储方法只存储数据元素，不存储数据元素之间的逻辑关系。哈希存储方法一般只适合要求对数据进行快速查找和插入的场合。
上述四种存储方法既可以单独使用，也可以组合起来使用。