一篇博客读懂顺序表 —

一篇博客读懂顺序表 —— Sequence-List

一、顺序表的初始定义

1.1新建头文件和源文件

1.2 SeqList.h 中的准备工作

二、顺序表的初始化与销毁

三、首尾插入元素

四、首尾删除元素

五、中间插入元素

六、中间删除元素

七、查找指定元素下标

八、源代码

一、顺序表的初始定义

1.1新建头文件和源文件

当我们要实现通讯录时，我们会自定义一个 contact.h 文件来存储我们的各种声明，自定义一个 contact.c 文件来存储实现声明的函数，同时还会存在一个 test.c 来测试我们代码的可行性。

在这里我们学习顺序表时，也要使用这种方式，来分割我们的代码使程序更加简洁耐看：

在 SeqList.h 中，我们要声明我们需要的头文件、重新定义的类型、我们需要的函数......

1.2 SeqList.h 中的准备工作

为了方便我们修改顺序表中的数据类型，我们把我们顺序表中的类型(int为例)重定义为SLDataType，这样如果我们以后想修改数据类型的话，可以直接来此处将 int 改为 double......

typedef int SLDataType;

其次，我们定义的顺序表其实是一个结构体，其包含了一个表头(一个指针)，实际保存的数据以及表的容量，这里我们并把结构体名称重定义为简称，方便后续的使用。

typedef struct SeqList
{
	int* p;//表头
	int size;//实际存储的数据数量
	int capacity;//此时表中的容量
}SL;

我们的顺序表要具有哪些特点呢？

1.动态存储，可以动态开辟使用空间

2.各种位置的增删查改，分为头、尾、中间。

二、顺序表的初始化与销毁

初始化和销毁：

首先用断言来保证传入的指针不为空，其次我们需要用 SLInit 函数来将结构体中的数据一一赋初值，其次在销毁数据时，也要保证 free 函数的对象为非空指针，接着将数据重新初始化。

void SLInit(SL* psl) //初始化顺序表
{
	assert(psl != NULL);
	psl->p = NULL;
	psl->size = 0;
	psl->capacity = 0;
}
void SLDestroy(SL* psl) //销毁顺序表
{
	assert(psl != NULL);
	if (psl->p != NULL)
	{
		free(psl->p);
		psl->size = 0;
		psl->capacity = 0;
	}
}

因为我们的顺序表是动态开辟空间，所以写一个检查实时容量的函数是必备的，在此处我们使用二倍扩容的方法来开辟内存空间，但是在初始化时我们把我们的 capacity 赋值为 0，在进行二倍扩容时还是 0，这时就可以用三目运算符完美规避这个问题。

检查并扩充容量：

并且我们用新的临时变量来保存扩容后的空间，在没有问题后再把值返回给原本的变量。

void SLCheckCapacity(SL* psl)
{
	assert(psl != NULL);
	if (psl->size == psl->capacity)
	{
        //因为初始化时capacity为0，所以我们按照二倍扩容后也是0，这里运用三目运算符就能很好的解决
		SLDataType NewCapacity = (psl->capacity == 0) ? 4 : psl->capacity * 2;
        //动态开辟的空间是给顺序表的，注意不要把改行上下两个数据颠倒
        //sizeof() 不要忘！！
		SLDataType* tmp = (SLDataType*)realloc(psl->p, sizeof(SL) * NewCapacity);
		if (tmp == NULL)
		{
			perror("SLCheckCapacity -> realloc");
			return;
		}
		psl->capacity = NewCapacity;
		psl->p = tmp;
	}
}

三、首尾插入元素

打印顺序表：

为了更好的测试我们的代码，我们可以先写一个打印函数来打印我们的顺序表。

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

尾部插入元素：

void SLPushBack(SL* psl, SLDataType x)
{
	assert(psl != NULL);
	SLCheckCapacity(psl);//检查是否需要扩容
	psl->p[psl->size] = x;
	psl->size++;
}

首部插入元素：

首部插入元素就比尾部插入元素复杂一点啦，我们需要让前面的元素覆盖后面的元素，下图我们模拟顺序表中有 8 个元素(size == 8)，来看一下我们的代码应该如何写：

我们让 i 从后面开始向前走，才能保证有用的元素不会被覆盖，同时我们根据首尾元素的覆盖下标推理出 i 的取值范围。

//第一种取值
void SLPushFront(SL* psl, SLDataType x)
{
	assert(psl != NULL);
	SLCheckCapacity(psl);
	int i = psl->size;
	for (; i > 0; i--)
	{
		psl->p[i] = psl->p[i - 1];
	}
	psl->p[0] = x;
	psl->size++;
}

//第二种取值
void SLPushFront(SL* ps, SLDateType x)//ʱ临Ӷ O(n) ;  n O(n^2)
{
	assert(ps != NULL);
	SLCheckCapacity(ps);
	int i = ps->size - 1;
	for (; i >= 0; i--)
	{
		ps->p[i + 1] = ps->p[i];
	}
	ps->p[0] = x;
	ps->size++;
}

四、首尾删除元素

尾部删除元素：

这里我们采用 size-- 的方法，让我们直接无法访问到最后一个元素，下一次增添时又会被新的元素覆盖以实现删除的操作，同时断言我们的实际元素个数必须多余 0

void SLPopBack(SL* psl)
{
	assert(psl != NULL);
    assert(psl->size > 0);
	psl->size--;
}

首部删除元素：

void SLPopFront(SL* psl)
{
	assert(psl != NULL);
	int i = 1;
	for (; i <= psl->size; i++)
	{
		psl->p[i - 1] = psl->p[i];
	}
	psl->size--;
}

void SLPopFront(SL* ps)
{
	assert(ps != NULL);
	assert(ps->size > 0);
	int i = 0;
	for (; i < ps->size - 1; i++)
	{
		ps->p[i] = ps->p[i + 1];
	}
	ps->size--;
}

五、中间插入元素

void SLInsert(SL* psl, int num, SLDataType x)
{
	assert(psl != NULL);
	assert(num >= 0 && num <= psl->size);
	SLCheckCapacity(psl);
	int i = psl->size - 1;
	for (; i >= num; i--)
	{
		psl->p[i + 1] = psl->p[i];
	}
	psl->p[num] = x;
	psl->size++;
}

六、中间删除元素

void SLErase(SL* psl, int num)
{
	assert(psl != NULL);
	assert(num >= 0 && num < psl->size);
	SLCheckCapacity(psl);
	int i = num;
	for (; i < psl->size - 1; i++)
	{
		psl->p[i] = psl->p[i + 1];
	}
	psl->size--;
}

七、查找指定元素下标

int SLFind(SL* ps, SLDataType x)
{
	assert(ps != NULL);
	int i = 0;
	for (; i < ps->size; i++)
	{
		if (ps->p[i] == x)
		{
			return i;
		}
	}
	return -1;
}