线性表顺序表示-C语言实现

线性表是最常用且最简单的一种数据结构。简而言之，一个线性表是 n 个数据元素的有限序列。
线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

线性表顺序表示 数据结构有3个字段：存储数据、存储数量、存储容量。这里的存储数据 存的是线性表总数据的集合

const int INITCAP = 4;    // 初始 分配 容量
const int INCEWMENT = 2;  // 扩容新增 倍数

// 顺序表的实现
typedef int sequenceListType;
typedef struct sequenceList
{
    sequenceListType * elem;        // 存储数据：这里存的是数组
    int size;       // 存储数量
    int capacity;   // 存储容量
} seqList ;

给 seqList 初始分配存储空间、存储数量与存储容量

// 初始化
void sequenceListInit(seqList *L)
{
    // 检测指针是否可用
    // 1.assert将通过检查表达式expresion的值来决定是否需要终止执行程序。
    // 2、如果表达式expresion的值是假的(即0)，它将首先向标准错误流stderr打印错误信息。通过调用abort函数终止程序运行。否则，assert没有效果
    assert(L);
    L->elem = malloc(sizeof(sequenceListType) * INITCAP);
    L->size = 0;
    L->capacity = INITCAP;
}

这里介绍的是动态的顺序表，存储达到容量上限就扩容存储。静态的没有扩容操作，容量达到上限就不允许再存储数据了

// 容量不足 扩容
void sequenceListInsertCap(seqList *L)
{
    assert(L);
    if (L->capacity == L->size * sizeof(sequenceListType))
    {
        size_t newCap = L->capacity * INCEWMENT;
        sequenceListType *tmp = realloc(L->elem, sizeof(sequenceListType) * newCap);
        if (tmp == NULL)
        {
            // 新增分配空间失败,直接终止程序
            printf("CheckCapacity::%sn", strerror(errno)); //若空间开辟失败，则打印开辟失败的原因
            exit(-1);
        }
        else
        {
            L->elem = tmp;
            L->capacity = newCap;
        }
    }
}

插入分三种情况，头插入（pos = 0）、尾插入（pos = L->size）、其他中间位置插入。其中 尾插入 不需要移动数据，其他两种插入需要把 pos 位置及其后面的数据 向后移动一个位置，再插入

// 插入数据: pos 是下标
void sequenceListInsertElem(seqList *L, int pos, sequenceListType elem)
{
    assert(L);
    if (pos < 0 || pos > L->size)
    {
        printf("seqList 顺序表当前个数 %d, 插入位置 %d 错误。（插入位置必须在原顺序表内） n", L->size, pos);
        return;
    }

    // 检测是否要扩容
    sequenceListInsertCap(L);

    // pos 与 后面所有数据 后移一位
    for (int i = L->size; i > pos; i--)
    {
        L->elem[i] = L->elem[i - 1];
    }
    //插入数据
    L->elem[pos] = elem;
    L->size++;
}

删除数据一样 3种删除位置：pos = 0、pos = L->size - 1、其他中间位置。pos = L->size - 1 这种删除不需要处理数据，其他方式需要把 pos 位置后面的数据向前移动一个位置。这里与上面插入的判断区别，插入可以 向 L->size 位置插入，删除的最大下标是 L->size - 1

// 删除数据：pos 是下标
void sequenceListDeleteElem(seqList *L, int pos)
{
    assert(L);
    // 这里 L->size 这个元素 不存在，不能删除
    if (pos < 0 || pos >= L->size)
    {
        printf("seqList 顺序表当前个数 %d, 删除位置 %d 错误。（删除位置必须在原顺序表内） n", L->size, pos);
        return;
    }

    // pos 之后的数据 全部前移一位， 删除最后一位 不需要 移数据
    for (int i = pos; i < L->size - 1; i++)
    {
        L->elem[i] = L->elem[i + 1];
    }

    L->size--;
}

for 循环 L->size 次数，获取第一个与 elem 相等的元素，返回其下标，没找到就返回 -1

// 查找数据，返回下标，不存在 返回 -1
int sequenceListSearchElem(seqList *L, sequenceListType elem)
{
    if (L->size == 0)
    {
        return -1;
    }
    for (int i = 0; i < L->size; i++)
    {
        if (L->elem[i] == elem)
        {
            return i;
        }
    }

    return -1;
}

for 循环 L->size 次数，逐个打印数据

// 打印顺序链表
void sequenceListPrint(seqList *L)
{
    assert(L);
    if (L->size == 0)
    {
        printf("该顺序表为空 n");
    }
    else
    {
        for (int i = 0; i < L->size; i++)
        {
            printf("%d ", L->elem[i]);
        }
        printf("n");
    }
}

释放 L->elem 的空间 并赋值 NULL，存储容量与存储数据量置0

// 摧毁顺序表
void sequenceListDestroy(seqList *L)
{
    assert(L);
    free(L->elem);
    L->elem = NULL;
    L->size = L->capacity = 0;
}

加 srand(time(NULL)); 可以保证每次获取的一组数据 不一致

// 获取 范围内的一组随机数
int * getRandNumList(int num, int min, int max)
{
    int * list;
    list = malloc(sizeof(int) * num);
    srand(time(NULL));
    for (int i = 0; i < num; i++)
    {
        list[i] = getRandNum(min, max);
    }
    
    return list;
}

这里初始化 顺序表没用 sequenceListInit 方法，而是手动初始化的。
这里要说明下，seqList * L 表示的是 L 存储的是 地址信息，因此初始化是 先要声明一个 seqList l; 再把其地址赋值给指针 L。之后才是对 L 的各元素进行赋值

int main(){
    int num = 15;
    int * list = getRandNumList(num, 0, 10);
    //输出列表
    printf("随机数列表：");
    for (int i = 0; i < num; i++)
    {
        printf("%d ", list[i]);
    }
    printf("n");
    
    // 初始化 顺序表
    seqList l;
    seqList * L = &l;
    // sequenceListInit(L);
    L->elem = malloc(sizeof(sequenceListType) * num);
    for (int i = 0; i < num; i++)
    {
        L->elem[i] = list[i];
    }

    L->size = num;
    L->capacity = sizeof(int) * num;

    printf("初始化顺序表：");
    sequenceListPrint(L);
    printf("size: %d, cap: %d n", L->size, L->capacity);

    // 插入元素
    sequenceListInsertElem(L, 5, 88);
    printf("插入元素");
    sequenceListPrint(L);
    printf("size: %d, cap: %d n", L->size, L->capacity);

    // 删除元素
    sequenceListDeleteElem(L, 5);
    printf("删除元素");
    sequenceListPrint(L);
    printf("size: %d, cap: %d n", L->size, L->capacity);

    // 查找元素
    sequenceListType searchNum = 5;
    int index = sequenceListSearchElem(L, searchNum);
    printf("查找元素【%d】的下标是: %d n", searchNum, index);

    // 摧毁顺序表
    sequenceListDestroy(L);
    printf("size: %d, cap: %d n", L->size, L->capacity);

}

数据结构 是存储在 dataStructlinearList 目录下，
随机数获取方法是存储在 test 目录下，
main.c 存储在根目录下。
除了 main.c 外，每个 .c 文件都有个 同名的 .h 文件，在 main.c 文件引用的都是 .h 文件。如下：

#include “dataStructlinearListlinearList.h”
#include “test/test.h”

gcc .main.c .dataStructlinearList* .test* -o .cmdtest.exe
cmdtest.exe

结果如下