C中的Cons Cell数据结构
在构建一个小型Scheme解释器的早期阶段，我是C的新手。 对于项目的这一部分，我正在尝试构建一个简单的cons单元数据结构。 它应该采取像这样的列表
(abc)
并在内部表示如下：
[ ][ ] -> [ ][ ] -> [ ][/] | | | ABC
为了测试它是否正常工作，我有一个打印function来回显输入。 这是不起作用的代码：
#include #include #include #include "lexer.h" #include "parse.h" char token[20]; struct conscell { char *data; struct conscell *first, *rest; }; void S_Expression () { /* function from lexer to receive input a split into tokens no greater than 20 */ startTokens(20); /* gets the next token */ strcpy(token, getToken()); /* List is a typedef for the struct conscell */ List tree = createList (); tree = nextNode (tree); printList(tree); } List createList () { List node = malloc(sizeof (List)); if (node == NULL) { printf("Out of memory!\n"); exit(1); } node->data = NULL; node->first = NULL; node->rest = NULL; return node; } /* Recursive function to build cons cell structure */ List nextNode (List node) { node = createList (); if (token[0] == '(') { strcpy(token, getToken()); node->first = nextNode(node->first); node->rest = nextNode(node->rest); } else { if (token[0] == ')') { node = NULL; } else { List temp = createList(); temp->data = token; temp->first = NULL; temp->rest = NULL; node->first = temp; strcpy(token, getToken()); node->rest = nextNode(node->rest); } } return node; } /* Prints output. So far, just trying to print symbols */ void printList(List node) { if (node != NULL) { if (node->data != NULL) { printf("%s", node->data); } } }
到目前为止无法打印出任何东西。 我几乎肯定它的指针问题。 如果有人能指出我（没有双关语意）朝着正确的方向发展，我们将非常感激。
谢谢
首先，我假设List是struct conscell*的typedef。 如果不是，它应该是，否则你的代码将在没有大量警告的情况下编译。
方案缺陷单元应该是一个简单的单链表，而不是双向链表。 所以你的个体细胞应该更像：
typedef conscell { unsigned char *data; //<== use unsigned char for a memory buffer struct conscell* next; //<== only a "next" pointer needed } conscell;
我看到你现在只是试图打印符号，所以使用char而不是unsigned char可以用于此目的，但是当你使用更通用的数据结构如lambdas等时，你将不得不切换到unsigned char*或void*以获取对包含这些类型的更复杂数据结构的内存缓冲区的引用。
另一个看起来有点令人困惑的问题是，你正在使你的cons细胞的每个细胞成为另一个利弊细胞，例如，这些代码行，
if (token[0] == '(') { strcpy(token, getToken()); node->first = nextNode(node->first); node->rest = nextNode(node->rest); }
递归地添加cons单元格作为“第一”和“rest”......但这不是链表应该如何。 它应该有一个指向列表节点的指针作为列表的“头部”（而不是像你在这里看到的那样的另一个cons-cell），然后列表中的每个节点指向一些数据和下一个节点列表。
接下来，使用createList()函数在整个地方都有内存泄漏，因为你用它分配内存，但是从不删除那个内存（也就是说，你有像node = NULL这样的代码实际上是因为你丢失而导致内存泄漏对node最初指向的已分配内存位置的内存引用。 在为节点指针指定NULL之前，必须在节点指针上调用free() 。
最后， printList()不会执行任何操作， printList()打印传递它的列表的第一个元素...没有递归调用或循环来循环到链接列表中的下一个节点。 因此，您不会使用该function进行多次打印。 它看起来应该更像：
void printList(List node) { List current = node; while (current != NULL) //<== guard for the end-of-list { if (node->data != NULL) { printf("%s", node->data); } current = current->next; //cycle to the next node in the linked list } }
总而言之，1）您的cons数据结构应该表示由具有数据元素和指向下一个节点的指针的结构数据类型组成的单链表。 通过指向第一个节点的头指针访问cons'ed列表。 2）当您解析输入时，您应该将节点添加到链表的前面，因为Scheme的cons操作，以及方案中的所有操作，都是递归的，并且“向右折叠”，这意味着它们可以从基础工作 - case（即两个元素的构成），然后扩展该基础案例。 因此，如果你有类似的东西(dcba) (cons 'd (cons 'c (cons 'b (cons 'a '())))) ，你就打印出列表(dcba) 。 如果你愿意，也可以帮助将令牌放入堆栈，因为你递归地解析输入，然后从堆栈输入到你的链表（有点像RPN计算器的工作方式）。
还要将\ n添加到printf以确保将其刷新到stdout：
printf("%s\n", node->data);