數(shù)據(jù)結構C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)文庫

/*數(shù)據(jù)結構C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn) P42-43 編譯環(huán)境：Dev-C+ 4.9.9.2日期：2011年2月10日 */#include <stdio.h>#include <malloc.h>#include <stdlib.h>/ 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn) typedef struct / 項的表示,多項式的項作為LinkList的數(shù)據(jù)元素 float coef;/ 系數(shù) int expn;/ 指數(shù) term, ElemType;/ 兩個類型名:term用于本ADT,ElemType為LinkList的數(shù)據(jù)對象名 typedef struct LNode / 結點類型 ElemType data;struct LNode *next;LNode,*Link,*Position;typedef struct _LinkList / 鏈表類型 Link head,tail;/ 分別指向線性鏈表中的頭結點和最后一個結點 int len;/ 指示當前線性鏈表中數(shù)據(jù)元素的個數(shù) 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滿足判定函數(shù)compare()取值為0的元素，則q指示L中/ 第一個值為e的結點的位置，并返回1；否則q指示第一個與e滿足判定函數(shù) / 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)<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，返回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);/動態(tài)分配一個Link空間if(!*p)return 0;(*p)->data = e;/ 賦值return 1;/ 釋放p所指結點void FreeNode(Link *p) free(*p);/老規(guī)矩，先釋放存儲空間，然后置空*p=NULL;/ h指向L的一個結點，把h當做頭結點，將s所指結點插入在第一個結點之前 / 頭結點沒有數(shù)據(jù)域，而第一個結點是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;/ 按有序判定函數(shù)compare()的約定，將值為e的結點插入或合并到升序/ 鏈表L的適當位置 int OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term)Position q,s;if(LocateElemP(*L,e,&q,compare) / L中存在該指數(shù)項 q->data.coef+=e.coef; / 改變當前結點系數(shù)的值 if(!q->data.coef) / 系數(shù)為0 / 刪除多項式L中當前結點 s = PriorPos(*L,q); / s為當前結點的前驅 if(!s) / q無前驅 s=(*L).head;DelFirst(L,s,&q);FreeNode(&q);return 1;else / 生成該指數(shù)項并插入鏈表 if(MakeNode(&s,e) / 生成結點成功 InsFirst(L,q,s);return 1;else / 生成結點失敗 return 0;/ 依a的指數(shù)值<、=或>b的指數(shù)值，分別返回-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項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P void CreatPolyn(polynomial *P,int m)Position q,s;term e;int i;InitList(P);printf("請依次輸入%d個系數(shù)，指數(shù)：（空格）n",m);for(i=1;i<=m;+i) / 依次輸入m個非零項（可按任意順序） scanf("%f%d",&e.coef,&e.expn);/ 當前鏈表中不存在該指數(shù)項,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所指結點的直接后繼的位置 / 若無后繼，則返回NULL Position NextPos(Link p) return p->next;/ 已知p指向線性鏈表中的一個結點，返回p所指結點中數(shù)據(jù)元素的值ElemType GetCurElem(Link p) return p->data;/ 將指針s(s->data為第一個數(shù)據(jù)元素)所指(彼此以指針相鏈,以NULL結尾)的 / 一串結點鏈接在線性鏈表L的最后一個結點之后,并改變鏈表L的尾指針指向新 / 的尾結點 int Append(LinkList *L,Link s)int i=1;/記錄s為頭的串結點個數(shù)(*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中當前結點（現(xiàn)為第一個結點） 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中當前結點的指數(shù)值小 qa=NextPos(ha); / ha和qa均向后移一個結點 break;case 0:qa->data.coef+=qb->data.coef;/ 兩者的指數(shù)值相等,修改Pa當前結點的系數(shù)值 if(qa->data.coef=0) / 系數(shù)和為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中當前結點的指數(shù)值小 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 / 一元多項式系數(shù)取反 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(" 系數(shù) 指數(shù)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("請輸入第一個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&p,m);/構建另一個多項式printf("請輸入第二個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&q,m);/多項式相加AddPolyn(&p,&q);printf("兩個一元多項式相加的結果：n");/打印多項式PrintPolyn(p);/ 使用另一種多項式相加的方法 printf("n兩個一元多項式相加(另一種方法)n");printf("請輸入第三個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&p,m);printf("請輸入第四個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&q,m);/ 多項式相加的另一種方法AddPolyn1(&p,&q);printf("兩個一元多項式相加的結果(另一種方法)：n");PrintPolyn(p);/ 多項式相減 printf("n兩個一元多項式相減n");printf("請輸入第五個個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&p,m);printf("請輸入第六個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&q,m);/ 多項式相減SubtractPolyn(&p,&q);printf("兩個一元多項式相減的結果：n");PrintPolyn(p);/多項式相乘printf("n兩個一元多項式相乘n");printf("請輸入第七個個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&p,m);printf("請輸入第八個一元多項式的非零項的個數(shù)：");scanf("%d",&m);CreatPolyn(&q,m);/多項式相乘MultiplyPolyn(&p,&q);printf("兩個一元多項式相乘的結果：n");PrintPolyn(p);/銷毀多項式DestroyPolyn(&p);DestroyPolyn(&q);system("pause");return 0;/*輸出效果：兩個一元多項式相加請輸入第一個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 1 1請輸入第二個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）-1 0 -2 1兩個一元多項式相加的結果： 系數(shù) 指數(shù)-1.000000 1兩個一元多項式相加(另一種方法)請輸入第三個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 1 1請輸入第四個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）-1 0 -2 1兩個一元多項式相加的結果(另一種方法)： 系數(shù) 指數(shù)-1.000000 1兩個一元多項式相減請輸入第五個個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 2 1請輸入第六個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）-2 0 -1 1兩個一元多項式相減的結果： 系數(shù) 指數(shù)3.000000 03.000000 1兩個一元多項式相乘請輸入第七個個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 1 1請輸入第八個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 1 1兩個一元多項式相乘的結果： 系數(shù) 指數(shù)1.000000 02.000000 11.000000 2請按任意鍵繼續(xù). . .*/