我的链表中的分配不起作用

Question

我正在尝试实现一个链表，该链表仅在列表中不存在时才插入一个项目。如果该项目存在，ent_exists returns 指向该项目的指针。

typedef struct nodo_ent{
  struct nodo_ent *next;
  char *ent;
}nodo_ent;

nodo_ent *head;
nodo_ent *tail;
head = NULL;
tail = NULL;

nodo_ent *ent_exists(char *ent)
{
  if (head == NULL)
 {
   return NULL;
 }
 else
 {
   nodo_ent *cursor;
   cursor = head;
   while (cursor != tail)
   {
     if (strcmp(cursor->ent, ent) == 0);
     {
       return cursor;
     }
     cursor = cursor->next;
   }
   if (strcmp(tail->ent, ent) == 0);
   {
     return tail;
   }
   return NULL;
 }
}

void addent(char *ent)
{
  if (ent_exists(ent) != NULL)
  {
    return;
  }
  else
  {
    nodo_ent nodo = {NULL, ent};
    nodo_ent *ptr;
    ptr = (nodo_ent*)malloc(sizeof(nodo_ent));
    ptr = &nodo;
    if (head == NULL)
    {
      head = ptr;
      tail = ptr;
    }
    else
    {
      tail->next = ptr;
      tail = ptr;
    }
    return;
  }
}

第一次调用"addent"后，"head"和"tail"都指向添加节点的地址，但是第二次调用时，尝试访问tail ->ent（在 ent_exists 中），valgrind 表示它未初始化

Answer 1

正如风向标指出的那样，

nodo_ent nodo = {NULL, ent};
nodo_ent *ptr;
ptr = (nodo_ent*)malloc(sizeof(nodo_ent));
ptr = &nodo;

这个序列分配内存，然后用局部变量的地址覆盖指向这个分配内存的指针nodo。

然后你处理这个局部变量，但是当函数 returns 时，那个局部变量不再存在并且你的列表已损坏。

一切尽在掌握，只需使用：

nodo_ent *ptr;
ptr = malloc(sizeof(nodo_ent));

（并且不要转换 malloc 的结果。指向 void 的指针，其中 malloc returns 与任何指针兼容。）

Answer 2

对于初学者来说，如果这个代码片段

nodo_ent *head;
nodo_ent *tail;
head = NULL;
tail = NULL;

在全局命名空间中，则代码将无法编译。

函数ent_exists太复杂了。

它可以更简单地实现。

nodo_ent * ent_exists( const char *ent )
{
    nodo_ent *cursor = head;

    while ( cursor != NULL && strcmp( cursor->ent, ent ) != 0 )
    {
        cursor = cursor->next;
    }

    return cursor;  
}

函数 addent 应该有 return 类型的 int 来报告新节点的插入是否成功。

这段代码

nodo_ent nodo = {NULL, ent};
nodo_ent *ptr;
ptr = (nodo_ent*)malloc(sizeof(nodo_ent));
ptr = &nodo;

没有意义，而且存在内存泄漏。

您必须复制作为参数传递的字符串。否则程序通常会有未定义的行为。

这是一个演示程序，展示了如何定义函数。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct nodo_ent{
  struct nodo_ent *next;
  char *ent;
}nodo_ent;

nodo_ent *head = NULL;
nodo_ent *tail = NULL;

nodo_ent * ent_exists( const char *ent )
{
    nodo_ent *cursor = head;

    while ( cursor != NULL && strcmp( cursor->ent, ent ) != 0 )
    {
        cursor = cursor->next;
    }

    return cursor;  
}

int addent( const char *ent )
{
    nodo_ent *target_nodo = ent_exists( ent );

    int success = target_nodo == NULL;

    if ( success )
    {
        target_nodo = malloc( sizeof( nodo_ent ) );
        success = target_nodo != NULL;
    }

    if ( success )
    {
        char *s = malloc( strlen( ent ) + 1 );

        success = s != NULL;

        if ( success )
        {
            strcpy( s, ent );
            target_nodo->ent = s;
            target_nodo->next = NULL;
        }           
        else 
        {
            free( target_nodo );
        }           
    }

    if ( success )
    {
        if ( head == NULL )
        {
            head = tail = target_nodo;
        }
        else
        {
            tail = tail->next = target_nodo;
        }
    }       

    return success;
}

void output()
{
    for ( nodo_ent *cursor = head; cursor != NULL; cursor = cursor->next )
    {
        printf( "%s ", cursor->ent );
    }
}

int main(void) 
{
    const char *ent;

    ent = "Hello";
    addent( ent );

    ent = "Jack";
    addent( ent );

    output();

    return 0;
}

它的输出是

Hello Jack

我的链表中的分配不起作用

Assignments in my linked list doesn't work

c

list

insert

singly-linked-list