列表（list）是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。
- 链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。
- 数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。
当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要存储多少数据，从而难以选择合适的列表长度。若长度过小，则很可能无法满足使用需求；若长度过大，则会造成内存空间浪费。
为解决此问题，我们可以使用动态数组（dynamic array）来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。
但是在C语言中,没有提供内置的动态数组,所以需要依靠数组来实现
列表的实现
在C语言中,可以通过构建一个结构体来完成列表的创建
typedef struct
{
int capacity; // 列表容量
int size; // 列表大小
int *arr;
} SequeueList;
在这段代码中,构建了一个创造了一个别名为SequeueList的匿名结构体的新类型,内部元素capacity用来表示列表容量,size表示列表大小,指针arr用来存放列表数据
通过构建结构体的方式做到列表的统一管理,将不具有关联性的元素相互关联在一起,方便了数据的管理和代码的可读性
制作一个构造函数用来初始化一个顺序表结构体
SequeueList *newSequeueList(int capacity)
{
SequeueList *s = malloc(sizeof(SequeueList));
s->capacity = capacity; // 数组最大容量
s->size = 0; // 表示数组中已经存放了多少数据
s->arr = malloc(sizeof(int) * s->capacity);
return s;
}在上面的函数体内,创建了一个SequenceList类型的指针变量s指向一个大小为结构体大小的堆空间, 将接受的参数capacity赋值给解引用的s结构体内的capacity变量作为数组的最大容量.解引用的s结构体内的size变量大小赋值为0,表示数组中存放数据的数量,最后给解引用的s结构体内的数组arr创造一个int类型的堆空间,大小为传入参数capacity的大小.最后返回这个结构体s,至此,完成顺序表的初始化.
列表增删改查的判断(异常判断)
通过构建一个is_full函数用来判断列表是否填满.如果填满,返回1,没有填满,继续操作
int is_full(SequeueList *s)
{
if (s->size == s->capacity) //数组的大小等于数组的容量 表示已经填满数组
{
printf("列表已满无法添加 \n");
return 1;
}
return 0;
}构建一个is_empty函数, 判断列表是否为空,如果列表为空,返回1,提示无法做删除操作
int is_empty(SequeueList *s)
{
if (s->size == 0)
{
printf("列表为空无法删除 \n");
return 1;
}
return 0;
}列表数据的插入(增)
构建一个insert_list函数用来做列表的插入方法
int insert_list(SequeueList *s, int data, int index)
{
if (is_full(s))
{
return -1;
}
if (index > s->size)
{
printf("插入范围异常 \n");
return -1;
}
// 移动
// 把所有元素向后移动
for (int i = s->size - 1; i >= index; i--)
{
s->arr[i + 1] = s->arr[i];
}
s->arr[index] = data;
s->size++;
return data;
}在这个函数中,通过传入SequenceList类型的列表s,int类型的插入数据data,int类型的插入位置index的参数完成数据插入顺序列表的任意位置
首先进行两次异常判断,如果列表已满或者传入的index参数大于数组大小,返回-1,结束操作
没有异常的情况下,通过一个for循环,把列表中的数据依次向后移动,为新插入的数据data留出下标位置,向下标位置写入数据后更新size的大小,调整数组下标,返回data表示数据插入成功
逻辑：从最后一个元素开始（索引 size-1）向后移动到目标位置（索引 index）
方向：从后向前移动，避免覆盖未处理的元素
如果 size = 5 , 要在index = 2 处插入数据 可以有:
原始：arr[0] arr[1] arr[2] arr[3] arr[4]
移动：将 arr[4]→arr[5], arr[3]→arr[4], arr[2]→arr[3]
具备可以任意插入的列表函数后,可以拓展出列表的头插(add_head)和尾插(add_tail)两种特殊方法
int add_tail(SequeueList *s, int data)
{
return insert_list(s, data, s->size); //每次向列表末尾插入数据
}
int add_head(SequeueList *s, int data)
{
return insert_list(s, data, 0); //每次向列表开头插入数据
}列表的删减
构建一个remove_list函数用来做列表的删除方法
int remove_list(SequeueList *s, int index)
{
if (is_empty(s))
{
return -1;
}
if (index > s->size - 1 || index < 0)
{
printf("删除下标异常 \n");
return -1;
}
// 移动元素
for (int i = index + 1; i < s->size; i++)
{
s->arr[i - 1] = s->arr[i];
}
s->size--;
return index;
}在这个函数中，通过传入传入SequenceList类型的列表s,int类型的插入位置index的参数完成数据删除顺序列表的任意位置
首先进行两次异常判断，如果列表为空或者下标志小于0，那么返回-1，不进行删除操作
没有异常的情况下,通过一个for循环,把列表中的数据依次向前移动,然后更新size的大小,调整数组下标,返回index表示数据删除成功
逻辑：从目标位置开始（索引 index+1）向前移动（索引 index）直到末尾移动结束
方向：从后向前移动，避免覆盖未处理的元素
如果 size = 5 , 要在index = 2 处删除数据 可以有:
原始：arr[0] arr[1] arr[2] arr[3] arr[4]
移动：将 arr[3]→arr[2], arr[4]→arr[3]
具备可以任意删除的列表函数后,可以拓展出列表的头删(remove_head)和尾插删(remove_tail)两种特殊方法
int remove_head(SequeueList *s)
{
return remove_list(s, 0);
}
int remove_tail(SequeueList *s)
{
return remove_list(s, s->size - 1);
}列表的销毁
当列表不需要时，需要将列表中的每一个元素删除并释放其所占用的内存
定义一个destory_list方法用来销毁列表
在顺序列表中，需要先释放掉SequeueLise类型的指针变量解引用s内的arr数组，然后在释放掉s所占用的堆内存空间
void destor_list(SequeueList *s)
{
free(s->arr); // 先释放内部数组
free(s); // 释放s
}实际使用中，对于main函数中的列表list也需要释放，引用destory_list函数后仍需要释放主函数中定义的指针变量，并且将其指向NULL，防止野指针的产生。
Comments NOTHING