2.5 线性表的应用

2.5.1 设计线性表应用程序的一般步骤

当通过分析确定了求解问题中数据逻辑结构为线性关系时，设计线性表应用程序的一般步骤如下：

（1）根据求解功能的特点设计相应的存储结构。

（2）设计相应的基本运算算法。

（3）设计求解问题的主程序。

线性表的主要存储结构如图2.44所示，分为顺序存储结构和链式存储结构两类，每一类又有若干种具体实现方式，这两类存储结构的优缺点如表2.1所示。

在实际求解问题中应根据求解功能的特点来选择合适的存储结构，例如：

（1）若线性表需要频繁查找，很少进行插入和删除操作，宜采用顺序存储结构。

（2）若线性表需要频繁插入和删除操作，宜采用链式存储结构。

（3）当线性表中元素个数变化较大或难以确定时，宜采用链式存储结构。

2.5.2 线性表应用示例

本节通过实现计算两个多项式相加运算的示例介绍线性表的应用。

1．问题描述

假设一个多项式形式为p（x）=c1xe1+c2xex+…+cmxem，其中，ei（1≤i≤m）为整数类型的指数，ci（1≤i≤m）为实数类型的系数。为了简便，假设每个多项式按指数递减排列，并且没有相同指数的多项式项。编写求两个多项式相加的程序。

例如，两个多项式分别为p（x）=3.2x5+2x3—6x+10，q（x）=1.8x5—2.5x4—2x3+x2+ 6x—5，则相加后的结果为r（x）=p（x）+q（x）=5x5—2.5x4+x2+5。

说明：本示例讨论的两个多项式相加运算是一种符号运算，而不是直接求多项式的值，即不是数值运算。

2．设计存储结构

一个多项式由多个cixei（1≤i≤m）多项式项组成，这些多项式项之间构成一种线性关系，所以一个多项式可以看成是由多个多项式项元素构成的线性表。

线性表可以采用顺序表和各种链表存储，由于本例中每个多项式的项数难以确定，所以采用带头结点的单链表存储多项式。也就是说，一个多项式的存储结构对应一个带头结点的单链表，每个多项式项采用以下结点类型进行存储：

其中，coef数据域存放系数ci；exp数据域存放指数ei；next域是一个链域，指向下一个结点。这样的单链表结点的类型声明如下。

例如，前面的两个多项式p（x）、q（x）的存储结构如图2.45所示。

3．设计基本运算算法

在多项式单链表上设计如下基本运算算法。

1）建立多项式单链表

由数组a指定一个多项式的系数，数组b指定指数，共有n个多项式项（a[0]，b[0]），（a[1]，b[1]），…，（a[n—1]，b[n—1]）构成一个多项式（所有的多项式项构成一种线性关系），假设多项式的指数是按递减排列的（如果多项式不按指数递减排列，可以采用单链表排序算法使之这样排列）。采用尾插法建立对应的多项式单链表L的算法如下。

2）销毁多项式单链表

销毁多项式单链表L的算法（与销毁一般单链表的过程相同）如下。

3）输出多项式单链表

输出多项式单链表L的算法如下。

4）两个有序多项式单链表相加运算

对于ha和hb两个有序多项式单链表（按指数递减排列），采用二路归并实现多项式相加运算（产生有序单链表hc）的过程如下。

示意图如图2.46所示。

对应的算法如下。

4．设计主程序

设计主函数调用上述算法实现前面的两个多项式p（x）、q（x）相加功能。其执行过程是，调用CreateListR（）函数两次创建两个多项式单链表Poly1和Poly2，调用DispPoly（）函数两次输出这两个多项单链表，调用Add（Poly1，Poly2，Poly3）函数由Poly1和Poly2相加得到结果多项式单链表Poly3，再调用DispPoly（）函数输出Poly3。最后调用DestroyList（）函数三次销毁所有的三个多项式单链表。对应的主函数如下。

5．程序运行结果

本程序的执行结果如图2.47所示，从中看到上述两个多项式相加的结果为：

5x5—2.5x4+x2+5