链表多项式大整数-BigInt

非负大整数类 - BigInt大整数ADT - 链表实现为了进行大整数乘法时好进位我们把幂次低的项靠近链表头部即反着存放将大整数封装为一个BigInt类(singly-linked-list)BigInt类内部有一个节点类Node一个节点代表一项BigInt类可以看做是一个节点按幂次从小到大排列的有序链表classBigInt{private:structNode;typdef Node*PtrToNode;PtrToNode bigint;PtrToNodeclone()const;//返回自身的深拷贝voidswap(BigIntother);//交换两个对象的指针(copy-and-swap)voidCarry();//对链表进行统一进位public://///* 三/五法则 */////BigInt();//无参构造~BigInt();//析构函数BigInt(intnum);//将一个整型变量转换为大整数BigInt(constBigIntother);//深拷贝构造BigIntoperator(BigInt other);//赋值重载copy-and-swapBigInt(BigIntother)noexcept;//移动构造BigIntoperator(BigIntother)noexcept;//移动赋值/////* 大整数的输入输出 */////friendstd::istreamoperator(std::istreamis,BigIntB);friendstd::ostreamoperator(std::ostreamos,constBigIntB);/////* 大整数的加法 */////BigIntoperator(constBigIntB)const;/////* 大整数的乘法 */////BigIntoperator*(constBigIntB)const;在做运算(加减)或输入输出时一定要注意抵消(val 0)的情况大整数的加法函数声明BigIntoperator(constBigIntB)const;因为加法会产生临时对象所以返回值只能是BigInt对象 不能加引用避免悬空引用注意一定要声明为const, 因为const对象和临时对象只能调用const成员函数要实现 BigInt BigInt BigInt ········BigInt 必须加constBigInt A,B,C;//std::cout A B C;std::cout(A.operator(B)).operator(C);//(A.operator(B))为临时对象C默认临时对象只能调用const成员函数//如果operator不声明为const,那么临时对象(A.operator(B))无法调用operator//无法实现连加的操作维护一个变量carry代表进位维护两个指针ptr1、ptr2分别指向this-bigint、B.bigint如果两个指针都不为空一定要保持同时前进(保证位次相同)如果一个指针为空将其值定义为0继续后移另一个指针直到carry 0 ptr1 nullptr ptr2 nullptr//// 大整数的加法//BigIntoperator(constBigIntB)const{BigInt newBigInt;intcarry0,curSum0;PtrToNode ptr1bigint;PtrToNode ptr2B.bigint;PtrToNode curnewBigInt.bigint;//用于延长链表while(ptr1||ptr2||carry){intval1ptr1?ptr1-val:0;intval2ptr2?ptr2-val:0;curSumcarryval1val2;carrycurSum/10;cur-valcurSum%10;if(ptr1)ptr1ptr1-Next;if(ptr2)ptr2ptr2-Next;if(ptr1||ptr2||carry)//判断要不要延长链表{cur-NextnewNode();curcur-Next;}}returnnewBigInt;//返回临时对象}大整数的乘法模拟竖式乘法最后再统一进位第i位与第j位相乘的结果直接放到第ij位上(i,j 从0开始算)不用先考虑进位后面再统一进位//统一向后进位voidCarry()//调用: A.Carry();{PtrToNode ptrbigint;for(;;){if(ptr){intcarryptr-val/10;ptr-val%10;if(carry0!ptr-Next)ptr-NextnewNode();elseif(!carry!ptr-Next)return;ptrptr-Next;ptr-valcarry;}}}函数声明BigIntoperator*(constBigIntB)const;定义变量inti,j,newSize;//第i位与第j位相乘intsize10,size20,preIdx0;BigInt newBigInt;//相乘的结果PtrToNode curnullptr;//用于遍历链表PtrToNode ptr1bigint;PtrToNode ptr2B.bigint;提前计算两个相乘链表的长度方便新开一个链表存放相乘的结果//计算两个相乘链表的长度for(curptr1;cur;curcur-Next)size1;for(curptr2;cur;curcur-Next)size2;//将结果链表的长度加长每个节点的值初始化为0newSizesize1size2-2;curnewBigInt.bigint;for(i0;inewSize;i){cur-NextnewNode();curcur-Next;}模拟运算两重循环用指针ptr1、ptr2遍历链表用变量i, j记录链表的位次每一次用cur指针找第i j个节点将ptr1-val * ptr2-val加到该节点小优化不用每次都让cur从头开始遍历链表我们可以用一个preIdx记录上一次cur停在第几个节点了如果这一次的i j在preIdx的后面或相等那就直接往后就行了如果cur在后面了在从头遍历//// 大整数的乘法//BigIntoperator*(constBigIntB)const{inti,j,newSize;//第i位与第j位相乘intsize10,size20,preIdx0;BigInt newBigInt;//相乘的结果PtrToNode curnullptr;//用于遍历链表PtrToNode ptr1bigint;PtrToNode ptr2B.bigint;for(curptr1;cur;curcur-Next)size1;for(curptr2;cur;curcur-Next)size2;newSizesize1size2-2;curnewBigInt.bigint;for(i0;inewSize;i){cur-NextnewNode();curcur-Next;}curnewBigInt.bigint;for(i0,ptr1bigint;ptr1;ptr1ptr1-Next,i){for(j0,ptr2B.bigint;ptr2;ptr2ptr2-Next,j){intcurSumptr1-val*ptr2-val;intidxij;intk0;//cur需要后移的步数if(idxpreIdx)for(;kidx-preIdx;k)curcur-Next;elsefor(curnewBigInt.bigint;kidx;k)curcur-Next;cur-valcurSum;preIdxij;}}newBigInt.Carry();//统一进位returnnewBigInt;}完整代码#includeiostream#includestring#includestackclassBigInt{private:structNode;typedefNode*PtrToNode;structNode{intval;PtrToNode Next;Node():val(0),Next(nullptr){}Node(intv,PtrToNode pnullptr):val(v),Next(p){}~Node(){deleteNext;}Node(constNodenode)delete;Nodeoperator(constNodenode)delete;};PtrToNode bigint;//// 工具函数//PtrToNodeclone()const{if(!bigint)returnnullptr;PtrToNode newHeadnewNode(bigint-val);PtrToNode curnewHead;for(PtrToNode ptrbigint-Next;ptr;ptrptr-Next){cur-NextnewNode(ptr-val);curcur-Next;}returnnewHead;}voidswap(BigIntother)noexcept{PtrToNode ptrbigint;bigintother.bigint;other.bigintptr;}voidCarry(){PtrToNode ptrbigint;for(;;){if(ptr){intcarryptr-val/10;ptr-val%10;if(carry0!ptr-Next)ptr-NextnewNode();elseif(!carry!ptr-Next)return;ptrptr-Next;ptr-valcarry;}}}public://// 三/五法则//BigInt():bigint(newNode(0)){}BigInt(intnum):bigint(newNode(num%10)){PtrToNode curbigint;while(num/10){cur-NextnewNode(num%10);curcur-Next;}}~BigInt(){deletebigint;}//封闭类的析构BigInt(constBigIntother):bigint(other.clone()){}BigIntoperator(BigInt other){swap(other);return*this;}BigInt(BigIntother)noexcept:bigint(other.bigint){other.bigintnullptr;}BigIntoperator(BigIntother)noexcept{deletebigint;bigintother.bigint;other.bigintnullptr;return*this;}//// 大整数的输入输出//friendstd::istreamoperator(std::istreamis,BigIntB){std::string num;isnum;intlennum.size();deleteB.bigint;B.bigintnewNode(num[len-1]-0);PtrToNode curB.bigint;for(intilen-2;i0;--i){intcurValnum[i]-0;cur-NextnewNode(curVal);curcur-Next;}returnis;}friendstd::ostreamoperator(std::ostreamos,constBigIntB){std::stackintst;PtrToNode ptrB.bigint;while(ptr){st.push(ptr-val);ptrptr-Next;}while(!st.empty()){osst.top();st.pop();}returnos;}//// 大整数的加法//BigIntoperator(constBigIntB)const{BigInt newBigInt;intcarry0,curSum0;PtrToNode ptr1bigint;PtrToNode ptr2B.bigint;PtrToNode curnewBigInt.bigint;while(ptr1||ptr2||carry){intval1ptr1?ptr1-val:0;intval2ptr2?ptr2-val:0;curSumcarryval1val2;carrycurSum/10;cur-valcurSum%10;if(ptr1)ptr1ptr1-Next;if(ptr2)ptr2ptr2-Next;if(ptr1||ptr2||carry){cur-NextnewNode();curcur-Next;}}returnnewBigInt;}//// 大整数的乘法//BigIntoperator*(constBigIntB)const{inti,j,newSize;//第i位与第j位相乘intsize10,size20,preIdx0;BigInt newBigInt;//相乘的结果PtrToNode curnullptr;//用于遍历链表PtrToNode ptr1bigint;PtrToNode ptr2B.bigint;for(curptr1;cur;curcur-Next)size1;for(curptr2;cur;curcur-Next)size2;newSizesize1size2-2;curnewBigInt.bigint;for(i0;inewSize;i){cur-NextnewNode();curcur-Next;}curnewBigInt.bigint;for(i0,ptr1bigint;ptr1;ptr1ptr1-Next,i){for(j0,ptr2B.bigint;ptr2;ptr2ptr2-Next,j){intcurSumptr1-val*ptr2-val;intidxij;intk0;if(idxpreIdx)for(;kidx-preIdx;k)curcur-Next;elsefor(curnewBigInt.bigint;kidx;k)curcur-Next;cur-valcurSum;preIdxij;}}newBigInt.Carry();returnnewBigInt;}};