一、问题与要求
问题：1、大整数运算C++中整型的表示范围受限，但在某些领域存在大整数（如位数>20）的计算。请使用线性表实现大整数的加法和乘法，并分析算法时间复杂度。
要求：顺序表类用C++的模板实现
算法用流程图和伪代码的形式分别描述，并分析算法时间复杂度
二、程序设计的基本思想，原理和算法描述：
（包括程序的结构，数据结构，输入/输出设计，符号名说明等）
自然语言：首先在头文件中定义顺序表类，在public中声明函数，private中创建固定数组和数据长度，在具体的加法函数实现中记录进位变量，用短的数据长度次进行循环相加进位，并用array数组接收，每经过一次循环，两个数据长度减一，较长的数据长度继续进行进位操作，若最后还有一位进位，存入array数组，由于存入数组的顺序是从右向左，为逆序，因此需要正序存入data数组中。
时间复杂度：O(N)
伪代码：
3.流程图：
三、源程序及注释
三个文件：
大数相加.h
大数相加函数.cpp
大数相加测试.cpp
四、运行输出结果：
五、源代码：
大数相加.h:
include
using namespace std;
class Seqlist
{
public:
Seqlist(){length = 0;}
Seqlist(int a[], int n);
~Seqlist(){}
void SeqlistAdd(Seqlist A,Seqlist B,int array[]);
void Print_sum();
int count();
private:
int num[100];
int length;
};
extern int sub;
extern int E[1000];
Seqlist::Seqlist(int a[],int n)//将数组的值传入顺序表中
{
for(int i=0;i<n;i++)
{
num[i]=a[i];
}
length=n;
}
void Seqlist::SeqlistAdd(Seqlist A,Seqlist B,int array[])
{
int a=A.length,b=B.length;
int sh=a<b?a:b;//选择短的数据长度
int m=a-1,n=b-1;//两个数组下标
sub=0;//和数组下标
int jw=0;//产生的进位
for(int i=0;i<sh;i++)
{
int add=A.num[m--]+B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(m>=0)
{
int add=A.num[m--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(n>=0)
{
int add=B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
if(jw)
{
array[sub++]=jw;
}
length=sub;
for(int i=0;i<length;i++)
{
num[i]=array[length-i-1];
}
}
void Seqlist::Print_sum()
{
for(int i = 0; i < length; i++){
cout << num[i];
}
}
int Seqlist::count()
{
return length;
}
大数相加函数.cpp：
include"大数相加.h"
int sub;
int E[1000];
Seqlist::Seqlist(int a[],int n)//将数组的值传入顺序表中
{
for(int i=0;i<n;i++)
{
num[i]=a[i];
}
length=n;
}
void Seqlist::SeqlistAdd(Seqlist A,Seqlist B,int array[])
{
int a=A.length,b=B.length;
int sh=a<b?a:b;//选择短的数据长度
int m=a-1,n=b-1;//两个数组下标
sub=0;//和数组下标
int jw=0;//产生的进位
for(int i=0;i<sh;i++)
{
int add=A.num[m--]+B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(m>=0)
{
int add=A.num[m--]+jw;
array[sub++]=add%10;
jw=add/10;
}
while(n>=0)
{
int add=B.num[n--]+jw;
array[sub++]=add%10;
jw=add/10;
}
if(jw)
{
array[sub++]=jw;
}
length=sub;
for(int i=0;i<length;i++)
{
num[i]=array[length-i-1];
}
}
void Seqlist::Print_sum()
{
for(int i = 0; i < length; i++){
cout << num[i];
}
}
大数相加主程序.cpp:
include"大数相加.h"
int sub;
int E[1000]; //逆序数组变量
int main()
{
int m;
cout<<"请输入位数：";
cin>>m;
int arr1[m];
cout<<endl<<"请输入数字：";
for(int i=0;i<m;i++)
{
cin>>arr1[i];
}
cout<<endl;
int n;
cout<<"请输入位数：";
cin>>n;
int arr2[n];
cout<<endl<<"请输入数字：";
for(int i=0;i<n;i++)
{
cin>>arr2[i];
}
Seqlist A(arr1,m);
Seqlist B(arr2,n);
Seqlist sum;
sum.SeqlistAdd(A, B, E);
cout<<"位数为："<<sum.count()<<endl;
cout << "大数相加：" << endl;
A.Print_sum();
cout << " + " << endl;
B.Print_sum();
cout << " = " << endl;
sum.Print_sum();
cout << endl << endl;
return 0;
}
