перемещение структуры из конца одного списка в начало другого списка

Question

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

void last_cell_out(CellPtr list, CellPtr c)
{
    if (list==NULL)/*if list is empty*/
        return;/*doing nothing*/
    if (list->next==NULL)/*if theres only one cell in the list*/
    {
        c=list;
        list=NULL;
        return;/*deleting from list and moving to c*/
    }
    if (list->next->next==NULL)
    {
        c=list->next;
        list->next=NULL;
    }
    else
        last_cell_out(list->next, c);
    return;
}

CellPtr new_first_cell(CellPtr list, CellPtr c)
{
    c->next=list;
    return c;/*returnes the start of the list*/
}

Answer 1

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

list=NULL;

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

Так что функция должна быть определена как минимум следующим образом

void last_cell_out(CellPtr *list, CellPtr *c)
{
    if ( *list == NULL )/*if list is empty*/
    {
        *c = NULL;
        return;/*doing nothing*/
    }        
    else if ( ( *list )->next == NULL )/*if theres only one cell in the list*/
    {
        *c = *list;
        *list = NULL;
        return;/*deleting from list and moving to c*/
    }
    else if ( ( *list )->next->next == NULL )
    {
        *c = ( *list )->next;
        ( *list )->next = NULL;
        return;/*deleting from list and moving to c*/
    }
    else
    {
        last_cell_out( &( *list )->next, c );
        return;/*doing nothing*/
    }        
}

Вот демонстрационная программа.

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

struct Cell
{
    int data;
    struct Cell *next;
};

typedef struct Cell *CellPtr;

void last_cell_out(CellPtr *list, CellPtr *c)
{
    if ( *list == NULL )/*if list is empty*/
    {
        *c = NULL;
        return;/*doing nothing*/
    }        
    else if ( ( *list )->next == NULL )/*if theres only one cell in the list*/
    {
        *c = *list;
        *list = NULL;
        return;/*deleting from list and moving to c*/
    }
    else if ( ( *list )->next->next == NULL )
    {
        *c = ( *list )->next;
        ( *list )->next = NULL;
        return;/*deleting from list and moving to c*/
    }
    else
    {
        last_cell_out( &( *list )->next, c );
        return;/*doing nothing*/
    }        
}

CellPtr new_first_cell(CellPtr list, CellPtr c)
{
    c->next = list;
    return c;/*returnes the start of the list*/
}

void print_cells( CellPtr list )
{
    for ( CellPtr current = list; current != NULL; current = current->next )
    {
        printf( "%d -> ", current->data );
    }

    puts( "NULL" );
}

int main(void) 
{
    CellPtr list = NULL;

    CellPtr cell = malloc( sizeof( struct Cell ) );
    cell->data = 1;

    list = new_first_cell( list, cell );

    print_cells( list );

    last_cell_out( &list, &cell );

    CellPtr list1 = NULL;

    list1 = new_first_cell( list1, cell );

    print_cells( list );
    print_cells( list1 );

    last_cell_out( &list1, &cell );

    free( cell );

    return 0;
}

Его вывод

1 -> NULL
NULL
1 -> NULL

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

А функцию last_cell_out можно написать проще без рекурсии. Например

void last_cell_out(CellPtr *list, CellPtr *c)
{
    if ( *list )
    {
        while ( ( *list )->next ) list = &( *list )->next;
    }

    *c = *list;
    *list = NULL;
}

или с рекурсией

void last_cell_out(CellPtr *list, CellPtr *c)
{
    if ( *list && ( *list )->next )
    {
        last_cell_out( &( *list )->next, c );
    }
    else
    {
        *c = *list;
        *list = NULL;
    }       
}

Answer 2

Эта функция мне кажется вполне подходящей, учитывая, как вы описали свои требования

CellPtr new_first_cell(CellPtr list, CellPtr c)
{
    c->next=list;
    return c;/*returnes the start of the list*/
}

Однако у last_cell_out есть некоторые проблемы.

Прежде всего вам это не нужноблок кода

if (list->next->next==NULL)
{
    c=list->next;
    list->next=NULL;
}

в любом случае это будет рассматриваться в следующем цикле.

При этом ваша функция удаляет последний элемент из списка.Он просто не возвращает его и не изменяет его в вашем коде так, как вы можете видеть это.

Один из вариантов - вернуть последнюю ячейку вместо передачи ее в качестве параметра.

CellPtr last_cell_out(CellPtr *listPtr)
{
    CellPtr list = *listPtr;
    if (list==NULL)/*if list is empty*/
        return NULL;/*doing nothing*/
    if (list->next==NULL)/*if theres only one cell in the list*/
    {
        *listPtr = NULL;
        return list;/*deleting from list and return*/
    }
    return last_cell_out(&(list->next));
}

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

void last_cell_out(CellPtr *listPtr, CellPtr *c)
{
    CellPtr list = *listPtr;
    if (list==NULL)/*if list is empty*/
    {
        *c = NULL;
        return;/*doing nothing*/
    }
    if (list->next==NULL)/*if theres only one cell in the list*/
    {
        *c=list;
        *listPtr = NULL;
        return;/*deleting from list and moving to c*/
    }
    last_cell_out(&((*listPtr)->next), c);
    return;
}

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

CellPtr last_cell_out(CellPtr *listPtr)
{
    CellPtr list = *listPtr;
    if(list == NULL)
        return NULL;

    if(list->next == NULL) {
        *listPtr = NULL;
        return list;
    }

    while(list->next->next != NULL)
        list = list->next;

    CellPtr tmp = list->next;
    list->next = NULL;
    return tmp;
}

Полная программа испытаний:

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

typedef struct cell *CellPtr;
typedef struct cell
{
    int contents; /* contents of the cell */
    CellPtr next; /* next cell in the list */
} Cell;

CellPtr last_cell_out(CellPtr *listPtr)
{
    CellPtr list = *listPtr;
    if(list == NULL)
        return NULL;

    if(list->next == NULL) {
        *listPtr = NULL;
        return list;
    }

    while(list->next->next != NULL)
        list = list->next;

    CellPtr tmp = list->next;
    list->next = NULL;
    return tmp;
}

CellPtr new_first_cell(CellPtr list, CellPtr c)
{
    c->next=list;
    return c;/*returnes the start of the list*/
}

void show_list(CellPtr list)
{
    if(list == NULL) {
        printf("\n");
        return;
    }

    printf("%d ", list->contents);
    show_list(list->next);
}

int main()
{
    CellPtr list = NULL;
    CellPtr out;
    int i;

    show_list(list);

    CellPtr elem = malloc(sizeof(struct cell));
    elem->contents = 0;
    list = new_first_cell(list, elem);

    show_list(list);

    out = last_cell_out(&list);
    show_list(list);
    list = new_first_cell(list, out);
    show_list(list);

    for(i = 1; i < 5; ++i) {
        CellPtr elem = malloc(sizeof(struct cell));
        elem->contents = i;
        list = new_first_cell(list, elem);
    }

    show_list(list);
    out = last_cell_out(&list);
    show_list(list);
    list = new_first_cell(list, out);
    show_list(list);
}