Назначение узлов (реверсирование связанного списка)

Я хочу написать итеративный и рекурсивный способ перевернуть связанный список.

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

node *reverse(node *initial){
    node *prev = initial;
    node *nextNode;
    nextNode = (node *)malloc(sizeof(struct node));
    nextNode = initial->next;
    if(nextNode->next == NULL){
        return  prev;
    }
    else{
        nextNode = reverse(nextNode);
        nextNode->next = prev;
    }
}

Строка nextNode = initial->next; приводит к сбою программы. Я уверен, что есть много других проблем с этим кодом, и хотя я открыт для предложений, если он фатально некорректен, я в основном просто хочу устранить эту ошибку, чтобы я мог самостоятельно отладить остальное. В итерационной версии некоторые из похожих строк, приводящих к сбою программы:

startA = startA->next; // startA is a node pointer
backNode = startB; // backNode and startB are both node pointers
backNode->data = frontNode->data; //both ints
frontNode->data = temp; //again both ints

По запросу остальная часть кода:

main(){
node *  start = buildList();
int i;
int nodeSize = sizeof(struct node);
reverse(start);
}

И buildList:

node *buildList(){
node *head = NULL;
node *second = NULL;
node *third = NULL;
node *fourth = NULL;
node *fifth = NULL;

head = (node *)malloc(sizeof(struct node));
second = (node *)malloc(sizeof(struct node));
third = (node *)malloc(sizeof(struct node));
fourth = (node *)malloc(sizeof(struct node));
fifth = (node *)malloc(sizeof(struct node));

head->data = 1;
head->next = second;

second->data  =2;
second->next = third;

third->data = 3;
third->next = fourth;

fourth->data =4;
fourth->next = fifth;

fifth->data = 5;
fifth->next = NULL;

return head;    
}
4 голоса | спросил CowGoes 19 J0000006Europe/Moscow 2012, 01:25:11

2 ответа


0

Вот краткое руководство для вас:

node *reverse(node *initial){

    if (initial is NULL)
        /* this is an empty list so return */
        return a null pointer;

    if (initial->next is NULL)
        /* this is the recursion base case under normal operation - one elem left */
        return initial;

    node *prev = initial;
    node *nextNode = initial->next;

    /* reverse the rest of the list starting at the next node */
    nextNode = reverse(nextNode);

    /* now just reverse the pointers */
    initial->next->next = prev;
    /*
     * but remember that prev->next still points to the wrong node,
     * we need to clear that 
     */
    prev->next = NULL;

    /* you were also missing the return case here */
    /* we want to keep track of the last element (the new head element) */
    /* keep passing this back up through the recursive steps */
    return nextNode;

}
ответил Jis Ben 19 J0000006Europe/Moscow 2012, 04:58:10
0

Обратите внимание, что при разыменовании nextNode->next в вашем if, вы не проверили на nextNode == NULL.

По сути, вы делаете:

if (initial->next->next == NULL)

Что здесь происходит, если initial->next == NULL? Это также проблема с вашей рекурсией base-case .

Кроме того, ваш malloc потрачен впустую и приведет к утечке памяти: вы присваиваете nextNode новый блок памяти, затем теряете ссылку на этот блок, когда вы назначаете что-то еще для nextNode в следующей строке: nextNode = initial->next; A malloc здесь не нужен: вы не добавляете новые узлы в свой список, а только переставляете имеющиеся у вас узлы.

При реализации рекурсии внимательно рассмотрите свой базовый вариант . С вашим кодом вы хотите выполнить рекурсивный просмотр списка до последнего узла, а затем использовать return, чтобы построить список снова, в обратном направлении. Как вы узнаете, когда находитесь на последнем узле в списке? Это ваш базовый случай , и ваша функция рекурсии должна начинаться именно там. Можете ли вы определить это, используя только аргумент вашей функции?

Это не сильно отличается от вашего текущего кода, но код, который вы опубликовали, содержит ряд ошибок.

ответил pb2q 19 J0000006Europe/Moscow 2012, 01:35:55

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132