【数据结构】顺序表（增、删、查、改）的实现 [初阶篇 _ 复习专用]

作者：Dream-Y.ocean

2022 年 9 月 19 日
广东
本文字数：4904 字
阅读完需：约 16 分钟

前情提要

恭喜大家成功完成C语言，入门了这美丽的世界呀

本章节就开始进入数据结构啦~

接下来我们即将进入一个全新的空间，对代码有一个全新的视角~

以下的内容一定会让你对数据结构有一个颠覆性的认识哦！！！

❗以下内容以C语言的方式实现，对于数据结构来说最重要的是思想哦❗

以下内容干货满满，跟上步伐吧~

💡本章重点

线性表 &顺序表
顺序表接口的实现
顺序表的优缺点

🍞一.线性表

🥐Ⅰ.什么是线性表

线性表：是n个具有相同特性的数据元素的有限序列
线性表：是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表：在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的【线性表在物理上存储时，通常以数组和链式结构的形式存储】

❗对于数据结构,C语言提供了结构体类型给我们使用，让我们更方便的整合一个结构，去利用结构体实现数据结构

🥯Ⅱ.总结

✨综上：就是线性表的概念啦~

➡️简单来说：线性表是一种常见的数据结构，它在逻辑结构上呈连续直线结构，但物理上就不一定是连续的啦

🍞二.顺序表

🥐Ⅰ.什么是顺序表

💡概念及结构：

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

➡️简单来说：

顺序表可以理解为就是数组，因为数组的元素存放，在物理结构和逻辑结构上都是连续，呈直线结构的

但有一点不同就是：顺序表之所以称为顺序表，是因为里面的元素是按照顺序存放的【而数组内可随意存放】

✨有了以上对顺序表的概念后，我们便可以实现它啦~

🥐Ⅱ.静态版顺序表

💡静态版： 即顺序表的空间大小不会随存储的数据个数而发生空间大小的变化【即固定的存储空间】

➡️简单来说： 使用定长数组存储

#define N 100
typedef int SLDataType;
typedef struct SeqList{    SLDataType array[N]; // 定长数组    size_t size; // 有效数据的个数    }SeqList;

复制代码

👉由上述我们可知：

将存储的数据类型重命名为SLDataType，这样有利于后续对顺序表的维护，更改存储的数据类型
size_t size是设置来记录顺序表内已存储的数据个数

❗缺点： 不能在存储的过程中进行增容

✨那么为了让我们的顺序表更加灵活，我们便可以将其写成动态版的

🥐Ⅲ.动态版顺序表

💡静态版： 即实现了对顺序表内空间进行动态的增长，简称增容

➡️简单来说： 使用动态开辟的数组存储

Tips: 关于动态开辟不熟悉的同学可以跳转去🔍【C语言】动态内存管理 [进阶篇_ 复习专用]查看呀

typedef int SLDataType;
typedef struct SeqList{    SLDataType* array; // 指向动态开辟的数组    size_t size ; // 有效数据个数    size_t capicity ; // 容量空间的大小    }SeqList;

复制代码

👉由上述我们可知：

基本实现和静态版没什么不同，唯独将定长数组，改为可以接收动态开辟内存地址的指针，且增加了一个变量

SLDataType* array用来指向动态开辟的数组
size_t capicity是用来记录动态开辟的数组的总大小

✨综上：

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

🍞三.顺序表插口实现

对于数据结构的接口实现，一般围绕增、删、查、改的内容

💡如下的实现围绕此原码进行：

typedef int SeqDataType;
typedef struct SeqList{    //int*a;    SeqDataType* a;
    int size;     int capacity;    }SeqList, SEQ;

复制代码

void TestSeqList1(){    SeqList s;}
int main(){    TestSeqList1();    //顺序表一般不要自己去动它    //而是交给函数去 初始化，去操纵
    return 0;}

复制代码

🥐Ⅰ.初始化顺序表

1️⃣初始化的函数声明：

void SeqListInit(SeqList* pq);

复制代码

2️⃣初始化函数的实现：

void SeqListInit(SeqList* pq){    assert(pq);
    pq-> a = NULL;    pq-> capacity = 0；    pq-> size = 0;}

复制代码

🥐Ⅱ.检查是否要扩容

❗往后实现的接口都需要检查顺序表是否需要扩容，那我们便可以将其集成为一个函数，方便后续调用

👉原理： 检查顺序表内的空间大小是否足够大

不够，则增容

💥特别注意：

一般增容的大小：以 2 倍进行增容
这样增下来不会导致增的太大，从而浪费空间

1️⃣检查扩容的函数声明：

void SeqCheckCapacity(SeqList* pq);

复制代码

2️⃣检查扩容函数的实现：

void SeqCheckCapacity(SeqList* pq){    //满了，需要增容    if (pq->size == pq->capacity)    {        //通常 增容2倍         pq->capacity == 0 ? 4 : pq->capacity * 2;                 int newcapacity = pq->capacity;                SeqDataType* newA = realloc(pq->a, sizeof(SeqDataType)*newcapacity);
        if (newA == NULL)        {            printf("增容失败\n");        }        exit(-1);
        pq->a = newA;        pq->capacity = newcapacity;    }}

复制代码

🥐Ⅲ.尾插顺序表

👉简单来说： 对顺序表进行尾部插入数据

➡️实现： 直接访问顺序表的最后一个元素进行插入

1️⃣尾插的函数声明：

void SeqListPushBack(SeqList* pq, SeqDataType x);

复制代码

2️⃣尾插函数的实现：

void SeqListPushBack(SeqList* pq, SeqDataType x){    assert(pq);
    //检查空间大小    SeqCheckCapacity(pq);
    pq->a[pq->size] = x;    pq->size++;}

复制代码

🥐Ⅳ.头插顺序表

👉简单来说： 对顺序表进行头部插入数据

➡️实现： 需要将顺序表整体往后移动，空出头部一个位置给插入

1️⃣头插的函数声明：

void SeqListPushFront(SeqList* pq, SeqDataType x);

复制代码

2️⃣头插函数的实现：

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++;}

复制代码

🥐Ⅴ.尾删顺序表

👉简单来说： 对顺序表进行删除最后一个数据

➡️实现： 直接将记录数组有效个数的变量size减减即可，这样就访问不到了

❗没必要对要删除的这个元素进行置空等等，因为不影响【因为当后面如果尾插的话，就会直接覆盖原来的数据了~】

💥特别注意： 如果顺序表只剩下一个元素的时候，就不能执行尾删了

1️⃣尾删的函数声明：

void SeqListPopBack(SeqList* pq);

复制代码

2️⃣尾删函数的实现：

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

复制代码

🥐Ⅵ.头删顺序表

👉简单来说： 对顺序表进行删除第一个数据

➡️实现： 需要将顺序表整体前移数据，覆盖第一位数据即达到删除的目的

💥特别注意： 如果顺序表只剩下一个元素的时候，就不能执行头删了

1️⃣头删的函数声明：

void SeqListPopFront(SeqList* pq);

复制代码

2️⃣头删函数的实现：

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--;}

复制代码

🥐Ⅶ.查找元素

👉简单来说： 对顺序表进行查找所需的元素

➡️实现： 遍历顺序表一一比较查找是否有我们想要的元素

没有,则返回-1
有，则返回元素的下标（若有多个符合要查找的元素，则返回优先找到的元素的下标）

1️⃣查找元素的函数声明：

int SeqListFind(SeqList*pq, SeqDataType x);

复制代码

2️⃣查找元素函数的实现：

int SeqListFind(SeqList*pq, SeqDataType x){    assert(pq);
    for (int i = 0; i < pq->size; i++)    {        if (pq->a[i] == x)        {            return i;  //如果又 多个 x，返回的是 优先找到的那个x的 下标        }    }
    return -1;}

复制代码

🥐Ⅷ.修改元素

👉简单来说： 对顺序表的某个位置的元素进行修改

➡️实现： 直接访问想要修改的元素的下标进行修改

💥特别注意： 修改元素的下标要在顺序表有效个数的范围内

1️⃣修改元素的函数声明：

void SeqListModify(SeqList*pq, int pos, SeqDataType x);

复制代码

2️⃣修改元素函数的实现：

void SeqListModify(SeqList*pq, int pos, SeqDataType x){    assert(pq);
    assert(pos >= 0 && pos < pq->size);
    pq->a[pos] = x;}

复制代码

🥐Ⅸ.任意位置前插入元素

👉简单来说： 对顺序表的某个位置前进行插入

➡️实现： 将从顺序表中要插入的位置开始，往后原有的元素整体往后移动，腾出空位来插入

💥特别注意： 插入的位置要在顺序表有效个数的范围内

1️⃣任意位置插入元素的函数声明：

void SeqListInsert(SeqList*pq, int pos, SeqDataType x);

复制代码

2️⃣任意位置插入元素函数的实现：

void SeqListInsert(SeqList*pq, int pos, SeqDataType x){    assert(pq);
    aseert(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++;}

复制代码

💡有了任意位置插入元素函数的实现，我们的头插、尾插函数便可以复用这个函数来实现了

🧇1.【复用】头插函数

👉复用任意位置插入函数的头插函数的实现：

void SeqListPushFront(SeqList* pq, SeqDataType x){    SeqListInsert(pq, x, 0);}

复制代码

🧇2.【复用】尾插函数

👉复用任意位置插入函数的尾插函数的实现：

void SeqListPushBack(SeqList* pq, SeqDataType x){    SeqListInsert(pq, pq->size-1);}

复制代码

🥐Ⅹ.任意位置删除元素

👉简单来说： 对顺序表的某个位置进行删除

➡️实现： 将从顺序表中要删除的元素开始，往后所有的元素整体往前移动，后面的元素覆盖要删除的位置的元素，以达到删除的目的

💥特别注意： 删除的位置要在顺序表有效个数的范围内

1️⃣任意位置删除元素的函数声明：

void SeqListErase(SeqList*pq, int pos);

复制代码

2️⃣任意位置删除元素函数的实现：

void SeqListErase(SeqList*pq, int pos){    assert(pq);
    aseert(pos > 0 && pos < pq->size);
    int begin = pos;    while (begin <= pq->size - 1)    {        pq->a[begin] = pq->a[begin + 1];
        begin++;    }    pq->size--;}

复制代码

💡有了任意位置删除元素函数的实现，我们的头删、尾删函数便可以复用这个函数来实现了

🧇1.【复用】头删函数

👉复用任意位置删除函数的头删函数的实现：

void SeqListPopFront(SeqList* pq) {    SeqListErase(pq, 0);}

复制代码

🧇2.【复用】尾删函数

👉复用任意位置删除函数的尾删函数的实现：

void SeqListPopBack(SeqList* pq){    SeqListErase(pq, pq->size - 1);}

复制代码

🥐Ⅺ.打印顺序表

👉简单来说： 对顺序表进行组个打印

➡️实现： 遍历顺序表一一打印即可

1️⃣打印顺序表的函数声明：

void SeqListPrint(SeqList* pq);

复制代码

2️⃣打印顺序表函数的实现：

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

复制代码

🥐Ⅻ.销毁顺序表

👉简单来说： 对顺序表进行销毁，释放内存空间

➡️实现： 直接将顺序表中的成员变量置为0，且释放顺序表的空间即可

1️⃣销毁顺序表的函数声明：

void SeqListDestory(SeqList* pq);

复制代码

2️⃣销毁顺序表函数的实现：

void SeqListDestory(SeqList* pq){    assert(pq);
    free(pq->a);    pq->a = NULL;    pq->capacity = pq->size = 0;}

复制代码

🥯XⅢ.总结

✨综上：就是顺序表接口实现的内容啦~

➡️相信大家对顺序表有不一样的看法了吧🧡

🍞四.顺序表的优缺点

🔵优点：

可以按下标进行随机访问

🔴缺点：

动态增容有性能缺陷【且伴随着一定的空间浪费，有内存碎片】
头部或者中间插入删除数据，需要挪动数据，效率比较低【O(N)】

🫓总结

综上，我们基本了解了数据结构中的“顺序表”:lollipop:的知识啦~~

恭喜你的内功又双叒叕得到了提高！！！

感谢你们的阅读:satisfied:

后续还会继续更新:heartbeat:，欢迎持续关注:pushpin:哟~

:dizzy:如果有错误❌，欢迎指正呀:dizzy:

:sparkles:如果觉得收获满满，可以点点赞👍支持一下哟~:sparkles:

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/94c0d2bf3dc7684bfad1fb1f4】。未经作者许可，禁止转载。

Dream-Y.ocean

关注

还未添加个人签名 2022.06.17 加入

还未添加个人简介

发布

暂无评论

创作场景

【数据结构】顺序表（增、删、查、改）的实现 [初阶篇 _ 复习专用]

💡本章重点

🍞一.线性表

🥐Ⅰ.什么是线性表

🥯Ⅱ.总结

🍞二.顺序表

🥐Ⅰ.什么是顺序表

🥐Ⅱ.静态版顺序表

🥐Ⅲ.动态版顺序表

🍞三.顺序表插口实现

🥐Ⅰ.初始化顺序表

🥐Ⅱ.检查是否要扩容

🥐Ⅲ.尾插顺序表

🥐Ⅳ.头插顺序表

🥐Ⅴ.尾删顺序表

🥐Ⅵ.头删顺序表

🥐Ⅶ.查找元素

🥐Ⅷ.修改元素

🥐Ⅸ.任意位置前插入元素

🧇1.【复用】头插函数

🧇2.【复用】尾插函数

🥐Ⅹ.任意位置删除元素

🧇1.【复用】头删函数

🧇2.【复用】尾删函数

🥐Ⅺ.打印顺序表

🥐Ⅻ.销毁顺序表

🥯XⅢ.总结

🍞四.顺序表的优缺点

🫓总结

Dream-Y.ocean

评论