从零实现动态顺序表：深入理解动态顺序表的作用原理

一、什么是动态顺序表？

顺序表（Sequential List）是线性表在内存中的连续存储实现，也是数据结构中最基础的存储方式之一。与静态数组不同，动态顺序表通过实时内存管理实现了以下关键特性：

• 容量自动扩展/收缩
• 随机访问时间复杂度O(1)
• 支持动态增删元素
• 内存利用率可控

二、动态顺序表的实现原理

2.1 定义动态顺序表结构体

typedef int SLDataType;//重命名顺序表所存储数据的数据类型
typedef struct SeqList
{
	SLDataType* a;//动态数组指针
	int size;//当前顺序表所存储的元素个数
	int capacity;//当前顺序表内存分配的容量
}SL;

2.2 初始化顺序表

#define Init_capacity 4//设置容量初始值
void Seq_Init(SL* s)
{
	assert(s);
	s->a = (SLDataType*)malloc(sizeof(SLDataType) * Init_capacity);
	s->size = 0;
	s->capacity = Init_capacity;
}

2.3 顺序表的扩容

顺序表经过不断的数据插入，先前的容量不足以继续存放数据，此时，我们需要对顺序表进行扩容处理。

void SeqExpand(SL* s)
{
	assert(s);
	SLDataType* p = (SLDataType*)realloc(s->a, sizeof(SLDataType) * s->capacity * 2);
	if (p == NULL)
		perror("realloc failed");
	s->a = p;
	s->capacity *= 2;
}

2.4 顺序表的增删查改

2.4.1 在pos处插入数据

void Seqpush(SL* s,int pos, SLDataType val)
{
	assert(s && s->a);
	assert(pos > 0 && pos <= s->size+1);
	if (s->size == s->capacity)//检查是否需要扩容
	{
		SeqExpand(s);
	}
	int i = 0;
	for (i = s->size - 1;i >=pos-1;i--)
	{
		s->a[i + 1] = s->a[i];
	}
	s->a[pos - 1] = val;
	s->size++;
}

2.4.2 在pos处删除数据

void Seqpop_pos(SL* s, int pos)
{
	assert(s && s->a);
	assert(pos > 0 && pos <= s->size);
	int i = 0;
	for (i = pos - 1;i < s->size-1;i++)
	{
		s->a[i] = s->a[i + 1];
	}
	s->size--;//删除数据后元素个数减一
}

2.4.3 删除第一个值为val的数据

void Seqpop_val(SL* s, SLDataType val)
{
	assert(s && s->a);
	int i = 0,flag=0;
	for (i = 0;i < s->size;i++)
	{
		if (s->a[i] == val)
		{
			flag = 1;
			for (int j = i;j < s->size;j++)
			{
				s->a[j] = s->a[j + 1];
			}
			break;
		}
	}
	if (flag == 1)
	{
		s->size--;
	}
	//如果顺序表中不存在值为val的数据则无变化
}

2.4.4 查找的一个值为val的数据的位置

int SeqFind(SL* s, SLDataType val)
{
	assert(s && s->a);
	int i = 0;
	for (i = 0;i < s->size;i++)
	{
		if (s->a[i] == val)
		{
			return i+1;
		}
	}
	return 0;//若未找到则返回0
}

2.4.5 修改pos处的数据

void SeqRevise(SL* s, int pos, SLDataType val)
{
	assert(s && s->a);
	assert(pos > 0 && pos <= s->size);
	int i = 0;
	s->a[pos - 1] = val;
}

2.5 打印顺序表

void Seq_printf(SL* s)
{
	assert(s&&s->a);
	int i = 0;
	for (i = 0;i < s->size;i++)
	{
		printf("%d ", s->a[i]);
	}
}

2.6 销毁顺序表

动态顺序表使用手动管理的内存（malloc/realloc分配），如果不主动释放，会导致内存泄漏，最终可能耗尽系统内存。

void SeqDestroy(SL* s)
{
	free(s->a);
	s->a = NULL;
}

三、动态顺序表 vs 普通数组

四、结语

动态顺序表是C语言中非常实用的数据结构，它让数组拥有了"自动扩容"的超能力。掌握了动态顺序表，你就能更好地处理各种需要动态存储数据的场景。

感谢您的阅读和关注！ (˶╹ꇴ╹˶)