北邮数据结构实验报告 图

同类项才能实现，所以在运算时

要注意判断指数出现的各种不同的情况，分别写出计算方法。将每项运算得到

的结果都插入到新的链表中，形成结果多项式。 3. 多项式的求导运算：多项式的求导根据数学知识，就是将每项的系数乘以指数，将

指数减1即可，将每项得到的结果插入到结果多项式的链表中。

4. 多项式在某点的值：由用户输入x的值，然后求出每项的值相加即可。 存储结构

单链表: 其定义的结点包括三部分：系数、指数以及下一个结点的地址 关键算法分析

关键算法：

1.一元多项式求和算法:

初始化工作指针p和q,以及p节点前驱节点指针p_prior

若p和q都不为空,则循环以下操作: 若p->,则p_prior=p;p=p->nenx; 否则,若p->>q->,则:

将q结点加入到A链表p结点之前 q指向B链表的下一个结点 否则:p->=p->+q->; 若p->为0,则删除结点p p指向下一个结点 删除q结点 q指向下一个结点

若p为空并且q不为空,则将q结点及其后所有结点追加到A链表的最后端 将B链表 制成空链表 2.一元多项式求导

初始化工作指针p及p_prior 若p不为空,循环以操作

若p->=0;p_prior->next=p->next; p; p=p_prior; 否则 p->*=p->; p->; 3.一元多项式求在X处的值 初始化工作指针p,定义会参数a 若p不为空,循环以下操作 a+=p->*pow(x,p->); p=p->next; 4.输出多项式 获取头结点;

循环n-1次(n为多项式的项数) 将指针的指向后移;

依照多项式的各种情况，设置输出方式 系数为1且指数不为1和0，输出x^expn+; 系数不为0且指数为0，输出(coef)+; 系数不为0且指数为1，输出(coef)x+; 代码详细分析： 求和算法详细分析: 1.若p-> (1)q结点不变 (2)p结点向下移 (1)p_prior=p; (2)p=p->next;

2.若p->>q->执行一下主要操作步骤 (1) p_prior->next=q; (2)p_prior=q; (3)q=q->next; (4)p_prior->next=p; 示意图 :

3.若p->==q->执行以下操作步骤:

(a)若合并系数为零,则删除p结点,主要步骤:

(1)p_prior->next=p->next; (2) p;

(3)p=p_prior->next; (4)Node*temp=q; (5)q=q->next; (6) temp; 示意图 :

(b)合并系数不为零,将其从新赋予p结点,主要步骤: (1)p_prior=p; (2)p=p_prior->next; (3)Node*temp=q; (4)q=q->next; (5) temp; 示意图:

5. 若p为空且q不为空的情况 p_prior->next=q; 示意图:

3、计算关键算法的时间,空间复杂度

时间复杂度(1)一元多项式的构建(2)求和(3)减法(4)求导 时间复杂度都为O(n) 空间复杂度为:S(1)