[数据结构]动态顺序表的实现与应用

一、引言

想象一下，你有一个箱子（静态顺序表），它的大小是固定的，你只能在这个箱子里面放东西或者拿出来，如果东西放不下了，箱子就满了，没办法再放更多。但现在，我们有了一种更灵活的箱子 —— 动态顺序表。这个箱子不仅能放东西，还能根据需要自动变大或变小，非常方便。

不过，要想玩转这个神奇的箱子，我们得先对里面的 “东西” （数据）的存放方式有所了解，也就是得熟悉数组和指针。如果你对这些还不太熟悉，别担心，我已经为你准备了一篇文章作为参考：传送门。读完之后，你会发现它们其实并不复杂。

---

二、动态顺序表的基本概念

动态顺序表，简单来说，就是一个可以 “长大” 或 “缩小” 的箱子。它不像静态顺序表那样一开始就确定了大小，而是根据我们需要存放的东西的多少来动态地调整自己的大小。

当我们往动态顺序表里放东西时，如果箱子满了，它就会自动去找一个更大的箱子，然后把原来的东西和新东西一起放进去。这个过程就像是我们换了一个更大的家，然后把所有家具都搬进去一样。

反过来，如果我们从动态顺序表里拿走了很多东西，箱子变得空荡荡的，那它也会考虑换个小点的箱子住，毕竟节省空间也是一种美德嘛。

总之，动态顺序表就是这样一个既智能又灵活的箱子，它能够帮助我们更加高效地管理和存储数据。

---

三、动态顺序表的实现

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：传送门
建议读者，仔细阅读源代码，理解数据结构的设计思路，尝试修改和扩展功能以加深理解。通过编写测试案例来验证理解和代码的正确性。

---