数据结构-利用线性表链式存储实现一元多项式相加减-课程设计-实验报告

(2023)数据结构利用链表计算一元多项式课程设计实验报告(一)2023数据结构课程设计实验报告——利用链表计算一元多项式实验背景和目的在本课程设计实验中，我们旨在通过使用链表数据结构，实现对一元多项式的计算功能。

通过本次实验，我们将深入学习和掌握链表的基础知识和应用技能，掌握实现链表操作的代码实现方式，提高编程实践能力和解决问题的能力。

思路和方法首先，我们需要定义链表节点数据结构，包含多项式中的系数和指数两个数据成员。

然后，我们需要实现一元多项式的相加、相减、求导、求值等基本操作。

其中，相加和相减操作需要利用链表遍历的方式，比较两个多项式中的指数，进行对应系数的加减，并将结果存储到新的链表中。

求导操作只需要遍历链表，将每一项的指数减一，系数乘以指数值，再将其插入到新的链表中即可。

求值操作仅需要遍历链表，根据指数和系数计算多项式值即可。

在具体实现过程中，我们需要注意边界条件的判断和处理，如何处理空链表、单项式情况等。

还需要精细设计代码逻辑，避免重复遍历链表，浪费时间和空间资源。

结果分析和展示经过数次测试和调试，我们最终实现了一元多项式的链表计算功能。

我们在终端输入多项式的系数和指数，再根据指令进行相应的操作。

结果能够准确输出，并且经过大量数据测试，程序运行稳定，没有出现崩溃和错误的情况。

总结和反思通过本次实验，我们进一步深入学习了链表数据结构的应用方法和相关算法。

我们学会了如何通过遍历链表实现复杂计算操作，如一元多项式的求导、求值等。

在实现过程中，我们对代码结构和逻辑设计进行反复思考和优化，提高了自己的编程能力和解决问题的能力。

同时，我们也需要进一步加强数据结构的学习，提升自己的算法水平，为后续的专业学习和职业发展打下坚实的基础。

可能的改进和优化方案虽然我们已经实现了一元多项式链表计算功能，但是我们也发现了以下几点可以改进和优化的方案：•异常处理：在用户输入有误或者数据不规范的情况下，程序可能会出现崩溃或者不符合预期的结果。

数据结构实验报告实验名称：实验一——线性表日期：2013年10月28日1．实验要求实验目的1、熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法2、学习指针、模板类、异常处理的使用3、掌握线性表的操作的实现方法4、学习使用线性表解决实际问题的能力实验内容利用线性表实现一个一元多项式Polynomialf(x) = a0 + a1x + a2x2 + a3x3+ … + a n x nPolynomial的结点结构如下：struct term{float coef; //系数int expn; //指数};要求：1、能够实现一元多项式的输入和输出2、能够进行一元多项式相加3、能够进行一元多项式相减4、能够计算一元多项式在x处的值5、能够计算一元多项式的导数（选作）6、能够进行一元多项式相乘（选作）7、编写测试main()函数测试线性表的正确性2. 程序分析考虑到数据结构的实现，因为多项式是线性结构因此选择线性表，而本次实验中涉及到多项式的加减，要进行节点的添加或者删除，用顺序表显然不能满足要求，而且由于不知道多项式的项数，很容易造成空间的浪费，当两个多项式指数相差很远时，操作要移动很多项，步骤很麻烦繁琐。

综上，我选择了单链表，每个节点有三个部分，分别储存系数、指数、和指针，这样在计算加减或者指数不等时，只需要简单的摘连加链即可，而且不会造成空间的太多浪费。

每次利用尾插法将结点插入基准多项式。

2.1 存储结构本次实验采取的多项式加减算法是将一个多项式作为基准，把另一个多项式加到基准多项式中去，求和后的多项式仍然存储在第一个线性表中，因此用单链表的数据结构更为方便。

单链表存储结构在本次实验中，因为形式的特殊性，每个节点如下图表示：空链表 非空链表其中每个结点前两个分别储存float 型系数coef 和int 型指数expn ，第三个作为指针指向下一个节点（不是最后一个结点时，否则为NUll ）2.2 关键算法分析1、输入多项式自然语言描述：1) 指定多项式的项数n2) 建立一个叫term 的struct 结构类型，用来储存指定多项式的系数和指数的数据。

韶关学院计算机科学学院数据结构课程设计题目：多项式运算学生姓名：学号：专业：班级：指导教师姓名及职称：讲师起止时间：年月——年月1.课题分析1.1课题背景及意义《数据结构课程设计》是一门实践性的计算机课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。

通过这次课程设计，要求掌握较大程序的设计方法，相应数据结构的选择应用、算法的设计及其实现和性能分析等方面中加深对课程基本内容的理解。

同时，在设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

1.2程序功能本程序的功能是建立按照指数降序排列的两个一元多项式，并能够完成加、减和乘运算，最后将结果按照指数降序排列显示出来。

输入和输出值范围：系数精确到小数点6位，指数以整数表示。

输入形式：系数指数系数指数……0 0 //以0 0作为结束输出形式：fk(x)=系数x^指数+系数x^指数+……+0 x^01.3测试数据：1）加法操作:请输入第一个要操作的多项式：请按多项式指数由高到低输入系数和指数：（以0 0结束）8 64 5-2 4-123 3-1 110 00 0fa(x)=(8.000000x^6)+(4.000000x^5)+(-2.000000x^4)+(-123.000000x^3)+(-1.000000x ^1)+(10.000000x^0)请输入第二个要操作的多项式：请按多项式指数由高到低输入系数和指数：（以0 0结束）2 3-5 21 10 0fb(x)=(2.000000x^3)+(-5.000000x^2)+(1.000000x^1)请选择你要进行的操作:1.多项式相加2.多项式相减3.多项式相乘1fa(x)+f(b)=(8.000000x^6)+(4.000000x^5)+(-2.000000x^4)+(-121.000000x^3)+(-5.000 000x^2)+(10.000000x^0)2）减法操作:请输入第一个要操作的多项式：请按多项式指数由高到低输入系数和指数：（以0 0结束）8 64 5-2 4-123 3-1 110 00 0fa(x)=(8.000000x^6)+(4.000000x^5)+(-2.000000x^4)+(-123.000000x^3)+(-1.000000x ^1)+(10.000000x^0)fa(x)=(3.000000x^3)+(2.000000x^2)请输入第二个要操作的多项式：请按多项式指数由高到低输入系数和指数：（以0 0结束）2 3-5 21 10 0fb(x)=(2.000000x^3)+(-5.000000x^2)+(1.000000x^1)请选择你要进行的操作:1.多项式相加2.多项式相减3.多项式相乘2fa(x)-fb(x)=(8.000000x^6)+(4.00000x^5)+(-2.000000x^4)+(-125.000000x^3)+(-5.0000 00x^2)+(-2.000000x^1)+(10.000000x^0)3）乘法操作:请输入第一个要操作的多项式：请按多项式指数由高到低输入系数和指数：（以0 0结束）8 64 5-2 4-123 3-1 110 00 0fa(x)=(8.000000x^6)+(4.000000x^5)+(-2.000000x^4)+(-123.000000x^3)+(-1.000000x ^1)+(10.000000x^0)fa(x)=(3.000000x^3)+(2.000000x^2)请输入第二个要操作的多项式：请按多项式指数由高到低输入系数和指数：（以0 0结束）2 3-5 21 10 0fb(x)=(2.000000x^3)+(-5.000000x^2)+(1.000000x^1)请选择你要进行的操作:1. 多项式相加2. 多项式相减3. 多项式相乘3fa(x)*fb(x)=(16.000000x^9)+(-32.000000x^8)+(-16.000000x^7)+(-232.000000x^6)+(6 13.000000x^5)+(-125.000000x^4)+(25.000000x^3)+(-51.000000x^2)+(10.000000x^1) 2.概要设计2.1本程序包含的模块typedefstructLinkNode //定义单向链表{}linknode;voidcreatelink(linknode *head){ }；//构建一个以单链表存储的多项式void show(linknode *head){ }；//显示多项式voidaddtion(linknode *fa,linknode *fb,linknode *fc){ }；//加法操作void subtraction(linknode *fa,linknode *fb,linknode *fc){ } ；//减法操作void multiply(linknode *fa,linknode *fb,linknode *fc){ }；//乘法操作voidsortion(linknode *fc){ }；//将乘法所得的结果合并同类项void deletion(linknode *head,linknode *s);{ }；//删除结点操作voidmian(){ }；//主程序2.2问题解决的思路概述首先是确定结构化程序设计的流程图，利用已存在的数据结构来构造一个存储一元多项式的结构，接着把三则运算分成五个主要的模块：实现加法的模块、实现减法的模块、实现乘法的模块、实现合并同类项模块、删除结点模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。

数据结构课程设计设计题目：基于链式表实现一元多项式的加减乘运算目录问题分析11.1 问题描述设计一个n元多项式程序，并完成多项式的乘法运算。

从实际的角度出发，这里设计的程序是基于一元n次多项式的数学模型。

1.2 问题的数学模型在数学上，一个一元多项式Pn(x>可按升幂写成：Pn(x>=a 0+a1 x+a2 x^2 +…+a n x^n-1.它由n+1个系数惟一确定，因此，在计算机里，它可用一个线性表P来表示：Pn=(a0,a1,a2,…,an>每一项的指数i隐含在其系数ai的序号里。

多项式的乘法规则：多次运用单项式与多项式相乘的法则得到的．计算时(a+b>(m+n>，先把(m+n>看成一个单项式，(a+b>是一个多项式，运用单项式与多项式相乘的法则，得到(a+b>(m+n>=a(m+n>+b(m+n>,然后再次运用单项式与多项式相乘的法则。

1.3 构造数据结构通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0时，该项就失去了意义，在计算机内要表示一个多项式，至少以下数据信息：系数信息、指数信息和指向下一个单项式的指针。

通过指针，我们就可以把多个单项式连接起来，形式一个多项式，需要说明的是从广义的角度讲，单项式也是一个多项式。

基于以上的分析，我们定义多项式的数据结构为如下结构体形式：typedef struct Polynomial{float coef。

//系数int expn。

//指数struct Polynomial *next。

//指向下一个结点}*Polyn,Polynomial。

//Polyn为结点指针类型2 系统分析2.1 可行性研究该程序主要从技术的角度来分析可行性。

技术上的可行性研究主要分析技术条件能否顺利完成开发工作，硬、软件能否满足开发者的需要等。

该系统采用了Windows XP操作系统结合Visual C++ 6.0,TC 2.0等软件开发平台已成熟可行。

实验报告课程名称____数据结构上机实验__________ 实验项目______线性表的应用 ____________实验仪器________PC机___________________系别_____电子信息与通信学院___专业________ ___班级/学号______ __学生姓名______ ___________实验日期_______________________成绩_______________________指导教师_______________________实验一.线性表的应用1.实验目的：掌握线性链表的存储、运算及应用。

利用链表实现一元多项式计算。

2.实验内容：1)编写函数，实现用链表结构建立多项式；2)编写函数，实现多项式的加法运算；3)编写函数，实现多项式的显示；4)测试：编写主函数，它定义并建立两个多项式，显示两个多项式，然后将它们相加并显示结果。

变换测试用的多项式，检查程序的执行结果。

选做内容：修改程序，选择实现以下功能：5)多项式求值：编写一个函数，根据给定的x值计算并返回多项式f(x)的值。

测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。

6)多项式相减：编写一个函数，求两个多项式相减的多项式。

7)多项式相乘：编写一个函数，求两个多项式的乘积多项式。

3.算法说明：1)多项式的建立、显示和相加算法见讲义。

可修改显示函数，使输出的多项式更符合表达规范。

2)多项式减法：同次项的系数相减（缺项的系数是0）。

例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x)=4x3-5x2-x+3。

提示：a(x)-b(x) = a(x)+(-b(x))。

3)多项式乘法：两个多项式的相乘是“系数相乘，指数相加”。

算法思想是用一个多项式中的各项分别与另一个多项式相乘，形成多个多项式，再将它们累加在一起。

例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3)= (20x5-8x4-12x3) + (-15x3+6x2+9x) =20x5-8x4-27x3+6x2+9x。

##大学数据结构课程设计报告题目：顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现院（系）：计算机工程学院学生姓名:班级：学号:起迄日期: 2011.06.20-06.30指导教师:2010—2011年度第 2 学期一、需求分析1、顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。

可以分为几个模块：输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。

2、在程序过程中加入汉字提示符，让读者清楚明白的操作该程序。

运行程序时看起来简洁有序，操作简单明了3、程序执行时的命令：①选择创建两个一元多项式②输入第一个一元多项式的项数③依次输入一元多项式的系数和指数④以相同方式输入第二个一元多项式⑤选择操作方式⑥选择降幂或升幂排序⑦输出结果⑧是否退出。

4、测试数据。

输入的一元多项式系数指数分别为7 0,3 1,9 8,5 17和8 1,22 7，-9 8。

加法结果为；升幂降幂减法结果为：升幂降幂乘法结果为：升幂降幂二、概要设计1、设计思路：在该程序中分别分为顺序存储和链式存储结构。

2、数据结构设计：一元多项式抽象数据类型的定义：ADT Polynomial{数据对象：D={ai|ai∈TermSet,i=1,2…,m,m>=0TermSet中的每一个元素包含一个表示系数的实数和表示指数的整数}数据关系:R1={<ai-1,ai>|ai-1,ai∈D, 且ai-1中的指数值<ai中的指数值，i=2,…,n} 基本操作：CreatPolyn(&P,m)操作结果：输入m项的系数和指数，建立一元多项式P.DesteoyPolyn(&P)初始条件：一元多项式P已存在。

操作结果：销毁一元多项式P。

PrintfPolyn(P)初始条件：一元多项式P已存在。

操作结果：打印输出一元多项式P。

PolynLength(P)初始条件：一元多项式P已存在。

简单介绍：本次作业力在学会链表表示线性表的插入、删除、查找等基本操作设计与实现，学习利用链表提供的接口去求解实际问题，同时熟悉链表的的存储方法。

再基于线性链表的基础设计完成多项式的相加运算程序。

一、实验目的和要求完成多项式的相加、相乘运算。

（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、实验内容和原理1.实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加运算。

利用单链表实现。

2.实验原理使用单链表实现一元多项式的存储，并实现两个一元多项式的加法运算。

三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统（2）VC6.0四、算法描述及实验步骤1、描述：加法：输入建立一元多项式,进行简单加法运算,输出结果；通过建立单链表A和B分别存放多项式的a和b的各项系数及指数；并且利用A使得不产生新的节点而在A中存放数据运算结果；该过程通过定义指针变量p和q使它们分别指向两个多项式的第一个节点，之后依次比较它们所指向的项的指数，即一种情况指数相等时系数相加且和不为零，修改当前p所指项的系数（和），同时删除q所指项，若和为零则同时删除p和q各自所指；情况二，p当前项指数大于q当前项，将q所指插入p所指之前作为结果项之一；情况三，p当前项指数小于q当前项，p所指作为多项式和的一项，移动p指向下一项，进行比较，在移动p，q至其中以个链空，把另一个链余下节点插在p所指之后；乘法：定义指针p,q指向所操作节点，通过A链表的每一项与B链表各项相乘，指数相加，系数相乘，将值赋给新节点各自域，构成一新的链表，最后返回头结点。

可这样有一个问题，即新生成的链表，即最终结果混乱，没有对数据进行过滤，相同指数项应在执行加法运算，所以可以这样实现，通过A链表的每一项与B链表各项相乘的新生成节点单独构成一链表，并将第一个链表加入另一新链表，循环此操作将后生成的链表加之先前的链表，即可实现排序问题。

南昌航空大学实验报告课程名称：数据结构实验名称：实验二线性表的链式存储结构班级：080611 学生姓名：学号：08指导教师评定：签名:题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。

一、需求分析1.用户可以根据自己的需求分别输入两个一元多项式，并且能够实现输入的一元多项式的显示。

2.能够完成两个一元多项式的相加功能，而且还能显示相加后的逆置的一元多项式。

3.程序执行的命令包括：（1）构造链表A （2）构造链表B （3）两个链表的相加（4）求链表的长度（5）打印（显示）已有的链表（6）将已相加的链表进行逆序排列二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Polynomial {数据对象：D={a i:|a i∈TermSet,i=1…n,n≥0TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={<a i-1,a i>|a i-1,a i∈D,且a i-1中的指数值< a i中的指数值i=2,…n≥0}基本操作:initlink(& L)操作结果：构造一个空的链表L。

Creatlink(&L,n)操作结果：输入n项的系数和指数，建立一个非空的一元多项式L。

LinkLength(L)初始条件：链表L已经存在。

操作结果：返回一元多项式L中的项数。

Displaylink（L）初始条件：链表L已经存在。

操作结果：打印输出一元多项式L。

Addpolyn(A,B,&C)初始条件：一元多项式A和B已存在。

操作结果：完成多项式相加运算，即：C=A+B，并且带回C。

subtracypolyn(&La,&Lb,)初始条件：一元多项式La和Lb已存在。

操作结果：完成多项式的相减运算La=La+Lb，并且销毁多项式Lb。

数据结构实验报告（⼀）线性表的应⽤实验说明数据结构实验⼀ 线性表的实验——线性表的应⽤⼀、实验⽬的通过本实验使学⽣了解线性表的⼀种简单应⽤，熟悉线性表顺序存储与链式存储的特性，特别训练学⽣编程灵活控制链表的能⼒，为今后编程控制更为复杂的数据结构奠定基础。

⼆、实验内容1.⽤顺序表和链表分别分别编程实现教材中例⼦2-1与2-2。

要求：（1）只能⽤C语⾔编程实现；（2）完全保持书中算法2.1与算法2.2形式，不允许有任何变化，除⾮语法上不允许;所调⽤各函数参照书中19页的功能描述，其中函数名、参数个数及性质、函数功能必须与书中完全⼀致，不能有变化。

2.利⽤线性表表⽰⼀元多项式完成多项式的加、减、乘、求导、求值运算。

要求：（1）输⼊的⼀元多项式可以采⽤只输⼊各项的系数与指数这种简化的⽅式。

如对于多项式2x2+6x5，输⼊可为： 2,2 6,5 这样的简单形式。

（2）遇到有消项时应当处理，如2x2+6x5与3x2-6x5进⾏相加时，结果为5*x^2。

（3）当给定x的值时，能计算表达式相加或相减的结果。

（4）操作的结果放⼊⼀个新线性表中，原来的两个表达式存储表⽰不变，也可以不是产⽣新的线性表，⽽是将两上线性表合并为⼀个。

（5）要求程序功能模块划分合理（每个函数功能单⼀、可重⽤性好），使⽤空间尽可能少，算法尽可能⾼效。

实验报告1.实现功能描述使⽤线性表表⽰⼀元多项式完成多项式的加、减，乘，求导、求值运算。

2.⽅案⽐较与选择（1）因为使⽤的是线性表，所以主要⽅案有数组法和链表法。

（2）从时间复杂度来说，使⽤数组法更优；从空间复杂度来说，链表法更优。

因为数组法是指定好空间的，若式⼦⼤⼩超出设置⼤⼩，那程序必然出错；若式⼦⼤⼩⼩于设置⼤⼩，那就意味着有多余的空间被浪费了。

综合来讲，若计算式⼦较为庞⼤，使⽤链表法更佳；相反，若计算式⼦较⼩，数组法更佳。

3.设计算法描述（1）单个项式的数据存储使⽤了结构体，数组法是在⼀个结构体中定义两个⼀维数组；链表法是通过⼀个结构体作为⼀个节点，通过next指针连接起来。

数据结构课程设计设计题目：利用线性表链式存储实现一元多项式相加减学生姓名：专业班级：指导教师：完成时间：信息工程学院信息与计算科学系课程设计成绩评定表(本科)目录第一章、课题描述 (1)第二章、课题设计目的 (1)第三章、课题设计意义 (1)第四章、设计思路 (1)第五章、需求分析 (2)第六章、概要设计 (2)6.1、存储结构： (2)6.2、基本算法： (2)6.2.1、输入输出 (2)6.2.2、构造数据类型 (3)6.2.3、多项式的加法 (4)6.2.4、多项式的减法 (4)第七章、程序结果及截图 (4)第八章、算法的时间复杂度及改进 (5)第九章、总结及心得体会 (5)第十章、附录 (6)第十一章、参考文献 (13)第一章、课题描述能够完成两个或多个多项式的输出，并且实现两个多项式的相加和相减，并且输出结果。

第二章、课题设计目的了解数据结构与算法的设计方法，独立分析和设计一元多项式加减的程序编码，通过程序编写掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能，提高综合运用所学的理论知识和方法独立分析和解决问题的能力，通过这次实践将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理，掌握线性表的链式存储如何实现一元多项式的加减，通过不断探索程序的算法，不断优化程序，使得学生的知识掌握更加牢固，实践能力加强，也激发了学生对于数据结构这门课的兴趣，为以后这门课的深入研究做了准备，这次实践使同学更加深入了解了数据结构内在的逻辑关系。

第三章、课题设计意义通过完成此次课题，可以了解各种数据结构内在的逻辑关系，讨论它在计算机中的存储表示，以及在其上进行各种运算时的算法实现，并对算法的效率和优化进行简单的分析和讨论，不仅加强了学生对于线性表链式存储的理解，也提高了学生的思维能力，促进学生的综合应用能力和专业素质的提高，解决了现实生活中复杂繁琐的计算过程，不仅提高了效率，也增加了正确率，学生对于线性表和指针等知识的理解更加深入深刻，也灵活运用了理论知识解决了实际问题，活学活用，加强了学生的实践能力，同时完成作业还需要与同学的讨论，增强了学生的团队合作能力。

多项式实验报告2011-4-9实验题目：一元多项式的表示及四则运算实验目的：1.了解线性表的链式存储结构，熟悉掌握链表2.了解作为链表的多项式存储方式3.熟悉掌握多项式加减乘除四则运算的算法实验内容:一、抽象数学模型：ADT Polynomial{数据对象：D={ai|ai∈TermSet,i=1,2,···，m, m>=0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数} 数据关系：R1={<ai-1,ai>|ai-1,ai∈D,且ai-1中的指数值<ai中的指数值，i=2,···，n}基本操作：Insert(p,h);初始条件：多项式p与h已存在操作结果：合并指数相同的项CreatePolyn(& head, m)操作结果：建立一个头指针为head、项数为m的一元多项式DestroyPolyn(& p)初始条件：一元多项式P已存在操作结果：销毁多项式pPrintPolyn( P)初始条件：一元多项式P已存在操作结果：打印输出一元多项式PAddPolyn(&pa,& pb)初始条件：一元多项式Pa和Pb已存在操作结果：求解并建立多项式Pa=Pa+Pb, 返回其头指针SubtractPolyn(& pa，& pb)初始条件：一元多项式Pa和Pb已存在操作结果：求解并建立多项式Pa=Pa-Pb，返回其头指针MultiplyPolyn(& pa,& pb)初始条件：一元多项式Pa和Pb已存在操作结果：求解并建立多项式Pa=Pa*Pb，返回其头指针DevicePolyn(& pa,& pb)初始条件：一元多项式Pa和Pb已存在操作结果：求解并建立多项式Pa=Pa/Pb，返回其头指针}ADT Polynomial二、算法描述：为了实现上述程序功能，根据一元多项式的特点，可以构造链式存储的线性表存放一元多项式各式的信息。

线性表的链式存储结构实验报告文件编码（008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256）实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：班级：数媒1401 姓名：范业嘉学号 08一、实验目的掌握线性表的链式存储结构设计与基本操作的实现。

二、实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。

⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。

三、数据结构设计1.按所用指针的类型、个数、方法等的不同，又可分为：线性链表（单链表）静态链表循环链表双向链表双向循环链表2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。

四、算法设计1.定义一个链表void creatlist(Linklist &L,int n){int i;Linklist p,s;L=(Linklist)malloc(sizeof(Lnode));p=L;L->next=NULL;for(i=0;i<n;i++){s=(Linklist)malloc(sizeof(Lnode));scanf("%d",&s->data);s->next=NULL;p->next=s; p=s;}}2.（1）两个链表的合并void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc) {Linklist pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;} }pc->next=papa:pb;free(Lb);}（2）两个链表的并集Linklist unionlist(Linklist &La,Linklist &Lb){Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){flag=0;p2=Lb->next;while(p2){if(p1->data==p2->data){flag=1;break;}p2=p2->next;}if(flag==0){s=(Linklist)malloc(sizeof(Lnode));s->data=p1->data;q->next=s;q=s;}p1=p1->next;}q->next=Lb->next;return head;}3.（1）一元多项式的加法List addpoly(List pa,List pb)3.六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。

试验一多项式相加一. 实验内容：多项式相加二.实验目的和要求：利用双向链表实现通讯录的建立、删除、检索和列表，并可保存至文件，可重新装入。

用链式存储结构实现一元多项式的相加运算。

三．算法思想描述:1. 以单链表为存储结构插入多项式: 多项式输入：多项式按幂从高到低，以“系数，幂”的格式输入，并以“0，0”结束。

printf("Please input coef:");scanf("%d",&i);printf("Please input exp: ");scanf("%d",&j);while(i!=0){q=(pnode)malloc(sizeof(struct node));q->coef=i;q->exp=j;p->link=q;p=q;printf("Please input coef:");scanf("%d",&i);printf("Please input exp: ");scanf("%d",&j);}p->link=NULL;2. 多项式相加单链表合并:由两个多项式对应的单链表头节点开始，依次扫描各节点。

(1)若两表的节点均非空：比较二者的幂，按幂大者先入表。

如果幂相等，则系数相加再入表。

具体由以下代码实现：while(p!=NULL && q!=NULL){if(p->exp==q->exp){x=p->coef+q->coef;if(x!=0){s=(pnode)malloc(sizeof(struct node));s->coef=x;s->exp=p->exp;r->link=s;r=s;}p=p->link;q=q->link;}else if(p->exp<q->exp){s=(pnode)malloc(sizeof(struct node));s->coef=q->coef;s->exp=q->exp;r->link=s;r=s;q=q->link;}else{s=(pnode)malloc(sizeof(struct node));s->coef=p->coef;s->exp=p->exp;r->link=s;r=s;p=p->link;}(2). 若有一链表已空，则将非空链表插入新表：while(p!=NULL){s=(pnode)malloc(sizeof(struct node));s->coef=p->coef;s->exp=p->exp;r->link=s;r=s;p=p->link;}while(q!=NULL){s=(pnode)malloc(sizeof(struct node));s->coef=q->coef;s->exp=q->exp;r->link=s;r=s;q=q->link;}3. 输出合并后的链表:while(head->link!=NULL){head=head->link;printf(" %d*x^%d",head->coef,head->exp);}4. 主函数调用，完成多项式相加。

山东理工大学计算机学院课程设计（数据结构）班级计科1102姓名张汝全学号1111051010指导教师肖爱梅2013年1 月7 日课程设计任务书及成绩评定课题名称动态链表结构下的一元多项式的加法、减法和乘法的实现。

Ⅰ、题目的目的和要求：1.巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2.设计题目要求：1)首先判定一元多项式是否稀疏2)分别采用顺序和链式结构实现；3)结果在M(x)中无重复阶项和无零系数项；4)要求结果以升幂排列输出Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二年月日目录第一章概述 (1)第二章系统分析 (2)第三章概要设计 (3)第四章详细设计 (4)第五章运行与测试 (18)第六章总结与心得 (20)参考文献 (21)第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。

课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。

《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

利用线性表链式存储实现一元多项式相加减课程设计，实验报告数据结构课程设计设计题目:利用线性表链式存储实现一元多项式相加减学生姓名: 专业班级: 指导教师: 完成时间:信息工程学院信息与计算科学系课程设计成绩评定表(本科)课题名称利用线性表链式存储实现一元多项式相加减院系年级专业学号姓名成绩1、课题设计目的:了解数据结构与算法的设计方法，独立分析和设计一元多项式加减的程序编码，通过程序编写掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能，提高综合运用所学的理论知识和方法独立分析和解决问题的能力，通过这次实践将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理，掌握线性表的链式存储如何实现一元多项式的加减。

1、课题设计意义:课题设计通过完成此次课题，可以了解各种数据结构内在的逻辑关系，讨论它在计算机中的存储表示，以及在其上进行各种运算时的算法实目的与现，并对算法的效率和优化进行简单的分析和讨论，不仅加强了学生对于线性表链式存储的理解，也提高了学生的思维能力，促进学设计意义生的综合应用能力和专业素质的提高。

指导教师:年月日目录第一章、课题描述 (1)第二章、课题设计目的 .................................................... 1第三章、课题设计意义 .................................................... 1 第四章、设计思路 ....................................................... 1 第五章、需求分析 . (2)概要设计 (2)第六章、6.1、存储结构: .....................................................26.2、基本算法: .....................................................26.2.1、输入输出 (2)6.2.2、构造数据类型 (3)6.2.3、多项式的加法 (4)6.2.4、多项式的减法 (4)第七章、程序结果及截图 ..................................................4 第八章、算法的时间复杂度及改进 .......................................... 5 第九章、总结及心得体会 ................................................. 5 第十章、附录 ............................................................ 6 第十一章、参考文献 .. (13)第一章、课题描述能够完成两个或多个多项式的输出，并且实现两个多项式的相加和相减，并且输出结果。

数据结构课程设计设计题目：基于线性表链式存储实现一元多项式加减课题名称基于线性表的链式存储实现一元多项式的相加减姓名成绩课题设计目的与设计意义1、课题设计目的：（1）.熟练掌握线性表链式存储基本的存储形式：单链表，循环链表以及双链表(2).熟练运用线性表链式存储的基本运算(3).能应用循环链表实现一元多项式的相加减(4).将一元多项式相加减的思想利用C语言编写程序在计算机上实现2、课题设计意义：（1）.进一步了解循环链表的特点：无须增加存储量，仅对表的连接方式稍作改变，即可使得表处理更加方面灵活（2）.学会将数学语言转化为计算机语言（3）.懂得课程设计的格式及要求，有利于以后写毕业论文（4）.耐心，细心以及广泛的材料收集的成功的前提指导教师：年月日目录第一章．课程设计的目的与意义41.1课题设计的目的41.2课题设计的意义4第二章．课题设计的内容和要求42.1 课题设计的内容42.2 课题设计的要求4第三章．问题分析43.1问题描述43.2解决途径53.2.1顺序表与链式表的比较53.2.2构造数据类型5第四章．概要设计54.1构造数据类型54.2基本运算64.2.1主函数64.2.2输入输出函数64.2.3多项式的相加减6第五章．详细分析65.1思路分析65.2具体分析75.2.1主函数7根据流程图可写出主函数的主要语句75.2.2输入输出函数85.2.3 多项式相加95.2.4 多项式相减12第六章运行结果分析156.1 输入输出分析156.2 运行结果分析16第七章结束语167.1心得体会与总结16第八章源代码17参考文献：22第一章．课程设计的目的与意义1.1课题设计的目的（1）.熟练掌握线性表链式存储基本的存储形式：单链表，循环链表以及双链。

(2).熟练运用线性表链式存储的基本运算。

(3).能应用循环链表实现一元多项式的相加减。

（4）.将一元多项式相加减的思想利用C语言编写程序在计算机上实现1.2课题设计的意义（1）.进一步了解循环链表的特点：无须增加存储量，仅对表的连接方式稍作改变，即可使得表处理更加方面灵活（2）.学会将数学语言转化为计算机语言（3）.懂得课程设计的格式及要求，有利于以后写毕业论文（4）.耐心，细心以及广泛的材料收集的成功的前提第二章．课题设计的内容和要求2.1 课题设计的内容利用计算机语言实现一元n次多项式的输入输出及其多项式的相加减并正确输出，并且让别人看得一目了然（即编辑程序界面友好化）。