[ 数据结构 - C实现] 顺序表

1、线性表

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

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

本篇文章我们要了解的是顺序表

2、顺序表

2.1 顺序表的概念

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

顺序表可分为静态顺序表和动态顺序表：

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

可以理解为开辟空间一定，小了不够，大了浪费（比较死板，不够灵活）

// 要求：存储的数据从0开始，依次连续存储
// 静态的顺序表
// 问题：开小了，不够用。开大了，存在浪费。
#define N 10000
struct SeqList
{
    int a[N];
    int size; // 记录存储了多少个数据
};

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

显而易见如果空间不够可以增容（灵活，实用）

2.2 接口

// 动态的顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;     // 存储数据个数
    int capacity; // 存储空间大小
}SeqList;

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 检查空间，如果满了，进行增容
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位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

3、接口实现

3.1 顺序表尾插

void SeqListPushBack(SeqList* psl, SLDataType x)
{
    assert(psl);

    /*SeqListCheckCapacity(psl);

    psl->a[psl->size] = x;
    psl->size++;*/

    SeqListInsert(psl, psl->size, x);
}

注意：尾插数据首先要考虑开辟的空间是否够用，如果不够用要增容。增容完成后再进行插入数据。

增容函数：

void SeqListCheckCapacity(SeqList* psl)
{
    assert(psl);

    // 如果满了，我们要扩容
    if (psl->size == psl->capacity)
    {
        size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
        SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        else
        {
            psl->a = tmp;
            psl->capacity = newCapacity;
        }
    }
}

3.2 顺序表头插

void SeqListPushFront(SeqList* psl, SLDataType x)
{
    assert(psl);

    //SeqListCheckCapacity(psl);

     挪动数据，腾出头部空间
    //int end = psl->size - 1;
    //while (end >= 0)
    //{
    //    psl->a[end + 1] = psl->a[end];
    //    --end;
    //}

    //psl->a[0] = x;
    //psl->size++;

    SeqListInsert(psl, 0, x);
}

注意：头插时必须从后向前移动。

3.3 在指定位置插入数据

void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
    // 暴力检查
    assert(psl);

    // 温和检查
    if (pos > psl->size)
    {
        printf("pos 越界：%d\n", pos);
        return;
        //exit(-1);
    }
    // 暴力检查
    //assert(pos <= psl->size);

    SeqListCheckCapacity(psl);

    //int end = psl->size - 1;
    //while (end >= (int)pos)
    //{
    //    psl->a[end + 1] = psl->a[end];
    //    --end;
    //}

    size_t end = psl->size;
    while (end > pos)
    {
        psl->a[end] = psl->a[end - 1];
        --end;
    }

    psl->a[pos] = x;
    psl->size++;
}

注意：

1：覆盖仍然是从后往前。

2：pos的值一定要小于size，否则会造成越界（由于是size_t 无符号整数，因此一定大于0）

3：当 pos等于size时，功能等同于尾插，pos等于0时，功能等同于头插。

3.4 顺序表尾删

void SeqListPopBack(SeqList* psl)
{
    assert(psl);

    //psl->a[psl->size - 1] = 0;
    /*if (psl->size > 0)
    {
        psl->size--;
    }*/
    SeqListErase(psl, psl->size - 1);
}

尾删直接删除即可。

3.5 顺序表头删

void SeqListPopFront(SeqList* psl)
{
    assert(psl);

    // 挪动数据覆盖删除
    /*if (psl->size > 0)
    {
        int begin = 1;
        while (begin < psl->size)
        {
            psl->a[begin - 1] = psl->a[begin];
            ++begin;
        }

        --psl->size;
    }*/
    SeqListErase(psl, 0);
}

注意：头删是从前往后覆盖

3.6 在指定位置删除数据

void SeqListErase(SeqList* psl, size_t pos)
{
    assert(psl);
    assert(pos < psl->size);

    size_t begin = pos + 1;
    while (begin < psl->size)
    {
        psl->a[begin - 1] = psl->a[begin];
        ++begin;
    }

    psl->size--;
}

注意：

1、pos必须小于size的值（由于size_t 不考虑小于零）。

2、begin 定义在 pos的下一位，右前向后走向前覆盖。

3、当pos 等于0时，功能等同于头删，当pos 等于size-1时，功能等同于尾删。

3.7 查找数据

int SeqListFind(SeqList* psl, SLDataType x)
{
    assert(psl);

    for (int i = 0; i < psl->size; ++i)
    {
        if (psl->a[i] == x)
        {
            return i;
        }
    }

    return -1;
}

查到返回下标，未查到返回-1。

完整代码：2022_03_09_顺序表/2022_03_09_顺序表 · 李兴宇/数据结构 - 码云 - 开源中国 (gitee.com)

演示：

4、菜单

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

void menu()
{
    printf("***********************************************\n");
    printf("       1.尾插数据           \n");
    printf("       2.头插数据           \n");
    printf("       3.在指定位置插入数据   \n");
    printf("       4.尾删数据           \n");
    printf("       5.头删数据           \n");
    printf("       6.在指定位置删除数据   \n");
    printf("       7.打印数据           \n");
    printf("       8.查找数据           \n");
    printf("       -1.退出             \n");
    printf("***********************************************\n");
}

int main()
{
    //TestSeqList5();
    SeqList s;
    SeqListInit(&s);
    int option = -1;
    do
    {
        menu();
        printf("请选择你的操作:>");
        scanf("%d", &option);
        if (option == 1)
        {
            printf("请输入你要尾插的数据:>");
            //int val = 0;
            SLDataType val = 0;
            scanf("%d", &val);
            SeqListPushBack(&s, val);
        }
        else if (option == 2)
        {
            printf("请输入你要头插的数据:>");
            SLDataType val = 0;
            scanf("%d", &val);
            SeqListPushFront(&s, val);
        }
        else if (option == 3)
        {
            printf("请输入你插入的位置pos和数据x:>");
            SLDataType val = 0;
            int x = 0;
            scanf("%d %d", &val, &x);
            SeqListInsert(&s, val - 1, x);
        }
        else if (option == 4)
        {
            SeqListPopBack(&s);
            printf("尾删成功!\n");
        }
        else if (option == 5)
        {
            SeqListPopFront(&s);
            printf("头删成功!\n");
        }
        else if (option == 6)
        {
            printf("请输入你删除的位置pos:>");
            int x = 0;
            scanf("%d", &x);
            SeqListErase(&s, x - 1);
        }
        else if (option == 8)
        {
            printf("请输入你查找的数据x:>");
            int x = 0;
            scanf("%d", &x);
            int i = SeqListFind(&s, x);
            if (i == -1)
            {
                printf("该数据不存在\n");

            }
            else
            {
                printf("该数据的下标是%d\n", i);
            }
        }
        else if (option == 7)
        {
            SeqListPrint(&s);
        }
    } while (option != -1);
    SeqListDestroy(&s);
    return 0;
}

（本篇完）