longint .c

数据结构试验

#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 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()
{
    int i, k ;
    int dex = 0, flag = 0 ;
    char ch ;
    LinkList num[3];
    
    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) {      /*  两串数字获取完毕  */
                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 ;        /*  换字符串索引  */
        }
    }
    return 0;
}