Cons C单元格数据结构 [英] Cons Cell data structure in C
问题描述
（abc）
并在内部表示如下：
[] [] - > [] [] - > [] [/]
| | |
ABC
要测试它是否正常工作，我有一个打印功能来回显输入。以下代码不起作用：
#include< stdlib.h>
#include< stdio.h>
#include< string.h>
#includelexer.h
#includeparse.h
char token [20];
struct conscell {
char * data;
struct conscell * first，* rest;
};
void S_Expression（）
{
/ *从lexer函数接收输入一个拆分为令牌不大于20 * /
startTokens（20）;
/ *获取下一个标记* /
strcpy（token，getToken（））;
/ * List是struct conscell的typedef * /
列表树= createList（）;
tree = nextNode（tree）;
printList（tree）;
}
列表createList（）
{
列表node = malloc（sizeof（List））;
if（node == NULL）{
printf（Out of memory！\\\
）;
exit（1）;
}
node-> data = NULL;
node-> first = NULL;
node-> rest = NULL;
返回节点;
}
/ *构建cons单元格结构的递归函数* /
列表nextNode（列表节点）
{
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
{
列表temp = createList（）;
temp-> data = token;
temp-> first = NULL;
temp-> rest = NULL;
node-> first = temp;
strcpy（token，getToken（））;
node-> rest = nextNode（node-> rest）;
}
}
返回节点;
}
/ *打印输出。到目前为止，只是试图打印符号* /
void printList（List node）
{
if（node！= NULL）
{
if（node-> ; data！= NULL）
{
printf（％s，node-> data）;
}
}
}
到目前为止不能打印出任何东西。我几乎肯定了它的指针问题。如果有人可以指出我（不是双关语）在正确的方向，那将是非常感谢。
谢谢
首先，我假设列表是一个用于 struct conscell *的typedef 。如果不是，应该是，否则你的代码不会编译没有吨的警告。
方案cons单元格应该是一个简单的单链表，而不是双重链接列表。所以你的单个细胞应该更像：
typedef conscell
{
unsigned char * data; //< ==用于内存缓冲区的unsigned char
struct conscell * next; //< ==只需一个next指针
} conscell;
我看到你只是打算打印符号，所以使用 char 而不是 unsigned char 可以为此目的工作，但是当您使用更多通用数据结构（如lambdas等）时，重新转到 unsigned char * 或 void * ，以引用持有这些类型的内存缓冲区更复杂的数据结构。
另一个看起来有点混乱的问题是，您正在使您的cons的每个单元格成为另一个cons单元格，例如这些代码行
if（token [0] =='（'）
{
strcpy （token，getToken（））;
node-> first = nextNode（node-> first）;
node-> rest = nextNode（node-> rest）;
正在递归添加cons单元格作为第一个和休息...但是不是链接列表应该如何，它应该有ap指向列表节点作为列表的头（而不是像您在这里执行的另一个cons-cell），然后列表中的每个节点指向列表中的一些数据和下一个节点。 / p>
接下来，当您分配内存时，您的内存泄漏遍及您的 createList（）函数，但是不要删除该内存（即，您有代码，如 node = NULL ，它们有效地是内存泄漏，因为您已经丢失了内存引用到分配的内存位置， code> node 最初指向）。您必须在节点指针上调用 free（），然后再分配 NULL 。
最后， printList（）不执行任何操作，只能打印您传递的列表的第一个元素...没有递归呼叫或循环循环到链表中的下一个节点。所以你不会打印很多这个功能。它应该看起来更像：
void printList（List node）
{
列表current = node;
while（current！= NULL）//< == end for the end-of-list
{
if（node-> data！= NULL）
{
printf（％s，node-> data）;
}
current = current-> next; //循环到链表中的下一个节点
}
}
所以总结一下，1）你的cons数据结构应该表示一个单一的链表，它由具有数据元素的结构数据类型和指向下一个节点的指针组成。通过指向第一个节点的头指针来访问被占用的列表。 2）在解析输入时，您应该从Scheme的 cons 操作之后将节点添加到链表的前端，并且scheme中的所有操作都是递归的，而折叠到右边，这意味着它们从一个基础案例（即，两个元素的共同）起作用，然后在该基础上扩展。所以如果你有一些类似（cons'd（cons'c（cons'b（cons'a'（）））））），你打印列表（dcba）。如果你愿意，它也可以帮助把令牌放入一个堆栈，作为递归解析输入，然后从堆栈输入到你的链表（有点像RPN计算器的工作方式）。
I'm a newbie at C, in the early stages of building a small Scheme interpreter. For this part of the project I'm trying to build a simple cons cell data structure. It should take a list like
(a b c)
and represent it internally like so:
[ ][ ] -> [ ][ ] -> [ ][/]
| | |
A B C
To test that it's working correctly, I have a print function to to echo out the input. Here is the code that isn't working:
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#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);
}
}
}
So far can't print out anything. I'm almost positive its a pointer issue. If anyone could point me (no pun intended) in the right direction, it'd be very much appreciated.
Thank you
First, I'm assuming List is a typedef for a struct conscell*. If it's not, it should be, otherwise your code won't compile without tons of warnings.
A scheme cons cell should be a simple singly linked list, not a doubly-linked list. So your individual cells should be more like:
typedef conscell
{
unsigned char *data; //<== use unsigned char for a memory buffer
struct conscell* next; //<== only a "next" pointer needed
} conscell;
I see you're just trying to print symbols at the moment, so using char rather than unsigned char can work for that purpose, but when you go with more generic data-structures like lambdas, etc., you're going to have to switch to either unsigned char* or void* for the reference to the memory buffer holding those types of more complex data-structures.
The other issue that seems a bit confusing is that you're making each cell of your cons cells another cons cell, for instance, these lines of code,
if (token[0] == '(')
{
strcpy(token, getToken());
node->first = nextNode(node->first);
node->rest = nextNode(node->rest);
}
are recursively adding cons cells as your "first" and "rest" ... but that's not how a linked-list should look like. It should have a pointer to a list-node as the "head" of the list (not another cons-cell like it seems you're doing here), and then each node in the list points to some data and the next node in the list.
Next, you have memory leaks all over the place with your createList() function as you allocate memory with it, but then never delete that memory (i.e., you have code like node = NULL which effectively is a memory leak because you've lost the memory reference to the allocated memory location that node was originally pointing to). You have to call free() on a node pointer before you assign NULL to it.
Finally, printList() doesn't do anything but print the first element of the list you pass it ... there are no recursive calls or loops to cycle to the next node in the linked list. So you're not going to be printing much with that function. It should look more like:
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
}
}
So to sum things up, 1) your cons data-structure should represent a singly linked list composed of a structure data-type having a data element and a pointer to the next node. The cons'ed list is accessed through a head pointer pointing to the first node. 2) As you parse the input, you should add nodes to the front of the linked list since Scheme's cons operation, and really all the operations in scheme, are recursive, and "fold to the right", meaning they work from a base-case (i.e., the cons'ing of two elements), and then expand on that base-case. So if you had something like (cons 'd (cons 'c (cons 'b (cons 'a '())))), you'd the print the list (d c b a). If you want, it could also help to put tokens into a stack as your recursively parse the input, and then from the stack input into your linked list (sort of like how a RPN calculator would work).
这篇关于Cons C单元格数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
