一元多项式的加法减法乘法和求导.doc

一元多项式的加法、减法、乘法和求导一、【实验构思（Conceive）】(10%)（本部分应包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识） 1、一元稀疏多项式的加法、减法、乘法和求导法则： 假设：f(x) = 3 x8 + 9 x5 g(x) = 7 x9 + 3 x 则：f(x) + g(x) = 7 x9 + 3 x8 + 9 x5 + 3 x f(x) - g(x) = -7 x9 + 3 x8 + 9 x5 - 3 x f(x) * g(x) = 21 x17 + 63 x14 + 9 x9 + 27 x6 f(x) = 24 x7 + 45 x42、 基本思路： 首先定义一个结构体，其中定义一元多项式中的两个参数:系数和指数和链表中结点的指针域；然后一一罗列每个在主程序中用到的函数，并一一实现；最后在主程序中主要完成用户的输入和相关函数的调用。二、【实验设计(Design)】(20%)void insert(PLOYList *head,PLOYList *input) /查找位置插入新链节的函数，且让输入的多项式呈降序排列PLOYList *creat(char ch)/输入多项式PLOYList *add(PLOYList *head,PLOYList *pre)/多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头PLOYList *sub(PLOYList *head,PLOYList *pre)/多项式相减PLOYList *mul(PLOYList *head,PLOYList *pre)/多项式相乘PLOYList *der(PLOYList *head)/多项式求导void print(PLOYList *fun) /输出多项式，fun指要输出的多项式链表的表头void start()/用户选择界面主程序：void main()PLOYList *f,*g,*pf,*hf,*p; int sign=-1; start(); while(sign!=0) scanf(%d,&sign); switch(sign) case 0: break; case 1:/多项式相加 printf( 你选择的操作是多项式相加:n); printf( 请输入第一个多项式f(x)：); f=creat(f); printf( 第一个多项式为：f(x)=); print(f); printf( 请输入第二个多项式g(x)：); g=creat(g); printf( 第二个多项式为：g(x)=); print(g); printf( 结果为：F(x)=f(x)+g(x)=); f=add(f,g); print(f); printf(nn); printf( 继续请选择相应操作，退出请按0. ); break; case 2:/多项式相减 printf( 你选择的操作是多项式相减:n); printf( 请输入第一个多项式f(x)：); f=creat(f); printf( 第一个多项式为：f(x)=); print(f); printf( 请输入第二个多项式g(x)：); g=creat(g); printf( 第二个多项式为：g(x)=); print(g); printf( 结果为：F(x)=f(x)-g(x)=); f=sub(f,g); print(f); printf(nn); printf( 继续请选择相应操作，退出请按0. ); break; case 3:/多项式相乘 printf( 你选择的操作是多项式相乘:n); printf( 请输入第一个多项式f(x)：); f=creat(f); printf( 第一个多项式为：f(x)=); print(f); printf( 请输入第二个多项式g(x)：); g=creat(g); printf( 第二个多项式为：g(x)=); print(g); printf( 结果为：F(x)=f(x) * g(x)=); pf=mul(f,g); print(pf); printf(nn); printf( 继续请选择相应操作，退出请按0. ); break; case 4:/多项式求导 printf(您选择的是对一个一元多项式求导：n); printf(请输入一个一元多项式：); f = creat(f); printf(这个多项式为：f(x)= ); print(f); printf(求导结果为：F(x)=f(x)= ); f=der(f); print(f); printf(nn); printf( 继续请选择相应操作，退出请按0. ); break; case 5:/帮助用户理解输入规则 printf(-帮助-n); printf( n); printf( 1.输入时只输入多项式的系数与指数 n); printf( 2.输入多项式形式：系数1 指数1 系数2 指数2 ，以0 0 结束n); printf( 3.例如输入 1 1 2 2 0 0 表示 1*X1+2*X2 n); printf( n); printf(-帮助-n); printf(nn); break; default: printf( 看完帮助信息后请重新选择操作n); break; /swith /while/void三、【实现描述（Implement）】(30%)1.插入函数，用来对根据用户输入的项建立的单个结点进行排序，使其按照指数降序排列，此函数也可以用在多项式的加减法里，因为加减法实质上也是插入的过程。void insert(PLOYList *head,PLOYList *input) /查找位置插入新链节的函数，且让输入的多项式呈降序排列 PLOYList *pre,*now; int signal=0; pre=head; if(pre-next=NULL) pre-next=input; /如果只有一个头结点，则把新结点直接连在后面 else now=pre-next;/如果不是只有一个头结点，则设置now指针 while(signal=0) if(input-expn expn) if(now-next=NULL) now-next=input; signal=1; else pre=now; now=pre-next;/始终让新输入的数的指数与最后一个结点中的数的指数比较，小于则插在其后面 else if( input-expn now-expn ) input-next=now; pre-next=input; signal=1; /若新结点中指数比最后一个结点即now中的指数大，则插入now之前 else/若指数相等则需合并为一个结点，若相加后指数为0则释放该结点 now-coef=now-coef+input-coef; signal=1; free(input); if(now-coef=0) pre-next=now-next; free(now); /else /while/else/void2.输入函数，用来实现用户对多项式的输入，且根据用户的输入，输入一个项则建立一个结点并调用insert函数进行排序，此函数满足用户随便输入多项式的项数，以0 结束输入。PLOYList *creat(char ch) /输入多项式 PLOYList *head,*input; float x; int y; head=(PLOYList *)malloc(sizeof(PLOYList); /创建链表头 head-next=NULL; scanf(%f %d,&x,&y);/实现用户输入的第一个项，包括其指数和系数 while(x!=0)/当用户没有输入结束标志0时可一直输入多项式的项，且输入一个创建一个结点 input=(PLOYList *)malloc(sizeof(PLOYList); /创建新链节 input-coef=x; input-expn=y; input-next=NULL; insert(head,input); /每输入一项就将其排序，是的链表中多项式呈降序排列 scanf(%f %d,&x,&y); return head;3.实现多项式的加法的函数，运用插入函数，若实现f(x)+g(x），即将g(x)中的每项一个一个查找位置并插入到f(x)中，即最后加法的结果保存在f(x)中。PLOYList *add(PLOYList *head,PLOYList *pre) /多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头 PLOYList *input; int flag=0; while(flag=0) if(pre-next=NULL) flag=1; /若该链表为空，则无需进行加法运算，跳出循环 else pre=pre-next; input=(PLOYList *)malloc(sizeof(PLOYList);/申请空间 input-coef=pre-coef; input-expn=pre-expn; input-next=NULL; insert(head,input); / 把g(x)插入到f(x）中，相当于两者相加，结果保存于f(x) return head;4. 实现多项式的减法的函数，运用插入函数，若实现f(x)-g(x），则将g(x)中的每项的系数变为其相反数，再用和加法实现一样的过程实现。PLOYList *sub(PLOYList *head,PLOYList *pre) /多项式相减 PLOYList *input; int flag=0; while(flag=0) if(pre-next=NULL) flag=1; else pre=pre-next; input=(PLOYList *)malloc(sizeof(PLOYList); input-coef=0-pre-coef;/将第二个多项式里的数变为其相反数，再用和加法一样的方法实现减法 input-expn=pre-expn; input-next=NULL; insert(head,input); return head;4.实现多项式的乘法的函数，也运用插入函数，若实现f(x)*g(x），则运用二重循环将g(x)中的每项与f(x)中的每项相乘，再运用插入函数对其进行排序和合并。PLOYList *mul(PLOYList *head,PLOYList *pre)/多项式项乘PLOYList *hf,*pf,*qa,*qb; qa = head - next; qb = pre - next;/定义指针指向表头后一个元素，即链表中第一个元素hf = ( PLOYList * )malloc( sizeof(PLOYList);/新创建一个结点，当做表头hf - next = NULL;for ( ;qa;qa = qa - next)for( qb = pre - next;qb;qb= qb - next)/用两个循环，实现两个多项式之间每个项相乘，结果用insert函数进行排序与合并pf = ( PLOYList *)malloc(sizeof(PLOYList);pf - coef = qa - coef * qb - coef;pf - expn = qa - expn + qb - expn;pf - next = NULL;insert( hf,pf);return hf;5.实现多项式的求导的函数，将多项式的每项系数和指数相乘得到新的系数，指数减一得到新的指数即完成求导。PLOYList *der(PLOYList *head)/多项式求导PLOYList *p;p = head - next;while (p)p - coef = p - coef * p - expn;p - expn = p - expn-;p = p - next;return head;/将多项式的每项系数和指数相乘得到新的系数，指数减一得到新的指数即完成求导6. 输出函数，满足判断多项式输出，根据是用户的输入选择我调用算法来实现用户想要计算的功能，与此同时他其实也在调用上面的功能函数void print(PLOYList *fun) /输出多项式，fun指要输出的多项式链表的表头 PLOYList *printing; int flag=0; printing=fun-next; if(fun-next=NULL)/若为空表，则无需输出 printf(0n); return; while(flag=0) if(printing-coef0&fun-next!=printing) printf(+); if(printing-coef=1); else if(printing-coef=-1) printf(-); else printf(%f,printing-coef); if(printing-expn!=0) printf(x%d,printing-expn); else if(printing-coef=1)|(printing-coef=-1) printf(1); if(printing-next=NULL) flag=1; else printing=printing-next; printf(n);7.用户输入界面，提供用户输入的提示。void start() /用户选择界面printf( *n); printf( 用户选择界面 n); printf( *n); printf( * *n); printf( * 1.两个一元多项式相加 *n); printf( * 2.两个一元多项式相减 *n); printf( * 3.两个一元多项式相乘 *n); printf( * 4.对一个一个一元多项式求导 *n); printf( * 5.帮助 *n); printf( * 0.退出系统 *n); printf( * *n); printf( *n); printf( n); printf( 注：输入多项式格式为：系数1 指数1 系数2 指数2 ，并以0 0 结束：n); printf( n); printf( 请选择操作: );四、【测试结果（Testing）】(10%)* 用户选择界面* * 1.两个一元多项式相加 * 2.两个一元多项式相减 * 3.两个一元多项式相乘 * 4.对一个一个一元多项式求导 * 5.帮助 * 0.退出系统 * *注：输入多项式格式为：系数1 指数1 系数2 指数2 ，并以0 0 结束：请选择操作: 1你选择的操作是多项式相加:请输入第一个多项式f(x)：2 3 4 5 6 7 0 0第一个多项式为：f(x)=6.000000x7+4.000000x5+2.000000x3请输入第二个多项式g(x)：1 3 5 6 7 5 0 0第二个多项式为：g(x)=5.000000x6+7.000000x5+x3结果为：F(x)=f(x)+g(x)=6.000000x7+5.000000x6+11.000000x5+3.000000x3继续请选择相应操作，退出请按0. 2 你选择的操作是多项式相减: 请输入第一个多项式f(x)：2 3 4 5 6 7 0 0 第一个多项式为：f(x)=6.000000x7+4.000000x5+2.000000x3 请输入第二个多项式g(x)：1 3 5 6 7 5 0 0 第二个多项式为：g(x)=5.000000x6+7.000000x5+x3 结果为：F(x)=f(x)-g(x)=6.000000x7-5.000000x6-3.000000x5+x3 继续请选择相应操作，退出请按0. 3 你选择的操作是多项式相乘: 请输入第一个多项式f(x)：2 3 4 5 0 0 第一个多项式为：f(x)=4.000000x5+2.000000x3 请输入第二个多项式g(x)：1 3 5 6 0 0 第二个多项式为：g(x)=5.000000x6+x3 结果为：F(x)=f(x) * g(x)=20.000000x11+10.000000x9+4.000000x8+2.000000x6 继续请选择相应操作，退出请按0. 4您选择的是对一个一元多项式求导：请输入一个一元多项式：2 3 4 5 6 5 0 0这个多项式为：f(x)= 10.000000x5+2.000000x3求导结果为：F(x)=f(x)= 50.000000x4+6.000000x2 继续请选择相应操作，退出请按0. 5-帮助- 1.输入时只输入多项式的系数与指数 2.输入多项式形式：系数1 指数1 系数2 指数2 ，以0 0 结束 3.例如输入 1 1 2 2 0 0 表示 1*X1+2*X2-帮助-1（帮助后可重新输入想要进行的操作，这里选1，进行加法运算） 你选择的操作是多项式相加: 请输入第一个多项式f(x)：1 2 3 4 0 0 第一个多项式为：f(x)=3.000000x4+x2 请输入第二个多项式g(x)：3 2 4 5 0 0 第二个多项式为：g(x)=4.000000x5+3.000000x2 结果为：F(x)=f(x)+g(x)=4.000000x5+3.000000x4+4.000000x2 继续请选择相应操作，退出请按0.四、【实验总结】(10%）通过本次试验，更加规范了我使用数据结构来编写相关程序的格式和方法。且增强了寻找错误位置的能力。在实验过程中，出现过很多各种各样的错误，如函数的参数设定不对或调用时的参数不对、循环时的某些初始化的遗忘，以及指针的运用出错。通过解决问题，还增加了很多以前不懂得知识，但仍然还有很多方面需要更正和改进，以使自己编写的程序的出错率减少。五、【项目运作描述（Operate）】(10%)通过用户输入界面，让用户省掉了笔算的麻烦，并使处理一元稀疏多项式运算的速率提高。六、【代码】(10%)（本部分应包括：完整的代码及充分的注释。 注意纸质的实验报告无需包括此部分。格式统一为，字体: Georgia , 行距: 固定行距12，字号: 小五）#include#include/动态申请空间的函数的头文件typedef struct node /定义节点类型float coef; /多项式的系数 int expn; /多项式的指数 struct node * next; /结点指针域PLOYList;void insert(PLOYList *head,PLOYList *input) /查找位置插入新链节的函数，且让输入的多项式呈降序排列 PLOYList *pre,*now; int signal=0; pre=head; if(pre-next=NULL) pre-next=input; /如果只有一个头结点，则把新结点直接连在后面 else now=pre-next;/如果不是只有一个头结点，则设置now指针 while(signal=0) if(input-expn expn) if(now-next=NULL) now-next=input; signal=1; else pre=now; now=pre-next;/始终让新输入的数的指数与最后一个结点中的数的指数比较，小于则插在其后面 else if( input-expn now-expn ) input-next=now; pre-next=input; signal=1; /若新结点中指数比最后一个结点即now中的指数大，则插入now之前 else/若指数相等则需合并为一个结点，若相加后指数为0则释放该结点 now-coef=now-coef+input-coef; signal=1; free(input); if(now-coef=0) pre-next=now-next; free(now); /else /while/else/voidPLOYList *creat(char ch) /输入多项式 PLOYList *head,*input; float x; int y; head=(PLOYList *)malloc(sizeof(PLOYList); /创建链表头 head-next=NULL; scanf(%f %d,&x,&y);/实现用户输入的第一个项，包括其指数和系数 while(x!=0)/当用户没有输入结束标志0时可一直输入多项式的项，且输入一个创建一个结点 input=(PLOYList *)malloc(sizeof(PLOYList); /创建新链节 input-coef=x; input-expn=y; input-next=NULL; insert(head,input); /每输入一项就将其排序，是的链表中多项式呈降序排列 scanf(%f %d,&x,&y); return head;PLOYList *add(PLOYList *head,PLOYList *pre) /多项式相加，head为第一个多项式建立的链表表头，pre为第二个多项式建立的链表表头 PLOYList *input; int flag=0; while(flag=0) if(pre-next=NULL) flag=1; /若该链表为空，则无需进行加法运算，跳出循环 else pre=pre-next; input=(PLOYList *)malloc(sizeof(PLOYList);/申请空间 input-coef=pre-coef; input-expn=pre-expn; input-next=NULL; insert(head,input); / 把g(x)插入到f(x）中，相当于两者相加，结果保存于f(x) return head;PLOYList *sub(PLOYList *head,PLOYList *pre) /多项式相减 PLOYList *input; int flag=0; while(flag=0) if(pre-next=NULL) flag=1; else pre=pre-next; input=(PLOYList *)malloc(sizeof(PLOYList); input-coef=0-pre-coef;/将第二个多项式里的数变为其相反数，再用和加法一样的方法实现减法 input-expn=pre-expn; input-next=NULL; insert(head,input); return head;PLOYList *mul(PLOYList *head,PLOYList *pre)/多项式项乘PLOYList *hf,*pf,*qa,*qb; qa = head - next; qb = pre - next;/定义指针指向表头后一个元素，即链表中第一个元素hf = ( PLOYList * )malloc( sizeof(PLOYList);/新创建一个结点，当做表头hf - next = NULL;for ( ;qa;qa = qa - next)for( qb = pre - next;qb;qb= qb - next)/用两个循环，实现两个多项式之间每个项相乘，结果用insert函数进行排序与合并pf = ( PLOYList *)malloc(sizeof(PLOYList);pf - coef = qa - coef * qb - coef;pf - expn = qa - expn + qb - expn;pf - next = NULL;insert( hf,pf);return hf;PLOYList *der(PLOYList *head)/多项式求导PLOYList *p;p = head - next;while (p)p - coef = p - coef * p - expn;p - expn = p - expn-;p = p - next;return head;/将多项式的每项系数和指数相乘得到新的系数，指数减一得到新的指数即完成求导void print(PLOYList *fun) /输出多项式，fun指要输出的多项式链表的表头 PLOYList *printing; int flag=0; printing=fun-next; if(fun-next=NULL)/若为空表，则无需输出 printf(0n); return; while(flag=0) if(printing-coef0&fun-next!=printing) printf(+); if(printing-coef=1); else if(printing-coef=-1) printf(-); else printf(%f,printing-coef); if(printing-expn!=0) printf(x%d,printing-expn); else if(printing-coef=1)|(printing-coef=-1) printf(1); if(printing-next=NULL) flag=1; else printing=printing-next; printf(n);void start() /用户选择界面printf( *n); printf( 用户选择界面 n); printf( *n); printf( * *n); printf( * 1.两个一元多项式相加 *n); printf( * 2.两个一元多项式相减 *n); printf( * 3.两个一元多项式相乘 *n); printf( * 4.对一个一个一元多项式求导 *n); printf( * 5.帮助 *n); printf( * 0.退出系统 *n); printf( * *n); printf( *n); printf( n); printf( 注：输入多项式格式为：系数1 指数1 系数2 指数2 ，并以0 0 结束：n); printf( n); printf( 请选择操作: );void main()PLOYList *f,*g,*pf,*hf,*p; int sign=-1; start(); while(sign!=0) scanf(%d,&sign); switch(sign) case 0: break; case 1:/多项式相加 printf( 你选择的操作是多项式相加:n); printf( 请输入第一个多项式f(x)：); f=creat(f); printf( 第一个