当我尝试使用双向链表实现 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);

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

Answer 1

如果您现有的链表类型是某种结构（例如 typedef struct { ... } MyLinkedListType;，唯一可以与您编写的 API 一起使用的 typedef，并允许您修改 调用者的 副本（在某些情况下即使没有指针也可能，但并非总是如此）将是：

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

这里的主要成本是您不能堆栈分配类型。或者更准确地说，你不应该，因为你不知道指向的东西是在堆栈上，可以直接删除，还是在堆上，必须释放，以及二进制 back-compat 问题； OpenSSL 的 BIGNUM 过去允许两者，但最终决定避免在堆栈情况下分配的好处不值得知道您拥有哪种类型的成本，以及它背后的 struct 的要求透明的;在较新的版本中，struct 是不透明的（用户不能无意中依赖在升级动态链接的 OpenSSL 时中断的给定布局）并且您只能使用动态链接的 API 来创建和销毁它们分配底层结构。

除此之外：If you use the typedef-ed pointer solution, MyLinkedListType should be opaque；调用者应该 never 对 BigInt 做任何事情，而不是将其作为函数参数传递（通常传递给您的 APIs，对于所有其他函数，它只是让他们获得所有权 and/or 排除对您的 API 的调用）。你永远不应该看到不是来自你的 API 的代码取消引用指针，分配它，释放它，或者用它做任何不是你调解的事情。一旦它是一个指针这一事实变得相关，ever，代码就会令人困惑；它应该是一个不透明的句柄，或者应该明确处理指针（或缺少指针），而不是隐藏在 typedef.

中

如果不需要修改调用者（例如，所有此类链表至少指向一个节点，并且您会改变该节点的值而不是替换它，所以即使 mutate-in-place 操作也不会t 需要更改调用者指向的内容），你可以这样做：

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

以在每次调用时复制 struct 构成 MyLinkedListType 的任何内容为代价（移除直接修改调用者副本的能力；您只能修改它指向的内容）。

最后一个选项是“evil magic”选项（但仍在 GMP 等大牌库中使用），其中：

你可以堆栈分配
当你将它传递给一个函数时，你隐式地传递了一个指向数据的指针，而不是一个副本（有点像 C++ 引用语义）

解决方案是：

typedef MyLinkedListType BigInt[1];

因为它是一个数组，所以它的大部分使用都会衰减到指向它的第一个（也是唯一的）元素的指针，因此您可以将它声明为一个局部函数（它会为数据本身获取堆栈 space）但是在将它传递给任何其他函数时，它会收到一个指向该存储的指针（相当于传递 &localvar[0]）。

许多 C 程序员讨厌这种方法（隐式引用语义在 C 中通常不是一回事；），而且它不允许 pass-by-value 可以工作，但正如我所说，它是 GMP 等主要库的公认部分（并且它实际上是 setjmp/longjmp 支持中使用的 jmp_buf 结构的标准所强制要求的），所以它不仅合法，而且显然可用。也就是说，您不会使用：

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

初始化分配给 in-place 的调用者变量（例如 BigInt mynum; big_init(bi, "12345"); code_using_bi; big_clear(bi);）。

与指针解决方案一样，one-element 数组解决方案应该只用于逻辑上不透明的类型（它们实际上不能是不透明的，因为调用者必须能够声明 non-pointer 版本的类型，但调用者不应该 want/need 在不通过你的 APIs 的情况下修改它们。

由于您提供的详细信息有限，我只能提供这些信息。据我所知，指针最适合您现有的 API，但其他方法可能效果更好（稍作 API 修改）。

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

How should i define BigInt when i am trying to implemnet bigints with double linked list?

c

biginteger

doubly-linked-list