c - C中的双向链表:为什么我必须明确地重新分配头部和尾部,即使它们没有改变?
问题描述
我有一个双向链表,您可以在其中通过指向头或尾节点指针的指针添加到头或尾。
这样,您只需将头和尾指针更新为最新的头或尾节点的地址。
我在它们自己的函数中启动了那些“指向指针的指针”,并存储在一个同时包含两者的结构中。
当我添加到尾部或头部时,我必须明确保存旧头部并重新分配它,而尾部则相反。否则,结构发生突变,头部也变成尾部,或者尾部变成头部。
我试图了解发生了什么。也许必须静态/全局定义头/尾保留结构?
来源:
#include <stdio.h>
#include <stdlib.h>
typedef struct dcl_node {
char *content;
struct dcl_node *next;
struct dcl_node *prev;
} Node;
Node *create_node (char *content) {
Node *n = malloc(sizeof(Node));
n->content = content;
n->next = NULL;
n->prev = NULL;
return n;
}
typedef struct dc_list {
struct dcl_node **head;
struct dcl_node **tail;
} DCList ;
DCList *init_list (char *content_head, char *content_tail) {
Node *head = create_node(content_head);
Node *tail = create_node(content_tail);
head->next = tail;
tail->prev = head;
DCList *list = malloc(sizeof(DCList));
list->head = &head;
list->tail = &tail;
return list;
}
void insert_head (char *content, DCList *list) {
Node *old_head = *list->head;
Node *old_tail = *list->tail; // note the saving here
Node *node = create_node(content);
node->next = old_head;
old_head->prev = node;
*list->head = node;
*list->tail = old_tail; // and reassigning here
}
void insert_tail (char *content, DCList *list) {
Node *old_head = *list->head; // note the saving here
Node *old_tail = *list->tail;
Node *node = create_node(content);
node->prev = old_tail;
old_tail->next = node;
*list->head = old_head; // and reassigning here
*list->tail = node;
}
int main (int argc, char *argv[]) {
DCList *list = init_list("c", "d");
insert_head("b", list);
// If I don't explicitly save and reassign the tail node,
// in this case both head and tail would become the "b node".
printf("head: %s\ntail: %s\n",
(*list->head)->content, (*list->tail)->content);
return 0;
}
解决方案
因为list->head
andlist->tail
是指向init_list
函数中局部变量的指针。
这些变量在init_list
返回时会被销毁,并且可以重用它们存储的内存。
巧合的是,当您保存它们insert_head
并且insert_tail
您保存的head
和tail
变量(可能!)获得相同的内存地址时,它们不会被覆盖。否则,旧的head
可能会被 覆盖node
。
这是一个大概的解释——很难说编译器实际上在做什么。但关键是head
and在返回tail
时被销毁init_list
,然后你的list->head
andlist->tail
指向可以重用的空闲内存。
推荐阅读
- c# - C# - 静态初始化程序的顺序问题
- dart - 如何将 flutter_local_notifications 添加到我的应用程序中?
- sql - SQL Server:在查询中获取按日期安全计数 - 有没有更简单的方法来编写它?
- javascript - Javascript - 按前 2 个空格分割字符串
- r - 我正在尝试使用 Ubuntu 18.04 在 R 中安装 openssl 包但没有成功
- rust - 如何在 rust 中连接静态数组?
- mysql - mysql - 如何获取父表中缺少的所有关系外键?
- db2 - SQLCODE -981,SQLERRMC:00C12219
- powershell - 将脚本指向最新文件
- python - 无法从烧瓶服务器提供静态文件