北邮22信通：（8）实验1 题目五：大整数加减法（搬运官方代码）

北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

上一篇文章：

北邮22信通：（7）实验1 题目四：一元多项式（节省内存版）_青山如墨雨如画的博客-CSDN博客

下一篇文章：

*****声明*****

本代码由官方提供，不是作者的算法。

本代码仅供研究学习使用，请不要用于其他用途。

有问题的友友也可以在评论区留言，我们可以一起讨论。

本代码在DEVC++中可以运行。

*****声明完毕*****

1.实验要求：

利用链表实现大整数加减法操作；32位极其直接操作的数据最大为32bit，若超过32bit，则需要单独设计算法。在这里，可以用链表的每个节点存储大整数的每一位的十进制数字，则可以进行大整数的算术运算，该实验仅实现加减法操作。

要求：

随机产生2个1~50位的字符串，并存储到新的链表中；

打印运算结果。

考虑链表结构的设计，是否有更节省空间的数据结构。

2.代码部分：

#include <iosfwd>
#include <iostream>
#include <stack>
#include "time.h"
using namespace std;struct Node
{int data;Node  *next;
};
class BigInteger
{
public:BigInteger();BigInteger(int a[], int n, bool pos);friend BigInteger add(BigInteger &int1, BigInteger &int2);  //int1 + int2friend BigInteger sub(BigInteger &int1, BigInteger &int2);  //int1 - int2int getLength();                   //获取链表长度void print();~BigInteger();
private:Node *first;int length;bool positive = true;   //记录整数的正负
};BigInteger::BigInteger()
{first = new Node;first->data = 0;first->next = NULL;length = 1;
}BigInteger::BigInteger(int a[], int n, bool pos = true)	//引用和声明只能有一个默认参数定义
{if (n < 1){throw "integer length should be at least 1";}//尾插法 不带头结点的链表first = new  Node;Node *r = first;  //指向最后一个结点for (int i = 0; i<n - 1; i++){r->data = a[i];Node *s = new Node; //（1）生成新结点s->next = NULL;r->next = s;  //(2) 链接在尾结点后面r = s; //(3) 尾指针后移}r->data = a[n-1];r->next = NULL;length = n;positive = pos;
}
BigInteger::~BigInteger() {}BigInteger sub(BigInteger &int1, BigInteger &int2) {      //都可以转换成正数的加减法BigInteger newint = BigInteger();newint.length = 0;              //友元能直接访问私有变量if ((!int1.positive)&&(!int2.positive)){    //-int1-（-int2） = -int1 + int2int2.positive = true;newint = add(int1,int2);int2.positive = false;return newint;}else if (!int1.positive){int1.positive = true;newint = add(int1,int2);newint.positive = false;int1.positive = false;return newint;}else if (!int2.positive){int2.positive = true;newint = add(int1,int2);int2.positive = false;return newint;}// 这里开始的处理，int1和int2应都为正整数Node *cursor = new Node;    //游标用来创建新的链表Node *tobedelete = cursor;      //临时的头结点cursor->next = newint.first;    Node *int1_first = int1.first;     //遍历int1Node *int2_first = int2.first;     //遍历int2stack<Node*> substk;  //定义一个栈用来处理高位的连续0  如77772-77771 = 1 ，需要把前面的0都删除int flag = 0;   //记录减法的借位//首先遍历到 min(int1.length, int2.length)位，之后至少有一个指针为NULLfor (int i = 0; i < int1.length && i < int2.length; i++){int tmp = int1_first->data - int2_first->data - flag;if (tmp < 0){tmp += 10;if (tmp == 0){substk.push(cursor);    //1000 - 99 = 901}else{while (!substk.empty())      //有出现不为0的位，就把栈清空substk.pop();}flag = 1;}else if ((tmp == 0)&&(cursor->next!=newint.first)){  //个位为0不入栈，入栈的是0前面的结点substk.push(cursor);flag = 0;}else{while (!substk.empty())substk.pop();flag = 0;}cursor->next->data = tmp;       //在结果链表中插入新节点cursor->next->next = new Node;cursor = cursor->next;cursor->next->next = NULL;int1_first = int1_first->next;int2_first = int2_first->next;newint.length++;}//减完位数相同的部分，讨论接下来的情况if ((int1_first == NULL) && (int2_first == NULL)){if (!flag == 0)        //最高位有借位说明结果是负的，在后面计算补码newint.positive = false;}else if(int1_first == NULL){// int2位数多，结果一定是负数newint.positive = false;while (int2_first != NULL){int tmp = 0 - int2_first->data - flag;if (tmp < 0){tmp += 10;if (tmp == 0){substk.push(cursor);}else{while (!substk.empty())substk.pop();}flag = 1;}else if (tmp == 0){substk.push(cursor);flag = 0;}else{while (!substk.empty())substk.pop();flag = 0;}cursor->next->data = tmp;cursor->next->next = new Node;cursor = cursor->next;cursor->next->next = NULL;newint.length++;int2_first = int2_first->next;}}else{while (int1_first != NULL){// int1位数高，结果必为正int tmp = int1_first->data - flag;if (tmp < 0){tmp += 10;if (tmp == 0){substk.push(cursor);}else{while (!substk.empty())substk.pop();}flag = 1;}else if (tmp == 0){substk.push(cursor);flag = 0;}else{while (!substk.empty())substk.pop();flag = 0;}cursor->next->data = tmp;cursor->next->next = new Node;cursor = cursor->next;cursor->next->next =NULL;newint.length++;int1_first = int1_first->next;}}//删除初始化的临时节点delete tobedelete;//删除末尾的临时节点tobedelete = cursor->next;cursor->next = NULL;delete tobedelete;//删除最后的连续0节点while (!substk.empty()){cursor = substk.top();if (cursor->next == newint.first)  //个位不能被删除（删除的也不是个位，tobedelete已经被释放了）break;substk.pop();tobedelete = cursor->next;cursor->next = NULL;newint.length--;delete tobedelete;}if (!newint.positive){//得到的newint为负数，需要补码操作，如9-16 -> 93,100-93 = 7int a[int2.length+1];for (int i = 0; i < int2.length;i++)a[i] = 0;a[int2.length] = 1;newint.positive = true;BigInteger complement = BigInteger(a,newint.length + 1);tobedelete = newint.first;newint = sub(complement,newint);    //newint的地址换了，构造了一个新对象newint.positive = false;while (tobedelete != NULL){Node *tobed = tobedelete;tobedelete = tobedelete->next;delete tobed;}}return newint;
}BigInteger add(BigInteger &int1, BigInteger &int2) {BigInteger newint = BigInteger();  //定义新的大整数作为返回值newint.length = 0;if ((!int1.positive)&&(!int2.positive))newint.positive = false;else if(!int1.positive){int1.positive = true;newint = sub(int2,int1);int1.positive = false;return newint;}else if(!int2.positive){int2.positive = true;newint = sub(int1,int2);int2.positive = false;return newint;}// 这里开始的处理，int1和int2应都为正整数Node *cursor = new Node;    //创建一个游标指针用于构建newintNode *tobedelete = cursor;  //记录临时用的节点位置，最后删掉，防止内存泄漏cursor->next = newint.first;Node *int1_first = int1.first;Node *int2_first = int2.first;int flag = 0;  //记录加法的进位//首先遍历到 min(int1.length, int2.length)位，之后至少有一个指针为NULLfor (int i = 0; i < int1.length && i < int2.length; i++){int tmp = int1_first->data + int2_first->data + flag;if (tmp >= 10){tmp -= 10;flag = 1;} elseflag = 0;cursor->next->data = tmp;cursor->next->next = new Node;cursor = cursor->next;int1_first = int1_first->next;int2_first = int2_first->next;newint.length++;}if ((int1_first == NULL) && (int2_first == NULL)){}else if(int1_first == NULL){// int2的位数多while (int2_first != NULL){int tmp = int2_first->data + flag;if (tmp >= 10){tmp -= 10;flag = 1;} elseflag = 0;cursor->next->data = tmp;cursor->next->next = new Node;cursor = cursor->next;newint.length++;int2_first = int2_first->next;}}else{while (int1_first != NULL){// int1的位数多int tmp = int1_first->data + flag;if (tmp >= 10){tmp -= 10;flag = 1;} elseflag = 0;cursor->next->data = tmp;cursor->next->next = new Node;cursor = cursor->next;newint.length++;int1_first = int1_first->next;}}delete tobedelete; //删除初始化的临时节点，防止内存泄漏if (flag != 1){//如果最后没有进位，删除末尾的临时节点，防止内存泄漏tobedelete = cursor->next;cursor->next = NULL;delete tobedelete;return newint;}else{//如果有进位，则将数据赋到末尾节点cursor->next->data = 1;cursor->next->next = NULL;newint.length++;}return newint;
}int BigInteger::getLength() //O(1)
{return this->length;
}void BigInteger::print() {stack<int> s;Node *p = first;while (p != NULL){s.push(p->data);p = p->next;}if(!positive)cout << "-";while (!s.empty()){int tmp = s.top();cout << tmp;s.pop();}
}int main()
{//从低位到高位//{个，十，百，千，万，...}int nums1[2] = {2,3};BigInteger int1(nums1, 2);int nums2[2] = {2,3};BigInteger int2(nums2, 2);// srand((unsigned )time(NULL));    //随机数种子// int n = rand() % 50 +1;// int nums1[n];// for(int i = 0; i < n; i++)// {//     nums1[i] = rand()%10;// }// if(nums1[n-1] == 0)//     nums1[n-1] = 1;// BigInteger int1(nums1,n);// n = rand() % 50 + 1;// int nums2[n];// for(int i = 0; i < n; i++)// {//     nums2[i] = rand()%10;// }// if(nums2[n-1] == 0)//     nums2[n-1] = 1;// BigInteger int2(nums2, n);cout << "int1: ";int1.print();cout << endl;cout << "int2: ";int2.print();cout << endl;try{cout << "*********************" << endl;BigInteger newint = add(int1,int2);newint.print();cout << "=";int1.print();cout << "+";int2.print();cout << endl;cout << "*********************" << endl;BigInteger subint = sub(int1,int2);subint.print();cout << "=";int1.print();cout << "-";int2.print();cout << endl;}catch (const char* e){cout << e << endl;return 0;}return 0;
}

程序运行结果：