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

1、/* 數(shù)據(jù)結(jié)構(gòu)C語言版 抽象數(shù)據(jù)類型Polynomial一元多項(xiàng)式的實(shí)現(xiàn) P42-43 編譯環(huán)境：Dev-C++ 4.9.9.2 日期：2011年2月10日 */ #include #include #include // 抽象數(shù)據(jù)類型Polynomial一元多項(xiàng)式的實(shí)現(xiàn) typedef struct // 項(xiàng)的表示,多項(xiàng)式的項(xiàng)作為LinkList的數(shù)據(jù)元素 { float coef; // 系數(shù) int expn; // 指數(shù) }term, ElemType; //

2、 兩個類型名:term用于本ADT,ElemType為LinkList的數(shù)據(jù)對象名 typedef struct LNode // 結(jié)點(diǎn)類型 { ElemType data; struct LNode *next; }LNode,*Link,*Position; typedef struct _LinkList // 鏈表類型 { Link head,tail; // 分別指向線性鏈表中的頭結(jié)點(diǎn)和最后一個結(jié)點(diǎn) int len; // 指示當(dāng)前線性鏈表中數(shù)據(jù)元素的個數(shù) }LinkList; typedef LinkList polynomia

3、l; #define DestroyPolyn DestroyList #define PolynLength ListLength // 已知p指向線性鏈表L中的一個結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接前驅(qū)的位置 // 若無前驅(qū)，則返回NULL Position 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; r

4、eturn q; } } // 若升序鏈表L中存在與e滿足判定函數(shù)compare()取值為0的元素，則q指示L中 // 第一個值為e的結(jié)點(diǎn)的位置，并返回1；否則q指示第一個與e滿足判定函數(shù) // compare()取值>0的元素的前驅(qū)的位置。并返回0。（用于一元多項(xiàng)式） int LocateElemP(LinkList L,ElemType e,Position *q, int(*compare)(ElemType,ElemType)) { Link p=L.head,pp; do { pp=p; p=p->next; }while

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

6、h,Link *q) { *q=h->next; if(*q) // 鏈表非空 { h->next=(*q)->next; if(!h->next) // 刪除尾結(jié)點(diǎn) (*L).tail=h; // 修改尾指針 (*L).len--; return 1; } else return 0; // 鏈表空 } // 分配由p指向的值為e的結(jié)點(diǎn)，并返回1；若分配失敗。則返回0 int MakeNode(Link *p,ElemType e) { *p = (Link)malloc(sizeof(LNode));

7、//動態(tài)分配一個Link空間 if(!*p) return 0; (*p)->data = e; // 賦值 return 1; } // 釋放p所指結(jié)點(diǎn) void FreeNode(Link *p) { free(*p); //老規(guī)矩，先釋放存儲空間，然后置空 *p=NULL; } // h指向L的一個結(jié)點(diǎn)，把h當(dāng)做頭結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在第一個結(jié)點(diǎn)之前 // 頭結(jié)點(diǎn)沒有數(shù)據(jù)域，而第一個結(jié)點(diǎn)是h->next int InsFirst(LinkList *L,Link h,Link s) { s->next = h->next;

8、 h->next=s; if(h==(*L).tail) // 如果h指向尾結(jié)點(diǎn) (*L).tail=h->next; // 修改尾指針 (*L).len++; return 1; } // 按有序判定函數(shù)compare()的約定，將值為e的結(jié)點(diǎn)插入或合并到升序 // 鏈表L的適當(dāng)位置 int OrderInsertMerge(LinkList *L,ElemType e,int(* compare)(term,term)) { Position q,s; if(LocateElemP(*L,e,&q,compare)) // L中存在該指數(shù)項(xiàng)

9、 { q->data.coef+=e.coef; // 改變當(dāng)前結(jié)點(diǎn)系數(shù)的值 if(!q->data.coef) // 系數(shù)為0 { // 刪除多項(xiàng)式L中當(dāng)前結(jié)點(diǎn) s = PriorPos(*L,q); // s為當(dāng)前結(jié)點(diǎn)的前驅(qū) if(!s) // q無前驅(qū) s=(*L).head; DelFirst(L,s,&q); FreeNode(&q); } return 1; } else // 生成該指數(shù)項(xiàng)并插入鏈表 if(MakeNode(&s,e)) // 生成結(jié)點(diǎn)成功 {

10、 InsFirst(L,q,s); return 1; } else // 生成結(jié)點(diǎn)失敗 return 0; } // 依a的指數(shù)值<、=或>b的指數(shù)值，分別返回-1、0或+1 // CreatPolyn()的實(shí)參 int cmp(term a,term b) { if(a.expn==b.expn) return 0; else return (a.expn-b.expn)/abs(a.expn-b.expn); } // 構(gòu)造一個空的線性鏈表 int InitList(LinkList *L) {

11、 Link p; p=(Link)malloc(sizeof(LNode)); // 生成頭結(jié)點(diǎn) if(p) { p->next=NULL; //將頭尾結(jié)點(diǎn)都分配好，并將其下一結(jié)點(diǎn)置空 (*L).head=(*L).tail=p; (*L).len=0; //初始為0 return 1; } else // 分配失敗返回 return 0; } // 算法2.22 P42 // 輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表P void CreatPolyn(polynomial *P,int m) { Posi

12、tion q,s; term e; int i; InitList(P); printf("請依次輸入%d個系數(shù)，指數(shù)：（空格）\n",m); for(i=1;i<=m;++i) { // 依次輸入m個非零項(xiàng)（可按任意順序） scanf("%f%d",&e.coef,&e.expn); // 當(dāng)前鏈表中不存在該指數(shù)項(xiàng),cmp是實(shí)參 if(!LocateElemP(*P,e,&q,cmp)) if(MakeNode(&s,e)) // 生成結(jié)點(diǎn)并插入鏈表 InsFirst(P,q,s); } } //

13、 返回線性鏈表L中頭結(jié)點(diǎn)的位置 Position GetHead(LinkList L) { return L.head; } // 已知p指向線性鏈表L中的一個結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)的直接后繼的位置 // 若無后繼，則返回NULL Position NextPos(Link p) { return p->next; } // 已知p指向線性鏈表中的一個結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值 ElemType GetCurElem(Link p) { return p->data; } // 將指針s(s->data為第一個數(shù)據(jù)元素

14、)所指(彼此以指針相鏈,以NULL結(jié)尾)的 // 一串結(jié)點(diǎn)鏈接在線性鏈表L的最后一個結(jié)點(diǎn)之后,并改變鏈表L的尾指針指向新 // 的尾結(jié)點(diǎn) int Append(LinkList *L,Link s) { int i=1; //記錄s為頭的串結(jié)點(diǎn)個數(shù) (*L).tail->next=s; //尾結(jié)點(diǎn)指向s while(s->next) { s=s->next; i++; } (*L).tail=s; (*L).len+=i; return 1; } // 若線性鏈表L為空表，則返回1，否則返回0 int ListEmpty(L

15、inkList L) { if(L.len) return 0; else return 1; } // 將線性鏈表L重置為空表（頭尾結(jié)點(diǎn)相同為空表），并釋放原鏈表的結(jié) // 點(diǎn)空間，不釋放頭尾結(jié)點(diǎn)，只是置空而已 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;

16、 free(q); q=p; } free(q); (*L).tail=(*L).head; (*L).len=0; } return 1; } // 銷毀線性鏈表L，L不再存在 int DestroyList(LinkList *L) { ClearList(L); // 清空鏈表（頭尾結(jié)點(diǎn)并沒有釋放） FreeNode(&(*L).head); //再釋放頭尾結(jié)點(diǎn) (*L).tail=NULL; (*L).len=0; return 1; } // 算法2.23 P43 // 多項(xiàng)式加法:Pa=

17、Pa+Pb,并銷毀一元多項(xiàng)式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é)點(diǎn) qa=NextPos(ha); qb=NextPos(hb); // qa和qb分別指向Pa和Pb中當(dāng)前結(jié)點(diǎn)（現(xiàn)為第一個結(jié)點(diǎn)） while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa) { // Pa和Pb均非空且h

18、a沒指向尾結(jié)點(diǎn)(qa!=0) a=GetCurElem(qa); b=GetCurElem(qb); // a和b為兩表中當(dāng)前比較元素 switch(cmp(a,b)) { case -1: ha=qa; // 多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 qa=NextPos(ha); // ha和qa均向后移一個結(jié)點(diǎn) break; case 0: qa->data.coef+=qb->data.coef; // 兩者的指數(shù)值相等,修改Pa當(dāng)前結(jié)點(diǎn)的系數(shù)值 if(qa->data.coef==0) // 系數(shù)和為

19、0，則刪除多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn) { DelFirst(Pa,ha,&qa); FreeNode(&qa); } else ha=qa; DelFirst(Pb,hb,&qb); FreeNode(&qb); qb=NextPos(hb); qa=NextPos(ha); break; case 1: DelFirst(Pb,hb,&qb); // 多項(xiàng)式Pb中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 InsFirst(Pa,ha,qb); ha=ha->next; qb=Next

20、Pos(hb); } } if(!ListEmpty(*Pb)) { (*Pb).tail=hb; Append(Pa,qb); // 鏈接Pb中剩余結(jié)點(diǎn) } DestroyPolyn(Pb); // 銷毀Pb } // 另一種多項(xiàng)式加法的算法:Pa=Pa+Pb,并銷毀一元多項(xiàng)式Pb void AddPolyn1(polynomial *Pa,polynomial *Pb) { Position qb; term b; qb=GetHead(*Pb); // qb指向Pb的頭結(jié)點(diǎn) qb=qb->next; // qb指

21、向Pb的第一個結(jié)點(diǎn) while(qb) { b=GetCurElem(qb); OrderInsertMerge(Pa,b,cmp); qb=qb->next; } DestroyPolyn(Pb); // 銷毀Pb } // 一元多項(xiàng)式系數(shù)取反 void Opposite(polynomial Pa) { Position p; p=Pa.head; while(p->next) { p=p->next; p->data.coef*=-1; } } // 多項(xiàng)式減法:Pa=Pa-Pb,并銷毀一元多項(xiàng)式

22、Pb void SubtractPolyn(polynomial *Pa,polynomial *Pb) { Opposite(*Pb); AddPolyn(Pa,Pb); } // 多項(xiàng)式乘法:Pa=PaPb,并銷毀一元多項(xiàng)式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) {

23、 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.

24、head; (*Pa).tail=Pc.tail; (*Pa).len=Pc.len; } // 打印輸出一元多項(xiàng)式P void PrintPolyn(polynomial P) { Link q; q=P.head->next; // q指向第一個結(jié)點(diǎn) printf(" 系數(shù) 指數(shù)\n"); while(q) { printf("%f %d\n",q->data.coef,q->data.expn); q=q->next; } } int main() { polynomial p,q; int m;

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

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

27、多項(xiàng)式相減 printf("\n兩個一元多項(xiàng)式相減\n"); printf("請輸入第五個個一元多項(xiàng)式的非零項(xiàng)的個數(shù)："); scanf("%d",&m); CreatPolyn(&p,m); printf("請輸入第六個一元多項(xiàng)式的非零項(xiàng)的個數(shù)："); scanf("%d",&m); CreatPolyn(&q,m); // 多項(xiàng)式相減 SubtractPolyn(&p,&q); printf("兩個一元多項(xiàng)式相減的結(jié)果：\n"); PrintPolyn(p); //多項(xiàng)式相乘 printf("\n兩個一元多項(xiàng)式相乘\n");

28、 printf("請輸入第七個個一元多項(xiàng)式的非零項(xiàng)的個數(shù)："); scanf("%d",&m); CreatPolyn(&p,m); printf("請輸入第八個一元多項(xiàng)式的非零項(xiàng)的個數(shù)："); scanf("%d",&m); CreatPolyn(&q,m); //多項(xiàng)式相乘 MultiplyPolyn(&p,&q); printf("兩個一元多項(xiàng)式相乘的結(jié)果：\n"); PrintPolyn(p); //銷毀多項(xiàng)式 DestroyPolyn(&p); DestroyPolyn(&q); system("pause");

29、return 0; } /* 輸出效果： 兩個一元多項(xiàng)式相加 請輸入第一個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） 1 0 1 1 請輸入第二個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） -1 0 -2 1 兩個一元多項(xiàng)式相加的結(jié)果： 系數(shù) 指數(shù) -1.000000 1 兩個一元多項(xiàng)式相加(另一種方法) 請輸入第三個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） 1 0 1 1 請輸入第四個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） -1 0 -

30、2 1 兩個一元多項(xiàng)式相加的結(jié)果(另一種方法)： 系數(shù) 指數(shù) -1.000000 1 兩個一元多項(xiàng)式相減 請輸入第五個個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） 1 0 2 1 請輸入第六個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） -2 0 -1 1 兩個一元多項(xiàng)式相減的結(jié)果： 系數(shù) 指數(shù) 3.000000 0 3.000000 1 兩個一元多項(xiàng)式相乘 請輸入第七個個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） 1 0 1 1 請輸入第八個一元多項(xiàng)式的非零項(xiàng)的個數(shù)：2 請依次輸入2個系數(shù)，指數(shù)：（空格） 1 0 1 1 兩個一元多項(xiàng)式相乘的結(jié)果： 系數(shù) 指數(shù) 1.000000 0 2.000000 1 1.000000 2 請按任意鍵繼續(xù). . . */