今日学习大整数类和STL知识点的复习，以及竞赛题目选讲。
目录
大整数类的引入与声明
大整数类的四则运算
大整数类的比较
总结
大整数类的引入与声明
在C语言中，长度较长的数字通常使用高精度——也就是使用数组存储该长数字的每一位。C++中也可以使用类似的方法，但是STL和类（结构体）的存在可以使高精度使用更加方便：
C++中STL的存在可以使用不定长数组vector代替C中的定长数组，不需要考虑数字位数且不会浪费空间；
C++中类的存在可以在vector的基础上添加构造函数和其他成员函数（多用运算符重载函数）
所以可以定义以下的结构体BigInteger存储高精度的非负整数：
struct BigInteger{
//首先定义两个静态成员变量————规定vector中每一个元素可以存储的最大数据
static const int BASE = 100000000; //应用于使用数字赋值
static const int WIDTH = 8; //应用于使用字符串赋值
//接着定义vector
vector s;
//构造函数
BigInteger(long long num=0){*this=num;}
//使用数字赋值的赋值运算符重载
BigInteger operator=(long long num)
{
s.clear() //赋值则先清除原有数据
do{
s.push_back(num%BASE); //这里保证了vector中存储的每个元素都在int范围内
num/=BASE;
}while(num>0);
}
//使用字符串赋值的运算符重载
BigInteger operator=(const string& str)
{
s.clear();
int x,len=(str.length()-1)/WIDTH+1; //判断需要几个元素来存储
for(int i=0;i
对于初学者这是一段含金量较高的代码。首先定义了两个静态成员变量，分别用于限制数字赋值和字符串赋值的情况下存储进vector的数字大小不超过int：
众所周知有符号的int型最大数据为2147483647（一共10位），所以取BASE为8位，且代码保证进入vector的数据都小于BASE，所以一定不会超限。
同理，取WIDTH为8保证了每一次只录入长度≤8的数据，小于int。
在字符串方式赋值中有一些比较重要的字符串处理函数，比如sscanf函数和sprintf函数：
sscanf和scanf的区别在于数据来源——scanf我们很熟悉，是以键盘为输入源；但是sscanf却是以字符串为输入源：
sscanf(const char* str1,"%d",&var); //表示从str1中读取数据并自动转为数字存储在变量var中
这里“自动转为数据”是一个很奇妙的过程。比如字符串是字符“1234”的组合，通过上述步骤var中得到的是真正int型1234。还有一种方法是使用字符串流 strstringstream。
同理sprintf(const char* str2,"%d",var)就是将数字var转成字符串形式，“输出”目标不是屏幕而是str2。
同时注意如果第一个参数是个string类型，不适用，具体操作后面会介绍。
其次是C++字符串类型自带的substr函数，可以写为str.substr(start,n)，表示取出原字符串中下标从start开始的长度为n的子字符串，返回值同样是string。
那很容易就可以想到，可以将本函数和上面的sscanf结合起来，把子字符串作为输入源。但是由于string类型不能作为sscanf的第一个参数，所以引入函数string类型的库函数c_str()，写作str.c_str()，作用是将string类型的第一个元素值返回，达到的是一个将C++风格字符串转换为C风格的字符数组的效果。
此处还可以定义大整数类的流运算符重载，即通过cin>>x和cout<
//流输入运算符>>的重载
istream& operator>>(istream &in,BigInteger& x)
{
string s;
if(!(in>>s)) //确保有输入
return in;
x=s; //使用了赋值运算符的重载
return in;
}
//流输出运算符<<的重载
ostream& operator<<(ostream &out,const BigInteger& x)
{
out<=0;i--){ //从倒数第二个元素开始，从后往前输入（存储反序）
char buf[20];
sprintf(buf,"%08d",x.s[i]); //格式化输出，输出目标为buf
for(int j=0;j
这样一个大整数类的定义及赋值、输入输出运算符重载就算完成了。
大整数类的四则运算
以加法为例，核心步骤为 取余+进位：
//以下内容定义在结构体内部定义
BigInteger operator+(const BigInteger& b) const
{
BigInteger c;
c.s.clear();
for(int i=0,g=0;;i++){
if(g==0&&i>=s.size()&&i>=b.s.size()) //判断计算完成
break;
int x=g; //g为上一阶层保留下来的剩余值
if(i
根据+可以进一步定义+=：函数中调用+的重载实现
BigInteger operator+=(const BigInteger& b){
*this=*this+b;
return *this;
}
大整数类的比较
只需要定义一个小于，其他符号都可以通过小于的变化得到（类似于上面+=运用了+的性质）
//定义在结构体中
bool operator<(const BigInteger& b)const{
if(s.size()!=b.s.size())
return s.size()=0;i--){ //位数相等，从后往前（此高位往低位）比较
if(s[i]!=b.s[i])
return s[i]
上面算法成立的前提是没有前导零（不然计算正确但是比较乱套）。那么同理可以通过小于运算符定义出其他所有运算符：
bool operator > (const BigInteger& b) const{return b<*this;}
bool operator <=(const BigInteger& b) const{return !(b<*this);}
bool operator >=(const BigInteger& b) const{return !(*this
总结
说一些我的心得体会吧。自学算法竞赛内容第五天，发现竞赛写代码的思维和普通的工程思维还是有很大的不同。就看大整数类，虽说是类，但是上面使用的都是结构体（这俩其实是一个东西）——省去了private和public的麻烦，这在工程上会导致数据的泄露（破坏封装性），但是在算法竞赛中不但节省了时间和脑力，还能减少“可不可访问”的很多问题。如果严格使用类操作，可能读取private数据都需要单独写函数，麻烦至极。
今日完，明学习栈和队列（进阶）以及链表
