【数据结构】顺序表 详解（初始化、增、删、查、改）

🐱作者：傻响
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

1.线性表🤩

线性表的解释：

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

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

2.顺序表🤩

2.1概念及结构

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

顺序表一般可以分为：

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

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

2.2 接口实现：

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

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

// 动态顺序表。
typedef int SLDataType;

typedef struct SeqList
{
    SLDataType* data;        // 存储数据和内容数量。
    size_t size;            // 存储数据的个数。
    int capacity;            // 存储空间的大小。
}SeqList;

// 增、删、查、改接口。
// 顺序表初始化函数声明。
void SLInit(SeqList* pSL);
// 顺序表销毁函数声明。
void SLDestory(SeqList* pSL);
// 顺序表尾插头插函数声明。
void SLPushBack(SeqList* pSL, SLDataType data);
void SLPushFront(SeqList* pSL, SLDataType data);
// 顺序表查找函数声明。
int SLFind(SeqList* pSL, SLDataType data);
// 顺序表出入函数声明。
void SLInset(SeqList* pSL, size_t pos, SLDataType data);
// 顺序表尾删头删函数声明。
void SLPopBack(SeqList* pSL);
void SLPopFront(SeqList* pSL);
// 顺组表删除函数声明。
void SLErase(SeqList* pSL, size_t pos);
// 顺组表修改函数声明。
void SLModifi(SeqList* pSL, size_t pos, SLDataType data);
// 顺序表打印。
void SLPrint(const SeqList* pSL);

3.顺序表代码讲解🤩

    跟着我的节奏我们一起看看这些函数是如何编写的吧。

🤢3.1顺序表初始化

// 顺序表初始化实现。
void SLInit(SL* pSL)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    pSL->data = NULL;
    pSL->capacity = pSL->size = 0;
}

🤢3.2顺序表销毁

// 顺序表销毁实现。
void SLDestory(SL* pSL)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    if (pSL->data != NULL)        //如果顺序表不等于空，执行。
    {
        free(pSL->data);
        pSL->data = NULL;
        pSL->capacity = pSL->size = 0;
    }
}

🤢3.3顺序表尾插

// 顺序表尾插头插。
void SLPushBack(SL* pSL, SLDataType data)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 判断容量是否允许插入。
    if (pSL->capacity == pSL->size)
    {
        int newCapacity = pSL->capacity == 0 ? 4 : pSL->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(pSL->data, newCapacity * sizeof(SLDataType));
        if (tmp == NULL)
        {
            perror("SLPushBack realloc");
            return;
        }
        pSL->data = tmp;
        pSL->capacity = newCapacity;
        tmp = NULL;
    }

    // 程序有到这里：进行插入数据。
    pSL->data[pSL->size] = data;
    pSL->size++;    // 增加存储数据的个数。
}

🤢3.4顺序表头插

// 顺序表头插。
void SLPushFront(SL* pSL, SLDataType data)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 检查容量。
    SLCheckCapacity(pSL);

    // 移动数据
    int end = pSL->size - 1;
    while (end >= 0)
    {
        pSL->data[end + 1] = pSL->data[end];
        end--;
    }

    // 头部存入数据
    pSL->data[0] = data;
    pSL->size++;
}

    我们在这里做了一下检测容量的调整，因检测数据被重复调用很多次，所以封装了一个函数SLCheckCapacity()，让其他的函数可以进行多次调用。

🤢3.5顺序表尾删除

    尾删除的话是比较简单的。

// 顺序表尾删。
void SLPopBack(SL* pSL)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 检测还是否有数据。
    if (pSL->size == 0)
        return 0;

    // 进行理论上的删除
    pSL->size--;

}

🤢3.6顺序表头删除

// 顺序表头删实现。
void SLPopFront(SL* pSL)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 检测还是否有数据。
    if (pSL->size == 0)
        return;

     //从后向前移动数据。
    for (int i = 0; i < pSL->size-1; i++)
    {
        pSL->data[i] = pSL->data[i + 1];
    }
    --pSL->size;
}

🤢3.6顺序表查找

// 顺序表查找函数实现。
int SLFind(SeqList* pSL, SLDataType data)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 查找数据.
    for (int i = 0; i < pSL->size; i++)
    {
        if (pSL->data[i] == data)
            return i;
    }

    // 如果没有找到的话返回-1.
    return -1;
}

🤢3.7顺序表插入pos位置数据

// 顺序表出入函数声明声明
void SLInset(SeqList* pSL, size_t pos, SLDataType data)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 检测要插入的位置是否越界。
    assert(pos <= (size_t)pSL->size);

    // 容量检查。
    SLCheckCapacity(pSL);

    // 移动数据。
    size_t end = pSL->size;
    while (end > pos)
    {
        pSL->data[end] = pSL->data[end - 1];
        end--;
    }

    pSL->data[pos] = data;
    pSL->size++;
}

🤢3.8顺序表删除pos位置数据

// 顺组表删除函数实现。
void SLErase(SeqList* pSL, size_t pos)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 检测要插入的位置是否越界。
    assert(pos < pSL->size);

    // 删除数据（数据后往前移动到pos处）
    for (size_t begin = pos; begin < pSL->size - 1; begin++)
    {
        pSL->data[begin] = pSL->data[begin + 1];
    }

    --pSL->size;
}

当然在这里我们就可以把之前的头删和尾删进行复用SLErase()这个函数。

    修改代码如下：

// 顺序表尾删函数实现。
void SLPopBack(SeqList* pSL)
{
     断言 - - 检测指针变量是否为空。
    //assert(pSL);

     检测还是否有数据。
    //if (pSL->size == 0)
    //    return;

     进行理论上的删除
    //pSL->size--;

    SLErase(pSL, pSL->size - 1);
}



// 顺序表头删函数实现。
void SLPopFront(SeqList* pSL)
{
     断言 - - 检测指针变量是否为空。
    //assert(pSL);

     检测还是否有数据。
    //if (pSL->size == 0)
    //    return;

    从后向前移动数据。
    //for (size_t i = 0; i < pSL->size - 1; i++)
    //{
    //    pSL->data[i] = pSL->data[i + 1];
    //}
    //--pSL->size;

    SLErase(pSL, 0);
}

🤢3.9顺序表修改pos位置数据

    这个修改的代码就简单实现

// 顺组表修改函数实现。
void SLModifi(SeqList* pSL, size_t pos, SLDataType data)
{
    // 断言 - - 检测指针变量是否为空。
    assert(pSL);

    // 检测要插入的位置是否越界。
    assert(pos < pSL->size);

    // 修改数据
    pSL->data[pos] = data;
}

😍到此位置我们简单入门级别的顺序表就全部完成了。