🐱作者：傻响
🐱专栏：《数据结构与算法 - 顺序表》
🔥格言：你只管努力，剩下的交给时间！
目录
顺序表
3.1 概念及结构
顺序表是指用一组地址连续的内存单元依次存储线性表的数据元素
通常都用数组来描述数据结构中的顺序存储结构。由于线性表的长度可变，且所需最大存储空间随问题不同而不同，则在C语言中可用动态内存分配一维数组，如下描述：
3.2 静态顺序表定义数据结构
// 顺序表数据结构 - 静态版本
#define N 10
typedef int SSQLType;
typedef struct SSeqList
{
SSQLType data[N]; // 数据存储区。
size_t size; // 当前数据去有效数据个数。
}SSeqList;
// 静态顺序表 - 初始化
void SSeqListInit(SSeqList* pSSQ);
// 静态顺序表 - 头插入
void SSeqListPushFront(SSeqList* pSSQ, SSQLType data);
// 静态顺序表 - 尾插入
void SSeqListPushBack(SSeqList* pSSQ, SSQLType data);
// 静态顺序表 - 头删除
void SSeqListPopFront(SSeqList* pSSQ);
// 静态顺序表 - 尾删除
void SSeqListPopBack(SSeqList* pSSQ);
// 动态顺序表 - 在pos位置插入
void SeqListInsert(SeqList* pSQ, size_t pos, SQLType data);
// 动态顺序表 - 在pos位置删除
void SeqListErase(SeqList* pSQ, size_t pos);
// 静态顺序表 - 打印
void SSeqListPrint(SSeqList* pSSQ);
// 静态顺序表 - 查找 - 返回下标
int SSeqListFind(SSeqList* pSSQ, SSQLType data);
// 静态顺序表 - 修改
void SSeqListModifi(SSeqList* pSSQ, size_t pos, SSQLType data);
// 静态顺序表 - 检测 - 满了返回false - 没满返回true
bool SSeqListCheck(SSeqList* pSSQ);
// 静态顺序表 - 检测是否存在数据个数 - 有数据返回false - 没有数据返回true。
bool SSeqListEmpty(SSeqList* pSSQ);
// 静态顺序表 - 获取有效数据个数
bool SSeqListGetSize(SSeqList* pSSQ);3.3 静态顺序表初始化函数
// 静态顺序表初始化函数实现
void SSeqListInit(SSeqList* pSSQ)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
memset(pSSQ->data, 0, sizeof(pSSQ->data));
pSSQ->size = 0;
}3.4 静态顺序表头插入
// 静态顺序表 - 头插入
void SSeqListPushFront(SSeqList* pSSQ, SSQLType data)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
// 判断存储空间大小
if (!SSeqListCheck(pSSQ))
{
printf("SSeqList Full!\n");
return;
}
// 移动数据
size_t end = pSSQ->size;
while (end > 0)
{
pSSQ->data[end] = pSSQ->data[end - 1];
end--;
}
// 数据插入头部
pSSQ->data[0] = data;
pSSQ->size++;
}3.5 静态顺序表尾插入
// 静态顺序表 - 尾插入
void SSeqListPushBack(SSeqList* pSSQ, SSQLType data)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
// 判断存储空间大小
if (!SSeqListCheck(pSSQ))
{
printf("SSeqList Full!\n");
return;
}
// 程序走到这里说明数组中的数据没有满！
pSSQ->data[pSSQ->size++] = data;
}3.6 静态顺序表头删除
// 静态顺序表 - 头删除
void SSeqListPopFront(SSeqList* pSSQ)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
// 判断顺序表中是否还有有效的数据
if (!SSeqListEmpty(pSSQ))
{
printf("SSeqList Empty!\n");
return;
}
// 移动数据
int begin = 0;
while(begin < pSSQ->size - 1)
{
pSSQ->data[begin] = pSSQ->data[begin + 1];
begin++;
}
pSSQ->size--;
}3.7 静态顺序表尾删除
// 静态顺序表 - 尾删除
void SSeqListPopBack(SSeqList* pSSQ)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
// 判断顺序表中是否还有有效的数据
if (!SSeqListEmpty(pSSQ))
{
printf("SSeqList Empty!\n");
return;
}
// 程序走到这里说明数组中还有有效数据
pSSQ->size--;
}3.8 静态顺序表在pos位置插入
// 动态顺序表 - 在pos位置插入
void SSeqListInsert(SSeqList* pSSQ, size_t pos, SQLType data)
{
// 断言保护形参指针变量不为NULL
assert(pSSQ);
// 判断存储空间大小
if (!SSeqListCheck(pSSQ))
{
printf("SSeqList Full!\n");
return;
}
// 移动数据
int end = SSeqListGetSize(pSSQ) + 1;
while (end > pos)
{
pSSQ->data[end] = pSSQ->data[end - 1];
end--;
}
pSSQ->data[pos] = data;
pSSQ->size++;
}3.9 静态顺序表在pos位置删除
// 动态顺序表 - 在pos位置删除
void SSeqListErase(SSeqList* pSSQ, size_t pos)
{
// 断言保护形参指针变量不为NULL
assert(pSSQ);
// 判断动态顺序表中是否还有数据
if (!SSeqListEmpty(pSSQ))
{
printf("SeqList Empty!");
return;
}
size_t begin = pos;
while (begin < pSSQ->size)
{
pSSQ->data[begin] = pSSQ->data[begin + 1];
begin++;
}
--pSSQ->size;
}
3.10 静态顺序表打印
// 静态顺序表 - 打印
void SSeqListPrint(SSeqList* pSSQ)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
for (int i = 0; i < pSSQ->size; i++)
{
printf("%d\t",pSSQ->data[i]);
}
printf("\n");
}3.11 静态顺序表查找返回下标
// 静态顺序表 - 查找 - 返回下标
int SSeqListFind(SSeqList* pSSQ, SSQLType data)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
// 判断顺序表中是否还有有效的数据
if (!SSeqListEmpty(pSSQ))
{
printf("SSeqList Empty!\n");
return -1;
}
// 程序走到这里说明数组中有元素，找到下表并且返回
for (int i = 0; i < pSSQ->size; i++)
{
if (pSSQ->data[i] == data)
return i;
}
return -1;
}3.12 静态顺序表修改
// 静态顺序表 - 修改
void SSeqListModifi(SSeqList* pSSQ, size_t pos, SSQLType data)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
pSSQ->data[pos] = data;
}3.13 静态顺序表检测空间是否满
// 静态顺序表 - 检测 - 满了返回false - 没满返回true
bool SSeqListCheck(SSeqList* pSSQ)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
return pSSQ->size != N;
}3.14 静态顺序表检测是否为空
// 静态顺序表 - 检测是否存在数据个数 - 有数据返回true - 没有数据返回false。
bool SSeqListEmpty(SSeqList* pSSQ)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
return pSSQ->size != 0;
}3.15 静态顺序表获取有效数据个数
// 静态顺序表 - 获取有效数据个数
bool SSeqListGetSize(SSeqList* pSSQ)
{
// 断言：保护形参指针不为NULL
assert(pSSQ);
return pSSQ->size - 1;
}3.16 动态顺序表定义数据结构
// 动态的顺序表数据结构
#define SEQLIST_INIT_SIZE 4;// 定义初始化时开辟内容空间的大小。
typedef int SLDataType;
typedef struct SeqList
{
SLDataType *data; // 顺序表数据存放区。
size_t size; // 顺序表数据存储大小。
size_t capacity; // 顺序表数据存储空间的大小。
}SeqList;
// 顺序表接口的实现
// 顺序表初始化 - 函数声明
void SLInit(SeqList* pSl);
// 顺序表检查容量 - 函数声明
void SLCheckCapacity(SeqList* pSl);
// 顺序表销毁 - 函数声明
void SLDestory(SeqList* pSl);
// 顺序表尾插 - 函数声明
void SLPushBack(SeqList* pSl, SLDataType data);
// 顺序表头插 - 函数声明
void SLPushFront(SeqList* pSl, SLDataType data);
// 顺序表尾删 - 函数声明
void SLPopBack(SeqList* pSl);
// 顺序表头删 - 函数声明
void SLPopFront(SeqList* pSl);
// 顺序表查找 - 函数声明
int SLFind(SeqList* pSl, SLDataType data);
// 顺序表在pos位置插入data - 函数声明
void SLInsert(SeqList* pSl, size_t pos, SLDataType data);
// 顺序表在pos位置删除data - 函数声明
void SLErase(SeqList* pSl, size_t pos);
// 顺序表修改pos位置数据 - 函数声明
void SLModify(SeqList* pSl, size_t pos, SLDataType data);
// 顺序表打印 - 函数声明
void SLPrint(const SeqList* pSl);3.17 动态顺序表初始化开辟函数
// 动态顺序表 - 初始化
void SeqListInit(SeqList* pSQ)
{
// 断言保护形参指针变量不为NULL
assert(pSQ);
pSQ->data = NULL;
pSQ->size = pSQ->capacity = 0;
}备注：此函数其实没有什么可以注意的，因为就是对新创建的顺序表数组进行初始化。
3.18 动态顺序表销毁函数
// 顺序表销毁 - 函数声明
void SLDestory(SeqList* pSl)
{
assert(pSl); // 形参不可以为空。
if (pSl->data != NULL)
{
// 顺序表对应的数组，所以可以直接free数组。
free(pSl->data);
pSl->data = NULL;
pSl->capacity = pSl->size = 0;
}
}备注：可以直接对 pSl->data 这个数组进行初始化。因为数组，free是对一个对象的总的内存空间进行初始化，所以可以直接free()掉。
3.19 动态顺序表检测扩容
这个检测扩容的函数提前拿出来说一下，在每次进行添加数据的时候，都要进行检测扩容，如果数据不足的话就应该进行扩容了，值得注意的是，此程序没有初始化的开辟内存，当容量和数据个数相等的时候，会自己判断是否是第一次扩容。
// 顺序表检查容量
void SLCheckCapacity(SeqList* pSl, SLDataType data)
{
// 断言：形参不可以为空。
assert(pSl);
// 检测扩容
if (pSl->size == pSl->capacity)
{
// 说明需要进行扩容了。
size_t newCapacity = pSl->capacity == 0 ? 4 : pSl->capacity * 2;
SLDataType* pTemp = (SLDataType*)realloc(pSl->data, newCapacity * sizeof(SLDataType));
if (pTemp == NULL)
{
perror("SLPushBack realloc fail");
exit(-1);
}
// 程序走到这里说明扩容成功了。
pSl->data = pTemp;
pTemp = NULL;
pSl->capacity = newCapacity;
// 已经扩容成功。
}
}代码这里用了realloc这个函数进行扩容的，为啥不用malloc呢？
3.20 动态顺序表尾插函数
尾插的代码。
尾插的时候无非注意的就是，在插之前检查容量是否满足，让size指向的下表位置的数据存储要插入的数据。
// 顺序表尾插
void SLPushBack(SeqList* pSl, SLDataType data)
{
// 形参pSl不可以是空指针。
assert(pSl);
// 检测扩容
SLCheckCapacity(pSl,data);
// 给数据，并且计数存储数量的大小。
pSl->data[pSl->size] = data;
pSl->size++;
}3.21 动态顺序表头插函数
头插函数的代码：
在头插前我们需要把第一位的数据空出来，值得注意的是，我们需要倒这拿数据。
// 顺序表头插
void SLPushFront(SeqList* pSl, SLDataType data)
{
// 形参pSl不可以是空指针。
assert(pSl);
// 检测扩容
SLCheckCapacity(pSl, data);
// 将pSl->data[0]这个数据空出来
int end = (int)pSl->size - 1;
while (end >= 0)
{
pSl->data[end + 1] = pSl->data[end];
end--;
}
// 给数据，并且计数存储数量的大小。
pSl->data[0] = data;
pSl->size++;
}
//---------------------------------------------------------------------------------------
// 动态顺序表 - 头插入
void SeqListPushFront(SeqList* pSQ, SQLType data)
{
// 断言保护形参指针变量不为NULL
assert(pSQ);
// 判断容量，开辟容量.
SeqListBuyCapacity(pSQ);
// 先移动数据，在头部位置插入数据
int end = (int)pSQ->size;
while (end > 0)
{
pSQ->data[end] = pSQ->data[end - 1];
end--;
}
// 移动完数据直接插入第一个位置
pSQ->data[0] = data;
pSQ->size++;
}3.22 动态顺序表尾删函数
我们分析一下尾删除：
// 动态顺序表 - 尾删除
void SeqListPopBack(SeqList* pSQ)
{
// 断言保护形参指针变量不为NULL
assert(pSQ);
// 判断动态顺序表中是否还有数据
if (!SeqListEmpty(pSQ))
{
printf("SeqList Empty!");
return;
}
// 判断容量，开辟容量.
--pSQ->size;
}3.23 动态顺序表头删函数
我们分析一下头删除：
// 顺序表头删
void SLPopFront(SeqList* pSl)
{
// 形参pSl不可以是空指针。
assert(pSl);
// 强制检测pSl->的值要大于0
assert(pSl->size > 0);
int begin = 0;
while (begin < pSl->size - 1)
{
pSl->data[begin] = pSl->data[begin + 1];
++begin;
}
// 数据个数减一
pSl->size--;
}
// 还有另一种挪动位置的方式，我们可以看一下。
3.24 动态顺序表查找函数
查找函数的就不解析了 很简单。
// 顺序表查找
int SLFind(SeqList* pSl, SLDataType data)
{
// 形参pSl不可以是空指针。
assert(pSl);
// 遍历查找要找的值
for (int i = 0; i < pSl->size; i++)
{
if (pSl->data[i] == data)
return i;
}
return -1;
}3.25 动态顺序表在pos位置插入函数
这个函数的代码要注意的是因为定义end的类型是size_t的数据类型，它没有负数，在进行条件判断的时候要格外注意，当然可以直接定义成int的型，但是我们要模拟库中的范例来写，尽量用size_t的数据类型来写函数。
当然我们可以按照下面这个图来进行编写代码。
// 顺序表在pos位置插入data
void SLInsert(SeqList* pSl, size_t pos, SLDataType data)
{
// 形参pSl不可以是空指针。
assert(pSl);
// 在插入数据之前要检测容量。
SLCheckCapacity(pSl);
// 容量足够的情况下，这时候我们就可以插数据了
size_t end = pSl->size;
while (end > pos)
{
pSl->data[end] = pSl->data[end - 1];
end--;
}
// 保存数据，记录数据个数。
pSl->data[pos] = data;
++pSl->size;
}3.26 动态顺序表在pos位置删除函数
在pos位置删除，其实和直接头删除差不多，只不过有一个pos位置，也就是说，从pos出走到pSl->size-1的位置上。
void SLErase(SeqList* pSl, size_t pos)
{
// 形参pSl不可以是空指针。
assert(pSl);
// 判断动态顺序表中是否还有数据
if (!SeqListEmpty(pSQ))
{
printf("SeqList Empty!");
return;
}
size_t begin = pos;
while (begin < pSl->size - 1)
{
pSl->data[begin] = pSl->data[begin + 1];
++begin;
}
pSl->size--;
}3.27 动态顺序表修改函数
修改的函数比较简单，直接看代码吧。
void SLModify(SeqList* pSl, size_t pos, SLDataType data)
{
// 形参pSl不可以是空指针。
assert(pSl);
// 强制检测pSl->的值要大于0
assert(pos < pSl->size);
// 修改数据。
pSl->data[pos] = data;
}3.28 动态顺序表打印函数
// 动态顺序表 - 打印
void SeqListPrint(SeqList* pSQ)
{
// 断言保护形参指针变量不为NULL
assert(pSQ);
for (int i = 0; i < pSQ->size; i++)
{
printf("%d ",pSQ->data[i]);
}
printf("\n");
}3.29 动态顺序表判断空函数
bool SeqListEmpty(SeqList* pSQ)
{
// 断言保护形参指针变量不为NULL
assert(pSQ);
return pSQ->size != 0;
}3.30 动态顺序表过去有效数据个数
// 动态顺序表 - 获取有效数据个数
int SeqListGetSize(SeqList* pSQ)
{
// 断言保护形参指针变量不为NULL
assert(pSQ);
// 判断动态顺序表中是否还有数据
if (!SeqListEmpty(pSQ))
{
return -1;
}
return (int)pSQ->size - 1;
}
顺序表完整版《终结》
本文含有隐藏内容，请 开通VIP 后查看