数据结构 · 线性表 | 顺序表

啊我摔倒了..有没有人扶我起来学习….

👱个人主页：

《

C

G

o

d

的

个

人

主

页

》

\color{Darkorange}{《CGod的个人主页》}

《CGod的个人主页》交个朋友叭~

💒个人社区：

《

编

程

成

神

技

术

交

流

社

区

》

\color{Darkorange}{《编程成神技术交流社区》}

《编程成神技术交流社区》加入我们，一起高效学习，收割好Offer叭~

🌱刷题链接：

《

L

e

e

t

C

o

d

e

》

\color{Darkorange}{《LeetCode》}

《LeetCode》快速成长的渠道哦~

目录

• 前言
• 顺序表
• • 1.1概念及结构
  • 1.2 接口实现
  • 1.3 顺序表的问题及思考

前言

• 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
• 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，

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

  

顺序表

1.1概念及结构

• 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存

  储。在数组上完成数据的增删查改

  顺序表一般可以分为：

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

     

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

     

1.2 接口实现

• 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空

  间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间

  大小

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

typedef int SLDataType;// 顺序表的动态存储typedef struct SeqList{	SLDataType* array;  // 指向动态开辟的数组	size_t size;       // 有效数据个数	size_t capicity;   // 容量空间的大小}SeqList;// 基本增删查改接口// 顺序表初始化void SeqListInit(SeqList* psl);// 检查空间，如果满了，进行增容void CheckCapacity(SeqList* psl);// 顺序表尾插void SeqListPushBack(SeqList* psl, SLDataType x);// 顺序表尾删void SeqListPopBack(SeqList* psl);// 顺序表头插void SeqListPushFront(SeqList* psl, SLDataType x);// 顺序表头删void SeqListPopFront(SeqList* psl);// 顺序表查找int SeqListFind(SeqList* psl, SLDataType x);// 顺序表在pos位置插入xvoid SeqListInsert(SeqList* psl, size_t pos, SLDataType x);// 顺序表删除pos位置的值void SeqListErase(SeqList* psl, size_t pos);// 顺序表销毁void SeqListDestory(SeqList* psl);// 顺序表打印void SeqListPrint(SeqList* psl);

2. 具体实现：

//初始化void SeqListInit(SL* psl){    assert(psl);    psl->a = NULL;    psl->size = psl->capacity = 0;}//检查扩容void CheckCapacity(SL* psl){    assert(psl);    if (psl->size == psl->capacity)    {        int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;        SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));        if (tmp == NULL)        {            perror("realloc fail");            exit(-1);        }        psl->a = tmp;        psl->capacity = newcapacity;    }}//尾插void SeqListPushBack(SL* psl, SLDataType x){    SeqListInsert(psl, psl->size, x);}//尾删void SeqListPopBack(SL* psl){    SeqListErase(psl, psl->size - 1);}//头插void SeqListPushFront(SL* psl, SLDataType x){    SeqListInsert(psl, 0, x);}//头删void SeqListPopFront(SL* psl){    SeqListErase(psl, 0);}//查找int SeqListFind(SL* psl, SLDataType x){    for (int i = 0; i size; i++)    {        if (psl->a[i] == x)            return i;    }    return -1;}//任意位置插入void SeqListInsert(SL* psl, size_t pos, SLDataType x){    assert(psl);    assert(pos size);    //检查扩容    CheckCapacity(psl);    //挪动数据    int end = psl->size;    while (end > pos)    {        psl->a[end] = psl->a[end - 1];        --end;    }    psl->a[pos] = x;    ++psl->size;}//任意位置删除void SeqListErase(SL* psl, size_t pos){    assert(psl);    assert(pos size&& pos >= 0);    //挪动数据    while (pos size - 1)    {        psl->a[pos] = psl->a[pos + 1];        ++pos;    }    --psl->size;}//销毁void SeqListDestroy(SL* psl){    assert(psl);    free(psl->a);    psl->size = psl->capacity = 0;}//打印void SeqListPrint(SL* psl){    for (int i = 0; i size; i++)    {        printf("%d ", psl->a[i]);    }}

1.3 顺序表的问题及思考

问题：

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

   200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间

   思考：如何解决以上问题呢？后面文章会给出链表的结构与实现