标签： 单链表

C-单链表的实现

本文将介绍使用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

以上就是全部的内容，如有错误，欢迎留言交流或者关注公众号交流。