数据结构课程设计-基于线性表的链式存储进行一元多项式的相加减.doc

数 据 结 构 课 程 设 计设计题目： 基于线性表的链式存储实现一元多项式的相加减 13课题名称基于线性表的链式存储进行一元多项式的相加减院 系年级专业学 号姓 名成 绩课题设计目的与设计意义1、 课题设计目的：掌握链表的概念与原理，即链表是用一组任意的存储单元来存放线性表的节点，根据单链表的存储特点来建立两个单链表来分别存储两个一元多项式，然后通过单链表的基本运算中的查找找出这两个单链表中系数相同的项，最后通过合并同类项使这两个一元多项式相加和相减，最后输出它们相加减后的数值。2、 课题设计意义：一元多项式的表示在计算机内可以用线性表中的链表来表示，目的是为了节省存储空间，所以可以只存储多项式中系数非零项的数值。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。指导教师：年 月 日目 录一 需求分析1二 目的和意义1三 问题分析11问题描述12解决路径：13构造数据类型：1四 概要设计2五 算法的基本思想2六 基本算法：21、构造数据类型22、输入输出33、多项式的加法34、多项式的减法45、在主函数中建立菜单56、根据流程图可写出主函数的主要语句56、程序编译图6七 程序设计的心得与体会7八 附录（算法源程序）7九 参考文献14一 需求分析利用线性表的链式存储结构，通过尾插法建立两个单链表，分别存储两个一元多项式，建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，然后依次找出系数相同的项来合并同类项，最后完成两个多项式的加减运算并输出结果。实现本程序需要解决以下几个问题：（1）如何确定要输入的多项式的项数；（2）如何将要输入的两个一元多项式进行显现出来；（3）如何将输入的两个一元多项式进行相加操作；（4）如何将输入的两个一元多项式进行想减操作；二 目的和意义（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计的能力。（2）提高综合运用所学理论知识和方法独立分析和解决问题的能力，加深对数据结构基本知识的掌握和理解。(3)掌握链表的概念与原理，即链表是用一组任意的存储单元来存放线性表的节点，运用线性表的基本运算中的查找找出这两个单链表中系数相同的项，最后通过合并同类项使这两个一元多项式相加和相减，最后输出它们相加减后的数值.三 问题分析1问题描述已知两个一元多项式a和b，试编写一个程序使得一元多项式a和b相加和相减，且输出相加相减后的多项式。2解决路径：利用线性表的链式存储结构，通过尾插法建立两个单链表，分别存储两个一元多项式，建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，然后依次找出系数相同的项来合并同类项，最后完成两个多项式的加减运算并输出结果。3构造数据类型：在计算机内，我们用一个结点来存放多项式的一项，为了节约空间，并和书写习惯一致，只需保留非0系数的项。每个结点分系数,指数和指针三个域。 建立两条循环链表A,B编写程序实现指数相同的项相加。具体思想如下： 若p1-exp=p2-exp，则将两个结点中的系数相加，当和不为0时修改结点p1的系数,否则修改结点p2的系数 若p1-expp2-exp， 则结点p2所指的结点应是“和多项式”中的一项，将结点p2插入在结点p1之前，且令指针p2在原来的链表上后移。 若p1-expexp，则结点p1所指的结点应是“和多项式”中的一项，将结点p1插入在结点p2之前，且令指针p1在原来的链表上后移。四 概要设计 基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加和删除节点数据结构，为了实现任意多项式的加法、减法，因此选择单链表的结构体。一元多项式的表示在计算机内可以用线性表中的链表来表示，目的是为了节省存储空间，所以可以只存储多项式中系数非零项的数值。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。五 算法的基本思想（1） 输入并建立多项式Creatlink()（2）输出多项式，输出形式为整数序列，序列按降序排列。（3）多项式a和b相加，建立多项式a+b，输出相加后的多项式polyadd。（4）多项式a和b相减，建立多项式a-b，输出相加后的多项式polyminus。 六 基本算法：1、构造数据类型根据上面的解决途径可以对指数，系数及指针进行以下说明： typedef struct pnodeint exp; /*指数*/float coef; /*系数*/struct pnode *next;polynode;2、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入开始申请结点空间+num输入多项式的项数指针数组tempi中（i=1num）输入多项式各项的系数 a, 指数 b输出已输入的多项式 合并同类项结束否是是否输入正确3、多项式的加法 “和多项式”链表中的节点不需要另生成，而应该从两个多项式的连表中摘取。其运算规则如下： 假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个节点，则比较两个节点中的指数项，有下列三种情况：（1） 指针qa所指节点的指数值指针qb所指节点的指数值，则应摘取qa所指节点的指数值插入到“和多项式”链表中去；（2） 指针qa所指节点的指数值指针qb所指节点的指数值，则应摘取qb所指节点的指数值插入到“和多项式”链表中去，则将两个节点中的系数相加；（3） 指针qa所指节点的指数值指针qb所指节点的指数值，若和数不等于零，则修改qa所指节点的系数值，同时释放qb所指节点；反之，从多项式A的链表中删除相应节点，并释放指针qa和qb所指节点。4、多项式的减法 两个多项式的减法实现，是从两个多项式的尾部开始，两个多项式的某一项都不为空时：（1）如果指数相等的话，系数就应该相减；相减的和不为零的话，用尾插法建立一个新的节点。（2）P的系数小于q的系数的话，就应该复制q接点到多项式中。（3）P的系数大于q的系数的话，就应该复制p接点到多项式中，并且建立节点的系数为原来的相反数。 （4） 当第二个多项式为空，第一个多项式不为空时，将第一个数剩下的全部用于新节点的产生。当第一个多项式为空，第二个多项式不为空是，将第二个数剩下的全部用于新节点的产生，并且建立的节点的系数为原来的相反数。流程图如下：主程序main（）建立一元多项式Creatlink（）减法Polyminus（）加法polyadd（）显示结果print5、在主函数中建立菜单1.用0和1分别表示建立一元多项式A,B2.用2和3分别表示输出多项式A,B3.用4表示使多项式A和B相加4.用5表示输出相加后的多项式C5.用6表示使多项式A和B相减6.用7表示输出相见后的多项式D。具体如下图所示：菜单建立A建立B输出A输出BAB相加输出CAB相减输出D结束继续01234567016、根据流程图可写出主函数的主要语句switch(i)case 0:creatA();break;case 1:creatB();break;case 2: printA(A)case 3:printA(B);break;case 4: p=polyadd(A,B);break;case 5:printC(p);break;case 6:p=polyminus(A,B);break;case 7:printD(p);break;printf(ntt0:结束ntt1:继续n);scanf(%d,&i);6、程序编译图 图1.菜单图 图2.建立多项式A七 程序设计的心得与体会通过运用线性表的链式存储来实现一元多项式的相加减，设计出了本次的程序，我认识到了要想设计出一个正确而又完整的程序不是想象中那么简单容易的。首先，在设计之前要提前查阅好关于本次设计主题的所需要的资料，要能够很好的掌握主题之后再进行编程，当然，在编写程序的过程当中肯定也会遇到一些问题，只要我们认真的去对待这些问题，耐心的探究那些出问题的地方，我们就能够很好的去解决它。通过此次的关于一元多项式相加减的课题研究，我对数据结构也有了更深一步的了解，也提高了自己运用所学习的理论知识和方法进行实践的能力。只有发现错误才能更好的解决问题，平常不懂得仍需多请教同学和老师，自己应多动手多看书上的题目多找学习的资料，通过这次的课程设计，让我学习到很多，同时也体会到更多，同时也认识到自己的不足。总之，日后需更加努力学习到更多有用的东西。八 附录（算法源程序）一元多项式相加减的程序：#include#includetypedef struct pnodeint exp;float coef;struct pnode *next;polynode;polynode *A,*B,*C,*D;polynode *creatA()polynode *p1,*r;int i,n;A=(polynode*)malloc(sizeof(polynode); A-next=NULL;r=A;printf(请输入A多项式的项数:);scanf(%d,&n);for(i=1;icoef,&p1-exp);r-next=p1;r=p1;r-next=NULL;return A;polynode *creatB() polynode *p2,*r;int i,n;B=(polynode*)malloc(sizeof(polynode);B-next=NULL;r=B;printf(请输入B多项式的项数:);scanf(%d,&n);for(i=1;icoef,&p2-exp);r-next=p2;r=p2;r-next=NULL;return B;void printA(polynode *A)polynode *p1;p1=A-next;while(p1-next!=NULL)if(p1-next-coef0)printf(%.2fx%d+,p1-coef,p1-exp);elseprintf(%.2fx%d,p1-coef,p1-exp);p1=p1-next;printf(%.2fx%d,p1-coef,p1-exp);void printB(polynode *B)polynode *p2;p2=B-next;while(p2-next!=NULL)if(p2-next-coef0)printf(%.2fx%d+,p2-coef,p2-exp);elseprintf(%.2fx%d,p2-coef,p2-exp);p2=p2-next;printf(%.2fx%d,p2-coef,p2-exp);void printC(polynode *C) polynode *p=C-next;while(p-next!=NULL)if(p-next-coef0)printf(%.2fx%d+,p-coef,p-exp);elseprintf(%.2fx%d,p-coef,p-exp);p=p-next;printf(%.2fx%d,p-coef,p-exp);void printD(polynode *D) polynode *p=D-next;while(p-next!=NULL)if(p-next-coef0)printf(%.2fx%d+,p-coef,p-exp);else printf(%.2fx%d,p-coef,p-exp);p=p-next;printf(%.2fx%d,p-coef,p-exp);polynode *polyadd(polynode *A,polynode *B)polynode *p1,*p2,*p,*C;float x;p1=A-next;p2=B-next;p=(polynode*)malloc(sizeof(polynode);p-next=NULL;C=p;while(p1&p2)if(p1-exp=p2-exp)x=p1-coef+p2-coef;if(x!=0)p-next=(polynode*)malloc(sizeof(polynode);p=p-next;p-coef=x;p-exp=p1-exp;p1=p1-next;p2=p2-next;elsep-next=(polynode*)malloc(sizeof(polynode);p=p-next;if(p1-expp2-exp)p-coef=p2-coef;p-exp=p2-exp;p2=p2-next;elsep-coef=p1-coef;p-exp=p1-exp;p1=p1-next;while(p1!=NULL) p-next=(polynode*)malloc(sizeof(polynode); p=p-next; p-coef=p1-coef; p-exp=p1-exp; p1=p1-next; while(p2!=NULL) p-next=(polynode*)malloc(sizeof(polynode); p=p-next; p-coef=p2-coef; p-exp=p2-exp; p2=p2-next;p-next=NULL;return C; polynode *polyminus(polynode *A,polynode *B)polynode *p1,*p2,*p,*D;float x;p1=A-next;p2=B-next;p=(polynode*)malloc(sizeof(polynode);p-next=NULL;D=p;while(p1&p2)if(p1-exp=p2-exp)x=p1-coef-p2-coef;if(x!=0)p-next=(polynode*)malloc(sizeof(polynode);p=p-next;p-coef=x;p-exp=p1-exp;p1=p1-next;p2=p2-next;elsep-next=(polynode*)malloc(sizeof(polynode);p=p-next;if(p1-expp2-exp)p-coef=p2-coef;p-exp=p2-exp;p2=p2-next;elsep-coef=p1-coef;p-exp=p1-exp;p1=p1-next;while(p1!=NULL) p-next=(polyno