题目：设计一个实现任意长的整数的加法运算的演示程序

一、需求分析

本演示程序中，利用双向循环链表来实现长整数的储存，每个节点含一个整型变量。输入和输出形式按照中国对于长整数的表示习惯，每四位一组，组间用逗号隔开；其中输入的两个长整数用 ';' (英语输入法)结尾，允许逗号位置错误，并在输入非法字符是提示错误。

2.测试数据

（1）0;0;应输出“0”。
（2）-2345,6789;-7654,3211;应输出“-1,0000,0000”
（3）-9999,9999;1,0000,0000,0000;应输出“9999,0000,0001”
（4）1,0001,0001;-1,0001,0001;应输出“0”
（5）1,0001,0001;-1,0001,0000;应输出“1”
（6）-9999,9999,9999;-9999,9999,9999;应输出“-1,9999,9999,9998”
（7）1,0000,9999,9999;1;应输出“1,0001,0000,0000”

二、概要设计

1.数据结构

为实现上述程序功能，采用双向循环链表来储存长整数。
双向循环链表的储存结构:

typedef struct node{
    int info;
    struct node *prior,*next;
}DLink;

利用头结点的数据域符号来表示长整数的符号，大小表示长整数长度。
2.使用函数
DLink *Dcreat()
操作结果：初始化储存长整数的双向循环链表
DLink *addition(DLink *a, DLink *b)
操作结果：实现同符号长整数的加法操作
DLink *subtraction(DLink *a, DLink *b)
操作结果：实现异号号长整数的加法操作
void printDlink(DLink *head)
操作结果：实现长整数的中国表示方法输出
void main()
操作结果：主函数，调用以上函数进行加法运算

三、详细设计

1.读入数据初始化双向循环链表函数

采用getchar()从屏幕上读取字符，定义flag变量表示输入是否合法，对于不合法的输入将链表头结点数据域(head->info)置为0；对于正规输入构成链表的头结点数据域为:长整数长度×符号，长整数长度（len）在循环读入字符时确定，将读入的','以及'-'外每一位字符转化为int型，存在链表节点的数据域中，实现如下:

DLink *Dcreat()
{
    DLink *head,*p,*last;
    int flag = 0; //输入是否合法
    char c;
    int num;
    int len = 0;//长整数长度
    head=(DLink *)malloc(sizeof(DLink));
    head->next = NULL;
    head->prior = NULL;
    head->info = 1;//起始符号位为1
    last = head;
    while((c=getchar())!=';')
    {
        if(c=='-')
        {
            head->info = -1;//符号位
            continue;
        }
        if(c==',')
        {
            continue;
        }
        num = c - '0';
        if(num > 9 || num <0){
            flag = 1; //输入不合法
            break;
        }
        p = (DLink*)malloc(sizeof(DLink));
        p->info = num;
        len++;
        if(head->next == NULL)
        {
            head->next = p;
            p->prior = head;
            last = p;
        }
        else
        {
            p->prior = last;
            last->next = p;
            last = p;
        }
    }
    if(flag == 0)
    {
        last->next = NULL;
        head->prior = last;
        head->info = (head->info)*len; 
    }
    else
    {
       head->info = 0;
    }
    return head;
}

2. 加法函数(同号相加)

读取两个链表头结点数据域的数值，判断符号和整数长度，较长的整数作为被加数（upper），从被加数的尾节点（个位）开始向前遍历，两个链表对应节点的数据域数值相加，有进位(carry=1)情况前一节点运算时要加上进位值，判断最高位有进位的时候在头结点与其之间插入新的节点，并更新头结点数据域数值，实现如下:

DLink *addition(DLink *a, DLink *b)
{
    int symbol = abs(a->info)/(a->info);
    int len_a = abs(a->info);
    int len_b = abs(b->info);
    DLink *upper,*lower;
    if(len_a > len_b)
    {
        upper = a;
        lower = b;
    }
    else
    {
        upper = b;
        lower = a;
    }
    int len_up = abs(upper->info);
    int len_low = abs(lower->info);
    int cnt = 0;
    int carry = 0; //进位            
    while (cnt != len_up)
    {
        upper = upper->prior; //个位开始
        lower = lower->prior;
        if (cnt < len_low)
        {
            upper->info = upper->info + lower->info + carry;
        }
        else
        {
            upper->info = upper->info + carry;
        }
        carry = 0;
        if (upper->info >= 10) 
        {
            upper->info -= 10, carry = 1;   
        }
        ++cnt;
    }
    if (carry)
    {
        DLink *p;
        p = (DLink *)malloc(sizeof(DLink));
        p->info = carry;
        p->prior = upper->prior;
        upper->prior->next = p;
        p->next = upper;
        upper->prior = p;
        upper = p;
        ++len_up;
    }
    upper = upper->prior;
    upper->info = symbol*len_up;
    return upper;
}

3. 减法函数(异号相加)

减法函数与加法函数原理基本相同，不同点主要为：需要找到两个数中绝对值较大的数作为被减数（upper），通过条件语句和对两链表从头节点向后遍历比较各节点元素来实现，因为是绝对值较大数减去绝对值较小数（lower），最高位不会产生借位操作，在向前遍历进行运算的过程中，节点有借位情况(carry=1)情况时，前一节点运算时要减去借位值，实现如下：

DLink *subtraction(DLink *a, DLink *b)
{
    int len_a = abs(a->info);
    int len_b = abs(b->info);
    DLink *upper, *lower;       
    if(len_a > len_b)
    {
        upper = a;
        lower = b;
    }
    else if(len_a < len_b)
    {
        upper = b;
        lower = a;
    }
    else
    {
        DLink *tmp1 = a, *tmp2 = b;
        int cnt = 0;
        tmp1 = tmp1->next;
        tmp2 = tmp2->next;
        while (cnt != len_a)
        {
            if(tmp1->info > tmp2->info)
            {
                upper = a;
                lower = b;
                break;
            }
            else if(tmp1->info < tmp2->info)
            {
                upper = b;
                lower = a;
                break;
            }
            tmp1 = tmp1->next;
            tmp2 = tmp2->next;
            ++cnt;
        }
        if(cnt == len_a)
        { 
            upper = a;
            lower = b;
        }
    }
    int len_up = abs(upper->info);          
    int len_low = abs(lower->info);           
    int symbol = abs(upper->info)/(upper->info);
    int cnt = 0;
    int carry = 0;  // 借位
    while (cnt != len_up)
    {
        upper = upper->prior;
        lower = lower->prior;
        if (cnt < len_low)
        {
           upper->info = upper->info - lower->info - carry; 
        }
        else
        {
            upper->info = upper->info - carry;
        }
        carry = 0;
        if (upper->info < 0)
        {
          upper->info += 10, carry = 1;  
        }
        ++cnt;
    }
    upper = upper->prior;       
    upper->info = symbol*len_up;      
    return upper;
}

4. 输出

根据头结点的符号确定结果是否以’-’开始，由于减法函数处理后从头结点到存储有效数字的节点间可能会有0值，需要从头节点向后循环判断是否为0并输出（同时考虑结果仅是0的情况），在循环过程中计算还未输出的位数（len），能被4整除时则输出’,’达到输出中国表示习惯长整数的目的，实现如下:

void printDlink(DLink *head)
{
    DLink *p;
    p = head;
    int len = abs(p->info);
    int cnt = 1;
    if(p->info < 0)
    {
        printf("-");
    }
    p = p->next;
    while(p->info == 0 && p->next != NULL)
    {
        p = p->next;
        --len;
    }
    while(len)
    {
        printf("%d", p->info);
        p = p->next;
        --len;
        if(!(len%4) && len) putchar(',');
    }
}

5. 主函数

提示输入格式，并通过所构成链表头结点的数据判断输入是否合法（不合法进行提示），对合法输入判断采用函数种类，计算输出，实现如下:

void main()
{   
    printf("请输入需要计算的两个长整数，以分号隔开(如：-9999,9999;1,0000,0000)\n");
    DLink *a;
    a = Dcreat();
    if(a->info == 0)
    {
        printf("invalid input");
    }
    else
    {
        DLink *b;
        b = Dcreat();
        if(b->info == 0)
        {
            printf("invalid input");
        }
        else
        {
            DLink *c;
            if((a->info)*(b->info)<0)
                {
                    c = subtraction(a,b);
                }
            else
                {
                    c = addition(a,b);
                }
            printDlink(c);
        }
    }
}

6. 程序的层次结构

层次结构.png

五、用户手册

本程序的运行环境为DOS操作系统，执行文件为：longadd.exe
进入程序按提示操作，注意两数字间和结束用分号（英文输入法）隔开
输入后按回车符即显示结果

六、测试结果

测试.png

数据结构：长整数的四则运算