Блог

Предположим, у меня есть следующая структура:

 struct _node {
    int id;
    char *name;
    struct node *next;
};
  

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

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

Вот моя функция:

 struct _node *containSubstr(struct _node *head, char needle[]) {
    if (head == NULL) {
        printf("BLOOP BLEEP BOOP BEEP.n");
        exit(EXIT_FAILURE);
    }

    struct _node *curr = head;
    struct _node *returnHead = createEmptyNode();

    while (curr != NULL) {
        char haystack[strlen(curr->name)];
        strcpy(haystack, curr->name);

        strToLower(needle);
        strToLower(haystack);

        if (strstr(haystack, needle) != NULL) {
            // this is where I get the infinite loop
            append(returnHead, curr);
        }

        curr = curr->next;
    }

    return returnHead;
}
  

Функции append и createEmptyNode протестированы и работают нормально.

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

Вот моя функция добавления:

 void append(struct _node *head, struct _node *newNode) {
    if (head == NULL) {
        printf("BLOOP BLEEP BOOP BEEP.n");
        exit(EXIT_FAILURE);
    }

    struct _node *curr = head;

    if(curr == NULL) {
        head = newNode;
    }
    else {
        while(curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}
  

Представьте такой случай: у вас есть список L, который содержит всего 2 узла (A и B) в вашем связанном списке. Представьте, что оба узла A и B содержат подстроку, которую вы ищете:

Исходный список L:

A-> B-> NULL

Итак, после первой итерации ваш новый список L2 должен выглядеть следующим образом:

A-> NULL

Но в вашей функции добавления вы не создаете глубокую копию нового узла. Следовательно, ваш новый список L2 выглядит следующим образом:

Empty_node->A-> B-> NULL

На следующем шаге вы переходите к узлу B. Итак, вы берете свой L2 и добавляете туда B. Ваш L2 после второй итерации выглядит следующим образом:

Empty_node->A->B-> B (B указывает на себя).

Поскольку вы не создаете глубоких копий, вы фактически всегда работаете со списком L, и когда вы добавляете узел B к тому, что вы считаете списком L2, вы фактически добавляете B к L, а затем B указывает на себя ( curr->next = newNode; в вашей append функции). Итак, на следующей итерации вы снова спрашиваете, содержит ли B искомую строку.

Заключение

При создании нового списка необходимо создавать глубокие копии.

В текущей настройке ваша append функция изменяет исходный список.