多项式链表的结构和接口均参考严蔚敏老师的（c语言版）《数据结构》。
加法的实现：
假设指针pa，pb分别指向多项式A和B当前进行比较的某个结点，则比较这两个结点的指数项，有下列三种情况：
指针pa所指结点的指数值 < 指针pb所指结点的指数值：则应摘取pa指针所指结点插入到“和多项式”链表中去 指针pa所指结点的指数值 < 指针pb所指结点的指数值：则应摘取pb指针所指结点插入到“和多项式“链表中去 指针pa所指结点的指数值 = 指针pb所指结点的指数值：则两个结点中的系数相加，若和数部位零，pa所指结点的系数值，同时释放pb所指的结点；反之，从多项式链表中删除相应的结点，同时释放pa和pb所指向的结点。
减法的实现：
简单的思路：先把减数多项式的系数一一取相反数，然后调用加法函数即可实现。
乘法的实现：
M (
x
) ＝ A(
x
) x B(
x
)
＝ Ａ(
x
) x [
b1xe1+b2xe2＋...+bnxen
]
=
∑ni=1biA(x)xei
所以，乘法也可以转换成加法实现。
对于链表的操作有几点需要牢记：
需要对链表进行有效性判断
对于链表的操作过程中，首先要创建一个节点，并将头结点复制给新节点
如果要构建新的链表是，表头需要单独保存；同时每个节点需要创建新节点，完成赋值、指针操作；组后需要一个游标节点，负责将各个节点串联起来。 对于尾节点，最后一定要将其next指向NULL。 若在对链表操作时不想改变链表的值，则需要使用malloc函数重新定义一个链表，并把 原链表的内容赋给新链表。此时切记，不要把原链表的指针赋给新生成的结点，否则，在使用的过程中依旧会改变原链表，这是因为指针的特性。
c语言代码实现
/* 接口声明和数据结构声明头文件 */
/* 项的表示
* 多项式的项作为单链表的数据元素
*/
typedef struct{
/* 系数 */
int coef;
/* 指数 */
int expn;
}datatype;
/* 线性单链表的存储结构 */
typedef struct l_node{
/* 数据域表示多项式的项 */
datatype data;
/* 指针域 */
struct l_node *next;
}l_node,*link_list;
/* 用带头结点的有序链表表示多项式 */
typedef link_list polynomial;
#define true 1
#define false 0
/* 定义ccompare函数的返回值 */
#define a_e_b 0 //a = b
#define a_g_b 1 //a > b
#define a_s_b -1 //a < b
/* 定义polyn_locate函数的返回值 */
#define prior -1 //要找元素值不存在且小于链表中的某些结点
#define curor 0 //要找元素存在
#define nextor 1 //要找元素值不存在且大于链表中的结点
/* -------------------基本操作的函数原型说明------------------- */
/* 比较两个类型为datatype的变量
* 若a = b,返回a_e_b
* 若a > b,返回a_g_b
* 若a < b,返回a_s_b
*/
int compare(datatype a, datatype b);
/* 定义polyn_locate函数的返回类型 */
typedef struct{
/* 指向某结点的指针 */
polynomial p;
/* 类型 */
int type;
}locate;
/* 若有序链表中HEAD中存在与e满足判定函数compare()取值为a_e_b的元素
则p为指向HEAD中第一个值为e的结点的指针,并返回curor
*若有序链表中HEAD中存在与e满足判定函数compare()取值为a_g_b的元素
则p为指向HEAD中最后一个结点的指针,并返回nextor
*若有序链表中HEAD中存在与e满足判定函数compare()取值为a_s_b的元素
则p为指向HEAD中第一个大于e的结点的指针,并返回prior
*/
locate polyn_locate(polynomial HEAD, datatype e, int(*compare)(datatype, datatype));
/* 按有序判定函数compare()的约定,将值为e的结点插入到有序链表的适当位置
*/
void polyn_order_insert(polynomial HEAD, datatype e, int(*compare)(datatype, datatype));
/* 输入m项的系数和指数,建立表示一元多项式的有序链表
* HEAD为链表的头指针
*/
void polyn_create(polynomial HEAD);
/* 销毁一元多项式 */
void polyn_destroy(polynomial HEAD);
/* 打印输出一个一元多项式 */
void polyn_print(polynomial HEAD);
/* 返回一元多项式的项数 */
int polyn_length(polynomial HEAD);
/* 完成多项式的相加
* pa = pa + pb
* 然后销毁一元多项式pb
*/
polynomial polyn_add(polynomial pa, polynomial pb);
/* 完成多项式的相减
* pa = pa -pb
* 并销毁一元多项式pb
*/
polynomial polyn_subtract(polynomial pa, polynomial pb);
/* 完成多项式的相乘
* pa = pa * pb
* 并销毁一元多项式pb
*/
polynomial polyn_multiply(polynomial pa, polynomial pb);
/* 复制一个单链表 */
polynomial polyn_clone(polynomial HEAD);
/* 接口的实现文件 */
#include
#include
#include"polynomial.h" int compare(datatype a, datatype b) { if(a.expn == b.expn) return a_e_b; if(a.expn > b.expn) return a_g_b; if(a.expn < b.expn) return a_s_b; } void polyn_print(polynomial HEAD) { /* p指向第一个结点 */ polynomial p = HEAD -> next; if(!p) printf("此链表为空\n"); else { while(p -> next) { if (p -> next -> data.coef >= 0) printf("%dx^%d + ",p -> data.coef,p -> data.expn); else printf("%dx^%d ",p -> data.coef,p -> data.expn); p = p -> next; } printf("%dx^%d\n",p -> data.coef,p -> data.expn); } } locate polyn_locate(polynomial HEAD, datatype e, int(*compare)(datatype, datatype)) { /* 初始化ptr指向头指针 */ locate ptr; ptr.p = HEAD; while((ptr.p) -> next) { if(compare( (ptr.p -> next -> data), e) == a_e_b) { ptr.p = ptr.p -> next; ptr.type = curor; return ptr; } if(compare( ptr.p -> next -> data, e) == a_g_b) { ptr.type = prior; return ptr; } if(compare( ptr.p -> next -> data, e) == a_s_b) { ptr.p = ptr.p -> next; } } ptr.type = nextor; return ptr; } void polyn_order_insert(polynomial HEAD, datatype e, int(*compare)(datatype, datatype)) { locate ptr = polyn_locate(HEAD, e, compare); if (ptr.type == nextor) { /* 新建结点 */ polynomial new_node = (polynomial)malloc(sizeof(l_node)); new_node -> data = e; /* 修改指针域 */ ptr.p -> next = new_node; new_node -> next = NULL; } if (ptr.type == prior) { /* 新建结点 */ polynomial new_node = (polynomial)malloc(sizeof(l_node)); new_node -> data = e; /* 修改指针域 */ new_node -> next = ptr.p -> next; ptr.p -> next = new_node; } /* 若该项已存在 */ if (ptr.type == curor) { (ptr.p -> data).coef += e.coef; } } void polyn_create(polynomial HEAD) { /* 初始化头指针 */ HEAD -> next = NULL; datatype temp; scanf("%d %d",&(temp.coef), &(temp.expn)); /* 系数为零,指数为任意值时退出 */ while(temp.coef != 0) { /* 建立新结点 */ polyn_order_insert(HEAD, temp, compare); scanf("%d %d",&(temp.coef), &(temp.expn)); } } void polyn_destroy(polynomial HEAD) { while(HEAD) { polynomial p = HEAD; HEAD = HEAD -> next; free(p); } } int polyn_length(polynomial HEAD) { polynomial p = HEAD -> next; int i = 0; while(p) { i += 1; p = p -> next; } return i; } polynomial polyn_add(polynomial pa, polynomial pb) { /* 和链表的头结点 */ polynomial hc = pa; /* 指向和链表的最后一个结点 */ polynomial pc = hc; /* hb为链表b的头结点 */ polynomial hb = pb; /* 当前结点 */ pb = pb -> next; /* 当前结点 */ pa = pa -> next; int type; while(pa && pb) { type = compare(pa -> data, pb -> data); if (type == a_e_b) { /* 指数相同,系数相加 */ (pa -> data).coef = (pa -> data).coef + (pb -> data).coef; if (pa -> data.coef == 0) { /* 删除pa的当前结点 */ pc -> next = pa; pa = pa -> next; free(pc -> next); pc -> next = NULL; /* 删除pb的当前结点 */ hb -> next = pb ->