转载

用链表实现的多项式

是基于上个博客的内容，将上个博客实现的基本操作组成一个自己的lib，将头文件添加到多项式的头文件中即可，注意：要多有关于Elemtype类型数据的输入输出要进行重写

链表的头文件：

#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; }

结果：

用链表实现的多项式