目录

一、问题与要求

二、程序设计的基本思想，原理和算法描述：

三、源程序及注释

四、运行输出结果：

源代码：

---

一、问题与要求

问题：1、大整数运算C++中整型的表示范围受限，但在某些领域存在大整数（如位数>20）的计算。请使用线性表实现大整数的加法和乘法，并分析算法时间复杂度。

要求：顺序表类用C++的模板实现

算法用流程图和伪代码的形式分别描述，并分析算法时间复杂度

二、程序设计的基本思想，原理和算法描述：

（包括程序的结构，数据结构，输入/输出设计，符号名说明等）

1. 自然语言：首先在头文件中定义顺序表类，在public中声明函数，private中创建固定数组和数据长度，在具体的加法函数实现中记录进位变量，用短的数据长度次进行循环相加进位，并用array数组接收，每经过一次循环，两个数据长度减一，较长的数据长度继续进行进位操作，若最后还有一位进位，存入array数组，由于存入数组的顺序是从右向左，为逆序，因此需要正序存入data数组中。

时间复杂度：O(N)

1. 伪代码：

3.流程图：

三、源程序及注释

三个文件：

大数相加.h

大数相加函数.cpp

大数相加测试.cpp

四、运行输出结果：

五、源代码：

大数相加.h:

#include<iostream>
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;
}