顺序表的模拟实现

1.线性表

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

  线性表在逻辑结构是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

💡ps：

  逻辑结构：想象的该数据结构在内存中的存储方式，逻辑结构便于我们的思考。

  物理结构：实际的该数据结构在内存中的存储方式。

例如，C语言中的二维数组int arr[M][N]：

逻辑结构：M行，N列的元素集合，不是连续存放的

物理结构：1行，M*N列的元素集合，是连续存放的

线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1概念结构

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

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。(静态数组)

   

2. 动态顺序表：使用动态开辟的数组存储。(malloc动态开辟空间)

   

    

2.2顺序表的模拟实现

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

SeqList.h中的声明(因为需要通过函数来修改顺序表，所以要传址)

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDateType;//顺序表的成员
typedef struct SeqList
{SLDateType* a;//顺序表的首元素地址size_t size;//顺序表的数据个数size_t capacity;//顺序表的容量
}SL;void SLInit(SL* ps);//顺序表的初始化void SLDestroy(SL* ps);//顺序表的销毁//尾部操作
void SLPushBack(SL* ps, SLDateType x);//尾插
void SLPopBack(SL* ps);//尾删//头部操作
void SLPushFront(SL* ps, SLDateType x);//头插
void SLPopFront(SL* ps);//头删//中间
size_t SLFind(SL* ps, SLDateType x);//查找(返回下标)
void SLInsert(SL* ps, size_t pos, SLDateType x);//在pos前插入数据x
void SLErase(SL* ps, size_t pos);//删除pos处的数据void SLPrint(SL* ps);//打印顺序表

SeqList.c结构功能实现：

包含头文件#include"SeqList.h"

2.2.1顺序表的初始化

void SLInit(SL* ps)//顺序表的初始化
{assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}

2.2.2顺序表的销毁

💡ps：由于是动态开辟的空间，使用完要还给操作系统，不然会造成内存泄漏。

void SLDestroy(SL* ps)//顺序表的销毁
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}

2.2.3尾插数据

void Enhance(SL* ps)
{size_t newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;//如果容量为0，开辟4，否则两倍开辟SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType)*newcapacity);//这里要考虑异地增容的情况if (tmp == NULL)//增容失败{perror("realloc fail\\n");return;}else{ps->a = tmp;ps->capacity = newcapacity;}
}void SLPushBack(SL* ps, SLDateType x)//尾插
{assert(ps);//防止ps为空，进行断言//考虑增容if (ps->size == ps->capacity)//空间不足时需要增容{Enhance(ps);}ps->a[ps->size++] = x;
}

💡ps：顺序表插入操作都要检查是否需要增容

时间复杂度：O(1)

2.2.4尾删数据

void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps->size > 0);//顺序表为空，则不可继续再删除--(ps->size);
}

💡ps：顺序表的删除操作都要检查是是否为空顺序表

时间复杂度：O(1)

2.2.5头插数据

void SLPushFront(SL* ps, SLDateType x)//头插
{assert(ps);//考虑增容if (ps->size == ps->capacity){Enhance(ps);}//挪动数据size_t end = ps->size;while (end > 0){ps->a[end] = ps->a[end - 1];--end;}//插入数据ps->a[end] = x;++(ps->size);
}

💡ps：由于顺序表是连续存储的，在头部插入数据时，需要将整体数据向后挪动一次，再将数据插入到头部

时间复杂度：O(N)

2.2.6头删数据

void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps->size > 0);//挪动数据--(ps->size);size_t begin = 0;while (begin < ps->size){ps->a[begin] = ps->a[begin + 1];++begin;}}

💡ps：头删数据，将后面的数据向前移动，将第一个数据覆盖即可

时间复杂度：O(N)

2.2.7中间插入数据

void SLInsert(SL* ps, size_t pos, SLDateType x)//中间插
{assert(ps);assert(pos >= 0 && pos <= ps->size);//==0是头插，等于ps->size是尾插//考虑增容if (ps->size == ps->capacity){Enhance(ps);}//挪动数据size_t cur = ps->size;while (cur > pos){ps->a[cur] = ps->a[cur - 1];--cur;}//插入ps->a[cur] = x;++(ps->size);}

💡ps：中间插入数据，同样也需要向后挪动数据

时间复杂度：O(N)

2.2.8中间删除数据

void SLErase(SL* ps, size_t pos)//中间删
{assert(ps);assert(pos >= 0 && pos < ps->size);//等于0相等于头删，等于ps->size-1等于尾删//assert(ps->size > 0);//对pos的检查，间接检查了size要大于0--(ps->size);size_t cur = pos;while (cur < ps->size){ps->a[cur] = ps->a[cur + 1];++cur;}
}

💡ps：中间删除数据，同样也需要向前挪动数据

时间复杂度：O(N)

2.2.9打印顺序表

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

2.2.10查找数据

size_t SLFind(const SL* ps, SLDateType x)//查找(返回下标)
{assert(ps);for (size_t i = 0; i < ps->size; ++i){if (ps->a[i] == x){return i;}}return EOF;//找不到
}

2.2.11复用Insert和Erase实现尾部操作和头部操作

Insert和Erase功能中是包含了尾部操作和头部操作的，所以尾部操作和头部操作可以使用Insert和Erase来复用

void SLPushBack(SL* ps, SLDateType x)//尾插
{SLInsert(ps, ps->size, x);
}void SLPopBack(SL* ps)//尾删
{SLErase(ps, ps->size - 1);
}void SLPushFront(SL* ps, SLDateType x)//头插
{SLInsert(ps, 0, x);
}void SLPopFront(SL* ps)//头删
{SLErase(ps, 0);
}

2.3顺序表的优缺点

优点：

1. 尾插和尾删的效率很高，时间复杂度为：O(1)
2. 支持随机访问，知道了一个元素的下标，就可以直接访问和修改

缺点：
1. 头部操作和中间操作中，需要挪动数据，时间复杂度为：O(N)，效率较低
2. 增容会带来一定的性能消耗，特别是异地增容，代价是极大的
3. 2倍增容方式，会有一部分的空间浪费

3.顺序表OJ题目训练

1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。OJ链接
2. 删除排序数组中的重复项。OJ链接
3. 合并两个有序数组。OJ链接