Обобщенный связанный список: добавление дочерней ссылки при открытии скобок - PullRequest
Новая
       3

Обобщенный связанный список: добавление дочерней ссылки при открытии скобок

0 голосов
/ 14 ноября 2018

Вот мой код для генерации GLL для строкового ввода: a, (b, c), d, где (b, c) будет связан как дочерний элемент при следующей ссылке a. 

GLL* generateList(char poly[])
{
    GLL* newNode = NULL, *first = NULL, *ptr = NULL;

    while (poly[i] != '\0')
    {
        if (poly[i] == ')')
        {
            return first;
        }
        else
        {
            if (poly[i] != ',')
            {
                if (poly[i] != '(')
                {
                    newNode = createNode(poly[i], 0);
                }
                else
                {
                    ++i;
                    newNode = createNode('#', 1);
                    newNode->dlink = generateList(poly);
                }
            }
        }

        if (first != NULL)
        {
            ptr = first;
            while (ptr->next != NULL)
            {
                ptr = ptr->next;
            }
            ptr->next = newNode;
        }
        else
        {
            first = newNode;
        }
        i++;
    }
    return first;
}

А вот структура, которую я использовал для каждого узла. 

    typedef struct gll
    {
       int tag;
       struct gll* next;
       char data;
       struct gll* dlink;
    } GLL;

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

Примечание: я объявил i = 0 как глобальную переменную для хранения позиции символа.

Редактировать: вот функция createNode 

GLL* createNode(char value, int flag)
{
 GLL* newNode;

 newNode = (GLL *) malloc(sizeof(GLL)*1);

 newNode->data = value;
 newNode->dlink = NULL;

 newNode->tag = flag;
 newNode->next = NULL;

return newNode;
}

1 Ответ

0 голосов
/ 14 ноября 2018

Как мне тогда это сделать?

Вы можете сделать что-то подобное: 

#include <stdbool.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct gll
{
    int tag;
    struct gll* next;
    char data;
    struct gll* dlink;
} GLL;

GLL* createNode(char value, int flag)
{
    GLL* newNode = calloc(1, sizeof(*newNode));

    if (!newNode)
        return NULL;

    newNode->tag = flag;
    newNode->data = value;
    return newNode;
}

void freeList(GLL *list)
{
    for (GLL *current_node = list, *temp; current_node; current_node = temp) {
        temp = current_node->next;
        freeList(current_node->dlink);
        free(current_node);
    }
}

GLL* generateList(char *poly, size_t *pos)
{
    size_t const length = strlen(poly);
    GLL *head = NULL;
    GLL *tail = NULL;

    for (; *pos < length; ++*pos) {
        if (poly[*pos] == '(') {
            ++*pos;  // don't have the next called generateList() read '(' again
            tail->dlink = generateList(poly, pos);
            if (!tail->dlink) {
                freeList(head);
                return NULL;
            }
            continue;
        }
        else if (poly[*pos] == ')') {
            return head;
        }
        else if (isalpha((char unsigned)poly[*pos])) {
            if (!head) {
                head = tail = createNode(poly[*pos], 0);
            }
            else {
                tail->next = createNode(poly[*pos], 0);
                tail = tail->next;
            }
            continue;
        }
        else if (poly[*pos] == ',')
            continue;

        fputs("Format error :(\n\n", stderr);
        freeList(head);
        return NULL;
    }

    return head;
}

void printList(GLL *list)
{
    for (GLL *node = list; node; node = node->next) {
        printf("%c ", node->data);
        if (node->dlink) {
            putchar('(');
            printList(node->dlink);
            printf("\b) ");
        }
    }
}

int main(void)
{
    size_t pos = 0;
    GLL *list = generateList("a,(b,(c,d,e(f)),g,h),i,j,k", &pos);

    printList(list);
    putchar('\n');

    freeList(list);
}

Вывод

a (b (cde(f)) gh) ijk

Кроме того, если флаг равен true, это означает, что данные не должны рассматриваться, но есть дочерний список, который необходимо связать.

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

...