DHU-高级程序语言设计链表基础9长整数加法运算

9长整数加法运算

呃 这个题巨长 没难度就是细节特别特别多…第一次有耐心写这么长 最后debug找了同学帮忙 感谢我的小伙伴（鞠躬
问题描述：
假设2个任意长度的整数x、y分别由双向链表A和B存储，现要求设计一个算法，实现x+y。计算结果存储在链表C中。

说明：由于A和B输出时需要从头至尾遍历，而做加法时需要从尾至头遍历，因此使用双向链表存储。可以从长整数的低位开始拆分（4位为一组，即不超过9999的非负整数），依次存放在链表的每个结点的数据域中；头结点的数据域存放正负数标志（正数或0：1，负数：-1）。
输入说明：
第一行：长整数x
第二行：长整数y
输出说明：
第一行：格式化后的长整数x（从低位到高位每4位用",“分开）
第二行：格式化后的长整数y（从低位到高位每4位用”,“分开）
第三行：空行
第四行：单链表C的遍历结果
第五行：格式化后的计算结果（从低位到高位每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
代码：

#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#define N 10000000
using namespace std;

typedef struct DoubleNode {
    int num;
    struct DoubleNode *prior;
    struct DoubleNode *next;
}DLNode;//双链表结构体

void  displayLink(DLNode *head)//用来显示链表 c
{
     DLNode *p;
     p=head->next;
     printf("%d",p->num);
     p=p->next;
       while(p!= NULL)
       {
            printf("->%04d",p->num);
            p=p->next;
       }
}

void insertbyhead(DLNode *head,int numb)//头插插入
{
 DLNode *q,*p;
 q=head;
 if(q->next==NULL)//只有一个头节点的时候
   {
    p=(DLNode*)malloc(sizeof(DLNode));
    p->num=numb;
    p->next=head->next;
    head->next=p;
    p->prior=head;
   }
   else{//除了头节点已经插入别的节点了
     p=(DLNode*)malloc(sizeof(DLNode));
     p->num=numb;
     p->next=head->next;
     head->next=p;
     p->prior=head;//头插法建双链表
     p->next->prior=p;
   }
 }

void CreateDLink(DLNode *head,string str)//创建双链表
{
	DLNode *p;
	if(str[0]=='-')
		head->num=-1;
	else
		head->num=1;
	 int len=str.length();
	 int cnt=0,numb=0;
	 for(int i=len-1;i>=0;i--)
	 {
	     if(str[i]=='-')  break;  //暴力解决循环终点问题哈哈哈
	         numb=numb+pow(10,cnt)*(str[i]-'0');
	         cnt++;
	     if(cnt==4)
	     {
	         insertbyhead(head,numb);
	         cnt=0;numb=0;
	     }
	 }
	 if(cnt!=0){  //解决少于4位数的部分同样也需要插入结点的问题
	  insertbyhead(head,numb);
	 }
}
	
DLNode *calculate(DLNode *heada,DLNode *headb,string str1,string str2)
{
	 DLNode *taila,*tailb,*p,*q1,*q2,*longer,*shorter;
	 int len1,len2;
	 len1=str1.length();
	 len2=str2.length();
	 if(str1[0]=='-')  len1-=1;  //除去负号的真正长度
	 if(str2[0]=='-')  len2-=1;
	 p=heada;
	 int numb=0;
	 while(p->next)
	  p=p->next;
	 taila=p;
	 p=headb;
	 while(p->next)
	  p=p->next;
	 tailb=p;//设置两个尾指针
	 DLNode *headc;
	 headc=(DLNode*)malloc(sizeof(DLNode));
	 headc->next=NULL;
	 headc->prior=NULL;
	 if(len1<len2)//q1始终指向短的那个尾部，q2指向长的链表尾部
	 {
	  longer=headb;//longer指针指向较长链表的头 shorter指向较短链表头
	  shorter=heada;
	  headc->num=headb->num;
	  q1=taila;
	  q2=tailb;
	 }
	 else
	 {
	  headc->num=heada->num;
	  q1=tailb;
	  q2=taila;
	  longer=heada;
	  shorter=headb;
	 }
	 if((heada->num)*(headb->num)>0)//同号的时候 做加法
	 {
	  while(q1!=shorter)//当短的计算完成时
	  {
	   numb=q1->num+q2->num;
	   if(numb>9999)//进位
	   {
	    numb-=10000;
	    q2->prior->num+=1;
	   }
	   insertbyhead(headc,numb);//不进位直接插
	   q1=q1->prior;
	   q2=q2->prior;//这里你加完一个结点后只将q1挪了，未将q2挪
	  }//若两个数长度相等且长度为4的倍数，则当前链表中的结点计算完毕后仍有进位，此时就需要保留此进位并新建一个结点插入
	  if(longer->num==0||longer->num==2)
	  {
	   longer->num-=1;
	   insertbyhead(headc,1);
	  }
	  while(q2!=longer)//把长的剩下的接上
	  {
	   if(q2->num>9999)//判断之前进位后当前位是否要进位
	   {
	    q2->num%=10000;
	    /*q2->prior->num+1;//这里少个=
	    insertbyhead(longer,q2->num);//这里应该是插入到headc吧
	    */
	    q2->prior->num+=1;
	    insertbyhead(headc,q2->num);
	    if(q2->prior==longer)//如果已经移动到最前面这个数据节点还要进位 就多加一个节点 数值位1
	    {
	    headc->num-1;
	    insertbyhead(headc,1);
	    }
	   }//少了个else，不需要进位的话应该直接插入到headc
	   else{
	                insertbyhead(headc,q2->num);
	   }
	   q2=q2->prior;
	  }
	 }
	 else//异号的时候 就是做减法
	 {
	  while(q1!=shorter)//当短的计算完成时
	  {
	   int numb=q2->num-q1->num;
	   if(numb<0)//借位
	   {
	    numb=q2->num+10000-q1->num;
	    q2->prior->num-=1;
	   }
	   insertbyhead(headc,numb);
	   q1=q1->prior;
	   q2=q2->prior;
	  }
	  while(q2!=longer)//把长的剩下的接上
	  {
	   if(q2->num<0)//借位
	   {
	    q2->num=9999;
	    q2->prior->num-=1;
	    //insertbyhead(headc,q2->num);//重复插入
	    /*if(q2->prior==longer)//如果借位后 节点数据<0 就把这个节点删了,我想它应该换个位置
	    {
	     longer->num+1;
	     DLNode *temp;
	     longer->next=q2->next;
	     temp=q2;
	     q2->next->prior=longer;
	     delete temp;
	    }*/
	   }
	   insertbyhead(headc,q2->num);
	   q2=q2->prior;
	  }
	  q1=headc;   //去掉结果链表headc中前面的0，但是若链表headc中所有结点均为0就保留最后一个
	  while(q1->next->num==0 && q1->next->next != NULL)
	        {
	            DLNode *temp;
	            temp=q1->next;
	            q1->next=temp->next;
	            temp->next->prior=q1;
	            delete temp;
	        }
	 }
	 return headc;
	}
	
int main(){
    string str1,str2;
    cin>>str1>>str2;
    DLNode *num1, *num2;
    num1=(DLNode*)malloc(sizeof(DLNode));
    num2=(DLNode*)malloc(sizeof(DLNode));
    num1->next=NULL;
    num1->prior=NULL;
    num2->next=NULL;
    num2->prior=NULL;
    CreateDLink(num1,str1);
    display(num1);
    CreateDLink(num2,str2);
    display(num2);
    printf("\n");
    DLNode *num3;
    num3=calculate(num1,num2,str1,str2);
    displayLink(num3);
    printf("\n");
    display(num3);
    return 0;
}