1.2.1 数据结构

数据结构是程序存储、组织数据的方式。一个数据结构是由程序中的数据元素按照某种逻辑关系组织起来的，是若干个数据元素的组合。数据结构描述了数据元素之间的逻辑关系，数据必须存储在内存中，数据在内存中的存储结构是数据结构的实现形式，是数据结构在内存中的物理表示。

数据结构是程序中处理数据的基本单位，在程序中作为一个整体来使用。有如下所示的三类数据结构。

· 第一类是不可分割的单个数据。例如：整数“12”、字符“C”等。

· 第二类由多个数据构成。例如：“2008年3月21日12时12分12秒”，该数据结构描述了一个具体的时刻，它由6个部分组成，分别为年、月、日、时、分和秒。

· 第三类由多个第一类数据和第二类数据组成。例如，一个人的信息也可以是一个数据结构，内容如下：

        {
            张三                                 /* 姓名 */
            男                                   /* 性别 */
            1980年12月12日                        /* 生日 */
            北京邮电大学                           /* 毕业学校 */
        }

该数据结构由姓名、性别、生日和毕业学校4部分组成，其中，生日属于第二类数据结构，即由多个数据组成的数据结构。

在许多类型的程序设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重依赖于是否选择了最优的数据结构。合理选择和精心设计的数据结构可以有效地提高程序的运行效率，同时，还能节约存储空间的使用。下面讨论如何以数组结构和链表结构来处理学生信息，通过这两种数据结构的优劣性比较，来体现数据结构选择的重要性。

数组是一种可以存放数据的容器，其数据在内存中连续存放；访问数组元素时，可以直接使用数组名加下标的方式。例如，要处理一个有42个学生的班级的学生信息，将其存储在数组中，其内存组织形式如图1-2所示。其中，数组序号从0开始排，即序号为n的元素实际为n+1个学生。

将该数组数据结构名命名为stuArray，它一般包含数组第一个元素的地址信息，因为数组是连续存放的，因此，只要把第一个元素地址加上N，即可得到第N+1元素的地址。若要访问第三个学生王五的信息，只需使用stuArray[2]（等效于stuArray+2，把第一个元素的地址加上2）即可。类似地，要访问数组序号为n的学生信息，只需使用stuArray[n]即可，只需要一步操作。

链表也是一种可以存放数据的容器，但是其数据在内存中是分散存放的。链表中的相邻元素间存在一些关系，这种关系有很多种形式，最典型的一种是每个链表元素都包含下一个元素的地址信息，通过该元素的信息就可以查找到下一个元素。同样，如果把上面所说的班级学生的信息存储在链表中，其内存的组织形式如图1-3所示。

图1-2 数组的存储形式

图1-3 链表的存储形式

将该链表数据结构命名为stuLink，一个链表的已知信息只有链表头的地址。如果要在该链表中访问第三个学生王五的信息，需要先访问第一个学生张三的信息，从中获得第二个学生李四的地址信息，然后才能访问李四的内存，再从中得到第三个学生王五的地址信息，之后才能访问王五的内存。也就是说，在数组中访问一个元素，必须得先按顺序从第一个元素往后依次访问，直至得到要访问的元素。

由此可以知道，访问数组的效率远远高于访问链表。因此，如果程序的任务需要频繁地访问容器中的元素时，比如，一个用于查询学生数据的学生系统，需要频繁地读取数据，这时，应该选择数组来存储学生信息，其运行效率要远远快于使用链表结构。

但是，数组增删元素时的效率远远不如链表。例如，李四同学由于过度沉迷C语言而旷课过多，被学校勒令退学。因此，班级信息中要删除李四的资料。如果使用数组stuArray存储学生信息的话，删除操作必须先删除stuArray[1]，再将其后面的stuArray[2]到stuArray[41]都向前移一个位置，这样共需要41步操作。删除后，stuArray的内存组织形式如图1-4所示。

如果使用链表stuLink存储学生信息的话，操作就相对简单。首先，删除李四的信息；同时，只要修改李四前面的学生张三的相邻元素信息即可。在删除李四前，张三中保存的下一个元素的地址是李四的地址；删除时，将其修改为王五的地址。整个过程总共只需要两步操作。删除李四的信息后，stuLink的内存组织形式如图1-5所示。

图1-4 删除李四后stuArray的内存组织形式

图1-5 删除李四后stuLink的内存组织形式

使用数组和链表处理信息还有其他方面的不同，在此不多做比较。