1.1 数据结构的基本概念
1.1.1 为什么要学习数据结构
软件设计是计算机学科的核心内容之一。进行软件设计时要考虑的首要问题是数据的表示、组织和处理方法，这直接关系到软件的工程化程度和软件的运行效率。
随着计算机技术的飞速发展，计算机应用从早期的科学计算扩大到过程控制、管理和数据处理等领域。计算机处理的对象也从简单的数值数据，发展到各种多媒体数据。软件系统处理的数据量越来越大，数据的结构也越来越复杂。因此，针对实际问题，如何合理地组织数据，如何建立合适的数据结构，如何设计好的算法，是软件设计的重要问题，而这些正是“数据结构”课程讨论的主要内容。
在计算机中，现实世界中的对象用数据来描述。“数据结构”课程的任务是，讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。数据结构课程的主要目的是，培养学生掌握处理数据和编写高效率软件的基本方法，为学习后续专业课程以及进行软件开发打下坚实基础。
数据结构是软件设计的重要理论和实践基础，数据结构设计和算法设计是软件系统设计的基础和核心。“数据结构”课程讨论的知识内容是软件设计的理论基础，“数据结构”课程介绍的技术方法是软件设计中使用的基本方法。“数据结构”是一门理论与实践并重的课程，学生既要掌握数据结构的基础理论知识，又要掌握运行和调试程序的基本技能。因此，“数据结构”课程在计算机学科本科培养过程中的地位十分重要，是计算机专业本科的核心课程，是培养程序设计能力的必不可少的重要环节。
在计算机界流传着一句经典名言“数据结构+算法=程序设计”（瑞士Niklaus Wirth教授），这句话简洁、明了地说明了程序（或软件）与数据结构和算法的关系，以及“数据结构”课程的重要性。
1.1.2 什么是数据结构
数据（data）是描述客观事物的数字、字符以及所有能输入到计算机中并能被计算机接受的各种符号集合的统称。数据是信息的符号表示，是计算机程序的处理对象。除了数值数据，计算机能够处理的数据还可以是各种非数值数据，如字符串、图形、图像、音频、视频等多媒体数据。
表示一个事物的一组数据称为一个数据元素（data element），数据元素是数据的基本单位。一个数据元素可以是一个不可分割的原子项，也可以由多个数据项组成。数据项（data item）是数据元素中有独立含义的、不可分割的最小标识单位。例如，一个整数、一个字符都是原子项，一个学生数据元素由学号、姓名、性别和出生日期等多个数据项组成。关键字（key）是数据元素中用于识别该元素的一个或多个数据项，能够唯一识别数据元素的关键字称为主关键字（primary key）。
在由数据元素组成的数据集合中，数据元素之间通常具有某些内在联系。研究数据元素之间存在的关系并建立数学模型，是设计有效地组织数据和处理数据方案的前提。
数据的结构是指数据元素之间存在的关系。一个数据结构（data structure）是由n（n≥0）个数据元素组成的有限集合，数据元素之间具有某种特定的关系。
数据结构概念包含三方面：数据的逻辑结构、数据的存储结构和数据的操作。
1.数据的逻辑结构
数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常被简称为数据结构。
根据数据元素之间逻辑关系的不同数学特性，数据结构可分为三种：线性结构、树结构和图结构（如图1.1所示），其中树和图又称为非线性结构。
图1.1以图示法表示了数据的逻辑结构，一个圆表示一个数据元素，圆中的字符表示数据元素的标记或取值，连线表示数据元素之间的关系。
图1.1 三种数据结构
（1）线性结构
线性结构是最简单的数据结构，数据元素之间具有线性关系，即除第一个和最后一个元素外，每个元素有且仅有一个直接前驱元素和一个直接后继元素，第一个元素没有前驱元素，最后一个元素没有后继元素。在图1.1（a）中，元素B的前驱是A，后继是C，元素A没有前驱，元素C没有后继。线性表、串、栈和队列等都是线性结构。
数据元素可以是数字﹑字符、字符串或其他复杂形式的数据，如整数序列{1, 2, 3, 4, 5, 6}，字母序列{'A', 'B', 'C',…, 'Z'}，表1-1所示的学生序列也是线性表，数据元素之间具有顺序关系。学生数据元素由“学号”、“姓名”、“年龄”等多个数据项组成，“姓名”可以作为标识一个学生的关键字，但不是主关键字；“学号”是能够唯一标识一个学生的主关键字。
表1-1 学生信息表
（2）树结构
树结构是数据元素之间具有层次关系的一种非线性结构，树中的数据元素通常称为结点。树结构的层次关系是指，根结点（最顶层）没有前驱结点（称为父母结点），除根之外的其他结点有且仅有一个父母结点，所有结点可有零到多个直接后继结点（称为孩子结点）。在图1.1（b）中，A是树的根结点，B结点有一个父母结点A，且有3个孩子结点D、E和F。家谱、Windows文件系统的组织方式、淘汰赛的比赛规则等都是树结构。具有树结构的淘汰赛比赛规则如图1.2所示，其中的数据是2006年世界杯足球赛淘汰赛的比赛结果。
图1.2 具有树结构的淘汰赛比赛规则
（3）图结构
图也是非线性结构，每个数据元素可有多个直接前驱元素和多个直接后继元素。例如，交通道路图、飞机航班路线图等都具有图结构。图1.3是从南京飞往昆明的航班路线图，有直飞航班，也有经停重庆或长沙的航班，连线边上数值表示两地间的千米数。
图1.3 南京飞往昆明的航班路线图
2.数据的存储结构
数据元素及其关系在计算机中的存储表示或实现称为数据的存储结构，也称为物理结构。软件系统不仅要存储所有数据，还要正确地表示出数据元素之间的逻辑关系。
数据的逻辑结构是从逻辑关系角度观察数据，与数据的存储无关，是独立于计算机的。而数据的存储结构是逻辑结构在计算机物理存储中的实现，是依赖于计算机的。
数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。
（1）顺序存储结构
顺序存储结构使用一组连续的内存单元依次存放数据元素，元素在内存的物理存储次序与它们的逻辑次序相同，即每个元素与其前驱及后继元素的存储位置相邻。这样，元素的物理存储次序体现数据元素间的逻辑关系，通常使用程序设计语言中的数组实现。
（2）链式存储结构
链式存储结构使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素间的关系需要采用附加信息特别指定。通常，采用指针变量记载前驱或后继元素的存储地址，由数据域和指针域组成的一个结点表示一个数据元素，通过指针域把相互直接关联的结点链接起来，结点间的链接关系体现数据元素间的逻辑关系。
线性表可采用上述两种存储结构。如线性表（A, B, C, D）的两种存储结构如图1.4所示。
图1.4 线性表（A, B, C, D）的两种存储结构
在线性表的顺序存储结构中，数据域占用所有存储空间，数据元素连续存储，逻辑上相邻的数据元素在存储位置上也相邻，因此数据的存储结构体现数据的逻辑结构。
在链式存储结构中，数据元素分散存储，每个结点至少由两部分组成：数据域和指针域，分别保存数据元素及前驱和（或）后继结点的地址。结点间的链接关系体现数据的逻辑结构。
如果一个数据元素由多个数据项组成，则数据域有多个。例如，学生信息表的顺序存储结构和链式存储结构如图1.5所示。
图1.5 学生信息表的两种存储结构
顺序存储结构和链式存储结构是两种最基本、最常用的存储结构。除此之外，将顺序存储结构和链式存储结构进行组合，还可以构造出更复杂的存储结构。
3.数据操作
数据操作是指对一种数据结构中的数据元素进行各种运算或处理。每种数据结构都有一组数据操作，其中包含以下基本操作。
◉ 初始化。
◉ 判断是否空状态。
◉ 求长度：统计元素个数。
◉ 包含：判断是否包含指定元素。
◉ 遍历：按某种次序访问所有元素，每个元素只被访问一次。
◉ 取值：获取指定元素的值。
◉ 置值：设置指定元素的值。
◉ 插入：增加指定元素。
◉ 删除：移去指定元素。
数据操作定义在数据的逻辑结构上，对数据操作的实现依赖于数据的存储结构。例如，线性表包含上述一组数据操作，采用顺序存储结构或链式存储结构，都可实现这些操作。
1.1.3 数据类型与抽象数据类型
1.数据类型
类型（type）是具有相同逻辑意义的一组值的集合。数据类型（data type）是指一个类型和定义在这个类型上的操作集合。数据类型定义了数据的性质、取值范围以及对数据所能进行的各种操作。例如，C++语言的整数类型int，除了数值集合[-231, …, -2, -1, 0, 1, 2, …, 231-1]之外，还包括在这个值集上的操作集合[+, -, *, /, %, =]。
程序中的每个数据都属于一种数据类型，决定了数据的类型也就决定了数据的性质以及对数据进行的运算和操作，同时数据也受到类型的保护，确保对数据不能进行非法操作。
高级程序设计语言通常预定义一些基本数据类型和构造数据类型。基本数据类型的值是单个的、不可分解的，它可直接参与该类型所允许的运算。构造数据类型是使用已有的基本数据类型和已定义的构造数据类型按照一定的语法规则组织起来的较复杂的数据类型。构造数据类型的值由若干元素组合而成，这些元素按某种结构组织在一起。
C++语言的基本数据类型有整数类型、浮点数类型、字符类型等，构造数据类型有数组、结构体和文件等。例如，学生数据元素可声明为如下结构体类型，也可声明为类（class）。
struct Student
{
char number[10]; //学号
char name[20]; //姓名
int age; //年龄
};
由若干学生组成的数据序列可声明存储在一个数组（array）中。例如：
Student group[50];
数据类型与数据结构这两个概念的侧重点不同。数据类型研究的是每种数据所具有的特性，以及对这种特性的数据能够进行哪些操作；数据结构研究的是数据元素之间具有的相互关系，与数据元素的数据类型无关，也不随数据元素值的变化而改变。
2.抽象数据类型
抽象数据类型（Abstract Data Type，ADT）是指一个数学模型以及定义在该模型上的一组操作。例如，复数是数学中常用的一种类型，但多数程序设计语言没有提供复数类型。一个复数a+bi由实部a和虚部b两部分组成，i是虚部标记。复数抽象数据类型描述如下：
ADT CompIex //复数抽象数据类型
{
doubIe reaI,im; //复数的实部和虚部
CompIex（reaI,im）; //指定实部和虚部构造一个复数
CompIex add（CompIex c）; //加法，返回当前复数与c相加之后的复数
CompIex sub（CompIex c）; //减法，返回当前复数与c相减之后的复数
};
抽象数据类型和数据类型本质上是一个概念，“抽象”的含义是“定义与实现相分离”，即将一个类型上的数据及操作的逻辑含义与具体实现分离。程序设计语言提供的数据类型是抽象的，仅描述数据的特性和对数据操作的语法规则，并没有说明这些数据类型是如何实现的。程序员按照语言规则使用数据类型，只考虑对数据执行什么操作（做什么），而不必考虑怎样实现这些操作（怎样做）。程序设计语言实现了它预定义数据类型的各种操作。例如，赋值语句的语法定义如下：
变量=表达式
它表示先求得指定表达式的值，再将该值赋给指定变量。程序员需要关注所用数据类型的值能够参加哪些运算、表达式是否合法、表达式类型与变量类型是否赋值相容等；至于如何存储一个整数、变量的存储地址是什么、如何求得表达式值等实现细节则不必关注，这些操作由语言的实现系统完成。
ADT的规范描述包括ADT名称、数据描述和操作描述，操作描述包括操作名、初始条件和操作结果。例如，集合ADT描述如下：
ADT Set
{
数据：集合中有n（n≥0）个数据元素，元素类型为T
操作：
booI isEmpty（ ）; //判断集合是否为空
int Iength（ ）; //返回集合的元素个数
booI contain（T x）; //判断集合是否包含指定元素x
booI add（T x）; //增加指定元素x
booI remove（T x）; //移去首次出现的指定元素x
void cIear（ ）; //清空集合元素
void print（ ）; //输出集合中所有元素
booI equaIs（Set s）; //比较当前集合与集合s是否相等
booI containAII（Set s）; //判断当前集合是否包含集合s中的所有元素
booI addAII（Set s）; //增加集合s中的所有元素，集合并
booI removeAII（Set s）; //移去那些也包含在集合s中的元素，集合差
booI retainAII（Set s）; //仅保留那些也包含在集合s中的元素
}
类似地，可将线性表、栈、队列、串、树、二叉树、图等数据结构分别定义为抽象数据类型，描述相应数据结构的逻辑特性和操作，与该数据结构在计算机内的存储及实现无关。
抽象是研究复杂对象的基本方法，也是一种信息隐蔽技术，从复杂对象中抽象出本质特征，忽略次要细节，使实现细节相对于使用者不可见。抽象层次越高，其软件复用程度也越高。抽象数据类型是实现软件模块化设计思想的重要手段。一个抽象数据类型是描述一种特定功能的基本模块，由各种基本模块可组织和构造起来一个大型软件系统。