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

《數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)文庫》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)文庫（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、/*數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn) P42-43 編譯環(huán)境：Dev-C+ 4.9.9.2日期：2011年2月10日 */#include #include #include / 抽象數(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 / 結(jié)點類型 ElemType

2、data;struct LNode *next;LNode,*Link,*Position;typedef struct _LinkList / 鏈表類型 Link head,tail;/ 分別指向線性鏈表中的頭結(jié)點和最后一個結(jié)點 int len;/ 指示當(dāng)前線性鏈表中數(shù)據(jù)元素的個數(shù) LinkList;typedef LinkList polynomial;#define DestroyPolyn DestroyList #define PolynLength ListLength / 已知p指向線性鏈表L中的一個結(jié)點，返回p所指結(jié)點的直接前驅(qū)的位置 / 若無前驅(qū)，則返回NULL Positi

3、on PriorPos(LinkList L,Link p)Link q;q=L.head-next;if(q=p) / 無前驅(qū) return NULL;elsewhile(q-next!=p) / q不是p的直接前驅(qū) q=q-next;return q;/ 若升序鏈表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(

4、*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的一個結(jié)點，把h當(dāng)做頭結(jié)點，刪除鏈表中的第一個結(jié)點并以q返回。 / 若鏈表為空(h指向尾結(jié)點)，q=NULL，返回0 int DelFirst(LinkList *L,Link h,Link *q) *q=h-next;if(*q) / 鏈表非空

5、 h-next=(*q)-next;if(!h-next)/ 刪除尾結(jié)點 (*L).tail=h; / 修改尾指針 (*L).len-;return 1;elsereturn 0; / 鏈表空 / 分配由p指向的值為e的結(jié)點，并返回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所指結(jié)點void FreeNode(Link *p) free(*p);/老規(guī)矩，先釋放存儲空

6、間，然后置空*p=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 OrderInsertMerge(LinkList *L,ElemType

7、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;else / 生成該指數(shù)項并插入鏈表 if(MakeNode(&s,e) / 生成結(jié)點成功 In

8、sFirst(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)malloc(sizeof(LNode); / 生成頭結(jié)點 if(p)p-next=NULL;/將頭尾結(jié)點都分配好，并將其下一

9、結(jié)點置空(*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;inext;/ 已知p指向線性鏈表中的一個結(jié)點，返回p所指結(jié)點中數(shù)據(jù)元素的值ElemType GetCurElem(Link p) return p-

10、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é)點指向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

11、 1;/ 將線性鏈表L重置為空表（頭尾結(jié)點相同為空表），并釋放原鏈表的結(jié)/ 點空間，不釋放頭尾結(jié)點，只是置空而已 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) ClearL

12、ist(L);/ 清空鏈表（頭尾結(jié)點并沒有釋放） FreeNode(&(*L).head);/再釋放頭尾結(jié)點(*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的頭結(jié)點 qa=NextPos(ha);qb=NextPos(hb); / qa和qb分別指

13、向Pa和Pb中當(dāng)前結(jié)點（現(xiàn)為第一個結(jié)點） while(!ListEmpty(*Pa)&!ListEmpty(*Pb)&qa) / Pa和Pb均非空且ha沒指向尾結(jié)點(qa!=0) a=GetCurElem(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

14、=0) / 系數(shù)和為0，則刪除多項式Pa中當(dāng)前結(jié)點 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中當(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é)點 DestroyPo

15、lyn(Pb); / 銷毀Pb / 另一種多項式加法的算法:Pa=Pa+Pb,并銷毀一元多項式Pbvoid 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)Po

16、sition 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=Get

17、Head(*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;/

18、打印輸出一元多項式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(請輸入第一個一元多項式的非零項的個數(shù)：);scanf(%d,&m);CreatPolyn(&p,m);/構(gòu)建另一個多項式printf(請輸入第二個一元多項式的非零項

19、的個數(shù)：);scanf(%d,&m);CreatPolyn(&q,m);/多項式相加AddPolyn(&p,&q);printf(兩個一元多項式相加的結(jié)果：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(兩個一

20、元多項式相加的結(jié)果(另一種方法)：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(兩個一元多項式相減的結(jié)果：n);PrintPolyn(p);/多項式相乘printf(n兩個一元多項式相乘n);printf(請輸入第七個個一元多項式的非零項的個數(shù)：);s

21、canf(%d,&m);CreatPolyn(&p,m);printf(請輸入第八個一元多項式的非零項的個數(shù)：);scanf(%d,&m);CreatPolyn(&q,m);/多項式相乘MultiplyPolyn(&p,&q);printf(兩個一元多項式相乘的結(jié)果：n);PrintPolyn(p);/銷毀多項式DestroyPolyn(&p);DestroyPolyn(&q);system(pause);return 0;/*輸出效果：兩個一元多項式相加請輸入第一個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 1 1請輸入第二個一元多項式的非零項的個數(shù)：2請依次輸入2

22、個系數(shù)，指數(shù)：（空格）-1 0 -2 1兩個一元多項式相加的結(jié)果： 系數(shù) 指數(shù)-1.000000 1兩個一元多項式相加(另一種方法)請輸入第三個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 1 1請輸入第四個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）-1 0 -2 1兩個一元多項式相加的結(jié)果(另一種方法)： 系數(shù) 指數(shù)-1.000000 1兩個一元多項式相減請輸入第五個個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）1 0 2 1請輸入第六個一元多項式的非零項的個數(shù)：2請依次輸入2個系數(shù)，指數(shù)：（空格）-2 0 -1 1兩個一元多項式相減的結(jié)果： 系數(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兩個一元多項式相乘的結(jié)果： 系數(shù) 指數(shù)1.000000 02.000000 11.000000 2請按任意鍵繼續(xù). . .*/