实现两个多项式进行相加 不开辟空间 ( 这要求实现进行相加,代价为两个原链表将被修改)
分析:
this>other 就把other当前结点放置在this之前
this<other 就this当前结点前移一位,并且后继也前移一位
this==other 求和为0就删除,并全部前移一位,不等就删除other中的当前结点并前移
注意:
必须注意 n 作为始终指向 mHead, n->next 始终指向other链表的下一个结点,所以修改了other链表时候必须注意 n->next的指向
有些书上 C语言实现的多项式之和,如果 修改对应的代码植入于C++中,能够得到正确结果,但是 C++ 的析构函数将会出错,故此要将 other 表中的指针 n 指向明确
1 void Link::Add( Node * mHead) {
2 Node * ph = Head->Next;
3 Node * pm = mHead->Next;
4 Node * m = Head; //作为一个标记,标记this上一次访问的结点
5 Node * n = mHead; // n 始终指向头结点,并且 n->next指向 pm 的下一个结点元素
6
7 while( ph!=NULL && pm!=NULL) { // 判断当 A 或 B 两个链表不为空时
8 if( ph->Index>pm->Index) { //this>other ,将other的第一个结点插入到 this当前结点之前
9 n->Next = pm->Next; // 让 n 的 next指针指向 pm的下一个结点,
10 m->Next = pm;
11 m = pm;
12 m->Next = ph;
13 pm = n->Next; // 上述将 pm 插入时,将 pm 指向下一个结点,即 n->enxt
14 }
15 else if( ph->Index<pm->Index) { //this<other 只需要将this的结点后移一位,注意 m 始终未 this的上一个结点
16 m = ph;
17 ph = ph->Next;
18 }
19 else { //this==other
20 Node * tem;
21 if( ph->Ratio+pm->Ratio==0) { // 求和为0 将this的当前结点删除,并且后移一位
22 tem = ph;
23 ph = ph->Next;
24 Delete(tem);
25 }
26 else { //求和不为0, 将系数相加
27 ph->Ratio = ph->Ratio+pm->Ratio;
28 } // 当相等时,都要删除掉other的当前结点,并后移一位
29 tem = pm;
30 pm = pm->Next;
31 n->Next = pm; //
32 Delete(tem);
33 }
34 }
35 if( ph==NULL) { // 由于当other > this时,只将this后移,所以 pm 为空表示都插入进去,不为空时,
36 m->Next = pm; // 表示this的链表为空了,所以将other剩下的链表插入 this 的表尾,即 n 指向最后一个结点 n->next正好是表尾指针
37 n->Next = NULL; // 设置表尾为空
38 }
39 }
40 void Link::Delete(Node * tem) { // 删除结点 tem
41 delete tem;
42 }
原文链接: https://www.cnblogs.com/log-xian/p/6032114.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/243340
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!