C语言实现一个简单的单向链表list
cheungmine
用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__*/
好了。是不是很简单啊。适合初学者学习,适合喜欢简单就是生活的人!
标签:node,head,listnode,list,C语言,链表,size,define From: https://blog.51cto.com/mapaware/6024048