数据结构 双向链表的应用之大整数运算

/ 好叫你见识见识，什么叫做又臭又长的裹脚布代码，这篇帖子也是 /

（大数运算） long long类型一般占8个字节是C/C++中的精度最高的整数类型，取值范围在 -9223372036854775808～+9223372036854775807。在很多场景中，整数范围超出了long long的最值，例如在非对称加密中密钥长度一般为1024bit，转换为十进制数将超过300位，因此不能直接用内置的整数类型来运算。请编写大数运算类型MyBigInteger，使其支持大数据的加法，减法，乘法的运算。 （除法为选做功能，除法运算符合C/C++中的整数除法运算的规则，有20%的测试用例包含除法运算）

【输入】 大整数n，n的位数 Target entry; Node* next; Node* back; Node(); Node(Target item,Node *link_back=NULL,Node *link_next=NULL); }; Node::Node() { next=NULL; back=NULL; } Node::Node(Target item,Node *link_back,Node *link_next) { entry=item; next=link_next; back=link_back; } class List { public: List(); ~List(); List(const List ©); void operator= (const List ©); int size( ) const; bool is_full( ) const; bool is_empty( ) const; void clear( ); void traverse(void (*visit)(Target &)); void antitraverse(void (*visit)(Target &)); Error_code retrieve(int position, Target &x) const; Error_code replace(int position, const Target &x); Error_code remove(int position, Target &x); Error_code insert(int position, const Target &x); Error_code back_insert(const Target &x); Error_code front_insert(const Target &x); protected: int count; mutable int current_position; mutable Node *current; void set_position(int position) const; }; List::List() { count = 0; current_position = -1; current = NULL; } List::List(const List ©) { count=copy.count; current_position=copy.current_position; Node *new_node,*old_node=copy.current; if(old_node==NULL) current=NULL; else { new_node=current=new Node(old_node->entry); while(old_node->next!=NULL) { old_node=old_node->next; new_node->next=new Node(old_node->entry,new_node); new_node=new_node->next; } old_node=copy.current; new_node=current; while(old_node->back!=NULL) { old_node=old_node->back; new_node->back=new Node(old_node->entry,NULL,new_node); new_node=new_node->back; } } } void List::operator= (const List ©) { List new_copy(copy); clear(); count=new_copy.count; current_position=new_copy.current_position; current=new_copy.current; new_copy.current=NULL; new_copy.current_position=0; new_copy.count=0; } List::~List() { clear(); } void List::clear() { Node *p,*q; if(current==NULL) return; for(p=current->back;p;p=q) { q=p->back; delete p; } for(p=current;p;p=q) { q=p->next; delete p; } count=0; current=NULL; current_position=-1; } int List::size() const { return count; } bool List::is_empty() const { return count==0; } bool List::is_full() const { Node *new_node; new_node=new Node; if(new_node==NULL) return true; else { delete new_node; return false; } } void List::set_position(int position) const { if (position>=current_position) for ( ; current_position != position; current_position++) current=current->next; else for ( ; current_position != position; current_position--) current=current->back; } void List::traverse(void (*visit)(Target &)) { Node *q=current; if(q!=NULL) for(;q->back;q=q->back) ; for(;q;q=q->next) (*visit)(q->entry); } void List::antitraverse(void (*visit)(Target &)) { Node *p=current; if(p!=NULL) for(;p->next;p=p->next); for(;p;p=p->back) (*visit)(p->entry); } Error_code List::replace(int position,const Target &x) { if (position count) return Range_error; set_position(position); current->entry=x; return success; } Error_code List::insert(int position, const Target &x) { if (position count) return Range_error; Node *new_node, *preceding, *following; if (position==0) { if(count==0) following=NULL; else { set_position(0); following=current; } preceding=NULL; } else { set_position(position-1); preceding=current; following=preceding->next; } new_node=new Node(x,preceding,following); if(new_node==NULL) return overflow; if(preceding!=NULL) preceding->next=new_node; if(following!=NULL) following->back=new_node; current=new_node; current_position=position; count++; return success; } Error_code List::remove(int position,Target &x) { if (position=count) return Range_error; Node *old_node, *neighbor; set_position(position); old_node=current; if (neighbor=current->back) { neighbor->next=current->next; } if (neighbor=current->next) { neighbor->back=current->back; current=neighbor; } else { current=current->back; current_position--; } x=old_node->entry; delete old_node; count--; return success; } Error_code List::back_insert(const Target &x) { insert(count,x); return success; } Error_code List::front_insert(const Target &x) { insert(0,x); return success; } Error_code List::retrieve(int position, Target &x) const { if (position = count) return Range_error; set_position(position); x=current->entry; return success; } void print(Target &x) { cout sym=-1; for(int i=1;i sym=0; for(int i=0;i flag=0; int lenp=p.size(),lena=a.size(); if(lenp>lena) flag=1; else if(lenp Target np,na; p.retrieve(cnt,np); a.retrieve(cnt,na); if(np>na) { flag=1; break; } else if(na>np) { flag=-1; break; } cnt--; } } if(flag==-1) { List temp; temp=p; p=a; a=temp; } } 计算 加法

纯模拟，从低位开始两两相加，只留个位，十位作为进位参与到下次计算，两个list的所有结点都参与过运算之后进位如果大于0，则再进位。 感觉这里对于两个加数不同长度的处理还是蛮妙的。

每次从乘数的低位取一个数字，和另一个乘数的每一位数字相乘，还是进位那一套，最后根据一开始取的数字的位数，在每次乘积的低位补上相应个数的0，最后把这些乘积加起来就可以了。

之前的计算函数都是默认输入为两个整数，但是实际情况更加复杂，在运用时需要对具体情况，比如数据的正负，数据的长度等进行判断，比如“-” + “-” ， “+” - “-”…… 好叭我承认这样处理确实是因为我很愚蠢很笨蛋。