此 Link 列表的头部指向递归语句后的位置

Question

我有一个简单的 link 列表程序，它将 create/print 它，然后打印它的最后 2 个数字（以相反的顺序）

cat link_list.c 
/**
 * C program to create and traverse a Linked List
 */

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

/* Structure of a node */
struct node {
    int data;          // Data 
    struct node *next; // Address 
}*head;


/* 
 * Functions to create and display list
 */
void createList(int n);
void traverseList();
void ReverseList(struct node *);


int main()
{
    int n;

    printf("Enter the total number of nodes: ");
    scanf("%d", &n);

    createList(n);

    printf("\nData in the list \n");
    traverseList();

    ReverseList(head);

    return 0;
}

/*
 * Create a list of n nodes
 */
void createList(int n)
{
    struct node *newNode, *temp;
    int data, i;

    head = (struct node *)malloc(sizeof(struct node));

    // Terminate if memory not allocated
    if(head == NULL)
    {
        printf("Unable to allocate memory.");
        exit(0);
    }


    // Input data of node from the user
    printf("Enter the data of node 1: ");
    scanf("%d", &data);

    head->data = data; // Link data field with data
    head->next = NULL; // Link address field to NULL


    // Create n - 1 nodes and add to list
    temp = head;
    for(i=2; i<=n; i++)
    {
        newNode = (struct node *)malloc(sizeof(struct node));

        /* If memory is not allocated for newNode */
        if(newNode == NULL)
        {
            printf("Unable to allocate memory.");
            break;
        }

        printf("Enter the data of node %d: ", i);
        scanf("%d", &data);

        newNode->data = data; // Link data field of newNode
        newNode->next = NULL; // Make sure new node points to NULL 

        temp->next = newNode; // Link previous node with newNode
        temp = temp->next;    // Make current node as previous node
    }
}


/*
 * Display entire list
 */
void traverseList()
{
    struct node *temp;

    // Return if list is empty 
    if(head == NULL)
    {
        printf("List is empty.");
        return;
    }
    
    temp = head;
    while(temp != NULL)
    {
        printf("Data = %d\n", temp->data); // Print data of current node
        temp = temp->next;                 // Move to next node
    }
}

static count=0, k=2;

ReverseList(struct node *head)
{
    if (head == NULL)
        return;
    else {
        ReverseList(head->next);
        count++;
        if (count <= k)
            printf("Data = %d\n", head->data);
    }
}

对于输入 1 2 3 ，它会先打印 3 2 1 然后正确打印 3 2 但我对 :

感到困惑

    if (head == NULL)
        return;

它 return 与 return 的确切含义；以及
之后头部指向的位置反向列表（头->下一个）；声明 ?

Answer 1

假设我们有一个简单的三节点列表，如下所示：

1 -> 2 -> 3

当我们最初调用 ReverseList 时，我们将 1 节点作为 head 传递，我们有这个调用链：

ReverseList(1 -> 2 -> 3 -> NULL)
  ReverseList(2 -> 3 -> NULL)
    ReverseList(3 -> NULL)
      ReverseList(NULL)
    printf(3)
  printf(2)
printf(1)

Answer 2

对于初学者，您忘记在函数定义中指定函数的 return 类型：

ReverseList(struct node *head)
{
    if (head == NULL)
        return;
    else {
        ReverseList(head->next);
        count++;
        if (count <= k)
            printf("Data = %d\n", head->data);
    }
}

你必须写：

void ReverseList(struct node *head)

关于你的问题：

I have confusion about the :
if (head == NULL)
    return;
what exactly it returns with return;, and where head is pointing after the ReverseList(head->next); statement ?

那么由于函数具有 return 类型 void 并且 return 语句不包含表达式，因此 return 语句 return 什么都没有.

函数参数head是函数的局部变量。函数不改变文件作用域中声明的指针头

struct node {
    int data;          // Data 
    struct node *next; // Address 
}*head;

在函数的第一次调用中，由于以下语句，参数 head 具有全局变量 head 的值：

 ReverseList(head);

如果值不等于 NULL 则函数递归调用自身并传递指针的值 head->next:

ReverseList(head->next);

所以在函数本身的第二次递归调用中，其参数 head 的值等于 head->next 的值，在此表达式中 head 是函数参数函数的前一次调用。

即参数head首先获取全局变量head的值，然后依次由下一个节点的数据成员next的值初始化参数。

因此对于包含值为 1、2、3 的节点的列表，您有

第 1 次通话参数head等于全局变量head

第二次通话参数head等于head->next指向值为1的节点

第三次通话参数head等于head->next->next指向值为2

的节点

第 4 次调用参数head等于head->next->next->next指向值为3

的节点

第 5 次通话参数 head 等于 head->next->next->next->next 等于 NULL

注意在函数内使用静态全局变量不是一个好主意

static count=0, k=2;

如果你想再次调用该函数，你需要记住重新初始化它们。最好让变量 k 成为函数参数。

函数可以按照下面的演示程序所示的方式定义。

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

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

int push( struct node **head, int data )
{
    struct node *new_node = malloc( sizeof( *new_node ) );
    int success = new_node != NULL;
    
    if ( success )
    {
        new_node->data = data;
        new_node->next = *head;
        *head = new_node;
    }
    
    return success;
}

void display( const struct node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }
    
    puts( "null" );
}

size_t display_last_n( const struct node *head, size_t n )
{
    size_t i = 0;
    
    if ( head != NULL )
    {
        i = display_last_n( head->next, n ) + 1;
        
        if ( !( n < i ) )
        {
            if ( i != 1 ) printf( ", " );
            printf( "%d", head->data );
        }
    }
    
    return i;
}

void clear( struct node **head )
{
    while ( *head )
    {
        struct node *tmp = *head;
        *head = ( *head )->next;
        free( tmp );
    }
}

int main(void) 
{
    struct node *head = NULL;
    const int N = 10;
    
    for ( int n = N; n--; )
    {
        push( &head, n );
    }
    
    display( head );
    
    for ( size_t i = 0; i < N; i++ )
    {
        display_last_n( head, i + 1 );
        putchar( '\n' );
    }
    
    clear( &head );
    
    return 0;
}

程序输出为：

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

此 Link 列表的头部指向递归语句后的位置

Where head of this Link list points after recursive statement

c

recursion

reverse

singly-linked-list

function-definition