Page 59 - 高中 信息技术 选择性必修1 数据与数据结构

第二章 数据的存储方式  2.4 数组与链表及其应用

1．针对信息化管理中的各个不同功能，分别适合使用数组还是链表来存储与组织
数据？
2．如何通过定义数组和链表，以及实施相应操作，实现信息化管理中的各个功能？

3．进一步对比分析使用数组和使用链表在现实数据的存储与组织上的异同。

2.4 数组与链表及其应用

广东教育出版社

从超市商品管理系统的设计与实现中，我们看到，数组和链表都可以实现对数据的存
储和组织，进而都可以实现对商品信息的增、删、查、改等操作。那么，这两种数据结构

在实际应用时有什么区别？针对什么样的情况应该采用什么样的数据结构才能实现更有
效、更科学的信息管理？下面让我们一起来分析。

2.4.1 数组与链表

在逻辑上具有简单的线性关系的数据，其数据元素中除了第一个和最后一个，其他数

据元素都是首尾相接的。然而逻辑上线性排列的数据，在物理存储上却可以有两种不同的
形式，即采用顺序的存储结构或链式的存储结构。根据存储结构的不同，对数据组织与管
理的方式也不同，分别可以通过数组和链表来实现。

在数组中，元素之间的逻辑关系是通过数组的下标来表示的，如某个元素在数组中
下标为i的位置，则该元素的前驱在数组中下标为i-1的位置，后继在数组中下标为i+1的位
置。由于每个元素在物理存储器中是连续存放的，且占用内存空间大小相同，因此可以通
过下标快速、简便地访问数组中的任何元素。然而数组元素的访问虽然很方便，但若要在

数组中插入一个元素，则需要将待插入位置的元素及其后所有元素往后移动；同样地，如
果想删除一个元素，也需要将待删除元素之后的所有元素往前移动。因此，当数组元素较

多且需要频繁进行插入、删除操作时，显得相当不便。另一方面，定义一个数组，其实就
是在内存中开辟一段大小固定且连续的存储空间，因此需要事先知道所需数组元素的个
数。为防止定义的数组长度不足导致无法存储过多的数据，在不确定数据量多少的情况
下，一般会定义长度足够大的数组，这在遇到实际存储的数据较少时无疑会造成内存空间

的浪费。
在链表中，结点之间是通过结点中的指针联系到一起的，指针将多块不连续的内存空
间连接，在逻辑上形成一片连续的数据存储空间。由于每个结点的物理存储位置保存在它

前驱的指针域中，只有当访问到其前驱后才能通过前驱的指针访问到该结点。因此，要访

51 51

21X2204.indd 51 2019/9/26 13:53:09