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

第二章 数据的存储方式  2.3 数据的链式存储与组织

如图2-11所示是单向链表的几种基本操作示意图。

（a）空链表
（b）插入结点

广东教育出版社

（c）删除结点
图2-11 单向链表的基本操作示意图

由于链表可以实现灵活的内存动态管理，因此在数据的组织上有许多应用，如操作系
统软件的实现中，大量使用各种链表存储系统信息，包括设备列表、内存分配信息、进程
信息等。在很多应用软件中也会使用链表存储和处理数据，例如地图导航软件、网络数据

包的记录等。
利用一维数组存储一元多项式时，数组的下标与项的指数对应，数组元素保存该项的
100
3
系数，这样存储简单明了。但是对于类似这样的多项式：3x +5x -2x+10，最少需要具有
101个元素的数组来保存，其中绝大部分的元素为零，不仅浪费空间，而且在进行多项式
运算时，其执行效率也不高。如果采用链表来存储这样的多项式，则方便多了。用链表存
储多项式，链表的每个结点对应一个项，只需要存储系数不为0的项，但如果采用这种方
3
100
式，就不仅要存储项的系数，还要存储项的指数。以多项式3x +5x -2x+10为例，下面的
代码定义了多项式的链表结构：
//存储多项式项的结点定义
struct term{

float exponent; //项的指数
float coefficient; //项的系数
term *next; //下一结点

};
typedef term *polynomial; //定义多项式类型名称
基于上面的结构类型定义，我们可以定义一个向多项式添加项的函数，其代码如下：
//该函数向多项式中增加项（添加到最后）

void add_term(polynomial p,float exponent,float coefficient)
{
term *q,*t;

49 49

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