數(shù)據(jù)結構四則運算C語言.doc

#include#include#includetypedef struct PolyNode int exp; /x指數(shù) float coef; /x系數(shù) int exp1; /y指數(shù) int exp2; /z指數(shù) PolyNode* next; PolyNode,*PolyList;PolyList Create()/構建一元多項式PolyNode *s,*rear,*head;int e=1; /指數(shù)float c=1; /系數(shù)int n=1; /計數(shù)器head=(PolyNode*) malloc(sizeof(PolyNode);rear=head;/輸入多項式(含括號)，出現(xiàn)系數(shù)為0強制退出if(getchar()=()scanf(%fx%d,&c,&e);while(fabs(c)1e-3) s=(PolyNode*)malloc(sizeof(PolyNode);s-exp=e;s-coef=c;s-exp1=0;s-exp2=0;rear-next=s;rear=s; if(getchar()=)break;scanf(%fx%d,&c,&e);rear-next=NULL;return head;PolyList Create1()/構建二元多項式PolyNode *s,*rear,*head;int e,e1; /指數(shù)float c; /系數(shù)int n=1; /計數(shù)器head=(PolyNode*) malloc(sizeof(PolyNode);rear=head;/一次性輸入多項式(含括號)，出現(xiàn)系數(shù)為0強制退出if(getchar()=()scanf(%fx%dy%d,&c,&e,&e1);while(fabs(c)1e-3) s=(PolyNode*)malloc(sizeof(PolyNode);s-exp=e;s-coef=c;s-exp1=e1;rear-next=s;rear=s;if(getchar()=)break;scanf(%fx%dy%d,&c,&e,&e1);rear-next=NULL;return head;PolyList Create2()/構建三元多項式PolyNode *s,*rear,*head;int e,e1,e2; /指數(shù)float c; /系數(shù)int n=1; /計數(shù)器head=(PolyNode*) malloc(sizeof(PolyNode);rear=head;/一次性輸入多項式(含括號)，出現(xiàn)系數(shù)為0強制退出if(getchar()=()scanf(%fx%dy%dz%d,&c,&e,&e1,&e2);while(fabs(c)1e-3) s=(PolyNode*)malloc(sizeof(PolyNode);s-exp=e;s-coef=c;s-exp1=e1;s-exp2=e2;rear-next=s;rear=s;if(getchar()=)break;scanf(%fx%dy%dz%d,&c,&e,&e1,&e2);rear-next=NULL;return head;void Merge(PolyList Poly)/和并同類項PolyNode *p,*q,*rear,*pre,*temp; rear=Poly;p=Poly-next ;while(rear-next!=NULL) q=p-next;pre=p;temp=p;while(q)if(p-exp=q-exp)&(p-exp1=q-exp1)&(p-exp2=q-exp2) /指數(shù)相同則合并 p-coef+=q-coef;if(fabs(p-coef)1e-3)pre-next=q-next;temp = q;q = temp-next;free(temp);else /兩項系數(shù)和為0，釋放結點p和qrear-next = p-next;temp = p;p = temp-next;free(temp);pre-next = q-next;temp = q; q = temp-next;free(temp);elsepre= q;q = q-next; /指數(shù)不等，指針q后移/與p指數(shù)相同的節(jié)點合并完畢，或者沒有找到，p后移rear = p;p = rear-next;rear-next = NULL;void Sort(PolyList Poly) /將多項式按x降冪排列PolyList rear , p ,temp , prior;if(!Poly-next) return; /若多項式為空，返回Merge(Poly);/合并同類項rear = Poly;int exp;/記錄當前啊搜索項中的最小的x指數(shù) while(rear-next!=NULL)/遍歷整個鏈表exp = rear-next-exp;p = rear-next ;prior = rear;temp = prior-next ;while(p!=NULL)/排序算法if(p-expexp)exp = p-exp ; temp = p ;p = temp-next ;else p = p-next ; if(rear-next-next =NULL) return; /p為最后一個元素且指數(shù)最小，提前返回while(prior-next != temp) prior = prior-next;prior-next = temp-next;temp-next = rear-next;rear-next = temp;rear = rear-next;void Display(PolyList Poly)/輸出一元多項式if(Poly = NULL)printf(錯誤n);return;PolyNode *p=Poly-next;if(p = NULL)printf(錯誤n); return; /鏈表為空while(p-next!=NULL)if(fabs(p-coef)1e-3) if(fabs(p-next-coef)1e-3&p-next-coef0) if(p-exp!=0)printf(%.1f*x%d+,p-coef,p-exp); else printf(%.1f+,p-coef);else if(p-exp!=0) printf(%.1f*x%d,p-coef,p-exp); else printf(%.1f,p-coef);else /printf(.);/輸出分割點 break; p = p-next ; if(fabs(p-coef)1e-6)if(p-exp!=0)printf(%.1f*x%d,p-coef,p-exp); else printf(%.1f,p-coef);/模printf(n);void Display1(PolyList Poly)/輸出二元多項式if(Poly = NULL) printf(無數(shù)據(jù)n);return;PolyNode *p=Poly-next ;if(p = NULL)printf(錯誤n); return; /如果鏈表為空提前退出while(p-next!=NULL)if(fabs(p-coef)1e-3) if(fabs(p-next-coef)1e-3) printf(%.1f*x%dy%d + ,p-coef,p-exp,p-exp1); else printf(%.1f*x%dy%d ,p-coef,p-exp,p-exp1);else printf(.);/輸出分割點p = p-next ;if(fabs(p-coef)1e-3)printf(%.1f*x%dy%d , p-coef , p-exp, p-exp1);printf(n);void Display3(PolyList Poly)/輸出三元多項式if(Poly = NULL) printf(無數(shù)據(jù)n);return;PolyNode *p=Poly-next ;if(p = NULL)printf(錯誤n); return; /如果鏈表為空提前退出while(p-next!=NULL)if(fabs(p-coef)1e-3) if(fabs(p-next-coef)1e-3&p-next-coef0) printf(%.1f*x%dy%dz%d+,p-coef,p-exp,p-exp1,p-exp2); else printf(%.1f*x%dy%dz%d,p-coef,p-exp,p-exp1,p-exp2);else printf(.);/輸出分割點p = p-next ;if(fabs(p-coef)1e-3)printf(%.1f*x%dy%dz%d, p-coef , p-exp, p-exp1, p-exp2);printf(n);void Display2(PolyList Poly)/一元多項式取模計算的輸出if(Poly = NULL)printf(無數(shù)據(jù)n);return;PolyNode *p=Poly-next ;if(p = NULL)printf(錯誤n); return; /如果鏈表為空提前退出while(p-next!=NULL)if(fabs(p-coef)1e-3);else printf(取模結果為:);p = p-next ;if(fabs(p-coef)1e-6)if(p-exp!=0)printf(%.1f*x%d,p-coef,p-exp); else printf(%.1f,p-coef);/模if(fabs(p-coef)=0)printf(0);printf(n);void Destroy(PolyList L)/銷毀 PolyNode *q1,*q2; q1=L-next; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next;/多項式相加，結果存到PolyC中，并返回頭指針PolyList Add(PolyList PolyA,PolyList PolyB)PolyList PolyC;Sort(PolyA);Sort(PolyB);float sum=0;/存儲兩項系數(shù)和PolyNode *pa , *pb , *rear , *s ;PolyC = (PolyNode *)malloc(sizeof(PolyNode);pa = PolyA-next;pb = PolyB-next;rear = PolyC;rear-next = NULL;while(pa&pb)/長度相同部分的計算并連接至新鏈表if(pa-exp=pb-exp)&(pa-exp1=pb-exp1)&(pa-exp2=pb-exp2)/三指數(shù)均相同sum = pa-coef+pb-coef;if(fabs(sum)1e-3) /如果兩兩系數(shù)不為0，則將兩項和存入s中，并插入PolyC尾部s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = sum;s-exp = pa-exp;s-exp1 = pa-exp1;s-exp2 = pa-exp2;rear-next = s;rear = s;/pa,pb指針后移pa = pa-next;pb = pb-next;else if(pa-exppb-exp) /若pa的x指數(shù)大于pb指數(shù)，將pa結點副本插入到PolyC尾部s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = pa-coef;s-exp = pa-exp;s-exp1 = pa-exp1;s-exp2 = pa-exp2;rear-next = s ;rear = s ;pa = pa-next;else /若pb的x指數(shù)大于pa指數(shù)，將pb結點副本插入到PolyC尾部s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = pb-coef;s-exp = pb-exp;s-exp1 = pb-exp1;s-exp2 = pa-exp2;rear-next = s;pb = pb-next;rear = s ;/長度大的鏈表數(shù)據(jù)拷貝while(pa)/pb結束拷貝pa數(shù)據(jù)s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = pa-coef;s-exp = pa-exp;s-exp1 = pa-exp1;s-exp2 = pa-exp2;rear-next = s;pa = pa-next;rear = s ;while(pb)/pa結束至拷貝pb數(shù)據(jù)s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = pb-coef;s-exp = pb-exp;s-exp1 = pb-exp1;s-exp2 = pa-exp2;rear-next = s;pb = pb-next;rear=s;rear-next=NULL;return PolyC;/多項式相減，返回結果PolyC頭指針PolyList Sub(PolyList PolyA , PolyList PolyB)PolyList PolyC ;Sort(PolyA);Sort(PolyB);float sum =0 ;/存儲兩項系數(shù)差PolyNode *pa , *pb , *rear , *s ;PolyC = (PolyNode *)malloc(sizeof(PolyNode);pa = PolyA-next;pb = PolyB-next;rear = PolyC;rear-next = NULL;while(pa & pb)if(pa-exp=pb-exp)&(pa-exp1=pb-exp1)sum = pa-coef-pb-coef;if(fabs(sum)1e-3) /如果兩兩系數(shù)不為0，則將兩項和存入s中，并插入PolyC尾部s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = sum;s-exp = pa-exp;s-exp1 = pa-exp1;s-exp2 = pa-exp2;rear-next = s;rear = s;pa = pa-next;/pa,pb指針后移pb = pb-next;else if(pa-exppb-exp) /若pa指數(shù)大于pb指數(shù)，將pa結點副本插入到PolyC尾部s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = pa-coef;s-exp = pa-exp;s-exp1 = pa-exp1;s-exp2 = pa-exp2;rear-next = s ;rear = s ;pa = pa-next;else /若pb指數(shù)大于pa指數(shù)，將pb結點副本插入到PolyC尾部s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = -pb-coef;s-exp = pb-exp;s-exp1 = pb-exp1;s-exp2 = pa-exp2;rear-next = s;pb = pb-next;rear = s ;while(pa)s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = pa-coef;s-exp = pa-exp;s-exp1 = pa-exp1;s-exp2 = pa-exp2;rear-next = s;pa = pa-next;rear = s ;while(pb)s = (PolyNode *)malloc(sizeof(PolyNode);s-coef = -pb-coef;s-exp = pb-exp;s-exp1 = pb-exp1;s-exp2 = pa-exp2;rear-next = s;pb = pb-next;rear = s ;rear-next = NULL;return PolyC;/多項式相乘，結果由PolyC返回PolyList Mutiply(PolyList PolyA , PolyList PolyB)PolyList PolyC;PolyNode *pa,*pb,*pc_pre,*pc,*s;if(PolyA=NULL|PolyB=NULL) return NULL; /若某一個多項式為空，返回PolyC = (PolyNode*)malloc(sizeof(PolyNode);pc = PolyC ;pc-next = NULL; if(PolyA-next=NULL | PolyB-next=NULL) /數(shù)據(jù)有誤return PolyC; Sort(PolyA);Sort(PolyB);pa = PolyA-next ;pb = PolyB-next;s = (PolyNode*)malloc(sizeof(PolyNode);s-coef = pa-coef * pb-coef;s-exp = pa-exp + pb-exp;s-exp1 = pa-exp1 + pb-exp1;s-exp2 = pa-exp2 + pb-exp2;if(pc-next = NULL)pc-next = s ; pc =s ; pc-next = NULL ; /直接插入第一個結點while(pa)pb = PolyB-next ;while(pb)/兩項對應相乘，結果存入到s中pc = PolyC-next;if(pa = PolyA-next & pb=PolyB-next) /避免重復插入第一個結點pb=pb-next;if(pb = NULL) break;s = (PolyNode*)malloc(sizeof(PolyNode);s-coef = pa-coef * pb-coef;s-exp = pa-exp + pb-exp;s-exp1 = pa-exp1 + pb-exp1;s-exp2 = pa-exp2 + pb-exp2;/查找s合適的插入位置，使得插入后PolyC仍為升序排列while(pc&pc-exps-exp) pc_pre=pc;pc=pc_pre-next;if(pc =NULL)pc_pre-next=s;s-next =NULL;pb=pb-next; else if( pc-expexp)pc_pre-next = s;s-next = pc;pb=pb-next;else if(s-exp=pc-exp )pc-coef+=s-coef ;free(s);if(fabs(pc-coef)next=pc-next;free(pc);pb = pb-next;pa = pa-next;return PolyC;/多項式相除，結果存到PolyC中，商和余數(shù)用系數(shù)為0的結點分開PolyList Divide(PolyList PolyA , PolyList PolyB)if(!PolyA | !PolyB) return NULL;if(PolyB-next = NULL)printf(Error:除項為空!n);return NULL;PolyList PolyT1,PolyT2,pt,s,PolyC,p,s_pre;PolyC=(PolyList)malloc(sizeof(PolyNode);PolyC-next=NULL;if(PolyA-next=NULL) return PolyC;p=PolyA-next;PolyT1=(PolyList)malloc(sizeof(PolyNode);pt = PolyT1;s_pre=(PolyList)malloc(sizeof(PolyNode);while(p) /將PollyA復制到PolyT中，作為被除數(shù)的專門存儲序列s = (PolyList)malloc(sizeof(PolyNode);s-coef = p-coef ;s-exp = p-exp ;pt-next = s;pt = s;p = p-next ;pt-next=NULL;/將商存入到PolyC中，PolyC中的每個節(jié)點都對應商中的每一項/循環(huán)會直至被除數(shù)序列的未知數(shù)最高次小于除數(shù)的未知數(shù)的最高次為止或者被除數(shù)序列至于以單獨的項p = PolyC;while(PolyT1-next & PolyT1-next-exp = PolyB-next-exp)s = (PolyList)malloc(sizeof(PolyNode);/商節(jié)點s_pre-next = s;s-next=NULL;s-coef = PolyT1-next-coef/PolyB-next-coef;s-exp = PolyT1-next-exp - PolyB-next-exp;p-next = s;p = s;PolyT2 = Sub(PolyT1 , Mutiply(PolyB , s_pre);/模Destroy(PolyT1);PolyT1 = PolyT2; /設置分隔結點s =(PolyList)malloc(sizeof(PolyNode);s-coef=0;s-exp=0;p-next=s;p=s;p-next=PolyT1-next; /將余項PolyT復制到PolyC中free(PolyT1);return PolyC;void menu(PolyList PolyA,PolyList PolyB,PolyList PolyC)/一元計算主控char c=getchar();printf(輸入一元多項式：n); PolyA = Create(); Sort(PolyA);switch(getchar()case +: PolyB = Create();Sort(PolyB);Display(Add(PolyA , PolyB);char ch=getchar();return;case -: PolyB = Create();Sort(PolyB);Display(Sub(PolyA , PolyB);char ch=getchar();break;case *: PolyB = Create();Sort(PolyB);Display(Mutiply(PolyA , PolyB);char ch=getchar();break;case /: PolyB = Create();Sort(PolyB);Display(Divide(PolyA , PolyB);char ch=getchar();break;case %: PolyB = Create();Sort(PolyB); Display2(Divide(PolyA , PolyB);char ch=getchar();break;default:printf(未知錯誤待修正。);system(pause);system(cls);return;void menu1(PolyList PolyA,PolyList PolyB,PolyList PolyC)/二元計算主控char c=getchar();printf(輸入二元多項式：n); PolyA = Create1(); Sort(PolyA);switch(getchar()case +: PolyB = Create1();Sort(PolyB);Display1(Add(PolyA , PolyB); char ch=getchar();return;case -: PolyB = Create1();Sort(Pol