数据结构 - 链表

Intro

链表是一个非常基础的数据结构，包括二叉树，所谓的环等都是链表变种。无论是上位机还是下位机多少都能看到它的影子。

Q&A

Q.为什么不用数组

A1: 数组编译的时候要确认大小，不能动态插入

A2: 链表非连续存储，插入速度更快

A3: 动态分配堆内存，避免爆栈StackOverflow(常见于上位机开发)

Example

链表示例(基于Linux Shell代码)

假设你需要处理一个别名，比如将a替换为b，那么这时候有两个字符串，如果要动态插入动态删除这时候链表就派上用场了

类型定义

struct alias
{
    char *alias_name;
    char *alias_command;
    struct alias *next;
};
typedef struct alias *alias_t;

上述代码新建一个结构体，内含两个指向char类型的指针，定义一个新类型alias_t -> struct alias *

struct head_alias
{
    struct alias *next;
};
typedef struct head_alias *head_alias_t;

创建一个链表头，内含一个alias_t变量

这里多一个head_alias_t看似多此一举，实际上假设你的链表头是alias_t类型，刚好你要free()的就是链表头那就会Segmentation fault(段错误了)

创建链表

static alias_t init_alias(alias_t alias_chain, const char *alias_name, const char
*alias_command)
{
    alias_chain = (alias_t)malloc(sizeof(struct alias));
    alias_chain->alias_name = mstrcpy(NULL, alias_name);
    alias_chain->alias_command = mstrcpy(NULL, alias_command);
    alias_chain->next = NULL;
    return alias_chain;
}

head_alias_t init_alias_head(head_alias_t alias_head)
{
    alias_head = (head_alias_t)malloc(sizeof(struct head_alias));
    if (alias_head != NULL)
    {
        alias_head->next = NULL;
        return alias_head;
    }
    else
        return NULL;
}

此处mstrcpy()原型为封装函数，实现如下

static inline unsigned short count_for_strlcpy(const char *pointer)
{
    return pointer != NULL ? (sizeof(char) * strlen(pointer) + sizeof(char)) : 0;
}

char *mstrcpy(char *dest, const char *src)
{
    if (src != NULL)
    {
        if (dest == NULL)
            dest = (char *)calloc(count_for_strlcpy(src), sizeof(char));
        else if (sizeof(dest) != sizeof(src))
            dest = (char *)realloc((void *)dest, count_for_strlcpy(src) * sizeof(char));
        strlcpy(dest, src, count_for_strlcpy(src));
        return dest;
    }
    else
        return (char *)NULL;
}

实际上用到的代码mstrcpy()在init_alias()等效为

char *alias_name_upload = (char *)calloc(count_for_strlcpy(alias_name), sizeof(char));
char *alias_command_upload = (char *)calloc(count_for_strlcpy(alias_command), sizeof(char));
strlcpy(alias_name_upload, alias_name, count_for_strlcpy(alias_name));
strlcpy(alias_command_upload, alias_command, count_for_strlcpy(alias_command));
alias_chain->alias_name = alias_name_upload;
alias_chain->alias_command = alias_command_upload;

链表的插入和删除

插入

head_alias_t upload_alias_node(head_alias_t alias_head, const char *alias_name, const char *alias_command)
{
    if (alias_head->next != NULL)
    {
        alias_t current = alias_head->next;
        while (1)
        {
            if (!strcmp(current->alias_name, alias_name))
            {
                current->alias_command = mstrcpy(current->alias_command, alias_command);
                return alias_head;
            }
            else if (current->next != NULL)
                current = current->next;
            else if (current->next == NULL)
            {
                current->next = init_alias(current->next, alias_name, alias_command);
                return alias_head;
            }
        }
    }
    else
    {
        alias_head->next = init_alias(alias_head->next, alias_name, alias_command);
        return alias_head;
    }
}

依次索引，首先查看alias_head指向的第一个元素是否为空，是的话就alias_head的next指向它，否的话就依次索引查找，如果查找到匹配的就替换，如果查找不到对应的名字就新建一个节点在链表尾部

删除

head_alias_t remove_alias_node(head_alias_t alias_head, const char *alias_name)
{
    alias_t current = alias_head->next, prev = alias_head->next;
    if (current == NULL)
    {
        printf("fshell : unalias : no alias\n");
        return alias_head;
    }
    if (strcmp(current->alias_name, alias_name))
    {
        if (current->next != NULL)
        {
            current = current->next;
            while (1)
            {
                if (!strcmp(current->alias_name, alias_name))
                {
                    prev->next = current->next;
                    free(current->alias_name);
                    free(current->alias_command);
                    free(current);
                    return alias_head;
                }
                else if (current->next != NULL)
                {
                    prev = current;
                    current = current->next;
                }
                else
                    return alias_head;
            }
        }
        else
            return alias_head;
    }
    else
    {
        alias_head->next = current->next;
        return alias_head;
    }
}

和插入一样的索引方法，直到找到匹配的名称free()

深入讲解

void *calloc(size_t nitems, size_t size)函数申请堆内存

nitems – 要被分配的元素个数

size – 元素的大小

void free(void *ptr)函数用于释放堆内存

size_t strlcpy(char *dst, const char *src, size_t size)函数是BSD提供的，在BSD和Linux API均提供，类似于strncpy()但是会在结尾最后一个添加’\0’

Linux ManPage : “The strlcpy() function copies up to size - 1 characters from the NUL-terminated string src to dst, NUL-terminating the result.”