使用空指针在 C 的通用链表中创建具有给定值的新节点

Question

我正在使用 void 指针为 C 中的通用链表编写一个库。这是我的节点：

typedef struct List {
    void* data;
    struct List* next;
} List;

这是我用给定数据创建新节点的函数：

List* newNode (void* data) {
    List* newNode = (List*)malloc(sizeof(List));
    if (newNode) {
        newNode->data = malloc(sizeof(data));
        newNode->data = data;
        newNode->next = NULL;
    }
    return newNode;
}

我不知道如何替换 newNode->data = data 行以使作业生效。我尝试使用 memcpy(newNode->data, data, sizeof(data)) 但它似乎只适用于字符串。另外，我不确定在函数内部评估 sizeof(data) 因为我担心它不会 return 正确的值。

在新节点的 data 字段中复制新数据的正确方法是什么？

Answer 1

您必须决定是要让列表存储指向值的指针，还是要自己存储值。

如果你只想存储个指针，让你的库的用户关心元素的内存分配，那么：

List* newNode (void* data) {
    List* newNode = malloc(sizeof(List));
    if (newNode) {
        newNode->data = data;
        newNode->next = NULL;
    }
    return newNode;
}

很好。如果你想存储值，你必须将对象的大小传递给你的函数才能知道要分配和复制多少：

List* newNode(void* data, size_t datasize) {
    List* newNode = malloc(sizeof(List));
    if (newNode) {
        newNode->data = malloc(datasize);
        if (!newNode->data) {
             free(newNode);
             return NULL;
        }
        memcpy(newNode->data, data, datasize);
        newNode->next = NULL;
    }
    return newNode;
}
int main() {
    int a;
    List *l = newNode(&a, sizeof(a));
}

I'm not sure about evaluating sizeof(data) inside the function since I'm afraid it wouldn't return the correct value.

data 是一个 void*，所以 sizeof(data) 给你 sizeof(void*) - void* 指针的大小。

how can we do that since void* pointer can't be de-referenced?

创建一个打印一个元素并将其应用于每个列表元素的函数。在伪代码中：

void list_apply_foreach(list *t,
      void (*apply)(void *elem, void *cookie), void *cookie) {
   for (iterate over list in t) {
      apply(i->data, cookie);
   }
}

void print_int(void *elem, void *cookie) {
    printf("%d ", *(int*)elem);
}

int main() {
     list *l = list_make_list_of_ints(1, 2, 3, 4);
     list_apply_foreach(l, print_int);
}

Answer 2

我正在编写代码来做这件事，作为一项学术练习来锻炼我的旧数据结构肌肉（因为我对我应该做的事情感到无聊到流泪）。这是一个 key-value 对的 doubly-linked 列表（对于整数、浮点数或字符串等单个项目的列表，我们只使用键并将数据项留空），其中键和值几乎可以是任何东西.

我通过大量使用 void * 和依赖注入来做到这一点。

在我们继续之前，请注意下面的代码是一个正在进行中的工作 - 不要过于关注任何不一致或 iffy-looking 实践。

我设置它的方式是将一堆回调附加到列表 object 以处理复制、赋值和比较：

struct glist {
  Node *head;       // Node is opaque - I provide an API to create
  Node *tail;       // and manipulate Node objects. 
  size_t count;

  int   (*cmp) ( const void *, const void * ); // comparison for ordering
  void *(*kcpy)( const void * );               // copy key 
  void *(*dcpy)( const void * );               // copy data
  void  (*kdst)( const void * );               // destroy key
  void  (*ddst)( const void * );               // destroy data
};

然后在插入、搜索、删除等操作上，我依靠那些回调来知道如何处理实际数据。

在插入时，我将 *cpy 回调传递给节点创建函数，然后使用 cmp 回调按顺序插入节点：

bool glist_insert( GList *l, const void *key, const void *data )
{
  assert( l != NULL && key != NULL );

  Node *newNode = node_create( key, data, l->kcpy, l->dcpy );
  if ( !newNode )
    return false;

  Node *cur = glist_begin( l );
  if ( node_next( cur ) != glist_end( l ) )
  {
    while ( node_next( cur ) != glist_end( l ) && l->cmp( node_key( newNode ), node_key( node_next( cur ) ) ) >= 0 )
      cur = node_next( cur );
  }

  node_insert_after( cur, newNode );
  l->count++;
  return true;
}

然后在节点创建函数中，回调知道如何分配和复制键和数据值：

Node *node_create( const void *key, const void *data, void *(*kcpy)( const void * ), void *(*dcpy)( const void * ) )
{
  assert( key != NULL && kcpy != NULL );
  Node *n = calloc( 1, sizeof *n );
  if ( n )
  {
    n->key = kcpy( key );
    if ( !n->key )
    {
      free( n );
      n = NULL;
    }
    else if ( data && dcpy )
    {
      n->data = dcpy( data );
      if ( !n->data )
      {
        free( n->key );
        free( n );
        n = NULL;
      }
    }
  }
  return n;
}

然后对于整数列表，我只需要创建用于分配 ints:

的回调

void *int_cpy( const void *data )
{
  assert( data != NULL );

  const int *d = data;

  int *buf = malloc( sizeof *buf );
  if ( buf )
    *buf = *d;

  return buf;
}

并比较它们：

/**
 * Sorts in ascending order
 */
int int_cmp_asc( const void *lhs, const void *rhs )
{
  assert( lhs != NULL && rhs != NULL );

  const int *l = lhs;
  const int *r = rhs;

  if ( *l < *r ) return -1;
  else if ( *l > *r ) return 1;
  
  return 0;
}

/**
 * Sorts in descending order
 */
int int_cmp_dsc( const void *lhs, const void *rhs )
{
  assert( lhs != NULL && rhs != NULL );

  const int *l = lhs;
  const int *r = rhs;

  if ( *l < *r ) return 1;
  else if ( *l > *r ) return -1;
  
  return 0;
}

然后我创建一个轻量级的 type-aware 包装通用接口的接口：

bool ilist_insert( GList *l, int data )
{
  return glist_insert( l, &data, NULL );
}

同样，为了显示列表的内容，我依靠回调来格式化数据以供显示：

/**
 * Display list contents, formatted.  
 * 
 * My list type supports bidirectional traversal with functions like
 *
 *    list_begin  - begin at the head of the list
 *    list_rbegin - begin at the tail of the list
 *    list_end    - end at the tail of the list
 *    list_rend   - end at the head of the list
 *    node_next   - get the node following the current node
 *    node_rnext  - get the node preceding the current node
 *
 * So to display in either order, I call this function with either
 * list_begin, list_end, and node_next, or list_rbegin, list_rend,
 * and node_rnext.
 */
void glist_display( FILE *stream, GList *l, Node *(*start)( GList * ), Node *(*end)( GList * ), Node *(*iter)( Node * ), char *delim, char *(*fmt)( Node *n, char *tgt, size_t tgtSize ) )
{
  assert( stream != NULL && l != NULL );

  /**
   * I need a better way to determine the buffer size, but that's
   * for a later version.
   */
  char dbuf[1024];

  Node *cur = start( l );
  cur = iter( cur );
  if ( cur == end( l ) )
  {
    fputs( "[nil]", stream );
    return;
  }

  char *sep = "";
  do
  {
    fprintf( stream, "%s%s", sep, fmt( cur, dbuf, sizeof dbuf ) );
    cur = iter( cur );
    sep = delim;
  } while( cur != end( l ) );
}

/**
 * Formatter for int objects.  Caller must supply the target
 * buffer.
 */
char *int_fmt( Node *n, char *tgt, size_t tgtSize )
{
  assert( n != NULL && tgt != NULL && tgtSize > 12 );

  sprintf( tgt, "%d", *(int *) node_key( n ) );
  return tgt;
}

所有这些都被称为

glist_display( stdout, list, glist_begin, glist_end, node_next, ", ", int_fmt );

示例int（升序和降序）：

#include <stdio.h>
#include <math.h>
#include "IList.h"

int main( int argc, char **argv )
{
  /**
   * ilist_create "overloads" glist_create, passing "default"
   * copy and destroy callbacks - the only thing we specify here
   * is the comparison callback.
   */
  GList *asc = ilist_create( int_cmp_asc );
  GList *dsc = ilist_create( int_cmp_dsc );

  size_t limit = 10;

  if ( argc > 1 )
  {
    limit = strtoul( argv[1], NULL, 0 );
  }

  for( size_t i = 0; i < limit; i++ )
  {
    int r = rand() % 100;

    ilist_insert( asc, r );
    ilist_insert( dsc, r );
  }
  glist_display( stdout, asc, glist_begin, glist_end, node_next, ", ", int_fmt );
  putc( '\n', stdout );

  glist_display( stdout, dsc, glist_begin, glist_end, node_next, ", ", int_fmt );
  putc( '\n', stdout );

  glist_destroy( asc );
  return 0;
}

输出：

$ ./list_test_int
7, 9, 23, 30, 44, 49, 58, 72, 73, 78
78, 73, 72, 58, 49, 44, 30, 23, 9, 7

这是一个创建电影列表的示例 - 键是标题和发行年份，数据是导演、评级和运行时间：

struct movie_key {
  char *title;
  int year;
};

struct movie_data {
  char *director;
  char rating[6];
  char *runtime;
};

...

bool movie_insert( GList *l, const struct movie_key key, const struct movie_data data )
{
  return glist_insert( l, &key, &data );
}

...

int main( void )
{
  GList *l = glist_create( movie_kcpy, movie_dcpy, movie_kcmp, movie_kdst, movie_ddst );

  FILE *f = fopen( "movies.dat", "r" );
  if ( f )
  {
    struct movie_key key = { NULL, 0 };
    struct movie_data data = { NULL, "", NULL };

    while( getNextMovie( f, &key, &data ) )
      movie_insert( l, key, data );
    fclose( f );
  }

  glist_display( stdout, l, glist_begin, glist_end, node_next, "\n", movie_fmt );
  fputc( '\n', stdout );
  glist_destroy( l );

  return 0;
}

输出：

$ ./movies 
"Cape Fear" (1962) Rated NR; Directed by J. Lee Thompson; Run time 1h 46min
"Cape Fear" (1991) Rated R; Directed by Martin Scorsese; Run time 2h 8min
"Gone with the Wind" (1939) Rated G; Directed by Victor Fleming, George Cukor, Sam Wood; Run time 3h 58min
"Jaws" (1975) Rated PG; Directed by Steven Spielberg; Run time 2h 4min
"Phantom of the Paradise" (1974) Rated PG; Directed by Brian DePalma; Run time 1h 31min
"The Adventures of Buckaroo Banzai Across the 8th Dimension" (1984) Rated PG; Directed by W.D. Richter; Run time 1h 43min
"The Lord of the Rings" (1978) Rated PG; Directed by Ralph Bakshi; Run time 2h 12min
"The Lord of the Rings: The Fellowship of the Ring" (2001) Rated PG-13; Directed by Peter Jackson; Run time 2h 58min
"The Lord of the Rings: The Return of the King" (2003) Rated PG-13; Directed by Peter Jackson; Run time 3h 21min
"The Lord of the Rings: The Two Towers" (2002) Rated PG-13; Directed by Peter Jackson; Run time 2h 59min

两者的基本列表代码相同，只是带有轻量级包装器和大量依赖项注入。

这是 Node 界面（同样，这是一项正在进行的工作，我知道这里存在不一致之处）：

#ifndef GNODE_H
#define GNODE_H

#include <stdbool.h>

/**
 * Implementation of Node type is hidden
 */
typedef struct node Node;

Node *node_create( const void *key, const void *data, void *(*kcpy)( const void * ), void *(*dcpy)( const void * ) );
void node_destroy( Node *n, void (*kdst)( const void * ), void (*ddst)( const void * ) );
void node_insert_after( Node *n, Node *newNode );
void node_insert_before( Node *n, Node *newNode );
bool node_remove( Node *n );
 
/**
 * Iterators
 */
Node *node_next( Node *n );
Node *node_rnext( Node *n );

/**
 * Get the value attached to the node
 */
void *node_key( Node *n );
void *node_data( Node *n );
void node_set_data( Node *n, const void * data, void (*dst)( const void * ), void *(*cpy)( const void * ) );
void node_clear_data( Node *n, void (*dst)( const void * ) );

#endif

和GList界面：

#ifndef GLIST_H
#define GLIST_H

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include "GNode.h"

/**
 * Generic doubly-linked list type.  Only the name is exposed, not the implementation.
 */
typedef struct glist GList;

GList *glist_create( void *(*kcpy)( const void * ), 
                   void *(*dcpy)( const void * ), 
                   int  (*cmp)( const void *, const void * ), 
                   void (*kdst)( const void * ), 
                   void (*ddst)( const void * ) );

void glist_destroy( GList *l );

/**
 * Insert at the beginning of the list
 */
bool glist_insert( GList *l, const void *key, const void *data );

/**
 * Insert at the end of the list
 */
bool glist_rinsert( GList *l, const void *key, const void *data );
bool glist_remove( GList *l, const void *key );

/**
 * Search from the beginning of the list
 */
Node *glist_find( GList *l, const void *key );

/**
 * Search from the end of the list
 */
Node *glist_rfind( GList *l, const void *key );

void glist_display( FILE *stream, GList *l, Node *(*begin)( GList * ), Node *(*end)( GList * ), Node *(*iter)( Node * ), char *delim, char *(*fmt)( Node *n, char *tgt, size_t tgtSize ) );
void glist_dump( FILE *stream, GList *l );

Node *glist_begin( GList *l );
Node *glist_end( GList *l ); 
Node *glist_rbegin( GList *l );
Node *glist_rend( GList *l ); 

size_t glist_size( GList *l );

#endif

使用空指针在 C 的通用链表中创建具有给定值的新节点

Creating a new node with given value in a generic linked list in C with void pointers

c

memory

malloc

linked-list

void