时间戳

首页 > 解决方案 > 通用链表：每当出现左括号时添加子链接

c - 通用链表：每当出现左括号时添加子链接

问题描述

这是我为字符串输入生成 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;
}

标签： cdata-structureslinked-list

解决方案

那我该怎么做呢？

你可以这样做：

#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

此外，如果 flag 为真，则表示不考虑数据，但有要链接的子列表。

抱歉，如果节点没有数据，我不明白怎么会有子列表。

推荐阅读