文章目录
1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
2.顺序表
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
- 静态顺序表：使用定长数组存储元素。
- 动态顺序表：使用动态开辟的数组存储
2.2 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。
#pragma once
#include<stdio.h>
#include<assert.h>
typedef int SLDataType;
typedef struct SeqList
{
int* a;
int size; //存储数据个数
int capacity;//存储空间大小
}SeqList;
void SeqListInit(SeqList* psl);//初始化
void SeqListDestroy(SeqList* psl);//销毁
void SeqListPrint(SeqList* psl);//打印
void SeqListCheckCapacity(SeqList* psl);//检查容量
int SeqListFind(SeqList* psl, SLDataType x);//查找
//时间复杂度是O（1）
void SeqListPushBack(SeqList* psl, SLDataType x);//尾插
void SeqListPopBack(SeqList* psl);//尾删
//时间复杂度是O（N）
void SeqListPushFront(SeqList* psl, SLDataType x);//头插
void SeqListPopFront(SeqList* psl);//头删
//时间复杂度是O（N）
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);//在pos位置插入
void SeqListErase(SeqList* psl, size_t pos);//在pos位置删除
2.2.1初始化
就是将元素分别初始化。
//初始化
void SeqListInit(SeqList* psl)
{
assert(psl);
psl->a = NULL;
psl->size = 0;
psl->capacity = 0;
}
2.2.2 检查容量
初始化时容量为0，想要放数据得增加容量，每次插入数据也得保证容量充足，为了方便，我们先写一个用于检查容量并增容的函数。
//检查容量
void SeqListCheckCapacity(SeqList* psl)
{
assert(psl);
//如果满了，就要扩容
if (psl->size == psl->capacity)
{
size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//防止一开始capacity=0无法*2增容
SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity = newCapacity;
}
}
}
2.2.3 顺序表打印
就是遍历一次把所有元素打印出来，这样可以检查函数写的是否正确，及时订正。
//打印
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
2.2.4 顺序表尾插
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
assert(psl);
//如果满了，就要扩容
SeqListCheckCapacity(psl);
psl->a[psl->size] = x;
psl->size++;
}
2.2.5 顺序表尾删
只需要把size-1这样的话下一个数据就会把尾部数据覆盖掉，达到删除的效果。
//尾删
void SeqListPopBack(SeqList* psl)
{
assert(psl);
if (psl->size > 0)
{
psl->size--;
}
}
2.2.6 顺序表头插
//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
//如果满了，就要扩容
SeqListCheckCapacity(psl);
//挪动数据,腾出头部位置
int end = psl->size - 1;
while (end >= 0)
{
psl->a[end + 1] = psl->a[end];
end--;
}
psl->a[0] = x;
psl->size++;
}
2.2.7 顺序表头删
将第一个位置覆盖掉，然后用尾删的思路将最后一个数据删除。
//头删
void SeqListPopFront(SeqList* psl)
{
assert(psl);
//挪动数据覆盖第一个
if(psl->size>0)
{
int begin = 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
begin++;
}
}
psl->size--;
}
2.2.8 顺序表在pos位置插入x
思路跟头插很像,但内含陷阱！
//在pos位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
assert(psl);
//如果满了，就要扩容
SeqListCheckCapacity(psl);
温和检测
//if (pos > psl->size)
//{
// printf("pos越界：%d\n", pos);
// return;
//}
//暴力检测
assert(pos <= psl->size);
//pos=0的时候由于无符号整型判断时的整型提升，会出问题
//size_t end = psl->size - 1;
//while (end >= pos)
//{
// psl->a[end + 1] = psl->a[end];
// end--;
//}
//psl->a[pos] = x;
//psl->size++;
//这样写才不会有问题
size_t end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end - 1];
--end;
}
psl->a[pos] = x;
psl->size++;
}
2.2.9 顺序表删除pos位置的值
思路跟头删很像
//在pos位置删除
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos < psl->size);
size_t begin = pos + 1;
while (begin < psl->size)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
psl->size--;
}
2.2.10 尾插、尾删、头插、头删的改进
有了上面两个通常情况下的增删函数，我们就能改进尾插、尾删、头插、头删。这样能够快速写完顺序表
//尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
SeqListInsert(psl, psl->size, x);//在size位置插入数据
}
//尾删
void SeqListPopBack(SeqList* psl)
{
assert(psl);
SeqListErase(psl, psl->size-1);//在size-1位置删除数据
}
//头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
assert(psl);
SeqListCheckCapacity(psl);
SeqListInsert(psl, 0, x);//在0位置插入数据
}
//头删
void SeqListPopFront(SeqList* psl)
{
assert(psl);
SeqListErase(psl, 0);//在0位置删除数据
}
2.2.11 顺序表查找
遍历一遍，一个个找
int SeqListFind(SeqList* psl, SLDataType x)
{
assert(psl);
for (int i = 0; i < psl->size; ++i)
{
if (psl->a[i] == x)
{
return i;
}
}
return -1;
}
2.2.12 顺序表销毁
最后的最后，一定要养成好习惯，不要忘记销毁之前申请的空间，防止内存泄漏。
//销毁
void SeqListDestroy(SeqList* psl)
{
free(psl->a);
psl->a = NULL;
psl->capacity = 0;
psl->size = 0;
}
2.3 数组相关面试题
-
删除排序数组中的重复项。26. 删除有序数组中的重复项.
-
原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。27. 移除元素.
-
合并两个有序数组。88. 合并两个有序数组.
2.4 顺序表的问题及思考
问题：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢？下期会给出了链表的结构，现在大家可以想想链表会如何解决这些问题。