使⽤C语⾔实现“泛型”链表
看到这个标题，你可能⾮常惊讶，C语⾔也能实现泛型链表？我们知道链表是我们⾮常常⽤的数据结构，但是在C中却没有像C++中的STL那样有⼀个list的模板类，那么我们是否可以⽤C语⾔实现⼀个像STL中的list那样的泛型链表呢？答案是肯定的。下⾯就以本⼈的⼀个⽤C语⾔设计的链表为例⼦，来分析说明⼀下本⼈的设计和实现要点，希望能给你⼀点有⽤的帮助。
⼀、所⽤的链表类型的选择c语言struct用法例子
我们知道，链表也有⾮常多的类型，包括单链表、单循环链表、双链表、双向循环链表等。在我的设计中，我的链表使⽤的类型是双向循环链表，并带⼀个不保存真实数据的头结点。其原因如下：
1）单链表由于不能从后继定位到前驱，在操作时较为不⽅便
2）双链表虽然能⽅便到前驱，但是如果总是在其尾部插⼊或删除结点，为了定位的⽅便和操作的统⼀（所有的删除和插⼊操作，都跟在中间插⼊删除结点的操作⼀样），还要为其增加⼀个尾结点，并且程序还要保存⼀个指向这个尾结点的指针，并管理这个指针，从⽽增加程序的复杂性。⽽使⽤带头结点的循环双向链表，就能⽅便的定位（其上⼀个元素为链表的最后⼀个元素，其下⼀个元素为链表的第0个元素），并使所有的插⼊和删除的操作统⼀，因为头结点也是尾结点。注：结点的下标从0开始，头结点不算⼊下标值。
3）接⼝的使⽤与C++中stl中list和泛型算法的使⽤⼤致相同。
⼆、list类型的定义
为了让⼤家⼀睹为快，下⾯就给出这个⽤C语⾔实现的“泛型”的定义，再来说明，我这样设计的原因及要点，其定义如下：其定义在⽂件list_v2.c中
[cpp]
1. <SPAN ><SPAN >typedef struct node
2. {
3. //循环双链表的结点结构
4. void* data;//数据域指针
5. struct node *next;//指向当前结点的下⼀结点
6. struct node *last;//指向当前结点的上⼀结点
7. }Node;
8. struct list
9. {
10. struct node *head;//头指针，指向头结点
11. int data_size;//链表对应的数据所占内存的⼤⼩
12. int length;//链表list的长度
13. };</SPAN></SPAN>
typedef struct node
{
//循环双链表的结点结构
void* data;//数据域指针
struct node *next;//指向当前结点的下⼀结点
struct node *last;//指向当前结点的上⼀结点
}Node;
struct list
{
struct node *head;//头指针，指向头结点
int data_size;//链表对应的数据所占内存的⼤⼩
int length;//链表list的长度
};
其声明在⽂件list_v2.h中
[cpp]
1. <SPAN ><SPAN >//泛型循环双链表，带头结点，结点下标从0开始，
头结点不计⼊下标值
2.
3. //定义结点指针Node*为List类型的迭代器
4. typedef struct node* Iterator;
5.
6. //List类型的定义
7. typedef struct list* List;
8.
9. //初始化链表，数据域所占内存的⼤⼩由data_size给出
10. int InitList(List *list, int data_size);
11.
12. //把data的内容插⼊到链表list的末尾
13. //assign指定数据data间的赋值⽅法
14. Iterator Append(List list, void *data,
15. void (*assign)(void*, const void*));
16.
17. //把data的内容插⼊到链表的迭代器it_before的前⾯
18. //assign指定数据data间的赋值⽅法
19. Iterator Insert(List list, void *data, Iterator it_before,
20. void (*assign)(void*, const void*));
21.
22. //把链表A中迭代器it_a指向的结点移动到链表B中迭代器it_b_befroe的前⾯
23. Iterator MoveFromAtoB(List A, Iterator it_a,
24. List B, Iterator it_b_before);
25.
26. //删除链表list中迭代器it指向的结点
27. int Remove(List list, Iterator it);
28.
29. //删除链表list的第0个结点，下标从0开始
30. int RemoveFirst(List list);
31.
32. //删除链表list的最后⼀个结点
33. int RemoveLast(List list);
34.
35. //返回list中第index个数据的指针
36. void* At(List list, int index);
37.
38. //在begin和end之间查符合condition的第⼀个元素，
39. //⽐较函数由condition指向,⽐较的值由data指向
40. //当第⼀个参数的值⼩于第⼆个参数的值时，返回1，否则返回0
41. //根据condition函数的不同，可以查第⼀个相等、⼤于或⼩于data的值
42. Iterator FindFirst(Iterator begin, Iterator end, void *data,
43. int (*condition)(const void*, const void*));
44.
45. //查list中第⼀个与data相等的元素的下标，
46. //equal函数，当第⼀个参数与第⼆个参数的值相等时，返回1，否则返回0
47. int IndexOf(List list, void *data,
48. int (*equal)(const void*,const void*));
49.
50. //查在begin和end之间的最⼩值，⽐较函数由less指向
51. //当第⼀个参数的值⼩于第⼆个参数的值时，返回1，否则返回0
52. Iterator GetMin(Iterator begin, Iterator end,
53. int (*less)(const void*, const void*));
54.
55. //查在begin和end之间的最⼤值，⽐较函数由large指向
56. //当第⼀个参数的值⼤于第⼆个参数的值时，返回1，否则返回0
57. Iterator GetMax(Iterator begin, Iterator end,
58. int (*large)(const void*, const void*));
59.
60. //获取list的长度
61. int GetLength(List list);
62.
63. //若list为空链表，则返回1，否则返回0
64. int IsEmpty(List list);
65.
66. //销毁list
67. void DestroyList(List *list);
68.
69. //获得list的⾸迭代器
70. Iterator Begin(List list);
71.
72. //获得list的尾迭代器，指向最后⼀个元素的下⼀个位置
73. Iterator End(List list);
74.
75. //使it指向下⼀个位置，并返回指向下⼀个位置后的迭代器
76. Iterator Next(Iterator *it);
77.
78. //使it指向上⼀个位置，并返回指向上⼀个位置后的迭代器
79. Iterator Last(Iterator *it);
80.
81. //通过迭代器it获得数据，相当于*p
82. void* GetData(Iterator it);
83.
84. //获取当前迭代器的下⼀个迭代器，注意，并不改变当前迭代器
85. Iterator GetNext(Iterator it);
85. Iterator GetNext(Iterator it);
86.
87. //获取当前迭代器的上⼀个迭代器，注意，并不改变当前迭代器
88. Iterator GetLast(Iterator it);</SPAN></SPAN>
//泛型循环双链表，带头结点，结点下标从0开始，头结点不计⼊下标值
//定义结点指针Node*为List类型的迭代器
typedef struct node* Iterator;
//List类型的定义
typedef struct list* List;
//初始化链表，数据域所占内存的⼤⼩由data_size给出
int InitList(List *list, int data_size);
//把data的内容插⼊到链表list的末尾
//assign指定数据data间的赋值⽅法
Iterator Append(List list, void *data,
void (*assign)(void*, const void*));
//把data的内容插⼊到链表的迭代器it_before的前⾯
//assign指定数据data间的赋值⽅法
Iterator Insert(List list, void *data, Iterator it_before,
void (*assign)(void*, const void*));
//把链表A中迭代器it_a指向的结点移动到链表B中迭代器it_b_befroe的前⾯Iterator MoveFromAtoB(List A, Iterator it_a,
List B, Iterator it_b_before);
//删除链表list中迭代器it指向的结点
int Remove(List list, Iterator it);
//删除链表list的第0个结点，下标从0开始
int RemoveFirst(List list);
//删除链表list的最后⼀个结点
int RemoveLast(List list);
//返回list中第index个数据的指针
void* At(List list, int index);
//在begin和end之间查符合condition的第⼀个元素，
//⽐较函数由condition指向,⽐较的值由data指向
//当第⼀个参数的值⼩于第⼆个参数的值时，返回1，否则返回0
//根据condition函数的不同，可以查第⼀个相等、⼤于或⼩于data的值Iterator FindFirst(Iterator begin, Iterator end, void *data,
int (*condition)(const void*, const void*));
//查list中第⼀个与data相等的元素的下标，
//equal函数，当第⼀个参数与第⼆个参数的值相等时，返回1，否则返回0
int IndexOf(List list, void *data,
int (*equal)(const void*,const void*));
//查在begin和end之间的最⼩值，⽐较函数由less指向
//当第⼀个参数的值⼩于第⼆个参数的值时，返回1，否则返回0
Iterator GetMin(Iterator begin, Iterator end,
int (*less)(const void*, const void*));
//查在begin和end之间的最⼤值，⽐较函数由large指向
//当第⼀个参数的值⼤于第⼆个参数的值时，返回1，否则返回0
Iterator GetMax(Iterator begin, Iterator end,
int (*large)(const void*, const void*));
//获取list的长度
int GetLength(List list);
//若list为空链表，则返回1，否则返回0
int IsEmpty(List list);
//销毁list
void DestroyList(List *list);
//获得list的⾸迭代器
Iterator Begin(List list);
//获得list的尾迭代器，指向最后⼀个元素的下⼀个位置
Iterator End(List list);
//使it指向下⼀个位置，并返回指向下⼀个位置后的迭代器
Iterator Next(Iterator *it);
/
/使it指向上⼀个位置，并返回指向上⼀个位置后的迭代器
Iterator Last(Iterator *it);
//通过迭代器it获得数据，相当于*p
void* GetData(Iterator it);
//获取当前迭代器的下⼀个迭代器，注意，并不改变当前迭代器
Iterator GetNext(Iterator it);
//获取当前迭代器的上⼀个迭代器，注意，并不改变当前迭代器
Iterator GetLast(Iterator it);
为了更加清楚地表达这个链表的结构，下图所⽰的，就是该链表的结构：
调⽤InitList函数后，链表的结构如下：
当向链表中插⼊⼀定数量的结点后，链表的结构如下：
PS：其完整的代码可以点击这⾥下载：
三、如何实现隐藏链表的成员变量（即封装）
⾸先，我们为什么需要封装呢？我觉得封装主要有三⼤好处。
1）隔离变化，在程序中需要封装的通常是程序中最容易发⽣变化的地⽅，例如成员变量等，我们可以把它们封装起来，从⽽让它们的变化不会影响到系统的其他部分，也就是说，封装的是变化。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论