下载掌阅APP，畅读海量书库
立即打开
在系统地学习数据结构知识之前，先对一些基本概念和术语赋予确切的含义。
数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，将一切能够输入计算机，并被计算机程序处理的信息，包括文字、表格、图像等，都称为数据。例如，一个学生信息的表格。
数据元素是组成数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。在程序中通常把结点作为一个整体进行考虑和处理。例如，在如图1.4所示的学生信息中，为了便于处理，把其中的每一行（代表一个学生）作为一个基本单位来考虑，故该数据由30 个结点构成。一般情况下，一个结点中含有若干个字段（也称为数据项）。例如，在图1.4 中，每个结点都由学号、姓名、分组、年龄和住址5 个字段构成。字段是构成数据的最小单位。
数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，如图1.4所示的表也可看成一个数据对象。由此可以看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同，都是同一个数据对象。
图1.4 学生信息表
数据结构是研究数据元素（Data Element）之间抽象化的相互关系和这种关系在计算机中的存储表示（即所谓数据的逻辑结构和物理结构），并对这种结构定义相适应的运算，设计出相应的算法，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。根据数据元素间关系的不同特性，通常有下列4 类基本的结构：
● 集合结构：在集合结构中，数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。
● 线性结构：该结构的数据元素之间存在着一对一的关系。
● 树形结构：该结构的数据元素之间存在着一对多的关系。
● 图形结构：该结构的数据元素之间存在着多对多的关系，图形结构也称为网状结构。
图1.5为表示上述4 类基本结构的示意图。由于集合是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它。
图1.5 4 类基本结构的示意图
从上述的数据结构的概念中可知，一个数据结构有两个要素：一个是数据元素的集合；另一个是关系的集合。在形式上，数据结构通常可以采用一个二元组来表示。
数据结构的形式定义为：数据结构是一个二元组。
Data_Structure＝（D，R）
其中：D是数据元素的有限集，R是D上关系的有限集。
数据的逻辑结构（Logical Structure）是指数据结构中元素之间的逻辑关系，它是从具体问题中抽象出来的数学模型，是独立于计算机存储器的（与具体的计算机无关）。数据的逻辑结构可分为4 种基本类型：集合结构、线性结构、树形结构和图形结构，表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构（一对一关系），树（一对多）和图（多对多）是非线性结构。
数据存储结构（Storage Structure）是数据的逻辑结构在计算机内存中的存储方式，又称为物理结构。数据存储结构要用计算机编程语言来实现，因而依赖于具体的计算机语言，其可分为顺序存储或链式存储两种方式。
● 顺序存储：是把逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储方式称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
● 链式存储：是对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示，由此得到的存储方式称为链式存储结构。链式存储结构通常借助于程序设计语言中的指针类型来实现。
除了通常采用的顺序存储方式和链式存储方式外，有时为了查找的方便还采用索引存储方式和散列存储方式。
索引存储：在数据文件的基础上增加一个索引文件，通过索引表建立索引，可以将一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，避免盲目查找。
散列存储：是通过数据元素与存储地址之间建立某种映射关系，使每个数据元素与每个存储地址之间尽量达到一对一的关系。
数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等的操作过程。在早期，计算机主要用于科学和工程计算，进入20 世纪80年代以后，计算机主要用于数据处理。据有关统计资料表明，现在计算机用于数据处理的时间比例达到80%以上，随着时间的推移和计算机应用的进一步普及，计算机用于数据处理的时间比例必将进一步增大。
数据类型（Data Type）是和数据结构密切相关的一个概念，在用高级程序设计语言编写的程序中，每个变量、常量或表达式都对应一个确定的数据类型。数据类型可分为两类：一类是非结构的原子类型，如基本数据类型（整型、实型、字符型等）；另一类是结构类型，它可以由多个结构类型组成，并可以分解。结构类型的分解量可以是结构的，也可以是非结构的。例如数组的值由若干分量组成，每个分量可以是整型，也可以是数组等结构类型。