建设银行环县支行网站,微营销推广的种类有哪些,电子政务网站建设ppt,免费注册邮箱北邮22信通一枚~
跟随课程进度每周更新数据结构与算法的代码和文章
持续关注作者 解锁更多邮苑信通专属代码~
上一篇文章#xff1a;
北邮22信通#xff1a;#xff08;7#xff09;实验1 题目四#xff1a;一元多项式#xff08;节省内存版#xff09;_青山如…北邮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; in - 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; //遍历int2stackNode* 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.length1];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() {stackint 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;
}程序运行结果
