论坛 › C\C++交流 › 数据结构

Echo。 发表于 2020-12-7 10:44:54

数据结构

[问题描述]设计一个程序实现两个任意 长的整数的求和运算

[输入形式]按中国对于长整数的表示习惯，每四位一一组， 组间用逗号隔开

[输出形式]每四位一组，组间用逗号隔开

【评分标准】任何整形变量的范围是：-（215-1）~（215-1）。采用恰当的存储结构，如：利用双向循环链表实现长整数的存储，每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表视为万位制数。可以利用头结点数据域的符号代表长整数的符号，用其绝对值表示元素结点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数的位数规定上限。

【选作内容】修改上述程序，使它在整形量范围是-（2n-1）~（2n-1）的计算机上都能有效地运行。其中，n是由程序读入的参量。

xieglt 发表于 2020-12-7 14:08:59

用的数组实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BASE                (10000)
#define        NUM_LEN                (4)
#define        _BASE_SIZE        (1024)
#define ISINIT(p)        ((p->_data != 0) && (p->_flag == 0))

typedef struct tagInteger
{
        int * _data;
        int _size;
        int _len;
        int _flag;
}INTEGER,*LPINTEGER;

int _InitInteger(LPINTEGER n,int size = 0)
{
        size = ((size == 0) ? _BASE_SIZE : size);
       
        n->_size = 0;
        n->_data = (int *)malloc(size * sizeof(int));
       
        if(n->_data == 0)
        {
                return 0;
        }

        memset(n->_data,0,size * sizeof(int));
        n->_len = 0;
        n->_size = size;
        n->_flag = 0;
        return 1;
}

void _UninitInteger(LPINTEGER n)
{
        if(ISINIT(n))
        {
                free(n->_data);
        }
}

int _ResizeInteger(LPINTEGER n,int _size = 0)
{
        int len = n->_size;
       
        if(!ISINIT(n))
        {
                return _InitInteger(n,_size);
        }
               
        if(_size < _BASE_SIZE)
        {
                n->_size += _BASE_SIZE;
        }
        else
        {
                n->_size += _size;
        }
               
        n->_data = (int *)realloc(n->_data,n->_size * sizeof(int));
               
        if(n->_data == 0)
        {
                        return 0;
        }
       
        memset(n->_data + len,0,(n->_size - len) * sizeof(int));
        return 1;
}

int _String2Integer(LPINTEGER pNum,char * number)
{
        int i = 0;
        int nRet = 0;
        char cByte = 0;
        int value = 0;
        int power = 0;
        int index =0;
        int nLen = strlen(number);
        int size = nLen / NUM_LEN + (nLen % NUM_LEN == 0 ? 0 : 1);

        do
        {
                if(nLen == 0)
                {
                        break;
                }
               
                if(!ISINIT(pNum) && _InitInteger(pNum,size) == 0)
                {
                        break;
                }

                if(size > pNum->_size && _ResizeInteger(pNum,size) == 0)
                {
                        break;
                }
               
                for(i=0 ; i<nLen ; i++)
                {
                        if(number<'0' || number>'9')
                        {
                                break;
                        }
                }
                if(i < nLen--)
                {
                        break;
                }


                for(i=nLen ; i>=0 ; i--)
                {
                        if((nLen - i) % NUM_LEN == 0)
                        {
                                if(nLen - i != 0)
                                {
                                        pNum->_data = value;
                                }

                                value = 0;
                                power = 1;
                        }
                        cByte = number - 0x30;
                        value += power * cByte;
                        power *= 10;
                }

                if(value != 0)
                {
                        pNum->_data = value;
                }

                pNum->_len = index;               
                nRet = 1;
        }while(0);

        return nRet;
}

int _Integer2String(LPINTEGER pNum,char * number)
{
        int i = 0;
        int nRet = 0;
        char buffer = {0};
       
        do
        {
                if(!ISINIT(pNum))
                {
                        break;
                }

                if(number == 0)
                {
                        nRet = pNum->_len * NUM_LEN + 1;
                        break;
                }

                number = 0;
               
                for(i=pNum->_len-1 ; i>=0 ; i--)
                {
                        if(i == pNum->_len-1)
                        {
                                sprintf(buffer,"%d",pNum->_data);
                        }
                        else
                        {
                                sprintf(buffer,"%04d",pNum->_data);
                        }
                        strcat(number,buffer);
                        if(i != 0)
                        {
                                strcat(number,",");
                        }
                }

                nRet = strlen(number);
        }while(0);

        return nRet;
}

void _PushBack(LPINTEGER src,int data)
{

        if(src->_len == src->_size)
        {
                if(!_ResizeInteger(src))
                {
                        return;
                }
        }

        src->_data = data;
}

void _IntegerAdd(LPINTEGER src,LPINTEGER dst)
{
        int sizeofme = src->_len;
        int sizeofyou = dst->_len;
        int len = sizeofme >= sizeofyou ? sizeofme : sizeofyou;
        int i = 0;
        int value = 0;
        int carry = 0;

        for(i=0 ; i<len ; i++)
        {
                value = carry;
                if(i < sizeofme)
                {
                        value += src->_data;
                }

                if(i < sizeofyou)
                {
                        value += dst->_data;
                }

                carry = value / BASE;
                value %= BASE;

                if(i < sizeofme)
                {
                        src->_data = value;
                }
                else
                {
                        _PushBack(src,value);
                }
        }

        if(carry != 0)
        {
                if(i < sizeofme)
                {
                        src->_data = carry;
                }
                else
                {
                        _PushBack(src,carry);
                }
        }

};


int main(int argc, char* argv[])
{
        INTEGER n,m;
        char buffer;
        _InitInteger(&n);
        _InitInteger(&m);
        _String2Integer(&n,"1234567890987654321012345678909876543210123");
        _String2Integer(&m,"9999888877777666665555544443333222211110000");
        _IntegerAdd(&n,&m);
        _Integer2String(&n,buffer);
        _UninitInteger(&n);
        _UninitInteger(&m);
        printf("%s",buffer);
        return 0;
}

xieglt 发表于 2020-12-7 14:44:37

本帖最后由 xieglt 于 2020-12-7 14:53 编辑

后面才看到要考虑符号。又改了下，一个有符号的版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define BASE                (10000)
#define        NUM_LEN                (4)
#define        _BASE_SIZE        (1024)
#define ISINIT(p)        ((p->_data != 0) && (p->_flag == 0))

typedef struct tagInteger
{
        int * _data;
        int _size;
        int _len;
        int _signed;
        int _flag;
}INTEGER,*LPINTEGER;

int _InitInteger(LPINTEGER n,int size = 0)
{
        size = ((size == 0) ? _BASE_SIZE : size);
       
        n->_size = 0;
        n->_data = (int *)malloc(size * sizeof(int));
       
        if(n->_data == 0)
        {
                return 0;
        }

        memset(n->_data,0,size * sizeof(int));
        n->_len = 0;
        n->_size = size;
        n->_flag = 0;
        return 1;
}

void _UninitInteger(LPINTEGER n)
{
        if(ISINIT(n))
        {
                free(n->_data);
        }
}

int _ResizeInteger(LPINTEGER n,int _size = 0)
{
        int len = n->_size;
       
        if(!ISINIT(n))
        {
                return _InitInteger(n,_size);
        }
               
        if(_size < _BASE_SIZE)
        {
                n->_size += _BASE_SIZE;
        }
        else
        {
                n->_size += _size;
        }
               
        n->_data = (int *)realloc(n->_data,n->_size * sizeof(int));
               
        if(n->_data == 0)
        {
                        return 0;
        }
       
        memset(n->_data + len,0,(n->_size - len) * sizeof(int));
        return 1;
}

int _String2Integer(LPINTEGER pNum,char * number)
{
        int i = 0;
        int nRet = 0;
        char cByte = 0;
        int value = 0;
        int power = 0;
        int index =0;
        int len = strlen(number);
        int size = len / NUM_LEN + (len % NUM_LEN == 0 ? 0 : 1);
        int flag = 0;

        do
        {
                if(len == 0)
                {
                        break;
                }

               
                if(number=='-' || number=='+')
                {
                        if(number == '-')
                        {
                                flag = 1;
                        }
                       
                        number ++;
                        len --;
                }
               
                if(!ISINIT(pNum) && _InitInteger(pNum,size) == 0)
                {
                        break;
                }

                if(size > pNum->_size && _ResizeInteger(pNum,size) == 0)
                {
                        break;
                }
               
                for(i=0 ; i<len ; i++)
                {
                        if(number<'0' || number>'9')
                        {
                                break;
                        }
                }
                if(i < len--)
                {
                        break;
                }


                for(i=len ; i>=0 ; i--)
                {
                        if((len - i) % NUM_LEN == 0)
                        {
                                if(len - i != 0)
                                {
                                        pNum->_data = value;
                                }

                                value = 0;
                                power = 1;
                        }
                        cByte = number - 0x30;
                        value += power * cByte;
                        power *= 10;
                }

                if(value != 0)
                {
                        pNum->_data = value;
                }
                pNum->_signed = flag;
                pNum->_len = index;
                while(pNum->_data == 0)
                {
                        pNum->_len--;
                }
                nRet = 1;
        }while(0);

        return nRet;
}

int _Integer2String(LPINTEGER pNum,char * number)
{
        int i = 0;
        int nRet = 0;
        char buffer = {0};
       
        do
        {
                if(!ISINIT(pNum))
                {
                        break;
                }

                if(number == 0)
                {
                        nRet = pNum->_len * (NUM_LEN + 1) + 1;
                        break;
                }

                number = 0;

                if(pNum->_signed != 0)
                {
                        strcat(number,"-");
                }
               
                for(i=pNum->_len-1 ; i>=0 ; i--)
                {
                        if(i == pNum->_len-1)
                        {
                                sprintf(buffer,"%d",pNum->_data);
                        }
                        else
                        {
                                sprintf(buffer,"%04d",pNum->_data);
                        }
                        strcat(number,buffer);
                        if(i != 0)
                        {
                                strcat(number,",");
                        }
                }

                nRet = strlen(number);
        }while(0);

        return nRet;
}

void _PushBack(LPINTEGER src,int data)
{

        if(src->_len == src->_size)
        {
                if(!_ResizeInteger(src))
                {
                        return;
                }
        }

        src->_data = data;
}

void _SimpleAdd(LPINTEGER src,LPINTEGER dst)
{
        int sizeofme = src->_len;
        int sizeofyou = dst->_len;
        int len = sizeofme >= sizeofyou ? sizeofme : sizeofyou;
        int i = 0;
        int value = 0;
        int carry = 0;

        for(i=0 ; i<len ; i++)
        {
                value = carry;
                if(i < sizeofme)
                {
                        value += src->_data;
                }

                if(i < sizeofyou)
                {
                        value += dst->_data;
                }

                carry = value / BASE;
                value %= BASE;

                if(i < sizeofme)
                {
                        src->_data = value;
                }
                else
                {
                        _PushBack(src,value);
                }
        }

        if(carry != 0)
        {
                if(i < sizeofme)
                {
                        src->_data = carry;
                }
                else
                {
                        _PushBack(src,carry);
                }
        }
};

void _SimpleSub(LPINTEGER src,LPINTEGER dst)
{
        int sizeofme = src->_len;
        int sizeofyou = dst->_len;
        int i = 0;
        int value = 0;
        int carry = 0;
       
        for(i=0 ; i<sizeofme ; i++)
        {
                value = src->_data;

                if(i < sizeofyou)
                {
                        value -= dst->_data;
                }
               
                value -= carry;
               
                if(value < 0)
                {
                        value += BASE;
                        carry = 1;
                }
                else
                {
                        carry = 0;
                }
                src->_data = value;
        }

        while(src->_data == 0)
        {
                src->_len--;
        }
}

int _UnsignedCompare(LPINTEGER src,LPINTEGER dst)
{
        int i = 0;

        if(src->_len > dst->_len)
        {
                return 1;
        }
        else if(src->_len < dst->_len)
        {
                return -1;
        }
       
        for(i=src->_len-1 ; i>=0 ; i--)
        {
                if(src->_data > dst->_data)
                {
                        return 1;
                }
                else if(src->_data < dst->_data)
                {
                        return -1;
                }
        }

        return 0;
}

void _CopyInteger(LPINTEGER dst,LPINTEGER src)
{
        if(!ISINIT(dst))
        {
                if(!_InitInteger(dst,src->_size))
                {
                        return;
                }
        }
        else if(dst->_size < src->_size)
        {
                if(!_ResizeInteger(dst,src->_size))
                {
                        return;
                }
        }

        memcpy(dst->_data,src->_data,src->_size);
        dst->_len = src->_len;
        dst->_signed = src->_signed;
}

void _UnsignedSub(LPINTEGER src,LPINTEGER dst)
{
        INTEGER n;
        int _signed = src->_signed;

        if(_UnsignedCompare(src,dst) == -1)
        {

                _CopyInteger(&n,dst);
                _SimpleSub(&n,src);
                _CopyInteger(src,&n);
                _UninitInteger(&n);
                src->_signed = !_signed;
        }
        else
        {
                _SimpleSub(src,dst);
        }
}

void _AddInteger(LPINTEGER src,LPINTEGER dst)
{
        int _signed = src->_signed - dst->_signed;
        if(_signed == 0)
        {
                _SimpleAdd(src,dst);
        }
        else
        {
                _UnsignedSub(src,dst);
        }
}

void _SubInteger(LPINTEGER src,LPINTEGER dst)
{
        int _signed = src->_signed - dst->_signed;
        if(_signed != 0)
        {
                _SimpleAdd(src,dst);
        }
        else
        {
                _UnsignedSub(src,dst);
        }
}

int main(int argc, char* argv[])
{
        INTEGER n,m;
        char buffer;
        _InitInteger(&n);
        _InitInteger(&m);
        _String2Integer(&n,"-1234567890987654321012345678909876543210123");
        _String2Integer(&m,"99998888777776666655555444433332222111100001234567890");
       
        _AddInteger(&n,&m);
        _Integer2String(&n,buffer);
        _UninitInteger(&n);
        _UninitInteger(&m);
        printf("%s",buffer);
        return 0;
}

查看完整版本: 数据结构