Разделение связанного списка

Question

Почему разделенные списки всегда пусты в этой программе? (Он получен из кода на странице Wikipedia в связанных списках.)

/* 
    Example program from wikipedia linked list article
    Modified to find nth node and to split the list
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct ns
{
    int data;
    struct ns *next; /* pointer to next element in list */
} node;

node *list_add(node **p, int i)
{
    node *n = (node *)malloc(sizeof(node));
    if (n == NULL)
        return NULL;

    n->next = *p; //* the previous element (*p) now becomes the "next" element */
    *p = n;       //* add new empty element to the front (head) of the list */
    n->data = i;

    return *p;
}

void list_print(node *n)
{
    int i=0;
    if (n == NULL)
    {
        printf("list is empty\n");
    }
    while (n != NULL)
    {
        printf("Value at node #%d = %d\n", i, n->data);
        n = n->next;
        i++;
    }
}

node *list_nth(node *head, int index) {
    node *current = head;
    node *temp=NULL;
    int count = 0; // the index of the node we're currently looking at
    while (current != NULL) {
        if (count == index)
            temp = current;
        count++;
        current = current->next;
    }
    return temp;
}
/* 
This function is to split a linked list:
Return a list with nodes starting from index 'int ind' and
step the index by 'int step' until the end of list.
*/
node *list_split(node *head, int ind, int step) {
    node *current = head;
    node *temp=NULL;
    int count = ind; // the index of the node we're currently looking at
    temp = list_nth(current, ind);
    while (current != NULL) {
        count = count+step;
        temp->next = list_nth(head, count);
        current = current->next;
    }

    return temp; /* return the final stepped list */
}

int main(void)
{
    node *n = NULL, *list1=NULL, *list2=NULL, *list3=NULL, *list4=NULL;
    int i;
    /* List with 30 nodes */
    for(i=0;i<=30;i++){
        list_add(&n, i);
    }
    list_print(n);

    /* Get 1th, 5th, 9th, 13th, 18th ... nodes of n etc */ 

    list1 = list_split(n, 1, 4);

    list_print(list1);

    list2 = list_split(n, 2, 4); /* 2, 6, 10, 14 etc */   
    list_print(list2);

    list3 = list_split(n, 3, 4); /* 3, 7, 11, 15 etc */   
    list_print(list3);

    list3 = list_split(n, 4, 4); /* 4, 8, 12, 16 etc */   
    list_print(list4);

    getch();
    return 0;
}

Answer 1

 temp = list_nth(current, ind);

 while (current != NULL) {
        count = count+step;
        temp->next = list_nth(head, count);
        current = current->next;
    }

Вы находите правильный элемент, чтобы начать разделение, но посмотрите, что происходит с темпом с тех пор ... вы назначаете только темп-> следующий.

Вам необходимо отслеживать как голову вашего разделенного списка, так и хвост, куда вы вставляете новые элементы.

Answer 2

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

Нарисуйте схему связанного списка и следуйте своей логике:

[0]->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]->...->[10]->[NULL]

Answer 3

Ваше описание того, что list_split должен вернуть, довольно ясно, но не ясно, что должно произойти, если что-нибудь, с первоначальным списком. Предполагая, что это не должно измениться:

node *list_split(node *head, int ind, int step) {
    node *current = head;
    node *newlist=NULL;
    node **end = &newlist;
    node *temp = list_nth(current, ind);

    while (temp != NULL) {
        *end = (node *)malloc(sizeof(node));
        if (*end == NULL) return NULL;
        (*end)->data = temp->data;
        end = &((*end)->next);
        temp = list_nth(temp, step);
    }

    return newlist; /* return the final stepped list */
}

(Вы, вероятно, хотите отделить подпрограмму list_insert от той, которая вставляет новую узел в данном месте. list_add не очень полезен, так как он всегда добавляет к начало списка.)

Answer 4

Программа, на самом деле, имеет более одной проблемы.

• Индексы не являются родным способом обращения к содержимому связанного списка. Обычно используются указатели на узлы или итераторы (которые являются замаскированными указателями на узлы). При использовании индексов доступ к узлу имеет линейную сложность (O(n)) вместо константы O(1).

• Обратите внимание, что list_nth возвращает указатель на «живой» узел в списке, а не копию. Присваивая temp->next в list_split, вы переписываете оригинальный список вместо создания нового (но может быть, это намеренно?)

• Внутри list_split, temp никогда не продвигается, поэтому цикл просто продолжает прикреплять узлы к голове, а не к хвосту.

• Из-за использования list_nth для поиска узлов путем перебора всего списка с начала, list_split имеет квадратичное время (O(n**2)) вместо линейного времени. Лучше переписать функцию, чтобы выполнить итерацию по списку один раз и скопировать (или повторно присоединить) требуемые узлы при их прохождении, вместо вызова list_nth. Или вы можете написать current = list_nth(current, step).

• [РЕДАКТИРОВАТЬ] Забыл упомянуть. Поскольку вы переписываете исходный список, запись list_nth(head, count) неверна: он будет перемещаться по «закороченному» списку, а не по неизмененному.