C++实现任意长度整数抽象数据类型
一、需求分析
1、问题描述
设计一个程序实现两个任意长的整数求和运算。
2、功能需求
用户根据提示，按格式输入两个任意长度的整数，经程序运算得出两个整数的和，并将结果输出在屏幕上。
程序执行的命令包括：
（1）、程序运行，提示用户按格式输入数据；
（2）、用户输入两个任意长度的整数；
（3）、计算出两个整数的和，并将结果输出在屏幕上；
（4）、结束。
3、输入及输出格式
（1）、 输入数据：用户输入数据时，给出清晰明确的提示信息，包括输入的数据内容、格式及结束方式等；输入支持使用或者不使用千位分隔符（每三位一组，组间用逗号隔开）；十进制数（屏幕输入）只有一行，含2个整数，以空格隔开，输入完毕按回车键结束。
（2）、 输出数据：（屏幕输出）只有一行，含 1 个整数，即求得的输入的两个整数的和，使用千位分隔符。
（3）、 输入输出样例：
屏幕输入：
14122 38324
屏幕输出：
输入的两个整数的和为：52,446
二、概要设计
1、 问题的抽象数据类型分析
本题要实现构造任意长度的整数抽象数据类型。考虑到C++中已有的数据类型，不管是整型、长整型，都只在一定位数范围内是精确的。为得到任意长度整数相加的精确结果，需自己构造抽象数据类型。
整数的特点是没有小数部分，从个位起，十位、百位、千位…，每一位都是介于0~9之间的正整数。因此，可将任意长度整数抽象为x=an-1an-2…ai…a2a1a0的形式。an-1、an-2、…、ai、…、a2、a1、a0分别是最高位、次高位、…、百位、十位、个位的数值（一元组）。
ADT arbitrary_length_integer
数据元素：ai=ni，i=0,1,…,n-1 (n≥0)，ni代表从个位起，第i位的数值。
为线性结构，对数据元素 ai (0≤i≤n-2)存在次序关系<ai，ai+1>, a0 的直接前驱是 an-1 ，an-1 的直接后继是 a0。
2、存储结构设计
1）、存储结构的确定
数据结构的目的是有效组织和处理数据。为了有效组织和处理数据，先要分析任意长度整数抽象数据类型逻辑操作的特点和指针所占空间比例，然后确定最优的存储结构。
对于输入的两个任意长度整数的构造，按从最高位依次到个位的顺序，将每一位的数值作为数据元素插入到下一位置。因长度不确定，可能位数很多，不能在构造时就确定最大长度并开辟存储空间，否则会造成空间的闲置或是空间的不足。不能采用顺序存储结构，而应采用链式存储结构，按需要随时开辟、撤销空间，便于插入、删除的操作。
进行相加操作时，从个位起依次按位计算。计算所得数值介于0~9之间，则作为结果整数相应的位。计算结果大于10，则将减去10后的数作为结果整数相应的位，并记录进位，下一位计算时加一。为实现能从尾部元素向上遍历至头部的目的，选择使用双向链表，对每一个结点都能方便地找到其上一个、下一个结点。
综上所述，采用带头指针、尾指针的双向链表（不循环）存储结构。
2）、逻辑操作设计
（1）、构造一个空的任意长度整数
（2）、任意长度整数 插入 新的一个数据元素
（3）、任意长度整数 删除 一个数据元素
（4）、任意长度整数 加法1：z=x+y（非就地实现）
（5）、任意长度整数 加法2：x=x+y（就地实现）
（6）、输出任意长度整数
三、详细设计
1、结点的定义：
struct DblNode
{
int data; //数据元素，存放任意长度整数某一位的数值
DblNode *lLink, *rLink; //前驱指针、后继指针，分别指向前一个结点和后一个结点
DblNode(DblNode *left = nullptr, DblNode *right = nullptr) //构造函数
:lLink(left), rLink(right) {}
DblNode(int value, DblNode *left = nullptr, DblNode *right = nullptr)
:data(value), lLink(left), rLink(right) {}
};
2、任意长度整数类的定义：
class arbitrary_length_integer
{
private:
int length; //length+1即为该任意长度整数的位数
DblNode *first; //头指针
DblNode *rear; //尾指针
public:
arbitrary_length_integer() //构造函数
{
first = new DblNode;
rear = first;
length = 0;
};
~arbitrary_length_integer() //析构函数
{
DblNode *q;
while ( rear != NULL)
{
q = rear;
rear = rear->lLink;
delete q;
}
length = 0;
if (!first)
{
delete first;
first = NULL;
rear = NULL;
}
}
DblNode *getHead() const { return first; } //取附加头结点地址
void setHead(DblNode *ptr) { first = ptr; } //设置附加头结点地址
int Length() const; //返回得到length
bool rInsert(int& x); //从尾部插入一个结点
bool fInsert(int& x); //从头部插入一个结点
bool Remove(); //从尾部删除一个结点
void input(string & n); //将字符串每个字符转为整型后按顺序依次作为新插入结点的数据元素存入
void output(); //将任意长度的整数输出到屏幕上（使用千位分隔符）
void add(arbitrary_length_integer& m); //就地实现任意长度两整数相加x=x+y
friend void add(arbitrary_length_integer& m, arbitrary_length_integer& l, arbitrary_length_integer& n); //非就地实现任意长度两整数相加z=x+y
};
3、类中具体函数的实现：
int arbitrary_length_integer::Length()const //返回得到length
{
return length;
}
bool arbitrary_length_integer::rInsert(int& x) //从尾部插入一个结点
{
DblNode *Newnode = new DblNode(x);
if (Newnode == NULL)
{
cout << "开辟内存空间失败" << endl;
return false;
}
Newnode->lLink = rear;
rear->rLink = Newnode;
rear = Newnode;
length++;
return true;
}
bool arbitrary_length_integer::fInsert(int& x) //从头部插入一个结点
{
DblNode *Newnode = new DblNode(x);
if (Newnode == NULL)
{
cout << "开辟内存空间失败" << endl;
return false;
}
Newnode->rLink = first->rLink;
Newnode->lLink = first;
first->rLink = Newnode;
length++;
return true;
}
bool arbitrary_length_integer::Remove() //从尾部删除一个结点
{
if (rear == NULL)
{
cout << "已为空，删除失败" << endl;
return false;
}
DblNode *q;
q = rear;
rear = rear->lLink;
delete q;
length --;
return true;
}
void arbitrary_length_integer::input(string & n) //将字符串每个字符转为整型后按顺序依次作为新插入结点的数据元素存入
{
int x;
for (int i = 0; n[i] != '\0'; i++)
{
if (n[i] == ',')continue; //如果输入的字符为千位分隔符的逗号，不存入
x = (int)(n[i] - '0'); //将char类型字符转为整型
rInsert(x);
}
}
void arbitrary_length_integer::output() //将任意长度的整数输出到屏幕上（使用千位分隔符）
{
int len=length;
DblNode *current = first->rLink;
while (current != NULL)
{
if (!(len % 3) && current != first->rLink)cout << ","; //每隔三位输出千位分隔符
cout << current->data;
len--;
current = current->rLink;
}
cout << endl;
}
void arbitrary_length_integer::add(arbitrary_length_integer& m) //就地实现任意长度两整数相加x=x+y
{
DblNode * currx = rear; //遍历指针，从尾部即整数个位开始遍历
DblNode * curry = m.rear;
int plus = 0; //用于记录进位，0表示不进位，1表示进位
int t; //用于计算每一位的值
if (length >= m.length) //第一个整数位数较多，或两个整数位数相同时
{
while (curry != m.first) //位数较少的整数未遍历完时
{
t = currx->data + curry->data + plus; //t为两整数对应位相加，再加上进位
if (t >= 0 && t <= 9) //t介于0~9之间时，即为结果整数相应位的值
{
currx->data = t;
plus = 0; //不进位
}
else //t大于10时，t-10即为结果整数相应位的值
{
t = t - 10;
currx->data = t;
plus = 1; //进位
}
currx = currx->lLink; //每一位处理完前移一位
curry = curry->lLink;
}
if (currx == first)
{
if (plus != 0) fInsert(plus);
}
else
{
t = currx->data + plus;
if (t >= 0 && t <= 9)
{
currx->data = t;
currx = currx->lLink;
}
else
{
t = t - 10;
currx->data = t;
plus = 1;
currx = currx->lLink;
if (currx == first) fInsert(plus);
}
}
while (currx != first) //位数较多的整数未遍历完时
{
t = currx->data;
currx->data = t;
currx = currx->lLink;
}
}
else //第二个整数位数较多时
{
while (currx != first)
{
t = curry->data + currx->data + plus;
if (t >= 0 && t <= 9)
{
currx->data = t;
plus = 0;
}
else
{
t = t - 10;
currx->data = t;
plus = 1;
}
currx = currx->lLink;
curry = curry->lLink;
}
if (curry == m.first)
{
if (plus != 0) fInsert(plus);
}
else
{
t = curry->data + plus;
if (t >= 0 && t <= 9)
{
fInsert(t);
curry = curry->lLink;
}
else
{
t = t - 10;
fInsert(t);
plus = 1;
curry = curry->lLink;
if (curry == m.first) fInsert(plus);
}
}
while (curry != m.first)
{
t = curry->data;
fInsert(t);
curry = curry->lLink;
}
}
}
void add(arbitrary_length_integer& m, arbitrary_length_integer& l, arbitrary_length_integer& n) //非就地实现任意长度两整数相加z=x+y
{
DblNode * currx = l.rear;
DblNode * curry = m.rear;
int plus = 0;
int t;
if (l.length >= m.length)
{
while (curry != m.first)
{
t = currx->data + curry->data+plus;
if (t >= 0 && t <= 9)
{
n.fInsert(t);
plus = 0;
}
else
{
t = t - 10;
n.fInsert(t);
plus = 1;
}
currx = currx->lLink;
curry = curry->lLink;
}
if (currx == l.first)
{
if(plus!=0) n.fInsert(plus);
}
else
{
t = currx->data+plus;
if (t >= 0 && t <= 9)
{
n.fInsert(t);
currx = currx->lLink;
}
else
{
t = t - 10;
n.fInsert(t);
plus = 1;
currx = currx->lLink;
if (currx == l.first) n.fInsert(plus);
}
}
while (currx != l.first)
{
t = currx->data;
n.fInsert(t);
currx = currx->lLink;
}
}
else
{
while (currx != l.first)
{
t = curry->data + currx->data + plus;
if (t >= 0 && t <= 9)
{
n.fInsert(t);
plus = 0;
}
else
{
t = t - 10;
n.fInsert(t);
plus = 1;
}
currx = currx->lLink;
curry = curry->lLink;
}
if (curry == m.first)
{
if (plus != 0) n.fInsert(plus);
}
else
{
t = curry->data + plus;
if (t >= 0 && t <= 9)
{
n.fInsert(t);
curry = curry->lLink;
}
else
{
t = t - 10;
n.fInsert(t);
plus = 1;
curry = curry->lLink;
if (curry == m.first) n.fInsert(plus);
}
}
while (curry != m.first)
{
t = curry->data;
n.fInsert(t);
curry = curry->lLink;
}
}
}
4、用于测试的主函数
（1）、就地实现任意长度整数相加
void main()
{
arbitrary_length_integer a,b;
cout << "请输入两个任意长度的正整数（使用或者不使用千位分隔符均可，两数间以空格分隔，输入结束时按回车键）：" << endl;
string x, y;
cin >> x >> y; //将屏幕输入的两个待加整数存入string类型的变量x,y中
a.input(x); //将字符串x,y每个字符转为整型后按顺序依次作为新插入结点的数据元素存入
b.input(y);
cout << "输入的两个正整数的和为 ：" << endl;
b.add(a); //计算两个任意长度整数的和
b.output(); //将计算结果输出到屏幕上
system("pause");
}
（2）、非就地实现任意长度整数相加
void main()
{
arbitrary_length_integer a,b,c;
cout << "请输入两个任意长度的正整数（使用或者不使用千位分隔符均可，两数间以空格分隔，输入结束时按回车键）：" << endl;
string x, y;
cin >> x >> y;
a.input(x);
b.input(y);
cout << "输入的两个正整数的和为 ：" << endl;
add(a, b, c);
c.output();
system("pause");
}
5、函数的调用关系图反映程序层次结构
四、调试分析
编程过程中，出现了一些错误，经逐步调试、debug，最终正确运行：
1、定义了string x,y;cin>>x>>y;从屏幕中输入值传给x,y，显示“没有与操作数匹配的“>>”运算符”。检查发现，头文件包错，将#include<string.h>改为#include，得以正确使用；
2、从链表头部插入一个新的结点，即fInsert函数中，程序运行时异常。Newnode->rLink = first;first赋值给Newnode->rLink有误。分析发现，first为头指针，头指针后还有一附加头结点。修改为Newnode->rLink = first->rLink;后正确；
3、将输入的string类型每一个字符，转换为int型，作为数据元素存入时不正确。查阅资料了解到，直接进行强制类型转换是不可行的。将(int)n[i]改为(int)(n[i]-’0’)后正确；
4、发现计算所得整数，若位数为三的倍数时，输出结果最前面会有一个多余的逗号。将逗号输出判断条件!(len % 3)改为!(len % 3) && current != first->rLink后，输出正确；
五、测试数据
1、测试实例 1
//两整数等位数，不使用千位分隔符输入的情况
2、测试实例 2
//两整数等位数，使用千位分隔符输入的情况
3、测试实例 3
//输入的第一个整数位数多于第二个整数的情况
4、测试实例 4
//最高位需进位的情况
5、测试实例 5
//最高位需连续进位的情况
6、测试实例 6
//输入的第一个整数位数少于第二个整数的情况
结论：测试结果正确。
推荐阅读
-
C++实现任意长度整数抽象数据类型
-
C++ stringstream：实现任意数据类型之间的转换
-
java数据结构----图的遍历应用举例：编程实现判断一个有向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径
-
【模板小程序】任意长度非负十进制数转化为二进制（java实现）
-
Java实现给定一个无序的整数数组，找到其中最长上升子序列的长度。
-
简单渲染流水管线C++代码实现（六）---绕任意过原点的轴旋转矩阵
-
C++实现LeetCode(7.翻转整数)
-
剑指offer之数值的整数次方(C++/Java双重实现)
-
【笔试】C++实现计算在网格中从原点到特定点的最短路径长度（BFS）
-
用c++实现正整数集合的交、并、差