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

數(shù)據(jù)結構C語言版 抽象數(shù)據(jù)類型Polynomial一元多項式的實現(xiàn)文庫.txt生活是過出來的，不是想出來的。放得下的是曾經，放不下的是記憶。無論我在哪里，我離你都只有一轉身的距離。/*數(shù)據(jù)結構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 / 結點類型 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)data.expndata,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;inext;/ 已知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);/多項式相乘MultiplyPoly