首页 / 软件开发 / C语言 / list.c - A linked list by C --- C语言实现的单向链表

list.c - A linked list by C --- C语言实现的单向链表2010-06-17 csdn博客 张亮这是我实现的单向链表。单向链表很简单，可以存储任意类型的数据：整型、字符串或指针类型。但是，不要混存。除整型外，链表节点数据由调用者分配和负责释放，即调用者负责提供一个回调函数，当链表释放时，自动调用你提供的这个函数。记住：链表不分配任何用户的数据，仅分配和管理自己的私有数据，因此，分配和释放链表所存放的数据的工作必须由用户来完成。读者可以在测试代码中看到用例。

链表需要的文件为：unistd.h，list.h，list.c。测试文件为test.c。以下是代码：

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

#ifdef __cplusplus
extern "C" {
#endif

#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（）
* - list_traverse（）
* - list_node_free（）
* NULL for no use
*/
typedef void（*pfunc_list_callback）（listnode_t* node）;

/**
* An prototype example of free node data function implemented by caller:
*/
static void my_listnode_data_free（listnode_t *node）
{
free（node->data）;
DBG_TRACE（"my_listnode_data_free "）;
}

/**
* A prototype example of traverse implemented by caller:
*/
static void my_listnode_key_traverse（listnode_t *node）
{
printf（" key=%ld ", node->key）;
}

/**
* Traverses a list, applied callback functionn for each node
*/
void
list_traverse（list_t *in_list, pfunc_list_callback pfcb_traversenode）;

/**
* Allocates a empty list from heap, this creates a new list
*/
list_t*
list_create（）;

/**
* Clears a list and free memory, the list cannot be used later
*/
void
list_destroy（list_t *in_list, pfunc_list_callback pfcb_freedata）;

/**
* Creates a new node assigned with data, not allocates for data
*/
listnode_t*
list_node_create（void* data）;

/**
* Free a list node and it's associated nodes, the freed node cannot be used later
*/
void
list_node_free（listnode_t* node, pfunc_list_callback pfcb_freedata）;

/**
* Creates a new node assigned with a key, not allocates for key
*/
listnode_t*
list_key_create（long key）;

/**
* Finds prev node of given node
*/
listnode_t*
list_find_prev（const list_t *in_list, const listnode_t *node）;

/**
* Appends a node to a list at back
*/
void
list_push_back（list_t *in_list, listnode_t *node）;

/**
* Inserts a node in front of head into a list
*/
void
list_push_front（list_t *in_list, listnode_t *in_node）;

/**
* Inserts a node after pos node into a list
*/
void
list_insert_after（list_t *in_list, listnode_t *pos_node, listnode_t *in_node）;

/**
* Inserts a node before pos node into a list
*/
void
list_insert_before（list_t *in_list, listnode_t *pos_node, listnode_t *in_node）;

/**
* Removes the first node from a list and returns it
*/
listnode_t*
list_pop_front（list_t *in_list）;

/**
* Removes the last node from a list and returns it
*/
listnode_t*
list_pop_back（list_t *in_list）;

/**
* Removes all nodes but for list itself
*/
void
list_clear（list_t *in_list, pfunc_list_callback pfcb）;

/**
* Returns a copy of a list_t from heap
*/
list_t*
list_copy（list_t list）;

/**
* Concatenates two lists into first list
*/
void
list_concat（list_t *first, list_t *second）;

/**
* Gets count of nodes in the list
*/
size_t
list_size（const list_t* in_list）;

/**
* Gets node by index: 0-based. 0 is head
*/
listnode_t*
list_node_at（const list_t* in_list, size_t index）;

/**
* Slices list off from begin to end, returns begin node
* Caller should free returned list nodes
* begin and end can be same one
*/
listnode_t*
list_slice（list_t* in_list, listnode_t* begin, listnode_t* end）;

#ifdef __cplusplus
}
#endif

#endif /* LIST_H_INCLUDED__ */


/****************************************************************************************
* list.c *
* Generic sequential linked list node structure -- can hold any type data. *
* cheungmine *
* Mar. 22, 2008. All rights reserved. *
****************************************************************************************/
#include "list.h"

void
list_traverse（list_t *in_list, pfunc_list_callback pfcb）
{
listnode_t* node;
DBG_TRACE（"list_traverse: size= %ld ", in_list->size）;
if （pfcb） {
node = in_list->head;
while （node） {
（*pfcb）（node）;
node = node->next;
}
}
}

list_t*
list_create（）
{
list_t *list = （list_t*）malloc （sizeof（list_t））;
list->size = 0;
list->head = list->tail = NULL;

DBG_TRACE（"list_create "）;
return list;
}

void
list_destroy（list_t *in_list, pfunc_list_callback pf）
{
DBG_TRACE（"list_destroy "）;
list_clear（in_list, pf）;
free（in_list）;
}

listnode_t*
list_node_create（void* data）
{
listnode_t *node = （listnode_t*）malloc （sizeof（listnode_t））;
node->next = NULL;
node->data = data;
DBG_TRACE（"list_node_create "）;
return node;
}

void
list_node_free（listnode_t* node, pfunc_list_callback pfcb）
{
listnode_t* next;
DBG_TRACE（"list_node_free "）;
while（node）{
next = node->next;
if （pfcb）
（*pfcb）（node）;
free（node）;
node = next;
}
}

listnode_t*
list_key_create（long key）
{
listnode_t *node = （listnode_t*）malloc （sizeof（listnode_t））;
node->next = NULL;
node->key = key;
DBG_TRACE（"list_key_create: key=%ld ", key）;
return node;
}

listnode_t*
list_find_prev（const list_t *in_list, const listnode_t *node）
{
listnode_t* prev;
assert（node）;
prev = in_list->head;
if （prev==node）
return NULL;
while（prev && prev->next！=node） {
prev = prev->next;
}
assert（prev）;
return prev;
}

void
list_push_back（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++;
DBG_TRACE（"list_push_back "）;
}

void
list_push_front（list_t *in_list, listnode_t *in_node）
{
in_node->next = in_list->head;
in_list->head = in_node;

if （！in_node->next）
in_list->tail = in_node;

in_list->size++;
DBG_TRACE（"list_push_front "）;
}

void
list_insert_after（list_t *in_list, listnode_t *pos_node, listnode_t *in_node）
{
in_node->next = pos_node->next;
pos_node->next = in_node;

if （in_list->tail==pos_node）
in_list->tail = in_node;

in_list->size++;
}

void
list_insert_before（list_t *in_list, listnode_t *pos_node, listnode_t *in_node）
{
listnode_t* prev_node;
prev_node = list_find_prev（in_list, pos_node）;
if （prev_node）
list_insert_after（in_list, prev_node, in_node）;
else
list_push_front（in_list, in_node）;
}

listnode_t*
list_pop_front（list_t *in_list）
{
listnode_t *pop_node = NULL;
if （in_list->head）
{
pop_node = in_list->head;
in_list->head = in_list->head->next;
if （in_list->head == NULL）
in_list->tail = NULL;
pop_node->next = NULL;
in_list->size--;
}
assert（in_list->size >= 0）;
DBG_TRACE（"list_pop_front "）;
return pop_node;
}

listnode_t*
list_pop_back（list_t *in_list）
{
listnode_t *pop_node = in_list->tail;
if （in_list->head==pop_node） {
in_list->size = 0;
in_list->head = in_list->tail = NULL;
}
else {
assert（pop_node && ！pop_node->next）;
in_list->tail = list_find_prev（in_list, pop_node）;
assert（in_list->tail）;
in_list->tail->next = NULL;
in_list->size--;
}
assert（in_list->size >= 0）;
DBG_TRACE（"list_pop_back "）;
return pop_node;
}

void
list_clear（list_t *in_list, pfunc_list_callback pfcb）
{
listnode_t *node;
if （pfcb） {
while（（node = list_pop_front（in_list）））{
（*pfcb）（node）;
free（node）;
}
}
else {
while（（node = list_pop_front（in_list）））{
free（node）;
}
}
assert （in_list->size==0）;
DBG_TRACE（"list_clear "）;
}

list_t*
list_copy（list_t list）
{
list_t *newlist = （list_t*）malloc （sizeof（list_t））;
*newlist = list;
DBG_TRACE（"list_copy "）;
return newlist;
}

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;
DBG_TRACE（"list_concat "）;
}

size_t
list_size（const list_t* in_list）
{
DBG_TRACE（"list_size:%ld ", in_list->size）;
return in_list->size;
}

listnode_t*
list_node_at（const list_t* in_list, size_t index）
{
size_t i=0;
listnode_t *node = in_list->head;
assert（index >=0 && index < in_list->size）;
while （i < index） {
node = node->next;
i++;
}
return node;
}

listnode_t*
list_slice（list_t* in_list, listnode_t* begin, listnode_t* end）
{
listnode_t* prev;
assert（end）;
prev = list_find_prev（in_list, begin）;

if （prev==NULL） {
assert（begin==in_list->head）;
in_list->head = end->next;
end->next = NULL;
if （in_list->tail == end）
in_list->tail = in_list->head;
}
else {
prev->next = end->next;
end->next = NULL;
if （in_list->tail == end）
in_list->tail = prev;
}
DBG_TRACE（"list_slice "）;

in_list->size = 0;
prev = in_list->head;
while（prev） {
in_list->size++;
prev = prev->next;
}

return begin;
}


/****************************************************************************************
* unistd.h *
* 2008-03-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>

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

#ifndef HAVE_INT8
#define HAVE_INT8
typedef signed char int8; /* NB: non-ANSI compilers may not grok */
typedef unsigned char uint8, uchar, byte, BYTE;
#endif

#ifndef HAVE_INT16
#define HAVE_INT16
typedef short int16;
typedef unsigned short uint16, word_t, ushort; /* sizeof （uint16） must == 2 */
#endif

#ifndef HAVE_INT32
#define HAVE_INT32
typedef int int32;
typedef unsigned int uint32, size_t, dword_t; /* sizeof （uint32） must == 4 */
typedef unsigned long ulong;
#endif

typedef long lresult;

typedef __int64 int64, longlong;
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

#ifdef _DEBUG
#include <stdarg.h>
static void DBG_TRACE（const char *fmt, ...） {
va_list ap;
va_start（ap, fmt）;
vprintf（fmt, ap）;
va_end（ap）;
}
#else
static void DBG_TRACE（const char *fmt, ...）{}
#endif

/*============================================================================*/
#endif /*UNISTD_H__*/