笔记

深浅模式

链表 ​

为什么需要链表？

前面我们写的线性表的顺序存储(动态数组)的案例，最大的缺点是插入和删除时需要移动大量元素，这显然需要耗费时间，。能不能想办法解决呢？链表。

链表为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。

单链表

  • 线性表的链式存储结构中，每个节点中只包含一个指针域，这样的链表叫单链表。
  • 通过每个节点的指针域将线性表的数据元素按其逻辑次序链接在一起（如图）。

概念解释：

  • 表头结点：链表中的第一个结点，包含指向第一个数据元素的指针以及链表自身的一些信息
  • 数据结点：链表中代表数据元素的结点，包含指向下一个数据元素的指针和数据元素的信息
  • 尾结点：链表中的最后一个数据结点，其下一元素指针为空，表示无后继。

单链表的设计 ​

插入操作 ​

c
node->next = current->next;
current->next = node;

删除操作 ​

c
current->next = ret->next;

C语言实现单链表 ​

c
#pragma once

#include <errno.h>
#include <stdio.h>

#define ERR_CHECK(lhs, rhs, errNum, msg, retVal) \
    {                                            \
        if (lhs == rhs) {                        \
            errno = errNum;                      \
            perror(msg);                         \
            return retVal;                       \
        }                                        \
    }
c
#pragma once

#include <stdbool.h>
#include <stdio.h>

// 定义节点结构体
typedef struct node {
    void *data;
    struct node *next;
} Node;

// 使用void*来防止用户直接获取到链表内的头节点进行恶意操作
typedef void *linkList;

// 初始化链表
linkList initLinkList();
// 插入数据 默认插入到链表头部
bool insertLinkList(linkList list, void *data);
// 按位置插入数据 如果指定无效位置则插入到链表头部 位置从0开始
bool insertByPosLinkList(linkList list, int pos, void *data);
// 获取链表长度
int getLengthLinkList(linkList list);
// 根据位置获取对应节点数据
void *getDataByPosLinkList(linkList list, int pos);
// 根据数据获取对应的索引位置
int indexOfLinkList(linkList list, void *data, bool (*compareElement)(void *data1, void *data2));
// 遍历链表
void forEachLinkList(linkList list, void (*prtList)(void *data));
// 清空链表
void clearLinkList(linkList list);
// 销毁链表
void destroyLinkList(linkList list);
c
#include "linkList.h"
#include "errcheck.h"
#include <stdlib.h>

typedef struct lList {
    Node *pHead; // 头节点
    int m_size;  // 链表长度
} LList;

linkList initLinkList() {
    LList *list = malloc(sizeof(LList));
    ERR_CHECK(list, NULL, ENOMEM, "初始化链表失败", NULL);

    list->pHead = malloc(sizeof(Node));
    ERR_CHECK(list->pHead, NULL, ENOMEM, "初始化链表失败", NULL);

    list->pHead->data = NULL;
    list->pHead->next = NULL;
    list->m_size = 0;

    return list;
}

bool insertLinkList(linkList list, void *data) {
    ERR_CHECK(list, NULL, EINVAL, "插入失败，传入参数有误", false);
    ERR_CHECK(data, NULL, EINVAL, "插入失败，传入参数有误", false);

    // 将void*还原成真实的链表结构
    LList *l = list;

    Node *node = malloc(sizeof(Node));
    ERR_CHECK(node, NULL, EINVAL, "插入失败，创建节点出错", false);

    node->data = data;
    node->next = l->pHead->next;
    l->pHead->next = node;
    ++l->m_size;

    return true;
}

bool insertByPosLinkList(linkList list, int pos, void *data) {
    ERR_CHECK(list, NULL, EINVAL, "插入失败，传入参数有误", false);
    ERR_CHECK(data, NULL, EINVAL, "插入失败，传入参数有误", false);

    // 将void*还原成真实的链表结构
    LList *l = list;

    if (pos < 0 || pos > l->m_size) {
        pos = 0;
    }

    Node *temp = l->pHead;
    for (int i = 0; i < pos; ++i) {
        temp = temp->next;
    }

    Node *node = malloc(sizeof(Node));
    ERR_CHECK(node, NULL, EINVAL, "插入失败，创建节点出错", false);

    node->data = data;
    node->next = temp->next;
    temp->next = node;
    ++l->m_size;

    return true;
}

int getLengthLinkList(linkList list) {
    ERR_CHECK(list, NULL, EINVAL, "传入的链表为空", -1);

    LList *l = list;

    return l->m_size;
}

void *getDataByPosLinkList(linkList list, int pos) {
    ERR_CHECK(list, NULL, EINVAL, "获取失败，传入的链表为空", NULL);

    LList *l = list;
    if (pos < 0 || pos >= l->m_size) {
        ERR_CHECK(0, 0, EINVAL, "获取失败，传入的位置有误", NULL);
    }

    Node *curNode = l->pHead->next;
    for (int i = 0; i < pos; ++i) {
        curNode = curNode->next;
    }

    return curNode->data;
}

int indexOfLinkList(linkList list, void *data, bool (*compareElement)(void *data1, void *data2)) {
    ERR_CHECK(list, NULL, EINVAL, "获取失败，传入的链表为空", -1);
    ERR_CHECK(compareElement, NULL, EINVAL, "获取失败，传入的比较函数为空", -1);

    LList *l = list;
    Node *curNode = l->pHead->next;
    int index = -1;
    for (int i = 0; i < l->m_size; ++i) {
        if (compareElement(curNode->data, data)) {
            index = i;
            break;
        }
        curNode = curNode->next;
    }

    return index;
}

void forEachLinkList(linkList list, void (*prtList)(void *data)) {
    ERR_CHECK(list, NULL, EINVAL, "传入的链表为空", );
    ERR_CHECK(prtList, NULL, EINVAL, "遍历失败，传入参数有误", );

    LList *l = list;
    Node *curNode = l->pHead->next;
    for (int i = 0; i < l->m_size; ++i) {
        prtList(curNode->data);
        curNode = curNode->next;
    }

    putchar('\n');
}

void clearLinkList(linkList list) {
    if (list == NULL) {
        return;
    }

    LList *l = list;
    if (l->m_size == 0) {
        return;
    }

    Node *curNode = l->pHead->next;
    for (int i = 0; i < l->m_size; ++i) {
        Node *delNode = curNode;
        curNode = curNode->next;
        free(delNode);
    }

    free(curNode);
    l->m_size = 0;
}

void destroyLinkList(linkList list) {
    if (list == NULL) {
        return;
    }

    clearLinkList(list);

    LList *l = list;

    free(l->pHead);
    l->pHead = NULL;

    free(l);
    l = NULL;
}
c
#include "linkList.h"

void printList(void *data) {
    int *p = data;
    printf("%d ", *p);
}

bool compareElement(void *lhs, void *rhs) {
    int *p1 = lhs;
    int *p2 = rhs;

    return *p1 == *p2;
}

int main(void) {
    linkList list = initLinkList();

    int a = 1;
    int b = 2;
    int c = 3;
    int d = 4;
    int e = 5;
    int f = 6;

    insertLinkList(list, &a);          // 1
    insertLinkList(list, &b);          // 2 1
    insertLinkList(list, &c);          // 3 2 1
    insertByPosLinkList(list, -1, &d); // 4 3 2 1
    insertByPosLinkList(list, 2, &e);  // 4 3 5 2 1
    insertByPosLinkList(list, 9, &f);  // 6 4 3 5 2 1

    forEachLinkList(list, printList);
    printf("list size is %d\n", getLengthLinkList(list));
    printf("list size is %d\n", getLengthLinkList(NULL));

    printf("pos is 3, data is %d\n", *(int *)(getDataByPosLinkList(list, 3)));
    // printf("pos is 7, data is %d\n", *(int *)(getDataByPosLinkList(list, 7)));

    int findNum = 3;
    printf("num %d index of %d\n", findNum, indexOfLinkList(list, &findNum, compareElement));

    clearLinkList(list);
    destroyLinkList(list);

    return 0;
}
bash
6 4 3 5 2 1 
list size is 6
传入的链表为空: Invalid argument
list size is -1
pos is 3, data is 5
num 3 index of 2

C语言实现单链表企业版 ​

企业版单链表的设计非常的巧妙，节点结构体内只维护指针域不维护数据域，指针域存放在用户数据的头部4字节内；链表结构体内正常维护头节点及链表长度。

c
#pragma once

#include <stdbool.h>
#include <stdio.h>

// 定义节点结构体
typedef struct node {
    // void *data;
    struct node *next;
} Node;

// 使用void*来防止用户直接获取到链表内的头节点进行恶意操作
typedef void *linkList;

// 初始化链表
linkList initLinkList();
// 插入数据 默认插入到链表头部
bool insertLinkList(linkList list, void *data);
// 按位置插入数据 如果指定无效位置则插入到链表头部 位置从0开始
bool insertByPosLinkList(linkList list, int pos, void *data);
// 获取链表长度
int getLengthLinkList(linkList list);
// 根据位置获取对应节点数据
void *getDataByPosLinkList(linkList list, int pos);
// 根据数据获取对应的索引位置
int indexOfLinkList(linkList list, void *data, bool (*compareElement)(void *data1, void *data2));
// 遍历链表
void forEachLinkList(linkList list, void (*prtList)(void *data));
// 清空链表 需要用户传入销毁元素的回调函数，如果是栈上的 回调函数可以直接返回 如果是堆上的 用户自行负责销毁
void clearLinkList(linkList list, void(*destoryElement)(void *data));
// 销毁链表
void destroyLinkList(linkList list);
c
#include "linkList.h"
#include "errcheck.h"
#include <stdlib.h>

typedef struct lList {
    Node *pHead; // 头节点
    int m_size;  // 链表长度
} LList;

linkList initLinkList() {
    LList *list = malloc(sizeof(LList));
    ERR_CHECK(list, NULL, ENOMEM, "申请链表空间失败", NULL);

    list->pHead = malloc(sizeof(Node));
    ERR_CHECK(list->pHead, NULL, ENOMEM, "申请链表头节点空间失败", list)

    list->m_size = 0;

    return list;
}

bool insertLinkList(linkList list, void *data) {
    ERR_CHECK(list, NULL, EINVAL, "插入失败，传入的链表为空", false);
    ERR_CHECK(data, NULL, EINVAL, "插入失败，传入的数据为空", false);

    LList *l = list;
    Node *node = data;

    node->next = l->pHead->next;
    l->pHead->next = node;
    ++l->m_size;

    return true;
}

bool insertByPosLinkList(linkList list, int pos, void *data) {
    ERR_CHECK(list, NULL, EINVAL, "插入失败，传入的链表为空", false);
    ERR_CHECK(data, NULL, EINVAL, "插入失败，传入的数据为空", false);

    LList *l = list;

    if (pos < 0) {
        pos = 0;
    } else if (pos > l->m_size) {
        pos = l->m_size;
    }

    Node *node = data;
    Node *curNode = l->pHead;
    for (int i = 0; i < pos; ++i) {
        curNode = curNode->next;
    }
    node->next = curNode->next;
    curNode->next = node;
    ++l->m_size;

    return true;
}

int getLengthLinkList(linkList list) {
    ERR_CHECK(list, NULL, EINVAL, "获取失败，传入的链表为空", -1);

    LList *l = list;

    return l->m_size;
}

void *getDataByPosLinkList(linkList list, int pos) {
    ERR_CHECK(list, NULL, EINVAL, "获取失败，传入的链表为空", NULL);

    LList *l = list;
    if (pos < 0 || pos >= l->m_size) {
        ERR_CHECK(0, 0, EINVAL, "获取失败，传入的位置有误", NULL);
    }

    Node *curNode = l->pHead->next;
    for (int i = 0; i < pos; ++i) {
        curNode = curNode->next;
    }

    return curNode;
}

int indexOfLinkList(linkList list, void *data, bool (*compareElement)(void *data1, void *data2)) {
    ERR_CHECK(list, NULL, EINVAL, "获取失败，传入的链表为空", -1);
    ERR_CHECK(data, NULL, EINVAL, "获取失败，传入的链表为空", -1);
    ERR_CHECK(compareElement, NULL, EINVAL, "获取失败，传入的链表为空", -1);

    LList *l = list;
    Node *curNode = l->pHead->next;
    int index = -1;
    for (int i = 0; i < l->m_size; ++i) {
        if (compareElement(curNode, data)) {
            index = i;
        }
        curNode = curNode->next;
    }

    return index;
}

void forEachLinkList(linkList list, void (*prtList)(void *data)) {
    ERR_CHECK(list, NULL, EINVAL, "遍历失败，传入的链表为空", );
    ERR_CHECK(prtList, NULL, EINVAL, "遍历失败，传入的打印函数为空", );

    LList *l = list;
    Node *curNode = l->pHead->next;
    for (int i = 0; i < l->m_size; ++i) {
        prtList(curNode);
        curNode = curNode->next;
    }
    // putchar('\n');
}

void clearLinkList(linkList list, void (*destoryElement)(void *data)) {
    ERR_CHECK(list, NULL, EINVAL, "清空失败，传入的链表为空", );
    ERR_CHECK(destoryElement, NULL, EINVAL, "清空失败，传入的销毁元素函数为空", );

    LList *l = list;
    Node *curNode = l->pHead->next;
    Node *delNode = NULL;
    for (int i = 0; i < l->m_size; ++i) {
        delNode = curNode;
        curNode = curNode->next;

        destoryElement(delNode);
    }
    l->m_size = 0;
}

void destroyLinkList(linkList list) {
    if (list == NULL) {
        return;
    }

    LList *l = list;

    free(l->pHead);
    l->pHead = NULL;

    free(l);
    l = NULL;
}
c
#include "linkList.h"
#include <string.h>

// 定义用户数据结构体，把头节点的4个字节给链表使用，在其后面放用户数据
// 32位平台是4字节， 64位平台位8字节，只要放一个指针类型就行了
typedef struct person {
    void *pNode;
    char name[1024];
    int age;
} Person;

void printList(void *data) {
    Person *p = data;
    printf("name is %s, age is %d\n", p->name, p->age);
}

bool compareElement(void *lhs, void *rhs) {
    Person *p1 = lhs;
    Person *p2 = rhs;

    return p1->age == p2->age && (strcmp(p1->name, p2->name) == 0);
}

void destoryPerson(void * data){
    return;
}

int main(void) {
    linkList list = initLinkList();

    Person p1;
    p1.age = 18;
    strcpy(p1.name, "张三");
    Person p2;
    p2.age = 20;
    strcpy(p2.name, "李四");
    Person p3;
    p3.age = 15;
    strcpy(p3.name, "王五");
    Person p4;
    p4.age = 12;
    strcpy(p4.name, "小明");
    Person p5;
    p5.age = 22;
    strcpy(p5.name, "小红");

    insertLinkList(list, &p1);
    insertLinkList(list, &p2);
    insertByPosLinkList(list, -1, &p3);
    insertByPosLinkList(list, 1, &p4);
    insertByPosLinkList(list, 10, &p5);

    forEachLinkList(list, printList);

    printf("list size is %d\n", getLengthLinkList(list));

    printList(getDataByPosLinkList(list, 2));

    printf("%s is index of %d\n", p3.name, indexOfLinkList(list, &p3, compareElement));
    printf("%s is index of %d\n", p2.name, indexOfLinkList(list, &p2, compareElement));

    clearLinkList(list, destoryPerson);
    destroyLinkList(list);

    return 0;
}
bash
$ gcc *.c -o main -g -Wall
$ valgrind --tool=memcheck --leak-check=full ./main
==32560== Memcheck, a memory error detector
==32560== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==32560== Using Valgrind-3.22.0 and LibVEX; rerun with -h for copyright info
==32560== Command: ./main
==32560== 
name is 王五, age is 15
name is 小明, age is 12
name is 李四, age is 20
name is 张三, age is 18
name is 小红, age is 22
list size is 5
name is 李四, age is 20
王五 is index of 0
李四 is index of 2
==32560== 
==32560== HEAP SUMMARY:
==32560==     in use at exit: 0 bytes in 0 blocks
==32560==   total heap usage: 3 allocs, 3 frees, 1,048 bytes allocated
==32560== 
==32560== All heap blocks were freed -- no leaks are possible
==32560== 
==32560== For lists of detected and suppressed errors, rerun with: -s
==32560== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

优缺点 ​

优点：

  • 无需一次性定制链表的容量
  • 插入和删除操作无需移动数据元素

缺点：

  • 数据元素必须保存后继元素的位置信息
  • 获取指定数据的元素操作需要顺序访问之前的元素