1内蒙古科技大学课程设计任务书-一元多项式的代数运算

1、内蒙古科技大学数据结构课程设计论文题 目：一元多项式的代数运算学生姓名：郭栋学 号：1176807301专 业：计算机科学与技术班 级：计-3指导教师：丁雨 内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目一元多项式的代数运算指导教师丁雨时间一、教学要求1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数一元多项式的代

2、数运算以链表存储一元多项式，在此基础上完成对多项式的操作。要求设计类（或类模板）来描述一元多项式，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：v 输入多项式v 输出多项式v 多项式加法v 多项式减法v 多项式乘法 并设计主函数测试该类。三、设计要求及成果1. 分析课程设计题目的要求2. 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告四、进度安排资料查阅与讨论系统分析系统的开发与测试编写课程设计说明书和验收五、评分标准考勤占20%课程设计论文40%答辩综合评定40%成绩采用五级分制评定六、建议参

3、考资料1数据结构 （C3.数据结构:用面向对象方法与C+语言描述，殷人昆 主编， 清华大学出版社 2007目录引言4需求分析4设计概要4一、 存储结构：4二、 一元多项式的创建：5三、 加法设计：6四、 乘法设计：7五、 减法设计：7六、 一元多项式输出：8运行环境与运行结果9运行环境9运行结果9心得体会10附录：源程序代码11引言一般的，我们只知道数学上的一元多项式的运算，且都是用笔来计算的，然而此次课程设计将会通过程序用电脑来实现一元多项式的加法和乘法运算。 通过C+使用顺序和动态存储结构实现一元多项式加法和乘法的运算，并且按升序和降序两种情况排列。需求分析这个程序的关

4、键是多项式的创建和排列，以及相乘时系数相乘和指数相加、相加时相同指数的系数相加、相减时相同指数的系数相减。由于多项式拥有指数和系数（假设基数已定），所以可以定义一个包含指数系数的结构体，用单链表存储多项式的数据，所以结构体包含next指针。数据插入时比较两数的指数，按照升序降序顺序排序，从表头的next开始，直至找到合适的位置，然后开始链表中数值的插入，如果相等则直接将指数相加，如果大于就将新数据插入到当前指向的前面，否则将新数据插入到最后。输入完数据后输出相乘、相加，多项式运算时要循环遍历整个多项式，多项式的每一组数据都要和另一个多项式整组数据相运算（每一个运算值都存储到新建的“多项式”链表

5、中），直到两个多项式都遍历完结束。设计概要一、 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。一元多项式相乘一元多项式输出一元多项式相减退出一元多项式创建一元多项式相加一元多项式的运算一元多项式排序图 开始创建一个含n个链表类型结点的项分别输入各项的系数和指数判断是否系数不为0且指数大于0重新输入一元多项式创建成功二、 一元多项式的创建：三、 加法设计：创建两个指针分别指向两个多项式表头的next，分别使用for函数独自循环

6、，遍历各自的每一组数据，每遍历一次都将系数与指数存储到新建多项式的链表中。因为存储时利用到插入函数，而插入函数中有相同指数的系数相加功能直接将两个多项式的数据依次插入到新的多项式中即可完成多项式相加。（1）功能：将两多项式相加。 （2）数据流入：输入函数。 （3）数据流出：多项式相加后的结果。 （4）程序流程图：多项式的加法流程图如图3.3所示。 （5）测试：两多项式是否为空，为空则提示重新输入，否则，进行运算。开始运算时系数相加删除该项判断所输入的多项式系数是否为0判断输入的两个多项式指数是否相等输入的第1个多项式为B判断输入的多项式1,2指数是否e1

7、>e2输入的第2个多项式为B进行运算四、 乘法设计：创建两个指针分别指向两个多项式表头的next，使用for函数嵌套循环，遍历每一组数据，每遍历一次都将两组数据的系数相乘，指数相加，再利用插入函数将系数与指数存储到新建多项式的链表中。（1）功能：将两多项式相乘。 （2）数据流入：输入函数。 （3）数据流出：多项式相乘后的结果。 （4）程序流程图：多项式的乘法流程图如图所示。 开始给出运算的两个多项式按系数相乘指数相加进行运算将运算的结果相加并输出（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。五、 减法设计：创建两个指针分别指

8、向两个多项式表头的next，以两个指针同时不为空为条件循环遍历，如果当前多项式A的指数小于多项式B，则将当前多项式B的系数置负，指数不变，存入新建多项式中，指向多项式B的指针指向下一个；如果如果当前多项式A的指数大于多项式B，则将当前多项式A的系数指数不变，存入新建多项式中，指向多项式A的指针指向下一个；否则将多项式A的系数减去B的系数后存入新建多项式中，指数不变存入，再将两个指针同时指向下一个。结束循环后判断是哪一个多项式遍历完了，将未遍历完的多项式剩下的数据全部插入到新建多项式中。（1）功能：将两多项式相减。 （2）数据流入：调用输入函数。 （3）数据流出：多项式相减后

9、的结果。 （4）程序流程图：多项式的减法流程图如图3.5所示。 开始调用多项式加法函数进行运算将多项式B进行复制取多项式B的相反数（5）测试要点：两多项式是否为空，为空则提示重新输入，否则，进行运算。六、 一元多项式输出：先判断录入的两个多项式是否有空项，如果两个多项式都不是空的，那么顺序输出多项式A和多项式B，否则多项式创建不成功。操作流程图如图所示：输出多项式B输出多项式A开始判断所输入的两个多项式是否有空的多项式创建有误，重新输入图运行环境与运行结果运行环境：本课程程序设计语言为 C+，程序的运行环境为。、运行结果： 进入运行界面A、 B多项式输出界面A、 B多项式加

10、、减、乘运算输出界面心得体会一元多项式计算是一个单链表的运用， 通过这个程序可以检测我们的学习情况，看看我们是否对单链表真正的理解。 一元多项式计算器的基本功能定为： (1) 建立多项式  (2) 输出多项式  (3) 两个多项式相加、相减、相乘，建立并输出和、差、积多项式  由于课程设计只有短短的两周时间，再加上原本自己编程能力并非突出，所以连这个简单的一元多项式的四则运算都令我大伤脑筋，尽管这样，还是没能完善，我还只能算勉勉强强完成了三则运算，不过虽说这样，我也从中学到不

11、少东西，我深刻认识到编程中结构化和模块化的重要性，当然也注意到很多细节问题是平时编小程序时经常疏忽的，如局部变量，外部变量等的定义与使用。虽然这次课程设计并非做的好，但我知道这也只不过是另一次尝试，一次考验。而且通过这次课程设计，我深知在做一件比较专业的事情的时候，没有其专业知识时绝对不可能把它做好的，也许并非这个一元多项式的运算难，而是自己的编程知识缺乏了点，所以一直在想我该先做什么，后来，我就去查阅了一些资料，就把目标锁定在要实现的功能上，从简单到容易，所以就构思了一下整体结构，然后开始找资料，写程序。但不管怎样，我受益还是颇多的，起码让我认识到自身编程知识还是有些欠缺的，所以我以后会踏踏

12、实实的走好每一步。附录：源程序代码#include<stdio.h>#include<malloc.h>#include<stdlib.h>struct data    int xishu;    int zhishu;struct node    data dat;    node *next;int cmp(const 

13、;void *a,const void *b)    return (data*)a)->zhishu-(data*)b)->zhishu;void output(node *head)    node *p;    node *shengxu;    shengxu=new node;    s

14、hengxu->next=NULL;    printf("升序排列n");    p=head->next;    while(p)            if(p->dat.xishu<0)          &

15、#160; printf("b");        if(p->dat.xishu!=0)                    if(p->dat.xishu=1)         &#

16、160;      printf("X%d+",p->dat.zhishu);            else if(p->dat.xishu=-1)                printf("-X%d+

17、",p->dat.zhishu);            else                printf("%dX%d+",p->dat.xishu,p->dat.zhishu);       &

18、#160;        node *q;        q=new node;        q->dat.zhishu=p->dat.zhishu;        q->dat.xishu=p->dat.xishu; &#

19、160;      q->next=shengxu->next;        shengxu->next=q;        p=p->next;        printf("b n");    pri

20、ntf("降序排列n");    p=shengxu->next;    while(p)            if(p->dat.xishu<0)            printf("b");  

21、      if(p->dat.xishu!=0)                    if(p->dat.xishu=1)                print

22、f("X%d+",p->dat.zhishu);            else if(p->dat.xishu=-1)                printf("-X%d+",p->dat.zhishu);   &#

23、160;        else                printf("%dX%d+",p->dat.xishu,p->dat.zhishu);              

24、0; p=p->next;        printf("b n");int main()    int sum1,sum2;    data *d1,*d2;    int zhishu_max1=-1,zhishu_max2=-1;    int i,j;&#

25、160;   int *biaodashi1,*biaodashi2;    node *he,*cha;    node *head1,*head2,*tail1,*tail2;    head1=(node *)malloc(sizeof(node);    head2=(node *)malloc(sizeof(node);  &#

26、160; head1->next=NULL;    head2->next=NULL;    tail1=head1;    tail2=head2;    /输入第一个表达式    printf("请输入第一个多项式的项数：");    scanf("%d",&sum1); &

27、#160;  d1=(data*)malloc(sum1*sizeof(data);    printf("请依次输入每项多项式的系数和指数:n");    for(i=0;i<sum1;i+)            scanf("%d%d",&d1i.xishu,&d1i.zhishu);  &

28、#160;     /输入第二个表达式    printf("请输入第二个多项式的项数：");    scanf("%d",&sum2);    d2=(data*)malloc(sum2*sizeof(data);    printf("请依次输入每项多项式的系数和指数:n");   &#

29、160;for(i=0;i<sum2;i+)            scanf("%d%d",&d2i.xishu,&d2i.zhishu);        /排序    qsort(d1,sum1,sizeof(data),cmp);    qsort(d2,sum2,siz

30、eof(data),cmp);    zhishu_max1=d1sum1-1.zhishu;    zhishu_max2=d2sum2-1.zhishu;    for(i=0;i<30;i+)        printf("=");    printf("n");   

31、0;/输出第一个表达式    printf("第一个表达式为：n");    for(i=0;i<sum1;i+)            if(d1i.xishu!=0)                 

32、   if(d1i.xishu=1)                printf("X%d",d1i.zhishu);            else if(d1i.xishu=-1)      &#

33、160;         printf("-X%d",d1i.zhishu);            else                printf("%dX%d",d1i.xishu

34、,d1i.zhishu);                if(i<sum1-1)            printf("+");        printf("n");  

35、   /输出第二个表达式    printf("第二个表达式为：n");    for(i=0;i<sum2;i+)            if(d2i.xishu!=0)              &#

36、160;     if(d2i.xishu=1)                printf("X%d",d2i.zhishu);            else if(d2i.xishu=-1)   

37、0;            printf("X%d",d2i.zhishu);            else                printf("%dX%d&

38、quot;,d2i.xishu,d2i.zhishu);                if(i<sum2-1)            printf("+");        printf("n"

39、;);     /求两个多项式的和和差    he=new node;    cha=new node;    he->next=NULL;    cha->next=NULL;    node *cha_tail,*he_tail;    he_tail=he;&#

40、160;   cha_tail=cha;    for(i=0,j=0;i<sum1&&j<sum2;)            node *p,*p2;        p=new node;       

41、0;p2=new node;        if(d1i.zhishu<d2j.zhishu)                    p->dat.zhishu=d1i.zhishu;         

42、60;  p->dat.xishu=d1i.xishu;            p2->dat.zhishu=d1i.zhishu;            p2->dat.xishu=d1i.xishu;          

43、;  i+;                else if(d1i.zhishu>d2j.zhishu)                    p->dat.zhishu=d2j.zhishu;&#

44、160;           p->dat.xishu=d2j.xishu;            p2->dat.zhishu=d2j.zhishu;            p2->dat.xishu=-d2j.xishu;

45、60;           j+;                else                    p->da

46、t.zhishu=d1i.zhishu;            p->dat.xishu=d1i.xishu+d2j.xishu;            p2->dat.zhishu=d1i.zhishu;            

47、;p2->dat.xishu=d1i.xishu-d2j.xishu;            i+;            j+;                he_tail->next

48、=p;        p->next=NULL;        he_tail=p;        cha_tail->next=p2;        p2->next=NULL;       

49、; cha_tail=p2;        /将剩余的项加到表达式中    if(sum1<sum2)            for(;j<sum2;j+)               &

50、#160;    node *p,*p2;            p=new node;            p2=new node;            p->

51、;dat.zhishu=d2j.zhishu;            p->dat.xishu=d2j.xishu;            p2->dat.zhishu=d2j.zhishu;            p2->

52、;dat.xishu=-d2j.xishu;            he_tail->next=p;            p->next=NULL;            he_tail=p;   

53、;         cha_tail->next=p2;            p2->next=NULL;            cha_tail=p2;        

54、60;       else if(sum1>sum2)            j=i;        for(;j<sum1;j+)              

55、60;     node *p,*p2;            p=new node;            p2=new node;            p

56、->dat.zhishu=d2j.zhishu;            p->dat.xishu=d2j.xishu;            p2->dat.zhishu=d2j.zhishu;            p2

57、->dat.xishu=d2j.xishu;            he_tail->next=p;            p->next=NULL;            he_tail=p;  &#

58、160;         cha_tail->next=p2;            p2->next=NULL;            cha_tail=p2;        

59、        /输出两个表达式的和    printf("两个表达式的和为：n");    output(he);    /输出两个表达式的差    printf("n两个表达式的差为：n");    output(cha);    /表

60、达式乘法    node *chengfa;    chengfa = new node;    chengfa -> next = NULL;    for(i=0;i<sum1;i+)            for(j=0;

61、j<sum2;j+)                    node *p;            p = new node;         

62、   p -> dat.zhishu = d1i.zhishu + d2j.zhishu;            p -> dat.xishu = d1i.xishu * d2j.xishu;          

63、60; p->next=NULL;            node *q;            q = chengfa;            while(q->next)                            if(q->next->dat.zhishu>p->dat.zhishu)