3 算法描述
注:这里建立的链表中的头结点是不保存数据的
(1) 一元多项式的存储
采用链表结构存储,设置两个数据项:指数和系数,还有一个指针型,
用于链接的变量
(2) 一元多项式的建立
先输入好应该输入的项数 n,然后开始建立链表,具体操作为:分配
三个指针变量 p1,p2,p3 先指向新建立的头结点,然后 p1 指向新建
立的结点,填完数据后,让 p2 指向的结点的后继指向 p1,p2 指向
与 p1 相同的结点,然后计数器+1,重复上述步骤,直到计数器的
值与 n 相同,最后让 p2 的后继指空
(3) 一元多项式的规范
考虑到用户输入时可能会输入相同指数的不同项,所以设计了一个让
多项式中相同指数合并的算法。具体思路如下:
1) 使 p1,p3 三个指针变量指向头结点的下一个结点,p2 指向 p3
的下一个结点
2) 当 p1 的后继不为空时,使 p2 开始遍历链表当 p2 所指的结点
的指数与 p3 所指的指数相同时,系数相加,删除 p2 所指的结点,
否则执行 4)
3) 使 p3 指向下一个结点,p1 指向 p3 所指结点,p2 指向 p3 的
下一个结点