C语言通用链表实现_c语言中使用链表的通用实现

最近想对自己的知识和技能做一个总结，看到有人在博客上说，最好的知识总结，就是将知识固化，所谓的固化，就是把所学的知识记录下来，或者写成笔记或者写成博客。最近也想实践一下，就从写博客开始，之前也把学习的过程通过学习笔记的形式写成博客，回头看一下还是有很多好处的，一来作为一种知识分享，让想学习同样知识的同学可以一起学习，二来可以作为自己学习的回顾，增加自己的学习效果。

总之，不管是学习还是做别的事情，都不能光想，落到实践上比什么都重要，尤其是做技术，动手能力非常重要。昨天自己动手写了一个通用的链表库，这里将代码贴出来，写的不对的地方还请大侠帮忙指正：

头文件list.h：

/***********************************************************
文件名：list.h
作者：Jerry
日期：2017年04月

转发或拷贝请将这段注释一起拷贝
***********************************************************/

#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED

#ifdef __cplusplus
extern "C"{
#endif
/*定义错误码*/
enum{
    LIST_OK = 0,    //成功
    LIST_ERR = 1    //失败
};


typedef struct tagNode{
    struct tagNode *pPrev;
    struct tagNode *pNext;
    void *data;
}LIST_NODE_S;

typedef struct tagList{
    LIST_NODE_S *pHead;
    LIST_NODE_S *pTail;
    unsigned int count;
}LIST_S;


/*迭代器结构*/
typedef LIST_NODE_S LIST_ITER_S;


typedef void(*ListDataFreeFunc)(void*);

/**************************************
功能：初始化空的链表
参数：
返回值：指向空链表的指针
**************************************/
extern LIST_S *List_Api_New();


/*****************************************
功能：释放LIST_S结构链表，对每一个链表结点调用pFunc释放内存
参数：
    LIST_S *pList,  //链表指针
    ListDataFreeFunc pFunc  //结点释放函数
返回值：void
******************************************/
extern void List_Api_FreeEx(LIST_S *pList, ListDataFreeFunc pFunc);



/***************************************************************
功能:向链表尾部插入数据
参数：
    LIST_S *pList    //要插入数据的链表,不能为NULL
    void *data     //要插入的数据，不区分类型，需要用户申请内存
返回值: 插入成功返回LIST_OK,失败返回非LIST_ERR
*******************************************************************/
extern int List_Api_Append(LIST_S *pList, void *data);



/************************************************************
功能：获取指向链表第一个元素的迭代器指针
参数：
    LIST_S *pList    //要操作的链表
返回值：指向第一个元素的迭代器指针
*************************************************************/
extern LIST_ITER_S *List_Api_Begin(LIST_S *pList);




/************************************************************
功能：获取指向链表最后一个元素的迭代器指针
参数：
    LIST_S *pList       //要操作的链表
返回值：指向最后一个元素的迭代器指针
*************************************************************/
extern LIST_ITER_S *List_Api_Last(LIST_S *pList);


/***********************************************************
功能：获取当前迭代器位置的数据
参数：
    LIST_ITER_S *pIter    //当前迭代器指针
返回值：void *
************************************************************/
extern void *List_Api_GetData(LIST_ITER_S *pIter);


/**********************************************************
功能：获取当前迭代器的前一个迭代器指针
参数：
    LIST_ITER_S *pIter  
返回值：LIST_ITER_S *
***********************************************************/
extern LIST_ITER_S *List_Api_Previous(LIST_ITER_S *pIter);


/**********************************************************
功能：获取当前迭代器的后一个迭代器指针
参数：
    LIST_ITER_S *pIter
返回值：LIST_ITER_S *
***********************************************************/
extern LIST_ITER_S *List_Api_Next(LIST_ITER_S *pIter);


/*********************************************************
功能：删除当前迭代器指向位置的元素
参数：
    LIST_S *pList         //要操作的链表，不能为NULL
    LIST_ITER_S *pIter    //当前迭代器
返回值：下一个迭代器指针
***********************************************************/
extern LIST_ITER_S *List_Api_Delete(LIST_S *pList, LIST_ITER_S *pIter); 


/*********************************************************
功能：获取当前链表长度
参数：LIST_S *pList   //要计算长度的链表
返回值：unsigned int
**********************************************************/
extern unsigned int List_Api_GetCount(LIST_S *pList);


#define List_Api_Free(p)   do{if(p) free(p); p = NULL;}while(0)


#ifdef __cplusplus
}
#endif

#endif // LIST_H_INCLUDED
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

源文件 list.c：

#include "list.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>


LIST_S *List_Api_New(){
    LIST_S *pList;
    pList = (LIST_S *)malloc(sizeof(LIST_S));
    if(NULL != pList) memset(pList, 0, sizeof(LIST_S));
    return pList;
}


void List_Api_FreeEx(LIST_S *pList, ListDataFreeFunc pFunc){
    LIST_ITER_S *pHead, *pNext;

    if(!pList) return;
    assert(pFunc != NULL);

    pHead = pList->pHead;
    while(pHead){
        pNext = pHead->pNext;
        pFunc(pHead->data);
        pHead = pNext;      
    }   

    pList->pHead = NULL;
    pList->pTail = NULL;
    pList->count = 0;
    List_Api_Free(pList);
}


int List_Api_Append(LIST_S *pList, void *data){
    LIST_NODE_S *pNode;
    assert(pList != NULL);
    pNode = (LIST_NODE_S *)malloc(sizeof(LIST_NODE_S));
    if(NULL == pNode){
        return LIST_ERR;
    }
    memset(pNode, 0, sizeof(LIST_NODE_S));
    pNode->data = data;
    if(pList->pHead == NULL){
        pList->pHead = pNode;   
        pList->pTail = pList->pHead;
    }
    else {
        //挂接结点
        pList->pTail->pNext = pNode;
        pNode->pPrev = pList->pTail;
        //更新链表尾结点
        pList->pTail = pList->pTail->pNext;
    }
    pList->count ++;

    return LIST_OK;
}

void *List_Api_GetData(LIST_ITER_S *pIter){
    assert(pIter != NULL);

    return pIter->data;
}

LIST_ITER_S *List_Api_Begin(LIST_S *pList){
    if(!pList) return NULL;
    return (LIST_ITER_S*)(pList->pHead);    
}

LIST_ITER_S *List_Api_Last(LIST_S *pList){
    if(!pList) return NULL;
    return (LIST_ITER_S*)(pList->pTail);
}


LIST_ITER_S *List_Api_Previous(LIST_ITER_S *pIter){
    assert(pIter !=NULL);
    return pIter->pPrev;
}

LIST_ITER_S *List_Api_Next(LIST_ITER_S *pIter){
    assert(pIter != NULL);
    return pIter->pNext;
}

LIST_ITER_S *List_Api_Delete(LIST_S *pList, LIST_ITER_S *pIter){
    LIST_ITER_S *pHead = NULL;
    LIST_ITER_S *pTail = NULL;
    if(!pList) return NULL;

    assert(pIter != NULL);

    pHead = pList->pHead;
    pTail = pList->pTail;

    if(pIter == pHead){
        pList->pHead = pIter->pNext;
        pList->pHead->pPrev = NULL;
        pList->count --;
        pIter->pPrev = NULL;
        pIter->pNext = NULL;
        return pList->pHead;
    }   

    if(pIter == pTail){
        pList->pTail = pList->pTail->pPrev;
        pList->pTail->pNext = NULL;
        pList->count --;
        pIter->pPrev = NULL;
        pIter->pNext = NULL;
        return NULL;
    } 

    while(pHead != pIter && pHead != pTail){
        pHead = pHead->pNext;
    }

    if(pHead == pTail){
        return NULL;
    }

    pHead = pIter->pPrev->pNext = pIter->pNext;
    pIter->pNext->pPrev = pIter->pPrev;
    pList->count --;

    pIter->pNext = NULL;
    pIter->pPrev = NULL;

    return pHead;
}

unsigned int List_Api_GetCount(LIST_S *pList){
    if(!pList) return 0;
    return pList->count;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

下面的这段代码可以对上面的接口进行测试：

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct testData{
    char *name;
    int age;
}STUDENT_S;


static STUDENT_S *Student_New(char *name, int age){
    STUDENT_S *stu;
    stu = (STUDENT_S*)malloc(sizeof(STUDENT_S));
    if(!stu) return NULL;
    memset(stu, 0, sizeof(STUDENT_S));
    stu->name = strdup(name);
    stu->age = age;
    return stu;
}

static void Student_Free(STUDENT_S *pStu){
    if(!pStu) return ;
    if(pStu->name) free(pStu->name);
    free(pStu);
}

int main(int argc, char **argv){
    int *val = NULL, i;
    int iRet;
    STUDENT_S students[] = {
        {"xiaoming", 15},
        {"xiaohua", 16},
        {"xiaofang", 16}
    };
    LIST_ITER_S *pstIter = NULL;

    LIST_S *pList = List_Api_New();
    if(!pList){
        fprintf(stderr, "out of memory");
        exit(1);
    }

    for(i = 0; i < sizeof(students)/sizeof(students[0]); i ++){
        STUDENT_S *pStu = Student_New(students[i].name, students[i].age);
        if(!pStu){
            fprintf(stderr, "out of momory");
            List_Api_FreeEx(pList, (void(*)(void*))Student_Free);
            exit(1);
        }
        iRet = List_Api_Append(pList, pStu);
        if(iRet != LIST_OK){
            Student_Free(pStu);
        }
        pStu = NULL;
    }   


    printf("\ncount: %u\n", List_Api_GetCount(pList));
    printf("output from first to last\n");
    pstIter = List_Api_Begin(pList);
    while(pstIter != NULL){
        STUDENT_S *v = (STUDENT_S *)List_Api_GetData(pstIter);
        if(v)
        {   
            printf("Name: %s\n", v->name);
            printf("Age: %d\n", v->age);
        }
        pstIter = List_Api_Next(pstIter);
    }


    printf("\noutput from last to first\n");
    pstIter = List_Api_Last(pList);
    while(pstIter != NULL){
        STUDENT_S *v = (STUDENT_S *)List_Api_GetData(pstIter);
        if(v)
        {   
            printf("Name: %s\n", v->name);
            printf("Age: %d\n", v->age);
        }
        pstIter = List_Api_Previous(pstIter);
    }

    printf("\nDelete first student\n");
    pstIter = List_Api_Begin(pList);
    //pstIter = List_Api_Next(pstIter);  //如果要删除中间的一个，将这一句前面的注释去掉
    (void)List_Api_Delete(pList, pstIter);

    Student_Free((STUDENT_S*)(pstIter->data));

    printf("\nnow count: %u\n", List_Api_GetCount(pList));
    printf("left students are:\n");
    pstIter = List_Api_Begin(pList);
    while(pstIter != NULL){
        STUDENT_S *v = (STUDENT_S *)List_Api_GetData(pstIter);
        if(v)
        {   
            printf("Name: %s\n", v->name);
            printf("Age: %d\n", v->age);
        }
        pstIter = List_Api_Next(pstIter);
    }

    List_Api_FreeEx(pList, (void(*)(void*))Student_Free);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108