🍏前言：
顺序表是数据结构里面很基础的一类，它是线性表的一种，其它线性表还有链表、栈和队列等，今天来和博主一起学习关于顺序表的知识吧。
🍏顺序表和数组的区别
顺序表，它分为两类：
动态顺序表和静态顺序表，这两个表的区别就是前者的空间不固定，是支持扩容的，后者的空间是固定的，但是两者的共同点是空间都是连续的，动态顺序表的底层是动态数组，而静态顺序表的底层是数组。
- 很明显我们经常用到的数据结构就是动态的顺序表，因为静态的顺序表空间固定，没什么实际的价值。
- 还有一个区别就是，动态顺序表是基于动态数组的，但是它作为一个数据结构，提供了很多动态数组没有直接提供的功能，像
增、删、查、改、创建和销毁、以及计算数组的大小这些基本的功能。
🍏动态顺序表的模拟实现
🍀动态顺序表的基本结构设计
#define DataTypeVector int
typedef struct my_vector
{
int* a;//储存数据
size_t size;//顺序表的数据大小
size_t capacity;//顺序表的空间大小
}mv;
各种接口：
//初始化
mv* Init();
//头插
void push_front(mv* mv1, DataTypeVector x);
//头删
void pop_front(mv* mv1);
//尾插
void push_back(mv* mv1, DataTypeVector x);
//尾删
void pop_back(mv* mv1);
//插入--在某个位置之前
void insert(mv* mv1,size_t positon, DataTypeVector x);
//删除某个位置的元素
void erase(mv* mv1,size_t position);
//查找某个值，并返回它出现的位置,没有找到，返回-1；
int find(mv* mv1, DataTypeVector x);
//计算动态顺序表的大小
size_t Size(mv* mv1);
//销毁动态顺序表
void Destroy(mv** mv1);
//修改某个位置的值
void Modify(mv* mv1, size_t position, DataTypeVector x);
🍀动态顺序表的各种功能模拟实现
🐲 初始化（init）
返回值版本：
//初始化动态顺序表
//返回值版本
mv* Init()
{
mv* mv1 = (mv*)malloc(sizeof(mv));
if (mv1 == NULL)
{
printf("malloc Falied\n");
exit(-1);
}
mv1->a = NULL;
mv1->capacity = 0;
mv1->size = 0;
return mv1;
}
二级指针版本：
//二级指针版本，不带返回值
void Init(mv** mv1)
{
assert(mv1);
(*mv1) = (mv*)malloc(sizeof(mv));
if ((*mv1) == NULL)
{
printf("malloc failed\n");
exit(-1);
}
(*mv1)->a = NULL;
(*mv1)->capacity = NULL;
(*mv1)->size = NULL;
}
🐲 头插、头删
🚙 头插
//头插
void push_front(mv* mv1, DataTypeVector x)
{
assert(mv1 != NULL);
if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
{
(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
DataTypeVector* tmp = NULL;
tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
mv1->a = tmp;
}
//将所有值后移
for (size_t i = mv1->size; i > 0; --i)
{
mv1->a[i] = mv1->a[i-1];
}
mv1->a[0] = x;
++mv1->size;
}
🚙 头删
//头删
void pop_front(mv* mv1)
{
assert(mv1 != NULL);
assert(mv1->size > 0);
//将后面的值依次覆盖前面的值
for (size_t i = 0; i < mv1->size-1; ++i)
{
mv1->a[i] = mv1->a[i + 1];
}
--mv1->size;//别忘了数组的大小要减减
}
🐲 尾插、尾删
🚙 尾插
//尾插
void push_back(mv* mv1, DataTypeVector x)
{
assert(mv1 != NULL);
if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
{
(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
DataTypeVector* tmp = NULL;
tmp = (DataTypeVector*)realloc(mv1->a,sizeof(DataTypeVector) * mv1->capacity);
if (tmp == NULL)
{
printf("realloc failed\n");
exit(-1);
}
mv1->a = tmp;
}
mv1->a[mv1->size] = x;
++mv1->size;
}
🚙 尾删
//尾删
void pop_back(mv* mv1)
{
assert(mv1);
assert(mv1->size > 0);
--mv1->size;
}
🐲 计算动态顺序表的大小（size接口）
//计算动态线性表的大小
size_t Size(mv* mv1)
{
assert(mv1);
return mv1->size;
}
🐲 动态顺序表在特定位置插入（insert）
这里我们仿照C++STL库，只实现了在pos位置之前插入。
//插入--在某个位置之前
//插入--在某个位置之前
void insert(mv* mv1, size_t position,DataTypeVector x)
{
assert(mv1 != NULL);
assert(position < mv1->size);
if ((mv1)->capacity == (mv1)->size)//判断是否需要扩容
{
(mv1)->capacity = (mv1)->capacity == 0 ? 4 : (mv1)->capacity * 2;
DataTypeVector* tmp = NULL;
tmp = (DataTypeVector*)realloc(mv1->a, sizeof(DataTypeVector) * mv1->capacity);
if (tmp == NULL)
{
printf("calloc failed\n");
exit(-1);
}
mv1->a = tmp;
}
//从下标size开始，把数据都往后挪动.
for (size_t i = mv1->size; i > position; --i)
{
mv1->a[i] = mv1->a[i-1];
}
//最后把下标position位置赋值为x
mv1->a[position] = x;
//别忘了size
++mv1->size;
}
🐲 动态顺序表在特定位置删除（erase）
//删除某个位置的元素
void erase(mv* mv1, size_t position)
{
assert(mv1 != NULL);
assert(position < mv1->size);
for (size_t i = position; i < mv1->size-1; ++i)
{
mv1->a[i] = mv1->a[i + 1];
}
--mv1->size;
}
🐲 动态顺序表的查找
//查找某个值，并返回它出现的位置,没有找到，返回-1；
int find(mv* mv1,DataTypeVector x)
{
assert(mv1 != NULL);
for (size_t i = 0; i < mv1->size; ++i)
{
if (x == mv1->a[i])//找到直接返回下标i
return i;
}
return -1;//没有找到返回-1
}
这里顺序表不一定是有序的，所以不能使用二分查找。
🐲 修改某个位置的值
void Modify(mv* mv1,size_t position,DataTypeVector x)
{
assert(mv1);
assert(position < mv1->size);
mv1->a[position] = x;
}
🐲 动态顺序表的销毁
动态顺序表的底层就是动态数组，它是堆上开辟的，通常遵循一下原则：
1. 由谁申请就由谁释放。 这是一个约定俗成的说法，指的是谁（程序员）申请的内存，需要自己负责去释放，避免出现内存泄漏。
2.只能一次释放整个动态数组，而不能只释放一部分
只要我们遵循这两个原则，然后再对顺序表类型的成员进行置空和置零，就实现了动态线顺序表的销毁。
//销毁动态顺序表
void Destroy(mv** mv1)
{
assert(mv1 != NULL);
(*mv1)->capacity = (*mv1)->size = 0;
free((*mv1)->a);//先销毁顺序表里面的成员
(*mv1)->a = NULL;
free(*mv1);//销毁整个顺序表
*mv1 = NULL;
}
⭕️ 总结
关于《数据结构初阶之顺序表（C语言实现）》这篇文章就讲解到这儿，感谢大家的支持，欢迎大家留言交流以及批评指正。接下来将为大家带来一篇《不一样的C语言之easyx库的使用》，敬请期待吧。下面是本篇博客的思维导图希望对您有所帮助。文章来源：https://www.toymoban.com/news/detail-770299.html
文章来源地址https://www.toymoban.com/news/detail-770299.html
到了这里，关于数据结构初阶之顺序表（C语言实现）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
