我应该使用什么数据结构来创建自己的“BigInteger”类？

data-structures java c++ biginteger

2022-09-04 04:20:01

作为可选作业，我正在考虑编写自己的BigInteger类的实现，在那里我将提供自己的加法，减法，乘法等方法。

这将适用于任意长的整数，甚至数百位数字。

在对这些数字进行数学运算时，逐位数字并不难，您认为最好的数据结构是什么来代表我的“BigInteger”？

起初我正在考虑使用数组，但后来我想，在进行大量加法或乘法后，我仍然可能溢出（数组插槽用完）。这是否是使用链表的好例子，因为我可以用O（1）时间复杂度来附加数字？

还有其他一些数据结构比链表更适合吗？我的数据结构所包含的类型是否应为我可用的最小可能的整数类型？

另外，我应该小心如何存储我的“carry”变量吗？它本身应该是我的“BigInteger”类型吗？

答案 1

查看David R. Hanson的C接口和实现一书。它有2个关于这个主题的章节，涵盖了矢量结构，字大小和您可能遇到的许多其他问题。

它是为C编写的，但其中大部分适用于C++和/或Java。而且，如果您使用C++它将会简单一些，因为您可以使用类似的东西来为您管理阵列分配。std::vector

答案 2

始终使用将完成所需工作的最小 int 类型（字节）。链表应该运行良好，因为您不必担心溢出。