【线性表】应用—一元多项式的表示及相加
typedef struct polynode
{
int coef;
int exp;
polynode* next;
}polynode,*polylist;
例：建立一元多项式链式存储算法
【算法思想】通过键盘输入一组多项式的系数和指数，用尾插法建立一元多项式的链表。以输入系数0为结束标注，并约定建立多项式链表时，总是按指数从小到大排序。
【算法描述】
polylist CreatList()
{
polynode* head = (polynode*)malloc(sizeof(polynode));//建立多项式的头结点；
polynode* temp = head;//rear始终指向单链表的尾，便于尾插法建表
int c, e,i=1;
cout<<"第"<<i << "项系数:" << endl;
cin >> c;
cout << "第" << i << "项质数:" << endl;
cin >> e;
while (c != 0)
{
polynode* node = CreatNode(c, e);
temp->next = node;
temp = node;
i++;
cout << "第" << i << "项系数:" << endl;
cin >> c;
cout << "第" << i << "项质数:" << endl;
cin >> e;
temp = node;
}
temp->next = NULL;//将表的最后一个结点的next置NULL，以表示结束
return head;
}
【算法思想】
以单链表polya和polyb分别表示两个一元多项式A和B，A+B的求和运算，就等同于单链表的插入问题（将单链表polyb中的结点插入到单链表polya中），因此“和多项式”中的结点无需另生成。
为实现处理，设p，q分别指向单链表polya和polyb的当前项，比较p，q的结点的指数项，由此得到下列运算规则：
①若p->exp < q->exp，则结点p所指的结点应该是“和多项式”中的一项，另指针后移；
②若p->exp = q->exp，则将两个结点中的系数增加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点。
③若p->exp > q->exp，则结点q所指的结点应该时“和多项式”中的一项，将结点q插入结点p之前，且令指针q在原来的链表上后移
polylist polyadd(polylist polya, polylist polyb)//将两个多项式相加，然后将和多项式存放在polya中，并将polyb删除
{
polynode* p, * q, * temp, * tail;
int sum;
p = polya->next;
q = polyb->next;//令p和q分别指向polya和polyb多项式链表中的第一个结点
tail = polya;//tail指向和多项式的尾结点
while (p!= NULL && q!= NULL)
{//规则（1）：如果p指向的多项式的指数小于q的指数，将p结点加入到和多项式中
if (p->exp < q->exp)
{
tail->next = p;
tail = p;
p = p->next;
}
else if (p->exp == q->exp)//规则(2)：若指数相等，则相应的系数相加
{
sum = p->coef + q->coef;//若系数和为0.删除p，q，并将指针指向下一个结点
if (sum == 0)
{
temp = p;
p = p->next;
free(temp);
temp = q;
q = q->next;
free(temp);
}
else//若系数和非0，则系数和置入结点p，释放结点q，并将指针后移
{
p->coef = sum;
tail->next = p;
tail = p;
temp = q;
q = q->next;
p = p->next;
free(temp);
}
}
//else规则（3）：如果p指向的多项式的指数大于q的指数，将q结点加入到和多项式中
{
tail->next = q;
tail = q;
q = q->next;
}
}
if (p != NULL)
//多项式A中还有剩余，则将剩余的结点加入到和多项式中
{
tail->next = p;
tail = p;
p = p->next;
}
else if(q!=NULL) {
tail->next = q;
tail = q;
q = q->next;
}
return polya;
}
总代码：
#include<iostream>//ZJJ数据据结构-链表(一元多项式的表示及相加）2.22
using namespace std;
#define ElemType int
typedef struct polynode
{
int coef;
int exp;
polynode* next;
}polynode,*polylist;
polylist CreatNode(int coef,int exp)
{
polynode* node = (polynode*)malloc(sizeof(polynode));
node->coef = coef;
node->exp = exp;
node->next = NULL;
return node;
}
polylist CreatList()
{
polynode* head = (polynode*)malloc(sizeof(polynode));//建立多项式的头结点；
polynode* temp = head;//rear始终指向单链表的尾，便于尾插法建表
int c, e,i=1;
cout<<"第"<<i << "项系数:" << endl;
cin >> c;
cout << "第" << i << "项质数:" << endl;
cin >> e;
while (c != 0)
{
polynode* node = CreatNode(c, e);
temp->next = node;
temp = node;
i++;
cout << "第" << i << "项系数:" << endl;
cin >> c;
cout << "第" << i << "项质数:" << endl;
cin >> e;
temp = node;
}
temp->next = NULL;//将表的最后一个结点的next置NULL，以表示结束
return head;
}
void ShowList(polylist head)
{
polylist temp = head->next;
cout << temp->coef << "x" <<"^"<< temp->exp;
while (temp->next) {
temp = temp->next;
cout << "+"<<temp->coef << "x" << "^" << temp->exp;
}
cout << endl;
}
polylist polyadd(polylist polya, polylist polyb)//将两个多项式相加，然后将和多项式存放在polya中，并将polyb删除
{
polynode* p, * q, * temp, * tail;
int sum;
p = polya->next;
q = polyb->next;//令p和q分别指向polya和polyb多项式链表中的第一个结点
tail = polya;//tail指向和多项式的尾结点
while (p!= NULL && q!= NULL)
{//规则（1）：如果p指向的多项式的指数小于q的指数，将p结点加入到和多项式中
if (p->exp < q->exp)
{
tail->next = p;
tail = p;
p = p->next;
}
else if (p->exp == q->exp)//规则(2)：若指数相等，则相应的系数相加
{
sum = p->coef + q->coef;//若系数和为0.删除p，q，并将指针指向下一个结点
if (sum == 0)
{
temp = p;
p = p->next;
free(temp);
temp = q;
q = q->next;
free(temp);
}
else//若系数和非0，则系数和置入结点p，释放结点q，并将指针后移
{
p->coef = sum;
tail->next = p;
tail = p;
temp = q;
q = q->next;
p = p->next;
free(temp);
}
}
//else规则（3）：如果p指向的多项式的指数大于q的指数，将q结点加入到和多项式中
{
tail->next = q;
tail = q;
q = q->next;
}
}
if (p != NULL)
//多项式A中还有剩余，则将剩余的结点加入到和多项式中
{
tail->next = p;
tail = p;
p = p->next;
}
else if(q!=NULL) {
tail->next = q;
tail = q;
q = q->next;
}
return polya;
}
int main()
{
polylist pa, pb;
pa = CreatList();
cout << "PA(x)=";
ShowList(pa);
pb = CreatList();
cout << "PB(x)=";
ShowList(pb);
pa=polyadd(pa, pb);
cout << "PA(x)+PB(x)=";
ShowList(pa);
}
运行结果：
有无欠缺的，欢迎指正。