北邮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 + int2
friend BigInteger sub(BigInteger &int1, BigInteger &int2); //int1 - int2
int 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 + int2
int2.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; //遍历int1
Node *int2_first = int2.first; //遍历int2
stack<Node*> substk; //定义一个栈用来处理高位的连续0 如77772-77771 = 1 ，需要把前面的0都删除
int flag = 0; //记录减法的借位
//首先遍历到 min(int1.length, int2.length)位，之后至少有一个指针为NULL
for (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 = 7
int 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; //创建一个游标指针用于构建newint
Node *tobedelete = cursor; //记录临时用的节点位置，最后删掉，防止内存泄漏
cursor->next = newint.first;
Node *int1_first = int1.first;
Node *int2_first = int2.first;
int flag = 0; //记录加法的进位
//首先遍历到 min(int1.length, int2.length)位，之后至少有一个指针为NULL
for (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;
} else
flag = 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;
} else
flag = 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;
} else
flag = 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;
}
程序运行结果：
![[论文解析] Cones: Concept Neurons in Diffusion Models for Customized Generation](https://img-blog.csdnimg.cn/c14ccae6016c49269e2bddc8260189a5.png#pic_center)
