顺序线性表之大整数求和C++落成

顺序线性表之大整数求和

顺序线性表之大整数求和C++实现,线性求和

顺序线性表之大整数求和

 

大整数求和伪代码
  1、初始化进位标志 flag=0;
  2、求大整数 A 和 B 的长度:
    int aLength = a.GetLength();
    int bLength = b.GetLength();
  3、从各位开始逐位进行第 i 位的加法,直到 A 或 B 计算完毕:
    3.1、计算第 i 位的值:c.Insert(i+1, (a.GetElement(i + 1) +
b.GetElement(i + 1) + flag) % 10);
    3.2、计算该位的进位:flag = (a.GetElement(i + 1) +
b.GetElement(i + 1) + flag) / 10;
  4、计算大整数 A 或 B 余下的部分;
  5、计算结果的进位
注:用数组来存放大整数

一、顺序线性表头文件:SeqList.h

//顺序线性表的头文件
#include<iostream>

const int MaxSize = 100;
//定义顺序表SeqList的模板类
template<class DataType>
class SeqList{
public:
  //顺序表无参构造器(创建一个空的顺序表)
  SeqList(){ length = 0; }
  //顺序表有参构造器(创建一个长度为n的顺序表)
  SeqList(DataType array[], int n);
  //顺序表析构函数
  ~SeqList(){}
  //求顺序表的长度
  int GetLength(){ return length; }
  //顺序表按位查找,返回i位置的元素
  DataType GetElement(int i);
  //顺序表按值查找,返回该元素所在的位置
  int GetLocal(DataType x);
  //顺序表在指定的位置插入指定的元素
  void Insert(int i, DataType x);
  //顺序表删除元素,返回删除的元素
  DataType Delete(int i);
  //输出顺序表中的元素
  void PrintSeqList();
private:
  //一维数组,存放数据元素
  DataType data[MaxSize];
  //顺序表的长度
  int length;
};

//实现顺序表有参构造器
template<class DataType>
SeqList<DataType>::SeqList(DataType array[], int n)
{
  if (n > MaxSize)
  {
    throw “传入的顺序表长度过长”;
  }
  //给顺序表的存储元素的数组赋值
  for (int i = 0; i < n; i++)
  {
    data[i] = array[i];
  }
  //给顺序表的长度赋值
  length = n;
}

//实现顺序表按位查找
template<class DataType>
DataType SeqList<DataType>::GetElement(int i)
{
  //判断是定的位置是否合理
  if (i < 1 || i >length)
  {
    throw “位置有误”;
  }
  else
  {
    //返回指定位置的元素
    return data[i – 1];
  }
}

//实现顺序表按值查找,返回该元素所在的位置
template<class DataType>
int SeqList<DataType>::GetLocal(DataType x)
{
  //遍历顺序表的元素
  for (int i = 0; i < length; i++)
  {
    //判断指定的元素是否在顺序表中
    if (data[i] == x)
    {
      //返回指定元素在顺序表中的位置
      return (i + 1);
    }
  }
  //如果指定的元素不在顺序表中,则返回位置为0
  return 0;
}

//实现顺序表插入元素
template<class DataType>
void SeqList<DataType>::Insert(int index, DataType x)
{
  //判断插入的位置是否合理
  if (length >= MaxSize)
  {
    throw “顺序表已存放满”;
  }
  if (index<1 || index>length + 1)
  {
    throw “插入元素的位置有误”;
  }
  //如何插入的位置合理,则把顺序表中从最后位置到指定插位置的元素整体向后移动一个位置
  for (int j = length; j >= index; j–)
  {
    data[j] = data[j – 1];
  }
  //给插入的位置放入指定的元素
  data[index – 1] = x;
  length++;
}

//实现顺序表删除指定位置的元素
template<class DataType>
DataType SeqList<DataType>::Delete(int index)
{
  //声明要取出的元素
  DataType x;
  //判断要删除的位置是否合理
  if (index<1 || index>length)
  {
    throw “删除的位置有误”;
  }
  else
  {
    //取出指定位置的元素
    x = data[index – 1];
    //将指定位置后的元素全部都向前移动一个位置
    for (int i = index; i < length; i++)
    {
      data[i – 1] = data[i];
    }
    //删除顺序表中的元素后,其长度减1
    length–;
  }
  return x;
}

//顺序输出顺序表中的元素
template<class DataType>
void SeqList<DataType>::PrintSeqList()
{
  if (length < 1)
  {
    throw “顺序表中没有元素”;
  }
  else
  {
    //顺序输出顺序表元素
    for (int i = 0; i < length; i++)
    {
      cout << data[i] << ” “;
    }
    cout << endl;
  }
}

 二、大整数求和头文件:BidIntegerAdd.h

//顺序线性表之大整数求和
#include<iostream>
//引入顺序线性表的头文件
#include”SeqList.h”
using namespace std;

SeqList<int> Add(SeqList<int>a, SeqList<int>b)
{
  //定义中间变量,顺序线性表
  SeqList<int> c = SeqList<int>();
  //flag 是进位标志,i 为大整数的某一位
  int flag = 0, i = 0;
  //求大整数 a,b 的位数
  int aLength = a.GetLength();
  int bLength = b.GetLength();
  //逐位计算加法直到某个大整数计算完毕
  while (i < aLength&&i < bLength)
  {
    //计算第 i 位的值
    c.Insert(i+1, (a.GetElement(i + 1) + b.GetElement(i + 1) + flag)
% 10);
    //计算第 i 位的进位
    flag = (a.GetElement(i + 1) + b.GetElement(i + 1) + flag) /
10;
    i++;
  }
  //计算大整数 A 余下的部分
  for (; i < aLength; i++)
  {
    c.Insert(i + 1, (a.GetElement(i + 1) + flag) % 10);
    flag = (a.GetElement(i + 1) + flag) / 10;
  }
  //计算大整数 B 余下的部分
  for (; i < bLength; i++)
  {
    c.Insert(i + 1, (b.GetElement(i + 1) + flag) % 10);
    flag = (b.GetElement(i + 1) + flag) / 10;
  }
  //如果最后有进位,则结果会多一位
  if (flag == 1)
  {
    c.Insert(c.GetLength()+1, 1);
  }
  return c;
}

三、测试顺序线性表之大整数求和:TestBigIntegerAdd.h

//测试顺序线性表之大整数求和
#include<iostream>
//引入顺序表之大整数求和头文件
#include”BigIntegerAdd.h”
using namespace std;
int main()
{
  //定义两个顺序线性表
  int array1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  int array2[] = { 1, 1, 1, 1, 1, 1, 1, 1 };
  SeqList<int>a = SeqList<int>(array1,9);
  cout << “第一个大整数是:” << endl;
  a.PrintSeqList();
  SeqList<int>b = SeqList<int>(array2,8);
  cout << “第二个大整数是:” << endl;
  b.PrintSeqList();
  SeqList<int>c = Add(a, b);
  cout << “他们的和是:” << endl;
  c.PrintSeqList();
  return 0;
}

 

顺序线性表之大整数求和 大整数求和伪代码 1、初始化进位标志 flag=0;
2、求大整数 A 和 B 的长…

C++大整数求和算法求解 20C
我们课程设计叫写一个大整数求和的算法,但是在重载加法运算符的时候出现了一个bug,一直不知道错在哪里,怎么改,但是大概知道应该是数据类型不匹配的缘故,可就是不知道到底怎么改,求解!!!
主函数部分:
#include#includeusing namespace std;#include”bigInt.h”//功能函数声明
void menu();//主界面函数 int main() { //测试 string a = “992”; string b
= “74”; bigInt b1;//定义测试数据 bigInt b2; bigInt
temp;//定义一个临时变量用来存储计算结果
我们课程设计叫写一个大整数求和的算法,但是在重载加法运算符的时候出现了一个bug,一直不知道错在哪里,怎么改,但是大概知道应该是数据类型不匹配的缘故,可就是不知道到底怎么改,求解!!!
主函数部分:
#include#includeusing namespace std;#include”bigInt.h”//功能函数声明
void menu();//主界面函数 int main() { //测试 string a = “992”; string b
= “74”; bigInt b1;//定义测试数据 bigInt b2; bigInt
temp;//定义一个临时变量用来存储计算结果 temp = b1 + b2; system; return
0;}

 

bigInt.h:
#ifndef BIG_INT_H#define BIG_INT_H#include//大整数的结构 class
bigInt{public: friend ostream& operator<<(ostream &output, bigInt
&a);//重载输出流运算符 friend bigInt operator+ (bigInt &a, bigInt
&b);//重载加法运算 friend bigInt operator- (bigInt &a, bigInt
&b);//重载减法运算 friend bigInt operator* (bigInt &a, bigInt
&b);//重载乘法运算 friend bigInt operator/ (bigInt &a, bigInt
&b);//重载除法运算 bigInt;//构造函数,初始化表示大整数的这个数组
bigInt();//默认构造函数 ~bigInt();//析构函数 bigInt& operator= (bigInt
&a);//重载赋值运算 private: int * m_bigInt; //顺序表的数组 int
m_length; const int maxCapcity;};#endif

大整数求和伪代码
  1、初始化进位标志 flag=0;
  2、求大整数 A 和 B 的长度:
    int aLength = a.GetLength();
    int bLength = b.GetLength();
  3、从各位开始逐位进行第 i 位的加法,直到 A 或 B 计算完毕:
    3.1、计算第 i 位的值:c.Insert(i+1, (a.GetElement(i + 1) +
b.GetElement(i + 1) + flag) % 10);
    3.2、计算该位的进位:flag = (a.GetElement(i + 1) +
b.GetElement(i + 1) + flag) / 10;
  4、计算大整数 A 或 B 余下的部分;
  5、计算结果的进位
注:用数组来存放大整数

bigInt.cpp:
#include#includeusing namespace
std;#include”bigInt.h”//成员函数实现bigInt& bigInt::operator=(bigInt
&a){ for (int i = 0; i= 0; i–, j++)//将大整数的低位存储到数组的低位 {
m_bigInt[j] = 0 + a[i] – 48; m_length++; }}bigInt::~bigInt(){
delete[]m_bigInt; m_bigInt = NULL; m_length = 0;}//友元函数的实现
ostream& operator<<(ostream &output, bigInt &a){ for (int i =
a.m_length – 1; i >= 0; i–) output << a.m_bigInt[i];
return output;}bigInt operator+ (bigInt &a, bigInt &b){ int flag =
0;//进位标志 bigInt temp; int m = a.m_length>b.m_length ?
(b.m_length) : (a.m_length); int i = 0;//循环变量 for (i = 0;
ib.m_length ? (a.m_length + 1) : (b.m_length + 1); } return temp;}
temp = b1 + b2; system; return 0;}

一、顺序线性表头文件:SeqList.h

bigInt.h:
#ifndef BIG_INT_H#define BIG_INT_H#include//大整数的结构 class
bigInt{public: friend ostream& operator<<(ostream &output, bigInt
&a);//重载输出流运算符 friend bigInt operator+ (bigInt &a, bigInt
&b);//重载加法运算 friend bigInt operator- (bigInt &a, bigInt
&b);//重载减法运算 friend bigInt operator* (bigInt &a, bigInt
&b);//重载乘法运算 friend bigInt operator/ (bigInt &a, bigInt
&b);//重载除法运算 bigInt;//构造函数,初始化表示大整数的这个数组
bigInt();//默认构造函数 ~bigInt();//析构函数 bigInt& operator= (bigInt
&a);//重载赋值运算 private: int * m_bigInt; //顺序表的数组 int
m_length; const int maxCapcity;};#endif

  1 //顺序线性表的头文件
  2 #include<iostream>
  3 
  4 const int MaxSize = 100;
  5 //定义顺序表SeqList的模板类
  6 template<class DataType>
  7 class SeqList{
  8 public:
  9   //顺序表无参构造器(创建一个空的顺序表)
 10   SeqList(){ length = 0; }
 11   //顺序表有参构造器(创建一个长度为n的顺序表)
 12   SeqList(DataType array[], int n);
 13   //顺序表析构函数
 14   ~SeqList(){}
 15   //求顺序表的长度
 16   int GetLength(){ return length; }
 17   //顺序表按位查找,返回i位置的元素
 18   DataType GetElement(int i);
 19   //顺序表按值查找,返回该元素所在的位置
 20   int GetLocal(DataType x);
 21   //顺序表在指定的位置插入指定的元素
 22   void Insert(int i, DataType x);
 23   //顺序表删除元素,返回删除的元素
 24   DataType Delete(int i);
 25   //输出顺序表中的元素
 26   void PrintSeqList();
 27 private:
 28   //一维数组,存放数据元素
 29   DataType data[MaxSize];
 30   //顺序表的长度
 31   int length;
 32 };
 33 
 34 //实现顺序表有参构造器
 35 template<class DataType>
 36 SeqList<DataType>::SeqList(DataType array[], int n)
 37 {
 38   if (n > MaxSize)
 39   {
 40     throw "传入的顺序表长度过长";
 41   }
 42   //给顺序表的存储元素的数组赋值
 43   for (int i = 0; i < n; i++)
 44   {
 45     data[i] = array[i];
 46   }
 47   //给顺序表的长度赋值
 48   length = n;
 49 }
 50 
 51 //实现顺序表按位查找
 52 template<class DataType>
 53 DataType SeqList<DataType>::GetElement(int i)
 54 {
 55   //判断是定的位置是否合理
 56   if (i < 1 || i >length)
 57   {
 58     throw "位置有误";
 59   }
 60   else
 61   {
 62     //返回指定位置的元素
 63     return data[i - 1];
 64   }
 65 }
 66 
 67 //实现顺序表按值查找,返回该元素所在的位置
 68 template<class DataType>
 69 int SeqList<DataType>::GetLocal(DataType x)
 70 {
 71   //遍历顺序表的元素
 72   for (int i = 0; i < length; i++)
 73   {
 74     //判断指定的元素是否在顺序表中
 75     if (data[i] == x)
 76     {
 77       //返回指定元素在顺序表中的位置
 78       return (i + 1);
 79     }
 80   }
 81   //如果指定的元素不在顺序表中,则返回位置为0
 82   return 0;
 83 }
 84 
 85 //实现顺序表插入元素
 86 template<class DataType>
 87 void SeqList<DataType>::Insert(int index, DataType x)
 88 {
 89   //判断插入的位置是否合理
 90   if (length >= MaxSize)
 91   {
 92     throw "顺序表已存放满";
 93   }
 94   if (index<1 || index>length + 1)
 95   {
 96     throw "插入元素的位置有误";
 97   }
 98   //如何插入的位置合理,则把顺序表中从最后位置到指定插位置的元素整体向后移动一个位置
 99   for (int j = length; j >= index; j--)
100   {
101     data[j] = data[j - 1];
102   }
103   //给插入的位置放入指定的元素
104   data[index - 1] = x;
105   length++;
106 }
107 
108 //实现顺序表删除指定位置的元素
109 template<class DataType>
110 DataType SeqList<DataType>::Delete(int index)
111 {
112   //声明要取出的元素
113   DataType x;
114   //判断要删除的位置是否合理
115   if (index<1 || index>length)
116   {
117     throw "删除的位置有误";
118   }
119   else
120   {
121     //取出指定位置的元素
122     x = data[index - 1];
123     //将指定位置后的元素全部都向前移动一个位置
124     for (int i = index; i < length; i++)
125     {
126       data[i - 1] = data[i];
127     }
128     //删除顺序表中的元素后,其长度减1
129     length--;
130   }
131   return x;
132 }
133 
134 //顺序输出顺序表中的元素
135 template<class DataType>
136 void SeqList<DataType>::PrintSeqList()
137 {
138   if (length < 1)
139   {
140     throw "顺序表中没有元素";
141   }
142   else
143   {
144     //顺序输出顺序表元素
145     for (int i = 0; i < length; i++)
146     {
147       cout << data[i] << " ";
148     }
149     cout << endl;
150   }
151 }

bigInt.cpp:
#include#includeusing namespace
std;#include”bigInt.h”//成员函数实现bigInt& bigInt::operator=(bigInt
&a){ for (int i = 0; i= 0; i–, j++)//将大整数的低位存储到数组的低位 {
m_bigInt[j] = 0 + a[i] – 48; m_length++; }}bigInt::~bigInt(){
delete[]m_bigInt; m_bigInt = NULL; m_length = 0;}//友元函数的实现
ostream& operator<<(ostream &output, bigInt &a){ for (int i =
a.m_length – 1; i >= 0; i–) output << a.m_bigInt[i];
return output;}bigInt operator+ (bigInt &a, bigInt &b){ int flag =
0;//进位标志 bigInt temp; int m = a.m_length>b.m_length ?
(b.m_length) : (a.m_length); int i = 0;//循环变量 for (i = 0;
ib.m_length ? (a.m_length + 1) : (b.m_length + 1); } return temp;}

二、大整数求和头文件:BidIntegerAdd.h

 1 //顺序线性表之大整数求和
 2 #include<iostream>
 3 //引入顺序线性表的头文件
 4 #include"SeqList.h"
 5 using namespace std;
 6 
 7 SeqList<int> Add(SeqList<int>a, SeqList<int>b)
 8 {
 9   //定义中间变量,顺序线性表
10   SeqList<int> c = SeqList<int>();
11   //flag 是进位标志,i 为大整数的某一位
12   int flag = 0, i = 0;
13   //求大整数 a,b 的位数
14   int aLength = a.GetLength();
15   int bLength = b.GetLength();
16   //逐位计算加法直到某个大整数计算完毕
17   while (i < aLength&&i < bLength)
18   {
19     //计算第 i 位的值
20     c.Insert(i+1, (a.GetElement(i + 1) + b.GetElement(i + 1) + flag) % 10);
21     //计算第 i 位的进位
22     flag = (a.GetElement(i + 1) + b.GetElement(i + 1) + flag) / 10;
23     i++;
24   }
25   //计算大整数 A 余下的部分
26   for (; i < aLength; i++)
27   {
28     c.Insert(i + 1, (a.GetElement(i + 1) + flag) % 10);
29     flag = (a.GetElement(i + 1) + flag) / 10;
30   }
31   //计算大整数 B 余下的部分
32   for (; i < bLength; i++)
33   {
34     c.Insert(i + 1, (b.GetElement(i + 1) + flag) % 10);
35     flag = (b.GetElement(i + 1) + flag) / 10;
36   }
37   //如果最后有进位,则结果会多一位
38   if (flag == 1)
39   {
40     c.Insert(c.GetLength()+1, 1);
41   }
42   return c;
43 }

三、测试顺序线性表之大整数求和:TestBigIntegerAdd.h

 1 //测试顺序线性表之大整数求和
 2 #include<iostream>
 3 //引入顺序表之大整数求和头文件
 4 #include"BigIntegerAdd.h"
 5 using namespace std;
 6 int main()
 7 {
 8   //定义两个顺序线性表
 9   int array1[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
10   int array2[] = { 1, 1, 1, 1, 1, 1, 1, 1 };
11   SeqList<int>a = SeqList<int>(array1,9);
12   cout << "第一个大整数是:" << endl;
13   a.PrintSeqList();
14   SeqList<int>b = SeqList<int>(array2,8);
15   cout << "第二个大整数是:" << endl;
16   b.PrintSeqList();
17   SeqList<int>c = Add(a, b);
18   cout << "他们的和是:" << endl;
19   c.PrintSeqList();
20   return 0;
21 }

四、运行示例结果

图片 1

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注