C语言通用链表实现
C语言的数组有时候很好用，但在不知道数据有多少的时候，并且涉及到某个数据的删除时，操作起来很不方便，这个时候就需要用到链表。自己定义一个链表数据结构，然后实现它，此时这个链表仅能表示你要处理的相关数据，并不是通用的，这将导致你要使用的时候就得重新写数据结构的代码。这个时候，定义一个通用链表，用这个链表就能处理所有的数据类型了，因为是通用的，所以会有一部分代码需要在用户使用的时候自己完成。
常见链表定义
struct Student
{
char name
[20];
int id
;
};
typedef struct node_t Node
;
struct node_t
{
struct Student stu
;
Node
*next
;
};
链表只是一个抽象概念，这里定义Node节点就可以表示一个链表信息。
也可以在定义的标准一点：
typedef struct {
Node
*head
;
Node
*tail
;
size_t size
;
} List
;
这里定义的List就是一个完完全全的链表了，有头结点，尾节点，还有链表大小。当然还可以在这里面增加很多内容，比如定义双向链表等。但是这个链表只能处理学生信息，不具备通用性。
下面定义一个通用链表：
typedef struct {
void *data
;
Node
*next
;
} Node
;
typedef struct {
Node
*head
;
Node
*tail
;
size_t size
;
} List
;
通过void *通用指针，我们可以处理不同的数据类型。（要是C语言可以用类型参数就好了）
通过这个通用链表，我们可以处理任何类型的链表。不在受到数据类型的约束。但是这会引入一个问题，就是关于data部分的内容，只能交给用户来进行处理 ，因为我们在写这个代码的时候并不清楚用户要使用何种类型的数据，只有在用户使用的时候才知道用什么数据。
所以链表该怎么写还是怎么写，当需要对data部分进行处理的时候，通过一个函数指针，把这部分的内容交给用户处理。这样，抽象出来的链表就是通用的，我们完成通用的部分，不通用的部分交给用户，用户在使用时，自己进行处理。这样能极大的减少代码量，还是能很方便的使用的。
list.h，list.c是我们定义的通用链表内容。用户使用的时候定义list_custom.h和list_custom.c，在这里完成data的定义和处理。
下面展示代码：
list.h
#ifndef __LIST_H__
#define __LIST_H__
#include <stdio.h>
typedef void (* p_free
)(void *data
);
typedef void *(* p_malloc
)(size_t size
);
typedef int (* p_traverse
)(void *nodeData
, void *data
);
typedef struct note_t Node
;
struct note_t
{
void *data
;
Node
*next
;
};
typedef struct {
Node
* head
;
Node
* tail
;
int size
;
} List
;
List
* init_list(void);
int delete_list(List
*plist
, p_free pfun_free
);
Node
* create_node(void *data
, p_malloc pfun_malloc
, size_t size
);
int delete_node(Node
*pnode
, p_free pfun_free
);
int add_node(List
*plist
, Node
*pnode
);
int remove_node(List
*plist
, p_free pfun_free
);
int remove_node_by_data(List
*plist
, void *data
, p_traverse pfun_compare
, p_free pfun_free
);
int traverse_list(List
*plist
, void *data
, p_traverse p_fun
);
Node
* get_node_by_index(List
*plist
, int index
);
Node
* find_node_by_data(List
*plist
, void *data
, p_traverse pfun_compare
);
int get_index_by_data(List
*plist
, void *data
, p_traverse pfun_compare
);
void sort_list(List
*plist
);
#endif
list.c
#include "list.h"
#include <stdlib.h>
#include <string.h>
#include "sal.h"
List
* init_list(void)
{
List
*plist
= NULL;
plist
= (List
*)malloc(sizeof(List
));
if (NULL == plist
) {
return NULL;
}
plist
->head
= NULL;
plist
->tail
= NULL;
plist
->size
= 0;
return plist
;
}
Node
* create_node(void *data
, p_malloc pfun_malloc
, size_t size
)
{
if (NULL == data
) {
return NULL;
}
Node
*pnode
= NULL;
pnode
= (Node
*)malloc(sizeof(Node
));
if (NULL == pnode
) {
return NULL;
}
pnode
->data
= pfun_malloc(size
);
if (pnode
->data
== NULL) {
free(pnode
);
return NULL;
}
memcpy(pnode
->data
, data
, size
);
pnode
->next
= NULL;
return pnode
;
}
int delete_node(Node
*pnode
, p_free pfun_free
)
{
SAL_CHECK_P_NULL(pnode
);
pfun_free(pnode
->data
);
free(pnode
);
return SAL_OK
;
}
int delete_list(List
*plist
, p_free pfun_free
)
{
SAL_CHECK_P_NULL(plist
);
Node
*pnode
= plist
->head
;
for (; pnode
!= NULL; pnode
= plist
->head
) {
plist
->head
= plist
->head
->next
;
delete_node(pnode
, pfun_free
);
}
free(plist
);
return SAL_OK
;
}
int add_node(List
*plist
, Node
*pnode
)
{
SAL_CHECK_P_NULL(pnode
);
SAL_CHECK_P_NULL(plist
);
if (NULL == plist
->head
) {
plist
->head
= pnode
;
plist
->tail
= pnode
;
}
else {
plist
->tail
->next
= pnode
;
plist
->tail
= pnode
;
}
plist
->size
++;
return SAL_OK
;
}
Node
* get_node_by_index(List
*plist
, int index
)
{
if (NULL == plist
|| NULL == plist
->head
|| index
< 1
|| index
> plist
->size
) {
return NULL;
}
Node
*pnode
= plist
->head
;
for (int i
= 1; i
< index
; i
++) {
pnode
= pnode
->next
;
}
return pnode
;
}
int remove_node(List
*plist
, p_free pfun_free
)
{
SAL_CHECK_P_NULL(plist
);
if (plist
->size
== 1) {
delete_node(plist
->tail
, pfun_free
);
plist
->head
= NULL;
plist
->tail
= NULL;
}
else {
Node
*pnode
= get_node_by_index(plist
, plist
->size
- 1);
if (NULL == pnode
) {
return SAL_ERR
;
}
delete_node(plist
->tail
, pfun_free
);
plist
->tail
= pnode
;
plist
->tail
->next
= NULL;
}
plist
->size
--;
return SAL_OK
;
}
int remove_node_by_data(List
*plist
, void *data
, p_traverse pfun_compare
, p_free pfun_free
)
{
SAL_CHECK_P_NULL(plist
);
SAL_CHECK_P_NULL(data
);
if (plist
->size
== 1 && 0 == pfun_compare(plist
->head
->data
, data
)) {
remove_node(plist
, pfun_free
);
}
else {
Node
*pnode
= plist
->head
;
for (Node
*pprior
= NULL; pnode
!= NULL; pprior
= pnode
, pnode
= pnode
->next
) {
if (0 == pfun_compare(pnode
->data
, data
)) {
pprior
->next
= pnode
->next
;
if (pnode
== plist
->tail
) {
plist
->tail
= pprior
;
}
delete_node(pnode
, pfun_free
);
plist
->size
--;
}
}
}
return SAL_OK
;
}
int get_index_by_data(List
*plist
, void *data
, p_traverse pfun_compare
)
{
SAL_CHECK_P_NULL(plist
);
SAL_CHECK_P_NULL(data
);
Node
*pnode
= plist
->head
;
for (int index
= 1; pnode
!= NULL; index
++, pnode
= pnode
->next
) {
if (0 == pfun_compare(pnode
->data
, data
)) {
return index
;
}
}
return 0;
}
Node
* find_node_by_data(List
*plist
, void *data
, p_traverse pfun_compare
)
{
if (NULL == plist
|| NULL == data
) {
return NULL;
}
#if 0
int index
= get_index_by_data(plist
, data
);
if (index
> 0) {
Node
*pnode
= NULL;
pnode
= get_node_by_index(plist
, index
);
if (pnode
!= NULL) {
return pnode
;
}
}
#else
Node
*pnode
= plist
->head
;
for (; pnode
!= NULL; pnode
= pnode
->next
) {
if (0 == pfun_compare(pnode
->data
, data
)) {
return pnode
;
}
}
#endif
return NULL;
}
int traverse_list(List
*plist
, void *data
, p_traverse pfun_traverse
)
{
SAL_CHECK_P_NULL(plist
);
Node
*pnode
= plist
->head
;
for (; pnode
!= NULL; pnode
= pnode
->next
) {
pfun_traverse(pnode
->data
, data
);
}
return SAL_OK
;
}
main.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
#include "list_custom.h"
int main()
{
List
*students
;
students
= init_list();
struct Student std
[5] = {
{"李明", 2001},
{"王强", 2002},
{"徐晓丽", 2003},
{"张强", 2004},
{"李伟", 2005}
};
for (int i
= 0; i
< 5; i
++) {
Node
*student
= create_node(std
+ i
, student_malloc
, sizeof(struct Student
));
add_node(students
, student
);
}
printf("\r\n------学生排名成绩表-------\r\n");
traverse_list(students
, NULL, student_print
);
printf("-------------------------\r\n\r\n");
Node
*pnode
= get_node_by_index(students
, 3);
struct Student
* stu3
= (struct Student
*)(pnode
->data
);
printf("第三名同学信息 name : %s, id : %d\r\n", stu3
->name
, stu3
->id
);
pnode
= find_node_by_data(students
, "张强", stu_name_compare
);
if (NULL == pnode
) {
printf("查无此人（张强）\r\n");
}
else {
struct Student
* stu
= (struct Student
*)(pnode
->data
);
printf("张强 name : %s, id : %d\r\n", stu
->name
, stu
->id
);
}
int rank
= get_index_by_data(students
, "李明", stu_name_compare
);
if (rank
< 1) {
printf("李明未上榜\r\n");
}
else {
printf("李明的排名： %d\r\n", rank
);
}
remove_node_by_data(students
, "王强", stu_name_compare
, student_free
);
printf("\r\n------学生排名成绩表-------\r\n");
traverse_list(students
, NULL, student_print
);
printf("-------------------------\r\n\r\n");
delete_list(students
, student_free
);
List
*worker
= init_list();
return 0;
}
list_custom.h
#ifndef __LIST_CUSTOM_H__
#define __LIST_CUSTOM_H__
#include <stdio.h>
struct Student
{
char name
[20];
int id
;
};
struct Worker
{
char name
[20];
long payment
;
char tele
[12];
};
void *student_malloc(size_t size
);
int student_print(void *nodeData
, void *data
);
int stu_name_compare(void *nodeData
, void *data
);
void student_free(void *data
);
#endif
list_custom.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
#include "list_custom.h"
void *student_malloc(size_t size
)
{
struct student
*stu
= (struct student
*)malloc(size
);
return stu
;
}
int student_print(void *nodeData
, void *data
)
{
struct Student
*stu
= (struct Student
*)(nodeData
);
printf("%s %d\r\n", stu
->name
, stu
->id
);
}
int stu_name_compare(void *nodeData
, void *data
)
{
char * name1
= (char *)nodeData
;
char * name2
= (char *)data
;
if (0 == strcmp(name1
, name2
)) {
return 0;
}
return -1;
}
void student_free(void *data
)
{
struct Student
*stu
= (struct Student
*)data
;
free(stu
);
}
链表测试结果
river@SHIELD-HJ:/mnt/f/Code/Code/clist$ ./test
------学生排名成绩表-------
李明 2001
王强 2002
徐晓丽 2003
张强 2004
李伟 2005
-------------------------
第三名同学信息 name
: 徐晓丽,
id : 2003
张强 name
: 张强,
id : 2004
李明的排名： 1
------学生排名成绩表-------
李明 2001
徐晓丽 2003
张强 2004
李伟 2005
-------------------------
要实现remove_node_by_index可以先用get_node_by_index然后再remove_node_by_data。
github连接：https://github.com/duapple/Code/tree/master/clist
