【数据结构】——顺序表详解

大家好！当我们学习了动态内存管理后，就可以写一个管理数据的顺序表了！！！

顺序表的理解：

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

静态顺序表就是像数组一样的大小固定的，动态的可以在容量不够时进行扩容而达到能够存储大量数据的效果！！！

一、先创建一个结构体来表示顺序表

typedef int DATE;//重命名顺序表的数据类型
typedef struct ArrayList {
	DATE* date;
	size_t size;//顺序表长度
	size_t capacity;//顺序表容量
}AL;

1
2
3
4
5
6
7

二、顺序表的所有接口展示

void Init(AL* al);
void checkCapacity(AL* al);
void pushBack(AL* al, DATE info);
void pushFront(AL* al, DATE info);
void insertDate(AL* al,size_t pos, DATE info);
void printDate(AL* al);
void Erase(AL* al, size_t pos);
void PopBack(AL* al);
void PopFront(AL* al);
size_t FindDate(AL* al, DATE info);
void ExchangeDate(AL* al, size_t pos, DATE info);
void Deatory(AL* al);
1
2
3
4
5
6
7
8
9
10
11
12

三、每个接口功能介绍及实现原理

1、初始化函数的实现

void Init(AL* al)
{
	assert(al);
	al->size = 0;
	al->capacity = 4;//初始化容量为4
	DATE* tmp = (DATE*)malloc(sizeof(DATE) * al->capacity);
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	al->date = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

初始化顺序表的长度为0、容量为4！

2、检查容量函数的实现

void checkCapacity(AL* al)
{
	if (al->size == al->capacity)
	{
		DATE* tmp = (DATE*)realloc(al->date, sizeof(DATE) * al->capacity*2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		al->capacity *= 2;
		al->date = tmp;
		printf("扩容成功！\n");
	}
}

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

如果长度等于容量时就说明需要扩容了，就将容量扩到2倍大小

3、尾插函数的实现

void pushBack(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	al->date[al->size] = info;
	al->size++;
}
1
2
3
4
5
6
7

每次插入之前一定要检查容量
尾插就是在size尾位置写入需要插入的值，然后要对长度进行加一

4、头插函数的实现

void pushFront(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	if (al->size == 0)
	{
		al->date[0] = info;
		al->size++;
	}
	else
	{
		size_t end = al->size;
		while (end)
		{
			al->date[end] = al->date[end-1];
			end--;
		}
		al->date[0] = info;
		al->size++;
	}
}

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

头插一个数据，必须将后面的数据向后面移动，移动的过程中可能超过容量大小，所以在插入时都需要进行扩容判断

挪动方法如上

5、尾删函数

void PopBack(AL* al)
{
    assert(ps);
	assert(al->size > 0);
	al->size--;
}
1
2
3
4
5
6

将长度减一即可删除最后一个数据

6、头删函数

void PopFront(AL* al)
{
    assert(al->size > 0);
	int begin = 1;
	while (begin<al->size)
	{
		al->date[begin - 1] = al->date[begin];
		begin++;
     }
	al->size--;
}
1
2
3
4
5
6
7
8
9
10
11

挪动顺序方法如下：

定义一个变量begin=1,首先是要将数据2移动到数据1的位置，对应的操作是
al->date[begin - 1] = al->date[begin];然后begin++,依次将数据3挪到数据2的位置，数据4挪到数据3的位置。循环最后一次是将数据5挪到数据4的位置，也就是begin=4,al->size=5.则循环判断条件为beginsize,循环结束后将
al->size–;

7、任意位置删除数据函数的实现

void Erase(AL* al, size_t pos)
{
	assert(al);
	assert(pos >= 0 && pos <= al->size);
	if (al->size == 0)
	{
		printf("暂无数据！！\n");
		return;
	}
	size_t end = pos;
	while (end<al->size-1)
	{![在这里插入图片描述](https://img-blog.csdnimg.cn/a1a63c6776c142eeb77e15536b8f9a53.png#pic_center)

		al->date[end] = al->date[end + 1];
		end++;
	}
	al->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

删除一个数据，就要将这个位置之后的元素全部向前挪动一个位置
由于下标易班都有size_t表示，所以一个要把握好头删时出现无符号-1和0循环条件比较大小的情况

如果我们要删除数3，然后数据3后面的数据向前挪动，第一步就是将数据4移动到数据3的位置，定义一个变量end=pos=2;对应的操作为al->date[end] = al->date[end+1];，然后end++;将数据5移动到最开始数据4的地方。最后一次循环是将数据5移动到数据4的地方，也就是end最后等于3，al->size=5，则循环判断条件是end< al->size-1,循环结束将al->size–;

8、任意位置插入数据函数的实现

void insertDate(AL* al, size_t pos, DATE info)
{
	assert(al);
	assert(pos >= 0 && pos <= al->size);
	checkCapacity(al);
	int end = al->size;
	while (end > pos)
	{
		al->date[end] = al->date[end - 1];
		end--;
	}
	al->date[pos] = info;
	al->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

由于下标易班都有size_t表示，所以一个要把握好头插时出现无符号-1和0循环条件比较大小的情况

任意位置插入需要将插入位置及其以后的数据一次向后挪动一个位置！

9、头插头删和头删尾删函数的改进

我们写完任意插和任意删后，就可以对头插头删和头删尾删函数的改进，直接在他们的函数体里面调用任意插入和任意删除函数

void pushFront(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	if (al->size == 0)
	{
		al->date[0] = info;
		al->size++;
	}
	else
	{
		insertDate(al, 0, info);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

void pushBack(AL* al, DATE info)
{
	assert(al);
	checkCapacity(al);
	insertDate(al, al->size, info);
}
1
2
3
4
5
6

void PopBack(AL* al)
{
	assert(al);
	if (al->size == 0)
	{
		printf("暂无数据！！\n");
		return;
	}
	Erase(al, al->size);

}
1
2
3
4
5
6
7
8
9
10
11

void PopFront(AL* al)
{
	assert(al);
	if (al->size == 0)
	{
		printf("暂无数据！！\n");
		return;
	}
	Erase(al, 0);
}
1
2
3
4
5
6
7
8
9
10

头插就是调用insert函数在0位置插入
尾插就是调用insert函数在size位置插入
头删就是调用Erase函数删除0位置
尾删就是调用Erase函数删除size位置

10、查找数据函数实现

size_t FindDate(AL* al, DATE info)
{
	assert(al);
	for (size_t i = 0; i < al->size; i++)
	{
		if (al->date[i] == info)
			return i;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10

依次便利顺序表，如果找到需要查找的数据，咋返回其下标，否则返回-1

11、修改数据

void ExchangeDate(AL* al, size_t pos, DATE info)
{
	assert(al);
	assert(pos >= 0 && pos <= al->size);
	al->date[pos] = info;
}

1
2
3
4
5
6
7

先查找要修改的数据是否存在，然后进行修改
他一般会和查找函数配合使用

12、销毁顺序表

由于顺序表开辟了堆区内存，所以我们在使用完顺序表后一定要对开辟的内存进行释放！

void Deatory(AL* al)
{
	assert(al);
	free(al->date);
	al->date=NULL;
	al->capacity = al->size = 0;
}
1
2
3
4
5
6
7

销毁一个顺序表，将顺序表的容量置为0，顺序表的有效数据个数置为0，将date指针所指向的动态开辟的内存空间释放了，由于释放了动态开辟的内存空间，所有p指向的空间未初始化，date成为野指针，为了防止野指针，将date置为空指针。

数据结构篇之——顺序表的分享到这里就结束了，感谢大家的浏览访问！！！