带你另一个有趣角度看顺序表基本操作(内含海量图解)

                                   每一个不曾起舞的日子,都是对生命的辜负! 

                                                                                               --------尼采

备注:顺序表本质上就是动态开辟的数组,名字高大上,其实 very easy!

一.基本介绍

1-1线性表

线性表 （linklist list） 是 数据结构 的一种，一个线性表是n个具有相同特性的数据元素的有限序列

顾名思义：线性表就像一条线,不会分叉(学到树和图你自然就明白了)

线性表分为:顺序表,链表,栈和队列

线性表的两种存储方式：顺序储存和链式存储

**1-2顺序表(**sequence list-----通常缩写为SeqList)

顺序表分类:静态顺序表和动态顺序表

(1)静态顺序表缺点:初始时开辟定长数组,在进行插入操作时容易超出预分配的空间长度,造成溢出等

(2)动态顺序表优点:初始时动态分配内存,在进行插入操作时可灵活扩充存储空间等,推荐使用

0.动态顺序表的动态分配结构体的定义:

typedef  int SeqDateType; 
typedef struct SeqList
{
    SeqDataType* a;
    int size;      // 有效数据的个数
    int capacity;  // 容量
}SeqList;

二、基本操作

1.顺序表的初始化

你要打开冰箱拿雪糕的前提就是你得先拥有一个冰箱（顺序表）

void SeqListInit(SeqList* pq)
{
    
    assert(pq);//等价于assert(pq != NULL)

    pq->a = NULL;

    pq->size = pq->capacity = 0;
}

2.顺序表的销毁

顺序表的数组是动态开辟的,占用的是堆上的空间,需要程序员手动去释放,防止长时间占用内存,这既符合谁开辟谁释放的原则,更是一个毋庸置疑的好习惯!

void SeqListDestory(SeqList* pq)
{
    assert(pq);

    free(pq->a);

    pq->a = NULL;

    pq->capacity = pq->size = 0;
}

备注:销毁同样改变了主函数内实参那个顺序表,所以依旧是传址调用

3.顺序表的打印

打印就是将顺序表展示给使用者观看的,但是这一步很简单!

void SeqListPrint(SeqList* pq)
{
    assert(pq);
    for (int i = 0; i < pq->size; ++i)
    {
        printf("%d ", pq->a[i]);
    }

    printf("\n");
}

4.顺序表插入时检查是否需要扩容

顺序表插入时检查是否需要扩容在每次插入操作时都会用到，所以建议封装成函数，模块化代码，需要时直接调用

void SeqCheckCapacity(SeqList* pq)
{
    
    if (pq->size == pq->capacity)
    {
        int newcapacity = pq->capacity == 0 ? 4 : pq->capacity * 2;
        SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
        if (newA == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }

        pq->a = newA;
        pq->capacity = newcapacity;
    }
}

5.顺序表的尾插

顺序表中对于初学者最为头疼的是特殊情况的考虑和元素的后移前移操作，但是只要动动脑筋，就能运用自如，切忌死记硬背！

插入删除移动问题的见解:

类比:尾插就是食堂打饭时老老实实在最后一个人的位置后面排着队,并且干饭人的队伍又多了一名成员罢了.

void SeqListPushBack(SeqList* pq, SeqDataType x)
{
    assert(pq);

    SeqCheckCapacity(pq);

    pq->a[pq->size] = x;
    pq->size++;
}

6.顺序表的头插

类比:在食堂打饭的时候,你直接插队插到第一个位置去了,就是头插,那么你占了第一个位置,原来的人就必须得全部后移一个位置啦(哈哈)🤣

void SeqListPushFront(SeqList* pq, SeqDataType x)
{
    assert(pq);

    SeqCheckCapacity(pq);

    int end = pq->size - 1;
    while (end >= 0)
    {
        pq->a[end + 1] = pq->a[end];
        --end;
    }

    pq->a[0] = x;
    pq->size++;
}

7.顺序表的尾删

类比:排队打饭时你突然发现阿姨颠勺颠的厉害,不想在这个窗口排队了

void SeqListPopBack(SeqList* pq)
{
    assert(pq);
    assert(pq->size > 0);

    --pq->size;
}

8.顺序表的头删

类比:你不文明的头插行为被阿姨发现了,在谩骂声下,你不得不离开队伍第一的位置,其他人又可以前进一个位置了

void SeqListPopFront(SeqList* pq)
{
    assert(pq);
    assert(pq->size > 0);

    int begin = 0;
    while (begin < pq->size-1)
    {
        pq->a[begin] = pq->a[begin+1];
        ++begin;
    }

    pq->size--;

}

9.顺序表的按值查找

类比:你想找队伍里的小明同学,于是你从队头走到队尾,挨个匹配每个人是否是小明,找到就不找了.

int SeqListFind(SeqList* pq, SeqDataType x)
{
    assert(pq);

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

    return -1;
}

10.顺序表的任意位置插入

类比:又是插队!不过这次你是在第pos个位置的前一位,这就要从插入的位置到最后一位均后退一位才能行

void SeqListInsert(SeqList* pq, int pos, SeqDataType x)
{
    assert(pq);
    assert(pos >= 0 && pos <= pq->size);

    SeqCheckCapacity(pq);

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

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

11.顺序表的任意位置删除

类比:不文明的行为当然不能容忍,这次你又被踢出去了

void SeqListErase(SeqList* pq, int pos)
{
    assert(pq);
    assert(pos >= 0 && pos < pq->size);

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

    pq->size--;
}

上面有很多步骤都是可以复用的，例如头插就是在第一个元素前插入一个元素，尾插就是在最后一个元素后插入一个元素等等，快去找找看看吧！

我的gitee代码仓库链接：代码仓库