线性表的顺序实现【C语言版的真代码】

线性表

线性表：一个线性表是含n个数据元素的有限序列。

它的逻辑结构要求是线性的，但其存储结构并没有做要求，即逻辑结构类似于如下的表则被称为线性表：

线性表的每个结点都有且仅有一个前驱（前一个）和一个后继（后一个），但它的第一个结点没有前驱，最后一个结点没有后继。

既然它对存储结构未做要求，那么它的存储结构可以采用顺序存储、也可以采用链式存储。因此一个线性表可以顺序实现、也可以链式实现。

采用顺序存储的线性表，被称为顺序表，更为详细一点的逻辑关系：

采用链式存储的线性表，则被称为链表，更为详细一点的逻辑关系：

线性表的第一个数据元素的存储位置，通常称为线性表的起始地址或者基地址。

顺序表

顺序表的概念及其结构

采用顺序存储的线性表即为顺序表，指的是用一组地址连续的存储单元依次存储线性表的数据元素。通俗地来说，就是这些数据元素存放的“位置是相邻的”。

通常情况下使用数组来描述顺序表（数组的逻辑结构是线性的，物理存储采用顺序存储符合顺序表的特点）

//例如
//定长的数组
int arr[10];
//动态开辟的数组
int* arr;
1
2
3
4
5

顺序表可以分为静态顺序表和动态顺序表

• 静态顺序表：采用定长的数组存储数据元素
• 动态顺序表：采用动态开辟的数组存储数据元素

【静态顺序表的定义】
现阶段数据元素的类型并不清楚，在C语言中可以使用类型重定义的方式，便于后续修改。

typedef int ELemType;
ElemType arr[100];
1
2

同理，究竟需要多大的空间我们也并不确定，因此使用宏定义的方式，便于后续修改

#define MAXSIZE 100
typedef int ELemType;
ElemType arr[MAXSIZE];
1
2
3

仅仅这样无法满足我们需求，线性表不仅要支持存储数据，还要能够对数据进行增删查改。如果顺序表内一个元素都不存在了，还要去删除，又或者说顺序表满了，还要去插入数据元素，这样是不可行的。因此我们还需要一个属性去标记它每个时刻所存放的真实数据元素的个数，当要进行删除的时候，就判断一下个数是不是为0，如果不为0的话再进行删除操作，其他操作根据情况来定：

#define MAXSIZE 100
typedef int ELemType;
struct SeqList
{
	ELemType arr[MAXSIZE];
	int size; //记录每个时刻保存的数据元素个数
};
1
2
3
4
5
6
7

此外，如果直接这样，一个顺序表就需要这样定义struct SeqList name。通常会把这个结构体类型进行类型重定义，达到简写的目的：

#define MAXSIZE 100
typedef int ELemType;
typedef struct SeqList
{
	ELemType arr[MAXSIZE];
	int size; //记录每个时刻保存的数据元素个数
}SeqList;
1
2
3
4
5
6
7

【动态顺序表的定义】

typedef int ELemType;
typedef struct SeqList
{
	ElemType* arr;
	int capacity; //记录此时容量大小，以数据元素个数为单位
	int size; //记录每个时刻保存的数据元素个数
}SeqList;
1
2
3
4
5
6
7

数组指针arr指向顺序表的基地址。

静态的顺序表因为其存储空间是静态的，如果开一个很大的空间，可能就会造成浪费，如果一开始开比较小的空间，则可能不够用。因此对于更加高阶一些并且基于线性表的数据结构来说，通常采用的都是动态顺序表。

顺序表基本操作

//线性表的初始化
void SeqListInit(SeqList* seq);
//线性表的销毁
void SeqListDestory(SeqList* seq);
//线性表的尾插
void SeqListPushBack(SeqList* seq, ElemType value);
//线性表的尾删
void SeqListPopBack(SeqList* seq);
//线性表的头插
void SeqListPushFront(SeqList* seq, ElemType value);
//线性表的头删
void SeqListPopFront(SeqList* seq);
//线性表的查找
int SeqListFind(SeqList* seq, ElemType value);
//在pos位置（下标）插入value
void SeqListInsert(SeqList* seq, int pos, ElemType value);
//删除pos位置（下标）的值
void SeqListErase(SeqList* seq, int pos);
//打印顺序表
void SeqListPrint(SeqList seq);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

下面将只介绍几个十分重要的顺序表基本操作

顺序表的初始化

void SeqListInit(SeqList* seq)
{
	seq->arr = NULL;
	seq->size = seq->capacity = 0;
}
1
2
3
4
5

顺序表的插入

顺序表的插入有三种情况：

• 尾插：在顺序表的尾部插入一个数据元素
• 头插：在顺序表的头部插入一个数据元素
• 在任意位置（下标）处插入一个数据元素

【尾插的实现】

void SeqListPushBack(SeqList* seq, ElemType value)
{

}
1
2
3
4

按照逻辑，直接将要插入的数据元素放入数组的尾部。

此时数组尾部的下标就是size的大小，插入之后一定要维护size的值。

void SeqListPushBack(SeqList* seq, SLDataType value)
{
	seq->arr[seq->size] = value;
	seq->size++;
}
1
2
3
4
5

但还可能会遇到顺序表已满的情况，此时就不能够直接进行插入。若顺序表已满，插入前则应该先扩容，再执行上述的逻辑。

那么在进行插入之前，应当先判断顺序表内此刻是否有空间，能够容纳要插入的数据元素。当size和capacity相同的时候，就表示顺序表内没有多余的空间。但还要分成两种情况：
（1）size=capacity=0；顺序表一点容量都没有
（2）size=capacity≠0；顺序表没有多余容量存放其他数据元素

void SeqListPushBack(SeqList* seq, SLDataType value)
{
	if(seq->size == seq->capacity)
	{
		//如果为空，则新容量为4；否则开辟原来的2倍
		//策略可以自行定制，但要注意适当
		int newcapacity = (seq->capacity == 0 ? 4 : seq->capacity * 2);
		ElemType* tmp = (ElemType*)realloc(seq->arr, sizeof(ElemType) * newcapacity);
		if(NULL == tmp)
		{
			printf("扩容失败\n");
			exit(-1);
		}
		seq->arr = tmp;
		seq->capacity = newcapacity;
	}
	seq->arr[seq->size] = value;
	seq->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

【头插的实现】
和尾插类似，在进行插入前需要检查是否还有足够的容量，容纳准备插入的数据元素。为了提高代码的复用率，我们可以将检查容量的工作提取出来，封装成一个方法。

void SeqListCheckCapac(SeqList* seq)
{
	//如果size== capacity说明：数组为空 或者满了；需要扩容
	if (seq->size == seq->capacity)
	{
		int newcapacity = seq->capacity == 0 ? 4 : (seq->capacity * 2);
		ElemType* tmp = (ElemType*)realloc(seq->arr, sizeof(ElemType) * newcapacity);
		if (tmp == NULL)
		{
			printf("扩容失败\n");
			exit(-1);
		}
		seq->arr = tmp;
		seq->capacity = newcapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

优化一下尾插的方法：

void SeqListPushBack(SeqList* seq, ElemType value)
{
	//检查容量
	SeqListCheckCapac(seq);

	seq->arr[seq->size] = value;
	seq->size++;
}
1
2
3
4
5
6
7
8

现在正式开始顺序表头插的实现

void SeqListPushFront(SeqList* seq, ElemType value)
{
	//检查容量
	SeqListCheckCapac(seq);
}
1
2
3
4
5

在顺序表的头部进行插入，若插入位置有数据元素，则应将数据元素往后面挪。但只将插入位置的一个数据元素挪到后面，会把后面的数据元素覆盖掉。因此要从顺序表的尾部开始，依次将数据元素往后挪一个位置。简而言之，就是要给插入的数据元素“腾位置”。

然后插入即可。

void SeqListPushFront(SeqList* seq, ElemType value)
{
	//检查容量
	SeqListCheckCapac(seq);

	int end = seq->size - 1;
	while(end > 0)
	{
		seq->arr[end + 1] = seq->arr[end]
		end--;
	}
	seq->arr[0] = value;
	seq->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

[在任意位置插入]
同样，插入前需要检查容量，并且还需要判断选择插入的位置是否合法，在准许插入的范围之内。

//在pos位置插入value
void SeqListInsert(SeqList* seq, int pos, ElemType value)
{
	//检查容量
	SeqListCheckCapac(seq);
	if(pos < 0 || pos > seq->size)
	{
		printf("试图插入一个非法的位置\n");
		return;
	}
}
1
2
3
4
5
6
7
8
9
10
11

如果不是尾部的插入（当前要插入的位置有数据元素），类似于头插，需要给它“腾位置”，从尾部开始依次往后挪一位。

//在pos位置插入value
void SeqListInsert(SeqList* seq, int pos, ElemType value)
{
	//检查容量
	SeqListCheckCapac(seq);
	if(pos < 0 || pos > seq->size)
	{
		printf("试图插入一个非法的位置\n");
		return;
	}
	int end = seq->size - 1;
	while(end > pos)
	{
		seq->arr[end + 1] = seq->arr[end]
		end--;
	}
	seq->arr[pos] = value;
	seq->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

顺序表的删除

顺序表的删除共有三种删除方式：

• 尾删：删除顺序表尾部的一个数据元素；
• 头删：删除顺序表头部的一个数据元素；
• 删除顺序表任意位置的一个数据元素

【尾删的实现】
尾删的基本做法：将尾部的位置置为初始值，同时size的大小减去1；
但对于我们的角度来说，只要访问不到这个位置，那么就认为这个位置不存在真实的数据元素。根据整个代码的逻辑来看，只需要将描述顺序表内真实数据元素个数的size，减去1即可。

void SeqListPopBack(SeqList* seq)
{
	seq->size--;
}
1
2
3
4

设想顺序表内没有数据元素了，却仍然要去执行删除的操作，那么必定不能够删除。因此在执行删除操作之前，还需判断顺序表内是否存在数据元素。此处可采用稍暴力的方式“断言”

void SeqListPopBack(SeqList* seq)
{
	assert(seq->size > 0);
	seq->size--;
}
1
2
3
4
5

【头删的实现】
同尾删一样，删除前需要检查顺序表内是否存在数据元素。

void SeqListPopFront(SeqList* seq)
{
	assert(seq->size > 0);
}
1
2
3
4

（1）若删除位置后面不存在数据元素，可直接将size的值减去1即可；
（2）若删除位置后面存在数据元素，将后面的值依次挪到前面，将要删除位置的数据元素进行覆盖，再将size的值减去1即可。

void SeqListPopFront(SeqList* seq)
{
	assert(seq->size > 0);
	int end = 0;
	while (end < seq->size)
	{
		seq->arr[end] = seq->arr[end + 1];
		end++;
	}
	seq->size--;
}
1
2
3
4
5
6
7
8
9
10
11

【任意位置的删除】
类似于头删，若后面存在数据元素，则将删除位置后面的数据元素依次挪动即可，若不存在数据元素就无需挪动，再将顺序表size的值减去1即可。

void SeqListErase(SeqList* seq, int pos)
{
	assert(seq->size > 0 && pos >=0 && pos < seq->size);

	int end = pos;
	while (end < seq->size)
	{
		seq->arr[end] = seq->arr[end + 1];
		end++;
	}
	seq->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

顺序表的查找

由于顺序表采用数组实现，那么它就支持随机访问。因此要查找一个数据元素时，只需要依次去比较，如果找到了符合的，返回对应的下标即可。否则返回-1，表示该顺序表内不存在这样的数据元素。

int SeqListFind(SeqList* seq, ElemType value)
{
	for (int i = 0; i < seq->size; i++)
	{
		if (value == seq->arr[i])
		{
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11