数据结构课程设计本课程设计已调试通过，请放心使用。请到：道客巴巴或豆丁网充值购买word版，省打字，直接修改即可，价格较便宜，在这里百度较贵！搜索：数据结构_基于线性表的链式存储进行一元多项式的相加减_课程设计_实验报告
设计题目：基于线性表的链式存储实现一元多项式的相加减
课题名称基于线性表的链式存储进行一元多项式的相加减院系年级专业学号姓名成绩
课题设计目的与设计意义1、课题设计目的：掌握链表的概念与原理，即链表是用一组任意的存储单元来存放线性表的节点，根据单链表的存储特点来建立两个单链表来分别存储两个一元多项式，然后通过单链表的基本运算中的查找找出这两个单链表中系数相同的项，最后通过合并同类项使这两个一元多项式相加和相减，最后输出它们相加减后的数值。2、课题设计意义：一元多项式的表示在计算机内可以用线性表中的链表来表示，目的是为了节省存储空间，所以可以只存储多项式中系数非零项的数值。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行分析，实现一元多项式的相加、相减操作。指导教师：
年月日
目录一需求分析.........................................................................................................................1二目的和意义.....................................................................................................................1三问题分析.........................................................................................................................11．问题描述....................................................................................................................12．解决路径：................................................................................................................13．构造数据类型：........................................................................................................1四概要设计.........................................................................................................................2五算法的基本思想.............................................................................................................2六基本算法：.....................................................................................................................21、构造数据类型............................................................................................................22、输入输出....................................................................................................................3
3、多项式的加法............................................................................................................34、多项式的减法............................................................................................................45、在主函数中建立菜单................................................................................................56、根据流程图可写出主函数的主要语句....................................................................56、程序编译图................................................................................................................6七程序设计的心得与体会.................................................................................................7八附录（算法源程序）.....................................................................................................7九参考文献.......................................................................................................................14
1
一需求分析利用线性表的链式存储结构，通过尾插法建立两个单链表，分别存储两个一元多项式，，建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，然后依次找出系数相同的项来合并同类项，最后完成两个多项式的加减运算并输出结果。实现本程序需要解决以下几个问题：（1）如何确定要输入的多项式的项数；（2）如何将要输入的两个一元多项式进行显现出来；（3）如何将输入的两个一元多项式进行相加操作；（4）如何将输入的两个一元多项式进行想减操作；二目的和意义
（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计的能力。（2）提高综合运用所学理论知识和方法独立分析和解决问题的能力，加深对数据结构基本知识的掌握和理解。(3)掌握链表的概念与原理，即链表是用一组任意的存储单元来存放线性表的节点，运用线性表的基本运算中的查找找出这两个单链表中系数相同的项，最后通过合并同类项使这两个一元多项式相加和相减，最后输出它们相加减后的数值.三问题分析1．问题描述已知两个一元多项式a和b，试编写一个程序使得一元多项式a和b相加和相减，且输出相加相减后的多项式。
2．解决路径：利用线性表的链式存储结构，通过尾插法建立两个单链表，分别存储两个一元多项式，，建立一元多项式并按照指数降序排列输出多项式，将一元多项式输入并存储在内存中，然后依次找出系数相同的项来合并同类项，最后完成两个多项式的加减运算并输出结果。3．构造数据类型：在计算机内，我们用一个结点来存放多项式的一项，为了节约空间，并和书写习惯一致，只需保留非0系数的项。每个结点分系数,指数和指针三个域。建立两条循环链表A,B编写程序实现指数相同的项相加。具体思想如下：
2
①若p1->exp==p2->exp，则将两个结点中的系数相加，当和不为0时修改结点p1的系数,否则修改结点p2的系数②若p1->exp>p2->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、构造数据类型根据上面的解决途径可以对指数，系数及指针进行以下说明：typedefstructpnode{intexp;/指数/floatcoef;/系数/structpnodenext;}polynode;
3
2、输入输出（1）功能：将要进行运算的多项式输入输出。（2）数据流入：要输入的多项式的系数与指数。（3）数据流出：合并同类项后的多项式。（4）程序流程图：多项式输入流程图如图1所示。（5）测试要点：输入的多项式是否正确，若输入错误则重新输入
3、多项式的加法“和多项式”链表中的节点不需要另生成，而应该从两个多项式的连表中摘取。其运算规则如下：假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个节点，则
开始申请结点空间输入多项式的项数输入多项式各项的系数a,指数b输出已输入的多项式
合并同类项结束否是是否输入正确
4
比较两个节点中的指数项，有下列三种情况：（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（）加法polyadd（）减法Polyminus（）
显示结果print
5
5、在主函数中建立菜单1.用0和1分别表示建立一元多项式A,B2.用2和3分别表示输出多项式A,B3.用4表示使多项式A和B相加4.用5表示输出相加后的多项式C5.用6表示使多项式A和B相减6.用7表示输出相见后的多项式D。具体如下图所示：01234567
016、根据流程图可写出主函数的主要语句switch(i){case0:creatA();break;case1:creatB();break;
case2:printA(A)case3:printA(B);break;case4:p=polyadd(A,B);break;case5:printC(p);break;case6:p=polyminus(A,B);break;case7:printD(p);break;
菜单建立A建立B输出A输出BAB相加输出CAB相减输出D
结束继续
6
}printf("\n\t\t0:结束\n\t\t1:继续\n");scanf("%d",&i);}6、程序编译图
图1.菜单图
7
图2.建立多项式A七程序设计的心得与体会通过运用线性表的链式存储来实现一元多项式的相加减，设计出了本次的程序，我认识到了要想设计出一个正确而又完整的程序不是想象中那么简单容易的。首先，在设计之前要提前查阅好关于本次设计主题的所需要的资料，要能够很好的掌握主题之后再进行编程，当然，在编写程序的过程当中肯定也会遇到一些问题，只要我们认真的去对待这些问题，耐心的探究那些出问题的地方，我们就能够很好的去解决它。通过此次的关于一元多项式相加减的课题研究，我对数据结构也有了更深一步的了解，也提高了自己运用所学习的理论知识和方法进行实践的能力。只有发现错误才能更好的解决问题，平常不懂得仍需多请教同学和老师，自己应多动手多看书上的题
目多找学习的资料，通过这次的课程设计，让我学习到很多，同时也体会到更多，同时也认识到自己的不足。总之，日后需更加努力学习到更多有用的东西。八附录（算法源程序）一元多项式相加减的程序：#include#includetypedefstructpnode{
8
intexp;floatcoef;structpnodenext;}polynode;polynodeA,B,C,D;polynodecreatA(){polynodep1,r;inti,n;A=(polynode)malloc(sizeof(polynode));
A->next=NULL;r=A;printf("请输入A多项式的项数:");scanf("%d",&n);for(i=1;i<=n;i++){p1=(polynode)malloc(sizeof(polynode));printf("请输入A的第i项的系数和指数:",i);scanf("%f%d",&p1->coef,&p1->exp);r->next=p1;
r=p1;}r->next=NULL;returnA;}polynodecreatB(){polynodep2,r;inti,n;B=(polynode)malloc(sizeof(polynode));
B->next=NULL;r=B;printf("请输入B多项式的项数:");scanf("%d",&n);for(i=1;i<=n;i++){p2=(polynode)malloc(sizeof(polynode));
9
printf("请输入B的第i项的系数和指数:",i);scanf("%f%d",&p2->coef,&p2->exp);r->next=p2;r=p2;}r->next=NULL;returnB;}voidprintA(polynodeA){
polynodep1;p1=A->next;while(p1->next!=NULL){if(p1->next->coef>0)printf("%.2fx^%d+",p1->coef,p1->exp);elseprintf("%.2fx^%d",p1->coef,p1->exp);p1=p1->next;}
printf("%.2fx^%d",p1->coef,p1->exp);}voidprintB(polynodeB){polynodep2;p2=B->next;while(p2->next!=NULL){if(p2->next->coef>0)
printf("%.2fx^%d+",p2->coef,p2->exp);elseprintf("%.2fx^%d",p2->coef,p2->exp);p2=p2->next;}printf("%.2fx^%d",p2->coef,p2->exp);
10
}voidprintC(polynodeC){polynodep=C->next;while(p->next!=NULL){if(p->next->coef>0)printf("%.2fx^%d+",p->coef,p->exp);elseprintf("%.2fx^%d",p->coef,p->exp);
p=p->next;}printf("%.2fx^%d",p->coef,p->exp);}voidprintD(polynodeD){polynodep=D->next;while(p->next!=NULL){if(p->next->coef>0)
printf("%.2fx^%d+",p->coef,p->exp);elseprintf("%.2fx^%d",p->coef,p->exp);p=p->next;}printf("%.2fx^%d",p->coef,p->exp);}polynodepolyadd(polynodeA,polynodeB){polynodep1,p2,p,C;
floatx;p1=A->next;p2=B->next;p=(polynode)malloc(sizeof(polynode));p->next=NULL;C=p;while(p1&&p2)
11
{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;}else{p->next=(polynode)malloc(sizeof(polynode));p=p->next;if(p1->exp>p2->exp){
p->coef=p2->coef;p->exp=p2->exp;p2=p2->next;}else{p->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;
12
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;returnC;}polynodepolyminus(polynodeA,polynodeB){polynodep1,p2,p,D;floatx;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;
13
}else{p->next=(polynode)malloc(sizeof(polynode));p=p->next;if(p1->exp>p2->exp){p->coef=p2->coef;p->exp=p2->exp;p2=p2->next;
}else{p->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;returnD;
14
}voidmain(){polynodep1,p2,p;inti;while(i){printf("\t\t0:创建多项式A\n\t\t1:创建多项式B\n\t\t2:输出多项式A\n\t\t3:输出多项式B\n\t\t4:多项式A与多项式B相加\n\t\t5:输出相加后的多项式C\n\t\t6:多项式A与多项式B相减\n\t\t7:输出相减后的多项式D\n");
scanf("%d",&i);switch(i){case0:creatA();break;case1:creatB();break;case2:printA(A);break;case3:printB(B);break;case4:p=polyadd(A,B);break;case5:printC(p);break;case6:p=polyminus(A,B);break;
case7:printD(p);break;}printf("\n\t\t0:结束\n\t\t1:继续\n");九参考文献[1].唐策善、李龙谢、黄刘生.数据结构—用C语言描述.高等教育出版社。[2].孙家启.C语言程序设计教程.合肥工业大学出版社。
|
|
