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

1、/*數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版 抽象數(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)作為L(zhǎng)inkList的數(shù)據(jù)元素 float coef;/ 系數(shù) int expn;/ 指數(shù) term, ElemType;/ 兩個(gè)類型名:term用于本ADT,ElemType為L(zhǎng)inkList的數(shù)據(jù)對(duì)象名 typedef struct LNode / 結(jié)點(diǎn)類型 ElemType

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

3、on PriorPos(LinkList L,Link p)Link q;q=L.head-next;if(q=p) / 無(wú)前驅(qū) return NULL;elsewhile(q-next!=p) / q不是p的直接前驅(qū) q=q-next;return q;/ 若升序鏈表L中存在與e滿足判定函數(shù)compare()取值為0的元素，則q指示L中/ 第一個(gè)值為e的結(jié)點(diǎn)的位置，并返回1；否則q指示第一個(gè)與e滿足判定函數(shù) / compare()取值0的元素的前驅(qū)的位置。并返回0。（用于一元多項(xiàng)式） 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的一個(gè)結(jié)點(diǎn)，把h當(dāng)做頭結(jié)點(diǎn)，刪除鏈表中的第一個(gè)結(jié)點(diǎn)并以q返回。 / 若鏈表為空(h指向尾結(jié)點(diǎn))，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é)點(diǎn) (*L).tail=h; / 修改尾指針 (*L).len-;return 1;elsereturn 0; / 鏈表空 / 分配由p指向的值為e的結(jié)點(diǎn)，并返回1；若分配失敗。則返回0int MakeNode(Link *p,ElemType e)*p = (Link)malloc(sizeof(LNode);/動(dòng)態(tài)分配一個(gè)Link空間if(!*p)return 0;(*p)-data = e;/ 賦值return 1;/ 釋放p所指結(jié)點(diǎn)void FreeNode(Link *p) free(*p);/老規(guī)矩，先釋放存儲(chǔ)空

6、間，然后置空*p=NULL;/ h指向L的一個(gè)結(jié)點(diǎn)，把h當(dāng)做頭結(jié)點(diǎn)，將s所指結(jié)點(diǎn)插入在第一個(gè)結(jié)點(diǎn)之前 / 頭結(jié)點(diǎn)沒(méi)有數(shù)據(jù)域，而第一個(gè)結(jié)點(diǎn)是h-nextint InsFirst(LinkList *L,Link h,Link s) s-next = h-next;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

7、e,int(* compare)(term,term)Position q,s;if(LocateElemP(*L,e,&q,compare) / L中存在該指數(shù)項(xiàng) 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無(wú)前驅(qū) s=(*L).head;DelFirst(L,s,&q);FreeNode(&q);return 1;else / 生成該指數(shù)項(xiàng)并插入鏈表 if(MakeNode(&s,e) / 生成結(jié)點(diǎn)成功 In

8、sFirst(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;elsereturn (a.expn-b.expn)/abs(a.expn-b.expn);/ 構(gòu)造一個(gè)空的線性鏈表int InitList(LinkList *L) Link p;p=(Link)malloc(sizeof(LNode); / 生成頭結(jié)點(diǎn) if(p)p-next=NULL;/將頭尾結(jié)點(diǎn)都分配好，并將其下一

9、結(jié)點(diǎn)置空(*L).head=(*L).tail=p;(*L).len=0;/初始為0return 1;else/ 分配失敗返回return 0;/ 算法2.22 P42/ 輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表P void CreatPolyn(polynomial *P,int m)Position q,s;term e;int i;InitList(P);printf(請(qǐng)依次輸入%d個(gè)系數(shù)，指數(shù)：（空格）n,m);for(i=1;inext;/ 已知p指向線性鏈表中的一個(gè)結(jié)點(diǎn)，返回p所指結(jié)點(diǎn)中數(shù)據(jù)元素的值ElemType GetCurElem(Link p) return p-

10、data;/ 將指針s(s-data為第一個(gè)數(shù)據(jù)元素)所指(彼此以指針相鏈,以NULL結(jié)尾)的 / 一串結(jié)點(diǎn)鏈接在線性鏈表L的最后一個(gè)結(jié)點(diǎn)之后,并改變鏈表L的尾指針指向新 / 的尾結(jié)點(diǎn) int Append(LinkList *L,Link s)int i=1;/記錄s為頭的串結(jié)點(diǎn)個(gè)數(shù)(*L).tail-next=s;/尾結(jié)點(diǎn)指向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é)點(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;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é)點(diǎn)并沒(méi)有釋放） FreeNode(&(*L).head);/再釋放頭尾結(jié)點(diǎn)(*L).tail=NULL;(*L).len=0;return 1;/ 算法2.23 P43 / 多項(xiàng)式加法:Pa=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分別指

13、向Pa和Pb中當(dāng)前結(jié)點(diǎn)（現(xiàn)為第一個(gè)結(jié)點(diǎn)） while(!ListEmpty(*Pa)&!ListEmpty(*Pb)&qa) / Pa和Pb均非空且ha沒(méi)指向尾結(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均向后移一個(gè)結(jié)點(diǎn) break;case 0:qa-data.coef+=qb-data.coef;/ 兩者的指數(shù)值相等,修改Pa當(dāng)前結(jié)點(diǎn)的系數(shù)值 if(qa-data.coef

14、=0) / 系數(shù)和為0，則刪除多項(xiàng)式Pa中當(dāng)前結(jié)點(diǎn) 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); / 多項(xiàng)式Pb中當(dāng)前結(jié)點(diǎn)的指數(shù)值小 InsFirst(Pa,ha,qb);ha=ha-next;qb=NextPos(hb);if(!ListEmpty(*Pb)(*Pb).tail=hb;Append(Pa,qb); / 鏈接Pb中剩余結(jié)點(diǎn) DestroyPo

15、lyn(Pb); / 銷毀Pb / 另一種多項(xiàng)式加法的算法:Pa=Pa+Pb,并銷毀一元多項(xiàng)式Pbvoid AddPolyn1(polynomial *Pa,polynomial *Pb) Position qb;term b;qb=GetHead(*Pb);/ qb指向Pb的頭結(jié)點(diǎn) qb=qb-next;/ qb指向Pb的第一個(gè)結(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)Po

16、sition p;p=Pa.head;while(p-next)p=p-next;p-data.coef*=-1;/ 多項(xiàng)式減法:Pa=Pa-Pb,并銷毀一元多項(xiàng)式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=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、打印輸出一元多項(xiàng)式Pvoid PrintPolyn(polynomial P) Link q;q=P.head-next; / q指向第一個(gè)結(jié)點(diǎn) 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;/ 多項(xiàng)式相加printf(兩個(gè)一元多項(xiàng)式相加n); /構(gòu)建一個(gè)多項(xiàng)式printf(請(qǐng)輸入第一個(gè)一元多項(xiàng)式的非零項(xiàng)的個(gè)數(shù)：);scanf(%d,&m);CreatPolyn(&p,m);/構(gòu)建另一個(gè)多項(xiàng)式printf(請(qǐng)輸入第二個(gè)一元多項(xiàng)式的非零項(xiàng)

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

20、元多項(xiàng)式相加的結(jié)果(另一種方法)：n);PrintPolyn(p);/ 多項(xiàng)式相減 printf(n兩個(gè)一元多項(xiàng)式相減n);printf(請(qǐng)輸入第五個(gè)個(gè)一元多項(xiàng)式的非零項(xiàng)的個(gè)數(shù)：);scanf(%d,&m);CreatPolyn(&p,m);printf(請(qǐng)輸入第六個(gè)一元多項(xiàng)式的非零項(xiàng)的個(gè)數(shù)：);scanf(%d,&m);CreatPolyn(&q,m);/ 多項(xiàng)式相減SubtractPolyn(&p,&q);printf(兩個(gè)一元多項(xiàng)式相減的結(jié)果：n);PrintPolyn(p);/多項(xiàng)式相乘printf(n兩個(gè)一元多項(xiàng)式相乘n);printf(請(qǐng)輸入第七個(gè)個(gè)一元多項(xiàng)式的非零項(xiàng)的個(gè)數(shù)：);s

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

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