C语言线性表

/*
线性表一般需要包含以下功能：

● 初始化线性表：将一个线性表进行初始化，得到一个全新的线性表。
● 获取指定位置上的元素：直接获取线性表指定位置i上的元素。
● 获取元素的位置：获取某个元素在线性表上的位置i。
● 插入元素：在指定位置i上插入一个元素。
● 删除元素：删除指定位置i上的一个元素。
● 获取长度：返回线性表的长度。

 */
/* 顺序表 */
#include <stdio.h>
#include <stdlib.h>
typedef int E;
typedef struct List List;
struct List
{
    E *array;   // 实现顺序表的底层数组 指向顺序表的底层数组
    E capacity; // 表示底层数组的容量
    E size;     // 表中的元素数量
};
typedef struct List *ArrayList; // 因为是数组实现，所以就叫ArrayList，这里直接将List的指针起别名
_Bool initList(ArrayList list)
{
    list->array = malloc(sizeof(E) * 10); // 使用malloc函数申请10个int大小的内存空间，作为底层数组使用
    if (list->array == NULL)
        return 0;        // 需要判断如果申请的结果为NULL的话，表示内存空间申请失败
    list->capacity = 10; // 直接把数组的容量设置为10即可
    list->size = 0;      // 元素数量默认为0
    return 1;            // 正常情况下返回true也就是1
}
/*
但是我们发现一个问题，这样的话我们的顺序表长度不就是固定为10的了吗？
而前面我们线性表要求的是长度是动态增长的，那么这个时候怎么办呢？
我们可以直接使用一个指针来指向底层数组的内存区域，
当装不下的时候，我们可以创建一个新的更大的内存空间来存放数据，
这样就可以实现扩容了，所以我们来修改一下：
 */
// 这样，一个比较简单的顺序表就定义好，我们可以通过initList函数对其进行初始化：
// 接着我们来编写一下插入和删除操作
_Bool insertList(ArrayList list, E element, E index)
{
    // 转换成位序，也就是[1, size + 1]这个闭区间，所以我们在一开始的时候进行判断
    if (index < 1 || index > list->size + 1)
    {
        return 0; // 如果在非法位置插入，返回0表示插入操作执行失败
    }
    // list就是待操作的表，element就是需要插入的元素，
    // index就是插入的位置（注意顺序表的index是按位序计算的，从1开始，一般都是第index个元素）

    /*

    不过我们还是没有考虑到一个情况，那么就是如果我们的表已经装满了，
    也就是说size已经达到申请的内存空间最大的大小了，那么此时我们就需要考虑进行扩容了，否则就没办法插入新的元素了：
     */
    if (list->size >= list->capacity)
    {
        E newCapacity = list->capacity + (list->capacity >> 1);      // 如果size已经到达最大的容量了，肯定是插不进了，那么此时就需要扩容了
        E *newArray = realloc(list->array, sizeof(E) * newCapacity); // 我们先计算一下新的容量大小，这里我取1.5倍原长度，当然你们也可以想扩多少扩多少
        // 这里我们使用新的函数realloc重新申请更大的内存空间
        if (newArray == NULL)
            return 0; // 如果申请失败，那么就确实没办法插入了，只能返回0表示插入失败了
        list->array = newArray;
        list->capacity = newCapacity;
    }

    for (int i = list->size; i > index - 1; i--)
    {
        list->array[i] = list->array[i - 1]; ////先使用for循环将待插入位置后续的元素全部丢到后一位
    }
    list->array[index - 1] = element; // 挪完之后，位置就腾出来了，直接设定即可
    list->size++;                     // 插入之后相当于多了一个元素，记得size + 1
    return 1;                         // 正常情况return 1
}
void printList(ArrayList list)
{
    for (E i = 0; i < list->size; i++)
    {
        printf("%d ", list->array[i]);
    }
    printf("\n");
}
_Bool deleteList(ArrayList list, E index)
{
    // list就是待操作的表，index是要删除的元素位序
    if (index < 1 || index > list->size)
        return 0;
    for (int i = index - 1; i < list->size; i++)
    {
        list->array[i] = list->array[i + 1];
    }
    list->size--;
    return 1; // 正常情况返回1
}
E sizeList(ArrayList list)
{
    return list->size;
}
E getList(ArrayList list, E index)
{
    if (index < 1 || index > list->size)
        return NULL; // 如果超出范围返回NULL
    return list->array[index - 1];
}
E findList(ArrayList list, E element)
{
    for (E i = 0; i < list->size; ++i)
    {
        if (list->array[i] == element)
            return i + 1;
    }
    return -1;
}
E main(void)
{
    List list;           // 创建新的结构体变量
    if (initList(&list)) // 对其进行初始化，如果失败就直接结束
    {
        for (E i = 1; i <= 30; ++i)
            insertList(&list, i, i);
        printList(&list);
        printf("\n");
        printf("%d\n", getList(&list, 23));
    }
    else
    {
        printf("顺序表初始化失败，无法启动程序！");
    }
}