数据结构初阶：顺序表的概念与动态实现

结论： 最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。

2. 顺序表

1. 顺序表的概念及结构

顺序表是线性表的一种

线性表有物理结构和逻辑结构。 线性表的物理结构不一定连续，但逻辑结构一定连续。

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

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

案例：蔬菜分为绿叶类、瓜类、菌菇类。 线性表指的是具有部分相同特性的一类数据结构的集合。

顺序表的物理结构跟逻辑结构都是连续的

2. 顺序表分类

• 顺序表和数组的区别
  • 顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口
• 顺序表分类
  • 静态顺序表
  • 动态顺序表

3. 动态顺序表的实现

先创建一个头文件用来声明函数，两个 .c 文件，SeqList.c 顺序表的实现，test.c 用来测试。

1. 定义一个动态顺序表

typedef struct SeqList // sequence 顺序的
{
    SLDataType* arr;
    int size;      // 有效数据个数
    int capacity;  // 空间大小
} SL; // SeqList 太长 我们把他换成 SL

因为我们不知道以后使用时要用什么类型的数据，所以我们最好给数据类型起一个别名。

typedef int SLDataType;

2. 顺序表的初始化

void SLInit(SL *s)
{
    s->arr = NULL;
    s->size = s->capacity = 0;
}

注意： 这里函数传参一定要用地址传参。

3. 顺序表的销毁

void SLDestroy(SL* ps)
{
    if (ps->arr)
    {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->size = ps->capacity = 0;
}

4. 顺序表的尾插

void SLPushBack(SL* ps, SLDataType x)
{
    assert(ps); // 表达式为真，继续执行；表达式假，程序报错
    
    // 插入之前先看空间够不够
    if (ps->size == ps->capacity)
    {
        // 申请空间
        // 只有 realloc 可以增容
        // 增容通常是成倍数的增加，一般是 2 倍或 3 倍，不能频繁增容，会造成性能降低
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
        
        // 用临时变量来接收，防止内存开辟失败数据丢失
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(1); // 直接退出程序，不再执行
        }
        
        // 空间申请成功
        ps->arr = tmp;
        ps->capacity = newcapacity;
    }
    ps->arr[ps->size++] = x;
}

5. 顺序表的头插

void SLPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SLCheckCapacity(ps); // 先让顺序表中数据整体后移一位
    
    for (int i = ps->size; i > 0; i--)
    {
        ps->arr[i] = ps->arr[i - 1]; // arr[1]=arr[0]
    }
    ps->arr[0] = x;
    ps->size++; // 加了一个数据
}

6. 空间大小检查函数

我们注意到在头插跟尾插中都检查了空间的大小，所以我们可以把它封装成函数。

void SLCheckCapacity(SL* ps)
{
    if (ps->size == ps->capacity)
    {
        // 申请空间
        // 只有 realloc 可以增容
        // 增容通常是成倍数的增加，一般是 2 倍或 3 倍，不能频繁增容，会造成性能降低
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
        
        if (tmp == NULL)
        {
            perror("realloc fail");
            exit(1); // 直接退出程序，不再执行
        }
        
        // 空间申请成功
        ps->arr = tmp;
        ps->capacity = newcapacity;
    }
}

7. 顺序表的尾删

void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size); // 判断顺序表是否为空
    // ps->arr[ps->size - 1] = -1;
    ps->size--;
}

8. 顺序表的头删

void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size);
    
    for (int i = 0; i < ps->size - 1; i++)
    {
        ps->arr[i] = ps->arr[i + 1]; // 逐个向前替换，最后一个是 arr[size-2]=arr[size-1]
    }
    ps->size--; // 这个不能忘
}

9. 测试示例

#include "SeqList.h"

// 打印函数原型
void SLPrintf(SL s);

void SLTest01()
{
    SL sl;
    SLInit(&sl); // 这里要传地址，传值（值拷贝）这都没有初始化，没有值
    
    SLPushBack(&sl, 1); // 尾插
    SLPushBack(&sl, 2);
    SLPushBack(&sl, 3);
    SLPushBack(&sl, 4);
    SLPrintf(sl); // 打印函数
    
    // 头插
    SLPushFront(&sl, 5);
    SLPushFront(&sl, 6);
    SLPrintf(sl);
    
    // 尾删
    SLPopBack(&sl);
    SLPrintf(sl);
    
    // 头删
    SLPopFront(&sl);
    SLPopFront(&sl);
    SLPopFront(&sl);
    SLPrintf(sl);
    
    SLDestroy(&sl); // 销毁
}

int main()
{
    SLTest01();
    return 0;
}

void SLPrintf(SL s) // 上文中的打印函数，这里不是对底层的修改，所以传值即可
{
    for (int i = 0; i < s.size; i++)
    {
        printf("%d ", s.arr[i]);
    }
    printf("\n");
}