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

 5.2 查找

解决同一个问题，我们可以用不同的算法编写程序，不同的算法对数据结构的要求可

能是不同的。对比顺序查找与二分查找算法，当数据量较大时，二分查找会比顺序查找快
很多，这是它的主要优点，但它要求查找表是有序的，所以在进行二分查找之前，必须先
对查找表进行排序。另外，二分查找要求表是顺序存储的，为保持表的有序性，在进行插

入、删除操作时，都必须移动大量记录。因此，二分查找的高查找效率是以排序为代价

的，所以它特别适合一经建立就很少移动而且经常需要查找的线性表。
了解不同算法的特点，可以帮助我们在解决实际问题时，从不同的算法中选择出较为
合适的一种，或对现有算法进行改进或创新，从而设计出更好的算法。

讨 论

理解顺序查找和二分查找的思想和算法实现过程，分析二分查找中的迭代过程是如何
进行的。体验顺序查找、二分查找两种实现方法在不同数据量上运行速度的差异。数据量

要多大，才有明显差异呢？

分 析 广东教育出版社

在编写“超市促销商品的选择与查询程序设计”程序之前，首先要抽取促销商品的相
关数据，列出促销商品共有的属性，如编号、名称、数量、价格、存放位置、销量、销售

额等，根据本次促销活动的原则，选择与问题相关的属性，并用数据来表示这些属性；然
后分析提取出来的各属性之间的关系，确定它们之间的数据关系，进而建立数据模型。

根据促销商品数据模型的逻辑关系，选择一维数组来组织、存储促销商品的数据，并
定义如下的数据结构：

struct ShangPinType //定义查找所用到的数据结构
{
int BianHao //数据项商品编号的类型为整型

int Where //数据项商品存放货架的类型为整型
int Count //数据项剩余商品数量的类型为整型
};

根据上面的数据结构，设计查询促销商品信息的算法：输入需查询商品的编号，然后
在数组中查找该编号，若查找到此编号就输出该商品的信息。数据量小时可以用顺序查找

算法；数据量比较大时，顺序查找花费时间较多，应该选用查找速度更快的二分查找。完
整程序请参阅教科书配套学习资源包。

119119

21X2204.indd 119 2019/9/26 13:53:39