清单未填写

Question

我写了一个反转列表的方法，结果列表还是空的。帮我们了解一下问题出在哪里。

反转列表的方法。

void reverseList(pLIST pL){
    pNODE pN = pL->top;
    pLIST pLReverse = createList();

    while(pN){
        pNODE pNew = malloc(sizeof(NODE));
        pNew->value = pN->value;
        if(!pLReverse->top){
            pNew->next = NULL;
            pLReverse->top = pNew;
        }
        else{
            pNew->next = pLReverse->top;
            pLReverse->top = pNew;              
        }

        pN = pN->next;
    }

    showList(pLReverse);
}

列表的结构

typedef struct Node{
    int value;
    struct Node * next;
} NODE, *pNODE;

typedef struct List{
    int len;
    pNODE top;
} LIST, *pLIST;

打印列表的方法

void showList(pLIST pL){
    if(isEmpty(pL)) printf("Empty\n");
    else{
        pNODE temp = pL->top;
        printf("Length: %d\n", pL->len);
        while(temp){
            printf("Pointer: %p\tValue: %d\tNext pointer: %p\n", temp, temp->value, temp->next);
            temp = temp->next;
        }
    }
}

Answer 1

首先，像这样为指针引入别名是个坏主意。

typedef struct List{
    int len;
    pNODE top;
} LIST, *pLIST;

例如，使用这样的别名，你不能声明一个指向常量列表的指针，因为这个声明

const pLIST list;

不等于

const struct List *list;

相反，它意味着

struct List * const list;

这不是要求。

考虑到这一声明

pLIST pLReverse = createList();

看来你是在动态地分配列表。没有必要这样做。列表可以被声明为具有自动存储期限的对象。

函数 reverseList 应该反转传递给它的列表本身，而不是在函数中创建一个新的列表。此外，你有一个内存泄漏，因为所创建的列表由指针指向的 pLReverse 不被释放。

下面是一个演示程序，展示了函数 reverseList 可以定义。

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

typedef struct Node
{
    int value;
    struct Node *next;
} Node;

typedef struct List
{
    size_t len;
    Node *head;
} List;

void init( List *list )
{
    list->len = 0;
    list->head = NULL;
}

int pushFront( List *list, int value )
{
    Node *new_node = malloc( sizeof( Node ) );

    int success = new_node != NULL;

    if ( success )
    {
        new_node->value = value;
        new_node->next = list->head;
        list->head = new_node;
        ++list->len;
    }

    return success;
}

void showList( const List *list )
{
    for ( Node *current = list->head; current != NULL; current = current->next )
    {
        printf( "%d -> ", current->value );
    }

    puts( "null" );
}

void reverseList( List *list )
{
    Node *current = list->head;
    list->head = NULL;

    while (  current != NULL )
    {
        Node *new_node = current;
        current = current->next;
        new_node->next = list->head;
        list->head = new_node;
    }
}

void freeList( List *list )
{
    while ( list->head != NULL )
    {
        Node *tmp = list->head;
        list->head = list->head->next;
        free( tmp ); 
    }
}

int main(void) 
{
    List list;
    init( &list );

    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        pushFront( &list, i );
    }

    showList( &list );

    reverseList( &list );

    showList( &list );

    freeList( &list );

    return 0;
}

程序输出为

9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null