线性表
线性表是数据结构的一种，它是一组具有相同数据类型的数据元素的有限序列。在线性表中，除了第一个和最后一个数据元素之外，每个数据元素均只有一个直接前驱和一个直接后继。线性表的元素个数n（n≥0）定义为线性表的长度，当n=0时，称为空表。
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
线性表的物理存储结构影响其操作的效率，主要分为两种：
顺序存储结构：
链式存储结构：
我们接下来介绍顺序表有关内容
顺序表
介绍顺序表之前，我们谈论一下数组
数组是程序设计中的一种基本数据结构，它是同一数据类型元素的集合，这些元素在内存中按照顺序排列，占据连续的内存空间。数组是静态的数据结构，它的大小在定义时就已确定，并且在整个生命周期中保持不变。数组可以是一维的，也可以是多维的（如二维数组、三维数组等）。
特点：
静态结构：一旦定义，大小不可变。
连续的内存空间。
支持随机访问，即可以通过索引访问任意元素。
大小固定，一旦数组被声明，它的大小就被确定下来，不能动态地增加或减少元素。
那么对于顺序表，通常使用数组作为其底层的物理结构，但它是一个更高级别的抽象。与“裸”数组不同的是，顺序表通常提供了一组用于操作和访问其元素的API接口，如插入、删除、搜索等操作，并且它们的实现细节对使用者是隐藏的。在一些实现中，顺序表还可以动态地调整其大小以适应元素数量的变化，这是通过在后台自动重新分配内存和复制现有元素到一个更大（或更小）的数组来实现的。
数组有给定长度的，也有动态的，顺序表也分为静态和动态
静态顺序表
静态顺序表：使用定长数组存储元素
#define N 7 typedef int SLDataType; typedef struct SeqList { SLDataType arr[N]; size_t size; }SeqList;
在这里，我们设置了一个定长数组arr，size为它的有效数据的个数，这里有效数据的个数是指已经初始化或赋值的部分，同时我们用新的类型别名 SLDataType 来代表 int 类型，这种操作再数据结构中非常常见，主要目的：
类型抽象：通过使用类型别名，可以将数据类型抽象化。这意味着如果将来需要改变数据类型（比如从 int 改为 float 或者某个结构体类型），只需修改 typedef 行的定义，而不用修改整个代码中的多个地方。这提高了代码的可维护性。我们展开讨论：
假设您在一个较大的项目中定义了一个数据类型别名 SLDataType 来代表 int，并在多个函数和数据结构中广泛使用了这个别名。现在，我们来看看如果需要更改这个数据类型，类型别名如何简化这个过程。
typedef float SLDataType; // 修改类型别名
typedef int SLDataType; // 初始类型别名定义 // 使用SLDataType的函数 void processElement(SLDataType element) { // ... 处理逻辑 ... } // 使用SLDataType的数据结构 typedef struct { SLDataType array[10]; int size; } DataArray;
在这个初始代码中，SLDataType 被用于函数 processElement 和结构体 DataArray。
更改数据类型
现在，假设您决定将 SLDataType 从 int 更改为 float。这种情况下，您只需修改 typedef 行：
typedef float SLDataType; // 修改类型别名
由于 SLDataType 被用于整个项目中，这一改变会自动应用于所有使用了 SLDataType 的地方。这意味着您不需要逐个查找和替换每个 int 类型的实例。processElement 函数和 DataArray 结构体现在都会使用 float 而不是 int，而且不需要对它们的代码进行任何修改
动态顺序表
动态顺序表是线性表顺序存储方式的一种动态实现，它能够根据需要动态调整内存空间的大小，从而适应元素数量的变化
typedef struct SeqList { SLDataType *array; size_t size; size_t capacity; }SL;
这里size为有效数据的大小，capacity为空间容量，后续的增容与此变量息息相关
这里我们构建一个头文件（seq.h），包含所要调用所有顺序表函数的信息：
typedef struct SeqList { SLDataType* a; int size; // 有效数据个数 int capacity; // 空间容量 }SL; //初始化和销毁 void SLInit(SL* ps); void SLDestroy(SL* ps); void SLPrint(SL* ps); //扩容 void SLCheckCapacity(SL* ps); //头部插⼊删除 / 尾部插⼊删除 void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); void SLPushFront(SL* ps, SLDataType x); void SLPopFront(SL* ps); //指定位置之前插⼊/删除数据 void SLInsert(SL* ps, int pos, SLDataType x); void SLErase(SL* ps, int pos); int SLFind(SL* ps, SLDataType x);
接下来我们逐个讲解
顺序表的初始化与销毁
思考下面这种方式能不能进行初始化？
void SLInit(SL ps)
这串代码并不能改变原来所创建的ps，这里是传值调用，为了使这种修改有效，需要通过指针传递SL结构。这样，SLInit将获取一个指向SL结构实例的指针，使其能够修改原始实例的内容。
修改如下：
1. void SLInit(SL*ps) 2. { 3. ps->array = NULL; 4. ps->size = 0; 5. ps->capacity = 0; 6. }
这里若ps为空指针，则可能发生未定义行为，我们在开始进行判断
1. void SLInit(SL* ps) 2. { 3. if (ps == NULL) { // 检查 ps 是否为 NULL 4. // 可以打印错误信息，直接返回或者采取其他措施 5. fprintf(stderr, "Error: NULL pointer passed to SLInit.\n"); 6. return; 7. } 8. 9. ps->array = NULL; 10. ps->size = 0; 11. ps->capacity = 0; 12. }
在头文件中我们进行声明，在SeqList.c中完成函数的功能，在test.c文件中进行测试代码。
销毁
1. void SLDestroy(SL* ps) 2. { 3. if (ps->array != NULL) 4. { 5. free(ps->array); 6. ps->array = NULL; 7. ps->size = 0; 8. ps->capacity = 0; 9. } 10. }
free(ps->array);这行代码的作用是释放顺序表（SeqList）中动态分配的数组内存。当ps->array不为NULL时，表示array指向了一块之前分配的内存，使用free来释放这块内存
顺序表头部尾部的插入与删除
这里我们定义四组函数，分别表示顺序表尾部的插入与删除，头部的插入与删除
void SLPushBack(SL* ps, SLDataType x);//尾插 void SLPopBack(SL* ps);//尾删 void SLPushFront(SL* ps, SLDataType x);//头插 void SLPopFront(SL* ps);//头删
首先来讨论尾部插入，这里有几种情况，即尾部有没有空间插入？
ps->arr[ps->size++]=6;
如果空间足够，直接在尾部放入数据即可。
比如插入数据“6”
ps->arr[ps->size++]=6;
如果size和capacity相等了，说明满了，如果再存储则会越界；这里就需要扩容
if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity; SLDataType* tmp = realloc(ps->array, sizeof(SLDataType) * newcapacity); }
由于初始化的时候我们将capacity的值赋值为0，这里进行新的capacity扩容的时候就用三目运算符，如果为0，赋予值为4，如果不为零，给其2倍扩容。
realloc进行扩容，判断是否开辟成功
if (tmp==NULL) { perror("realloc fail"); return; }
如果开辟成功，将新开辟的空间的地址给arr数组
ps->array = tmp;
完整的扩容代码如下：
if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity; SLDataType* tmp = (SLDataType*) realloc(ps->array, sizeof(SLDataType) * newcapacity); if (tmp==NULL) { perror("realloc fail"); return; } ps->array = tmp; ps->capacity = newcapacity; }
我们将这串代码放在SLCheckcapacity中
我们在测试文件中进行测试
调试如下
结果打印
接下来看头部插入
直接调用SLCheckcapacity检查空间是否足够
void SLPushFront(SL* ps, SLDataType x) { SLCheckcapacity(ps); }
头部插入，我们需要将数据往后挪动
void SLPushFront(SL* ps, SLDataType x) { SLCheckcapacity(ps); int end =ps-> size; while (end >= 0) { ps->array[end + 1] = ps->array[end]; end--; } ps->array[0] = x; ps->size++; }
最后让size指向下一个位置
示例如下：
接下来我们讨论尾部删除
尾删如何删除呢？
这里我们需要讨论是否有数据去删除
代码如下：
void SLPopBack(SL* ps) { if (ps->size == 0) { printf("The SeqList is empty, no elements to remove.\n"); } else { ps->size--; } }
顺序表的size属性标志着其中有效元素的数量。当我们进行size- -操作时，我们实际上是在逻辑上减少了顺序表中的元素数量，而不是在物理上从内存中移除该元素。被"删除"的元素在内存中依然存在，只是我们不再将其视为顺序表的一部分。
在多数情况下，顺序表的实现不会立即释放每次删除操作后的内存空间，因为频繁的内存分配和释放操作会影响性能。相反，它保留这些空间以支持未来的添加操作，从而提高了整体的内存使用和管理效率。
我们这里使用if语句可以避免size减为负值，避免后续插入时候缺少数据！！！
头部删除
头部删除，我们可以用数据往前挪动进行数据覆盖
void SLPopFront(SL* ps) { if (ps->size == 0) { printf("The SeqList is empty, no elements to remove.\n"); return; } for (size_t i = 1; i < ps->size; i++) { ps->array[i - 1] = ps->array[i]; } ps->size--; }
指定位置插入和删除
这里定义两个函数，删除或插入指定位置pos的数据
void SLinsert(SL* ps,int pos, SLDataType x);//顺序表在pos位置插入x void SLErase(SL* ps, int pos);//顺序表删除pos位置的值 1 2 关于数据插入，首先判断三件事： ps是否为空指针 pos是否在规定位置 空间是否足够 void SLinsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size); SLCheckcapacity(ps); }
接下来进行数据挪动
1. void SLInsert(SL* ps, int pos, SLDataType x) 2. { 3. assert(ps != NULL); 4. assert(pos >= 0 && pos <= ps->size); 5. 6. SLCheckCapacity(ps); 7. for (int i = ps->size; i > pos; --i) 8. { 9. ps->array[i] = ps->array[i - 1]; 10. } 11. // 在pos位置插入新元素 12. ps->array[pos] = x; 13. 14. ps->size++; 15. }
进行检查
这里进行思考，如果pos等于size是什么结果？
如果pos等于size，size是有效位置长度，在pos位置插入数据，则相当于尾插！
指定位置删除
首先进行判断是否为空指针和指定位置，再进行删除，代码如下
void SLErase(SL* ps, int pos) { assert(ps != NULL); assert(pos >= 0 && pos < ps->size); // 确保pos在有效范围内 // 从pos位置开始，将后面的元素前移 for (size_t i = pos; i < ps->size - 1; i++) { ps->array[i] = ps->array[i + 1]; } // 更新顺序表的大小 ps->size--; }
这里pos就不能等于size！
本节内容到此结束！感谢观看！
