第1关：基于链表的两个一元多项式的基本运算
在计算机科学中，一元多项式是常见的代数表达式形式，通常用来表示多项式函数。虽然一元多项式的计算看似简单，但如果使用数据结构来实现，将会大大提高计算效率。这篇文档将详细介绍基于链表的两个一元多项式的基本运算。
一元多项式的定义：
在代数学中，一元多项式是一种含有一个未知数的代数多项式。它是指一个代数式，它是由保持仅仅又有限个多项式的乘积。此外，一元多项式在基本运算方面具有封闭性，这也是为什么它被广泛应用的原因之一。在这里，我们将讨论在计算机科学中对一元多项式的实现。
链表的定义：
链表是一种线性数据结构，其中数据元素不是常规的数组索引组织，而是通过信息存储元素之间的链来相互连接。每个元素被称为节点，并且每个节点包含一个下一个节点的指针。
基于链表的一元多项式的实现：
基于链表的一元多项式的实现涉及到将每个多项式的系数和指数存储为链表中的节点。这种实现的主要优点是，它可以轻松地进行添加和删除操作，可以有效地分配内存，而不会浪费存储空间。
考虑到一元多项式的基本运算包括加法，减法和乘法，我们将详细介绍每种操作的实现。
一、基于链表的两个一元多项式的加法操作
在实现一元多项式加法时，我们需要创建两个链表来存储两个多项式。链表节点应该包含两个属性：系数和指数。然后我们可以使用以下方法将两个多项式相加。
1. 定义两个指针p1和p2分别指向多项式链表的头部。
2. 定义一个新链表，用于存储相加的项。
3. 当p1和p2都不为空时循环进行以下操作：
a. 如果p1当前节点的指数小于p2当前节点的指数，则将p1的节点添加到新链表中并将p1指针向下移动一个节点。
b. 如果p1当前节点的指数大于p2当前节点的指数，则将p2的节点添加到新链表中并将p2指针向下移动一个节点。
c. 如果p1和p2当前节点的指数相等，则将两个节点的系数相加，并将结果添加到新链表中，并将p1和p2指针都向下移动一个节点。 4. 如果p1和p2有任何一个为空，则将另一个多项式的所有剩余项添加到新链表中。
XX学 院
课程设计说明书
题目 一元多项式计算问题
系(部) 计算机科学与技术系
专业(班级) 计算机科学与技术专业
姓名
学号
指导教师
起止日期
I 课程设计任务书
课程名称：数据结构与算法
设计题目：一元多项式计算问题
已知技术参数和设计要求：
问题描述：
设计一个稀疏多项式简单计算器
基本要求：
(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课时
工作计划：
班级：计科3班 指导教师：刘钢钦
周次 星期 地点 设计方式
13 星期一1-2节 A多1 讲授内容
星期二3-4节 科1608 答疑
星期二5-8节 1403 上机调试
星期三1-4节 科1608 答疑
星期四1-4节 1404 上机调试
星期四5-8节 科1608 答疑
14
星期二3-4节 科1608 答疑
星期二5-8节 1403 上机调试
星期三1-4节 科1608 答疑
文档可能无法思考全面，请浏览后下载!
0 / 14
院 系： 计算机科学学院
专 业： 软件工程
年 级： 2013级
课程名称： 数据结构
姓 名： 韦宜（201321092034）
指导教师： 宋中山
2015年 12 月 15日文档可能无法思考全面，请浏览后下载!
1 / 14 题目：设计一个一元稀疏多项式简单计算器
班级：软件工程1301 姓名：韦宜 学号：201321092034 完成日期：12月15日
一、需求分析
问题描述：设计一个一元多项式加法器
基本要求：
输入并建立多项式；
(2)两个多项式相加；
(3)输出多项式：n, c1, e1, c2, e2, …cn , en, 其中，n是多项式项数，ci和ei分别是第 i 项的系数和指数，序列按指数降序排列。
(4)计算多项式在x处的值；
(5)求多项式的导函数。
软件环境：Windows，UNIX，Linux等不同平台下的Visual C++ 6.0
硬件环境: 512MB内存,80Gb硬盘,Pentium4 CPU,CRT显示器。文档可能无法思考全面，请浏览后下载!
2 / 14 概要分析
本程序有五个函数：
PolyNode *Input()(输入函数)；
PolyNode *Deri(PolyNode *head)（求导函数）；
PolyNode * Plus(PolyNode *A,PolyNode *B)（求和函数）；
void Output(PolyNode*head)（输出函数）；
int main()（主函数）
本程序可使用带有附加头结点的单链表来实现多项式的链表表示，每个链表结点表示多项式的一项，命名为node，它包括两个数据成员：系数coef和指数exp，他们都是公共数据成员，*next为指针域，用链表来表示多项式。适用于不定的多项式，特别是对于项数再运算过程中动态增长的多项式，不存在存储溢出的问题。其次，对于某些零系数项，在执行加法运算后不再是零系数项，这就需要在结果多项式中增添新的项；对于某些非零系数项，在执行加法运算后可能是零系数项，这就需要在结果多项式中删去这些项，利用链表操作，可以简单的修改结点的指针以完成这种插入和删除运算（不像在顺序方式中那样，可能移动大量数据项）运行效率高。文档可能无法思考全面，请浏览后下载!
数据结构教案(总32页)
-CAL-FENGHAI.-(YICAI)-Company One1
-CAL-本页仅作为文档封面，使用请直接删除
2015 至2016 学年第二学期
数 据 结 构 课程
教
案
课程编码： 1261D03
总学时／周学时： 80 / 5
开课时间： 2016年2 月 24日第 1 周至第 16
周
授课年级、专业、班级： 15级网工程2班
使用教材 严蔚敏. 数据结构（C语言版）[M] 北京：清华大学出版社，2011.
系别/教研室： 信息工程学院 / 物联网工程
授课教师： 刘波 教学目标：
《数据结构》是物联网工程专业的一门专业必修课。用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。
通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。
教学要求:
本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。
学生通过学习该课程后主要应掌握以下内容：
1．了解数据结构及有关的基本概念；
