当我尝试用双链表实现bigint时，我应该如何定义BigInt？

Question

我正在尝试实现 BigInts 基本操作，但在此之前我需要定义 BigInt，以便我可以调用函数和 BigInt a 之类的东西。我认为它应该是一个指针，因为我可以指向与 BigInt 关联的列表，但我不是 100% 确定如何定义它以及是否确实应该是一个指针。

我有这样的：

typedef  *BigInt;

我想这样称呼事情

BigInt big_new(char *num);
BigInt sum_b(BigInt a, BigInt b);
BigInt sub_b(BigInt a, BigInt b);
BigInt mult_b(BigInt a, BigInt b);
BigInt div_b(BigInt a, BigInt b);
BigInt mod_b(BigInt a, BigInt b);
void print_b(BigInt a);

我在其他文件上实现了列表，现在我将使用它们来创建大整数，我想创建列表，大整数将是一个列表，在一个节点中将是一个整数算法

Answer 1

如果您现有的链表类型是某种结构（例如，

typedef struct { ... } MyLinkedListType;

，唯一可以与您编写的API一起使用的

typedef

，并允许您修改调用者的副本（即使没有指针也可能在某些情况下，但并非总是如此）将是：

typedef MyLinkedListType *BigInt;  // BigInt is always a pointer to a linked list

这里的主要成本是你不能堆栈分配类型。或者更准确地说，你“不应该”，因为涉及到知道所指向的内容是否在堆栈上并且可以被删除，或者在堆上并且必须被释放以及二进制向后兼容问题; OpenSSL 的 BIGNUM 曾经允许两者，但最终决定避免在堆栈情况下分配的好处不值得了解您拥有哪种类型的成本，以及其背后的

struct

是透明的要求；在较新的版本中，

struct

是不透明的（用户不能无意中依赖于动态链接的 OpenSSL 升级时会破坏的给定布局），并且您只能使用动态分配底层结构的 API 来创建和销毁它们。除此之外：

如果使用

typedef ed 指针解决方案，

MyLinkedListType

应该是不透明的

；除了将其作为函数参数传递之外，调用者应该 

never 对 BigInt 做任何事情（通常传递给您的 API，对于所有其他函数，它们只是承担所有权和/或分解对您的 API 的调用） 。您永远不应该看到不是来自您的 API 的代码取消引用指针、分配它、释放它，或者用它做

anything

，而不是由您介导。一旦它是一个指针这一事实变得相关，永远，代码就会变得混乱；它应该是一个不透明的句柄，或者应该显式处理指针（或缺乏指针），而不是隐藏在 typedef 中。如果不需要修改调用者（例如，所有此类链表都指向至少一个节点，并且您将更改该节点的值而不是替换它，因此即使就地更改操作也不需要更改来电者指向的内容），你可以这样做：

typedef MyLinkedListType BigInt; // BigInt *is* a linked list

以每次调用时复制 

struct

组成的

MyLinkedListType

为代价（消除了直接修改调用者副本的能力；您只能修改它指向的内容）。最后一个选项是“evil magic”选项（但仍在 GMP 等大牌库中使用），其中：

您可以堆栈分配

1. 当您将其传递给函数时，您隐式地传递了一个指向数据的指针，而不是副本（有点像 C++ 引用语义）
该解决方案是：

typedef MyLinkedListType BigInt[1];

因为它是一个数组，所以它的大多数用途都会衰减为指向其第一个（也是唯一）元素的指针，因此您可以将其声明为本地函数（并且它为数据本身获取堆栈空间），但将其传递给任何其他函数它接收一个指向该存储的指针（相当于传递 

&localvar[0]

）。

许多 C 程序员讨厌这种方法（隐式引用语义通常不是 C 中的东西；

请参阅此处的注释，我解释了它是如何工作的

），并且它不允许按值传递工作，但是就像我说的，它是 GMP 等主要库的公认部分（实际上它是由 jmp_buf/setjmp

 支持中使用的 

longjmp

 结构标准强制执行的），所以它不仅合法，而且显然可用。也就是说，你不会使用：

BigInt big_new(char *num);

在这样的设计中；相反，你会使用：void big_init(BigInt bi, const char *num); // Maybe a return code to indicate if an allocation failed or the like

初始化就地分配的调用者变量（例如

BigInt mynum; big_init(bi, "12345"); code_using_bi; big_clear(bi);

）。

与指针解决方案一样，单元素数组解决方案只能用于逻辑上不透明的类型（它们实际上不能是不透明的，因为调用者必须能够声明该类型的非指针版本，但调用者应该永远不想/不需要在不通过 API 的情况下修改它们）。

由于您提供的信息有限，我只能告诉您这些。据我所知，指针最适合您现有的 API，但其他方法可能会更好（只需对 API 进行少量修改）。