Минусы Сотовая структура данных в C - PullRequest
Новая
       15

Минусы Сотовая структура данных в C

3 голосов
/ 24 мая 2011

Я новичок в C, на ранних стадиях создания небольшого интерпретатора Scheme.Для этой части проекта я пытаюсь построить простую структуру данных в ячейке.Он должен взять список вроде

(a b c)

и представить его внутренне так: 

[ ][ ] -> [ ][ ] -> [ ][/]
 |         |         |
 A         B         C

Чтобы проверить, что он работает правильно, у меня есть функция печати дляповторить ввод.Вот код, который не работает: 

#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);

      }
    }
}

Пока ничего не могу распечатать.Я почти уверен, что это проблема с указателем.Если бы кто-нибудь мог направить меня (без каламбура) в правильном направлении, это было бы очень признательно.

Спасибо

Ответы [ 2 ]

2 голосов
/ 24 мая 2011

Во-первых, я предполагаю, что List является typedef для struct conscell*.Если это не так, то так и должно быть, иначе ваш код не будет компилироваться без множества предупреждений.

Ячейка схемы должна быть простым односвязным списком, а не двусвязным списком.Таким образом, ваши отдельные ячейки должны быть больше похожи на: 

typedef conscell 
{
    unsigned char *data;   //<== use unsigned char for a memory buffer
    struct conscell* next; //<== only a "next" pointer needed
} conscell;

Я вижу, что вы просто пытаетесь напечатать символы в данный момент, так что использование char вместо unsigned char может работать для этой цели, но когдавы идете с более общими структурами данных, такими как лямбды и т. д., вам придется переключиться на unsigned char* или void* для ссылки на буфер памяти, содержащий эти типы более сложных структур данных.

Другая проблема, которая кажется немного запутанной, состоит в том, что вы делаете каждую ячейку ваших cons-ячеек другой cons-ячейкой, например, эти строки кода 

if (token[0] == '(')
{         
   strcpy(token, getToken());
   node->first = nextNode(node->first);
   node->rest = nextNode(node->rest);         
 }

рекурсивно добавляют cons-ячейкикак ваши "first" и "rest" ... но не так, как должен выглядеть связанный список.Он должен иметь указатель на узел списка в качестве «заголовка» списка (а не на другую конс-ячейку, как кажется, что вы здесь делаете), а затем каждый узел в списке указывает на некоторые данные и следующий узел всписок.

Далее, у вас есть утечки памяти повсюду с вашей функцией createList(), когда вы выделяете ей память, но затем никогда не удаляете эту память (т. е. у вас есть код, такой как node = NULL, который эффективноэто утечка памяти, потому что вы потеряли ссылку на выделенную область памяти, на которую изначально указывал node).Вы должны вызвать free() для указателя узла, прежде чем назначить ему NULL.

Наконец, printList() ничего не делает, но печатает первый элемент списка, который вы передаете ему ...нет рекурсивных вызовов или циклов для перехода к следующему узлу в связанном списке.Таким образом, вы не собираетесь много печатать с этой функцией.Это должно выглядеть примерно так: 

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 должна представлять собой односвязный список, состоящий из типа данных структуры, имеющего элемент данных и указатель наследующий узелДоступ к списку заключенных осуществляется через указатель головы, указывающий на первый узел.2) Когда вы анализируете входные данные, вы должны добавить узлы в начало связанного списка, так как операция Схемы cons, и на самом деле все операции в схеме являются рекурсивными и «сворачиваются вправо», то есть они работают избазовый случай (т. е. состоящий из двух элементов), а затем разверните этот базовый случай.Так что, если у вас было что-то вроде (cons 'd (cons 'c (cons 'b (cons 'a '())))), вы бы распечатали список (d c b a).Если вы хотите, это также может помочь поместить токены в стек, так как вы рекурсивно анализируете входные данные, а затем из стекового ввода в свой связанный список (вроде как будет работать калькулятор RPN).

0 голосов
/ 25 мая 2011

Также добавьте \ n в ваш printf, чтобы убедиться, что он сброшен в стандартный вывод: 

printf("%s\n", node->data);
...