长整数运算

ゝ一世哀愁。 2021-12-22 00:25 334阅读 0赞

![1520200-20190409191306425-2000070346.png][]

这是一道用链表实现大整数相加的题目，就是模拟加法和减法的过程，思路是很简单的，但是过程还是有些麻烦的。

写的过程也有很多小错误，通过运用测试集不断调试，最后终于写好了，自己完完整整写下来还是花了好几个小时的。

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<math.h>
    #define Max_size 100
    
    /*测试样例
    输入: 0; 0; 输出: 0
    输入: -2345,6789; -7654,3211; 输出:-1,0000,0000
    输入: -9999,9999; 1,0000,0000,0000; 输出: 9999,0000,0001
    输入: 1,0001,0001; -1,0001,0001;  输出:0
    输入： 1,0001,0001; -1,0000,0000;  输出:1
    */
    
    //利用双向循环链表实现长整数的存储
    typedef struct Node
    {
        int data;
        struct Node *prior;
        struct Node *next;
    }DoubleNode,*DoubleList;
    
    DoubleList InitList();
    void Insert(DoubleList *L,int number);
    void Readnumber(DoubleList *L);
    int Length(DoubleList L);
    void Add(DoubleList L1,DoubleList L2,DoubleList *L3);
    void Minus(DoubleList L1,DoubleList L2,DoubleList *L3);
    int Operation(DoubleList L1,DoubleList L2,DoubleList *L3);
    int Size(DoubleList L1,DoubleList L2);
    void Print(DoubleList L);
    
    int main(void)
    {
        DoubleList L1=InitList();
        DoubleList L2=InitList();
        printf("Enter the first integer(each four bits a group,separated by a comma): ");
        Readnumber(&L1);
        int len1=Length(L1);
        printf("Enter the first integer(each four bits a group,separated by a comma): ");
        Readnumber(&L2);
        int len2=Length(L2);
        /*printf("%d %d",len1,len2);
        printf("\n");
        int size=Size(L1,L2);
        printf("%d",size);
        printf("\n");*/
        DoubleList L3=InitList();
        printf("Add results: ");
        int sign=Operation(L1,L2,&L3);
        if(sign==-1)
           printf("%c",'-');
        Print(L3);
        return 0;
    
    }
    
    //建立一个带有头结点的空循环双链表
    DoubleList InitList()
    {
        DoubleList L=(DoubleList)malloc(sizeof(DoubleNode));
        L->prior=L;
        L->next=L;
        return L;
    }
    
    //插入结点时，让链表的高位在链表的尾部，低位在链表的头部
    void Insert(DoubleList *L,int number)
    {
        DoubleNode *p=(DoubleNode*)malloc(sizeof(DoubleNode));
        p->data=number;
        p->next=(*L)->next;
        (*L)->next->prior=p;
        (*L)->next=p;
        p->prior=*L;
    }
    
    //读取输入的整数，每四个数字存放在一个节点中
    void Readnumber(DoubleList *L)
    {
        int number,i=0;
        char c;
        scanf("%d%c",&number,&c);
        while(1)
        {
            if(number<0&&i==0)
            {
                (*L)->data=-1;
                number=abs(number);
                Insert(L,number);
            }
            else if(number>=0&&i==0)
            {
                (*L)->data=1;
                Insert(L,number);
            }
            else if(number>=0&&i!=0)
                Insert(L,number);
            if(c==';')
            {
                i++;
                break;
            }
            scanf("%d%c",&number,&c);
            i++;
        }
    }
    
    //求表长
    int Length(DoubleList L)
    {
        if(L==NULL||(L->next==L&&L->prior==L))
            return 0;
        DoubleNode *p=L->next;
        int count=0;
        while(p!=L)
        {
            count++;
            p=p->next;
        }
        return count;
    }
    
    //将链表中对应结点的绝对值相加
    void Add(DoubleList L1,DoubleList L2,DoubleList *L3)
    {
        DoubleNode *p=L1->next,*q=L2->next;
        int res,carry=0;
        while(p!=L1&&q!=L2)
        {
            res=p->data+q->data+carry;
            if(res>=10000)
            {
                res=res%10000;
                carry=1;
            }
            else
                carry=0;
            Insert(L3,res);
            p=p->next;
            q=q->next;
        }
        if(p==L1&&q!=L2)
        {
            while(q!=L2)
            {
                res=q->data+carry;
                if(res>=10000)
                {
                    res=res%10000;
                    carry=1;
                }
                else
                    carry=0;
                Insert(L3,res);
                q=q->next;
            }
        }
        if(p!=L1&&q==L2)
        {
            while(p!=L1)
            {
                res=p->data+carry;
                if(res>=10000)
                {
                    res=res%10000;
                    carry=1;
                }
                else
                    carry=0;
                Insert(L3,res);
                p=p->next;
            }
        }
        if(carry==1)  //最后最高位的进位有1则在头结点之后插入一个新结点
            Insert(L3,1);
    }
    
    //比较两个链表中存储数据的绝对值的大小
    //返回值为1: L1>L2  返回值为0: L1=L2  返回值为-1: L1<L2
    int Size(DoubleList L1,DoubleList L2)
    {
        DoubleNode *p=L1->next;
        DoubleNode *q=L2->next;
        int len1=Length(L1);
        int len2=Length(L2);
        if(len1>len2)
            return 1;
        if(len1<len2)
            return -1;
        //len1==len2
        while(p!=L1&&q!=L2)
        {
            if(p->data>q->data)
                return 1;
            if(p->data<q->data)
                return -1;
            p=p->next;
            q=q->next;
        }
         return 0;
    }
    
    //相减时，保证L1>=L2
    void Minus(DoubleList L1,DoubleList L2,DoubleList *L3)
    {
        DoubleNode *p=L1->next,*q=L2->next;
        int res,borrow=0;
        while(p!=L1&&q!=L2)
        {
            p->data=p->data+borrow;
            if(p->data>=q->data)
            {
                res=p->data-q->data;
                borrow=0;
            }
            else
            {
                res=p->data+10000-q->data;
                borrow=-1;
            }
            Insert(L3,res);
            p=p->next;
            q=q->next;
        }
        if(p!=L1&&q==L2)
        {
    
            while(p!=L1)
            {
                p->data=p->data+borrow;
                if(p->data<0)
                {
                    res=p->data+10000;
                    borrow=-1;
                    Insert(L3,res);
                    p=p->next;
                }
                if(p->data==0)
                    return;
            }
        }
    }
    
    //加法共有四种情况：正数加正数，正数加负数，负数加负数，负数加正数
    int  Operation(DoubleList L1,DoubleList L2,DoubleList *L3)
    {
        if(L1->data==1&&L2->data==1)
        {
            Add(L1,L2,L3);
            (*L3)->data=1;
            return 1;
        }
        else if(L1->data==-1&&L2->data==-1)
        {
            Add(L1,L2,L3);
            (*L3)->data=-1;
            return -1;
        }
        else if(L1->data==1&&L2->data==-1)
        {
            if(Size(L1,L2)==1)
            {
                Minus(L1,L2,L3);
                (*L3)->data=1;
                return 1;
            }
            else if(Size(L1,L2)==-1)
            {
                Minus(L2,L1,L3);
                (*L3)->data=-1;
                return -1;
            }
            Insert(L3,0);
            return 1;
        }
        else if(L1->data==-1&&L2->data==1)
        {
            if(Size(L1,L2)==1)
            {
                Minus(L1,L2,L3);
                (*L3)->data=-1;
                return -1;
            }
            else if(Size(L1,L2)==-1)
            {
                Minus(L2,L1,L3);
                (*L3)->data=1;
                return 1;
            }
            Insert(L3,0);
            return 1;
        }
    }
    
    //从表头开始输出
    void Print(DoubleList L)
    {
        DoubleNode *p=L->next;
        while(p->data==0&&p->next!=L)
           p=p->next;
        if(p->next==L)
        {
            printf("%d",p->data);
            return;
        }
        printf("%d",p->data);
        while(p->next!=L)
        {
           p=p->next;
           if(p->data<10)
               printf(",000%d",p->data);
           else if(p->data<100)
               printf(",00%d",p->data);
           else if(p->data<1000)
               printf(",0d",p->data);
           else
           printf(",%d",p->data);
        }
    }

转载于:https://www.cnblogs.com/CuteyThyme/p/10679066.html

[1520200-20190409191306425-2000070346.png]: /images/20211220/9965c4d2887f4959b41b393a5e69e5ba.png