精华内容
下载资源
问答
  • / 好叫你见识见识,什么叫做又臭...long long类型一般占8个字节是C/C++中精度最高的整数类型,取值范围在 -9223372036854775808~+9223372036854775807。在很多场景中,整数范围超出了long long最值,例如在非对...

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

    题目

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

    【输入】
    大整数n,n的位数<=200
    大整数m,m的位数<=200
    运算符(+,-,*, /)

    【输出】n和m的运算结果

    例如:
    【输入】
    56891237265
    32156789215
    -

    【输出】
    24734448050

    思路

    非常懒惰没有去写BigInt的类,直接用的自定义的双向链表,解题分为五部:写双向链表类,输入,判断,计算,输出。

    定义类

    基本都是书上那一套,没啥好说的,多加了一个倒序遍历,头插和尾插,用起来会顺手些。

    enum Error_code{underflow,overflow,success,Range_error};
    typedef int Target;
    struct Node
    {
    	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 &copy);
    		void operator= (const List &copy);
    		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 &copy)
    {
    	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 &copy)
    {
    	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 < 0 || position > count)
    		return Range_error;
    	set_position(position);
    	current->entry=x;
    	return success;
    }
    
    Error_code List::insert(int position, const Target &x)
    {
    	if (position < 0 || 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<0||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 < 0 || position >= count)
    		return Range_error;
    	set_position(position);
    	x=current->entry;
    	return success;
    }
    
    void print(Target &x)
    {
    	cout << x ;
    }
    
    

    输入

    大数作为字符串被读入,然后逐位放进 list 中,考虑到进位,我们将其倒序存放(头插),同时定义一个符号位sym,后面用得上。

    void input(List &info,int &sym)
    {
    	string s;
    	cin >> s;
    	if(s[0]=='-')
    	{
    		sym=-1;
    		for(int i=1;i<s.size();i++)
    		{
    			info.front_insert(s[i]-'0');
    		}
    	}
    	else
    	{
    		sym=0;
    		for(int i=0;i<s.size();i++)
    		{
    			info.front_insert(s[i]-'0');
    		}
    	}
    		
    }	
    

    判断

    在进行减法和除法运算的时候,我需要判断两个数的大小关系,有时还需要将他们交换。
    比较大小时先比较位数长短关系,位数相同时就从高位开始比较,直到出现不同。
    非交换的判断函数和判断交换函数只有最后几行不同。

    void judge_and_swap(List &p,List &a,int &flag)
    {
    	flag=0;
    	int lenp=p.size(),lena=a.size();
    	if(lenp>lena)
    		flag=1;
    	else if(lenp<lena)
    		flag=-1;
    	else
    	{
    		int cnt=lenp-1;
    		while(cnt>=0)
    		{
    			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,则再进位。
    感觉这里对于两个加数不同长度的处理还是蛮妙的。

    List bigintadd (List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int carry=0,cntp=0,cnta=0;
    	while(cntp<pre.size()||cnta<aft.size())
    	{
    		int sum=carry;
    		if(cntp<pre.size())
    		{
    			pre.retrieve(cntp,pret); 
    			sum+=pret;
    			cntp++;
    		}
    		if(cnta<aft.size())
    		{
    			aft.retrieve(cnta,aftt); 
    			sum+=aftt;
    			cnta++;
    		}
    		carry=sum/10;
    		res.back_insert(sum%10);
    	}
    	if(carry>0)
    		res.back_insert(carry);
    	return res;
    }
    
    减法

    减法比加法啰嗦一步,为了保证 bigintsub 函数执行完之后结果 list 中每一位都大于零,我们调用比较交换函数,确保大数减小数。
    之后还是模拟,被减数的位减去减数的位,如果结果小于零就加十,然后进位设置为-1参与下次运算。接着根据比较函数得到的两数大小给数据加符号,最后再剔除一手高位退位产生的前导0。

    List bigintsub (List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int flag1;
    	judge_and_swap(pre,aft,flag1);
    	if(flag1==0)
    		res.back_insert(0);
    	else
    	{
    		int carry=0,cntp=0,cnta=0;
    		while(cntp<pre.size()||cnta<aft.size())
    		{
    			int sum=carry;
    			if(cntp<pre.size())
    			{
    				pre.retrieve(cntp,pret); 
    				sum+=pret;
    				cntp++;
    			}
    			if(cnta<aft.size())
    			{
    				aft.retrieve(cnta,aftt); 
    				sum-=aftt;
    				cnta++;
    			}
    			if(sum<0) 
    			{
    				sum+=10;
    				carry=-1;
    			}
    			else
    			{
    				carry=0;
    			}
    			res.back_insert(sum%10);
    		}
    		if(flag1==-1)
    		{
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}
    	int rest;
    	res.retrieve(res.size()-1,rest);
    	while(rest==0&&(!res.is_empty()))
    	{
    		res.remove(res.size()-1,rest);
    		res.retrieve(res.size()-1,rest);
    	}
    	return res;
    }
    
    
    乘法

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

    List bigintmult(List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int flag1;
    	judge_and_swap(pre,aft,flag1);
    	Target i2;
    	int cnt=0;
    	while(!aft.is_empty())
    	{
    		List temps,tempr;
    		aft.remove(0,i2);
    		temps=pre;
    		if(!temps.is_empty())
    		{
    			int sum=0,carry=0;
    			while(!temps.is_empty())
    			{
    				Target i1;
    				temps.remove(0,i1);
    				sum=i1*i2+carry;
    				carry=sum/10;
    				sum%=10;
    				tempr.back_insert(sum);
    			}
    			if(carry>0)
    				tempr.back_insert(carry);
    		}
    		for(int i=0;i<cnt;i++)
    			tempr.front_insert(0);
    		cnt++;
    		res=bigintadd(res,tempr);
    	}
    	return res;
    }
    
    
    除法

    除法是折磨我时间最长的,一开始想到的思路是用被除数减除数,直到被减数小于减数,计算减的次数,但是这样做毫无疑问会超时,于是换了思路,本质也是做减法,但是最开始给减数补上0,0的个数为二者位数差,然后每次补零的个数递减。
    举个栗子:6666 / 23 。按照一开始的思路是 6666 = 23*289+19 ,需要计算 289 次,结果为 289,改良之后为 6666=2300*2+230*8+23*9+19,只需要计算19次,结果为 200+80+9=289,完全一致嘛。
    一些特殊情况就是被除数小于除数或者有0存在,就直接将结果返回为0。

    List bigintdiv(List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int flag1;
    	judge_and_swap(pre,aft,flag1);
    	pre.retrieve(pre.size()-1,pret);
    	aft.retrieve(aft.size()-1,aftt);
    	if(flag1==-1||pret==0||aftt==0)
    	{
    		res.back_insert(0);
    		return res;
    	}
    	else
    	{
    		List temp;
    		int cnt=pre.size()-aft.size();
    		temp.back_insert(1);
    		res.back_insert(0);
    		for(int i=0;i<cnt;i++) //补零
    		{
    			temp.front_insert(0);
    			aft.front_insert(0);
    		}
    		while(cnt>=0)
    		{
    			int flag2;
    			judge(pre,aft,flag2);
    			while(flag2!=-1)
    			{
    				pre=bigintsub(pre,aft);
    				int t;
    				pre.retrieve(pre.size()-1,t);
    				while(t==0&&(!pre.is_empty()))
    				{
    					pre.remove(pre.size()-1,t);
    					pre.retrieve(pre.size()-1,t);
    				}
    				judge(pre,aft,flag2);
    				res=bigintadd(res,temp);
    			}
    			cnt--;
    			Target tmp;
    			temp.remove(0,tmp);   //去零
    			aft.remove(0,tmp);
    		}
    	}
    	return res;
    }
    
    
    符号判断

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

    void solve(List &a,List &b,List &res,char s,int flaga,int flagb)
    {
    	int flag=flaga+flagb;
    	if(s=='+'&&flag==0)
    		res=bigintadd(a,b);
    	else if(s=='+'&&flag==-2)
    	{
    		res=bigintadd(a,b);
    		int rest;
    		res.retrieve(res.size()-1,rest);
    		rest*=-1;
    		res.replace(res.size()-1,rest);
    	}
    	else if((s=='+'&&flag==-1))
    	{
    		int cnt;
    		judge_and_swap(a,b,cnt);
    		res=bigintsub(a,b);
    		if((cnt==1&&flaga==-1)||(cnt==-1&&flagb==-1))
    		{
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}
    	else if(s=='-'&&flaga==-1&&flagb==0)
    	{
    		res=bigintadd(a,b);
    		int rest;
    		res.retrieve(res.size()-1,rest);
    		rest*=-1;
    		res.replace(res.size()-1,rest);
    	}
    	else if(s=='-'&&flaga==0&&flagb==-1)
    	{
    		res=bigintadd(a,b);
    	}
    	else if(s=='-')
    		res=bigintsub(a,b);
    	else if(s=='*')
    	{
    		res=bigintmult(a,b);
    		if(flag==-1)
    		{
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}
    	else if(s=='/')
    	{
    		res=bigintdiv(a,b);	
    		if(flag==-1)
    		{		
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}	
    	int rest;
    	res.retrieve(res.size()-1,rest);
    	while(rest==0&&(!res.is_empty()))
    	{
    		res.remove(res.size()-1,rest);
    		res.retrieve(res.size()-1,rest);
    	}
    	if(!res.is_empty())
    		res.antitraverse(print);
    	else
    		cout << 0;
    }
    
    

    输出

    具体代码写在上面的solve函数里了,就是再判断一次前导0,然后把 list 里的内容逆序输出即可。

    完整代码

    #include <bits/stdc++.h>
    using namespace std;
    /* run this program using the console pauser or add your own getch, system("pause") or input loop */
    
    enum Error_code{underflow,overflow,success,Range_error};
    typedef int Target;
    struct Node
    {
    	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 &copy);
    		void operator= (const List &copy);
    		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 &copy)
    {
    	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 &copy)
    {
    	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 < 0 || position > count)
    		return Range_error;
    	set_position(position);
    	current->entry=x;
    	return success;
    }
    
    Error_code List::insert(int position, const Target &x)
    {
    	if (position < 0 || 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<0||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 < 0 || position >= count)
    		return Range_error;
    	set_position(position);
    	x=current->entry;
    	return success;
    }
    
    void print(Target &x)
    {
    	cout << x ;
    }
    
    void input(List &info,int &sym)
    {
    	string s;
    	cin >> s;
    	if(s[0]=='-')
    	{
    		sym=-1;
    		for(int i=1;i<s.size();i++)
    		{
    			info.front_insert(s[i]-'0');
    		}
    	}
    	else
    	{
    		sym=0;
    		for(int i=0;i<s.size();i++)
    		{
    			info.front_insert(s[i]-'0');
    		}
    	}
    		
    }	
    
    List bigintadd (List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int carry=0,cntp=0,cnta=0;
    	while(cntp<pre.size()||cnta<aft.size())
    	{
    		int sum=carry;
    		if(cntp<pre.size())
    		{
    			pre.retrieve(cntp,pret); 
    			sum+=pret;
    			cntp++;
    		}
    		if(cnta<aft.size())
    		{
    			aft.retrieve(cnta,aftt); 
    			sum+=aftt;
    			cnta++;
    		}
    		carry=sum/10;
    		res.back_insert(sum%10);
    	}
    	if(carry>0)
    		res.back_insert(carry);
    	return res;
    }
    
    void judge_and_swap(List &p,List &a,int &flag)
    {
    	flag=0;
    	int lenp=p.size(),lena=a.size();
    	if(lenp>lena)
    		flag=1;
    	else if(lenp<lena)
    		flag=-1;
    	else
    	{
    		int cnt=lenp-1;
    		while(cnt>=0)
    		{
    			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;
    	}
    }
    
    void judge(List p,List a,int &flag)
    {
    	flag=0;
    	int lenp=p.size(),lena=a.size();
    	if(lenp>lena)
    		flag=1;
    	else if(lenp<lena)
    		flag=-1;
    	else
    	{
    		int cnt=lenp-1;
    		while(cnt>=0)
    		{
    			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--;
    		}
    	}
    }
    
    List bigintsub (List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int flag1;
    	judge_and_swap(pre,aft,flag1);
    	if(flag1==0)
    		res.back_insert(0);
    	else
    	{
    		int carry=0,cntp=0,cnta=0;
    		while(cntp<pre.size()||cnta<aft.size())
    		{
    			int sum=carry;
    			if(cntp<pre.size())
    			{
    				pre.retrieve(cntp,pret); 
    				sum+=pret;
    				cntp++;
    			}
    			if(cnta<aft.size())
    			{
    				aft.retrieve(cnta,aftt); 
    				sum-=aftt;
    				cnta++;
    			}
    			if(sum<0) 
    			{
    				sum+=10;
    				carry=-1;
    			}
    			else
    			{
    				carry=0;
    			}
    			res.back_insert(sum%10);
    		}
    		if(flag1==-1)
    		{
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}
    	int rest;
    	res.retrieve(res.size()-1,rest);
    	while(rest==0&&(!res.is_empty()))
    	{
    		res.remove(res.size()-1,rest);
    		res.retrieve(res.size()-1,rest);
    	}
    	return res;
    }
    
    List bigintmult(List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int flag1;
    	judge_and_swap(pre,aft,flag1);
    	Target i2;
    	int cnt=0;
    	while(!aft.is_empty())
    	{
    		List temps,tempr;
    		aft.remove(0,i2);
    		temps=pre;
    		if(!temps.is_empty())
    		{
    			int sum=0,carry=0;
    			while(!temps.is_empty())
    			{
    				Target i1;
    				temps.remove(0,i1);
    				sum=i1*i2+carry;
    				carry=sum/10;
    				sum%=10;
    				tempr.back_insert(sum);
    			}
    			if(carry>0)
    				tempr.back_insert(carry);
    		}
    		for(int i=0;i<cnt;i++)
    			tempr.front_insert(0);
    		cnt++;
    		res=bigintadd(res,tempr);
    	}
    	return res;
    }
    
    List bigintdiv(List pre,List aft)
    {
    	List res;
    	Target pret,aftt;
    	int flag1;
    	judge_and_swap(pre,aft,flag1);
    	pre.retrieve(pre.size()-1,pret);
    	aft.retrieve(aft.size()-1,aftt);
    	if(flag1==-1||pret==0||aftt==0)
    	{
    		res.back_insert(0);
    		return res;
    	}
    	else
    	{
    		List temp;
    		int cnt=pre.size()-aft.size();
    		temp.back_insert(1);
    		res.back_insert(0);
    		for(int i=0;i<cnt;i++)
    		{
    			temp.front_insert(0);
    			aft.front_insert(0);
    		}
    		while(cnt>=0)
    		{
    			int flag2;
    			judge(pre,aft,flag2);
    			while(flag2!=-1)
    			{
    				pre=bigintsub(pre,aft);
    				int t;
    				pre.retrieve(pre.size()-1,t);
    				while(t==0&&(!pre.is_empty()))
    				{
    					pre.remove(pre.size()-1,t);
    					pre.retrieve(pre.size()-1,t);
    				}
    				judge(pre,aft,flag2);
    				res=bigintadd(res,temp);
    			}
    			cnt--;
    			Target tmp;
    			temp.remove(0,tmp);
    			aft.remove(0,tmp);
    		}
    	}
    	return res;
    }
    
    void solve(List &a,List &b,List &res,char s,int flaga,int flagb)
    {
    	int flag=flaga+flagb;
    	if(s=='+'&&flag==0)
    		res=bigintadd(a,b);
    	else if(s=='+'&&flag==-2)
    	{
    		res=bigintadd(a,b);
    		int rest;
    		res.retrieve(res.size()-1,rest);
    		rest*=-1;
    		res.replace(res.size()-1,rest);
    	}
    	else if((s=='+'&&flag==-1))
    	{
    		int cnt;
    		judge_and_swap(a,b,cnt);
    		res=bigintsub(a,b);
    		if((cnt==1&&flaga==-1)||(cnt==-1&&flagb==-1))
    		{
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}
    	else if(s=='-'&&flaga==-1&&flagb==0)
    	{
    		res=bigintadd(a,b);
    		int rest;
    		res.retrieve(res.size()-1,rest);
    		rest*=-1;
    		res.replace(res.size()-1,rest);
    	}
    	else if(s=='-'&&flaga==0&&flagb==-1)
    	{
    		res=bigintadd(a,b);
    	}
    	else if(s=='-')
    		res=bigintsub(a,b);
    	else if(s=='*')
    	{
    		res=bigintmult(a,b);
    		if(flag==-1)
    		{
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}
    	else if(s=='/')
    	{
    		res=bigintdiv(a,b);	
    		if(flag==-1)
    		{		
    			int rest;
    			res.retrieve(res.size()-1,rest);
    			rest*=-1;
    			res.replace(res.size()-1,rest);
    		}
    	}	
    	int rest;
    	res.retrieve(res.size()-1,rest);
    	while(rest==0&&(!res.is_empty()))
    	{
    		res.remove(res.size()-1,rest);
    		res.retrieve(res.size()-1,rest);
    	}
    	if(!res.is_empty())
    		res.antitraverse(print);
    	else
    		cout << 0;
    }
    
    int main()
    {
    	List pre,aft,final;
    	int flaga=0,flagb=0;
    	char s;
    	input(pre,flaga);
    	input(aft,flagb);
    	cin >> s;
    	solve(pre,aft,final,s,flaga,flagb);
    	return 0;
    }
    

    小结

    减法部分的符号判断我觉得是不全面的,ac就说明,欸题目数据很弱欸。
    整个代码都透出一种不灵光,笨拙的气息,封装性和鲁棒性都很差,确实是又臭又长,要学的东西还很多啊。
    因为代码里面过多的使用了传引用,静态评估分基本被扣光了,OCLint真的很严格。
    在这里插入图片描述
    希望以后会来更新这篇博文,把BigInt的类补上,把符号重载写一写,再封装的好一些。
    最近确实太忙了,计算机系统的实验挺费时间的,但也挺有趣的,五一找时间会写一写。

    推荐

    这一篇是大佬室友写的,比我的简洁多了。
    https://blog.csdn.net/weixin_47003107/article/details/105848624

    这一篇是同学推荐的,很吊的大数模板。
    https://www.cnblogs.com/feiyue-1779930274/p/11628128.html

    展开全文
  • 巨型整数运算符重载定义部分

    千次阅读 2008-12-31 20:34:00
    巨型整型运算重载--定义部分(.h)关键词: HugeInt 运算符重载 实现的功能:实现巨型整数的基本运算(关系运算,算术运算,复合运算,++,--...) //处理的主要思想:采用双向循环链表存储巨型数据 每结点存储四位数字 #...

    巨型整型运算重载--定义部分(.h)<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

    关键词HugeInt    运算符重载    实现的功能:实现巨型整数的基本运算(关系运算,算术运算,复合运算,++,--...)

    //处理的主要思想:采用双向循环链表存储巨型数据 每结点存储四位数字

    #include < iostream >
    #include< string >
    #include< math.h >
    using namespace std;

    typedef struct node//自定义类型名(链表结点)
    {int data;
    struct node *left,*right;
    } node;
    //*------------------使用extern申明下列函数可以在本模块或其它模块中使用--------------*//

    class HugeInt;//巨型整数类申明

    //---------------------(重载关系运算)---------------------------------------//
    extern bool operator>(HugeInt &m,HugeInt &n);
    extern bool operator>(HugeInt &m,const long int &n);
    extern bool operator>(const long int &m,HugeInt &n);
    extern bool operator>( char* m,HugeInt &n);
    extern bool operator>(HugeInt& m, char* n);

    extern bool operator>=(HugeInt &m,HugeInt &n);
    extern bool operator>=(HugeInt &m,const long int &n);
    extern bool operator>=(const long int &m,HugeInt &n);
    extern bool operator>=( char* m,HugeInt &n);
    extern bool operator>=(HugeInt& m, char* n);

    extern bool operator<(HugeInt &m,HugeInt &n);
    extern bool operator<(HugeInt &m,const long int &n);
    extern bool operator<(const long int &m,HugeInt &n);
    extern bool operator<( char* m,HugeInt &n);
    extern bool operator<(HugeInt& m, char* n);

    extern bool operator<=(HugeInt &m,HugeInt &n);
    extern bool operator<=(HugeInt &m,const long int &n);
    extern bool operator<=(const long int &m,HugeInt &n);
    extern bool operator<=( char* m,HugeInt &n);
    extern bool operator<=(HugeInt& m, char* n);

    extern bool operator==(HugeInt &m,HugeInt &n);
    extern bool operator==(HugeInt &m,const long int &n);
    extern bool operator==(const long int &m,HugeInt &n);
    extern bool operator==( char* m,HugeInt &n);
    extern bool operator==(HugeInt& m, char* n);

    extern bool operator!=(HugeInt &m,HugeInt &n);
    extern bool operator!=(HugeInt &m,const long int &n);
    extern bool operator!=(const long int &m,HugeInt &n);
    extern bool operator!=( char* m,HugeInt &n);
    extern bool operator!=(HugeInt& m, char* n);

    //------------------------(重载加法+)---------------------------------------//
    extern HugeInt operator +(HugeInt& addend,const long int& augend);
    extern HugeInt operator +(const long int& addend,HugeInt& augend);
    extern HugeInt operator +(HugeInt& addend,HugeInt& augend);
    extern HugeInt operator +(HugeInt& addend,char* augend);
    extern HugeInt operator +(char* addend,HugeInt& augend);

    //------------------------(重载减法-)---------------------------------------//
    extern HugeInt operator -(HugeInt& minuend,HugeInt& subtrahend);
    extern HugeInt operator -(const long int& minuend,HugeInt& subtrahend);
    extern HugeInt operator -(HugeInt& minuend,const long int& subtrahend);
    //-----------------------(重载乘法*)----------------------------------------//
    extern HugeInt operator *(const long int& faciend,HugeInt& multiplicator);
    extern HugeInt operator *(HugeInt& faciend,const long int& multiplicator);
    extern HugeInt operator *(HugeInt& faciend,HugeInt& multiplicator);
    extern HugeInt operator *(HugeInt& faciend,char* multiplicator);
    extern HugeInt operator *(char* faciend,HugeInt& multiplicator);
    //-----------------------(重载除法/)----------------------------------------//
    extern HugeInt operator /(HugeInt dividend,HugeInt divisor);
    extern HugeInt operator /(const long int dividend,HugeInt divisor);
    extern HugeInt operator /(HugeInt dividend,const long int divisor);
    extern HugeInt operator /(HugeInt dividend,char* divisor);
    extern HugeInt operator /(char* dividend, HugeInt divisor);
    //------------------------(重载求余%)---------------------------------------//
    extern HugeInt operator %(HugeInt dividend,HugeInt divisor);
    extern HugeInt operator %(const long int dividend,HugeInt divisor);
    extern HugeInt operator %(HugeInt dividend,const long int divisor);
    //------------------------(重载求反)-------------------------------//
    extern HugeInt operator -(HugeInt h);

    //------------------------(重载求绝对值abs)---------------------------------//
    extern HugeInt abs(HugeInt);
    //------------------------(重载输出<<)--------------------------------------//
    extern ostream &operator<<(ostream & out,HugeInt &m);

    //*-------------------------HugeInt类及相关函数的定义------------------------*//
    //使用双向循环链表存储巨型数据,每四位数字为一个结点 如1,2653,0006,5632//
    class HugeInt
    {


    public:

    HugeInt(char *data);//使用字符串初始化

    HugeInt(const long);//使用长整型初始化

    HugeInt(HugeInt&);//拷贝构造函数

    HugeInt();//使用默认值0初始化

    bool Empty() const{return n==0;}//判断双链表是否为空

    void PrintList()const;//输出链表

    void DelList();//删除链表

    HugeInt& Insert(const short int x);//插入结点

    bool IsRight(char *data);//判断数据串是否合法

    char* abs(char*);//求数据串绝对值

    node* GetEndNode(){return RightEnd;}//获得链表尾结点

    int GetN(){return n;}//获得结点个数

    node* GetHeadNode(){return head;}//获得头结点

    HugeInt& SetHeadData(long int a){head->data=a;return *this;}//设置头结点值(巨型数符号)

    bool IsZero(){return (GetHeadNode()->right->data==0&&n==1);}//判断巨型数据值是否为零

    ~HugeInt();//析构函数

    //-----------------------以下是各运算符重载的定义---------------------------------//

    //------------------------(重载求绝对值abs)----------------------------//
    friend HugeInt abs(HugeInt);

    //-------------------------(重载关系运算)------------------------------//
    friend bool operator>(HugeInt &m,HugeInt &n);
    friend bool operator>(HugeInt &m,const long int &n);
    friend bool operator>(const long int &m,HugeInt &n);
    friend bool operator>(HugeInt &m, char* n);
    friend bool operator>( char* m,HugeInt &n);

    friend bool operator>=(HugeInt &m,HugeInt &n);
    friend bool operator>=(HugeInt &m,const long int &n);
    friend bool operator>=(const long int &m,HugeInt &n);
    friend bool operator>=(HugeInt &m,const char* &n);
    friend bool operator>=(const char*m,HugeInt &n);

    friend bool operator<(HugeInt &m,HugeInt &n);
    friend bool operator<(HugeInt &m,const long int &n);
    friend bool operator<(const long int &m,HugeInt &n);
    friend bool operator<(HugeInt &m, char*n);
    friend bool operator<( char*m,HugeInt &n);

    friend bool operator<=(HugeInt &m,HugeInt &n);
    friend bool operator<=(HugeInt &m,const long int &n);
    friend bool operator<=(const long int &m,HugeInt &n);
    friend bool operator<=(HugeInt &m,const char*n);
    friend bool operator<=(const char*m,HugeInt &n);

    friend bool operator==(HugeInt &m,HugeInt &n);
    friend bool operator==(HugeInt &m,const long int &n);
    friend bool operator==(const long int &m,HugeInt &n);
    friend bool operator==(HugeInt &m,const char* &n);
    friend bool operator==(const char*m,HugeInt &n);

    friend bool operator!=(HugeInt &m,HugeInt &n);
    friend bool operator!=(HugeInt &m,const long int &n);
    friend bool operator!=(const long int &m,HugeInt &n);
    friend bool operator!=(HugeInt &m, char*n);
    friend bool operator!=(char*m,HugeInt &n);

    //-------------------------(重载输出)-------------------------------//
    friend ostream &operator<<(ostream & out,HugeInt &m);

    //------------------------(重载乘法)-------------------------------//
    friend HugeInt operator *(const long int& faciend,HugeInt& multiplicator);
    friend HugeInt operator *(HugeInt& faciend,const long int& multiplicator);
    friend HugeInt operator *(HugeInt& faciend,HugeInt& multiplicator);
    friend HugeInt operator *(HugeInt& faciend,char* multiplicator);
    friend HugeInt operator *(char* faciend,HugeInt& multiplicator);

    //-----------------------(重载乘等于)------------------------------//
    HugeInt& operator *=(const long int& faciend);
    HugeInt& operator *=(HugeInt& faciend);
    HugeInt& operator *=(char* faciend);

    //------------------------(重载除法)-------------------------------//
    friend HugeInt operator /(HugeInt dividend,HugeInt divisor);
    friend HugeInt operator /(const long int dividend,HugeInt divisor);
    friend HugeInt operator /(HugeInt dividend,const long int divisor);
    friend HugeInt operator /(HugeInt dividend,char* divisor);
    friend HugeInt operator /(char* dividend, HugeInt divisor);
    //------------------------(重载除等于)-----------------------------//
    HugeInt& operator /=(HugeInt& dividend);
    HugeInt& operator /=(const long int& dividend);
    HugeInt& operator /=(char* dividend);
    //------------------------(重载求余)-------------------------------//
    friend HugeInt operator %(HugeInt dividend,HugeInt divisor);
    friend HugeInt operator %(const long int dividend,HugeInt divisor);
    friend HugeInt operator %(HugeInt dividend,const long int divisor);
    friend HugeInt operator %(HugeInt dividend,char* divisor);
    friend HugeInt operator %(char* dividend, HugeInt divisor);
    //------------------------(重载求余等于)---------------------------//
    HugeInt& operator %=(HugeInt& div);
    HugeInt& operator %=(const long int& div);
    HugeInt& operator %=(char* div);
    //------------------------(重载加法)-------------------------------//
    friend HugeInt operator +(const long int& addend,HugeInt& augend);
    friend HugeInt operator +(HugeInt& addend,const long int& augend);
    friend HugeInt operator +(HugeInt& addend,HugeInt& augend);
    friend HugeInt operator +(HugeInt& addend,char* augend);
    friend HugeInt operator +(char* addend,HugeInt& augend);

    //------------------------(重载加等于)-----------------------------//
    HugeInt& operator +=(HugeInt& augend);
    HugeInt& operator +=(const long int& augend);
    HugeInt& operator +=(char* augend);
    //------------------------(重载前++)-------------------------------//
    HugeInt& operator ++();
    //------------------------(重载后++)-------------------------------//
    HugeInt operator ++(int);
    //------------------------(重载前--)-------------------------------//
    HugeInt& operator --();
    //------------------------(重载后--)-------------------------------//
    HugeInt operator --(int);

    //------------------------(重载减法)-------------------------------//
    friend HugeInt operator -(const long int& minuend,HugeInt& subtrahend);
    friend HugeInt operator -(HugeInt& minuend,const long int& subtrahend);
    friend HugeInt operator -(HugeInt& minuend,HugeInt& subtrahend);
    friend HugeInt operator -(HugeInt& minuend,char* subtrahend);
    friend HugeInt operator -(char* minuend,HugeInt& subtrahend);
    //------------------------(重载减等于)-----------------------------//
    HugeInt& operator -=(HugeInt& subtrahend);
    HugeInt& operator -=(const long int& subtrahend);
    HugeInt& operator -=(char* subtrahend);


    //------------------------(重载赋值)-------------------------------//
    HugeInt& operator =(const long int& k);
    HugeInt& operator =(char* k);
    HugeInt& operator =(HugeInt& h);
    //------------------------(重载求反)-------------------------------//
    friend HugeInt operator -(HugeInt h);

    //私有数据成员
    private:

    int n;//表示结点个数

    node *RightEnd,*head;//头结点与尾结点 头结点用于存储数据的符号 正为0负为1

    };

    展开全文
  • Python笔记1 - 数据类型与转换Naiel•2019 年 07 月 02 日Python 数据类型与转换数据类型字符串有层名为【引号】皮,只要是被【单//三引号】这层皮括起来内容,不论那个内容是中文、英文、数字甚至火星文。...

    Python笔记1 - 数据类型与转换

    Naiel • 2019 年 07 月 02 日

    Python 数据类型与转换

    数据类型

    字符串

    有层名为【引号】的皮,只要是被【单/双/三引号】这层皮括起来的内容,不论那个内容是中文、英文、数字甚至火星文。只要是被括起来的,就表示是字符串类型。

    name = 'Phenxso'

    print(name)

    整数

    整数,整数英文为integer,简写做int。Python世界的整数其实和现实世界数学中定义的一样:是正整数、负整数和零的统称,是没有小数点的数字。

    a = 10

    b = -10

    c = 0

    浮点数

    比整数多了一个小数点『.』

    a = 1.0

    b = 3.14159

    c = -0.3333333

    浮点计算会存在误差

    数据的应用

    四则运算

    运算符

    表示

    例子

    +

    1 + 1 = 2

    -

    1 - 1 = 0

    *

    2 * 2 = 4

    /

    1 / 2 = 0.5

    %

    取模(返回除法的余数)

    5 % 2 = 1

    **

    幂(返回x的y次幂)

    2 ** 3 = 8(2的3次方)

    //

    取整除(返回商的整数部分)

    5 // 2 = 1 , 5.0 // 2.0 = 1.0

    字符串拼接

    合成零碎的词语变成完整一句话。

    使用 + 来拼接变量、字符串。

    数据类型的查询——type()函数

    #赋值

    name = 'Phenxso'

    int = 1

    float = 1.1

    #打印查询结果

    print(type(name))

    print(type(int))

    print(type(float))

    #运行结果

    数据转换

    str()函数

    str()函数能将数据转换成其字符串类型,不管这个数据是中文、数字、标点还是火星文,只要放到括号里。这个数据就能变成为字符串类型。

    int()函数

    将数据转换为整数类型的方法就是int()函数。其使用方法同str()一样,将你需要转换的内容放在括号里就行,像这样:int(转换的内容)。

    不过对于int()函数的使用,需要注意一点:只有符合整数规范的字符串类数据,才能被int()强制转换。

    首先,整数形式的字符串比如'6'和'1',可以被int()函数强制转换。

    文字形式,比如中文、火星文或者标点符号,不可以被int()函数强制转换。

    小数形式的字符串,由于Python的语法规则,也不能使用int()函数强制转换。

    但浮点数是可以被int()函数强制转换的。

    int()函数的本质是将数据转换为整数。所以对于浮点数,int()函数会做取整处理。但是,同我们平时对小数四舍五入的处理方法不同,int()函数会直接抹零,直接输出整数部分

    float()函数

    float()函数也可以将整数和字符串转换为浮点类型。但同时,如果括号里面的数据是字符串类型,那这个数据一定得是数字形式。

    展开全文
  • 算法(第4版) (豆瓣)一书中对链表的定义如下: 链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。链表(Linked list)是一种常见...

    3a34291e5b0927fd3d891df59b7920b7.png

    1 知识点

    1.1 什么是链表

    提到链表,我们大家都不陌生,在平时的编码中我们也或多或少地使用过这个数据结构。算法(第4版) (豆瓣)一书中对链表的定义如下:

    链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。

    链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。

    使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。

    1.2 链表结构

    1.2.1 单向链表

    链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。

    4c478d9cf0f879b0212be78952fe7734.png

    一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

    一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。

    1.2.2 双向链表

    一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接:一个指向前一个节点,(当此“连接”为第一个“连接”时,指向空值或者空列表);而另一个指向下一个节点,(当此“连接”为最后一个“连接”时,指向空值或者空列表)。

    8606ceb413531cdf3f0e6e3d0c7afc6b.png

    一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接

    双向链表也叫双链表双向链表中不仅有指向后一个节点的指针,还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点,当然也可以访问后一个节点,以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

    1.2.3 循环链表

    在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表,你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法,循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

    指向整个列表的指针可以被称作访问指针。

    e8a4ea83ea99582f72de14a4cbfef27e.png

    用单向链表构建的循环链表

    1.3链表相关的核心点

    • null/nil 异常处理
    • dummy node 哑巴节点
    • 快慢指针
    • 插入一个节点到排序链表
    • 从一个链表中移除一个节点
    • 翻转链表
    • 合并两个链表
    • 找到链表的中间节点

    2 常见题型

    83. 删除排序链表中的重复元素

    给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

    思路:直接法,遇到重复就跳过

    class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            cur = head
            while cur and cur.next:
                if cur.val == cur.next.val:
                    cur.next = cur.next.next
                else:
                    cur = cur.next
            return head

    82. 删除排序链表中的重复元素 II

    给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

    思路:定义哑节点指向链表头,定义双指针,一个指向当前节点,一个指向前一个节点。当有重复的元素时,cur指向下一位,直到下一位与当前节点不相等,用flag标记表示有重复数字,当循环完毕,pre的下一位指向cur的下一位,flag标记归位

    当没有重复数字,pre指向cur

    class Solution:
        def deleteDuplicates(self, head: ListNode) -> ListNode:
            if not head or not head.next:  # 空链表或单即节点链表
                return head
    
            dummy = ListNode(0)    # 定义哑节点
            dummy.next = head
            pre = dummy            # 哑节点指针
            cur = head             # 链表指针
            flag = False           # 标记是否重复
            while cur:
                while cur.next and pre.next.val == cur.next.val:
                    cur = cur.next   # 将所有重复节点标记为True
                    flag = True
                if flag is True:     # 重复节点就跳过
                    pre.next = cur.next
                    flag = False
                else:
                    pre = cur        # 不重复就下一个节点
                cur = cur.next
            return dummy.next

    206. 反转链表

    反转一个单链表。

    思路1:迭代,每次存储前一个节点,并让当前节点的next指针指向前一个节点

    思路2:递归,假设我子节点下的所有节点都已经反转好了,现在就剩我和我的子节点没有完成最后的反转了,所以反转一下我和我的子节点。

    # 迭代
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            pre = None
            cur = head
            while cur:
                temp = cur.next   # 存储节点的下一位
                cur.next = pre    # 指向前驱节点
                pre = cur         
                cur = temp        # cur指向原来的下一位
            return pre
    # 递归
    class Solution:
        def reverseList(self, head: ListNode) -> ListNode:
            if not head or not head.next:
                return head
            p = self.reverseList(head.next)
            head.next.next = head
            head.next = None
            return p

    92. 反转链表 II

    反转从位置 mn 的链表。请使用一趟扫描完成反转。

    思路:用双指针法,现将慢指针移动到要反转的部分的前一个节点,用另一个指针指向慢指针后面的节点,然后两两交换节点

    class Solution:
        def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
            dummy = ListNode(None)
            dummy.next = head
            pre = dummy
            for i in range(1, m):
                pre = pre.next         # 前驱指针移动到位置m
            cur = pre.next
            for i in range(m, n):      # 两两交换节点
                temp = cur.next        
                cur.next = temp.next   # cur一直不变,只修改指针到下一个位置
                temp.next = pre.next   # temp.next指向pre的next,也就是最新的第m个位置
                pre.next = temp        # 更新temp为最新的第m个位置
            return pre

    21. 合并两个有序链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    思路:建立新链表,依次按升序链接两个链表的元素

    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            dummy = ListNode(None)
            pre = dummy
            while l1 and l2:
                if l1.val < l2.val:
                    pre.next = l1
                    l1 = l1.next
                else:
                    pre.next = l2
                    l2 = l2.next
                pre = pre.next
            pre.next = l1 if l1 else l2
            return dummy.next

    86. 分隔链表

    给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。

    思路:创建双链表,一个存储小于x的值,一个存储大于x的值

    class Solution:
        def partition(self, head: ListNode, x: int) -> ListNode:
            before = befornHead = ListNode(None)
            after = afterHead = ListNode(None)
            while head:
                if head.val < x:
                    before.next = head
                    before = before.next
                else:
                    after.next = head
                    after = after.next
                head = head.next
                after.next = None
            before.next = afterHead.next
            return befornHead.next

    148. 排序链表

    O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

    思路:归并排序,找中点和合并操作

    # 归并排序(递归),空间复杂度O(n)
    class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            if not head or not head.next:
                return head
            slow, fast = head, head.next
            while fast and fast.next:
                slow, fast = slow.next, fast.next.next
            mid = slow.next
            slow.next = None
            left = self.sortList(head)
            right = self.sortList(mid)
            h = res = ListNode(0)
            while left and right:
                if left.val < right.val: 
                    h.next, left = left, left.next
                else: 
                    h.next, right = right, right.next
                h = h.next
            h.next = left if left else right
            return res.next
    # 快速排序
    class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            if head is None:
                return head
            # 分成三个链表,分别是比轴心数小,相等,大的数组成的链表
            big = None
            small = None
            equal = None
            cur = head
            while cur:
                temp = cur
                cur = cur.next
                if temp.val < head.val:
                    temp.next = small
                    small = temp
                elif temp.val > head.val:
                    temp.next = big
                    big = temp
                else:
                    temp.next = equal
                    equal = temp
            # 拆完各自排序即可,equal 无需排序
            big = self.sortList(big)
            small = self.sortList(small)
    
            ret = ListNode(None)
            cur = ret
            # 将三个链表组合成一起
            # 可以同时返回链表的头指针和尾指针加速链表的合并。
            for p in [small, equal, big]:
                while p is not None:
                    cur.next = p
                    p = p.next
                    cur = cur.next
                cur.next = None
            return ret.next

    143. 重排链表

    给定一个单链表 LL0→L1→…→Ln-1→Ln , 将其重新排列后变为: L0→LnL1→Ln-1→L2→Ln-2→…

    思路:找到中点断开,翻转后面部分,然后合并前后两个链表

    class Solution:
        def reorderList(self, head: ListNode) -> None:
            """
            Do not return anything, modify head in-place instead.
            """
            if not head or not head.next:
                return head
            slow, fast = head, head
            # 找到链表中点
            while fast.next and fast.next.next:   
                slow = slow.next
                fast = fast.next.next
            # 反转后半部分
            print(slow.next)
            right = None
            cur = slow.next
            while cur:
                temp = cur.next
                cur.next = right
                right = cur
                cur = temp
            # 将反转的后半部分插入到前半部分
            left = head
            while left and right:
                slow.next = right.next
                right.next = left.next
                left.next = right
                left = right.next
                right = slow.next

    141. 环形链表

    给定一个链表,判断链表中是否有环。

    思路1:哈希表,统计每个元素出现的次数

    思路2:快慢指针,快慢指针相同则有环,证明:如果有环每走一步快慢指针距离会减 1

    # 哈希表
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            dic = {}
            while head:
                if head in dic:
                    return True
                else:
                    dic[head] = 1
                head = head.next
            return False
    # 快慢指针
    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            if head is None or head.next is None:
                return False
            slow = head
            fast = slow.next
            while fast and fast.next:
                fast = fast.next.next
                slow = slow.next
                if fast == slow:
                    return True
            return False

    142. 环形链表 II

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

    思路:快慢指针,快慢相遇之后,慢指针回到头,快慢指针步调一致一起移动,相遇点即为入环点

    class Solution:
        def detectCycle(self, head: ListNode) -> ListNode:
            fast, slow = head, head
            while True:
                if not (fast and fast.next):
                    return 
                slow = slow.next
                fast = fast.next.next
                if slow == fast:
                    break
            fast = head
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return fast

    138. 复制带随机指针的链表

    给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
    要求返回这个链表的 深拷贝

    思路:1、hash 表存储指针,2、复制节点跟在原节点后面

    class Solution:
        def copyRandomList(self, head: 'Node') -> 'Node':
            if not head:
                return
            dic = {}
            dic[None] = None
            cur = head
            while cur:
                if cur not in dic:
                    dic[cur] = Node(cur.val)     # 将当前未拷贝的节点放入字典中
                if cur.random not in dic:
                    dic[cur.random] = Node(cur.random.val)   # 将当前未拷贝的random指针放入字典中
                dic[cur].random = dic[cur.random]
                if cur.next not in dic:
                    dic[cur.next] = Node(cur.next.val)     # 将当前未拷贝的next指针放入字典中
                dic[cur].next = dic[cur.next]
                cur = cur.next
            return dic[head]

    234. 回文链表

    请判断一个链表是否为回文链表。

    思路1:将值复制到数组中,时间复杂度O(n),空间复杂度O(n)

    思路2:快慢指针,先找到链表中点,然后反转后半部分,再与前半部分比较,时间复杂度O(n)空间复杂度O(1)

    # 将值复制到数组中
    class Solution:
        def isPalindrome(self, head: ListNode) -> bool:
            visit = []
            cur = head
            while cur:
                visit.append(cur.val)
                cur = cur.next
            return visit == visit[::-1]
    # 找中点 -> 反转 -> 比较
    class Solution:
        def isPalindrome(self, head: ListNode) -> bool:
            pre = None
            slow, fast = head, head
            while fast and fast.next:
                slow = slow.next      # 使慢指针指向中间节点
                fast = fast.next.next
            while slow:  # 反转后半部分,pre指向反转部分
                temp = slow.next
                slow.next = pre
                pre = slow
                slow = temp
            while head and pre:   # 比较两部分是否相同
                if head.val != pre.val:
                    return False
                head = head.next
                pre = pre.next
            return True
    展开全文
  • 标识符在Java中,标识符多用于类名、方法、字段、变量和包名等,他命名...关键字 Java关键字是电脑语言里事先定义的,有特别意义标识符,有时又叫保留字,还有特别意义变量。Java关键字对Java编译器有特...
  • 前言有的小伙伴说没有学过数据结构,对链表不是特别了解,所以今天我们就来对链表进行一个系统的总结,另外大家如果想提高算法思想的话,我建议还是要系统的学一下数据结构的。...链表的定义:定义:链表是一种递归...
  • 算法(第4版) (豆瓣)一书中对链表的定义如下:链表是一种递归的数据结构,它或者为空(null),或者是指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。链表(Linked list)是一种常见的基础...
  • 指示可以引用定义常量值字段 来自本机代码。注释可被以下工具用作提示: 生成本机头文件以确定头文件是否 必需,如果是,它应该包含什么声明。 然而,在阅读Java源代码时,我注意到在类@Native和Integer中,Long...
  • 在MATLAB中有15种基本数据类型:8种整型数据类型、单精度浮点型(float)、精度浮点型(double)、逻辑型(logical)、字符串型(char)、单元数组型(cell)、结构体类型(struct)和函数句柄型(function_handle)。...
  • 由于学校作业要求,需要使用链表来存储任意长的整数(包括正数和负数),借鉴了许多网上资料后,成功改造了轮子,于是把经验分享在这里,欢迎大家讨论: 首先是定义链表元素: 注意: malloc和free函数是配对,...
  • 学习目标了解C语言基本数据类型了解变量基本概念了解变量使用方法了解了变量命名方法了解格式占位符了解变量输出了解C语言程序基本数据类型及概念使用方法在C语言编程中,系统定义了多种数据类型,本...
  • 叫float,大小为24个字节(我这里Python3.6是这样,别版本不清楚),本身就是精度(你打个特别长小数,最后它会给你截止到15-16位有效数字,这是精度浮点数典型特征)。python中浮点数处理请问为什么是0....
  • 本个题目我们采用指针的方法进行解决, 但是这里有需要注意的地方,根据 好子数组 的定义,当我们使用指针的方法时,会发现当固定左边端点时,符合 恰好有 KK 个不同整数 的子区间的右端点并不是唯一的。...
  • 对于由较高协变导数正则化一般N $$ \ mathcal {N} $$ = 1超对称规理论,我们证明了以所有阶数表示,以裸耦合定义的β函数是由相对于总导数积分给出 循环运动。 借助于用于该证明技术,可以构造一种用于...
  • 在编写程序中,数据类型(data type)定义了使用存储空间方式。通过定义数据类型,告诉编译器怎样创建一片特定存储空间,以及怎样去操作这片存储空间。 C/C++中有四个基本内置数据类型。char是用于存储字符...
  • 下手,这里我也是听了别人分析才知道解这道题要使用指针思想,我们定义两个指针分别为s1和s2,s1指针首先从第一个数开始,由于 题目要求我们至少包括两个数,我们让s2从s1下一个位置开始即可。我们分析清楚...
  • 数据结构的定义 采用双向链表存储任意长整数双向链表的定义如下 class DblList ( private: DblNode *head, *tail; DblNode *current; int sign; public: 构造函数析构函数 构造函数 析构函数 生成一个双向链表存储...
  • printf("* 求两个任意长整数的和 *\n\n"); printf("* *\n\n"); printf("********************************\n\n"); printf("* 注意:输入时每四位用逗号隔开 *\n\n"); printf("* 如:123456789 *\n\n"); ...
  • 解法一:单次循环def num(n): i=1 c=1 h=0 while i&lt;=n: c*=i h+=c print(c) i+=1 print(h) num(n)解法二:while循环def num(n): row=1 h=0 while row&lt;=n:...
  • 定义函数main(),输入正整数n,计算并输出下列算式值。要求调用函数f(n)计算n*(n+1)…(2n-1),函数返回值类型是double。 输入格式: 输入在一行中给出一个正整数n。 输出格式: 在一行中按照“sum = S”格式输出...
  • 定义函数main(),输入正整数n,计算并输出下列算式值。要求调用函数f(n)计算n+(n+1)+…+(2n-1),函数返回值类型是double。 输入格式: 输入在一行中给出一个正整数n。 输出格式: 在一行中按照“sum = S”格式...
  • 关于单引号与引号一些问题: 转义字符 常用字符串函数 Python中字符串驻留机制: 链式赋值 使用这个方法会很方便进行变量交换 比起c++代码要见到多了,c++代码: int a=1,b=2,t; t = b; b = a; a = t; ...
  • 定义函数main(),输入正整数n,计算并输出下列算式值。要求调用函数f(n)计算n*(n+1)…(2n-1),函数返回值类型是double。 s= 1+1/2*3 +1/​3∗4∗5 ​ ​​ ​​ 输入格式: 输入在一行中给出一个正整数n。 输出格式...
  • json的定义

    2016-07-24 14:07:07
    一:json的定义有 (1)数据在键值对中 (2)数据有逗号分隔 (3)花括号保存对象 (4)方括号保存数组 二:JSON值可以是: (1)数字(整数或浮点数) (2)字符串(在引号中) (3)逻辑值(true或...
  • 常量的定义

    2017-03-09 14:08:00
    常量:在java程序运行过程中,值不会发生改变 ... (2)整数常量 -所有的整数  eg:77  (3)小数常量 -所有小数  eg:11.33  (4)字符常量 -用单引号括起来单个字符  eg:'a' , '0'  (5)boolean...
  • 给出一个函数f(x, y)和一个目标结果z,请你计算方程f(x,y) == z所有可能整数 数对x 和 y。 给定函数是严格单调,也就是说: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) 函数接口定义如下: ...
  • 在 JavaScript 中, Number 是一种 定义为 64位精度浮点型(double-precision 64-bit floating point format) (IEEE 754)数字数据类型。结构如下:【备注】所有数字以二进制存储,每个数字对应二进制分为三段:...
  • 在 JavaScript 中, Number 是一种 定义为 64位精度浮点型(double-precision 64-bit floating point format) (IEEE 754)数字数据类型。结构如下:【备注】所有数字以二进制存储,每个数字对应二进制分为三段:...
  • String对象最多能容纳字符 最长...形式定义一个字符串,那么引号里面ASCII字符最多只能有 65534 个。 为什么呢?因为在class文件规范中, CONSTANT_Utf8_info表中使用一个16位无符号整数来记录字符串...
  • [Java教程]JAVA变量类型,定义变量02015-05-23 00:00:10JAVA中常用数据类型数据类型数据类型解释说明char字符型用于存储单个字符,如:性别“男”、“女”,电灯“开”、“关”int整形用于存储整数,如一天...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,493
精华内容 597
关键字:

双整数的定义