【落羽的落羽 数据结构篇】顺序表

一、线性表

线性表是若干个具有相同特性的数据元素的有限序列，是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串，等等。线性表在逻辑上是线性结构的，但在物理层面上（地址）不一定是线性结构的。
（线性表逻辑上连续，地址不一定连续）

本篇文章先来了解顺序表。

二、顺序表

1. 概念与分类

顺序表的概念：顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构，一般情况下采用数组存储。
顺序表和数组的区别在于：顺序表的底层结构是数组，它是对数组的封装，实现了常用的增删查改等功能，是一个结构体类型。

一般情况下，顺序表可以分为：静态顺序表、动态顺序表

2. 准备工作

• 顺序表的英文是SeqList，一在实际写代码过程中，我们常常typedef重命名为SL方便书写。
• 由于顺序表存储的数据类型有很多种可能，在一个项目实战中，面对成百上千行代码，一旦要修改顺序表存放数据类型，一个个修改会很麻烦。所以我们可以一开始就定义typedef 类型 SLDataType;，然后创建顺序表的数组，或是其他要写到顺序表元素类型的地方，直接写成SLDataType。这样，需要改变数据类型时，直接改typedef那里就可。
• 通常我们把结构体的定义、函数的声明放在SeqList.h 头文件中。把顺序表的功能实现方法代码放在SeqList.c 源文件中，每一个功能都封装成一个函数。测试顺序表功能则在test.c 中完成。（它们都要包含SeqList.h头文件）

这些道理不仅适用于本文，未来学习其他内容也是一样的，以后就不再提醒了。

3. 静态顺序表

静态顺序表，就是固定大小的顺序表，使用定长数组存储元素：

typedef struct SeqList
{
    SLDataType arr[7];  //定长数组
    int size;           //有效元素个数
}SL;

其实它和数组也没有太大区别了，只是对数组进行了简单封装，
静态顺序表的大小无法再改变，因此面对空间给大了或空间给小了的情况时无能为力。所以在实际项目中我们很少用到它，动态顺序表才是更重要的。

4. 动态顺序表

动态顺序表的特点是空间按需申请。按需申请，说明数组的内存大小要靠动态内存分配实现。下面我们就来演示一下常见的动态顺序表的操作：

4.1 定义顺序表结构

typedef struct SeqList
{
    SLDataType* arr;//数组首元素地址
    int size;       //有效数据个数
    int capacity;   //空间大小
}SL;

4.2 顺序表的初始化

//不能进行传值调用，否则修改的只是形参，因此要传址调用
void SLInit(SL* psl)
{
    psl->arr = NULL;
    psl->size = psl->capacity = 0;
}

测试：

4.3 检查空间是否足够

在插入顺序表元素前，我们要确保表的空间足够，当size == capacity说明空间已满，需要扩容。而假如capacity还为0，则先自己给定一个大小；不为0，一般呈二倍扩容，这是由概率论总结出来的最适合的扩容大小。每个插入数据操作都应该包括这一步。

void SLCheckCapacity(SL* psl)
{
    if(psl->size == psl->capacity)
    {
        int newCapacity = (psl->capacity==0)? 5: 2*psl->capacity;
        SLDataType* tmp = (SLDataType*)realloc(psl->arr, newCapacity*sizeof(SLDataType));
        if(tmp == NULL)
        {
            perror("realloc fail!");
            return 1;
        }
        psl->arr = tmp;
        psl->capacity = newCapacity;
    }
}

测试：

4.3 尾部插入数据

我们实现的插入数据函数是单个数据的插入。插入一个新数据，意味着表的有效数据个数size也要++。这个功能是在顺序表的尾部插入一个数据，尾插函数应该有两个参数，被插入的表和被插入的数据：

void SLPushBack(SL* psl, SLDataType x)
{
    assert(psl); //确保psl不为空
    SLCheckCapacity(psl);
    psl->arr[psl->size] = x;
    psl->size++;
}

测试：

4.4 头部插入数据

这个功能是在顺序表的头部插入一个数据，参数也是要有两个：

void SLPushFront(SL* psl, SLDataType x)
{
    assert(psl);
    SLCheckCapacity(psl);
    for(int i = psl->size; i>0; i--)
    {
        psl->arr[i] = psl->arr[i-1];
    }
    psl->arr[0] = x;
    psl->size++;
}

测试：

4.5 尾部删除数据

这个功能是删除顺序表尾部的一个数据，但实际上并不是“删除”，而是修改size，让这个数据在size的范围之外。这样我们用size的值访问arr时，就访问不到这个数据了。

void SLPopBack(SL* psl)
{
    assert(psl && psl->size);//psl不能为空，size不能为0，否则没有意义
    psl->size--;
}

测试：

4.6 头部删除数据

头删就是真的删除头部一个数据了，会被第二个数据覆盖掉。

void SLPopFront(SL* psl)
{
    assert(psl && psl->size);
    for(int i = 0; i < psl->size-1; i++)
    {
        psl->arr[i] = psl->arr[i+1];
    }
    psl->size--;
}

测试：

4.7 在指定位置插入数据

这个功能有三个参数，一个是顺序表，一个是指定的位置，一个是要插入的数据。pos及之后的数据要整体向后挪动一位。

void SLInsert(SL* psl, int pos, SLDataType x)
{
    assert(psl);
    assert(pos>=0 && pos<=psl->size);//确保pos有意义
    SLCheckCapacity(psl);
    for(int i = psl->size; i>pos; i--)
    {
        psl->arr[i] = psl->arr[i-1];
    }
    psl->arr[pos] = x;
    psl->size++;
}

测试：

4.8 在指定位置删除数据

同样地，pos之后的数据要整体向前挪动一位

void SLErase(SL* psl, int pos)
{
    assert(psl);
    assert(pos>=0 && pos<=psl->size);
    SLCheckCapacity(psl);
    for(int i=pos; i<psl->size-1; i++)
    {
        psl->arr[i] = psl->arr[i+1];
    }
    psl->size--;
}

测试：

4.9 顺序表的销毁

void SLDestory(SL* psl)
{
    if(psl->arr != NULL)
    {
        free(psl->arr);
    }
    psl->arr = NULL;
    psl->size = psl->capacity = 0;
}

测试：

以上就是顺序表的部分用法了，但远不止这些，大家可以设计出更多功能的。

本篇完，感谢阅读。