C语言实现一个简单的单向链表list

作者在 2011-04-09 00:18:18 发布以下内容
用C语言实现一个简单实用的单向链表list,具有一定的实际意义。尤其我们不想使用STL里面的list<...>类的时候。我实现 的这个list,结点存储任何调用者分配的任意类型的数据(void*)。这个list适用于一些简单的场合,消耗极少的资源。 

头文件:

/*
 * list.h
 *        Generic sequential linked list node structure -- can hold any type data.
 *        cheungmine 
 *      Sep. 22, 2007.  All rights reserved.
 
*/
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

#include 
"unistd.h"

typedef 
struct _listnode_t
{
    
struct _listnode_t    *next;
    union{
        
void*            data;
        
struct _list_t    *list;
        
const char        *str;
        
long            key;
    };
}listnode_t;

typedef 
struct _list_t
{
    size_t        size;    
/* count of nodes */
    listnode_t    
*head;
    listnode_t  
*tail;
}list_t, 
*list_p;

/* A prototype of callbacked function called by list_destroy(), NULL for no use. */
typedef 
void(*pfcb_list_node_free)(listnode_t* node);    

/* An example of free node data function implemented by callee:
void my_list_node_free(listnode_t *node)
{
    free(node->data);
}
*/

/* Appends a node to a list */
extern void 
list_append_node(list_t 
*in_list, listnode_t *in_node);

/* Removes the first node from a list and returns it */
extern listnode_t* 
list_remove_head(list_t 
*in_list);

/* Removes all nodes but for list itself */
extern void
list_remove_all(list_t 
*in_list, pfcb_list_node_free pfunc /* NULL for no use or a key node */);

/* Returns a copy of a list_t from heap */
extern list_t* 
list_copy(list_t in_list);

/* Concatenates two lists into first list. NOT freeing the second */
extern void 
list_concat(list_t 
*first, list_t *second);

/* Allocates a new listnode_t from heap. NO memory allocated for input node_data */
extern listnode_t* 
list_node_create(
void* node_data);

/* Allocates a new listnode_t with a key node type */
extern listnode_t* 
list_key_create(
long node_key);

/* Allocates a empty list_t from heap */
extern list_t* 
list_create();

/* Frees in_list's all nodes and destroys in_list from heap.
 * the callee is responsible for freeing node data.
 * the node freed-function(pfunc) is called by list_destroy.
 
*/
extern void 
list_destroy(list_t 
*in_list, pfcb_list_node_free pfunc /* NULL for no use or a key node */);

/* Gets count of nodes in the list */
extern size_t 
list_size(
const list_t* in_list);

/* Gets node by index 0-based. 0 is head */
extern listnode_t* 
list_node_at(
const list_t* in_list, int index);


#endif  /* LIST_H_INCLUDED */

实现文件:

/*
 * list.c
 *        Generic linked list implementation.
 *        cheungmine 
 *      Sep. 22, 2007.  All rights reserved.
 
*/

#include 
"list.h"

/* Appends a node to a list */
void 
list_append_node(list_t 
*in_list, listnode_t *node)
{
    node
->next = NULL;

    
if (in_list->head)
    {
        in_list
->tail->next = node;
        in_list
->tail = node;
    }
    
else
        in_list
->head = in_list->tail = node;

    in_list
->size++;
}

/* Removes the first node from a list and returns it */
listnode_t
* 
list_remove_head(list_t 
*in_list)
{
    listnode_t    
*node = NULL;
    
if (in_list->head)
    {
        node 
= in_list->head;
        in_list
->head = in_list->head->next;
        
if (in_list->head == NULL)
            in_list
->tail = NULL;
        node
->next = NULL;

        in_list
->size--;        
    }
    assert(in_list
->size >= 0);
    
return node;
}

/* Removes all nodes but for list itself */
void
list_remove_all(list_t 
*in_list, pfcb_list_node_free pf)
{
    listnode_t    
*node;
    
while((node = list_remove_head(in_list))){
        
if (pf) (*pf)(node);
        free(node);
    }
    assert (in_list
->size==0);
}

/* Returns a copy of a list_t from heap */
list_t
* 
list_copy(list_t list)
{
    list_t    
*newlist = (list_t*)malloc (sizeof(list_t));
    
*newlist = list;
    
return newlist;
}

/* Concatenates two lists into first list */
void 
list_concat(list_t 
*first, list_t *second)
{
    
if (first->head)
    {
        
if (second->head)
        {
            first
->tail->next = second->head;
            first
->tail = second->tail;
        }
    }
    
else
        
*first = *second;
    second
->head = second->tail = NULL;

    first
->size += second->size;
}

/* Allocates a new listnode_t from heap */
listnode_t
* 
list_node_create(
void* data)
{
    listnode_t    
*node = (listnode_t*)malloc (sizeof(listnode_t));
    node
->next = NULL;
    node
->data = data;
    
return node;
}

listnode_t
* 
list_key_create(
long key)
{
    listnode_t    
*node = (listnode_t*)malloc (sizeof(listnode_t));
    node
->next = NULL;
    node
->key = key;
    
return node;
}

/* Allocates a empty list_t from heap */
list_t
* 
list_create()
{
    list_t    
*list = (list_t*)malloc (sizeof(list_t));
    list
->size = 0;
    list
->head = list->tail = NULL;
    
return list;
}

/* Frees a empty list_t from heap */
void 
list_destroy(list_t 
*in_list, pfcb_list_node_free  pf)
{
    list_remove_all(in_list, pf);    
    free(in_list);
}

/* Gets count of nodes in the list */
size_t 
list_size(
const list_t* in_list)
{
    
return in_list->size;
}

/* Gets node by index 0-based. 0 is head */
listnode_t
* 
list_node_at(
const list_t* in_list, int index)
{
    
int  i=0;
    listnode_t    
*node = in_list->head;

    assert(index 
>=0 && index < (int)in_list->size);

    
while (i < index)
    {
        node 
= node->next;
        i
++;
    }

    
return node;
}

公共头文件:

/* unistd.h 
   2008-09-15 Last created by cheungmine.
   All rights reserved by cheungmine.
*/
#ifndef UNISTD_H__
#define UNISTD_H__

/* Standard C header files included */
#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<string.h>
#include 
<assert.h>

/*============================================================================*/

typedef unsigned 
char uchar, byte, BYTE;

typedef unsigned 
short uint16, word_t, ushort;

typedef unsigned __int32 
uint, uint32, dword_t, size_t;

typedef unsigned 
long    ulong;

typedef __int16 int16;
typedef __int32 int32;
typedef __int64 int64, longlong;

typedef    
long    lresult;

typedef unsigned __int64 uint64, qword_t, ulonglong;

#ifndef BOOL
    typedef 
int     BOOL;
    
#define TRUE  1
    
#define FALSE 0
#endif

#ifndef RESULT
    
#define RESULT        lresult
    
#define _SUCCESS    0
    
#define _ERROR        -1
#endif

#ifndef IN
#define IN
#endif

#ifndef OUT
#define OUT
#endif

#ifndef INOUT
#define INOUT
#endif

#ifndef OPTIONAL
#define OPTIONAL
#endif

#define SIZE_BYTE    1
#define SIZE_ACHAR    1
#define SIZE_WCHAR    2
#define SIZE_SHORT    2
#define SIZE_INT    4
#define SIZE_LONG    4
#define SIZE_FLT    4
#define SIZE_DBL    8
#define SIZE_WORD    2
#define SIZE_DWORD    4
#define SIZE_QWORD    8
#define SIZE_LINT    8
#define SIZE_INT64    8
#define SIZE_UUID    16


/*============================================================================*/
#endif    /*UNISTD_H__*/
基础知识 | 阅读 2185 次
文章评论,共2条
贾文慧
2011-08-19 12:31
1
为了骗积分,赞一个
vfdff(作者)
2011-08-31 23:50
2
<div class="quote"><span class="q"><b>贾文慧</b>: 为了骗积分,赞一个</span></div>哈哈,图谋不轨
游客请输入验证码
浏览1940567次