数据结构四则运算C语言.doc

#include#include#includetypedef struct PolyNode int exp; /x指数 float coef; /x系数 int exp1; /y指数 int exp2; /z指数 PolyNode* next; PolyNode,*PolyList;PolyList Create()/构建一元多项式PolyNode *s,*rear,*head;int e=1; /指数float c=1; /系数int n=1; /计数器head=(PolyNode*) malloc(sizeof(PolyNode);rear=head;/输入多项式(含括号)，出现系数为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; /指数float c; /系数int n=1; /计数器head=(PolyNode*) malloc(sizeof(PolyNode);rear=head;/一次性输入多项式(含括号)，出现系数为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; /指数float c; /系数int n=1; /计数器head=(PolyNode*) malloc(sizeof(PolyNode);rear=head;/一次性输入多项式(含括号)，出现系数为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) /指数相同则合并 p-coef+=q-coef;if(fabs(p-coef)1e-3)pre-next=q-next;temp = q;q = temp-next;free(temp);else /两项系数和为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; /指数不等，指针q后移/与p指数相同的节点合并完毕，或者没有找到，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指数 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为最后一个元素且指数最小，提前返回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(无数据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(无数据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(无数据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;/存储两项系数和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)/三指数均相同sum = pa-coef+pb-coef;if(fabs(sum)1e-3) /如果两两系数不为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指数大于pb指数，将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指数大于pa指数，将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)/pb结束拷贝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)/pa结束至拷贝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 Sub(PolyList PolyA , PolyList PolyB)PolyList PolyC ;Sort(PolyA);Sort(PolyB);float sum =0 ;/存储两项系数差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) /如果两两系数不为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指数大于pb指数，将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指数大于pa指数，将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) /数据有误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中，商和余数用系数为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中，作为被除数的专门存储序列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中的每个节点都对应商中的每一项/循环会直至被除数序列的未知数最高次小于除数的未知数的最高次为止或者被除数序列至于以单独的项p = PolyC;while(PolyT1-next & PolyT1-next-exp = PolyB-next-exp)s = (PolyList)malloc(sizeof(PolyNode);/商节点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