用链表实现的超大数阶乘运算

代码风格很滥,请多多包涵,这个程序主要是为了练习链表的用法,因此没有考虑到效率的问题,里面涉及了超大数的存储,加法,乘法,最后才复合成了阶乘,希望对大家有一点用

 

 

#include <stdio.h>
#include <stdlib.h>
typedef struct record
{
    char n ;
    struct record*next ;
}
node,*pnode;

pnode inputint()   //input record
{
    pnode p,q=NULL ;
    char c ;
    while((c=getchar())!=’\n’)
    {
        p=(pnode)malloc(sizeof(node));
        p->n=c  ;
        p->next=q ;
        q=p ;
    }
    return p ;
}

 

void destroy(pnode p)    //destroy list
{
    pnode q=p ;
    while(p)
    {
        p=p->next ;
        q->n=’0′ ;
        free(q);
        q=p ;
    }
}

 

pnode insertint(pnode p,int n)   //insert record
{
   
    pnode q=(pnode)malloc(sizeof(node));
    q->n=n+’0′;
    q->next=NULL ;
    if(p)p->next=q ;
    p=q ;
    return p ;
}
pnode plus(pnode p1,pnode p2)    //two long numbers plus
{
    int s,i=0 ;
    pnode p=(pnode)malloc(sizeof(node)),q,m1=p,m2 ;
    if(!p1&&!p2)return NULL ;
    while(p1&&p2)
    {
        s=(p1->n-’0′+p2->n-’0′+i)%10 ;
        i=(p1->n-’0′+p2->n-’0′+i)/10 ;
        p=insertint(p,s);
        p1=p1->next,p2=p2->next ;
    }
    q=p1?p1:p2 ;
    while(q)
    {
        s=(q->n-’0′+i)%10  ;
        i=(q->n-’0′+i)/10 ;
        p=insertint(p,s);
        q=q->next ;
    }
    if(i)p=insertint(p,i);
    m2=m1->next ;
    free(m1);
    return m2 ;
}

void printint(pnode p)     //output record
{
 pnode a=p,b=a->next,temp=NULL;
 while(a)
 {
  a->next=temp;
  temp=a;
  a=b;
  if(b)b=b->next;
 }
 while(temp)
 {
  printf(“%c”,temp->n);
  temp=temp->next;
 }
 printf(“\n”);
}

 

pnode insertzero(pnode p,int n)    //insert zero
{
    int i=0 ;
    pnode q ;
    while(i<n)
    {
        q=(pnode)malloc(sizeof(node));
        q->n=’0′;
        q->next=p ;
        p=q ;
        i++;
    }
    return p ;
}

pnode copylist(pnode p)     //copy list
{
    pnode q=(pnode)malloc(sizeof(node)),r1=q,r2 ;
    q->next=NULL ;
    while(p)
    {
        q=insertint(q,p->n-’0′);
        p=p->next ;
       
    }
    r2=r1->next ;
    free(r1);
    return r2 ;
}

pnode multiply(pnode p,int n,int j)    //two long numbers multiply
{
    int i=0,s ;
    pnode q=(pnode)malloc(sizeof(node)),s1=q,s2 ;
    q->next=NULL ;
    while(p)
    {
        s=(n*(p->n-’0′)+i)%10 ;
        i=(n*(p->n-’0′)+i)/10 ;
        q=insertint(q,s);
        p=p->next ;
    }
    if(i)q=insertint(q,i);
    s2=s1->next ;
    free(s1);
    return insertzero(s2,j);
}

pnode fun(pnode p1,pnode p2)   //integrate calculate
{
    pnode q1,q2=NULL,s=NULL ;
    int i=0 ;
    while(p1&&p2)
    {
        q1=multiply(p1,p2->n-’0′,i);
        s=plus(q1,q2);
 destroy(q2);
        destroy(q1);
        q2=s ;
        p2=p2->next ;
        i++;
    }
    return s ;
}

pnode check(pnode p)    //check whether has zero before head
{
    pnode q=NULL,r=p ;
    if(!p)return NULL ;
    while(p->next)
    {
        q=p ;
        p=p->next ;
    }
    if(q&&p->n==’0′)
    {
        q->next=NULL ;
        free(p);
        return r ;
    }
    else
    {
        if(p->n!=’0′)return r ;
        else return NULL ;
    }
}

pnode f(pnode p)    //return number minus one
{
    pnode q=p ;
    while(q)
    {
        if(q->n>’0′)
        {
            q->n–;
            return check(p);
        }
        else
        {
            q->n=’9′ ;
            q=q->next ;
        }
    }
    return check(p);
}
int main()     
{
    pnode p,q,r ;
    system(“cls”);
    printf(“please input a number:”);
    p=inputint();
    q=copylist(p);
    while(p)
    {
        p=f(p);
 if(!p)break ;
 r=fun(q,p);
 destroy(q);
        q=r ;
    }
    printint(q);
    destroy(q);
    return 0;
}