1.3 数据的存储结构

所有的数据在处理前，都需要按照一定的格式进行存储，数据的存储结构关系到数据在内存中的组织形式。存储结构是数据的逻辑结构在计算机存储器内的表示，包含下列两层含义。

●存储具体数据元素。

●存储元素之间的关系。

按照数据元素的关系在计算机中存储表示的不同，存储结构分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构四种不同的结构，下面分别介绍这四类存储结构。

1. 顺序存储结构

顺序存储结构就是在计算机中开辟一组连续的存储空间来依次存储数据元素，数据元素的逻辑次序与其物理存放位置的次序是相同的。在C++语言中，用一维数组表示顺序存储结构，可以随机直接定位数据元素。

2. 链式存储结构

链式存储结构不需要开辟连续的存储空间，数据元素是离散存储的。为了存储数据元素之间的逻辑关系，链式存储结构在存储数据元素时，除存储数据元素本身数据以外，还需要额外的存储空间来存储逻辑关系。一般，在每一个数据元素中增加一个存放另一个元素地址的指针，用该指针表示数据元素之间的逻辑关系。

3. 索引存储结构

索引存储结构通过对一组数据元素中的关键码进行排序，通过关键码可以快速查找对应的数据元素。

4. 散列存储结构

散列存储结构通过建立一类函数，设计数据元素的存储地址和它的关键字之间的对应关系，直接通过关键字定位数据元素的存储位置。

数据结构作为一门独立的课程是从1968年才开始的。20世纪60年代中期，美国的一些大学开始设立有关课程，但当时的课程名称并不叫数据结构。1968年，美国的唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》的第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构、存储结构及其操作的著作。从20世纪70年代中期到20世纪80年代，各种版本的数据结构著作相继出现。

目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。