Page 40 - 高中 信息技术 选择性必修1 数据与数据结构
P. 40
第二章 数据的存储方式 2.1 数据存储的顺序结构与链式结构
2 . 1 . 2 数据存储的链式结构
数据的链式结构与顺序结构不同，它的特点是存储各个数据元素的计算机存储单元的
地址不一定是连续的。因此，为了表示每个数据元素a 与其后继数据元素a 之间的逻辑关
i+1
i
系，对于数据元素a 来说，除了存储其本身的信息，还需要存储其后继数据元素的存储位
i
置信息。比如，人们到银行、医院办理业务时，一般都是在叫号系统取号之后就在大厅中
静坐等候。此时的人们看似无序，但叫号系统为每个人分配的号码无形中把等候的人们串
成了一条链子。
当以链式结构存储数据时，一种最简单也最常用的方法是分别用两个域存储数据元素
的两部分信息：数据域存储数据元素自身信息，指针域存储后继数据元素的存储位置。
以表2-2所示的数据表为例，若将其进行链式存储，则计算机将分配若干不连续的存储单
元，其结构如图2-4所示。
在如图2-4所示的链式结构中，超市某年1月的奶粉销售信息存储在地址为0x401400的
存储单元中，其数据域为550，指针域指向2月的奶粉销售信息所在的存储位置0x401408，
而存储12月奶粉销售信息的存储单元，其指针域为NIL，表示空。
还有一些更复杂的链式结构，如将最后一个元素的指针域指向第一个数据元素，或者
每个数据元素不仅包含数据元素自身信息、后继数据元素的存储位置，还包含其前驱数据
元素的存储位置等。 广东教育出版社
图2-4 链式结构示意图
32 32
21X2204.indd 32 2019/9/26 13:53:06
