C 中的链表——方法
Linked list in C – methods
假设我们有节点的双向链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
struct Node* prev;
} Node;
typedef struct LinkedList {
Node *first;
Node *last;
} LinkedList;
void initList(LinkedList* l) {
l->first = NULL;
l->last = NULL;
}
我必须编写方法,该方法将具有给定值的新节点插入到列表的末尾,并 returns 指向新节点的指针。我的尝试如下:
Node *insert(LinkedList *list, int value) {
Node node;
node.value = value;
node.prev = list->last;
node.next = NULL;
if (list->last != NULL){
(list->last)->next = &node;
}else{
list->first = &node;
list->last = &node;
}
return &node;
}
似乎,在空列表中插入是可行的,但对于非空列表则行不通。
(有实现测试,可以告诉我插入是否成功。我可以post他们的代码,但我认为这不重要)。
所以请问哪里错了?
日志中有警告(第51行是'return &node')
C:\...\main.c|51|warning: function returns address of local variable [-Wreturn-local-addr]|
这个问题严重吗?以及如何删除它?
谢谢大家的解答,但是我觉得非空列表还是有问题,因为根据测试,这个是失败的:
void test_insert_nonempty(){
printf("Test 2: ");
LinkedList l;
initList(&l);
Node n;
n.value = 1;
n.next = NULL;
l.first = &n;
l.last = &n;
insert(&l, 2);
if (l.last == NULL) {
printf("FAIL\n");
return;
}
if ((l.last->value == 2) && (l.last->prev != NULL)) {
printf("OK\n");
free(l.last);
}else{
printf("FAIL\n");
}
}
Node node;
是您的函数 insert
中的局部变量。一旦您的函数终止并且不再定义,它就是 "destroyed"。返回指向函数局部变量的指针是未定义的行为。您必须分配动态内存。动态分配内存一直保留到你 free
it:
Node *insert(LinkedList *list, int value) {
Node *node = malloc( sizeof( Node ) ); // allocate dynamic memory for one node
if ( node == NULL )
return NULL; // faild to allocate dynamic memory
node->value = value;
node->prev = list->last;
node->next = NULL;
if ( list->first == NULL )
list->first = node; // new node is haed of list if list is empty
else // if ( list->last != NULL ) // if list->first != NULL then list->last != NULL
list->last->next = node; // successor of last node is new node
list->last = node; // tail of list is new node
return node;
}
请注意,为避免内存泄漏,您必须在销毁列表时free
列表的每个节点。
您正在 returning 非静态局部变量的地址,它将在从函数 returning 时消失,并且在 returning 从函数调用 returning 后取消引用地址 未定义的行为.
你必须分配一些缓冲区和return它的地址。
Node *insert(LinkedList *list, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL) return NULL;
node->value = value;
node->prev = list->last;
node->next = NULL;
if (list->last != NULL){
(list->last)->next = node;
}else{
list->first = node;
list->last = node;
}
return node;
}
您必须动态分配新节点。
否则函数中的变量node
Node *insert(LinkedList *list, int value) {
Node node;
//...
是函数的局部变量,退出函数后不会存活。因此,任何指向用于访问它的变量的指针都将无效。
函数看起来像
Node * insert( LinkedList *list, int value )
{
Node *node = malloc( sizeof( Node ) );
if ( node != NULL )
{
node->value = value;
node->prev = list->last;
node->next = NULL;
if ( list->last != NULL )
{
list->last->next = node;
}
else
{
list->first = node;
}
list->last = node;
}
return node;
}
假设我们有节点的双向链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int value;
struct Node* next;
struct Node* prev;
} Node;
typedef struct LinkedList {
Node *first;
Node *last;
} LinkedList;
void initList(LinkedList* l) {
l->first = NULL;
l->last = NULL;
}
我必须编写方法,该方法将具有给定值的新节点插入到列表的末尾,并 returns 指向新节点的指针。我的尝试如下:
Node *insert(LinkedList *list, int value) {
Node node;
node.value = value;
node.prev = list->last;
node.next = NULL;
if (list->last != NULL){
(list->last)->next = &node;
}else{
list->first = &node;
list->last = &node;
}
return &node;
}
似乎,在空列表中插入是可行的,但对于非空列表则行不通。
(有实现测试,可以告诉我插入是否成功。我可以post他们的代码,但我认为这不重要)。
所以请问哪里错了?
日志中有警告(第51行是'return &node')
C:\...\main.c|51|warning: function returns address of local variable [-Wreturn-local-addr]|
这个问题严重吗?以及如何删除它?
谢谢大家的解答,但是我觉得非空列表还是有问题,因为根据测试,这个是失败的:
void test_insert_nonempty(){
printf("Test 2: ");
LinkedList l;
initList(&l);
Node n;
n.value = 1;
n.next = NULL;
l.first = &n;
l.last = &n;
insert(&l, 2);
if (l.last == NULL) {
printf("FAIL\n");
return;
}
if ((l.last->value == 2) && (l.last->prev != NULL)) {
printf("OK\n");
free(l.last);
}else{
printf("FAIL\n");
}
}
Node node;
是您的函数 insert
中的局部变量。一旦您的函数终止并且不再定义,它就是 "destroyed"。返回指向函数局部变量的指针是未定义的行为。您必须分配动态内存。动态分配内存一直保留到你 free
it:
Node *insert(LinkedList *list, int value) {
Node *node = malloc( sizeof( Node ) ); // allocate dynamic memory for one node
if ( node == NULL )
return NULL; // faild to allocate dynamic memory
node->value = value;
node->prev = list->last;
node->next = NULL;
if ( list->first == NULL )
list->first = node; // new node is haed of list if list is empty
else // if ( list->last != NULL ) // if list->first != NULL then list->last != NULL
list->last->next = node; // successor of last node is new node
list->last = node; // tail of list is new node
return node;
}
请注意,为避免内存泄漏,您必须在销毁列表时free
列表的每个节点。
您正在 returning 非静态局部变量的地址,它将在从函数 returning 时消失,并且在 returning 从函数调用 returning 后取消引用地址 未定义的行为.
你必须分配一些缓冲区和return它的地址。
Node *insert(LinkedList *list, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL) return NULL;
node->value = value;
node->prev = list->last;
node->next = NULL;
if (list->last != NULL){
(list->last)->next = node;
}else{
list->first = node;
list->last = node;
}
return node;
}
您必须动态分配新节点。
否则函数中的变量node
Node *insert(LinkedList *list, int value) {
Node node;
//...
是函数的局部变量,退出函数后不会存活。因此,任何指向用于访问它的变量的指针都将无效。
函数看起来像
Node * insert( LinkedList *list, int value )
{
Node *node = malloc( sizeof( Node ) );
if ( node != NULL )
{
node->value = value;
node->prev = list->last;
node->next = NULL;
if ( list->last != NULL )
{
list->last->next = node;
}
else
{
list->first = node;
}
list->last = node;
}
return node;
}