[C][数据结构][顺序表]详细讲解+实现

1.线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列
线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

2.顺序表 - SeqList

概念及结构
- 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改 (此数组必须从第一个位置开始，连续存储)
动态顺序表 – 使用动态开辟的数组存储

3.实现

接口

typedef int SLDataType;//类型重命名，方便以后维护替换别的类型
 
typedef struct SeqList
{
	SLDataType* arr;//指向动态数组指针
	int size;//有效数据个数
	int capacity;//容量 - 空间大小
}SL;
 
//顺序表初始化
void SLInit(SL* ps);
//销毁顺序表
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
 
//检测增容
void SLCheckCapacity();
 
//增删查改
//尾插/尾删 - O(1)
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
 
//头插/头删 - O(N)
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
 
//从任意位置插入/删除
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
 
//查找和修改
int SLSearch(SL* ps, SLDataType x);
void SLModify(SL* ps, int pos, SLDataType x);

接口实现

void SLInit(SL* ps)
{
	assert(ps);
 
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
 
void SLDestroy(SL* ps)
{
	assert(ps);
 
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capacity = 0;
		ps->size = 0;
	}
}
 
void SLPrint(SL* ps)
{
	assert(ps);
 
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
 
	printf("\n");
}
 
void SLCheckCapacity(SL* ps)
{
	assert(ps);
 
	//检查容量空间，满了扩容
	if (ps->size == ps->capacity)
	{
		ps->capacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //最大容量扩容
		SLDataType* tmp = realloc(ps->arr, ps->capacity * sizeof(SLDataType));
		if (NULL == tmp)
		{
			perror("realloc:");
			exit(1);
		}
		ps->arr = tmp;
	}
}
 
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
 
	SLCheckCapacity(ps);
 
	ps->arr[ps->size] = x;
	ps->size++;
 
	//SLInsert(ps, ps->size, x); //以上代码可以用这个封装替换了
}
 
void SLPopBack(SL* ps)
{
	assert(ps);
	//暴力检查 - 适用于调试阶段
	assert(ps->size > 0);
 
	//温柔检查 - 适用于和用户交互使用
	//if (0 == ps->size)
	//{
	//	printf("SeqList is empty\n");
	//	return;
	//}
	
	ps->size--;
 
	SLErase(ps, ps->size - 1); //以上代码可以用这个封装替换了
}
 
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
 
	//挪动数据
	int end = ps->size - 1;
	while (end >= 0)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
 
	ps->arr[0] = x;
	ps->size++;
 
	//SLInsert(ps, 0, x); //以上代码可以用这个封装替换了
}
 
void SLPopFront(SL* ps)
{
	int begin = 1;
	while (begin < ps->size)
	{
		ps->arr[begin - 1] = ps->arr[begin];
		begin++;
	}
 
	ps->size--;
 
	//SLErase(ps, 0); //以上代码可以用这个封装替换了
}
 
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size); //检验位置合法性
 
	SLCheckCapacity(ps);
 
	//挪动数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->arr[end + 1] = ps->arr[end];
		end--;
	}
 
	ps->arr[pos] = x;
	ps->size++;
}
 
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
 
	//挪动数据
	int begin = pos;
	while (begin < ps->size - 1)
	{
		//后面的数据往前搬
		ps->arr[begin] = ps->arr[begin + 1];
		begin++;
	}
 
	ps->size--;
}
 
int SLSearch(SL* ps, SLDataType x)
{
	assert(ps);
	
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
 
	return -1;
}
 
void SLModify(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
 
	ps->arr[pos] = x;
}