dhu编程练习

9 长整数加法运算

1.问题描述
假设2个任意长度的整数x、y分别由双向链表A和B存储，现要求设计一个算法，实现x+y。计算结果存储在链表C中。

说明：

由于A和B输出时需要从头至尾遍历，而做加法时需要从尾至头遍历，因此使用双向链表存储。

可以从长整数的低位开始拆分（4位为一组，即不超过9999的非负整数），依次存放在链表的每个结点的数据域中；头结点的数据域存放正负数标志（正数或0：1，负数：-1）。

2.输入说明
第一行：长整数x

第二行：长整数y
3.输出说明
第一行：格式化后的长整数x（从低位到高位每4位用","分开）

第二行：格式化后的长整数y（从低位到高位每4位用","分开）

第三行：空行

第四行：单链表C的遍历结果

第五行：格式化后的计算结果（从低位到高位每4位用","分开）

（输入与输出之间用一空行分隔）

4.范例
输入
-53456467576846547658679870988098
435643754856985679
输出
-5345,6467,5768,4654,7658,6798,7098,8098
43,5643,7548,5698,5679

5345->6467->5768->4611->2014->9250->1400->2419
-5345,6467,5768,4611,2014,9250,1400,2419
5.代码

#include <iostream>
#include <string> //cin>>s1>>s2;
#include <math.h>
#include<algorithm> //使用reverse()函数
using namespace std;

//头结点的数据域存放正负数标志（正数或0：1，负数：-1） head->num=1(0或者正数)
struct node {
            
	int num;
	struct node* pre;
	struct node* next;
};

struct node* create(string s) {
       //由于链表从尾部到头部相加，所以结果采用头插法插入

	//1.新建头结点并初始化
	struct node* head = new node;
	head->next = NULL;
	head->pre = NULL;

	//2.计算链表真正长度
	int len=s.length();

	if (s[len - 1] == '-') {
    
		len = s.length() - 1;
		head->num = -1;
	}
	else {
    
		len = s.length();
		head->num = 1;
	}
	//3.进行相加工作，num保存结果数值，cnt用于控制每四位相加
	int cnt = 0;
	int num = 0;
	for (int i = 0; i < len; i++) {
    

		//num += (int)(s[i] - '0') * (pow(10, cnt) + 0.1);//此处改成num +=(s[i] - '0') * pow(10, cnt);
		num += (s[i] - '0') * pow(10, cnt);
		cnt++;
		if (cnt == 4 || i == len - 1) {
        //当读取4个数时重置

			struct node* p = new node;
			struct node* q = head->next;
			p->num = num;//p所指为新建结点

			head->next = p;
			p->pre = head;
			p->next = q;
			//链表中除了头结点，还有其他结点
			if (q)
				q->pre = p;

			cnt = 0;
			num = 0;
		}

	}   
	return head;
}

void display(struct node* head) {
    

	if (head->next) {
      //存在数据时

		if (head->num == -1)
			cout << '-';
		struct node* p = head->next;
		cout << p->num;
		p = p->next;
		while (p) {
    
			printf(",%04d", p->num);
			p = p->next;
		}

	}
	else
		cout << 0; //注意这里要考虑到没有数据的情况
}

struct node* add(struct node* num1, struct node* num2) {
       //两个链表相加情况 ，类似于合并链表操作

	struct node* head = new node;
	head->next = NULL;
	head->pre = NULL;
	
	struct node* p = num1;
	struct node* q = num2;
	
	while (p->next)
		p = p->next;
	
	while (q->next)
		q = q->next;

	//1.链表num1,num2均非空
	while (p != num1 && q != num2) {
              //从尾部到头部进行遍历

		struct node* t = new node;
		struct node* f = head->next;

		t->num = num1->num*p->num + num2->num*q->num;  //num1->num代表链表L1的符号 ， num2->num代表链表L2的符号 
		//t->num = p->num + q->num;这应该不行，因为Line ：155处开始有关于符号的处理

		head->next = t;
		t->pre = head;
		t->next = f;
		if (f)
			f->pre = t;

		p = p->pre;
		q = q->pre;
	}
	//2.链表num1非空，num2已空
	while (p != num1) {
         //类似于合并有序表，对没有运算的结点采用头部插入的方法

		struct node* t = new node;
		struct node* h = head->next;

		t->num = num1->num * p->num;

		head->next = t;
		t->pre = head;
		t->next = h;
		if (h)
			h->pre = t;
		p = p->pre;
	}
	//3.链表num2非空，num1已空
	while (q != num2) {
    

		struct node* t = new node;
		struct node* o = head->next;

		t->num = num2->num * q->num;

		head->next = t;
		t->pre = head;
		t->next = o;
		if (o)
			o->pre = t;
		q = q->pre;
	}

	//4.判断最后的取值是正是负
	if (head->next->num > 0)   
		head->num = 1;
	else
		head->num = -1;

	p = head;
	while (p->next)
		p = p->next;
	q = p;//q指向链表尾部结点

	/*接下来部分理解很重要！！！*/
	//5.处理进位情况 p指向链表尾部，逐步向前遍历
	while (p != head) {
                     //p指向链表尾部结点

		//关键：处理有进位的情况
		if (p->num * head->num < 0) {
      //正数借位减一，负数借位加1
			if (head->num > 0) {
     //正数
				p->num += 10000;
				p->pre->num -= 1;
			}
			else {
    
				p->num -= 10000;
				p->pre->num += 1;
			}
		}

		p = p->pre; //从尾部到前部进行遍历
	}
	
	

	//6.将原先带符号的各个数据结点都恢复为处理为正常形式，即只有头结点head->num==1||head->num==-1代表正负数或0
	p = head->next;
	while (p) {
    
		p->num = abs(p->num);
		p = p->next;
	}
	//7.处理进位情况，注意和5进行区分
	//q==head->next指代链表第一个数据结点（非头结点）
	while (q != head->next) {
              //进行进位处理
		if (q->num >= 10000) {
    
			q->num -= 10000;
			q->pre->num += 1;
		}
		q = q->pre;
	}

	if (q && q->num >= 10000) {
      //产生进位情况时

		struct node* t = new node;
		t->next = q;
		q->pre = t;
		head->next = t;
		t->pre = head;
		t->num = q->num / 10000;
		q->num = q->num % 10000;
	}

	//8.删除前面为0的结点
	p = head->next; 
	//当前边出现0时删除该结点 
	while (p && p->num == 0) {
    

		p->pre->next = p->next; //p结点指向数据为0 ，使P结点的前驱结点指向P的后继结点 处理P的前驱结点的next指向 

		if (p->next)
			p->next->pre = p->pre; //处理P的后继结点的pre指针指向

		p = p->next;
	}
	return head;
};
void display_2(struct node* head) {
    

	if (head->next) {
    
		struct node* p = head->next;

		cout << p->num;
		p = p->next;
		while (p) {
    
			printf("->%04d", p->num);  //%04d保证数据输出为四位数形式，若不足则在左边补零
			p = p->next;
		}
		cout << endl;
	}
	else
		cout << 0 << endl;
}

int main() {
    


	string s1, s2;
	struct node *num1, *num2, *c;

	cin >> s1;
	cin >> s2;


	reverse(s1.begin(), s1.end());
	num1 = create(s1);
	display(num1);
	cout << endl;

	reverse(s2.begin(), s2.end());
	num2 = create(s2);
	display(num2);
	cout << endl << endl;

	c = add(num1, num2);

	display_2(c);
	display(c);

	return 0;
}