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

1、數(shù)據(jù)結(jié)構(gòu) C 語言版 抽象數(shù)據(jù)類型 Polynomial 一元多項式的實現(xiàn)文庫 .txt 生活是過出來的， 不是想出來的。放得下的是曾經(jīng)，放不下的是記憶。無論我在哪里，我離你都只有一轉(zhuǎn)身的 距離。 /*數(shù)據(jù)結(jié)構(gòu) C 語言版 抽象數(shù)據(jù)類型 Polynomial 一元多項式的實現(xiàn)P42-43編譯環(huán)境： Dev-C+ 日期： 2011年 2月 10日*/ #include <stdio.h>#include <malloc.h>#include <stdlib.h> / 抽象數(shù)據(jù)類型 Polynomial 一元多項式的實現(xiàn)typedef struct /項的表示

2、, 多項式的項作為 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;結(jié)點類型typedef struct _LinkList / Link head,tail; /鏈表類型分別指向線性鏈表中的頭結(jié)點和最后一個結(jié)點int len;/ 指示當(dāng)前線性鏈表中數(shù)據(jù)元素的個數(shù)LinkList;

3、typedef LinkList polynomial; #define DestroyPolyn DestroyList #define PolynLength ListLength / 已知 p 指向線性鏈表 L 中的一個結(jié)點，返回 p 所指結(jié)點的直接前驅(qū)的位置 / 若無前驅(qū)，則返回 NULLPosition PriorPos(LinkList L,Link p)Link q;q=L.head->next;if(q=p) / 無前驅(qū) return NULL;else while(q->next!=p) / q 不是 p 的直接前驅(qū) q=q->next;return q;/

4、 若升序鏈表 L 中存在與 e 滿足判定函數(shù) compare() 取值為 0 的元素，則 q 指示 L 中/第一個值為e的結(jié)點的位置，并返回1;否則q指示第一個與e滿足判定函數(shù)/ compare()取值>0 的元素的前驅(qū)的位置。并返回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); /

5、沒到表尾且 p->data.expn<e.expnif(!p|compare(p->data,e)>0) /到表尾或 compare(p->data,e)>0*q=pp; return 0;else / 找到*q=p; return 1; / h指向L的一個結(jié)點，把h當(dāng)做頭結(jié)點，刪除鏈表中的第一個結(jié)點并以q返回。/若鏈表為空(h指向尾結(jié)點)，q=NULL返回0int DelFirst(LinkList *L,Link h,Link *q)*q=h->next;if(*q) / 鏈表非空 h->next=(*q)->next;if(!h-&g

6、t;next)/ 刪除尾結(jié)點(*L).tail=h; /修改尾指針(*L).len-;return 1;elsereturn 0; / 鏈表空/ 分配由 p 指向的值為 e 的結(jié)點，并返回 1；若分配失敗。則返回 0 int MakeNode(Link *p,ElemType e)*p = (Link)malloc(sizeof(LNode);/ 動態(tài)分配一個 Link 空間if(!*p)return 0;(*p)->data = e; / 賦值return 1;/ 釋放 p 所指結(jié)點void FreeNode(Link *p)free(*p); / 老規(guī)矩，先釋放存儲空間，然后置空*p

7、=NULL;/ h 指向 L 的一個結(jié)點，把 h 當(dāng)做頭結(jié)點，將 s 所指結(jié)點插入在第一個結(jié)點之前 / 頭結(jié)點沒有數(shù)據(jù)域，而第一個結(jié)點是 h->nextint InsFirst(LinkList *L,Link h,Link s)s->next = h->next;h->next=s;if(h=(*L).tail)/ 如果 h 指向尾結(jié)點(*L).tail=h->next;/ 修改尾指針(*L).len+;return 1;/ 按有序判定函數(shù) compare() 的約定，將值為 e 的結(jié)點插入或合并到升序/ 鏈表 L 的適當(dāng)位置int OrderInsertMer

8、ge(LinkList *L,ElemType e,int(* compare)(term,term)Position q,s;if(LocateElemP(*L,e,&q,compare) / L中存在該指數(shù)項q->data.coef+=e.coef; / 改變當(dāng)前結(jié)點系數(shù)的值if(!q->data.coef) / 系數(shù)為 0 / 刪除多項式 L 中當(dāng)前結(jié)點s = PriorPos(*L,q); / s 為當(dāng)前結(jié)點的前驅(qū) if(!s) / q 無前驅(qū)s=(*L).head; DelFirst(L,s,&q); FreeNode(&q); return 1;

9、else / 生成該指數(shù)項并插入鏈表 if(MakeNode(&s,e) / 生成結(jié)點成功 InsFirst(L,q,s); return 1;else / 生成結(jié)點失敗 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);/ 構(gòu)造一個空的線性鏈表int InitList(LinkList *L)Link p;p=(Link)m

10、alloc(sizeof(LNode); /生成頭結(jié)點if(p)p->next=NULL;/ 將頭尾結(jié)點都分配好，并將其下一結(jié)點置空 (*L).head=(*L).tail=p;(*L).len=0; / 初始為 0return 1;else / 分配失敗返回 return 0;/ 算法 2.22 P42/輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表Pvoid CreatPolyn(polynomial *P,int m)Position q,s;term e;int i;InitList(P);printf(”請依次輸入d個系數(shù)，指數(shù)：(空格)n”,m);for(i=1;i<

11、;=m;+i)/依次輸入m個非零項(可按任意順序) scanf("%f%d",&e.coef,&e.expn);/ 當(dāng)前鏈表中不存在該指數(shù)項 ,cmp 是實參 if(!LocateElemP(*P,e,&q,cmp)if(MakeNode(&s,e) / 生成結(jié)點并插入鏈表 InsFirst(P,q,s);/ 返回線性鏈表 L 中頭結(jié)點的位置Position GetHead(LinkList L)return L.head;/ 已知 p 指向線性鏈表 L 中的一個結(jié)點，返回p 所指結(jié)點的直接后繼的位置/ 若無后繼，則返回 NULLPositi

12、on NextPos(Link p)return p->next;/ 已知 p 指向線性鏈表中的一個結(jié)點，返回 p 所指結(jié)點中數(shù)據(jù)元素的值 ElemType GetCurElem(Link p)return p->data;/將指針s(s->data為第一個數(shù)據(jù)元素)所指(彼此以指針相鏈,以NULL結(jié)尾)的 / 一串結(jié)點鏈接在線性鏈表 L 的最后一個結(jié)點之后 , 并改變鏈表 L 的尾指針指向新 / 的尾結(jié)點int Append(LinkList *L,Link s)int i=1;/ 記錄 s 為頭的串結(jié)點個數(shù)(*L).tail->next=s;/ 尾結(jié)點指向 swhi

13、le(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 重置為空表(頭尾結(jié)點相同為空表) ，并釋放原鏈表的結(jié)/ 點空間，不釋放頭尾結(jié)點，只是置空而已int ClearList(LinkList *L)Link p,q; if(*L).head!=(*L).tail)/不是空表p=q=(*L).head->next;(*L).head-&

14、gt;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);/ 清空鏈表(頭尾結(jié)點并沒有釋放)FreeNode(&(*L).head);/ 再釋放頭尾結(jié)點(*L).tail=NULL;(*L).len=0;return 1;/ 算法 2.23 P43/ 多項式加法 :Pa=Pa+Pb, 并銷毀一元多項式 Pbvoid A

15、ddPolyn(polynomial *Pa,polynomial *Pb)Position ha,hb,qa,qb;term a,b;ha=GetHead(*Pa);hb=GetHead(*Pb); / ha 和 hb 分別指向 Pa 和 Pb 的頭結(jié)點 qa=NextPos(ha);qb=NextPos(hb); / qa 和 qb 分別指向 Pa 和 Pb 中當(dāng)前結(jié)點(現(xiàn)為第一個結(jié)點) while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa) / Pa 和 Pb 均非空且 ha 沒指向尾結(jié)點 (qa!=0) a=GetCurE

16、lem(qa);b=GetCurElem(qb); / a 和 b 為兩表中當(dāng)前比較元素 switch(cmp(a,b)case -1:ha=qa; / 多項式 Pa 中當(dāng)前結(jié)點的指數(shù)值小 qa=NextPos(ha); / ha 和 qa 均向后移一個結(jié)點 break;case 0: qa->data.coef+=qb->data.coef;/兩者的指數(shù)值相等，修改Pa當(dāng)前結(jié)點的系數(shù)值if(qa->data.coef=0)/系數(shù)和為0,則刪除多項式Pa中當(dāng)前結(jié)點DelFirst(Pa，ha，&qa);FreeNode(&qa); elseha=qa;DelF

17、irst(Pb,hb,&qb);FreeNode(&qb);qb=NextPos(hb);qa=NextPos(ha);break;case 1:DelFirst(Pb,hb,&qb); / 多項式 Pb 中當(dāng)前結(jié)點的指數(shù)值小 InsFirst(Pa,ha,qb);ha=ha->next;qb=NextPos(hb);if(!ListEmpty(*Pb)(*Pb).tail=hb;Append(Pa,qb); / 鏈接 Pb 中剩余結(jié)點DestroyPolyn(Pb); / 銷毀 Pb/ 另一種多項式加法的算法:Pa=Pa+Pb, 并銷毀一元多項式 Pbvoid

18、AddPolyn1(polynomial *Pa,polynomial *Pb)Position qb;term b;qb=GetHead(*Pb); / qb 指向 Pb 的頭結(jié)點 qb=qb->next; / qb 指向 Pb 的第一個結(jié)點 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)

19、 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)

20、; 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.t

21、ail;(*Pa).len=Pc.len;/ 打印輸出一元多項式 Pvoid PrintPolyn(polynomial P)Link q;q=P.head->next; / q 指向第一個結(jié)點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");/ 構(gòu)建一個多項式printf(&qu

22、ot; 請輸入第一個一元多項式的非零項的個數(shù)： "); scanf("%d",&m);CreatPolyn(&p,m);/ 構(gòu)建另一個多項式printf(" 請輸入第二個一元多項式的非零項的個數(shù)： "); scanf("%d",&m);CreatPolyn(&q,m);/ 多項式相加AddPolyn(&p,&q);printf(" 兩個一元多項式相加的結(jié)果： n");/ 打印多項式PrintPolyn(p);/ 使用另一種多項式相加的方法printf(&qu

23、ot;n 兩個一元多項式相加 ( 另一種方法 )n"); printf(" 請輸入第三個一元多項式的非零項的個數(shù)： "); scanf("%d",&m);CreatPolyn(&p,m);printf(" 請輸入第四個一元多項式的非零項的個數(shù)： "); scanf("%d",&m);CreatPolyn(&q,m);/ 多項式相加的另一種方法 AddPolyn1(&p,&q);printf(" 兩個一元多項式相加的結(jié)果 (另一種方法 ) ：n&qu

24、ot;); 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(" 兩個一元多項式相減的結(jié)果： n"); PrintPolyn(p);/ 多項式相乘printf("n 兩個一元多項式相乘 n");printf(" 請輸入第七個個一元多項式的非零項的個數(shù)： "); scanf("%d",&m);CreatPolyn(&p,m);printf(" 請輸入第八個一元多項式的非零項的個數(shù)： "); scanf("%d",&m)