学步园

        翻出一段大二时写的代码，大数运算，包括四则，阶乘，乘方。大数的数据结构是链表，每个节点存4位数，所以理论上可计算任意大的整数。

        刚刚测试了一下，在GCC 4.2下可以正常编译运行，顿时内牛满面（VC 6.0下写的代码）。在此贴上源代码。

#include<stdio.h><br /> #include<stdlib.h><br /> typedef int ElemType;<br /> typedef struct NodeType<br /> {<br /> ElemType data;<br /> NodeType *prior;<br /> NodeType *next;<br /> }NodeType,*LinkType;<br /> bool MakeNode(LinkType &p,ElemType e)<br /> {<br /> p=(LinkType)malloc(sizeof(NodeType));<br /> if(!p) return false;<br /> p->data=e;<br /> p->prior=NULL;<br /> p->next=NULL;<br /> return true;<br /> }<br /> typedef struct<br /> {<br /> LinkType head;<br /> int size;<br /> }OrderedList;<br /> bool InitList(OrderedList &L)<br /> {<br /> if(MakeNode(L.head,0))<br /> {<br /> L.size=0;<br /> return true;<br /> }<br /> else<br /> {<br /> L.head=NULL;<br /> return false;<br /> }<br /> }<br /> void DestroyList(OrderedList &L)<br /> {<br /> LinkType p,q;<br /> p=L.head;<br /> do{<br /> q=p;<br /> if(L.size) p=p->next;<br /> free(q);<br /> }while(L.size--);<br /> L.head=NULL;<br /> }<br /> int GetLength(OrderedList &L)<br /> {<br /> LinkType p;<br /> int i;<br /> i=0;<br /> p=L.head;<br /> do{<br /> p=p->next;<br /> i++;<br /> }while(p!=L.head);<br /> i--;<br /> return i;<br /> }<br /> void AddNodeTail(OrderedList &L,LinkType p)<br /> {<br /> if(!L.size)<br /> {<br /> L.head->next=p;<br /> L.head->prior=p;<br /> p->prior=L.head;<br /> }<br /> else<br /> {<br /> p->prior=L.head->prior;<br /> L.head->prior->next=p;<br /> L.head->prior=p;<br /> }<br /> p->next=L.head;<br /> L.size++;<br /> }<br /> void AddNodeHead(OrderedList &L,LinkType p)<br /> {<br /> if(L.size)<br /> {<br /> p->next=L.head->next;<br /> L.head->next->prior=p;<br /> }<br /> else<br /> {<br /> p->next=L.head;<br /> L.head->prior=p;<br /> }<br /> p->prior=L.head;<br /> L.head->next=p;<br /> L.size++;<br /> }<br /> void Delete0(OrderedList &L)<br /> {<br /> LinkType p,q;<br /> p=L.head->prior;<br /> while(!p->data&&L.size>1)<br /> {<br /> L.head->prior=p->prior;<br /> p->prior->next=L.head;<br /> L.size--;<br /> q=p;<br /> p=p->prior;<br /> free(q);<br /> }<br /> }<br /> bool CompareList(OrderedList &L1,OrderedList &L2)<br /> {<br /> LinkType p1,p2;<br /> int i;<br /> Delete0(L1);<br /> Delete0(L2);<br /> if(L1.size>L2.size) return true;<br /> else if(L1.size<L2.size) return false;<br /> else<br /> {<br /> p1=L1.head;<br /> p2=L2.head;<br /> for(i=1;i<=L1.size;i++)<br /> {<br /> p1=p1->prior;<br /> p2=p2->prior;<br /> if(p1->data>p2->data) return true;<br /> else if(p1->data<p2->data) return false;<br /> }<br /> return true;<br /> }<br /> }<br /> bool CopyList(OrderedList L1,OrderedList &L2)<br /> {<br /> int i;<br /> LinkType p1,p2,q1,q2;<br /> p1=L1.head;<br /> p2=L2.head;<br /> for(i=0;i<=L1.size;i++)<br /> {<br /> p2->data=p1->data;<br /> p1=p1->next;<br /> if(i<L1.size&&(!L2.size||p2->next==L2.head))<br /> {<br /> p2=NULL;<br /> if(MakeNode(p2,0)) AddNodeTail(L2,p2);<br /> else return false;<br /> }<br /> else p2=p2->next;<br /> }<br /> q1=p2->prior;<br /> while(L2.size>L1.size)<br /> {<br /> q2=p2;<br /> p2=p2->next;<br /> free(q2);<br /> L2.size--;<br /> if(L2.size==L1.size)<br /> {<br /> q1->next=L2.head;<br /> L2.head->prior=q1;<br /> }<br /> }<br /> return true;<br /> }<br /> bool Add(OrderedList &L1,OrderedList &L2,OrderedList &SumList)<br /> {<br /> LinkType pSum,p1,p2;<br /> int co,t;<br /> if(!InitList(SumList)) return false;<br /> Delete0(L1);<br /> Delete0(L2);<br /> co=0;<br /> p1=L1.head->next;<br /> p2=L2.head->next;<br /> while(p1!=L1.head&&p2!=L2.head)<br /> if(MakeNode(pSum,0))<br /> {<br /> AddNodeTail(SumList,pSum);<br /> t=p1->data+p2->data+co;<br /> pSum->data=t%10000;<br /> co=t/10000;<br /> pSum=NULL;<br /> p1=p1->next;<br /> p2=p2->next;<br /> }<br /> else return false;<br /> while(p1!=L1.head)<br /> if(MakeNode(pSum,0))<br /> {<br /> t=p1->data+co;<br /> pSum->data=t%10000;<br /> co=t/10000;<br /> AddNodeTail(SumList,pSum);<br /> pSum=NULL;<br /> p1=p1->next;<br /> }<br /> else return false;<br /> while(p2!=L2.head)<br /> if(MakeNode(pSum,0))<br /> {<br /> t=p2->data+co;<br /> pSum->data=t%10000;<br /> co=t/10000;<br /> AddNodeTail(SumList,pSum);<br /> pSum=NULL;<br /> p2=p2->next;<br /> }<br /> else return false;<br /> if(co)<br /> if(MakeNode(pSum,co))<br /> {<br /> AddNodeTail(SumList,pSum);<br /> pSum=NULL;<br /> }<br /> else return false;<br /> Delete0(SumList);<br /> return true;<br /> }<br /> bool Sub(OrderedList &L1,OrderedList &L2,OrderedList &SubList)<br /> {<br /> LinkType pSub,p1,p2;<br /> int co,t;<br /> if(!InitList(SubList)) return false;<br /> Delete0(L1);<br /> Delete0(L2);<br /> p1=L1.head->next;<br /> p2=L2.head->next;<br /> co=0;<br /> while(p1!=L1.head&&p2!=L2.head)<br /> if(MakeNode(pSub,0))<br /> {<br /> AddNodeTail(SubList,pSub);<br /> t=p1->data-p2->data+co;<br /> pSub->data=(t+10000)%10000;<br /> co=t<0?-1:0;<br /> pSub=NULL;<br /> p1=p1->next;<br /> p2=p2->next;<br /> }<br /> else return false;<br /> while(p1!=L1.head)<br /> if(MakeNode(pSub,0))<br /> {<br /> t=p1->data+co;<br /> pSub->data=(t+10000)%10000;<br /> co=t<0?-1:0;<br /> AddNodeTail(SubList,pSub);<br /> pSub=NULL;<br /> p1=p1->next;<br /> }<br /> else return false;<br /> Delete0(SubList);<br /> return true;<br /> }<br /> bool Mul(OrderedList &L1,OrderedList &L2,OrderedList &MulList)<br /> {<br /> LinkType p1,p2,pMul,pt,pnew;<br /> int co,t;<br /> if(!InitList(MulList)) return false;<br /> Delete0(L1);<br /> Delete0(L2);<br /> co=0;<br /> t=0;<br /> p2=L2.head->next;<br /> pMul=NULL;<br /> while(p2!=L2.head)<br /> {<br /> p1=L1.head->next;<br /> if(pMul==NULL&&MakeNode(pMul,0)) AddNodeTail(MulList,pMul);<br /> pt=pMul;<br /> while(p1!=L1.head)<br /> {<br /> t=pt->data+p1->data*p2->data+co;<br /> pt->data=t%10000;<br /> co=t/10000;<br /> if(pt->next==MulList.head&&MakeNode(pnew,0)) AddNodeTail(MulList,pnew);<br /> else if(pt->next==MulList.head) return false;<br /> pnew=NULL;<br /> p1=p1->next;<br /> pt=pt->next;<br /> }<br /> pt->data+=co;<br /> co=0;<br /> pMul=pMul->next;<br /> p2=p2->next;<br /> }<br /> if(co)<br /> {<br /> pt->data=co;<br /> co=0;<br /> }<br /> else if(co) return false;<br /> Delete0(MulList);<br /> return true;<br /> }<br /> bool Div(OrderedList &L1,OrderedList &L2,OrderedList &DivList)<br /> {<br /> int i,t;<br /> bool flag,x;<br /> LinkType pL1Left,pL1Right,pDiv,ptLeft,ptRight,pSingle;<br /> OrderedList MulList,L1Sub,SingleList;<br /> Delete0(L1);<br /> Delete0(L2);<br /> if(!InitList(DivList)||!InitList(SingleList)) return false;<br /> if(MakeNode(pSingle,0)) AddNodeTail(SingleList,pSingle);<br /> else return false;<br /> flag=false;<br /> pL1Right=L1.head;<br /> if(L1.size>L2.size)<br /> for(i=1;i<=L2.size;i++) pL1Right=pL1Right->prior;<br /> else pL1Right=L1.head->next;<br /> while(!flag)<br /> {<br /> pL1Left=L1.head->prior;<br /> if(MakeNode(pDiv,0)) AddNodeHead(DivList,pDiv);<br /> else return false;<br /> if(pL1Right->prior!=L1.head)<br /> {<br /> ptLeft=pL1Right->prior;<br /> ptRight=L1.head->next;<br /> pL1Right->prior=L1.head;<br /> L1.head->next=pL1Right;<br /> }<br /> else flag=true;<br /> L1.size=GetLength(L1);<br /> t=L1.size>L2.size?pL1Left->data*10000+pL1Left->prior->data:pL1Left->data;<br /> t=t>0?t-1:t;<br /> pSingle->data=t/(L2.head->prior->data+1);<br /> x=false;<br /> do{<br /> if(x) DestroyList(MulList);<br /> x=true;<br /> if(!Mul(SingleList,L2,MulList)) return false;<br /> pSingle->data++;<br /> }while(CompareList(L1,MulList));<br /> pSingle->data-=2;<br /> pDiv->data=pSingle->data;<br /> DestroyList(MulList);<br /> if(!Mul(SingleList,L2,MulList)||!Sub(L1,MulList,L1Sub)) return false;<br /> if(!CopyList(L1Sub,L1)) return false;<br /> DestroyList(L1Sub);<br /> if(!flag)<br /> {<br /> L1.head->next->prior=ptLeft;<br /> ptLeft->next=L1.head->next;<br /> ptRight->prior=L1.head;<br /> L1.head->next=ptRight;<br /> L1.size=GetLength(L1);<br /> pL1Right=pL1Right->prior;<br /> }<br /> pDiv=NULL;<br /> }<br /> Delete0(DivList);<br /> return true;<br /> }<br /> bool Factorial(OrderedList &L,OrderedList &Lt)<br /> {<br /> OrderedList L1,LSub,MulList;<br /> LinkType p1,pMul,pt;<br /> Delete0(L);<br /> if(L.size==1&&(!L.head->next->data||L.head->next->data==1))<br /> {<br /> if(!InitList(Lt)) return false;<br /> if(MakeNode(pt,1)) AddNodeTail(Lt,pt);<br /> else return false;<br /> return true;<br /> }<br /> if(!InitList(L1)) return false;<br /> if(MakeNode(p1,1)) AddNodeTail(L1,p1);<br /> else return false;<br /> if(!InitList(Lt)) return false;<br /> if(!CopyList(L,Lt)) return false;<br /> do{<br /> if(!Sub(L,L1,LSub)) return false;<br /> if(!Mul(Lt,LSub,MulList)) return false;<br /> if(!CopyList(MulList,Lt)) return false;<br /> DestroyList(MulList);<br /> if(!CopyList(LSub,L)) return false;<br /> DestroyList(LSub);<br /> }while(!(L.size==1&&L.head->next->data==1));<br /> return true;<br /> }<br /> bool Involution(OrderedList L1,OrderedList &L2,OrderedList &ResultList)<br /> {<br /> OrderedList L3,LMul,LSub;<br /> LinkType p3;<br /> Delete0(L1);<br /> Delete0(L2);<br /> if(!InitList(L3)) return false;<br /> if(MakeNode(p3,1)) AddNodeTail(L3,p3);<br /> else return false;<br /> if(!InitList(ResultList)) return false;<br /> if(!CopyList(L3,ResultList)) return false;<br /> while(!(L2.size==1&&L2.head->next->data==0))<br /> {<br /> if(!Mul(ResultList,L1,LMul)) return false;<br /> if(!CopyList(LMul,ResultList)) return false;<br /> DestroyList(LMul);<br /> if(!Sub(L2,L3,LSub)) return false;<br /> if(!CopyList(LSub,L2)) return false;<br /> DestroyList(LSub);<br /> }<br /> return true;<br /> }<br /> bool ReadInteger(OrderedList &L1,OrderedList &L2)<br /> {<br /> char elem;<br /> bool flag1,flag2,flag3;<br /> LinkType p;<br /> flag1=0;<br /> flag2=0;<br /> flag3=0;<br /> getchar();<br /> while(true)<br /> {<br /> elem=getchar();<br /> if(!flag1&&!flag2)<br /> if(InitList(L1))<br /> {<br /> if(elem=='-')<br /> {<br /> L1.head->data=1;<br /> flag2=1;<br /> }<br /> else if(elem=='+') continue;<br /> else if(elem>='0'&&elem<='9')<br /> if(MakeNode(p,elem-'0'))<br /> {<br /> AddNodeHead(L1,p);<br /> p=NULL;<br /> flag2=1;<br /> flag3=1;<br /> }<br /> else return false;<br /> }<br /> else return false;<br /> else if(!flag1&&flag2&&!flag3)<br /> if(MakeNode(p,elem-'0'))<br /> {<br /> AddNodeHead(L1,p);<br /> p=NULL;<br /> flag3=1;<br /> }<br /> else return false;<br /> else if(!flag1&&flag3)<br /> {<br /> if(elem==',') flag3=0;<br /> else if(elem==' ')<br /> {<br /> flag1=1;<br /> flag2=0;<br /> flag3=0;<br /> }<br /> else if(elem>='0'&&elem<='9')<br /> {<br /> L1.head->next->data*=10;<br /> L1.head->next->data+=elem-'0';<br /> }<br /> }<br /> else if(flag1&&!flag2)<br /> if(InitList(L2))<br /> {<br /> if(elem=='-')<br /> {<br /> L2.head->data=1;<br /> flag2=1;<br /> }<br /> else if(elem=='+') continue;<br /> else if(elem>='0'&&elem<='9')<br /> if(MakeNode(p,elem-'0'))<br /> {<br /> AddNodeHead(L2,p);<br /> p=NULL;<br /> flag2=1;<br /> flag3=1;<br /> }<br /> else return false;<br /> }<br /> else return false;<br /> else if(flag1&&flag2&&!flag3)<br /> if(MakeNode(p,elem-'0'))<br /> {<br /> AddNodeHead(L2,p);<br /> p=NULL;<br /> flag3=1;<br /> }<br /> else return false;<br /> else if(flag1&&flag2&&flag3)<br /> if(elem==',') flag3=0;<br /> else if(elem==' ') return true;<br /> else if(elem>='0'&&elem<='9')<br /> {<br /> L2.head->next->data*=10;<br /> L2.head->next->data+=elem-'0';<br /> }<br /> }<br /> }<br /> void InputStyle()<br /> {<br /> printf("输入长整数与运算符,如“123,4567 234,5678 *”\n");<br /> }<br /> void Error()<br /> {<br /> printf("内存空间不足\n");<br /> }<br /> void Output(OrderedList &L)<br /> {<br /> int i;<br /> bool flag;<br /> LinkType p;<br /> if(L.head->data==1) printf("-");<br /> flag=false;<br /> p=L.head->prior;<br /> for(i=1;i<=L.size;i++)<br /> {<br /> if(!flag) flag=true;<br /> else<br /> if(p->data<10) printf("000");<br /> else if(p->data<100) printf("00");<br /> else if(p->data<1000) printf("0");<br /> printf("%d",p->data);<br /> if(i!=L.size) printf(",");<br /> p=p->prior;<br /> }<br /> printf("\n");<br /> }<br /> bool Control(OrderedList &L1,OrderedList &L2,OrderedList &ResultList)<br /> {<br /> int t1,t2,t;<br /> bool compare;<br /> char elem;<br /> elem=getchar();<br /> t1=L1.head->data;<br /> t2=L2.head->data;<br /> t=L2.head->next->data;<br /> if((t1==t2&&elem=='+'||t1!=t2&&elem=='-')&&Add(L1,L2,ResultList)) ResultList.head->data=t1;<br /> else if(t1!=t2&&elem=='+')<br /> {<br /> compare=CompareList(L1,L2);<br /> if(compare&&Sub(L1,L2,ResultList)) ResultList.head->data=t1;<br /> else if(!compare&&Sub(L2,L1,ResultList)) ResultList.head->data=t2;<br /> else return false;<br /> }<br /> else if(t1==t2&&elem=='-')<br /> {<br /> compare=CompareList(L1,L2);<br /> if(compare&&Sub(L1,L2,ResultList)) ResultList.head->data=0;<br /> else if(!compare&&Sub(L2,L1,ResultList)) ResultList.head->data=1;<br /> else return false;<br /> }<br /> else if(elem=='*'&&Mul(L1,L2,ResultList))<br /> {<br /> if(t1==t2) ResultList.head->data=0;<br /> else ResultList.head->data=1;<br /> }<br /> else if(elem=='/'&&Div(L1,L2,ResultList))<br /> {<br /> if(t1==t2) ResultList.head->data=0;<br /> else ResultList.head->data=1;<br /> }<br /> else if(elem=='%'&&Div(L1,L2,ResultList))<br /> {<br /> CopyList(L1,ResultList);<br /> if(t1==t2) ResultList.head->data=0;<br /> else ResultList.head->data=1;<br /> }<br /> else if(elem=='!'&&Factorial(L1,ResultList)){}<br /> else if(elem=='^'&&Involution(L1,L2,ResultList))<br /> {<br /> if(!t1) ResultList.head->data=0;<br /> else<br /> {<br /> if(t%2==0) ResultList.head->data=0;<br /> else ResultList.head->data=1;<br /> }<br /> }<br /> else return false;<br /> if(ResultList.size==1&&!ResultList.head->next->data) ResultList.head->data=0;<br /> DestroyList(L1);<br /> DestroyList(L2);<br /> return true;<br /> }<br /> int main()<br /> {<br /> OrderedList L1,L2,ResultList;<br /> int times;<br /> printf("需要测试几组数据？ ");<br /> scanf("%d",×);<br /> while(times--)<br /> {<br /> InputStyle();<br /> if(!ReadInteger(L1,L2))<br /> {<br /> Error();<br /> return 0;<br /> }<br /> if(Control(L1,L2,ResultList))<br /> {<br /> Output(ResultList);<br /> DestroyList(ResultList);<br /> }<br /> else Error();<br /> }<br /> return 0;<br /> }
        排版有点乱，作为一个macvim小白，不知道怎么才能re-indent，愿知者以闻。

        现在看来，这段代码写得实在不咋的。从软件工程的角度看，用C++的语法写C代码，没把ADT封装成类，而写成了结构体和相关函数。从视觉美观的角度看，变量与运算符，行与行之间没有空格，空行，难看之极。从算法的角度看，乘法很朴素，没有用分治之类的优化，时间复杂度为O(n^2)；阶乘更加不堪，从前往后算……

        再往底层考虑优化，可以应用对象池技术，减少从堆区申请内存空间的次数。