数据结构——线性表之顺序表

一、顺序表的定义

顺序表是线性表结构当中的一种。它是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。它的优点有以下几个：可以依靠数组的下标，对数组存放的数据进行随机的访问。但是它的缺点也比较明显，那就是在增加和删除数据时要进行多次的挪动数据，会造成一定的时间复杂度的浪费。

二、顺序表的定义

(一)、顺序表的实现方式

顺序表的实现方式一般有两种，一种是静态存储，一种是动态存储。静态存储是指使用定长数组存储元素。这类方法的实现，有许多的局限性，例如在增加较多的数据，可能会导致出现数组存储空间不够的情况。所以我们一般采用动态存储的方法进行实现。但是为了本文的完整性，下面我也会给出静态存储的实现方法。

①、静态存储

#define N 20
typedef int SLDataType;
//静态实现
typedef struct SeqList
{
	SLDataType a [20];
	int size;
}SL;
1
2
3
4
5
6
7
8

②、动态存储

动态存储，顾名思义是使用动态开辟的数组存储。根据用户的使用需求随时随地的动态的开辟内存空间。用到的函数有malloc和realloc等。其实现方法如下：

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;
	int size;
	int capacity;
};

1
2
3
4
5
6
7
8

（二）、顺序表的初始化

对顺序表进行初始化，利用malloc函数动态开辟内存空间。这里需要注意的是malloc函数的使用方法。

//顺序表的初始化
void SLInit(SL* psl)
{
	psl->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (psl->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->capacity = 4;
	psl->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

（三）、顺序表的销毁

顺序表的销毁是指对maiiloc以及下文的realloc函数动态开辟的内存空间进行销毁，并将psl->a置为空，防止空指针的出现。

//顺序表的销毁
void SLDestory(SL* psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->capacity = 0;
	psl->size = 0;
}
1
2
3
4
5
6
7
8

（四）、顺序表的打印

顺序表的打印操作非常简单，易于实现，就是对数组进行遍历操作。

//顺序表的打印
void SLprint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("\n");
}

1
2
3
4
5
6
7
8
9
10
11

（五）、顺序表的扩容

顺序表的扩容是指当psl->size==psl->capacity时，数组的存储空间不够，因此便需要利用realloc重新申请内存空间，以满足插入数据的需求。这里需要注意的便是realloc函数的使用方法。

//顺序表的扩容
void SLCheckcapacity(SL* psl)
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		SLDataType* tmp = (SLDataType*)realloc(psl->a, sizeof(SLDataType) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror("reallc fail");
			return;
		}
		psl->a = tmp;
	}
	psl->capacity *= 2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(六)、顺序表的尾插

我们直接在数组的尾部，即psl->size位置进行插入数据操作即可，不需要挪动数据。

//顺序表的尾插
void SLPushBack(SL* psl, SLDataType x)
{
	assert(psl);
	SLCheckcapacity(psl);
	psl->a[psl->size] = x;
	psl->size++;
}
1
2
3
4
5
6
7
8

（七）、顺序表的头插

首先我们需要先明确，头插的意义，头插即在数组的首元素位置进行插入数据操作，那么我们就需要挪动数据，并且是从后往前挪动数据内容，因为从前往后挪动数据，会覆盖数据内容，所以我们可以在psl->end-1的位置定义一个end,让psl->a[end + 1] = psl->a[end ]，这样便实现了数据的挪动。这个接口我们需要注意的是while的循环条件，通过画图我们不难可以看出循环的终止条件便是（end>=0）

//顺序表的头插
void SLPushFront(SL* psl, SLDataType x)
{
	assert(psl);
	SLCheckcapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end ];
		end--;
	}
	psl->a[0] = x;
	psl->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（八）顺序表的尾删

尾删操作的实现最为简单，直接让psl->size–即可。

//顺序表的尾删
void SLPopBack(SL* psl)
{
	assert(psl);
	if (psl->size == 0)
	{
		return;
	}
	psl->size--;
}
1
2
3
4
5
6
7
8
9
10

(九)、顺序表的头删

头删样也需要挪动数据，但是和头插不一样的是，这次的挪动数据是从前往后进行挪动的，目的便是对数组的首元素进行覆盖操作。所以我们可以定义start=1.因为数组的下标是从零开始的，所以我们让psl->a[start - 1] = psl->a[start]，这样数组便开始了数据的挪动操作。这里我们通过画图可以很清楚的知道循环最终结束的落点位置是在psl->size-1处。

//顺序表的头删
void SLPopFront(SL* psl)
{
	assert(psl);
	int start = 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	psl->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

（十）、顺序表的按位置插入

顺序表的按位置插入操作是指在数组的任意位置插入元素，首先我们需要判断用户输入的pos值的合法性，接着我们需要对pos进行减一操作，因为数组的元素下标是从0开始的，然后便是进行数据的挪动和循环挪动的条件的判断，通过画图我们便可以很清晰的判断出来。。

//顺序表的按位置插入
void SLInsert(SL* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos <=psl->size);
	SLCheckcapacity(psl);
	pos = pos - 1;//数组下标从零开始
	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->a[end + 1] = psl->a[end];
		end--;
	}
	psl->a[pos] = x;
	psl->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（十一）、顺序表的按位置删除

同理和上文的按位置插入操作类似，在此就不一一赘述，通过画图可以非常简单的额分析处理，得到答案。

//顺序表的按位置删除
void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	pos = pos - 1;//数组下标从零开始
	int start = pos + 1;
	while (start < psl->size)
	{
		psl->a[start - 1] = psl->a[start];
		start++;
	}
	psl->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（十二）、顺序表的按值查找

/顺序表的按值查找
//找到返回下标，没有找到返回-1
int SLFind(SL* psl, SLDataType x)
{
	assert(psl);
	int i = 0;
	for (i = 0; i < psl->size; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（十三）、顺序表的按位置修改

void SLModify(SL* psl, int pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos < psl->size);
	psl->a[pos] = x;

}
1
2
3
4
5
6
7