数据结构课程设计--一元多项式计算问题(C语言).doc

长 沙 学 院课程设计说明书题目一元多项式计算问题系(部)计算机科学与技术系专业(班级)12软件4班姓名谢仲蛟学号2012022411指导教师邱建雄起止日期2013.12.92013.12.20课程设计任务书课程名称：数据结构与算法设计题目：一元多项式计算问题已知技术参数和设计要求：问题描述：设计一个稀疏多项式简单计算器基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出；测试数据：(1) A+B A= 3x14-8x8+6x2+2 B=2x10+4x8+-6x2 (2) A-B A=11x14+3x10+2x8+10x6+5 B=2x14+3x8+5x6+7(3) A+B A=x3+x1 B=-x3-x1(4) A+B A=0 B=x7+x5+x3+x1(5) A-B A=100x100+50x50+20x20+x B=10x100+10x50+10x20+x选作内容：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积设计工作量：40课时工作计划：班级时间节次地点内容指导老师12软件4班15周周一5-6节致远楼1403布置任务邱建雄15周周一9-10节致远楼1403上机调试15周周二5-8节致远楼1403上机调试15周周三5-8节致远楼1403上机调试15周周四1-4节涵虚楼C3302答疑15周周四7-8节致远楼1403上机调试15周周五1-4节涵虚楼A1103答疑16周周一5-6节致远楼1402上机调试16周周二5-8节致远楼1403上机调试16周周三1-4节致远楼1403上机调试16周周三5-8节致远楼1403上机调试16周周五5-8节致远楼1403答辩指导教师签名：日期： 教研室主任签名： 日期：系主任签名： 日期：长沙学院课程设计鉴定表姓名谢仲蛟学号2012022411专业软件工程班级软件4班设计题目一元多项式计算问题指导教师邱建雄指导教师意见：评定等级： 教师签名： 日期： 答辩小组意见：评定等级：答辩小组长签名：日期：教研室意见：教研室主任签名： 日期： 系（部）意见：系主任签名：日期：说明课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；摘要本次课程设计是在数据结构基础上设计以C语言来实现的，它的目的是帮助同学更深入的了解数据结构这门课程并熟练运用C语言，使同学达到熟练掌握的程度。课程设计一个稀疏多项式简单计算器。其基本要求有六：其一，输入建立两个多项式；其二,输出多项式，输出形式为整数序列：n，c1,e1,c2,e2,其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数的降序序列排列；其三，多项式排序，多项式按指数的降序序列排列；其四，多项式相加，指数相同系数相加，指数不同则把此项加进去；其五，多项式相减，指数相同系数相加，指数不同则把此项取反再加进去；其六，返回多项式的项数。选做内容有二：其一，计算多项式的值；其二，多项式相乘。关键词： 一元多项式，相加，相减，排序，相乘，计算，目录1 设计内容与要求72 详细设计83 测试16参考文献18附录：程序源代码191 设计内容与要求1、设计内容：设计一个稀疏多项式简单计算器2、基本要求：(1)输入并分别建立多项式A和B(2)输入输出多项式，输出形式为整数序列：n,c1,e1,c2,e2，其中n是多项式的项数，ci和 ei是第i项的系数和指数，序列按指数降序排列(3)完成两个多项式的相加、相减，并将结果输出； 3、提升要求：（1）.多项式在x=1时的运算结果（2）求多项式A和B的乘积2 详细设计1、主要设计思路本次设计的一元多项式计算问题以线性表的链式存储结构来存储多项式每一项的参数，采用二级存储结构，定义了两个结构体，一个用来存放每一项的信息如系数和指数，另一个用来存放指向链表的头结点的指针和多项式的项数。2、主要模块和流程开始操作界面创建多项式相加 1 5 排序相减 选择操作 2 6返回项数计算 3 7 输出多项式相乘 4 8 9 退出 结束3、数据结构Pya *nexteiai*nexteiaiaiei*next*Poln4、界面设计我的界面设计比较简单。有一个循环体构成，其中有八个选项，分别为：0.退出1.创建多项式2.排序3.相加4.相减5.计算6.相乘7.项数。用户可以任意选择其中的选项进行操作。其实现代码为：#include#include#includePolynomial.hvoid main()printf(n*xiezhongjiao!*n);struct Polynomial *Pya,*Pyb; Pya = new Polynomial; Pyb = new Polynomial;openface(); int A=1;int x0=1,x1=1;while(A)printf(选择：);scanf(%d,&A);switch(A)case 0: break;case 1: printf(Pya:n); scan_polynomial(Pya);/*创建*/printf(Pyb:n); scan_polynomial(Pyb);/*创建*/printf(Pya = ); print_polynomial(Pya);/*输出*/ printf(Pyb = ); print_polynomial(Pyb);/*输出*/ break;case 2: sort_polynomial(Pya);/*排序*/ printf(Pya = ); print_polynomial(Pya);/*输出*/sort_polynomial(Pyb); printf(Pyb = ); print_polynomial(Pyb);/*输出*/ break;case 3: addition_polynomial(Pya,Pyb);/*相加*/ printf(Pya+Pyb = ); print_polynomial(Pya);/*输出*/ break;case 4: mimus_polynomial(Pya,Pyb);/*相减*/ printf(Pya-Pyb = ); print_polynomial(Pya);/*输出*/ break;case 5: printf(输入x的值:);scanf(%d,&x0); count_polynomial(Pya,x0);/*计算*/printf(输入x的值:);scanf(%d,&x1); count_polynomial(Pyb,x1);/*计算*/ break;case 6: product_polynomial(Pya,Pyb);/*相乘*/ printf(Pya*Pyb = ); print_polynomial(Pya);/*输出*/ break;case 7: printf(Pya项数:); n_polynomial(Pya);/*返回项数*/printf(Pyb项数:); n_polynomial(Pyb);/*返回项数*/ break;default: printf(请正确输入.); break;/*end of switch*/ /*end of while*/printf(n感谢xzj,感谢home,感谢XX,感谢CL,感谢501,感谢yyxsz,感谢ccsu!n); void openface()printf(n*n);printf(1:创建多项式n);printf(2:排序n);printf(3:相加n);printf(4:相减n);printf(5:计算n);printf(6:相乘n);printf(7:项数n);printf(0:退出n);printf(*n);5、功能设计1、输入多项式此功能为创建一个线性链式链表，并将多项式每一项的信息输入到链表中存储起来。其实现代码为：struct Polynomial *scan_polynomial(struct Polynomial *Py) /* 输入多项式 */struct element *q,*p;q = (struct element *)malloc(sizeof(struct element); Py-Pol = q; Py-n = 1;printf(输入第1项的系数和指数(两数逗号相隔)：);scanf(%d,%d,&q-ai,&q-ei); q-next = NULL;if(q-ai != 0)for(int k=0;kn;k+) p = (struct element *)malloc(sizeof(struct element);printf(输入第%d项的系数和指数(两数逗号相隔)：,k+2); scanf(%d,%d,&p-ai,&p-ei); if(p-ai = 0) break;p-next = NULL;q-next = p; q = q-next ;Py-n = Py-n + 1;/*end of for*/*end of if*/return Py;2、 输出多项式 此项功能为输出创建的多项式。其实现代码为：void print_polynomial(struct Polynomial *Py) /* 输出多项式,项数为n项 */struct element *r;r = Py-Pol; for(int k=0;kn;k+) if(r-ei = 0)/*当指数为0时只输出系数*/if(r-ai ai);if(r-ai 0)if(k = 0) printf(%d,r-ai);/*当此项为第一项时前面不输出+*/if(k != 0) printf(+%d,r-ai);/*当此项不为第一项时前面输出+*/ /*end of if*/if(r-ei = 1)/*当系数为1时只输出系数和x*/if(r-ai ai = -1)printf(-x);/*系数为-1时取反输出x*/if(r-ai != -1)printf(%dx,r-ai);/*系数不为-1时输出系数*/*end of if*/if(r-ai 0)/*系数大于0时输出各项的参数*/if(r-ai = 1)/*系数为1时输出不输出系数*/if(k = 0) printf(x);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+x);/*当此项不为第一项时前面输出+*/if(r-ai != 1)/*系数不为1时输出输出系数*/if(k = 0) printf(%dx,r-ai);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+%dx,r-ai);/*当此项不为第一项时前面输出+*/ /*end of if*/ /*end of if*/if(r-ei != 0 & r-ei != 1)/*当指数既不为0也不为1时输出系数指数和*/if(r-ai ai = -1)printf(-x%d,r-ei);/*系数为-1时取反输出x和指数*/if(r-ai != -1)printf(%dx%d,r-ai,r-ei);/*系数不为-1时输出所有参数*/*end of if*/if(r-ai 0)/*系数大于0时输出各项的参数*/if(r-ai = 1)/*系数为1时输出不输出系数*/if(k = 0) printf(x%d,r-ei);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+x%d,r-ei);/*当此项不为第一项时前面输出+*/if(r-ai != 1)/*系数不为1时输出输出系数*/if(k = 0) printf(%dx%d,r-ai,r-ei);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+%dx%d,r-ai,r-ei);/*当此项不为第一项时前面输出+*/ /*end of if*/*end of if*/r = r-next ; /*指向下一项*/*end of for*/ printf(n); 3、排序多项式 此功能是将已经建立好的多项式按照其指数的降序序列排序，并按照内存的地址序列存储起来。 其实现代码为：struct Polynomial *sort_polynomial(struct Polynomial *Py)/* 排序按指数降序排列 */struct element *sr1,*sr0;int ai,ei;for(int k0=0;k0n-1;k0+)sr0 = sr1 = Py-Pol;for(int k0=0;k0n-1;k0+)for(int k1=0;k1n-1-k0;k1+)if(sr0-ei next-ei)/*如果当前项小则将两个结构中的值互换*/ai = sr0-ai ;ei = sr0-ei ;sr0-ai = sr1-next-ai ;sr0-ei = sr1-next-ei ;sr1-next-ai = ai;sr1-next-ei = ei;/*end of if*/sr1 = sr1-next ;/*end of for3*/sr0 = sr0-next ;sr1 = sr0;/*end of for2*/*end of for1*/return Py; 4、多项式相加 此项功能为将两个多项式A、B进行相加，首先对多项式中的每一项进行比较，当指数相同时，将当前项的系数相加，当指数不同时，则将B中的此项插入A当中，直到每一项都比较完为止，最后得到一条新的线性链表A。其实现代码为：struct Polynomial *addition_polynomial(struct Polynomial *Pya,struct Polynomial *Pyb) /* 两个多项式相加 */struct element *wa,*va,*wb,*vb;wb = vb = Pyb-Pol ;int A,B=Pyb-n;for(int j0=0;j0Pol ;A=0;for(int j1=0;j1n;j1+)if(wa-ei = wb-ei)/*如果所比较的两个多项式中的指数相同则将两系数相加*/ wa-ai=wa-ai+wb-ai; wb=wb-next; vb=wb; break;/*end of if*/if(wa-ei != wb-ei)/*如果所比较的两个多项式中的指数不同则将Pyb中的此项插入到Pya中*/ va = wa;wa=wa-next; A=A+1;if(A = Pya-n) wb = wb-next;va-next = vb; vb-next = NULL;vb = wb;Pya-n+;break;/*end of if*/*end of if1*/*end of for2*/*end of for1*/return Pya;5、多形式相减此项功能为将两个多项式A、B进行相减，此项功能与多项式相加算法相近，即首先对多项式中的每一项进行比较，当指数相同时，将当前项的项数相减，当指数不同时，则将B中此项插入到A当中，直到每一项都比较完为止，最后得到一条新的线性链表A.其实现代码为：struct Polynomial *mimus_polynomial(struct Polynomial *Pya,struct Polynomial *Pyb) /* 两个多项式相减 */struct element *wa,*va,*wb,*vb;wb = vb = Pyb-Pol ;int A,B=Pyb-n;for(int j0=0;j0Pol ;A=0;for(int j1=0;j1n;j1+)if(wa-ei = wb-ei)/*如果所比较的两个多项式中的指数相同则将两系数相减*/ wa-ai=wa-ai-wb-ai; wb=wb-next; vb=wb; break;/*end of if*/if(wa-ei != wb-ei)/*如果所比较的两个多项式中的指数不同则将Pyb中的此项插入到Pya中*/ va = wa;wa=wa-next; A=A+1;if(A = Pya-n) wb = wb-next;va-next = vb; vb-ai = -vb-ai ;vb-next = NULL;vb = wb;Pya-n+;break;/*end of if*/*end of if1*/*end of for2*/*end of for1*/return Pya; 6、返回项数 此项功能为得到一个多项式项数的值。其实现代码为：void n_polynomial(struct Polynomial *Py) /* 返回多项式的项数 */printf(%dn,Py-n);7、计算多项式的值此项功能为计算多项式的值，输入x的值，首先将第一项的值计算出来，并将下一项的值计算出，然后两值相加，接着再计算第三项数的值，再将前两项之和加上第三项的值，依次下去，计算出多项式每一项的值，得到多项式的值并输出。其实现代码为：void count_polynomial(struct Polynomial *Py,int x0) /* 计算多项式x=x1的结果 */struct element *z;z = Py-Pol;int x1,count=0;for(int k0=0;k0n;k0+)x1 = 1;for(int k1=0;k1ei;k1+)/*计算每一项变量的值*/x1 = x1 * x0;count =count + x1 * z-ai;/*累加*/z = z-next ;printf(当x0 = %d 时,多项式的值为:%dn,x0,count);8、 多项式相乘此项功能为将两个多项式A、B进行相乘，将多项式A中的每一项分别乘以B中的每一项并将得到的每项的信息用线性链表进行存储；最终得到一条新的线性链表。其实现代码为：struct Polynomial *product_polynomial(struct Polynomial *Pya,struct Polynomial *Pyb) /* 两个多项式相乘 */struct element *A0,*A1,*A2,*A3,*B0,*C0;A0 = A1 = A2 = A3 = Pya-Pol ;for(int k0=0;k0n;k0+)A0 = A2;A2 = A2-next ;B0 = Pyb-Pol ; for(int k1=0;k1n;k1+)/*先将Pya中第一项乘以Pyb中的每一项并把头结点赋给Pya，再将Pya中的第二项乘以Pyb中的每一项并把头结点赋给新的Pya的最后一项，依次下去直到没一项都乘完为止*/ if(k1 = 0) A1-ai = A0-ai * B0-ai ; A1-ei = A0-ei + B0-ei ;A1-next = NULL;/*emd of if*/ if(k1 != 0) C0 = (struct element *)malloc(sizeof(struct element);C0-ai = A0-ai * B0-ai ;C0-ei = A0-ei + B0-ei ; C0-next = NULL;A1-next = C0;A1 = A1-next ;/*end of if*/B0 = B0-next ; /*end of for2*/A1-next = A2;A1 = A2; /*end of for1*/Pya-n = Pya-n * Pyb-n;return Pya;3 测试1、 创建多项式测试首先选择1创建多项式选项，接着输入多项式A和B的指数和系数，其中指数和系数用逗号相隔，最后输出多项式A、B。2、 排序 选择操作2排序选项，对多项式A、B进行了降序排列。3、 相加 选择操作3多项式相加，对多项式A、B进行了相加。4、 相减 先选择操作0退出后再重新进入，接着选择创建多项式，后再选择操作4对多项式进行相减比输出。5、 计算 先选择操作5，接着数如x的值，得到多项式A、B的值。6、 返回项数值 选择操作7，返回了多项式A、B的项数。7、 相乘 选择操作6对多项式A、B进行了相乘毕输出。参考文献1 严蔚敏，吴伟民数据结构（C语言版）.北京：清华大学出版社，1997年.2 C程序设计/谭浩强.-3版.-北京：清华大学出版社，2005（2007重印）附录：程序源代码1、头文件#includestruct element int ai; /*系数*/int ei; /*指数*/ struct element *next; ;struct Polynomial struct element *Pol; int n; /*项数*/;/* 输入多项式 */struct Polynomial *scan_polynomial(struct Polynomial *Py);/* 销毁一个多项式 */void destroy_polynomial(struct Polynomial *Py); /* 输出多项式 */void print_polynomial(struct Polynomial *Py); /* 两个多项式相加 */struct Polynomial *addition_polynomial(struct Polynomial *Pya,struct Polynomial *Pyb);/* 两个多项式相减 */struct Polynomial *mimus_polynomial(struct Polynomial *Pya,struct Polynomial *Pyb); /* 排序按指数降序排列 */struct Polynomial *sort_polynomial(struct Polynomial *Py);/* 多项式的项数 */void n_polynomial(struct Polynomial *Py);/* 计算多项式x=x1的结果 */void count_polynomial(struct Polynomial *Py,int x0); /* 两个多项式相乘 */struct Polynomial *product_polynomial(struct Polynomial *Pya,struct Polynomial *Pyb); void openface();2、主函数文件#include#include#includePolynomial.hvoid main()printf(n*xiezhongjiao!*n);struct Polynomial *Pya,*Pyb; Pya = new Polynomial; Pyb = new Polynomial; openface(); int A=1;int x0=1,x1=1;while(A)printf(选择：);scanf(%d,&A);switch(A)case 0: break;case 1: printf(Pya:n); scan_polynomial(Pya);/*创建*/printf(Pyb:n); scan_polynomial(Pyb);/*创建*/printf(Pya = ); print_polynomial(Pya);/*输出*/ printf(Pyb = ); print_polynomial(Pyb);/*输出*/ break;case 2: sort_polynomial(Pya);/*排序*/ printf(Pya = ); print_polynomial(Pya);/*输出*/sort_polynomial(Pyb); printf(Pyb = ); print_polynomial(Pyb);/*输出*/ break;case 3: addition_polynomial(Pya,Pyb);/*相加*/ printf(Pya+Pyb = ); print_polynomial(Pya);/*输出*/ break;case 4: mimus_polynomial(Pya,Pyb);/*相减*/ printf(Pya-Pyb = ); print_polynomial(Pya);/*输出*/ break;case 5: printf(输入x的值:);scanf(%d,&x0); count_polynomial(Pya,x0);/*计算*/printf(输入x的值:);scanf(%d,&x1); count_polynomial(Pyb,x1);/*计算*/ break;case 6: product_polynomial(Pya,Pyb);/*相乘*/ printf(Pya*Pyb = ); print_polynomial(Pya);/*输出*/ break;case 7: printf(Pya项数:); n_polynomial(Pya);/*返回项数*/printf(Pyb项数:); n_polynomial(Pyb);/*返回项数*/ break;default: printf(请正确输入.); break;/*end of switch*/ /*end of while*/printf(n感谢xzj,感谢home,感谢XX,感谢CL,感谢501,感谢yyxsz,感谢ccsu!n); void openface()printf(n*n);printf(1:创建多项式n);printf(2:排序n);printf(3:相加n);printf(4:相减n);printf(5:计算n);printf(6:相乘n);printf(7:项数n);printf(0:退出n);printf(*n);3、功能函数文件#include#include#include#includePolynomial.hstruct Polynomial *scan_polynomial(struct Polynomial *Py) /* 输入多项式 */struct element *q,*p;q = (struct element *)malloc(sizeof(struct element); Py-Pol = q; Py-n = 1;printf(输入第1项的系数和指数(两数逗号相隔)：);scanf(%d,%d,&q-ai,&q-ei); q-next = NULL;if(q-ai != 0)for(int k=0;kn;k+) p = (struct element *)malloc(sizeof(struct element);printf(输入第%d项的系数和指数(两数逗号相隔)：,k+2); scanf(%d,%d,&p-ai,&p-ei); if(p-ai = 0) break;p-next = NULL;q-next = p; q = q-next ;Py-n = Py-n + 1;/*end of for*/*end of if*/return Py;void print_polynomial(struct Polynomial *Py) /* 输出多项式,项数为n项 */struct element *r;r = Py-Pol; for(int k=0;kn;k+) if(r-ei = 0)/*当指数为0时只输出系数*/if(r-ai ai);if(r-ai 0)if(k = 0) printf(%d,r-ai);/*当此项为第一项时前面不输出+*/if(k != 0) printf(+%d,r-ai);/*当此项不为第一项时前面输出+*/ /*end of if*/if(r-ei = 1)/*当系数为1时只输出系数和x*/if(r-ai ai = -1)printf(-x);/*系数为-1时取反输出x*/if(r-ai != -1)printf(%dx,r-ai);/*系数不为-1时输出系数*/*end of if*/if(r-ai 0)/*系数大于0时输出各项的参数*/if(r-ai = 1)/*系数为1时输出不输出系数*/if(k = 0) printf(x);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+x);/*当此项不为第一项时前面输出+*/if(r-ai != 1)/*系数不为1时输出输出系数*/if(k = 0) printf(%dx,r-ai);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+%dx,r-ai);/*当此项不为第一项时前面输出+*/ /*end of if*/ /*end of if*/if(r-ei != 0 & r-ei != 1)/*当指数既不为0也不为1时输出系数指数和*/if(r-ai ai = -1)printf(-x%d,r-ei);/*系数为-1时取反输出x和指数*/if(r-ai != -1)printf(%dx%d,r-ai,r-ei);/*系数不为-1时输出所有参数*/*end of if*/if(r-ai 0)/*系数大于0时输出各项的参数*/if(r-ai = 1)/*系数为1时输出不输出系数*/if(k = 0) printf(x%d,r-ei);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+x%d,r-ei);/*当此项不为第一项时前面输出+*/if(r-ai != 1)/*系数不为1时输出输出系数*/if(k = 0) printf(%dx%d,r-ai,r-ei);/*当此项为第一项时前面不输出+*/ if(k != 0) printf(+%dx%d,r-ai,r-ei);/*当此项不为第一项时前面输出+*/ /*end of if*/*end of if*/r = r-next ; /*指向下一项*/*end of for*/ printf(n);struct Polynomial *addition_polynomial(struct Polynomial *Pya,struct Polynomial