在动态数组尾部插入或删除元素

数据结构中对顺序表的基本操作。

​ 在 C 语言中，学习了数组这一数据类型，它的作用就是将一系列类型相同的数据连续的存起来，在需要使用时，也能很快的访问。学习了指针以后，了解到：数组的本质其实是指针。定义了一个固定长度的数组，就相当于定义了一个指针，这个指针指向了固定长度的地址。并且，这些地址都是连续的。所以可以快速的访问数组中的任一元素。

​ 数据结构开篇即介绍了线性表的顺序表示，如果是静态的线性表，那在C语言中就是一维数组，对线性表操作就可以理解为对数组进行操作。对数组进行基本操作是比较简单易懂的。由于在学习 C 语言时，对于指针和结构体不是很熟悉，所以本篇着重整理对在 C 语言中对动态分配的一维数组的一些基本操作。

在动态分配的一维数组尾部插入元素

创建一个动态分配的一维数组

首先重定义一个结构体:

1
2
3
4
5
6
7
8

typedef int SLDataType;  //重定义int

typedef struct SeqList   //重定义结构体为SL
{
	SLDataType* a;
	int size; // size表示顺序表的元素的个数
	int capacity; // capacity表示顺序表能存的元素个数
}SL;

这里使用 typedef 定义 int 的好处是如果需要修改数组中存储元素的类型，则只需要在 typedef 中修改一次。如果不使用这种方法，则需要修改代码中的所有int类型，显然是不利于代码的维护的。

初始化数组

定义一个函数来初始化数组，将a指针初始化为空指针，size 和 capacity 初始化为0。

1
2
3
4
5
6
7

void SeqListInit(SL* ps) //结构体指针
{

	ps->a = NULL;
	ps->size = ps->capacity = 0;  //初始化数组

}

实现尾插函数（关键）

怎样实现对数组长度的动态分配呢？这对于我来说却是是一个不简单的问题，这个问题让我难以下手。高中的时候，遇到无从下手的题，我一般用特殊值，或者临界状态去试着打开突破口。所以，解决这个问题不妨从临界状态开始分析：

从图中可以看出，有两种情况需要对数组进行扩容：

1、需要插入元素，但是数组已经满了，也就是数组元素的个数等于数组的容量了。

2、需要插入元素，但数组是空的（没有空间）。

所以我们就得出了什么时候应该对数组进行扩容。除此之外数组是不需要扩容的，也就是说可以直接在最后一个元素后面插入新的元素。

通过上面的分析，不难得出一下if语句：

1
2
3
4

if (ps->size == ps->capacity)
{
    扩容；
}

由前面定义可知，数组的容量用 capacity 表示，扩容就是扩大 capacity 的值。这是不难的，直接对 capacity*2 即可。由于考虑到数组是空的，即（capacity=0）这种情况，所以得多加一个判断条件，判断其是否为0，如果不判断，那*2有时也没意义。

实现扩容就得知道 realloc 这个函数

realloc函数是将数组扩容的一个函数，它的用法是：

指针名= （数据类型*）realloc（需要改变内存大小的指针名，新的大小） ，值得注意的是：“新的大小” 是字节。有时需要乘上sizeof（数据类型）

当需要改变内存大小的指针是空指针时，它的作用相当于malloc函数。

用以下语句就可以实现扩容：

1
2
3
4
5
6
7
8
9
10

//如果没有空间。或者空间不足，就进行扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  //三目运算符。扩2倍比较合适
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));  //扩容的是字节数，要强制类型转化
		if (tmp == NULL) // 检查扩容是否成功
		{
			printf("realloc failed\n");
			exit(-1); //未成功强制退出程序
		}
        ps->a = tmp;
		ps->capacity = newcapacity;

用以下语句在胃部插入元素：

1
2

   ps->a[ps->size] = x;  //下标从0开始
ps->size++;

完整的函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void SeqListPushBack(SL* ps, SLDataType x) //实现对顺序表尾部插入元素的函数
{
	if (ps->size == ps->capacity)
	{
		//如果没有空间。或者空间不足，就进行扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;  //三目运算符。扩2倍比较合适
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));  //扩容的是字节数，要强制类型转化
		if (tmp == NULL) // 检查扩容是否成功
		{
			printf("realloc failed\n");
			exit(-1); //未成功强制退出程序
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	//空间足够。直接在表尾插入
	ps->a[ps->size] = x;  //下标从0开始
	ps->size++;
}

在动态分配的一维数组尾部删除元素

相对于插入元素，删除元素没有数组长度是否足够的问题，所以也比较简单。

考虑直接忽略尾部的元素，即对 size 进行减法。有一个需要注意的点就是数组中元素的长度size必须是大于0的，如果小于0那就没意义了，所以如果不增加这个限制条件而对 size 进行减法程序可能会报错。

具体实现如下：

1
2
3
4
5
6
7
8
9

void SeqListPopBack(SL* ps) //尾删
{
	if (ps->size > 0)
	{
		ps->size--;
	}
	//assert(ps->size > 0);
	//ps.size--;
}

如上，还有另外一种写法就是使用assert函数，它表示只有括号内的表达式为真时，程序才会往下执行。