论坛 › 新手乐园 › 这个好难求指导！

a905448839 发表于 2023-4-9 21:38:00

这个好难求指导！

以下代码中的struct Node *reversed(struct Node *head)函数始终无法理解如何实现。。
不知道如何去生动形象理解，或者有大佬以图片或者动图或视频告知以下吗？


struct Node *reversed(struct Node *head)
{
    struct Node *pre;         //pre指针表示当前节点的前一个节点
    struct Node *cur;         //cur指针表示当前节点
    pre = NULL;               //初始的前一个节点为NULL，因为反转后最后一个节点为NULL
    cur = head;               //初始的当前节点为头结点
   
    while(cur)                //从头结点遍历全部节点
    {
      struct Node* next = cur->next;//定义了一个Node结构体的指针next变量 用来保存下一个节点的指针
            //在while循环体内 next是个局部变量 每次循环结束他都会被摧毁 不会影响链表其他部位
      cur->next = pre;                //将当前节点的指针指向前一个节点
      pre = cur;                      //更新前一个节点为当前节点
      cur = next;                     //当前节点指向下一个节点
    }
    return pre;   //返回反转后的头结点指针
}


完整代码：
#include<stdio.h>
#include<stdlib.h>

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

void printNode(struct Node *head);
void insertNode(struct Node **head, int value);
struct Node *reversed(struct Node *head);

void insertNode(struct Node **head, int value)
{
        struct Node *previous;//current上一个节点的指针
        struct Node *current;//当前位置   指向比value大的节点指针
        struct Node *new;
       
        current = *head;
        previous = NULL;
       
        while(current != NULL && current->value < value)
        {
                previous = current;
                current = current->next;
        }
        new = (struct Node *)malloc(sizeof(struct Node));
        if(new == NULL)
        {
                printf("内存分配失败！\n");
                exit(1);
        }
       
        new->value = value;
        //previous->next = new;这个先不用写 后面要判断他是不是为NULL
        new->next = current;
       
        if(previous == NULL)//previous为NULL只有一种情况（因为把current赋值给previous 且current不为NULL才能赋值）
                            //所以current本身一进来就为NULL 空的单链表
        {
                *head = new;//所以将*head指针修改为new    这个new是唯一一个节点

        }
        else
        previous->next = new;


}

void printNode(struct Node *head)
{
        struct Node *current;
       
        current = head;
        while(current != NULL)
        {
                printf("%d ",current->value);
                current = current->next;

        }
        putchar('\n');

}


struct Node *reversed(struct Node *head)
{
    struct Node *pre;         //pre指针表示当前节点的前一个节点
    struct Node *cur;         //cur指针表示当前节点
    pre = NULL;               //初始的前一个节点为NULL，因为反转后最后一个节点为NULL
    cur = head;               //初始的当前节点为头结点
   
    while(cur)                //从头结点遍历全部节点
    {
      struct Node* next = cur->next;//定义了一个Node结构体的指针next变量 用来保存下一个节点的指针
            //在while循环体内 next是个局部变量 每次循环结束他都会被摧毁 不会影响链表其他部位
      cur->next = pre;                //将当前节点的指针指向前一个节点
      pre = cur;                      //更新前一个节点为当前节点
      cur = next;                     //当前节点指向下一个节点
    }
    return pre;   //返回反转后的头结点指针
}


int main(void)
{
        struct Node *head = NULL;
        int input;
       
        while(1)
        {
                printf("请输入一个整数（输入-1表示结束）：");
                scanf("%d",&input);
                if(input == -1)
                {
                        break;       
                }
                insertNode(&head, input);
                printNode(head);       
        }

        printf("\n下面将单链表a原地反转...\n");
    head = reversed(head);
    printNode(head);


        return 0;
}

isdkz 发表于 2023-4-9 21:41:33

这个代码的主要目的是实现链表的反转。为了帮助您更好地理解这个过程，我将逐步向您解释代码以及代码的逻辑。为了进一步说明这个过程，我还将使用一些简单的示例进行说明。

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> NULL

首先，我们定义两个指针，pre 和 cur。pre 表示当前节点的前一个节点，而 cur 表示当前节点。

1、初始化 pre 和 cur：
pre = NULL
cur = head（也就是 1）

2、进入 while 循环，开始遍历链表的每个节点。在每次循环中，我们将执行以下操作：

a) 用 next 临时存储 cur 的下一个节点，以便在后续操作中使用。在这个例子中，第一次循环时，next 将指向 2。

b) 将 cur（当前节点）的 next 指针指向 pre（前一个节点）。第一次循环时，将 1 的 next 指针指向 NULL。

c) 更新 pre 和 cur。将 pre 设置为 cur，将 cur 设置为 next。在这个例子中，第一次循环后，pre 变为 1，cur 变为 2。

3、继续循环，直到 cur 变为 NULL，即遍历完整个链表。

在完成循环后，链表将被反转，如下所示：NULL <- 1 <- 2 <- 3 <- 4

最后，返回 pre（也就是新链表的头结点，也就是 4）。

在这个过程中，我们通过更新每个节点的 next 指针，使其指向前一个节点，从而实现链表的反转。希望这种解释方式能帮助您更好地理解这段代码的逻辑。

为了更好地理解这个过程，您可以在纸上画出链表的每一步操作，观察指针如何在每次迭代中更新。这将有助于您更直观地了解链表反转的过程。

a905448839 发表于 2023-4-9 21:54:54

isdkz 发表于 2023-4-9 21:41
这个代码的主要目的是实现链表的反转。为了帮助您更好地理解这个过程，我将逐步向您解释代码以及代码的逻辑 ...

我在草稿纸上演算
第一轮：
next = 2
cur->next =NULL
pre = 1
cur = 2

第二轮：
next = NULL
cur->next = 1
pre = 2
cur = NULL

cur = NULL是不是循环结束了呢?

isdkz 发表于 2023-4-9 21:59:31

a905448839 发表于 2023-4-9 21:54
我在草稿纸上演算
第一轮：
next = 2


对的

假设我们有一个链表：1 -> 2 -> 3 -> 4 -> NULL

首先，我们定义两个指针，pre 和 cur。pre 表示当前节点的前一个节点，而 cur 表示当前节点。

1、初始化 pre 和 cur：
pre = NULL
cur = head（也就是 1）

2、进入 while 循环，开始遍历链表的每个节点。在每次循环中，我们将执行以下操作：

a) 用 next 临时存储 cur 的下一个节点，以便在后续操作中使用。在这个例子中，第一次循环时，next 将指向 2。

b) 将 cur（当前节点）的 next 指针指向 pre（前一个节点）。第一次循环时，将 1 的 next 指针指向 NULL。

c) 更新 pre 和 cur。将 pre 设置为 cur，将 cur 设置为 next。在这个例子中，第一次循环后，pre 变为 1，cur 变为 2。

3、第二轮循环：
a) next = 3
b) 将 cur（当前节点，即 2）的 next 指针指向 pre（前一个节点，即 1）。现在链表看起来像这样：NULL <- 1 <- 2 3 -> 4 -> NULL
c) 更新 pre 和 cur。pre 变为 2，cur 变为 3。

4、第三轮循环：
a) next = 4
b) 将 cur（当前节点，即 3）的 next 指针指向 pre（前一个节点，即 2）。现在链表看起来像这样：NULL <- 1 <- 2 <- 3 4 -> NULL
c) 更新 pre 和 cur。pre 变为 3，cur 变为 4。

5、第四轮循环：
a) next = NULL
b) 将 cur（当前节点，即 4）的 next 指针指向 pre（前一个节点，即 3）。现在链表看起来像这样：NULL <- 1 <- 2 <- 3 <- 4
c) 更新 pre 和 cur。pre 变为 4，cur 变为 NULL。

6、cur 变为 NULL，循环结束。此时，链表已反转：NULL <- 1 <- 2 <- 3 <- 4

最后，返回 pre（也就是新链表的头结点，也就是 4）。

查看完整版本: 这个好难求指导！