[数据结构]动态顺序表的实现与应用
文章目录
一、引言
想象一下，你有一个箱子（静态顺序表），它的大小是固定的，你只能在这个箱子里面放东西或者拿出来，如果东西放不下了，箱子就满了，没办法再放更多。但现在，我们有了一种更灵活的箱子 —— 动态顺序表。这个箱子不仅能放东西，还能根据需要自动变大或变小，非常方便。
不过，要想玩转这个神奇的箱子，我们得先对里面的 “东西” （数据）的存放方式有所了解，也就是得熟悉数组和指针。如果你对这些还不太熟悉，别担心，我已经为你准备了一篇文章作为参考：传送门。读完之后，你会发现它们其实并不复杂。
二、动态顺序表的基本概念
动态顺序表，简单来说，就是一个可以 “长大” 或 “缩小” 的箱子。它不像静态顺序表那样一开始就确定了大小，而是根据我们需要存放的东西的多少来动态地调整自己的大小。
当我们往动态顺序表里放东西时，如果箱子满了，它就会自动去找一个更大的箱子，然后把原来的东西和新东西一起放进去。这个过程就像是我们换了一个更大的家，然后把所有家具都搬进去一样。
反过来，如果我们从动态顺序表里拿走了很多东西，箱子变得空荡荡的，那它也会考虑换个小点的箱子住，毕竟节省空间也是一种美德嘛。
总之，动态顺序表就是这样一个既智能又灵活的箱子，它能够帮助我们更加高效地管理和存储数据。
三、动态顺序表的实现
1、结构体定义
首先，我们需要定义一个结构体来表示动态顺序表，这个结构体将包含指向数组元素的指针、当前存储的元素数量以及分配的空间大小。
typedef int DataType;
typedef struct {
DataType* arr;//指向动态数组的指针
int size;//当前存储的元素个数
int capacity;//当前动态数组的容量
}Seq;
2、初始化
初始化动态顺序表时，我们需要为其分配一个初始的空间大小，并设置当前存储的元素数量为0。
void Init(Seq* ps, int capacity)
{
capacity == 0 ? capacity = 2 : capacity;
DataType* pos = (DataType*)malloc(sizeof(DataType) * capacity);
if (pos == NULL)
{
fprintf(stderr, "内存分配失败\n");
exit(EXIT_FAILURE);
}
ps->array = pos;
ps->capacity = capacity;
ps->size = 0;
}
3、销毁
使用完动态顺序表后，需要释放分配的内存，避免内存泄漏。
void Destroy(Seq* ps)
{
if (ps == NULL)
return;
free(ps->array);
ps->array = NULL;
ps->capacity = 0;
ps->size = 0;
}
4、扩容
当向动态顺序表中添加元素时，如果当前空间已满，则需要进行扩容操作。扩容通常会将容量加倍。
void Reserve(Seq* ps)
{
if (ps->size == ps->capacity)
{
int capacity = ps->capacity == 0 ? 2 : ps->capacity * 2;
DataType* pos = (DataType*)realloc(ps->array, capacity * sizeof(DataType));
if (pos == NULL)
{
fprintf(stderr, "内存分配失败\n");
exit(EXIT_FAILURE);
}
ps->array = pos;
ps->capacity = capacity;
}
}
5、缩容
当删除动态顺序表中的元素时，如果当前空间过大，则需要进行缩容操作。
void Shrink(Seq* ps)
{
if (ps->capacity >= 64 && ps->size < ps->capacity / 2.5)
{
int capacity = ps->capacity / 2;
DataType* pos = (DataType*)realloc(ps->array, capacity * sizeof(DataType));
if (pos == NULL)
{
fprintf(stderr, "内存分配失败");
exit(EXIT_FAILURE);
}
ps->array = pos;
ps->capacity = capacity;
}
}
5、打印
为了方便调试和查看动态顺序表中的内容，我们可以实现一个打印函数，将所有元素打印出来。
void Print(Seq* ps, void (*Pr) (DataType))
{
for (int i = 0; i < ps->size; i++)
{
Pr(ps->array[i]);
}
printf("NULL\n");
}
6、增删查改
实现顺序表的基本操作，让顺序表更具有实用性。
void PushFront(Seq* ps, DataType data)
{
Insert(ps, 0, data);
}
void PopFront(Seq* ps)
{
Erase(ps, 0);
}
void PushBack(Seq* ps, DataType data)
{
Insert(ps, ps->size, data);
}
void PopBack(Seq* ps)
{
Erase(ps, ps->size - 1);
}
void Insert(Seq* ps, int x, DataType data)
{
assert(x >= 0 && x <= ps->size);
Reserve(ps);
for (int i = ps->size - 1; i >= x; i--)
{
ps->array[i + 1] = ps->array[i];
}
ps->array[x] = data;
ps->size++;
}
void Erase(Seq* ps, int x)
{
assert(ps != NULL && ps->size > 0 && x >= 0 && x < ps->size);
for (int i = x; i < ps->size - 1; i++)
{
ps->array[i] = ps->array[i + 1];
}
ps->size--;
}
int Find(Seq* ps, DataType data)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->array[i] == data)
{
return i;
}
}
return -1;
}
void Modify(Seq* ps, int x, DataType data)
{
assert(ps != NULL && ps->size > 0 && x >= 0 && x < ps->size);
ps->array[x] = data;
}
四、分析动态顺序表
1、存储方式
顺序表是线性表的一种，线性表的逻辑结构是连续的，物理结构是不一定连续的。顺序表使用数组进行存储，数组在内存中是连续的，所以顺序表的物理结构是连续的。
2、优点
顺序表在随机访问时具有很高的效率，因为数组在内存中是连续的，所以可以通过下标直接访问到对应的元素。
3、缺点
顺序表在插入和删除元素时，需要移动大量元素，所以效率较低。另外，顺序表的大小是固定的，如果需要扩容，需要重新分配内存，这也会带来一定的开销。
五、总结
1、练习题
2、源代码
对于动态顺序表的源代码我已经开源在GItee：传送门
建议读者，仔细阅读源代码，理解数据结构的设计思路，尝试修改和扩展功能以加深理解。通过编写测试案例来验证理解和代码的正确性。
原文地址：https://blog.csdn.net/2301_79450966/article/details/142419347
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！