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

1.3 认识数据结构
 1.3 认识数据结构

分 析

数据结构在解决问题的过程中有重要作用。例如本节开头的商品查询问题，与此相似

的还有电话查询、图书查询、人员查询等，此类问题的共同点是从大量的数据中查找目标
数据。如电话查询，从表1-6的通信录中查找到对应的姓名，获得其电话号码。

表1-6 通信录

姓名 号码
张达 13712345678
广东教育出版社
熊二 13523456789

李三 13012345678
… …

用计算机解决此问题，首先要对数据进行组织，设计数据结构。
最简单的方法就是将生活中的通信录直接转化存储，构造一张号码表，表中每个数据
元素包含两个数据项：姓名和号码。将表中的数据元素顺序存储在计算机中，查找时从头

开始依次查对姓名，直到找到目标或找完整张表为止。
当数据量大的时候，这种方法就不实用了。要提高查找速度，就要改进数据表的结构
和存储方式。可通过以下方法改进数据结构的设计：
（1）号码表中的数据元素按姓氏排列。

（2）设计一张姓氏索引表，采用如图1-19所示的存储结构。

地址 姓名 号码
0000 李三 13012345678

0006 李四 13023456789
姓氏 号码 … … …
李 0000 4206 熊二 13523456789
… … 4212 熊三 13523456789

熊 4206 … … …
… … 9700 张达 13712345678
张 9700 9706 张二 18923456789

… … … … …
（a）索引表 （b）有序的号码表

图1-19 带索引的号码表

23
23

21X2204.indd 23 2019/9/26 13:53:00