结构指针分配未分配预期值 - 链表

Question

我正在用 C 编写一个反转链表的程序。在 gdb 中调试代码时，在 while 循环的第二次迭代后，函数，reverse，退出。

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

void insert (int number);
void print ();


struct Node {
    int data;
    struct Node *link;
} head, *last_node;

int count (struct Node *);
void reverse (struct Node *);

int main () {
    int number, choice = 0;

    while (choice != 4) {
        printf ("\nChoose the action: ");
        printf ("\n 1. Insert ");
        printf ("\n 2. Print List ");
        printf ("\n 3. Reverse");
        printf ("\n 4. Exit \n");

        scanf("%d", &choice);

        switch (choice) {

            case 1 : printf ("\nEnter number to be inserted: ");
            scanf ("%d", &number);
            insert (number);
            break;

            case 2 : printf ("\nHere is/are linked list element/s: ");
            print();
            break;

            case 3 : printf ("\nLinked List Reversed ");
            reverse(&head);
            break;

            case 4 : 
            default: exit(0);
        }
    }
}

void insert (int number) {
    if (head.data == 0) {
        head.data = number;
        head.link = NULL;
        last_node = &head;
    } else {
        struct Node *new_node;
        new_node = (struct Node *) malloc (sizeof(struct Node));
        new_node -> data = number;
        new_node -> link = NULL;
        last_node -> link = new_node;
        last_node = new_node;
    }
}

void print () {
    struct Node *start;
    start = &head;
    do {
        printf ("%d ", start->data);
        start = start->link;
    } while (start != NULL);
    printf ("\n");
}


void reverse (struct Node *start) {
    struct Node *temp1 = NULL, *temp2;

    while (start->link != NULL) {
        temp2 = start->link;
        start->link = temp1;
        temp1 = start;
        start = temp2;
    } 
}

在运行 reverse函数后只显示链表的第一个元素。

Answer 1

您的方法有几个缺点。

第一个是声明全局变量是个坏主意start。

struct Node {
    int data;
    struct Node *link;
} head, *last_node;

此外，如果它是一个单链表，那么节点应该被插入到列表的开头。所以不需要全局指针last_node。

函数reverse处理局部变量start因为函数参数是函数的局部变量

void reverse (struct Node *start)

函数中没有改变指向起始节点的原始指针，因为函数处理的是它的副本。

并且该函数必须检查传递的参数是否已经等于 NULL。

反向算法背后有一个简单的逻辑。

您应该只插入已经存在的节点，就像您在将新节点推入列表的函数中执行此操作一样。

并且指向起始节点（头）的指针必须使用指向它的指针通过引用传递。

这是一个演示程序。

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

struct Node 
{
    int data;
    struct Node *link;
};

int push_front( struct Node **head, int data )
{
    struct Node *current = malloc( sizeof( struct Node ) );
    int success = current != NULL;

    if ( success )
    {
        current->data = data;
        current->link = *head;
        *head = current;
    }

    return success;
}

void output( struct Node *head )
{
    for ( ; head != NULL; head = head->link )
    {
        printf( "%d -> ", head->data );
    }

    puts( "NULL" );
}

void reverse( struct Node **head )
{
    struct Node *current = *head;
    *head = NULL;

    while ( current != NULL )
    {
        struct Node *tmp = current;
        current = current->link;
        tmp->link = *head;
        *head = tmp;
    }
}    

int main(void) 
{
    struct Node *head = NULL;

    const int N = 10;

    for ( int i = 0; i < N; i++ ) push_front( &head, i );

    output( head );

    reverse( &head );

    output( head );

    return 0;
}

它的输出是

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

当然，您需要在列表实现后附加一个函数，该函数在不再需要时删除列表的所有节点。

结构指针分配未分配预期值 - 链表

Structure pointer assignment not assigning expected value - Linked Lists

c

reverse

reference

list

singly-linked-list