实验报告
CreateLinklist(): 从键盘输入数据，创建单链表
ContLinklist()：将前面建立的两个单链表首尾相连
OutputLinklist()：输出显示单链表
3）分析算法时间复杂度
三、实验过程与实验结果
1．一元稀疏多项式简单的计算器
➢数据结构定义
typedef struct PolyNode
{
float coef;
int exp;
struct PolyNode *next;
}PolyNode;
typedef PolyNode *Polynomial;
➢算法设计思路简介
用带头节点的单链表分别表示两个多项式L和p，同时新建一个链表N把两个多项式相加后的结果存放在N表中。所有链表均按指数从小到大顺序排列。链表N中的节点N1另外生成，把运算后的结果赋给N1，用尾部插入法将N1插入到链表N中，每次要将新节点N1插入到链表N尾部，因此给链表N声明一个尾指针N0始终指向链表N的尾节点。操作完成，按要求输出。
➢算法描述：
初始时，指针L1指向L链表的头节点，P1指向p链表的头结点，从头开始扫描两个相加多项式链表的表头节点，循环操作，直到其中一个单链表中的节点全部搜索结束为止。
比较指针L1和P1指向的指数，共有三种情况：
（1）L1->exp==P1->exp；则两个多项式的系数相加减，得到的新和多项式节点插入到链表N中。L1、P1指针后移；
（2）L1->expexp；则将该L1所指节点赋给N1插入到链表N中。L1、P1指针后移；
（3）L1->exp>P1->exp；则将该P1所指节点赋给N1插入到链表N中。L1、P1指针后移。
➢算法的实现和测试结果：
输入:
L1: 5 3 6 5 6 7 0 0; L2: 2 3 3 5 4 7 0 0;
输出：
L1: 5x^3+6x^5+6x^7；L2: 2x^3+3x^5+4x^7；L1+L2: 7x^3+9x^5+10x^7；L1-L2: 3x^3+3x^5+2x^7
➢算法时间复杂度分析
该程序中建立单链表过程采用了单链表的后插入操作，其时间复杂度T(n)=O(1)；当两个多项式相加减的时候，设L, p多项式分别有m、n项，其算法时间复杂度T(n)=O(m+n)。
3．单链表基本操作练习
➢数据结构定义
typedef int ElemType;
struct LNode
{
ElemType data;
struct LNode *next;
};
typedef LNode *LinkList;
➢算法设计思路简介
首先初始化两个带头结点的单链表L1,L2，要想实现两个链表的合并，可以将L2看成一个节点，将它插入到L1上即可。第一步遍历L1链表到最后一个，然后把第二个链表的地址赋值给它的next，即可实现。
➢算法描述：
初始时，指针L1指向L1链表的头节点，令L1=L1->next，L2=L2->next，然后从头开始扫描直到L1单链表中为空，此时令L1->next=L2，即把L2链表的地址赋给了L1的next，实现合并操作。最后通过Output 函数将合并后的链表输出，依次将链表中的data域输出即可。
➢算法的实现和测试结果：
输入:
L1: 9 6 2 4 8 2 3 6 0;
L2: 5 4 3 1 5 9 8 0;
输出：9 6 2 4 8 2 3 6 5 4 3 1 5 9 8；
➢算法时间复杂度分析
设L1链表共有n项，其循环操作就是遍历L1整个表，所以该算法时间复杂度T(n)=O(n)。
四、收获与体会
通过这次线性表的应用实验，我对于单链表的结构有了更深层次的理解，真正动手体会到怎样将查找、插入和删除这些基本操作应用在线性表中从而解决相关问题。同时我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。
五、源代码清单
1．一元稀疏多项式简单的计算器
#include
using namespace std;
