【数据结构】线性表——顺序表

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线（如图一）。但是在物理结构上并不一定是连续的（如图二）。线性表在物理上存储时，通常以数组和链式结构的形式存储。(假设在32位机器上)

二、顺序表

2.1概念及结构

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

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。（如下图）

2. 动态顺序表：使用动态开辟的数组存储。

说白了顺序表就是数组😆没想到把~意不意外
虽说顺序表就是数组，但是也不能说顺序表没用，在高级的储存单元里面（如二叉树）底层就是使用顺序表的。

2.2、顺序表接口实现

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

2.2.1、顺序表的动态存储

函数命名规则借鉴CPP的stl库进行命名。

首先创建一个结构体，用于储存顺序表结构。

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

• typedef int SLDateType;把顺序表结构的类型重命名为：SLDateType。若将来如果要改变数据顺序表内容的结构类型。可以极为方便的改变。
• 在结构体中定义了。顺序表的总体大小和当前容量。以便确认是否需要扩容。
• 定义的SLDateType*用于接收动态开辟的内存。
• size是顺序表的大小。
• capacity是顺序表当前的元素数量。

2.2.2、顺序表初始化

void SeqListInit(SeqList* ps) {
	
	SLDateType* arr = (SLDateType*)malloc(sizeof(SLDateType) * 2);
	if (arr == NULL) {
		perror("malloc in SeqListInit of arr::");
	}
	ps->a = arr;
	ps->size = 2;
	ps->capacity = 0;
}

• 因为顺序表的结构体是没有进行内存划分的。所以需要把顺序表的结构体进行初始化。
• 默认开辟两个空间。
• 在成功开辟后。把size设置为2。capacity设置为0。

2.2.3、检查空间判断进行增容

void CheckCapacity(SeqList* ps) {
	if (ps->capacity == ps->size) {
		SLDateType* arr = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->size * 2);
		if (arr == NULL) {
			perror("realloc in SeqListPushBack");
		}
		ps->a = arr;
		ps->size *= 2;
	}
}

• 每次进行插入都需要判断空间是否足够，所以，需要提前完成检查空间函数。
• 每次扩容扩二倍。

2.2.4、顺序表尾插、尾删

void SeqListPushBack(SeqList* ps, SLDateType x) {
	assert(ps);
	CheckCapacity(ps);
	//int i = ps->capacity;
	(ps->a)[ps->capacity] = x;
	ps->capacity++;
}

• 与数组的插入，并无二意。

void SeqListPopBack(SeqList* ps) {
	assert(ps && ps->capacity);
	ps->capacity--;
}

• 只要把当前数据。进行减减。无需把顺序表中的内容进行删除。因为再次尾插数据，就会把之前的数据覆盖。

2.2.5、顺序表头插、头删

void SeqListPushFront(SeqList* ps, SLDateType x) {
	assert(ps);

	CheckCapacity(ps);


	memmove(((ps->a) + 1), ps->a, sizeof(SLDateType) * ps->capacity);
	ps->a[0] = x;
	ps->capacity++;
}

• 顺序表的头插需要把全部数据往后移动一位。
• 移动完成后就插入数据到头部空位。

void SeqListPopFront(SeqList* ps) {
	assert(ps && ps->capacity);
	ps->capacity--;
	memmove(ps->a, ((ps->a) + 1), sizeof(SLDateType) * ps->capacity);
}

• 头删只需要把后面一位的数据全部往前移动一位。即可覆盖首元素的数据。

2.2.6、顺序表查找

int SeqListFind(SeqList* ps, SLDateType x) {
	assert(ps && ps->capacity);
	for (int i = 0; i < ps->capacity; i++) {
		if (ps->a[i] == x) {
			return i;
		}
	}
	return -1;
}

• 与数组查找数据一样，循环遍历即可。

2.2.7、顺序表在pos位置插入x

void SeqListInsert(SeqList* ps, int pos, SLDateType x) {
	assert(ps && ps->capacity);

	CheckCapacity(ps);

	memmove(ps->a + pos, ps->a + pos - 1, sizeof(SLDateType) * (ps->capacity - pos + 1));
	ps->a[pos - 1] = x;
	ps->capacity++;
}

• 找到对应位置后，从当前位置位置到数据结尾的内容全部向后移动一位。然后再在该位置进行数据的赋值。

2.2.8、顺序表删除pos位置的值

void SeqListErase(SeqList* ps, int pos) {
	assert(ps && ps->capacity);
	memmove(ps->a + pos - 1, ps->a + pos, sizeof(SLDateType) * (ps->capacity - pos + 1));
	
	ps->capacity--;

}

• 找到需要删除的pos位置后。把pos后一位的内容全部向前移动一位即可把pos值原先的内容覆盖。做到删除pos位置的值。

2.2.9、顺序表销毁

void SeqListDestroy(SeqList* ps) {
	assert(ps && ps->a);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

• 直接把动态开辟的内存释放掉，然后再把ps结构体中全部内容赋为空或零值。

2.2.10、顺序表打印

void SeqListPrint(SeqList* ps) {
	assert(ps && ps->a);
	for (int i = 0; i < ps->capacity; i++) {
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

• 与数组的循环打印并无二样。
• 把循环结束条件定为capacity，这样做可以把尾删的数据不再打印数据中。

三、顺序表的劣势

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

以上就是本章所有内容。若有勘误请私信不才。万分感激💖💖 如果对大家有帮助的话，就请多多为我点赞收藏吧~~~💖💖

ps:表情包来自网络，侵删🌹