Skip to content

Instantly share code, notes, and snippets.

@masquevil

masquevil/bigInt.cpp

Last active August 29, 2015 14:08
Show Gist options
  • Save masquevil/9dea041c139169bc951f to your computer and use it in GitHub Desktop.
Save masquevil/9dea041c139169bc951f to your computer and use it in GitHub Desktop.
Download ZIP
Try Big Int (C++)
Raw
bigInt.cpp
#include<iostream>
#include<string>
#include<time.h>
#include "bigInt.h"
using namespace std;
BigInt::BigInt(){ //构造函数
head = tail = temp = NULL;
symbol = '+';
length = 0;
}
BigInt::BigInt(const BigInt &bigNum){ //复制构造函数
NumUnit *p;
head = tail = temp = NULL;
symbol = bigNum.symbol;
length = 0;
p = bigNum.tail;
while (p){
insertHead(p->num);
p = p->prev;
}
}
BigInt::~BigInt(){ //析构函数
if (head == NULL) return;
NumUnit *next;
temp = head;
while (temp){
next = temp->next;
delete temp;
temp = next;
}
head = tail = temp = NULL;
}
void BigInt::randBigNum(){ //随机产生数
int MAX = rand() % 50;
for (int i = 1; i < MAX; i++){
insertHead(rand() % 10);
}
insertHead(rand() % 9 + 1);
}
void BigInt::insertHead(int num){ //插入到头部
temp = new NumUnit;
temp->num = num;
temp->prev = NULL;
if (!head){
head = tail = temp;
temp->next = NULL;
}
else{
temp->next = head;
head->prev = temp;
head = temp;
}
length++;
}
void BigInt::deleteHead(){ //头部为0时删除头部
temp = head;
head = head->next;
delete temp;
length--;
if (length == 0) symbol = '+'; //长度为0时，符号为+
}
BigInt BigInt::operator + (const BigInt &bigNum) const{ // + 的重载
BigInt result;
NumUnit *num1 = tail, *num2 = bigNum.tail;
int sum, carry = 0;
if (symbol != bigNum.symbol){
result = *this - bigNum;
return result;
}
result.symbol = symbol;
while (num1 && num2){
sum = num1->num + num2->num + carry;
carry = sum / 10;
sum %= 10;
result.insertHead(sum);
num1 = num1->prev;
num2 = num2->prev;
}
if (num2)num1 = num2;
while (num1){
sum = num1->num + carry;
carry = sum / 10;
sum %= 10;
result.insertHead(sum);
num1 = num1->prev;
}
if (carry)
result.insertHead(carry);
return result;
}
BigInt BigInt::operator - (const BigInt &bigNum) const{ // - 的重载
BigInt result;
NumUnit *num1 = tail, *num2 = bigNum.tail;
int sub, carry = 0;
if (symbol != bigNum.symbol){
result = *this + -bigNum;
return result;
}
if (*this < bigNum){
result = -(bigNum - *this);
return result;
}
result.symbol = symbol;
while (num1 && num2){
sub = num1->num - num2->num - carry;
sub += 10;
carry = 1 - (sub / 10);
sub %= 10;
result.insertHead(sub);
num1 = num1->prev;
num2 = num2->prev;
}
if (num2)num1 = num2;
while (num1){
sub = num1->num - carry;
sub += 10;
carry = 1 - (sub / 10);
sub %= 10;
result.insertHead(sub);
num1 = num1->prev;
}
if (carry)
result.insertHead(carry);
while (result.head && !result.head->num){
result.deleteHead();
}
return result;
}
BigInt BigInt::operator - () const{ // - (负号)的重载
BigInt result = *this;
result.symbol = symbol == '+' ? '-' : '+';
return result;
}
BigInt BigInt::operator = (const BigInt &bigNum){ // = 的重载
if (this == &bigNum)return *this;
NumUnit *p;
temp = head = tail = NULL;
length = 0;
symbol = bigNum.symbol;
p = bigNum.tail;
while (p){
insertHead(p->num);
p = p->prev;
}
return *this;
}
bool BigInt::operator < (const BigInt &bigNum) const{ // < 的重载
if (symbol == '-'){
if (bigNum.symbol == '+')return true;
if (length > bigNum.length || (length == bigNum.length && head->num > bigNum.head->num))return true;
}
else if (bigNum.symbol == '-')return false;
else if (length < bigNum.length || (length == bigNum.length && head->num < bigNum.head->num))return true;
return false;
}
int BigInt::getLength(){
return length;
}
void BigInt::display(){
if (head){
if (symbol == '-')cout << symbol;
cout << head->num;
temp = head->next;
}else{
cout << 0 << endl;
return;
}
while (temp){
cout << temp->num;
temp = temp->next;
}
cout << endl;
}
int main(){
BigInt a, b, sum, sub1, sub2;
srand((unsigned)time(NULL));
a.randBigNum();
b.randBigNum();
cout << "a = ";
a.display();
cout << "b = ";
b.display();
sum = a + b;
cout << "a + b = ";
sum.display();
sub1 = a - b;
cout << "a - b = ";
sub1.display();
sub2 = b - a;
cout << "b - a = ";
sub2.display();
return 0;
}
Raw
bigInt.h
struct NumUnit{
int num;
NumUnit *next, *prev;
};
class BigInt{
private:
NumUnit *head, *tail, *temp;
int length;
char symbol;
void insertHead(int num);
void deleteHead();
public:
BigInt();
BigInt(const BigInt &bigNum);
BigInt operator + (const BigInt &bigNum) const;
BigInt operator - (const BigInt &bigNum) const;
BigInt operator - () const;
BigInt operator = (const BigInt &bigNum);
bool operator < (const BigInt &bigNum) const;
int getLength();
void randBigNum();
void display();
~BigInt();
};
Raw
cpp文件的说明
#include<iostream>
#include<string>
#include<time.h>
#include "bigInt.h" //yu 在这里引入了自定义的头文件
using namespace std;
BigInt::BigInt(){ //构造函数 //yu 构造函数创建一个空的对象
head = tail = temp = NULL;
symbol = '+';
length = 0;
}
BigInt::BigInt(const BigInt &bigNum){ //复制构造函数 //yu 也叫拷贝构造函数
/* 关于拷贝构造函数，需要注意的是，与析构函数相同，一般情况下不需要自定义。有默认的拷贝构造函数
* 但是默认只能执行浅拷贝，即令新对象的所有元素与旧对象的所有元素值相等，如 b.x = a.x，遇到指针时，就会出现错误
* 让两个指针的值相等，b.p = a.p，以为着让 b.p这个指针，指向 a.p这个指针所指的空间。那么如果 a.p所指的空间被删除，b.p就会指向一个错误的地址
* 因此，拷贝构造函数的目的就是为所有的指针新申请一片空间，然后将空间上的值复制过来。
*/
NumUnit *p; //yu p是一个 NumUnit型的指针
head = tail = temp = NULL;
symbol = bigNum.symbol;
length = 0;
//yu 下面这一段代码，在后面的内容中多次用到类似的过程。从对象的一端（这里是尾部tail）开始，如果不为空，则执行一定的操作，循环直到所有的元素都执行
p = bigNum.tail; //yu p指向 bigNum（传进来的参数，也就是要复制的对象）的尾部
while (p){ //yu 当 p不为空时，执行循环
insertHead(p->num); //yu 对当前对象执行 insertHead操作，插入 p的值，也就是 bigNum对应位置的值
p = p->prev; //yu p指向 bigNum中的前一个位置
} //yu 假如初始状态：当前对象为空，bigNum代表大数字123；那么一次循环结束后，p从指向 bigNum的3变为指向 bigNum的2，当前对象变为大数字3
//yu 第二次循环结束后，p变为指向 bigNum的1，当前对象变为23；第三次，p变为指向 NULL（空），当前对象变为123,；之后跳出循环
}
BigInt::~BigInt(){ //析构函数
if (head == NULL) return;
NumUnit *next;
//yu 与上面的过程类似。从头部开始，循环删除元素，释放元素占用的空间
temp = head;
while (temp){
next = temp->next;
delete temp;
temp = next;
}
head = tail = temp = NULL;
}
void BigInt::randBigNum(){ //随机产生数 //yu 作业的要求是对大整数进行随机赋值，这个便是随机赋值的函数
int MAX = rand() % 50; //yu 先生成位数 MAX，值为0 - 49，用rand()除以50取余数，就会得到0 - 49的随机数
//然后用循环插入 MAX位数字，也均为随机产生，范围为 0 - 9
for (int i = 1; i < MAX; i++){
insertHead(rand() % 10); //yu insertHead，插入操作
}
insertHead(rand() % 9 + 1); //yu 最后再插入一位头部，范围为1 - 9，这样最终的随机数就为 1 - 50位
}
void BigInt::insertHead(int num){ //插入到头部
temp = new NumUnit; //yu 为要插入的数分配一个空间 NumUnit是一个结构体，需要用关键字 new来申请空间
temp->num = num; //赋值
temp->prev = NULL; //因为是插入到头部，所以新申请的这个空间的前一个元素肯定为空
if (!head){ //yu 如果对象本身为空，则 head 会指向 NULL，那么执行插入操作后，只有一个元素，所以 head 与 tail 都会指向 temp
head = tail = temp;
temp->next = NULL;
}
else{ //yu 如果本身不为空，则将原先的 head 的 prev指向现在要插入的头（temp），temp的 next 指向 head，最后让 head 指向现在的头
temp->next = head;
head->prev = temp;
head = temp;
}
length++; //yu 大整数的长度增加啦！
}
void BigInt::deleteHead(){ //头部为0时删除头部
temp = head;
head = head->next;
delete temp;
length--;
if (length == 0) symbol = '+'; //长度为0时，符号为+
}
BigInt BigInt::operator + (const BigInt &bigNum) const{ // + 的重载
BigInt result;
NumUnit *num1 = tail, *num2 = bigNum.tail;
int sum, carry = 0;
if (symbol != bigNum.symbol){
result = *this - bigNum;
return result;
}
result.symbol = symbol;
while (num1 && num2){
sum = num1->num + num2->num + carry;
carry = sum / 10;
sum %= 10;
result.insertHead(sum);
num1 = num1->prev;
num2 = num2->prev;
}
if (num2)num1 = num2;
while (num1){
sum = num1->num + carry;
carry = sum / 10;
sum %= 10;
result.insertHead(sum);
num1 = num1->prev;
}
if (carry)
result.insertHead(carry);
return result;
}
BigInt BigInt::operator - (const BigInt &bigNum) const{ // - 的重载
BigInt result;
NumUnit *num1 = tail, *num2 = bigNum.tail;
int sub, carry = 0;
if (symbol != bigNum.symbol){
result = *this + -bigNum;
return result;
}
if (*this < bigNum){
result = -(bigNum - *this);
return result;
}
result.symbol = symbol;
while (num1 && num2){
sub = num1->num - num2->num - carry;
sub += 10;
carry = 1 - (sub / 10);
sub %= 10;
result.insertHead(sub);
num1 = num1->prev;
num2 = num2->prev;
}
if (num2)num1 = num2;
while (num1){
sub = num1->num - carry;
sub += 10;
carry = 1 - (sub / 10);
sub %= 10;
result.insertHead(sub);
num1 = num1->prev;
}
if (carry)
result.insertHead(carry);
while (result.head && !result.head->num){
result.deleteHead();
}
return result;
}
BigInt BigInt::operator - () const{ // - (负号)的重载
BigInt result = *this;
result.symbol = symbol == '+' ? '-' : '+';
return result;
}
BigInt BigInt::operator = (const BigInt &bigNum){ // = 的重载
if (this == &bigNum)return *this;
NumUnit *p;
temp = head = tail = NULL;
symbol = bigNum.symbol;
length = 0;
p = bigNum.tail;
while (p){
insertHead(p->num);
p = p->prev;
}
return *this;
}
bool BigInt::operator < (const BigInt &bigNum) const{ // < 的重载
if (symbol == '-'){
if (bigNum.symbol == '+')return true;
if (length > bigNum.length || (length == bigNum.length && head->num > bigNum.head->num))return true;
}
else if (bigNum.symbol == '-')return false;
else if (length < bigNum.length || (length == bigNum.length && head->num < bigNum.head->num))return true;
return false;
}
int BigInt::getLength(){
return length;
}
void BigInt::display(){
if (head){
if (symbol == '-')cout << symbol;
cout << head->num;
temp = head->next;
}else{
cout << 0 << endl;
return;
}
while (temp){
cout << temp->num;
temp = temp->next;
}
cout << endl;
}
int main(){
BigInt a, b, sum, sub1, sub2;
srand((unsigned)time(NULL));
a.randBigNum();
b.randBigNum();
cout << "a = ";
a.display();
cout << "b = ";
b.display();
sum = a + b;
cout << "a + b = ";
sum.display();
sub1 = a - b;
cout << "a - b = ";
sub1.display();
sub2 = b - a;
cout << "b - a = ";
sub2.display();
return 0;
}
Raw
h文件的说明
struct NumUnit{ //yu 声明结构体，命名为 NumUnit
int num; //yu 一个 num 型的成员，用于存放大整数的 1位
NumUnit *next, *prev; //yu NumUnit类型的指针，指向大整数的上一位和下一位
};
class BigInt{ //yu 类，存放大整数，命名为BigInt
//yu 以下都为 BigInt类的成员，如果是变量就叫做成员变量，如果是函数就叫做成员函数
private: //yu 私有成员，仅自己和同类的成员可以访问。eg: 自己的访问，如第25行的display()成员函数，可以在其中进行 x = length 或者 length = y 这样的操作
//yu eg: 同类成员的访问，有两个 BigInt 类型的变量 a和b，可以在 b 的 display()中进行 x = a.length 或者 a.length = y 的操作
//yu 不同的类或者变量不能访问，如在 main函数中，就不能进行 x = a.length 或者 a.length = y 的操作
NumUnit *head, *tail, *temp; //yu NumUnit类型的指针，head 指向大整数(BigInt)的首位，tail 指向个位，temp 用于其它临时的操作
int length; //yu 大整数的位数
char symbol; //yu 大整数的符号，“+”或者“-”
void insertHead(int num); //yu 私有成员函数，void代表无返回值，需要一个 int型的参数。这个函数的功能是在大整数的头部插入一个数字
void deleteHead(); //yu 私有成员函数，无返回值，不需要参数。功能：将大整数的头部多于的0删除。
public: //yu 公有成员，任何地方都可以访问，如 main函数中可以使用 a.display();
BigInt(); //yu 无参构造函数。与类的名称相同的函数，被称为构造函数。在声明一个对象时调用。如 BigInt a; a就会调用构造函数。（对象 a出现的时候就要调用，也就意味着这个函数“构造”了 a）
BigInt(const BigInt &bigNum); //yu 有参构造函数。与上一条功能一样，但需要一个参数，所以会在有参数时调用。eg: BigInt a;(调用无参) BigInt b(a);(调用有参)
BigInt operator + (const BigInt &bigNum) const; //yu '+'符号的重载，功能：实现大整数加法，返回值和参数都是 const BigInt型。关于“重载”和“const”的介绍请看28行
BigInt operator - (const BigInt &bigNum) const; //yu '-'符号的重载，功能：实现大整数减法，返回值和参数都是 const BigInt型
BigInt operator - () const; //yu '-'（负号）的重载，功能：实现大整数的符号变化，返回值是 const BigInt型，无参数
BigInt operator = (const BigInt &bigNum); //yu '='的重载，实现大整数的赋值，返回值是 BigInt型，参数是 const BigInt型
bool operator < (const BigInt &bigNum) const; //yu '<'的重载，实现大整数的比较，返回值是 bool型（true和false），参数是 const BigInt型
int getLength(); //yu 公有成员函数（上面的也都是公有成员函数），返回 int类型，该大整数的长度
void randBigNum(); //yu 无返回值，功能：对该大整数进行随机赋值
void display(); //yu 无返回值，显示该大整数
~BigInt(); //yu 析构函数，与构造函数对应，这个是对象被销毁时调用的函数，功能是将对象所占用的空间清空（下详）
};
/*yu 重载，也就是运算符的重载，效果是改变或者增加运算符的功能。如对 + 符号进行改造，甚至可以实现减法功能，使得 5 + 3 输出 2。
* 但是通常重载并不这么用，而是用在自定义的类（class）或者结构体(struct)中，拓展运算符的功能，因为这些运算符本来不支持自定义的类型
* 比如 + 符号，本来只支持 int型、double型等这种数字的类型。但是我们现在想让它支持我们自定义的 BigInt 类，就需要对它进行重载
* 重载的过程，就是告诉程序，在遇到 BigInt + BigInt 的时候，要执行什么样的操作。达到什么样的目的。
* 运算符，本身也是一中函数。所以也需要参数和返回值。如 c = a + b，a和b 就是 '+' 的参数，a+b的返回值和c 就是 '=' 的参数。
*
* const 常数。与数学中的常数（常量）概念一样，就是不能改变的量，与“变量”相对应。
* 如上18行处，第一个 const，在参数的位置，代表传进来的变量是一个常数，也就是在函数执行的过程中，不能对这个变量进行改变。
* 第二个 const，在成员函数声明的最后，代表这个成员函数是“常成员函数”，也就是在函数执行的过程中，不能对对象本身的其它成员进行修改。
* 上面被重载的函数中，只有 '=' 左边的参数（即本身）没有被声明为 const，也就意味着只有 '=' 左边的对象是可以改变的（必须的啦，因为我们要对它进行赋值运算嘛）
*
* 析构函数。一般情况下，程序执行过程中会定义一些变量，申请一些空间，这些空间多在“栈区”，会随着程序的结束，系统自动回收。如 int型变量的空间
* 然而当我们使用到指针、类、结构体，通过关键字 new 申请了一些动态空间，这些空间在“堆区”，不会随着程序的结束而自动回收。
* 因此，我们需要对这些空间进行手动回收。每一个函数或者语句块在执行结束时（即 '}'出现时），会自动回收其内部定义的局部变量。
* 回收的方式，就是调用变量自身的析构函数。默认的析构函数为空，所以平时我们不用写。当我们写了析构函数时，系统就会调用我们写的析构函数。
* 于是我们可以手动回收堆区的空间。我们甚至可以在析构函数中做一些其他的事，比如 cout<<"hello"，这样的语句也可以正确执行。
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment