数据结构 ——— C语言实现动态顺序表
目录
顺序表的概念
顺序表的结构（静态顺序表和动态顺序表）
1. 静态顺序表：使用固定长度的数组存储元素
2. 动态顺序表：使用动态开辟的数组存储元素
为什么选择实现动态顺序表
静态顺序表的缺点：
动态顺序表的优点：
实现动态顺序表的准备工作
实现动态顺序表
1. 初始化动态顺序表
2. 释放动态顺序表
3. 打印动态顺序表的有效数据
4. 扩容
4. 在顺序表的尾部插入数据
5. 在顺序表的尾部删除数据
6. 在顺序表头部插入数据
7. 在顺序表头部删除数据
8. 在顺序表中间位置插入数据
9. 查找顺序表中的指定数据
10. 在顺序表中间位置删除数据
11. 在顺序表中修改指定的数据
顺序表的概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，顺序表的本质就是数组，所以一般情况下采用数组存储，在数组上完成数据的增删查改
顺序表的结构（静态顺序表和动态顺序表）
1. 静态顺序表：使用固定长度的数组存储元素
静态顺序表结构代码演示：
#define N 10
// 数据的类型
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N]; //固定长度的数组
size_t size; //有效数据的个数
}SeqList;2. 动态顺序表：使用动态开辟的数组存储元素
动态顺序表结构代码演示：
// 数据的类型
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* array; //指向动态开辟的数组的指针
size_t size; //有效数据个数
size_t capicity; //空间容量大小
}SeqList;为什么选择实现动态顺序表
静态顺序表的缺点：
空间大小是固定的，当有效数据 等于 数组的最大容量的时候就不能存储数据了
且存储的数据个数是未知的，所以数组空间的大小太小了不够用，但是太大了又浪费
动态顺序表的优点：
当当前有效数据 等于 数组最大容量的时候可以使用 malloc 扩容，不用担心数组会存储不了数据
实现动态顺序表的准备工作
创建3个文件
test.c 文件：用来测试增删查改功能是否完善
SeqList.h 文件：用来声明动态顺序表的结构以及声明增删查改函数
SeqList.c 文件：用来实现动态顺序表的增删查改及功能函数
实现动态顺序表
1. 初始化动态顺序表
void SLInit(SeqList* psl)
{
// 动态开辟 4 个 SLDataType 类型的空间
psl->array = (SLDataType*)malloc(sizeof(SLDataType) * 4);
// 判断是否开辟成功
if (psl->array == NULL)
{
perror("malloc fail");
return;
}
psl->capicity = 4;
psl->size = 0;
}SLDataType 是 typedef 而来的：
typedef int SLDataType;是用来定义数组元素的类型，这样做的好处是只需要修改这一处，就能改变整个数组的类型
测试代码：
2. 释放动态顺序表
void SLDestroy(SeqList* psl)
{
// 释放动态开辟的空间
free(psl->array);
// 置空和置零
psl->array = NULL;
psl->capicity = 0;
psl->size = 0;
}测试代码：
3. 打印动态顺序表的有效数据
void SLPrint(SeqList* psl)
{
// 当前动态数组中没有存储有效数据时
if (psl->size == 0)
{
printf("无有效数据\n");
return;
}
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->array[i]);
}
printf("\n");
}打印数据会出现两种情况，有数据和无数据：
无数据时：可以提醒用户当前动态数组中没有有效数据
有数据时：直接从 0 遍历到 size 当作下标再打印即可
4. 扩容
void BuyCapicity(SeqList* psl)
{
if (psl->capicity == psl->size)
{
// 利用三目操作符，防止用户不使用初始化函数，直接扩容的情况
psl->capicity = (psl->capicity == 0) ? 4 : psl->capicity * 2;
SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * psl->capicity);
// 判断是否扩容成功
if (tmp == NULL)
{
perror("realloc fail");
return;
}
// 确定扩容成功再赋值
psl->array = tmp;
printf("成功扩容，当前容量：%d\n", psl->capicity);
}
else
{
return;
}
}扩容时，先不要使用 pls->array 原指针进行扩容，要先创建一个临时指针，扩容成功后再赋值给原指针接管，这样做的好处是以免 realloc 函数扩容失败，扩容失败就会返回 NULL，当 pls->array 赋值为 NULL，那么就查看不到之前的有效数据
4. 在顺序表的尾部插入数据
void SLPushBack(SeqList* psl, SLDataType x)
{
// 尾插前先判断是否需要扩容
BuyCapicity(psl);
psl->array[psl->size] = x;
psl->size++;
}当前有效数据个数 psl->size 就是要尾插数据的下标
测试代码：
5. 在顺序表的尾部删除数据
void SLPopBack(SeqList* psl)
{
// 当前没有有效数据或者有效数据以被删完时
if (psl->size == 0)
{
printf("无数据可删除\n");
return;
}
psl->size--;
}直接把 psl->size 递减 1 即可
测试代码：
6. 在顺序表头部插入数据
void SLPushFront(SeqList* psl, SLDataType x)
{
// 头插前先判断是否需要扩容
BuyCapicity(psl);
// 当前有效数据整体向后挪动一个元素
for (int i = psl->size; i > 0; i--)
{
psl->array[i] = psl->array[i - 1];
}
psl->array[0] = x;
psl->size++;
}测试代码：
7. 在顺序表头部删除数据
void SLPopFront(SeqList* psl)
{
// 当前没有有效数据或者有效数据以被删完时
if (psl->size == 0)
{
printf("无数据可删除\n");
return;
}
// 从第二个元素开始，依次向前覆盖
for (int i = 0; i < psl->size - 1; i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->size--;
} 测试代码：
8. 在顺序表中间位置插入数据
void SLInsert(SeqList* psl, int pos, SLDataType x)
{
// 中插前先判断是否需要扩容
BuyCapicity(psl);
// 判断 pos 的合法性
if (pos < 1 || pos > psl->size)
{
printf("非法插入\n");
return;
}
// 从pos位置往后的有效元素整体向后挪动
for (size_t i = psl->size; i > pos - 1; i--)
{
psl->array[i] = psl->array[i - 1];
}
psl->array[pos - 1] = x;
psl->size++;
}我是以用户的角度设计的， pos 位置是元素个数位置，大家可以自行设计不同的 pos 位置，可以设计成 pos 位置是元素下标的位置
测试代码：
9. 查找顺序表中的指定数据
int SLFind(SeqList* psl, SLDataType x)
{
for (int i = 0; i < psl->size; i++)
{
if (psl->array[i] == x)
{
// 找到了返回下标
return i;
}
}
return -1;
}找到了指定的元素就返回元素的下标，没有找到就返回 -1 ，因为下标可不能是 -1
10. 在顺序表中间位置删除数据
void SLErase(SeqList* psl, SLDataType x)
{
int ret = SLFind(psl, x);
// 判断是否找到指定元素
if (ret != -1)
{
// 向前覆盖
for (int i = ret; i < psl->size - 1; i++)
{
psl->array[i] = psl->array[i + 1];
}
psl->size--;
}
else
{
printf("没有找到指定元素\n");
}
}配合 SLFind 函数使用，先使用 SLFind 函数找到要删除的值，并通过 SLFind 返回的下标判断并删除
测试代码：
11. 在顺序表中修改指定的数据
void SLModity(SeqList* psl, SLDataType x, SLDataType input)
{
int ret = SLFind(psl, x);
// 判断是否找到指定元素
if (ret != -1)
{
psl->array[ret] = input;
}
else
{
printf("没有找到指定元素\n");
}
}x 为顺序表中要修改的有效数据，input 是修改的值
测试代码：