案例1：一元多项式的运算
【案例分析】
已知一元多项式可以抽象成一个线性表。在计算机中，我们可以采用数组来表示一元多项式的线性表。
利用数组p表示：数组中每个分量p[i]表示多项式每项的系数pᵢ，数组分量的下标i即对应每项的指数。数组中非零的分量个数即为多项式的项数。
例如，多项式 P(x)= 10+5x-4x²+3x³+2x⁴ 可以用表所示的数组表示。
显然，利用上述方法表示一元多项式，多项式相加的算法很容易实现，只要把两个数组对应的分量项相加就可以了。
案例2：稀疏多项式的运算
【案例分析】
已知稀疏多项式也可以抽象成一个线性表。结合两个有序表的归并方法，可以看出，稀疏多项式的相加过程和归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况(小于等于、大于)，而多项式的相加过程在比较两个多项式指数时要考虑三种情况(等于、小于、大于)。因此，多项式相加的过程可以根据顺序有序表的合并算法和链式有序表的合并算法改进而成。
和顺序存储结构相比，利用链式存储结构更加灵活，更适合表示一般的多项式，合并过程的空间复杂度为O(1)，所以较为常用。
【案例实现】
用链表表示多项式时，每个链表结点存储多项式中的一个非零项，包括系数(coef)和指数(expn)两个数据域以及一个指针域(next)。对应的数据结构定义为：
typedef struct PNode
{
float coef; //系数
int expn; //指数
struct PNode *next; //指针域
}PNode,*Polynomial;
一个多项式可以表示成由这些结点链接起来的单链表，要实现多项式的相加运算，首先需要创建多项式链表。
1、多项式的创建
多项式的创建方法类似于链表的创建方法，区别在于多项式链表是一个有序表，每项的位置要经过比较才能确定。首先初始化一个空链表用来表示多项式，然后逐个输入各项，通过比较，找到第一个大于该输入项指数的项，将输入项插到此项的前面，这样即可保证多项式链表的有序性。
算法1 多项式的创建
【算法步骤】
① 创建一个只有头结点的空链表。
② 根据多项式的项的个数n，循环n次执行以下操作：
- 生成一个新结点*s；
- 输入多项式当前项的系数和指数赋给新结点*s的数据域；
- 设置一前驱指针pre，用于指向待找到的第一个大于输入项指数的结点的前驱， pre初值指向头结点；
- 指针q初始化，指向首元结点；
- 循链向下逐个比较链表中当前结点与输入项指数，找到第一个大于输入项指数的结点*q；
- 将输入项结点*s插入到结点*q之前。
【算法描述】
void CreatePolyn(Polynomial&P, int n)
{ //输入m项的系数和指数，建立表示多项式的有序链表P
P=new PNode;
P->next=NULL; //先建立一个带头结点的单链表
for( i=1;i<=n;++i) //依次输入n个非零项
{
s=new PNode; //生成新结点
cin>>s->coef>>s->expn; //输入系数和指数
pre=P; //pre用于保存q的前驱，初值为头结点
q=P->next; //q初始化，指向首元结点
while(q&&q->expn<s->expn) //通过比较指数找到第一个大于输入项指数的项*q
{
pre=q;
q=q->next;
} //while
s->next=q; //将输入项s插入到q和其前驱结点pre之间
pre->next=s;
} //for
}
【算法分析】
创建一个项数为n的有序多项式链表，需要执行n次循环逐个输入各项，而每次循环又都需要从前向后比较输入项与各项的指数。在最坏情况下，第n次循环需要作n次比较，因此，时复杂度为O(n²)。
2、多项式的相加
创建两个多项式链表后，便可以进行多项式的加法运算了。假设头指针为Pa和Pb的单链表分别为多项式A和B的存储结构，指针p1和p2分别指向A和B中当前进行比较的某个结点，则逐一比较两个结点中的指数项，对于指数相同的项，对应系数相加，若其和不为零，则将插入到“和多项式”链表中去；对于指数不相同的项，则通过比较将指数值较小的项插入到“和多项式”链表中去。
算法2 多项式的相加
【算法步骤】
① 指针pl和p2初始化，分别指向Pa和Pb的首元结点。
② p3指向和多项式的当前结点，初值为Pa的头结点。
③ 当指针p1和p2均未到达相应表尾时，则循环比较p1和p2所指结点对应的指数值(p1->expn与p2->expn),有下列3种情况:
- 当p1->expn等于p2->expn时，则将两个结点中的系数相加，若和不为零，则修改p1所指结点的系数值，同时删除p2所指结点，若和为零，则删除p1和p2所指结点；
- 当p1->expn小于p2->expn时,则应摘取p1所指结点插入到“和多项式”链表中去；
- 当p1->expn大于p2->expn时,则应摘取p2所指结点插入到“和多项式”链表中去。
④ 将非空多项式的剩余段插入到p3所指结点之后。
⑤ 释放Pb的头结点。
【算法描述】
void AddPolyn(Polynomial&Pa, Polynomial&Pb)
{ //多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”
p1=Pa->next;p2=Pb->next; //p1和p2初值分别指向Pa和Pb的首元结点
p3=Pa; //p3指向和多项式的当前结点，初值为Pa
while(pl&&p2) //p1和p2均非空
{
if(p1->expn==p2->expn) //指数相等
{
sum=p1->coef+p2->coef; //sum保存两项的系数和
if(sum!=0) //系数和不为0
{
p1->coef=sum; //修改Pa当前结点的系数值为两项系数的和
p3->next=p1;p3=p1; //将修改后的Pa当前结点链在p3之后，p3指向p1
p1=p1->next; //p1指向后一项
r=p2;p2=p2->next;delete r; //删除Pb当前结点,p2指向后一项
}
else //系数和为0
{
r=p1;p1=p1->next;delete r; //删除Pa当前结点,p1指向后一项
r=p2;p2=p2->next;delete r; //删除Pb当前结点,p2指向后一项
}
}
else if(p1->expn<p2->expn) //Pa当前结点的指数值小
{
p3->next=p1; //将p1链在p3之后
p3=p1; //p3指向p1
p1=p1->next; //p1指向后一项
}
else //Pb当前结点的指数值小
{
p3->next=p2; //将p2链在p3之后
p3=p2; //p3指向p2
p2=p2->next; //p2指向后一项
}
} //while
p3->next=p1?p1:p2; //插入非空多项式的剩余段
delete Pb; //释放Pb的头结点
}
【算法分析】
假设两个多项式的项数分别为m和n,则同算法2.17一样,该算法的时间复杂度为O(m+n)，空间复杂度为O(1)。
对于两个一元多项式减法和乘法的运算，都可以利用多项式加法的算法来实现。减法运算比较简单,只需要先对要减的多项式的每项系数进行取反,然后再调用加法运算AddPolyn即可。多项式的乘法运算可以分解为一系列的加法运算。假设A(x)和B(x)为式(2-1)的多项式，则
其中，每一项都是一个一元多项式。
多项式相加的例子说明，对于一些有规律的数学运算，借助链表实现是一种解决问题的途径。
案例3 图书信息管理系统
【案例分析】
把图书表抽象成一个线性表,每本图书(包括ISBN、书名、定价)作为线性表中的一个元素。在图书信息管理系统中要求实现查找、插入、删除、修改、排序和计数总计6个功能,具体分析如下
(1)对于查找、插入、删除这3个功能的算法,本章已分别给出了线性表利用顺序存储结构和链式存储结构表示时相应的算法描述。
(2)对于修改功能,可以通过调用查找算法,找到满足条件的图书进行修改即可。
(3)对于排序功能,如果在没有时间复杂度限制的情况下,可以采用读者熟悉的冒泡排序来完成；如果图书数目较多，对排序算法的时间效率要求较高，在学完第8章的内部排序算法后可以选取一种较高效的排序算法来实现，例如，快速排序。
(4)对于计数功能，如果采取顺序存储结构，线性表的长度是它的属性，可以直接通过x₂回length的值实现图书个数的统计功能，时间复杂度是O(1)；如果采取链式存储结构，则需要通过从首元结点开始，附设一个计数器进行计数，一直“数”到最后一个结点，时间复杂度是O(n)。
在实现图书信息管理系统时，具体采取哪种存储结构，可以根据实际情况而定。如果图书数据较多，需要频繁地进行插入和删除操作，则宜采取链表表示；反之，如果图书数据个数变化不大，很少进行插入和删除操作，则宜采取顺序表表示。
此案例中所涉及的算法比较基础，但非常重要，可以分别采用顺序表和链表实现此案例的相应功能。
标签：p2,结点,p1,多项式,next,链表,案例,数据结构 From： https://www.cnblogs.com/Santariki/p/16814651.html