C趣味編程百例(33)超長正整數(shù)的加法

99.超長正整數(shù)的加法
     請設計一個算法來完成兩個超長正整數(shù)的加法。
    *問題分析與算法設計
     首先要設計一種數(shù)據(jù)結構來表示一個超長的正整數(shù)，然后才能夠設計算法。
     首先我們采用一個帶有表頭結點的環(huán)形鏈來表示一個非負的超大整數(shù)，如果從低位開始為每 個數(shù)字編號，則第一位到第四位、第五位到第八位...的每四位組成的數(shù)字，依次放在鏈表的第一個、第二個、...結點中，不足4位的位存放在鏈表的最后一個結點中，表頭結點的值規(guī)定為-1。例如：
     大整數(shù)“587890987654321”可用如下的帶表頭結點head的鏈表表示：
    按照此數(shù)據(jù)結構，可以從兩個表頭結點開始，順序依次對應相加，求出所需要的進位后代入下面的運算。具體的實現(xiàn)算法請見程序中的注釋。
    *程序與程序注釋
    #include
    #include
    #define HUNTHOU 10000
    typedef struct node{ int data;
     struct node *next;
     }NODE; /*定義鏈表結構*/
    NODE *insert_after(NODE *u,int num); /*在u結點后插入一個新的NODE，其值為num*/
    NODE *addint(NODE *p,NODE *q); /*完成加法操作返回指向*p+*q結果的指針*/
    void printint(NODE *s);
    NODE *inputint(void);
    void main()
    {
     NODE *s1,*s2,*s;
     NODE *inputint(), *addint(), *insert_after();
     printf("Enter S1= ");
     s1=inputint(); /*輸入被加數(shù)*/
     printf("Enter S2= ");
     s2=inputint(); /*輸入加數(shù)*/
     printf(" S1="); printint(s1); putchar('\n'); /*顯示被加數(shù)*/
     printf(" S2="); printint(s2); putchar('\n'); /*顯示加數(shù)*/
     s=addint(s1,s2); /*求和*/
     printf("S1+S2="); printint(s); putchar('\n'); /*輸出結果*/
    }
    NODE *insert_after(NODE *u,int num)
    {
     NODE *v;
     v=(NODE *)malloc(sizeof(NODE)); /*申請一個NODE*/
     v->data=num; /*賦值*/
     u->next=v; /*在u結點后插入一個NODE*/
     return v;
    }
    NODE *addint(NODE *p,NODE *q) /*完成加法操作返回指向*p+*q結果的指針*/
    {
     NODE *pp,*qq,*r,*s,*t;
     int total,number,carry;
     pp=p->next; qq=q->next;
     s=(NODE *)malloc(sizeof(NODE)); /*建立存放和的鏈表表頭*/
     s->data=-1;
     t=s; carry=0; /*carry:進位*/
     while(pp->data!=-1&&qq->data!=-1) /*均不是表頭*/
     {
     total=pp->data+qq->data+carry; /*對應位與前次的進位求和*/
     number=total%HUNTHOU; /*求出存入鏈中部分的數(shù)值 */
     carry=total/HUNTHOU; /*算出進位*/
     t=insert_after(t,number); /*將部分和存入s向的鏈中*/
     pp=pp->next; /*分別取后面的加數(shù)*/
     qq=qq->next;
     }
     r=(pp->data!=-1)?pp:qq; /*取尚未自理完畢的鏈指針*/
     while(r->data!=-1) /*處理加數(shù)中較大的數(shù)*/
     {
     total=r->data+carry; /*與進位相加*/
     number=total%HUNTHOU; /*求出存入鏈中部分的數(shù)值*/
     carry=total/HUNTHOU; /*算出進位*/
     t=insert_after(t,number); /*將部分和存入s指向的鏈中*/
     r=r->next; /*取后面的值*/
     }
     if(carry) t=insert_after(t,1); /*處理最后一次進位*/
     t->next=s; /*完成和的鏈表*/
     return s; /*返回指向和的結構指針*/
    }
    NODE *inputint(void) /*輸入超長正整數(shù)*/
    {
     NODE *s,*ps,*qs;
     struct number {int num;
     struct number *np;
     }*p,*q;
     int i,j,k;
     long sum;
     char c;
     p=NULL; /*指向輸入的整數(shù)，鏈道為整數(shù)的最低的個位，鏈尾為整數(shù)的位*/
     while((c=getchar())!='\n') /*輸入整數(shù)，按字符接收數(shù)字*/
     if(c>='0'&&c<='9') /*若為數(shù)字則存入*/
     {
     q=(struct number *)malloc(sizeof(struct number)); /*申請空間*/
     q->num=c-'0'; /*存入一位整數(shù)*/
     q->np=p; /*建立指針*/
     p=q;
     }
     s=(NODE *)malloc(sizeof(NODE));
     s->data=-1; /*建立表求超長正整數(shù)的鏈頭*/
     ps=s;
     while(p!=NULL) /*將接收的臨時數(shù)據(jù)鏈中的數(shù)據(jù)轉換為所要求的標準形式*/
     {
     sum=0;i=0;k=1;
     while(i<4&&p!=NULL) /*取出低四位*/
     {
     sum=sum+k*(p->num);
     i++; p=p->np; k=k*10;
     }
     qs=(NODE *)malloc(sizeof(NODE)); /*申請空間*/
     qs->data=sum; /*賦值，建立鏈表*/
     ps->next=qs;
     ps=qs;
     }
     ps->next=s;
     return s;
    }
    void printint(NODE *s)
    {
     if(s->next->data!=-1) /*若不是表頭，則輸出*/
     {
     printint(s->next); /*遞歸輸出*/
     if(s->next->next->data==-1)
     printf("%d",s->next->data);
     else{
     int i,k=HUNTHOU;
     for(i=1;i<=4;i++,k/=10)
     putchar('0'+s->next->data%(k)/(k/10));
     }
     }
    }