1.1 数据结构的基本概念
1.1.1 数据、数据元素、数据元素的数据类型
数据是人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。
例如，“今天天气情况是，最高温度为5℃，最低温度为-5℃”，就是关于今天天气情况的描述数据。又如，“班上甲同学姓名叫张三，乙同学姓名叫李四”，就是关于班上同学姓名的描述数据。
表示一个事物的一组数据称作一个数据元素。构成数据元素的数据称作该数据元素的数据项。
例如，要描述学生信息，可包括学生的学号、姓名、性别、年龄等数据。学生的学号、姓名、性别、年龄等数据就构成学生情况描述的数据项；包括学号、姓名、性别、年龄等数据项的一组数据就构成学生信息的一个数据元素。表1-1是一个包含3个数据元素的学生信息表。
表1-1 学生信息表
在讨论数据结构时，关于数据元素、数据项的描述都使用某种高级程序设计语言来描述，本书采用C语言描述。学生信息的数据元素是由多个数据项构成的，其数据元素的数据类型的C语言描述方法定义为如下结构体：
struct Student
{
long number;
char name[10];
char sex[3];
int age;
};
通过上述定义，用户自定义的结构体struct Student就可像C语言中基本数据类型char、int、float一样使用。
为使用简便起见，还可以把上述定义改写为：
typedef struct Student
{
long number;
char name[10];
char sex[3];
int age;
} StudentType;
经过上述定义后，StudentType就被看作和struct Student含义相同的标识符。
上述学生情况数据元素的数据类型定义为StudentType，这与把数据元素定义为int、float、long、char等数据类型一样，都是给出了具体数据元素的数据类型。
但是，像数学一样，数据结构课程讨论的大部分算法都可以适用于任何数据类型的数据元素。这时，为了考虑算法的通用性，算法要处理的数据元素也可以是不具有实际含义的数据元素。我们把没有实际含义的数据元素称作抽象数据元素。在本书中，抽象数据元素用a0, a1, …, an-1表示。
在设计算法时，任何数据元素都要指定数据类型，抽象数据元素也不例外。本书用符号DataType表示抽象数据元素的数据类型。当软件设计问题具体确定时，抽象数据元素的数据类型将被具体数据元素的数据类型取代。例如，若线性表的数据元素类型为DataType，当设计的具体线性表的数据元素类型为int时，可通过预先定义DataType为int来完成程序的设计；当设计的具体线性表的数据元素集合为表1-1中的学生信息时，可通过定义DataType为StudentType来完成程序的设计。具体的C语言语句为：
typedef int DataType;
或
typedef StudentType DataType;
1.1.2 数据的逻辑结构
数据元素之间的相互联系方式称为数据的逻辑结构。
按照数据元素之间的相互联系方式，数据的逻辑结构主要可分为线性结构、树型结构和图型结构三种。
线性结构的定义是：除第一个和最后一个数据元素外，每个数据元素只有一个唯一的前驱数据元素和一个唯一的后继数据元素。线性结构可以表示为图1-1（a）所示的形式，图中，A、B、C、D为数据元素，A是第一个数据元素，D是最后一个数据元素，A是B的前驱数据元素，C是B的后继数据元素；依次类推。
图1-1 基本的数据逻辑结构
树型结构的定义是：除根结点外，每个数据元素只有一个唯一的前驱数据元素，可有零个或若干个后继数据元素。图1-1（b）是一个树型结构的例子。对于数据元素A、B、C、D、E、F、G，数据元素A是根结点，A没有前驱数据元素，有两个后继数据元素B和C；数据元素B的前驱数据元素为A，后继数据元素为D和E；数据元素C的前驱数据元素为A，没有后继数据元素；如此等等。
图型结构的定义是：每个数据元素可有零个或若干个前驱数据元素和零个或若干个后继数据元素。图1-1（c）是一个图型结构的例子。对于数据元素A、B、C、D、E、F、G，若以A为起始点，则数据元素E有两个前驱数据元素B和C，有两个后继数据元素F和G。
树型结构和图型结构也可以归为非线性结构。数据元素之间不存在如图1-1（a）所示的一对一关系的结构都称作非线性结构。
1.1.3 数据的存储结构
任何需要计算机进行管理和处理的数据元素都必须首先按某种方式存储在计算机中。数据元素在计算机中的存储方式称为数据的存储结构。数据存储结构的基本形式有两种：一种是顺序存储结构，另一种是链式存储结构。
顺序存储结构是指把数据元素存储在一块连续地址空间的内存中，其特点是，逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素的存储位置关系上。当采用高级程序设计语言表示时，实现顺序存储结构的方法是使用数组。图1-2（a）所示为线性结构数据元素a0, a1, …, an-1的顺序存储结构示意图。其中，0, 1, 2, …, n-2, n-1既是数据元素的编号，也是存储数据元素a0, a1, …, an-1的数组下标。
图1-2 基本的存储结构
指针是指向物理存储单元地址的变量。我们把由数据元素域和指针域组成的一个结构体称为一个结点。链式存储结构是使用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）链接起来，其特点是，逻辑上相邻的数据元素在物理上（即内存存储位置上）不一定相邻，数据间的逻辑关系表现在结点的链接关系上。图1-2（b）所示为线性结构数据元素a0, a1, …, an-1的链式存储结构示意图。其中，上一个结点到下一个结点的箭头表示上一个结点的指针域中保存的下一个结点在内存中的存储地址。head是指向第一个结点的指针，通常称作头指针。
顺序存储结构和链式存储结构是两种最基本、最常用的存储结构。除此之外，利用顺序存储结构和链式存储结构进行组合，还可以有一些更复杂的存储结构。
1.1.4 数据的操作
一种数据类型数据允许进行的某种操作称作数据的操作，一种数据类型数据所有的操作称作数据的操作集合。
数据结构课程在讨论数据的操作时，一般从抽象和具体两个角度进行讨论。在抽象角度下，数据的操作主要讨论数据操作所完成的逻辑功能。在抽象角度下，数据的操作一般与数据的逻辑结构一起讨论；在具体角度下，数据的操作主要讨论数据操作的具体实现算法。例如，若某软件要对表1-1中的学生信息进行处理，对学生信息可能进行的操作有：插入一条数据元素，删除一条数据元素，列出所有数据元素的值等。所以，该问题数据的操作有：插入一条数据元素，删除一条数据元素，列出所有数据元素的值等。在其抽象角度下，这些操作的逻辑功能如其字面含义所述；在具体角度下，表1-1的学生信息既可采用图1-2（a）的顺序存储结构存储数据元素，也可采用图1-2（b）的链式存储结构存储数据元素，不同的存储结构操作实现的具体算法将不同。
1.1.5 数据结构课程讨论的主要内容
数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构，在讨论这些典型的常用数据结构时，主要从它们的逻辑结构、存储结构和数据操作3个方面进行分析讨论。例如，我们在第2章中讨论线性表时，2.1节将讨论线性表的抽象数据类型（即线性表的逻辑结构和逻辑结构意义下的操作功能），2.2节将讨论线性表的顺序存储结构和顺序存储结构下各基本操作的具体实现算法，2.3节将讨论线性表的链式存储结构和链式存储结构下各基本操作的具体实现算法。其他各章中对堆栈、队列、串、数组、树、二叉树、图等进行讨论的章节安排次序与第2章的类同。