C语言 我不明白这段代码是如何替换链表的头的......也不明白一般情况下是如何做的

nhjlsmyf  于 2022-12-11  发布在  其他
关注(0)|答案(2)|浏览(202)

取代信头的程式码:
第一个
我用来创建节点的结构体:

typedef struct node
{
    int value;
    struct node* next;
} newnode;

head是链表的头部;第一个节点。我不明白为什么我们在push函数的参数列表中取消对head的引用,以及我在函数的最后一行和它之前的一行中 * 实际 * 做了什么。
我试着对代码做了一些实验来理解它,但我仍然没有真正理解它...

wvt8vs2t

wvt8vs2t1#

void push(newnode ** head, int val) 
{
    newnode * new_node;
    new_node = (newnode *) malloc(sizeof(newnode));

这将分配一个新节点,并使new_node指向它。

new_node->val = val;

这会将新节点的值设置为要添加的值。

new_node->next = *head;

这会将新节点之后的下一个节点设定为head指标目前指向的节点,也就是目前的第一个节点。

*head = new_node;

这使得头指针指向新节点,从而使新节点成为列表中的第一个节点。

}
ctrmrzij

ctrmrzij2#

首先:代码中的一些问题:

newnode* head = (newnode*) malloc(sizeof(newnode));

这分配了一个节点,但它的成员没有初始化。这是不好的,因为当head->next被用于潜在地寻找下一个节点时,迭代这样的列表将导致未定义的行为。它必须被设置为NULL。并且正如我们所做的,也没有好的理由不初始化节点的值。
其次,这个malloc重复了代码。你已经有一个函数执行这样的分配 * 和 * 初始化它的成员 * 和 * 使一个头指针指向它。这就是你真正想要发生的!
因此,将上面的代码更改为:

newnode* head = NULL;
addnode(*head, 0);

在代码注解中写入:
我假设由于push(即addnode)接受一个newnode**参数,因此head应该有一个附加的星号前缀。
是的,这是正确的。这是必要的,因为addnode将希望分配一个新的指针值给“您的”head,因此它需要获得放置它的地址。在addnode中使用名称head来表示这个地址有点误导。因为它实际上与主函数中的head不是一回事。我建议将其重命名为headPtr。同样,在C中,将malloc返回not cast the pointer视为更好的做法

void push(newnode ** headPtr, int val) 
{
    newnode * new_node = malloc(sizeof(newnode));

    new_node->value = val;
    new_node->next = *headPtr;
    *headPtr = new_node;
}

现在我将假定main的代码版本具有此更正代码:

newnode* head = NULL;
    addnode(*head, 0);
    addnode(*head, 4);

......并对执行该命令时发生的情况进行可视化。我们从head设置为NULL开始:

┌─head─┐
│ NULL │
└──────┘

addnode函数是用head的地址和0的值调用的。addnode有它自己的变量headPtr,它现在是指向head的 * 指针 *:

┌─headPtr─┐
│    ┬    │
└────│────┘
     ▼
  ┌─head─┐
  │ NULL │
  └──────┘

对于malloc,分配新节点并用值0初始化:

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     ▼               ▼
  ┌─head─┐      ┌──value──┐
  │ NULL │      │    0    │
  └──────┘      ├───next──┤
                │   ???   │
                └─────────┘

然后进行赋值new_node->next = *headPtr;,将值从*headPtr(即从head,即NULL...)复制到该next元素:

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     ▼               ▼
  ┌─head─┐      ┌──value──┐
  │ NULL │      │    0    │
  └──────┘      ├───next──┤
                │   NULL  │
                └─────────┘

但是,这个新节点还没有“在列表中”:addnode的最终赋值将执行以下操作:*headPtr = new_node。这将把节点的地址复制到*headPtr,即复制到head

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     ▼               ▼
  ┌─head─┐      ┌──value──┐
  │   ├────────►│    0    │
  └──────┘      ├───next──┤
                │   NULL  │
                └─────────┘

请注意,这将如何影响main函数在第一次调用addnode返回时看到的内容。head现在不再是NULL。因为我们传递了一个指向head的指针,addnode能够修改head的(指针)值。这是我们在main中看到的内容:

┌─head─┐      ┌──value──┐
  │   ├────────►│    0    │
  └──────┘      ├───next──┤
                │   NULL  │
                └─────────┘

让我们以同样的方式执行addnode的第二次调用。headPtr将再次指向head,这次的值为4。新节点将被分配malloc,而value成员将被分配4(我必须在图中为它留出一点空间):

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     │               ▼
     │         ┌──value──┐
     │         │    4    │ 
     │         ├───next──┤
     │         │   ???   │
     ▼         └─────────┘
  ┌─head─┐                       ┌──value──┐
  │   ├─────────────────────────►│    0    │
  └──────┘                       ├───next──┤
                                 │   NULL  │
                                 └─────────┘

现在,我们来看看“神奇的”两个赋值,第一个是new_node->next = *headPtr;,它将在新节点和已经存在的节点之间建立链接(从上一个对add_node的调用):

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     │               ▼
     │         ┌──value──┐
     │         │    4    │ 
     │         ├───next──┤
     │         │    ├──────┐
     ▼         └─────────┘ │
  ┌─head─┐                 │     ┌──value──┐
  │   ├────────────────────┴────►│    0    │
  └──────┘                       ├───next──┤
                                 │   NULL  │
                                 └─────────┘

最后,*headPtr = new_node;将使新节点成为列表的第一个节点:

┌─headPtr─┐    ┌─new_node─┐
│    ┬    │    │     ┬    │
└────│────┘    └─────│────┘
     │               ▼
     │         ┌──value──┐
     │         │    4    │ 
     │         ├───next──┤
     │     ┌──►│    ├──────┐
     ▼     │   └─────────┘ │
  ┌─head─┐ │               │     ┌──value──┐
  │   ├────┘               └────►│    0    │
  └──────┘                       ├───next──┤
                                 │   NULL  │
                                 └─────────┘

回到main,剩下的内容如下:

┌─head─┐     ┌──value──┐       ┌──value──┐
  │   ├───────►│    4    │       │    0    │
  └──────┘     ├───next──┤       ├───next──┤
               │    ├───────────►│   NULL  │
               └─────────┘       └─────────┘

希望这能澄清。

相关问题