Page 61 - 高中 信息技术 选择性必修1 数据与数据结构
P. 61
第二章 数据的存储方式 2.4 数组与链表及其应用
以超市商品信息管理系统为例：对于商品信息的存储与组织，我们既可以使用数组实
现，也可以使用链表实现。但为了降低复杂性、提高效率，我们对商品种类通常相对固
定、以查询操作居多的商品基本信息管理采用数组来实现，而对于每日商品频繁进货与售
出，因而需频繁进行商品进出信息添加（也可能因误操作需要删除）的进货与销售管理，
则采用链表来实现。
观 察
我们已经先后通过一维数组和链表实现了对一元多项式的存储，在此基础上，还可以
实现多项式的加法运算。打开配套学习资源包中的文档“第二章\课本素材\多项式的加法
广东教育出版社
运算.docx”，观察其中程序，程序中分别用一维数组和链表存储两个多项式，并完成这两
个多项式的加法运算，请同学们分析一下它们各有什么特点。
待处理的多项式为：
3
7
4
多项式1：72x +33x -18x +1
6
4
多项式2：36x -48x +22x-8
使用一维数组实现一元多项式加法运算：
假设多项式的最高指数为n，则一维数组会存储指数从0到n的每一个项的系数（如果
对应项没有，则系数为0），这样在做加法时就非常简单了，只要把相同下标的数组元素
相加就能得到对应的多项式加法结果。
使用链表实现一元多项式加法运算：
用链表存储一元多项式与一维数组不同，只需要存储系数不为0的项，如果我们保存
多项式时能够按照指数从高到低保存各个项，则加法运算可以描述为：
（1）取两个多项式p1、p2的第一项进行比较。
（2）如果两者的指数相同，则将系数相加作为结果项的系数，两者均取下一项继续
比较。
（3）如果p1的当前项指数>p2的当前项指数，则结果包含p1当前项，p1取下一项与p2
的当前项继续比较。
（4）如果p1的当前项指数<p2的当前项指数，则结果包含p2当前项，p2取下一项与p1
的当前项继续比较。
（5）重复以上步骤直至有一个链表处理完。
（6）将未处理完链表的剩余项包含到结果中。
实 践
根据表2-3的“超市商品管理系统功能分析”，结合本节所学知识，对管理系统中使
用的数据结构再次进行整体分析，对比、选择最佳策略，实现完整的系统功能。最后形成
的超市商品管理系统运行界面如图2-12所示。
53 53
21X2204.indd 53 2019/9/26 13:53:09
