【数据结构】顺序表

一、认识顺序表

1.线性表

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

2.顺序表的概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删改查。顺序表一般可分为：静态顺序表和动态顺序表（使用动态开辟的数组存储）。

1.静态顺序表：使用定长数组存储元素

#define MAX 10
typedef int SLDataType;//当存储数据类型改变时，方便修改
typedef struct SeqList
{
	SLDataType arr[MAX];//用来存储数据
	int size;//用来记录数组中存储有效数据元素的个数
}SL;

2.动态顺序表：使用动态开辟的数组存储

//动态顺序表
typedef int SLDataType;//当存储数据类型改变时，方便修改
typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	int size;//用来记录数组中存储有效数据元素的个数
	int capacity;//用来记录容量大小
}SL;

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致MAX定大了，空间开多了浪费，开少了不够用。所以现实中基本都是用动态顺序表，根据需要动态的分配空间大小，所以本文中使用动态开辟的顺序表实现顺序表的基本操作。

二、顺序表的基本操作（接口实现）

1.初始化顺序表

void SLInit(SL* ps)
{
	assert(ps);//不为空指针
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

初始化时设置其有效数据个数和容量都为0，指针指向NULL，断言assert(ps)，避免在定义结构体变量时写为SL* sl=NULL。

2.打印顺序表

void SLPrint(SL* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}

3.尾插

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity;//判断刚开始是否有空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = NewCapacity;
	}
	ps->arr[ps->size] = x;
	ps->size++;
}

尾插就是在尾部插入数据，因为刚开始的时候没有给数组分配空间，所以要考虑当没有空间时要去申请空间，realloc函数是扩容函数，在指针为空的情况下作用和malloc相同，int NewCapacity =ps->capacity == 0 ? 4 : 2 * ps->capacity判断当前容量大小并确定要开辟的空间大小。 SLDataType* tmp = (SLDataType*)realloc(ps->arr,sizeof(SLDataType) * NewCapacity)，用来在堆内存中开辟空间，realloc之后注意将其强制转化成SLDataType*类型。当成功开辟空间之后赋给ps->arr，同时注意将NewCapacity赋给ps->capacity。

4.尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	//暴力的检查
	assert(ps->size > 0);//判断ps->size是否大于0，当等于0时再删的话ps->size就会变为-1，越界
	//温柔的检查
	//if (ps->size == 0)
	//{
	//	return;
	//}
	ps->size--;
}

当ps->size等于0时直接返回，如果不返回，造成ps->size为负数，造成数组越界，当我们再次插入数据的时候可能会出现报错，同时当越界时可能不会报错，但是可能会在free时候报错。所以要用assert(ps->size > 0)检查ps->size大小，等于0时直接退出，并提示。 扩展：free时候报错可能的错误原因有两种，一是free时候指针不正确，可能是野指针，同时释放的时候必须从起始位置释放。二是越界时候free会报错。当越界读数组的时候基本不会被检查出来报错，但是改变它的值的时候就可能会报错，是一种抽查行为，是在运行时检查。

5.扩容

void SLCheckCapacity(SL* ps)
{
	assert(ps);
	//检查是否需要扩容
	if (ps->size == ps->capacity)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->capacity = NewCapacity;
		ps->arr = tmp;
	}
}

扩容函数，用于检查数组空间大小是否适合继续插入，当数组空间不足时进行扩容，定义此函数之后可以对上面尾插函数进行简化，如下：

void SLPushBack(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	
	ps->arr[ps->size] = x;
	ps->size++;
}

6.头插

void SLPushFront(SL* ps, SLDataType x)
{
	SLCheckCapacity(ps);
	int end = ps->size;
	//挪动数据
	while (end > 0)
	{
		ps->arr[end] = ps->arr[end-1];
		end--;
	}
	ps->arr[0] = x;
	ps->size++;
}

利用扩容函数对其检查，注意控制循环结束条件。

7.头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	int begin = 0;
	while (begin < ps->size-1)
	{
		ps->arr[begin] = ps->arr[begin + 1];
		begin++;
	}
	ps->size--;
}

注意判断当ps->size等于0时不能再进行ps->size--，要加上一条判断语句assert(ps->size > 0)。

8.任意位置插入

void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);
	SLCheckCapacity(ps);
	int end = ps->size;
	while (end>pos)
	{
		ps->arr[end] = ps->arr[end - 1];
		end--;
	}
	ps->arr[pos] = x;
	ps->size++;
}

pos是数组下标，同时注意判断pos的范围。

9.任意位置删除

void SLErase(SL* ps, int pos)//任意位置删除
{
	assert(ps);
	assert(pos >= 0);
	assert(pos < ps->size);
	while (pos < ps->size-1)
	{
		ps->arr[pos] = ps->arr[pos + 1];
		pos++;
	}
	ps->size--;
}

pos表示的是数组下标，有assert(pos >= 0)和assert(pos <= ps->size)两个判断条件之后不用再加assert(ps->size>0)，因为当ps->size等于0时，assert(pos <= ps->size)会报错。

10.查找某个数的位置

int SLFind(SL* ps, SLDataType x)//返回类型为int,是数组下标
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}

返回值是数组下标。

思考：当我们想删除某个值时应该怎么做？当被删除的值有多个时又要怎么做呢？ 我们可以通过下面的代码实现：

int SLNFind(SL* ps, SLDataType x, int begin)//begin是开始查找的位置
{
	assert(ps);
	int i = 0;
	for (i = begin; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}