实验报告
线性表的应用：稀疏一元多项式运算器
1.问题的描述
一元多项式在存储与运行的时候，一种常见的存储方法是根据最高项的幂次，按顺序生成数组。然而，当多项式比较稀疏的时候，大多数的存储空间被浪费在存储0系数的项中。因此，本实验采用链表的形式对多项式进行存储和运算，在节省空间的同时提高运算效率。
2.算法的描述
(1)数据结构的描述
本实验主要使用到了poly结构体，其定义如下：
struct poly
{
float coef;
int expn;
struct poly *next;
};
其中，coef是每个项的系数，expn是幂次，next为指向下一个poly的指针。
另外，在主函数中，本文主要使用到了结构体数组polyns，其定义如下：
struct poly polyns[5];本文的思想是，生成结构体数组，里面分别储存
- 主多项式
- 次多项式
- 求和结果
- 微分结果
- 不定积分结果
在使用的时候，主要使用该数组的指针，传入给对应的函数进行操作。
(2)程序结构的描述
函数原型、功能和接口的描述。
本实验主要定义如下函数，其原型为：
void intro();
status create(poly);
void show(struct poly);
int menu();
status add(poly, poly, poly);
status diff(poly, poly);
status integral(poly, poly);
status hasExpn(struct poly, int);
status insert(poly, poly);下面将分别介绍各个函数的功能和接口
- void intro();
该函数用于展示程序一开始的页面，以及使用说明，保证程序对使用人友好
- status create(struct poly *polyn);
该函数用于创建多项式，传入参数的为头节点指针，返回的参数为创建的status，如果创建成功则返回OK；
在本函数中，将接受用户的输入，分配空间并展示创建结果。
- status hasExpn(struct poly polyn, int expn)
本函数用于遍历一个链表，查看该链表中是否已经存在幂次为expn的项，如果有则返回TRUE，没有则返回FALSE。
- status insert(struct poly *polyn, struct poly *new_poly)
本函数用于将一个新的项插入已有的多项式链表，根据题目要求，采用递减顺序插入。
- void show(struct poly polyn)
本函数用于展示多项式，传入参数为一个多项式链表的头节点指针。
本函数针对微分可能出现的一些问题进行了深度优化，从而保证每种情况下都可以得到准确的结果。
- int menu()
本函数用于展示菜单，方便用户进行选择
- status add(struct poly *add1, struct poly *add2, struct poly *sum)
本函数用于实现多项式的相加。在使用本功能时，需要先创建一个新的多项式，求和的结果的头节点储存在结构体指针sum中。
- status diff(struct poly *raw, struct poly *diff_res)
本函数用于实现微分，通过用户输入次数来确定微分的次数，支持0次项消除
- status integral(struct poly *raw, struct poly *int_res)
本函数用于实现不定积分，结果的头节点储存在结构体指针int_res中。
3.调试分析
测试数据的选择，程序调试中遇到的问题及解决方法。
本实验采用题中给定的例子数据进行测试，在测试过程中遇到了各种各样的问题，问题描述与解决办法如下：
- Q:在做加法的时候，是否采用课上学的就地归并法
- A:由于接下来还要实现微分和积分，需要保持主多项式不变，所以每次都会生成新的空间进行存储，而不是改变原有的链接。
- Q:在做微分的时候，如何实现高阶微分
- A:采用循环方法，每次做完之后，把微分的结果作为下一次微分的初始值，进行下一次微分
- Q:在进行微分结果的输出时，如何消除0项
- A:由于低次函数在微分几次之后就会变成0，所以在show()函数中何时输出+号，输出在数字前方还是后方就很麻烦。本实验采用多个判断语句，考虑了是否全部系数都为0、系数是否为0；是否为倒数第一项、是否为倒数第二项、指数是否为0等多种特殊情况，最终使得结果变得合理且符合常识。
4.算法的时空分析
- 时间复杂度
- 创建：本实验在创建的时候就是按照非递减顺序排列，因此存在一个一边比较一边插入的情况，因此复杂度为O(Length)，其中Length为链表长度、
- 相加：在这里主要是遍历两个链表产生的时间复杂度，复杂度为O(Length 1+ Length 2)。
- 微分：在这里主要是遍历一个链表产生的时间复杂度+高阶微分产生的循环复杂度，复杂度为O(N*Length)，N为微分次数
- 不定积分：在这里主要是遍历一个链表产生的时间复杂度，复杂度为O(Length)。
- 空间复杂度
- 创建：生成一个链表，每个链表的长度为Length，所占空间为Length * (sizeof(float) + sizeof(int) + sizeof(poly))
- 相加：生成一个新的链表，长度为Length 1+ Length 2，所占空间为：(Length 1+ Length 2)* (sizeof(float) + sizeof(int) + sizeof(poly))
- 微分、不定积分：都是生成一个跟原始链表长度一样的新链表，所占空间为：Length * (sizeof(float) + sizeof(int) + sizeof(poly))
5.测试结果及分析
列出测试数据和测试结果，给出分析和说明。
(1)创建
这里使用题目中给出的例子进行创建：
X3+3X2+2X+6 X3-X2+2X-2
健壮性：
可以看出，产生的结果与输入顺序无关
(2)求和
采用题中所给的例子，求X3+3X2+2X+6与X3-X2+2X-2的和
可以看出，其和为2X3+2X2+4X+4，正确
健壮性：
可以看出，本代码可以把系数为0项消除，即实现：（X3+3X2+2X+6） + （X3-3X2+2X+6）=2X3+4X+12
(3)微分
采用题中例子，求X3+3X2+2X+6的1阶和2阶微分
可以看出，微分结果正确
健壮性：
可以看出，高阶微分完之后输出为0，与题目相符
(4)不定积分
采用题中例子，求X3+3X2+2X+6的不定积分
可以看出，不定积分计算正确。有几个系数看起来比较奇怪，是为了美观，对系数进行了保留一位小数的处理。
6.实验体会和收获
经过本次实验，我提高了对结构体指针的认识，在实践中实现了链表的各种运算，了解了类C语言和C语言的一些差别。