1.1 数据结构的基本概念

本节主要介绍数据结构有关的一些基本知识和概念。

1.数据

数据（Data）是能被计算机识别并能输入计算机中被处理的符号集合。换言之，数据就是计算机化的信息。

数据的概念经历了与计算机发展相类似的发展过程。计算机一问世，数据作为程序的处理对象随之产生。早期的计算机主要应用于数值计算，数据量小且结构简单，数据只包括整型、实型和布尔型，仅能用于算术运算与逻辑运算。那时的程序设计人员把主要精力放在程序设计的技巧上，并不重视计算机中数据的组织。

随着计算机软件、硬件的发展与应用领域的不断扩大，计算机应用领域也发生了战略性转移，非数值运算处理所占的比例越来越大，现在几乎达到90%以上，数据的概念被大大推广了。数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值数据。多种信息通过编码被归到数据的范畴，大量复杂的非数值数据需要处理，数据的组织显得越来越重要。例如，王鹏的身高是172cm，王鹏是对一个人姓名的描述数据，172cm是关于身高的描述数据；一张照片是图像数据，一部电影是视频数据。

2.数据元素

数据元素（Data Element）是组成数据的有一定意义的基本单位，在计算机中通常作为整体考虑和处理。例如，一个数据元素可以由若干个数据项组成，数据项是数据不可分割的最小单位。在如表1.1所示的教职工基本情况表中，数据元素包括工号、姓名、性别、所在院系、出生日期、职称等数据项。这里的数据元素也称为记录。

3.数据对象

数据对象（Data Object）是具有相同性质的数据元素的集合，是数据的一个子集。例如，集合{1,2,3,4,5,…}是自然数的数据对象，{‘A’，‘B’，‘C’，…，‘Z’}是英文字母表的数据对象。可以看出，数据对象可以是有限的，也可以是无限的。

4.数据结构

数据结构（Data Structure）是指相互之间存在的一种或多种特定关系的数据元素集合，是带有结构的数据元素结合，它是指数据的组织形式。计算机所处理的数据并不是孤立的、杂乱无序的，而是具有一定联系的数据集合，如表结构（表1.1所示的教职工基本情况表）、树形结构（如图1.1所示的学校组织结构图）、图结构（如图1.2所示的城市之间的交通路线图）。

5.数据类型

数据类型（Data Type）是用来刻画一组性质相同的数据及其上的操作的总称。数据类型中定义了两个集合：数据类型的取值范围和该类型中可允许的一组运算。例如，高级语言中的数据类型就是已经实现了的数据实例。在高级语言中，整型类型可能的取值范围是-32768～32767，允许的运算集合是加、减、乘、除、取模。字符类型对应的ASCII码取值范围是0～255，可进行赋值运算、比较运算等。

在高级语言中，按照取值的不同，数据类型还可以分为两类：原子类型和结构类型。原子类型是不可以再分解的基本类型，如在C语言中，标准类型包括整型、实型、字符型。结构类型是可以再分解的，由若干个类型组合而成。例如：

其中，STUDENT为结构体类型名，stu是结构体类型变量，p为指向结构体类型STUDENT的指针变量。