/*数据结构C语言版抽象数据类型Polynomial一元多项式的实现P42-43编译环境：Dev-C++ 4.9.9.2日期：2011年2月10日*/#include <stdio.h>#include <malloc.h>#include <stdlib.h>// 抽象数据类型Polynomial一元多项式的实现typedef struct // 项的表示,多项式的项作为LinkList的数据元素{float coef; // 系数int expn; // 指数}term, ElemType;// 两个类型名:term用于本ADT,ElemType为LinkList的数据对象名typedef struct LNode // 结点类型{ElemType data;struct LNode *next;}LNode,*Link,*Position;typedef struct _LinkList // 链表类型{Link head,tail; // 分别指向线性链表中的头结点和最后一个结点int len; // 指示当前线性链表中数据元素的个数}LinkList;typedef LinkList polynomial;#define DestroyPolyn DestroyList#define PolynLength ListLength// 已知p指向线性链表L中的一个结点，返回p所指结点的直接前驱的位置// 若无前驱，则返回NULLPosition PriorPos(LinkList L,Link p){Link q;q=L.head->next;if(q==p) // 无前驱return NULL;else{while(q->next!=p) // q不是p的直接前驱q=q->next;return q;}}// 若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中// 第一个值为e的结点的位置，并返回1；否则q指示第一个与e满足判定函数// compare()取值>0的元素的前驱的位置。
并返回0。
（用于一元多项式）int LocateElemP(LinkList L,ElemType e,Position *q,int(*compare)(ElemType,ElemType)){Link p=L.head,pp;do{pp=p;p=p->next;}while(p&&(compare(p->data,e)<0)); // 没到表尾且p->data.expn<e.expn if(!p||compare(p->data,e)>0) // 到表尾或compare(p->data,e)>0{*q=pp;return 0;}else // 找到{*q=p;return 1;}}// h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以q返回。
// 若链表为空(h指向尾结点)，q=NULL，返回0int DelFirst(LinkList *L,Link h,Link *q){*q=h->next;if(*q) // 链表非空{h->next=(*q)->next;if(!h->next) // 删除尾结点(*L).tail=h; // 修改尾指针(*L).len--;return 1;}elsereturn 0; // 链表空}// 分配由p指向的值为e的结点，并返回1；若分配失败。
则返回0int MakeNode(Link *p,ElemType e){*p = (Link)malloc(sizeof(LNode)); //动态分配一个Link空间if(!*p)return 0;(*p)->data = e; // 赋值return 1;}// 释放p所指结点void FreeNode(Link *p){free(*p); //老规矩，先释放存储空间，然后置空*p=NULL;}// h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前// 头结点没有数据域，而第一个结点是h->nextint InsFirst(LinkList *L,Link h,Link s){s->next = h->next;h->next=s;if(h==(*L).tail) // 如果h指向尾结点(*L).tail=h->next; // 修改尾指针(*L).len++;return 1;}// 按有序判定函数compare()的约定，将值为e的结点插入或合并到升序// 链表L的适当位置int OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term)) {Position q,s;if(LocateElemP(*L,e,&q,compare)) // L中存在该指数项{q->data.coef+=e.coef; // 改变当前结点系数的值if(!q->data.coef) // 系数为0{// 删除多项式L中当前结点s = PriorPos(*L,q); // s为当前结点的前驱if(!s) // q无前驱s=(*L).head;DelFirst(L,s,&q);FreeNode(&q);}return 1;}else // 生成该指数项并插入链表if(MakeNode(&s,e)) // 生成结点成功{InsFirst(L,q,s);return 1;}else // 生成结点失败return 0;}// 依a的指数值<、=或>b的指数值，分别返回-1、0或+1 // CreatPolyn()的实参int cmp(term a,term b){if(a.expn==b.expn)return 0;elsereturn (a.expn-b.expn)/abs(a.expn-b.expn); }// 构造一个空的线性链表int InitList(LinkList *L){Link p;p=(Link)malloc(sizeof(LNode)); // 生成头结点if(p){p->next=NULL;//将头尾结点都分配好，并将其下一结点置空(*L).head=(*L).tail=p;(*L).len=0; //初始为0return 1;}else // 分配失败返回return 0;}// 算法2.22 P42// 输入m项的系数和指数，建立表示一元多项式的有序链表Pvoid CreatPolyn(polynomial *P,int m){Position q,s;term e;int i;InitList(P);printf("请依次输入%d个系数，指数：（空格）\n",m);for(i=1;i<=m;++i){// 依次输入m个非零项（可按任意顺序）scanf("%f%d",&e.coef,&e.expn);// 当前链表中不存在该指数项,cmp是实参if(!LocateElemP(*P,e,&q,cmp))if(MakeNode(&s,e)) // 生成结点并插入链表InsFirst(P,q,s);}}// 返回线性链表L中头结点的位置Position GetHead(LinkList L){return L.head;}// 已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置// 若无后继，则返回NULLPosition NextPos(Link p){return p->next;}// 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值ElemType GetCurElem(Link p){return p->data;}// 将指针s(s->data为第一个数据元素)所指(彼此以指针相链,以NULL结尾)的// 一串结点链接在线性链表L的最后一个结点之后,并改变链表L的尾指针指向新// 的尾结点int Append(LinkList *L,Link s){int i=1; //记录s为头的串结点个数(*L).tail->next=s; //尾结点指向swhile(s->next){s=s->next;i++;}(*L).tail=s;(*L).len+=i;return 1;}// 若线性链表L为空表，则返回1，否则返回0int ListEmpty(LinkList L){if(L.len)return 0;elsereturn 1;}// 将线性链表L重置为空表（头尾结点相同为空表），并释放原链表的结// 点空间，不释放头尾结点，只是置空而已int ClearList(LinkList *L){Link p,q;if((*L).head!=(*L).tail)// 不是空表{p=q=(*L).head->next;(*L).head->next=NULL;while(p!=(*L).tail){p=q->next;free(q);q=p;}free(q);(*L).tail=(*L).head;(*L).len=0;}return 1;}// 销毁线性链表L，L不再存在int DestroyList(LinkList *L){ClearList(L); // 清空链表（头尾结点并没有释放）FreeNode(&(*L).head); //再释放头尾结点(*L).tail=NULL;(*L).len=0;return 1;}// 算法2.23 P43// 多项式加法:Pa=Pa+Pb,并销毁一元多项式Pbvoid AddPolyn(polynomial *Pa,polynomial *Pb){Position ha,hb,qa,qb;term a,b;ha=GetHead(*Pa);hb=GetHead(*Pb); // ha和hb分别指向Pa和Pb的头结点qa=NextPos(ha);qb=NextPos(hb); // qa和qb分别指向Pa和Pb中当前结点（现为第一个结点）while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa){ // Pa和Pb均非空且ha没指向尾结点(qa!=0)a=GetCurElem(qa);b=GetCurElem(qb); // a和b为两表中当前比较元素switch(cmp(a,b)){case -1:ha=qa; // 多项式Pa中当前结点的指数值小qa=NextPos(ha); // ha和qa均向后移一个结点break;case 0:qa->data.coef+=qb->data.coef;// 两者的指数值相等,修改Pa当前结点的系数值if(qa->data.coef==0) // 系数和为0，则删除多项式Pa中当前结点{DelFirst(Pa,ha,&qa);FreeNode(&qa);}elseha=qa;DelFirst(Pb,hb,&qb);FreeNode(&qb);qb=NextPos(hb);qa=NextPos(ha);break;case 1:DelFirst(Pb,hb,&qb); // 多项式Pb中当前结点的指数值小InsFirst(Pa,ha,qb);ha=ha->next;qb=NextPos(hb);}}if(!ListEmpty(*Pb)){(*Pb).tail=hb;Append(Pa,qb); // 链接Pb中剩余结点}DestroyPolyn(Pb); // 销毁Pb}// 另一种多项式加法的算法:Pa=Pa+Pb,并销毁一元多项式Pbvoid AddPolyn1(polynomial *Pa,polynomial *Pb){Position qb;term b;qb=GetHead(*Pb); // qb指向Pb的头结点qb=qb->next; // qb指向Pb的第一个结点while(qb){b=GetCurElem(qb);OrderInsertMerge(Pa,b,cmp);qb=qb->next;}DestroyPolyn(Pb); // 销毁Pb}// 一元多项式系数取反void Opposite(polynomial Pa){Position p;p=Pa.head;while(p->next){p=p->next;p->data.coef*=-1;}}// 多项式减法:Pa=Pa-Pb,并销毁一元多项式Pbvoid SubtractPolyn(polynomial *Pa,polynomial *Pb) {Opposite(*Pb);AddPolyn(Pa,Pb);}// 多项式乘法:Pa=PaPb,并销毁一元多项式Pbvoid MultiplyPolyn(polynomial *Pa,polynomial *Pb) {polynomial Pc;Position qa,qb;term a,b,c;InitList(&Pc);qa=GetHead(*Pa);qa=qa->next;while(qa){a=GetCurElem(qa);qb=GetHead(*Pb);qb=qb->next;while(qb){b=GetCurElem(qb);c.coef=a.coef*b.coef;c.expn=a.expn+b.expn;OrderInsertMerge(&Pc,c,cmp);qb=qb->next;}qa=qa->next;}DestroyPolyn(Pb); // 销毁PbClearList(Pa); // 将Pa重置为空表(*Pa).head=Pc.head;(*Pa).tail=Pc.tail;(*Pa).len=Pc.len;}// 打印输出一元多项式Pvoid PrintPolyn(polynomial P){Link q;q=P.head->next; // q指向第一个结点printf(" 系数指数\n");while(q){printf("%f %d\n",q->data.coef,q->data.expn);q=q->next;}}int main(){polynomial p,q;int m;// 多项式相加printf("两个一元多项式相加\n");//构建一个多项式printf("请输入第一个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&p,m);//构建另一个多项式printf("请输入第二个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&q,m);//多项式相加AddPolyn(&p,&q);printf("两个一元多项式相加的结果：\n");//打印多项式PrintPolyn(p);// 使用另一种多项式相加的方法printf("\n两个一元多项式相加(另一种方法)\n");printf("请输入第三个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&p,m);printf("请输入第四个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&q,m);// 多项式相加的另一种方法AddPolyn1(&p,&q);printf("两个一元多项式相加的结果(另一种方法)：\n");PrintPolyn(p);// 多项式相减printf("\n两个一元多项式相减\n");printf("请输入第五个个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&p,m);printf("请输入第六个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&q,m);// 多项式相减SubtractPolyn(&p,&q);printf("两个一元多项式相减的结果：\n");PrintPolyn(p);//多项式相乘printf("\n两个一元多项式相乘\n");printf("请输入第七个个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&p,m);printf("请输入第八个一元多项式的非零项的个数：");scanf("%d",&m);CreatPolyn(&q,m);//多项式相乘MultiplyPolyn(&p,&q);printf("两个一元多项式相乘的结果：\n");PrintPolyn(p);//销毁多项式DestroyPolyn(&p);DestroyPolyn(&q);system("pause");return 0;}/*输出效果：两个一元多项式相加请输入第一个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）1 0 1 1请输入第二个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）-1 0 -2 1两个一元多项式相加的结果：系数指数-1.000000 1两个一元多项式相加(另一种方法)请输入第三个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）1 0 1 1请输入第四个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）-1 0 -2 1两个一元多项式相加的结果(另一种方法)：系数指数-1.000000 1两个一元多项式相减请输入第五个个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）1 02 1请输入第六个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）-2 0 -1 1两个一元多项式相减的结果：系数指数3.000000 03.000000 1两个一元多项式相乘请输入第七个个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）1 0 1 1请输入第八个一元多项式的非零项的个数：2 请依次输入2个系数，指数：（空格）1 0 1 1两个一元多项式相乘的结果：系数指数1.000000 02.000000 11.000000 2请按任意键继续. . . */。
![一元多项式的实现_数据结构与算法分析（C++语言版）_[共5页]](https://img.taocdn.com/s1/m/4b7adb9bf7ec4afe05a1df93.png)
