数据结构C语言版抽象数据类型Polynomial一元多项式的实现文库.doc

数据结构C语言版 抽象数据类型Polynomial一元多项式的实现文库.txt生活是过出来的，不是想出来的。放得下的是曾经，放不下的是记忆。无论我在哪里，我离你都只有一转身的距离。/*数据结构C语言版 抽象数据类型Polynomial一元多项式的实现 P42-43 编译环境：Dev-C+ 4.9.9.2日期：2011年2月10日 */#include #include #include / 抽象数据类型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所指结点的直接前驱的位置 / 若无前驱，则返回NULL Position PriorPos(LinkList L,Link p)Link q;q=L.head-next;if(q=p) / 无前驱 return NULL;elsewhile(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;dopp=p;p=p-next;while(p&(compare(p-data,e)data.expndata,e)0) / 到表尾或compare(p-data,e)0 *q=pp;return 0;else / 找到 *q=p;return 1;/ h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以q返回。 / 若链表为空(h指向尾结点)，q=NULL，返回0 int 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项的系数和指数，建立表示一元多项式的有序链表P void CreatPolyn(polynomial *P,int m)Position q,s;term e;int i;InitList(P);printf(请依次输入%d个系数，指数：（空格）n,m);for(i=1;inext;/ 已知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,并销毁一元多项式Pb void 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,并销毁一元多项式Pb void SubtractPolyn(polynomial *Pa,polynomial *Pb)Opposite(*Pb);AddPolyn(Pa,Pb);/ 多项式乘法:Pa=PaPb,并销毁一元多项式Pb void 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); / 销毁Pb ClearList(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 %dn,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);/多项式相乘MultiplyPoly