#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MYOVERFLOW -2
typedef int Status;
typedef int Elemtype;
typedef struct LNode{//结点类型
Elemtype data;
LNode *next;
}*Link,*Position;
typedef struct{//链表类型
Link head, tail;//分别指向线性链表中的头结点和最后一个结点
int len;//指示线性链表中数据元素的个数
}LinkList;
Status compare(Elemtype s1, Elemtype s2);//比较两者的大小，相等返回TRUE，否则返回FALSE
Status visit(LinkList L);//若存在，则遍历L返回OK，否则返回ERROR
Status Create_List(LinkList &);//创造一个链表
Status MakeNode(Link &p, Elemtype e);
//分配由p指向的值为e的结点，并返回OK；若分配失败，则返回ERROR
void FreeNode(Link &p);
//释放p所指结点
Status InitList(LinkList &L);
//构造一个空的线性链表L
Status DestroyList(LinkList &L);
//销毁线性链表L，L不再存在
Status ClearList(LinkList &L);
//将线性链表L重置为空表，并释放原链表的结点空间
Status InsFirst(Link h, Link s);
//已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
Status DelFirst(Link h, Link &q);
//已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
Status Append(LinkList &L, Link s);
//将指针s所指（彼此以指针相链）的一串结点链接在线性链表L的最后一个结点
//之后，并改变链表L的尾指针指向新的尾结点
Status Remove(LinkList &L, Link &q);
//删除线性链表L中的尾结点并以q返回，改变链表L的尾指针指向新的尾结点
Status InsBefore(LinkList &L, Link &p, Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前，
//并修改指针p指向新插入的结点
Status InsAfter(LinkList &L, Link &p, Link s);
//已知p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之后，
//并修改指针p指向新插入的结点
Status SetCurElem(Link &p, Elemtype e);
//已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
Elemtype GetCurElem(Link p);
//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
Status ListEmpty(LinkList L);
//若线性链表L为空表，则返回TRUE，否则返回FALSE
int ListLength(LinkList L);
//返回线性链表L中元素个数
Position GetHead(LinkList L);
//返回线性链表L中头结点的位置
Position GetLast(LinkList L);
//返回线性链表L中最后一个结点的位置
Position PriorPos(LinkList L, Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置，
//若无前驱，则返回NULL
Position NextPos(LinkList L, Link p);
//已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置，
//若无后继，则返回NULL
Status LocatePos(LinkList L,int i, Link &p);
//返回p指示线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR
Position LocateElem(LinkList L, Elemtype e, Status(*P)(Elemtype, Elemtype));
//返回线性链表L中第一个与e满足函数p（）判定关系的元素的位置，
//若不存在这样的元素，则返回NULL
Status ListTraverse(LinkList L, Status(*visit)(LinkList));
//依次对L的每个元素调用函数visit（）。一旦visit（）失败，则操作失败

#include"LinkList.h"
typedef LinkList polynomial;
int compare2(Elemtype e1, Elemtype e2);
//如果e1的指数值<(或=)(或>)e2的指数值，分别返回-1，0，和+1
Status LocateElem(LinkList L, Elemtype e, Position &q, int(*compare)(Elemtype, Elemtype));
//若有序链表L中存在与e满足判定函数compare（）取值为0的元素，则q指示L中第一个值为e的结点的位置
//并返回TRUE；否则q指示第一个与e满足判定函数compare（）取值＞0的元素的前驱的位置，并返回FALSE
Status OrderInsert(LinkList &L, Elemtype e, int(*compare)(Elemtype, Elemtype));
//按有序判定函数compare（）的约定，将值为e的结点插入到有序链表L的适当位置上
void CreatPolyn(polynomial &P);
//输入n项的系数和指数，建立表示一元多项式的有序链表P
void DestroyPolyn(polynomial &P);
//销毁一元多项式P
void PrintPolyn(polynomial p);
//打印输出一元多项式P
int PolynLength(polynomial P);
//返回一元多项式P中的项数
void AddPolyn(polynomial &Pa, polynomial &Pb);
//完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb
void SubtractPolyn(polynomial &Pa, polynomial &Pb);
//完成多项式减法运算，即：Pa=Pa-Pb，并销毁一元多项式Pb
void MultiplyPolyn(polynomial &Pa, polynomial &Pb);
//完成多项式相乘运算，即：Pa=Pa*Pb，并销毁一元多项式Pb

int compare2(Elemtype e1, Elemtype e2)
//如果e1的指数值<(或=)(或>)e2的指数值，分别返回-1，0，和+1
{
int i = 0;
if (e1.expn < e2.expn)i = -1;
if (e1.expn>e2.expn)i = 1;
return i;
}
Status LocateElem(LinkList L, Elemtype e, Position &q, int(*compare)(Elemtype, Elemtype))
//若有序链表L中存在与e满足判定函数compare（）取值为0的元素，则q指示L中第一个值为e的结点的位置
//并返回TRUE；否则q指示NULL，并返回FALSE
{
if (L.head->next){
for (; L.head->next; L.head = L.head->next){
if (!compare(L.head->next->data, e))break;
}
q = L.head->next;
if (!L.head->next)//判断是否全部结点都不满足compare（）函数，如果有满足的则返回TRUE
return TRUE;
else
return FALSE;//否则返回FALSE
}
q = NULL;
return FALSE;
}
Status OrderInsert(LinkList &L, Elemtype e, int(*compare)(Elemtype, Elemtype))
//按有序判定函数compare（）的约定，将值为e的结点插入到有序链表L的适当位置上,注意L若是个空链表，则将值为e的结点插入到head的后面
{
Link temp=L.head,p=L.head;
for (; temp->next; temp = temp->next){
if (compare(e, temp->next->data) == -1)break;//找到前一个结点
}
Link t;
MakeNode(t, e);
t->next = temp->next;
if (temp->next)L.tail = t;//将值为e的结点插入到L中，如果为最后一个结点，则要改变尾结点的指向
temp->next = t;
L.len++;
return OK;
}
void CreatPolyn(polynomial &P)
//输入m项的系数和指数，建立表示一元多项式的有序链表P
{
Create_List(P);
}
void DestroyPolyn(polynomial &P)
//销毁一元多项式P
{
DestroyList(P);
}
void PrintPolyn(polynomial p)
//打印输出一元多项式P
{
ListTraverse(p, visit);
}
int PolynLength(polynomial P)
//返回一元多项式P中的项数
{
return ListLength(P);
}
void AddPolyn(polynomial &Pa, polynomial &Pb)
//完成多项式相加运算，即：Pa=Pa+Pb，并销毁一元多项式Pb
{
Link ta = Pa.head->next;
Link tb = Pb.head->next;
Link tta = Pa.tail;
Link beforeta = Pa.head;
for (; ta&&tb;){
if (ta->data.expn < tb->data.expn){//如果ta的指数小于tb的指数，则只需ta向后移
beforeta = ta; ta = ta->next;
}
else if (ta->data.expn == tb->data.expn){//如果==
ta->data.ceof += tb->data.ceof;//ta的系数为两者系数之和
Link tempb = tb;//删除tb，tb向后移一位
tb = tb->next;
delete tempb;
if (ta->data.ceof == 0){//如果系数之和为0，则要删除ta
Link tempa = ta;
beforeta->next = ta->next;
ta = ta->next;
Pa.len--;
if (tempa == tta)tta = beforeta;
delete tempa;
}
}
else {//如果是>
Link temp=tb->next;//则要把tb插进来
beforeta->next = tb;
tb->next = ta;
beforeta =tb;
tb = temp;
Pa.len++;
}
}
if (!ta){//如果是ta先为空，则要把tb的剩余元素插进来
tta->next = tb;
Pa.tail = Pb.tail;
for (; tb; tb = tb->next)Pa.len++;
delete Pb.head;
}
}
void SubtractPolyn(polynomial &Pa, polynomial &Pb)
//完成多项式减法运算，即：Pa=Pa-Pb，并销毁一元多项式Pb
{ Link tb = Pb.head->next;//将tb数据元素的系数全部变成相反数，然后进行加法的运算
for (; tb; tb = tb->next){
tb->data.ceof = -tb->data.ceof;
}
Link ta = Pa.head->next;
tb = Pb.head->next;
Link tta = Pa.tail;
Link beforeta = Pa.head;
for (; ta&&tb;){
if (ta->data.expn < tb->data.expn){//如果ta的指数小于tb的指数，则只需ta向后移
beforeta = ta; ta = ta->next;
}
else if (ta->data.expn == tb->data.expn){//如果==
ta->data.ceof += tb->data.ceof;//ta的系数为两者系数之和
Link tempb = tb;//删除tb，tb向后移一位
tb = tb->next;
delete tempb;
if (ta->data.ceof == 0){//如果系数之和为0，则要删除ta
Link tempa = ta;
beforeta->next = ta->next;
ta = ta->next;
Pa.len--;
if (tempa == tta)tta = beforeta;
delete tempa;
}
}
else {//如果是>
Link temp = tb->next;//则要把tb插进来
beforeta->next = tb;
tb->next = ta;
beforeta = tb;
tb = temp;
Pa.len++;
}
}
if (!ta){//如果是ta先为空，则要把tb的剩余元素插进来
tta->next = tb;
Pa.tail = Pb.tail;
for (; tb; tb = tb->next)Pa.len++;
delete Pb.head;
}
}
void MultiplyPolyn(polynomial &Pa, polynomial &Pb)
//完成多项式相乘运算，即：Pa=Pa*Pb，并销毁一元多项式Pb
{
polynomial Pc,Pd;
InitList(Pc);//构造一个空的链表
Pc.head->next = NULL;
Link tb = Pb.head->next;
for (; tb; ){
Link ta = Pa.head->next;
InitList(Pd);
Pd.head->next = NULL;
Link td = Pd.head;
Link tempd;
for (; ta; ta = ta->next){
tempd=new LNode;
tempd->data.ceof = ta->data.ceof*tb->data.ceof;
tempd->data.expn = ta->data.expn + tb->data.expn;
tempd->next = NULL;
td->next= tempd;
td = td->next;
Pd.len++;
if (ta->next == NULL)Pd.tail = tempd;
}
AddPolyn(Pc, Pd);
Link tempb = tb;
tb = tb->next;
delete tempb;
}
Pa.head = Pa.head->next;
for (; Pa.head;){
Link temp = Pa.head;
Pa.head = Pa.head->next;
delete temp;
}
delete Pb.head;
Pa = Pc;
}

// polynomial.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
int _tmain(int argc, _TCHAR* argv[])
{
polynomial list1,list2;
CreatPolyn(list1);
CreatPolyn(list2);
MultiplyPolyn(list1, list2);
PrintPolyn(list1);
return 0;
}