长整数.c

1. 本程序实现计算任意长的整数的四则运算. 以用户和计算机对话的方式,先后输入数字的最多位数,然后程序就计算并显示出这两个数的运算. 2. 利用双向循环链表现实长整数的存储,每个结点含一个整形变

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

typedef struct Node{
    int data ;          // 数据域 
    struct Node *prior; // 前驱 
    struct Node *next ; // 后继
}LNode, *LinkList;
 
void InitLink( LinkList *L )    // 初始化表头 
{
	*L = (LinkList) malloc(sizeof(LNode));
	(*L)->prior = *L ;
	(*L)->next = *L ;
}

void Delete( LinkList L )   // 清空头结点外的链表元素 
{
    LinkList p = L->next; 
    LinkList tmp;
    
    while (p != L){
        tmp = p;
        p = p->next;
        free(tmp);
    }
    L->next = L;
    L->prior = L;
}

void Append( LinkList L, int s )    // 链表尾部添加元素 
{
    LinkList p = L;
    LinkList tmp = (LinkList)malloc(sizeof(LNode));
    tmp->next = L ;
    tmp->data = s ;
    
    tmp->prior = L->prior ; // 新节点前驱指向链表最后元素 
    L->prior->next = tmp ;  // 连接新节点到链表尾部 
    L->prior = tmp;         // 更新链表头的前驱 
}

void Output( LinkList L )   // 正向输出一个长整数 
{
    LinkList p = L->next ;
    
    if (p == L) {
        printf("0");
        return ;
    }
    
    if (L->data == -1) printf("-");
    printf("%d", p->data);
    p = p->next;
    while (p != L){
        printf(",%04d", p->data);
        p = p->next;
    }
}

void Output2( LinkList L )  // 逆向输出一个长整数 
{
    LinkList p = L->prior ;
    
    if (p == L) {
        printf("0");
        return ;
    }
    
    if (L->data == -1) printf("-");
    printf("%d", p->data );
    p = p->prior;
    while (p != L){
        printf(",%04d", p->data );
        p = p->prior;
    }
}

void Sum_Linknum( LinkList A, LinkList B, LinkList C )  // 同号大数求和 
{
    LinkList a = A->prior;
    LinkList b = B->prior;
    
    int sum;
    int carry = 0;
    
    C->data = 1;
    if (A->data < 0) C->data = -1;
    
    while (a != A && b != B){   // 公共长度相加 
        sum = a->data + b->data + carry ;
        carry = sum/10000;
        Append( C, sum%10000 );
        a = a->prior;
        b = b->prior;
    }
    
    while (a != A){             // A串有余 
        sum = a->data + carry ;
        carry = sum/10000 ;
        Append( C, sum%10000 );
        a = a->prior ;
    }
    
    while (b != B){             // B串有余 
        sum = b->data + carry ;
        carry = sum/10000 ;
        Append( C, sum%10000 );
        b = b->prior ;
    }
    
    if (carry) Append( C, carry );  // 处理最后的进位     
}

void DelZero(LinkList L)  // 删除欲反向输出的整数结果串里的无效0 
{
    LinkList p = L;
    LinkList q;
    while (p->prior != L) {      // 遍历C串
        if (p->prior->data != 0) // 直到首个有效位 
            break;
        else {                   // 删除无效0 
            q = p->prior ;       // 记录欲删除 节点   
            p->prior = q->prior; // 链接跳过 此节点 
            q->prior->next = p ; // 重置后继 
            free(q);             // 释放空间 
        }
    }
}

void Sub_Linknum( LinkList A, LinkList B, LinkList C ) // 求差
{
    LinkList HA = A;        // 指向绝对值较大串 
    LinkList HB = B;        // 指向小串 
    LinkList a = HA->prior; // 遍历大串 
    LinkList b = HB->prior; // 遍历小串 
    
    int sub; 
    int borrow = 0;
    int flag = 0;   // 是否 A < B 
    C->data = 1;    // 假定所得 A - B 符号为正 
    
    while (a != HA && b != HB){   // 比较 A, B串大小
        if (a->data < b->data) flag = 1;
        if (a->data > b->data) flag = 0;
        a = a->prior;
        b = b->prior;
    }
    
    if (b != HB) flag = 1;   // B串长于A串, A < B 
    if (a != HA) flag = 0;   // A串长于B串, A > B 
    
    if (flag == 1){          // A < B 重置头指针指向 
        HA = B;
        HB = A;
        C->data = -1;        // 设置负号 
    }
    
    a = HA->prior;      // 重置 
    b = HB->prior;      // 以开始做减法操作 
    while (b != HB) {   // 减掉绝对值较小数 
        sub = a->data - borrow - b->data; 
        if (sub >= 0)
            borrow = 0;
        else {
            borrow = 1;
            sub += 10000;
        }
        Append( C, sub );
        a = a->prior;
        b = b->prior;
    }
    
    while (a != HA) {   // 处理剩余的绝对值较大数  
        sub = a->data - borrow; 
        if (sub >= 0)
            borrow = 0;
        else {
            borrow = 1;
            sub += 10000;
        }
        Append( C, sub );
        a = a->prior;
    }
    
    DelZero ( C ); // 去掉前导0 
}

int main()
{
   // freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
    int i, k ;
    int dex = 0, flag = 0 ;
    char ch ;
    LinkList num[3];
    printf("if you want exit,please input  1;0\n");
    
    for (i = 0; i < 3; ++i)
        InitLink( &num[i] );
    
    while (scanf("%d", &k) != EOF)
    {
        if (flag == 0) { // 未确定数字符号 
            if (k < 0) {
                num[dex]->data = -1;    // 设置符号位为负 
                k *= -1;                // 确定负数后依然以正数存储 
            } else if (k > 0)
                num[dex]->data = 1;     // 设置符号位为负 
            else num[dex]->data = 0; 
            flag = 1;                   // 符号已确定
        }
        ch = getchar();          // 获取 ',' 
        Append( num[dex], k );   // 链表追加元素 
        if (ch != ',') {         // 非','字符, 当前串数字获取完毕 
            if (dex == 1) {      // 两串数字获取完毕 
                   if (num[0]->data == 1 && num[1]->data == 0)  // 程序结束 
                    break;



                Output(num[0]);
                printf(" + ") ;
                Output(num[1]);
                printf(" = ") ;
                if (num[0]->data == num[1]->data)   // 同号 
                    Sum_Linknum( num[0], num[1], num[2] );
                else if (num[0]->data > 0)
                    Sub_Linknum( num[0], num[1], num[2] );
                else  
                    Sub_Linknum( num[1], num[0], num[2] );
                Output2( num[2] );
                puts("");
                for (i = 0; i < 3; ++i) // 清空链表 
                    Delete(num[i]);
            }
            flag = 0 ;          // 重新或许符号 
            dex = !dex ;        // 换字符串索引 
        }
    }
    system("pause");
    return 0;
}