【数据结构：顺序表】

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

• 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
• 线性表在逻辑上是线性结构（连续），也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
• 线性表在物理上存储时，通常以数组和链式结构的形式存储。

顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删改查。
顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用动态开辟的数组存储。

• 静态顺序表只适用于确定知道需要存多少数据的场景。
• 静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
• 所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小。

所以下面我们实现动态顺序表：

1.1 顺序表结构的定义

静态

#define N 10
typedef int SLDataType;
typedef struct SeqList
{
	int size;//有效数据的个数
	SLDataType arr[N];//指向开辟的数组
}SeqList;
1
2
3
4
5
6
7

动态

//动态顺序表
typedef int SLDataType;
typedef struct SeqList
{
	int size;//已存储数据的个数
	int capacity; //容量
	SLDataType* arr;//指向动态开辟的数组
}SeqList;
1
2
3
4
5
6
7
8

1.2 初始化顺序表

• 将顺序表中的元素全部置为0

void InitSeqList(SeqList* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
1
2
3
4
5
6
7

1.3 检查顺序表空间

如果满了，进行扩容

• 若是第一次扩容，直接开辟一定数量的空间
• 若不是第一次，则开辟当前空间的二倍
• 注意realloc函数的使用
• 要修改顺序表的容量

void CheckCapcity(SeqList* ps)
{
	assert(ps);
	//存储的数据和容量相等了，增加容量
	if (ps->capacity == ps->size)
	{
		//若起始容量为0，则将容量设置为4，否则二倍的形式错容；
		int newCapacity = ps->capacity == 0 ? 4 : (2 * ps->capacity);

		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("CheckCapcity():realloc()");
			return;
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.4 打印

//打印
void SeqListPrint(SeqList* ps)
{
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10

1.5 尾插

• 将数据存进arr中即可

//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	//先检查当前容量
	CheckCapcity(ps);
	//插入
	ps->arr[ps->size] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10

1.6 头插

• 先检查容量
• 旧数据往后挪一位
• 0位置放新数据

//头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	//先检查容量
	CheckCapcity(ps);
	//旧数据往后挪
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.7 尾删

• 数组得有数据
• 直接将数组的个数减小

//尾删
void SeqListPopBack(SeqList* ps)
{
	assert(ps);
	//得有数据
	assert(ps->size);
	//ps->arr[ps->size - 1] = -1;
	ps->size--;
}
1
2
3
4
5
6
7
8
9

1.8 头删

• 后面的数据往前挪，覆盖前面的
• 个数减一

//头删
void SeqListPopFront(SeqList* ps)
{
	assert(ps);
	assert(ps->size);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.9 查找

//查找
int SeqListFind(SeqList* ps, SLDataType x)
{
	assert(ps);

	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.10 指定位置插入

• 指定位置合理
• 检查容量
• pos及之后数据往后挪

// 在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDataType x)
{
	assert(ps);
	//位置合理
	assert(pos >= 0 && pos <= ps->size);
	CheckCapcity(ps);
	int i = 0;
	//pos及之后的数据往后挪
	for (i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.11 删除指定位置数据

• 将pos位置后的数据往前挪
• 注意边界

// 删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1]; //arr[size-2] = arr[size - 1]
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.12 销毁顺序表

• 将顺序表中为数组动态开辟的空间释放，置空
• 其它置为0

void SeqListDestory(SeqList* ps)
{
	assert(ps);
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8
9
10
11

顺序表就到这里啦~