将结构从一个列表的末尾移动到另一个列表的开头

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

考虑到您对要求的描述，这个功能对我来说似乎非常好

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;
}

反正下个周期处理。

话虽如此，您的函数确实会从列表中删除最后一个元素。它只是不 return 它或以您可以看到的方式在您的代码中更改它。

一个选项是 return 最后一个单元格，而不是将其作为参数传递。

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);
}

Answer 2

函数 last_cell_out 必须通过引用接受它的参数，因为它改变了它们的原始值。否则该函数将具有未定义的行为，因为例如这个语句

list=NULL;

不改变列表的原始值。它仅更改其定义为具有原始列表值副本的参数的局部变量list。

所以函数至少要这样定义

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

考虑到对指针使用 typedef 不是一个好主意，因为它有时会使用户感到困惑。

而函数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;
    }       
}

将结构从一个列表的末尾移动到另一个列表的开头

moving struct from end of one list to start of another list

c

pointers

structure

list

singly-linked-list