鱼C论坛

 找回密码
 立即注册
查看: 1904|回复: 3

[已解决]这个好难求指导!

[复制链接]
发表于 2023-4-9 21:38:00 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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


  1. struct Node *reversed(struct Node *head)
  2. {
  3.     struct Node *pre;         //pre指针表示当前节点的前一个节点
  4.     struct Node *cur;         //cur指针表示当前节点
  5.     pre = NULL;               //初始的前一个节点为NULL,因为反转后最后一个节点为NULL
  6.     cur = head;               //初始的当前节点为头结点
  7.    
  8.     while(cur)                //从头结点遍历全部节点
  9.     {
  10.         struct Node* next = cur->next;  //定义了一个Node结构体的指针next变量 用来保存下一个节点的指针
  11.             //在while循环体内 next是个局部变量 每次循环结束他都会被摧毁 不会影响链表其他部位
  12.         cur->next = pre;                //将当前节点的指针指向前一个节点
  13.         pre = cur;                      //更新前一个节点为当前节点
  14.         cur = next;                     //当前节点指向下一个节点
  15.     }
  16.     return pre;   //返回反转后的头结点指针
  17. }
复制代码



完整代码:
  1. #include<stdio.h>
  2. #include<stdlib.h>

  3. struct Node
  4. {
  5.         int value;
  6.         struct Node *next;
  7. };

  8. void printNode(struct Node *head);
  9. void insertNode(struct Node **head, int value);
  10. struct Node *reversed(struct Node *head);

  11. void insertNode(struct Node **head, int value)
  12. {
  13.         struct Node *previous;//current上一个节点的指针
  14.         struct Node *current;//当前位置   指向比value大的节点指针
  15.         struct Node *new;
  16.        
  17.         current = *head;
  18.         previous = NULL;
  19.        
  20.         while(current != NULL && current->value < value)
  21.         {
  22.                 previous = current;
  23.                 current = current->next;
  24.         }
  25.         new = (struct Node *)malloc(sizeof(struct Node));
  26.         if(new == NULL)
  27.         {
  28.                 printf("内存分配失败!\n");
  29.                 exit(1);
  30.         }
  31.        
  32.         new->value = value;
  33.         //previous->next = new;  这个先不用写 后面要判断他是不是为NULL
  34.         new->next = current;
  35.        
  36.         if(previous == NULL)//previous为NULL只有一种情况(因为把current赋值给previous 且current不为NULL才能赋值)
  37.                             //所以current本身一进来就为NULL 空的单链表
  38.         {
  39.                 *head = new;//所以将*head指针修改为new    这个new是唯一一个节点

  40.         }
  41.         else
  42.         previous->next = new;


  43. }

  44. void printNode(struct Node *head)
  45. {
  46.         struct Node *current;
  47.        
  48.         current = head;
  49.         while(current != NULL)
  50.         {
  51.                 printf("%d ",current->value);
  52.                 current = current->next;

  53.         }
  54.         putchar('\n');

  55. }


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


  73. int main(void)
  74. {
  75.         struct Node *head = NULL;
  76.         int input;
  77.        
  78.         while(1)
  79.         {
  80.                 printf("请输入一个整数(输入-1表示结束):");
  81.                 scanf("%d",&input);
  82.                 if(input == -1)
  83.                 {
  84.                         break;       
  85.                 }
  86.                 insertNode(&head, input);
  87.                 printNode(head);       
  88.         }  

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


  92.         return 0;
  93. }
复制代码
最佳答案
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)。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 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 指针,使其指向前一个节点,从而实现链表的反转。希望这种解释方式能帮助您更好地理解这段代码的逻辑。

为了更好地理解这个过程,您可以在纸上画出链表的每一步操作,观察指针如何在每次迭代中更新。这将有助于您更直观地了解链表反转的过程。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 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是不是循环结束了呢?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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)。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-10 03:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表