顺序表、链表及其C实现

1.顺序表及其C实现

顺序表是一种数据结构的存储形式，其在内存上申请连续的空间进行数据存储，本文主要介绍如何在C语言中使用顺序表。

通常情况，我们创建结构体进行顺序表管理，结构体中包含数据指针、当前存储数据计数、最大存储计数，若使用泛型顺序表，还需具有数据大小存储计数。

typedef struct _Sqlist
{
    void *data;
    int size;
    int cnt;
    int _data_size;
}Sqlist;

顺序表通常需要包含插入、删除、移除、读取等接口，各接口的函数实现如下：

//创建顺序表，申请内存，返回顺序表结构体指针，泛型顺序表还需额外传入需要存储的数据的尺寸
Sqlist *create_sq(int size_sq, size_t size_data){
    Sqlist* Sq = (Sqlist*)malloc(sizeof(Sqlist));
    if(Sq == NULL){
        printf("顺序表申请时内存申请错误\n");
        return NULL;
    }
    Sq->size = size_sq;
    Sq->cnt = 0;
    Sq->data = calloc(size_sq, size_data);
    Sq->_data_size = size_data;
    return Sq;
}

//向顺序表中插入数据，包含对顺序表存储计数的检查
bool insert_sq(Sqlist* sq, void* data){
    if(sq == NULL) return false;
    if(sq->cnt == sq->size){
        printf("顺序表已满\n");
        return false;
    }
    memcpy(sq->data+sq->cnt, data , sq->_data_size);
    sq->cnt++;
    return true;
}

从顺序表中插入数据
bool remove_sq(Sqlist* sq, int remove_n){
    if(remove_n > sq->cnt) return false;
    if(remove_n < 0) return false;

    for(int i = remove_n; i < sq->cnt; i++){
        memcpy(sq->data+i, sq->data+i+1, sq->_data_size);
    }

    sq->cnt--;
    return true;
}

读取顺序表中的数据
void* read_sq(Sqlist* sq, int n){
    if(n < 0){printf("n必须大于等于0!\n");return NULL;}
    if(n >= sq->cnt){
        printf("所读取的数据范围超出目前存储长度");
        return NULL;
    }

    char *base = sq->data;
    return sq->data + sq->_data_size * n;
}

通过对上述接口的调用，可以实现对顺序表的管理，在项目中使用时，创建对应的头文件，并引用头文件即可，如有需要，请点击顺序表代码下载下载示例头文件与C文件。

2.链表及其C实现

链表采用离散的内存单元来存储数据，并采用某种方式将数据链接起来，链表可以高效地使用碎片化内存。

在C语言中，同样采用结构体进行管理链表，区别在于，链表数据本身就是一个结构体，其包含数据本身，后继节点地址，当后继节点地址为NULL时，则代表当前节点为链表的最后一个节点。

本文同样采用结构体管理链表，并采用联合体创建泛型链表。

//数据联合体
typedef union _data{
    int integer;
    char character;
    float floatnum;
    bool error;
} data_t;
//链表数据类型枚举
typedef enum{
    integer = 1,
    character = 2,
    floatnum = 3
}data_type;
//链表节点结构体
typedef struct _lklist{
    data_t data;
    struct _lklist* next;
    data_type type;
} lklist;

通常情况下，链表的头节点不保存数据，仅用于链表管理，特别注意，链表不具有随机访问的能力，其访问的时间复杂度是O(n)，为获得更快的访问速度，在处理超长链表时，可以考虑使用跳表，在链表节点结构体多保存n个节点之后的节点地址。

链表通常需要具备查找、插入、删除以及销毁等能力，具体这些功能实现可以下载链表源代码获得，文中不在赘述，特别值得一提的是链表的数据的查找，本文中的链表为泛型列表，返回的数据是一个联合体，如果用户需要读取一个int数据时，在每次调用返回值的时候都需要对联合体进行二次访问，本文利用C语言宏的特性实现动态返回值。

//宏封装函数,type可以为int，char，float
#define read_lk(list_ptr, type, int_n) __read_lk(list_ptr, type, int_n).type

其中，__read_lk的源代码为

data_t __read_lk(lklist* list, data_type type, int n){
    data_t result;
    lklist* now = list;
    if(n < 0){
        printf("不可以读取第一个节点之前的数据，已默认读取第一个数据\n");
        if(type != list->type) printf("警告：读取的数据类型与链表的数据类型不匹配！\n");
        return list->data;
    }
    else{
        for(int i = 0; i <= n; i++){
            if(now->next == NULL && i < n){
                printf("警告：目标读取的数据超出链表长度，已默认返回最后一个节点的数据\n");
                if(type != list->type) printf("警告：读取的数据类型与链表的数据类型不匹配！\n");
                return now->data;
            }
            else if (now->next == NULL && i == n) {
                if(type != list->type) printf("警告：读取的数据类型与链表的数据类型不匹配！\n");
                return now->data;
            }
            now = now->next;
        }
        return now->data;
    }
};

在调用宏的时候，由于联合体的命名与枚举一致，由于宏文本替换的特性，在函数部分其会被识别作为enum，在点后面会被识别作为联合体的元素访问，由此可以实现对不同类型的元素的输出而不必重载函数（C语言也不具备重载函数的特性）。