C语言 双向链表处理大数加减

2023-12-19 12:13:58

处理无符号大数加减

处理有符号大数加减

处理有符号大数加减

1.定义的结构体

struct Node
{
    int digit;  //数字
    struct Node *next, *prev;  //前后指针
};

struct UBigNumber
{
    int digitCount;  //位数
    struct Node *pHead, *pTail;  //指向头结点和尾结点
};

2.定义的函数：

//动态分配1个结点，返回结点指针
//当分配失败时，简化程序，退出运行
struct Node *_NewNode();

//表示无符号大数用带头结点的双向链表
void _InitUBN(struct UBigNumber *pUBN);

//输入无符号大数
struct UBigNumber InputUBN();

//无符号大数尾部添加1位数字
void _AppendDigit(struct UBigNumber *pUBN, int digit);

//无符号大数首部添加1位数字
void _AppendFrontDigit(struct UBigNumber *pUBN, int digit);

//无符号大数的规范表示，去除高位多余的0，至少含1位数字
void _Normalize(struct UBigNumber *pUBN);

//两个无符号大数相加
struct UBigNumber AddUBN(struct UBigNumber *pA, struct UBigNumber *pB);

//无符号整数相减
struct UBigNumber SubUBN(struct UBigNumber *pA, struct UBigNumber *pB);

//打印无符号大数
void PrintUBN(struct UBigNumber ubn);

//销毁无符号大数，释放空间
void DestroyUBN(struct UBigNumber *pA);

  1. 函数实现代码：
//动态分配1个结点，返回结点指针
//当分配失败时，简化程序，退出运行
struct Node *_NewNode()
{
    struct Node *p;
    p = (struct Node*)malloc(sizeof(struct Node));
    if(p == NULL)  //分配失败
    {
        printf("Error:out of memory\n");
        exit(-1);  //简化程序，退出运行
    }
    return p;

}


//建立表示无符号大数用带头结点的双向链表
void _InitUBN(struct UBigNumber *pUBN)
{
    struct Node *p = _NewNode();
    pUBN->pHead = pUBN->pTail = p;  //建立头结点
    p->next = p->prev = NULL;
    pUBN->digitCount = 0;
}


//输入无符号大数
struct UBigNumber InputUBN()
{
    struct UBigNumber result;
    _InitUBN(&result);

    char ch;
    //跳过非数字字符
    do
        ch = getchar();
    while(ch < '0' || ch > '9');
    while(ch >= '0' && ch <= '9')
    {
        _AppendDigit(&result, ch-'0');  //添加1位
        ch = getchar();
    }
    _Normalize(&result);
    return result;
}


//无符号大数尾部添加1位数字
void _AppendDigit(struct UBigNumber *pUBN, int digit)
{  //原来只有一个高位0
    if(pUBN->digitCount == 1 && pUBN->pTail->digit == 0)
    {
        pUBN->pTail->digit = digit;  //位数不变，数值为0
        return;
    }
    struct Node *p = _NewNode();  //申请新结点
    p->digit = digit;  //设置结点数值
    p->next = NULL;  //修改双向链表，将新结点添加到尾部
    p->prev = pUBN->pTail;
    pUBN->pTail->next = p;
    pUBN->pTail = p;
    ++pUBN->digitCount;  //修改位数
}


//无符号大数首部添加1位数字
void _AppendFrontDigit(struct UBigNumber *pUBN, int digit)
{
    struct Node *p = _NewNode();  //申请新结点
    p->digit = digit;  //设置结点数值
    p->next = pUBN->pHead->next;  //修改双向链表，将新结点添加在头结点后
    if(p->next != NULL)
        p->next->prev = p;
    p->prev = pUBN->pHead;
    pUBN->pHead->next = p;
    if(pUBN->pTail == pUBN->pHead)
        pUBN->pTail = p;  //当原来只有头结点时，新结点也是尾结点
    ++pUBN->digitCount;  //修改位数
}


//无符号大数的规范表示，去除高位多余的0，至少含1位数字
void _Normalize(struct UBigNumber *pUBN)
{
    if(pUBN->digitCount == 0)
        _AppendDigit(pUBN, 0);
    while(pUBN->digitCount > 1 && pUBN->pHead->next->digit == 0)
    {   //去除高位多余的0
        struct Node *p;
        p = pUBN->pHead->next;  //待删除的结点
        pUBN->pHead->next = p->next;  //正向链表中删除
        p->next->prev = pUBN->pHead;  //反向链表中删除
        free(p);  //释放结点
        --pUBN->digitCount;  //调整位数
    }
}


//两个无符号大数相加
struct UBigNumber AddUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct UBigNumber result, *pResult = &result;
    _InitUBN(pResult);
    int iCarry = 0;  //进位，初始0
    struct Node *p1, *p2;
    p1 = pA->pTail;  //从低位开始处理
    p2 = pB->pTail;
    while(p1 != pA->pHead && p2 != pB->pHead)  //两数相同位处理
    {
        int digit = p1->digit + p2->digit + iCarry;
        iCarry = digit / 10;  //新进位
        digit %= 10;  //当前结果位
        _AppendFrontDigit(pResult, digit);  //添加至结果最高位
        p1 = p1->prev;  //准备处理前一位
        p2 = p2->prev;
    }
    while(p1 != pA->pHead)  //第一位大数剩余位处理
    {
        int digit = p1->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    while(p2 != pB->pHead)  //第二位大数剩余位处理
    {
        int digit = p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p2 = p2->prev;
    }
    if(iCarry != 0)  //最后进位处理
        _AppendFrontDigit(pResult, iCarry);
    return result;
}


//两个无符号大数相减
struct UBigNumber SubUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct UBigNumber result, *pResult = &result;
    _InitUBN(pResult);
    int iCarry = 0;  //退位，初始0
    struct Node *p1, *p2;
    p1 = pA->pTail;  //从低位开始处理
    p2 = pB->pTail;
    while(p1 != pA->pHead && p2 != pB->pHead)  //两数相同位处理
    {
        int digit = p1->digit - p2->digit - iCarry;
        iCarry = 0; //初始化
        if(digit < 0)
        {
            digit += 10;  
            iCarry = 1;  //前一位退1
        }
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
        p2 = p2->prev;
    }
    while(p1 != pA->pHead)  //最后退位处理
    {
        int digit = p1->digit - iCarry;
        iCarry = 0;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    _Normalize(pResult);
    return result;
}


//打印无符号大数
void PrintUBN(struct UBigNumber ubn)
{  //断言：至少有1位数字
    assert(ubn.digitCount > 0 && ubn.pHead->next != NULL);
    struct Node *la = ubn.pHead->next;  //头结点无数据，跳过
    while(la)
    {
        printf("%d",la->digit);
        la = la->next;
    }
}


//销毁无符号大数，释放空间
void DestroyUBN(struct UBigNumber *pUBN)
{
    while(pUBN->pHead != NULL)
    {
        struct Node *p = pUBN->pHead;  //待删除结点
        pUBN->pHead = p->next;  //尾指针前移
        free(p);  //释放结点
    }
}

4.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>


struct Node
{
    int digit;  //数字
    struct Node *next, *prev;  //前后指针
};

struct UBigNumber
{
    int digitCount;  //位数
    struct Node *pHead, *pTail;  //指向头结点和尾结点
};


//动态分配1个结点，返回结点指针
//当分配失败时，简化程序，退出运行
struct Node *_NewNode();
//表示无符号大数用带头结点的双向链表
void _InitUBN(struct UBigNumber *pUBN);
//输入无符号大数
struct UBigNumber InputUBN();
//无符号大数尾部添加1位数字
void _AppendDigit(struct UBigNumber *pUBN, int digit);
//无符号大数首部添加1位数字
void _AppendFrontDigit(struct UBigNumber *pUBN, int digit);
//无符号大数的规范表示，去除高位多余的0，至少含1位数字
void _Normalize(struct UBigNumber *pUBN);
//两个无符号大数相加
struct UBigNumber AddUBN(struct UBigNumber *pA, struct UBigNumber *pB);
//无符号整数相减
struct UBigNumber SubUBN(struct UBigNumber *pA, struct UBigNumber *pB);
//打印无符号大数
void PrintUBN(struct UBigNumber ubn);
//销毁无符号大数，释放空间
void DestroyUBN(struct UBigNumber *pA);


int main()
{
    struct UBigNumber A, B, C, D;
    A = InputUBN();
    B = InputUBN();
    C = AddUBN(&A, &B);
    D = SubUBN(&A, &B);

    PrintUBN(A);
    printf("+");
    PrintUBN(B);
    printf("=");
    PrintUBN(C);
    printf("\n");

    PrintUBN(A);
    printf("-");
    PrintUBN(B);
    printf("=");
    PrintUBN(D);

    DestroyUBN(&A);
    DestroyUBN(&B);
    DestroyUBN(&C);
    DestroyUBN(&D);

    return 0;
}


struct Node *_NewNode()
{
    struct Node *p;
    p = (struct Node*)malloc(sizeof(struct Node));
    if(p == NULL)  //分配失败
    {
        printf("Error:out of memory\n");
        exit(-1);  //简化程序，退出运行
    }
    return p;

}


//建立表示无符号大数用带头结点的双向链表
void _InitUBN(struct UBigNumber *pUBN)
{
    struct Node *p = _NewNode();
    pUBN->pHead = pUBN->pTail = p;  //建立头结点
    p->next = p->prev = NULL;
    pUBN->digitCount = 0;
}


//输入无符号大数
struct UBigNumber InputUBN()
{
    struct UBigNumber result;
    _InitUBN(&result);

    char ch;
    //跳过非数字字符
    do
        ch = getchar();
    while(ch < '0' || ch > '9');
    while(ch >= '0' && ch <= '9')
    {
        _AppendDigit(&result, ch-'0');  //添加1位
        ch = getchar();
    }
    _Normalize(&result);
    return result;
}


//无符号大数尾部添加1位数字
void _AppendDigit(struct UBigNumber *pUBN, int digit)
{  //原来只有一个高位0
    if(pUBN->digitCount == 1 && pUBN->pTail->digit == 0)
    {
        pUBN->pTail->digit = digit;  //位数不变，数值为0
        return;
    }
    struct Node *p = _NewNode();  //申请新结点
    p->digit = digit;  //设置结点数值
    p->next = NULL;  //修改双向链表，将新结点添加到尾部
    p->prev = pUBN->pTail;
    pUBN->pTail->next = p;
    pUBN->pTail = p;
    ++pUBN->digitCount;  //修改位数
}


//无符号大数首部添加1位数字
void _AppendFrontDigit(struct UBigNumber *pUBN, int digit)
{
    struct Node *p = _NewNode();  //申请新结点
    p->digit = digit;  //设置结点数值
    p->next = pUBN->pHead->next;  //修改双向链表，将新结点添加在头结点后
    if(p->next != NULL)
        p->next->prev = p;
    p->prev = pUBN->pHead;
    pUBN->pHead->next = p;
    if(pUBN->pTail == pUBN->pHead)
        pUBN->pTail = p;  //当原来只有头结点时，新结点也是尾结点
    ++pUBN->digitCount;  //修改位数
}


//无符号大数的规范表示，去除高位多余的0，至少含1位数字
void _Normalize(struct UBigNumber *pUBN)
{
    if(pUBN->digitCount == 0)
        _AppendDigit(pUBN, 0);
    while(pUBN->digitCount > 1 && pUBN->pHead->next->digit == 0)
    {   //去除高位多余的0
        struct Node *p;
        p = pUBN->pHead->next;  //待删除的结点
        pUBN->pHead->next = p->next;  //正向链表中删除
        p->next->prev = pUBN->pHead;  //反向链表中删除
        free(p);  //释放结点
        --pUBN->digitCount;  //调整位数
    }
}


//两个无符号大数相加
struct UBigNumber AddUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct UBigNumber result, *pResult = &result;
    _InitUBN(pResult);
    int iCarry = 0;  //进位，初始0
    struct Node *p1, *p2;
    p1 = pA->pTail;  //从低位开始处理
    p2 = pB->pTail;
    while(p1 != pA->pHead && p2 != pB->pHead)  //两数相同位处理
    {
        int digit = p1->digit + p2->digit + iCarry;
        iCarry = digit / 10;  //新进位
        digit %= 10;  //当前结果位
        _AppendFrontDigit(pResult, digit);  //添加至结果最高位
        p1 = p1->prev;  //准备处理前一位
        p2 = p2->prev;
    }
    while(p1 != pA->pHead)  //第一位大数剩余位处理
    {
        int digit = p1->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    while(p2 != pB->pHead)  //第二位大数剩余位处理
    {
        int digit = p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p2 = p2->prev;
    }
    if(iCarry != 0)  //最后进位处理
        _AppendFrontDigit(pResult, iCarry);
    return result;
}


//两个无符号大数相减
struct UBigNumber SubUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct UBigNumber result, *pResult = &result;
    _InitUBN(pResult);
    int iCarry = 0;  //退位，初始0
    struct Node *p1, *p2;
    p1 = pA->pTail;  //从低位开始处理
    p2 = pB->pTail;
    while(p1 != pA->pHead && p2 != pB->pHead)  //两数相同位处理
    {
        int digit = p1->digit - p2->digit - iCarry;
        iCarry = 0; //初始化
        if(digit < 0)
        {
            digit += 10;  
            iCarry = 1;  //前一位退1
        }
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
        p2 = p2->prev;
    }
    while(p1 != pA->pHead)  //最后退位处理
    {
        int digit = p1->digit - iCarry;
        iCarry = 0;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    _Normalize(pResult);
    return result;
}


//打印无符号大数
void PrintUBN(struct UBigNumber ubn)
{  //断言：至少有1位数字
    assert(ubn.digitCount > 0 && ubn.pHead->next != NULL);
    struct Node *la = ubn.pHead->next;  //头结点无数据，跳过
    while(la)
    {
        printf("%d",la->digit);
        la = la->next;
    }
}


//销毁无符号大数，释放空间
void DestroyUBN(struct UBigNumber *pUBN)
{
    while(pUBN->pHead != NULL)
    {
        struct Node *p = pUBN->pHead;  //待删除结点
        pUBN->pHead = p->next;  //尾指针前移
        free(p);  //释放结点
    }
}

处理有符号大数加减

  1. 定义的函数(与无符号相比有修改或增加的函数)

//输入有符号大数
struct UBigNumber InputUBN();

//大数绝对值比较大小
int CmpUBN(struct UBigNumber *pA, struct UBigNumber *pB);

//打印有符号大数
void PrintUBN(struct UBigNumber ubn);

  1. 函数的实现
//输入有符号大数
struct UBigNumber InputUBN()
{
    struct UBigNumber result;
    _InitUBN(&result);

    char ch;
    do
    {
        ch = getchar();
        if(ch == '-')
        {
            result.pHead->digit = '-';  //存储负号
            ch = getchar();
            break;
        }
        else
            result.pHead->digit = '+';  //存储正号
    }while(ch < '0' || ch > '9');
    while(ch >= '0' && ch <= '9')
    {
        _AppendDigit(&result, ch-'0');
        ch = getchar();
    }
    _Normalize(&result);
    return result;
}

//两个大数绝对值比较大小
int  CmpUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct Node *p1, *p2;
    //先比较位数
    if(pA->digitCount > pB->digitCount)
        return 0;  //0标记pA大于等于pB
    else
    {
        p1 = pA->pHead->next;
        p2 = pB->pHead->next;
        while(p1 != NULL)  //位数相同，只需判断p1与p2其中一个即可
        {
            if(p1 < p2)
                return 1;//1标记pA小于pB
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    return 0;  //pA与pB相等
}

//打印有符号大数
void PrintUBN(struct UBigNumber ubn)
{
    assert(ubn.digitCount > 0 && ubn.pHead->next != NULL);
    //若负数，打印负号
    if(ubn.pHead->digit == '-')
        printf("%c", ubn.pHead->digit);
    //打印数字
    struct Node *la = ubn.pHead->next;
    while(la)
    {
        printf("%d",la->digit);
        la = la->next;
    }
}
  1. 完整代码
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>


struct Node
{
    int digit;  //数字
    struct Node *next, *prev;  //前后指针
};

struct UBigNumber
{
    int digitCount;  //位数
    struct Node *pHead, *pTail;  //指向头结点和尾结点
};

//动态分配1个结点，返回结点指针
//当分配失败时，简化程序，退出运行
struct Node *_NewNode();
//表示大数用带头结点的双向链表
void _InitUBN(struct UBigNumber *pUBN);
//输入有符号大数
struct UBigNumber InputUBN();
//大数尾部添加1位数字
void _AppendDigit(struct UBigNumber *pUBN, int digit);
//大数首部添加1位数字
void _AppendFrontDigit(struct UBigNumber *pUBN, int digit);
//大数的规范表示，去除高位多余的0，至少含1位数字
void _Normalize(struct UBigNumber *pUBN);
//大数绝对值比较大小
int  CmpUBN(struct UBigNumber *pA, struct UBigNumber *pB);
//两个有符号大数相加
struct UBigNumber AddUBN(struct UBigNumber *pA, struct UBigNumber *pB);
//无符号整数相减
struct UBigNumber SubUBN(struct UBigNumber *pA, struct UBigNumber *pB);
//打印有符号大数
void PrintUBN(struct UBigNumber ubn);
//销毁有符号大数，释放空间
void DestroyUBN(struct UBigNumber *pA);


int main()
{
    struct UBigNumber A, B, C, D;
    A = InputUBN();
    B = InputUBN();
    //输入两个正数
    if(A.pHead->digit == '+' && B.pHead->digit == '+') 
    {
        if(CmpUBN(&A, &B))
        {   //A绝对值比B绝对值小
            C = AddUBN(&A, &B);
            C.pHead->digit = '+';
            D = SubUBN(&B, &A);
            D.pHead->digit = '-';
        }
        else
        {
            C = AddUBN(&A, &B);
            C.pHead->digit = '+';
            D = SubUBN(&A, &B);
            D.pHead->digit = '+';
        }

    }
    //输入第一个正数，第二个负数
    else if(A.pHead->digit == '+' && B.pHead->digit == '-')
    {
       if(CmpUBN(&A, &B))
        {   //A绝对值比B绝对值小
            C = SubUBN(&B, &A);
            C.pHead->digit = '-';
            D = AddUBN(&B, &A);
            D.pHead->digit = '+';
        }
        else
        {
            C = SubUBN(&A, &B);
            C.pHead->digit = '+';
            D = AddUBN(&A, &B);
            D.pHead->digit = '+';
        }
    }
    //输入第一个负数，第二个正数
    else if(A.pHead->digit == '-' && B.pHead->digit == '+')
    {
       if(CmpUBN(&A, &B))
        {   //A绝对值比B绝对值小
            C = SubUBN(&B, &A);
            C.pHead->digit = '+';
            D = AddUBN(&B, &A);
            D.pHead->digit = '-';
        }
        else
        {
            C = SubUBN(&A, &B);
            C.pHead->digit = '-';
            D = AddUBN(&A, &B);
            D.pHead->digit = '-';
        }
    }
    //输入第一个负数，第二个负数
    else if(A.pHead->digit == '-' && B.pHead->digit == '-')
    {
       if(CmpUBN(&A, &B))
        {   //A绝对值比B绝对值小
            C = AddUBN(&B, &A);
            C.pHead->digit = '-';
            D = SubUBN(&B, &A);
            D.pHead->digit = '+';
        }
        else
        {
            C = AddUBN(&A, &B);
            C.pHead->digit = '-';
            D = SubUBN(&A, &B);
            D.pHead->digit = '-';
        }
    }


    PrintUBN(C);

    printf("\n");

    PrintUBN(D);

    DestroyUBN(&A);
    DestroyUBN(&B);
    DestroyUBN(&C);
    DestroyUBN(&D);

    return 0;
}


//动态分配1个结点，返回结点指针
//当分配失败时，简化程序，退出运行
struct Node *_NewNode()
{
    struct Node *p;
    p = (struct Node*)malloc(sizeof(struct Node));
    if(p == NULL)
    {
        printf("Error:out of memory\n");
        exit(-1);
    }
    return p;

}


//表示大数用带头结点的双向链表
void _InitUBN(struct UBigNumber *pUBN)
{
    struct Node *p = _NewNode();
    pUBN->pHead = pUBN->pTail = p;
    p->next = p->prev = NULL;
    pUBN->digitCount = 0;
}


//输入有符号大数
struct UBigNumber InputUBN()
{
    struct UBigNumber result;
    _InitUBN(&result);

    char ch;
    do
    {
        ch = getchar();
        if(ch == '-')
        {
            result.pHead->digit = '-';  //存储负号
            ch = getchar();
            break;
        }
        else
            result.pHead->digit = '+';  //存储正号
    }while(ch < '0' || ch > '9');
    while(ch >= '0' && ch <= '9')
    {
        _AppendDigit(&result, ch-'0');
        ch = getchar();
    }
    _Normalize(&result);
    return result;
}


//大数尾部添加1位数字
void _AppendDigit(struct UBigNumber *pUBN, int digit)
{
    if(pUBN->digitCount == 1 && pUBN->pTail->digit == 0)
    {
        pUBN->pTail->digit = digit;
        return;
    }
    struct Node *p = _NewNode();
    p->digit = digit;
    p->next = NULL;
    p->prev = pUBN->pTail;
    pUBN->pTail->next = p;
    pUBN->pTail = p;
    ++pUBN->digitCount;
}


//大数首部添加1位数字
void _AppendFrontDigit(struct UBigNumber *pUBN, int digit)
{
    struct Node *p = _NewNode();
    p->digit = digit;
    p->next = pUBN->pHead->next;
    if(p->next != NULL)
        p->next->prev = p;
    p->prev = pUBN->pHead;
    pUBN->pHead->next = p;
    if(pUBN->pTail == pUBN->pHead)
        pUBN->pTail = p;
    ++pUBN->digitCount;
}


//大数的规范表示，去除高位多余的0，至少含1位数字
void _Normalize(struct UBigNumber *pUBN)
{
    if(pUBN->digitCount == 0)
        _AppendDigit(pUBN, 0);
    while(pUBN->digitCount > 1 && pUBN->pHead->next->digit == 0)
    {
        struct Node *p;
        p = pUBN->pHead->next;
        pUBN->pHead->next = p->next;
        p->next->prev = pUBN->pHead;
        free(p);
        --pUBN->digitCount;
    }
}


//两个大数绝对值比较大小
int  CmpUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct Node *p1, *p2;
    //先比较位数
    if(pA->digitCount > pB->digitCount)
        return 0;  //0标记pA大于等于pB
    else
    {
        p1 = pA->pHead->next;
        p2 = pB->pHead->next;
        while(p1 != NULL)  //位数相同，只需判断p1与p2其中一个即可
        {
            if(p1 < p2)
                return 1;//1标记pA小于pB
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    return 0;  //pA与pB相等
}


//两个大数相加
struct UBigNumber AddUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct UBigNumber result, *pResult = &result;
    _InitUBN(pResult);
    int iCarry = 0;
    struct Node *p1, *p2;
    p1 = pA->pTail;
    p2 = pB->pTail;
    while(p1 != pA->pHead && p2 != pB->pHead)
    {
        int digit = p1->digit + p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
        p2 = p2->prev;
    }
    while(p1 != pA->pHead)
    {
        int digit = p1->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    while(p2 != pB->pHead)
    {
        int digit = p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p2 = p2->prev;
    }
    if(iCarry != 0)
        _AppendFrontDigit(pResult, iCarry);
    return result;
}


//两个大数相减
struct UBigNumber SubUBN(struct UBigNumber *pA, struct UBigNumber *pB)
{
    struct UBigNumber result, *pResult = &result;
    _InitUBN(pResult);
    int iCarry = 0;
    struct Node *p1, *p2;
    p1 = pA->pTail;
    p2 = pB->pTail;
    while(p1 != pA->pHead && p2 != pB->pHead)
    {
        int digit = p1->digit - p2->digit - iCarry;
        iCarry = 0;
        if(digit < 0)
        {
            digit += 10;
            iCarry = 1;
        }
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
        p2 = p2->prev;
    }
    while(p1 != pA->pHead)
    {
        int digit = p1->digit - iCarry;
        iCarry = 0;
        _AppendFrontDigit(pResult, digit);
        p1 = p1->prev;
    }
    _Normalize(pResult);
    while(p2 != pB->pHead)
    {
        int digit = p2->digit + iCarry;
        iCarry = digit / 10;
        digit %= 10;
        _AppendFrontDigit(pResult, digit);
        p2 = p2->prev;
    }
    if(iCarry != 0)
        _AppendFrontDigit(pResult, iCarry);
    return result;
}


//打印有符号大数
void PrintUBN(struct UBigNumber ubn)
{
    assert(ubn.digitCount > 0 && ubn.pHead->next != NULL);
    //若负数，打印负号
    if(ubn.pHead->digit == '-')
        printf("%c", ubn.pHead->digit);
    //打印数字
    struct Node *la = ubn.pHead->next;
    while(la)
    {
        printf("%d",la->digit);
        la = la->next;
    }
}


//销毁大数，释放空间
void DestroyUBN(struct UBigNumber *pUBN)
{
    while(pUBN->pHead != NULL)
    {
        struct Node *p = pUBN->pHead;
        pUBN->pHead = p->next;
        free(p);
    }
}
上一篇：Leetcode剑指 Offer 43. 1～n 整数中 1 出现的次数


下一篇：Prime Path POJ-3126