本文将介绍使用C中关键字struct 定义结构体实现单链表。
在C语言中，结构体的自引用只能通过指针来实现，因为在系统中指针的大小是固定（32位系统时大小是4字节，64位系统时大小是8字节）。
结构体自引用实现方式
有2种实现方式，
方式一：
typedef struct tagNode
{
char *pItem;
struct tagNode *next;
} *pNode; // 注意结构体的结尾一定得有分号
方式二：
// typedef 一定要定义在struct之前
typedef struct tagNode *pNode;
struct tageNode
{
char *pItem;
pNode next;
};
链表定义
定义链表和相关操作
// 定义一个用显示数据的函数指针
typedef void (*DISPLAY)(void*);
// 定义一个用于比较数据大小的函数指针
typedef int (*COMPARE)(void*, void*);
// 节点定义
typedef struct _node
{
void *data; // 节点数据
struct _node *next; // 下一个节点
} *pNode;
// 链表定义
typedef struct _linkedlist
{
pNode *head;
pNode *tail;
pNode *current;
} LinkedList;
// 初始化链表
void init_linkedlist(LinkedList *list)
{
list->head = NULL;
list->tail = NULL;
list->current = NULL;
}
// 向链表头添加数据节点
void addHead(LinkedList *list, void *data)
{
pNode node = (pNode) malloc(sizeof(Node));
node->data = data;
if (list->head == NULL) {
list->tail = node;
node->next = NULL;
} else {
node->next = list->head;
}
list->head = node;
}
// 向链表尾部添加数据节点
void addTail(LinkedList *list, void *data)
{
pNode node = (pNode) malloc(sizeof(Node));
node->data = data;
node->next = NULL;
if (list->head == NULL) {
list->head = node;
} else {
list->tail->next = node;
}
list->tail = node;
}
// 获取指定的节点信息
pNode getNode(LinkedList *list, COMPARE compare, void *data)
{
pNode node = list->head;
while (node != NULL) {
if (compare(node->data, data)) {
return node;
}
node = node->next;
}
return NULL;
}
// 删除指定的节点
void deleteNode(LinkedList *list, pNode node)
{
if (node == list->head)
{
if (list->head->next == NULL) {
list->head = list->tail = NULL;
} else {
list->head = list->head->next;
}
} else {
pNode tmp = list->head;
while (tmp != NULL && tmp->next != node)
{
tmp = tmp->next;
}
if (tmp != NULL) {
tmp->next = node->next;
}
}
free(node);
}
// 展示数据
void displayList(LinkedList *list, DISPLAY display)
{
printf("\nLinkedList shown:\n");
pNode node = list->head;
while (node != NULL) {
display(node->data);
node = node->next;
}
}
// 比较函数
int compareInt(int *e1, int *e2)
{
return *e1 == *e2;
}
// 显示数据
void displayIntVal(int *e)
{
printf("%d\n", *e);
}
使用示例
1.从链表头部开始添加数据
LinkedList linkedList;
// 初始化
init_linkedlist(&linkedList);
int a = 20;
int b = 30;
int c = 40;
int *ptr_1 = &a;
int *ptr_2 = &b;
int *ptr_3 = &c;
addHead(&linkedList, ptr_1);
addHead(&linkedList, ptr_2);
addHead(&linkedList, ptr_3);
displayList(&linkedList, (DISPLAY)displayIntVal);
打印结果：
LinkedList shown:
40
30
20
2.从链表尾部添加数据
LinkedList linkedList;
// 初始化
init_linkedlist(&linkedList);
int a = 20;
int b = 30;
int c = 40;
int *ptr_1 = &a;
int *ptr_2 = &b;
int *ptr_3 = &c;
addTail(&linkedList, ptr_1);
addTail(&linkedList, ptr_2);
addTail(&linkedList, ptr_3);
displayList(&linkedList, (DISPLAY)displayIntVal);
打印结果：
LinkedList shown:
20
30
40
3.获取指定的节点
LinkedList linkedList;
// 初始化
init_linkedlist(&linkedList);
int a = 20;
int b = 30;
int c = 40;
int *ptr_1 = &a;
int *ptr_2 = &b;
int *ptr_3 = &c;
addTail(&linkedList, ptr_1);
addTail(&linkedList, ptr_2);
addTail(&linkedList, ptr_3);
pNode node = getNode(&linkedList, (COMPARE) compareInt, ptr_2);
printf("node val is %d\n", *((int *)node->data));
打印结果：
node val is 30
4.删除指定的节点
LinkedList linkedList;
// 初始化
init_linkedlist(&linkedList);
int a = 20;
int b = 30;
int c = 40;
int *ptr_1 = &a;
int *ptr_2 = &b;
int *ptr_3 = &c;
addTail(&linkedList, ptr_1);
addTail(&linkedList, ptr_2);
addTail(&linkedList, ptr_3);
pNode node = getNode(&linkedList, (COMPARE) compareInt, ptr_2);
printf("node val is %d\n", *((int *)node->data));
deleteNode(&linkedList, node);
displayList(&linkedList, (DISPLAY)displayIntVal);
打印结果：
node val is 30
LinkedList shown:
20
40
以上就是全部的内容，如有错误，欢迎留言交流或者关注公众号交流。
