备案控制台
探索云世界
开发者社区 云计算 文章 正文

【DS】顺序表@线性表 —— 增删查改

2022-07-29 110
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 顺序表

@[toc]

0. 线性表概念

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

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

<img src=" title="">

1. 顺序表概念及结构

:key:顺序表就是 数组，在数组的基础上要求 从头开始，要求数据挨着挨着 连续存储，没有跳跃间隔。

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储元素。
#define N 1000
typedef int SLDataType;

//静态顺序表
typedef struct SeqList
{
    SLDataType data[N];
    int size;//表示数组中存储多少个数据
}SL;

静态顺序表的缺点：

:snowflake:1. 如果满了，就无法再插入。
:snowflake:2. 数组大小给多少合适？这个很难确定， N给小了不够用， N给大了浪费。

因此现实中我们基本都是使用动态顺序表，动态分配内存空间，所以下面我们实现动态顺序表。

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

//动态顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;//表示数组中存储多少个有效数据
    int capacity;//数组实际能存数据的容量
}SL;

2. 顺序表的增删查改

函数接口 —— SeqList.h

本文希望展现一套自然而然又理所当然的思路，都配了图，建议复制所有函数接口自己写自己调，感受会很好，至于完整代码也附在后面了。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//条件为真--没事，条件为假--终止程序

typedef int SLDataType;

//动态顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;//表示数组中存储多少个有效数据
    int capacity;//数组实际能存数据的容量
}SL;

//接口函数--命名风格跟着STL走，方便后续学习STL
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListCeckCapacity(SL* ps);
void SeqListDestroy(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDataType x);
//头删
void SeqListPopFront(SL* ps);
//指定位置插入
void SeqListInsert(SL* ps,int pos,SLDataType x);
//删除指定位置数据
void SeqListErase(SL* ps,int pos);
//查找
int SeqListFind(SL* ps, SLDataType x);
//若找到--则返回下标
//找不到--返回-1
int SeqListFind(SL* ps, SLDataType x);

2.0 初始化、销毁、打印基本接口

2.0.1 初始化

初始化很有必要。开始时，顺序表中什么数据也没有，甚至也还没有为它动态申请一段空间。

因此，ps->a要置NULL，标识它是野指针。ps->size和ps->capacity都要置0，否则就是随机值了。

void SeqListInit(SL* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

注意：为什么传的是这个顺序表的地址？这是因为函数传参，形参是实参的拷贝，形参的改变不会影响实参。

2.0.2 打印

我们要写一点，就打印出来验证一下正确性，就写一个打印函数，遍历即可很简单。

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

2.0.3 销毁

现在我们写的是动态顺序表，那么malloc/realloc动态申请的空间，要记得释放，否则会发生内存泄漏。

关于此，可以复习一下这篇文章 动态内存函数，我顺便也复习了一下，发现有些东西用惯了之后，对于它们是怎么来的会有点淡忘。

void SeqListDestroy(SL* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

2.1 尾插尾删

2.1.1 扩容接口

:key:但凡插入数据就要考虑，空间够不够用是否需要增容的问题

void SeqListCeckCapacity(SL* ps)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        //1.没有空间 —— 申请空间
        //2.空间不够 —— 扩容
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));
        if (tmp == NULL)
        {
            printf("扩容失败\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
}

这里可能唯一要注意一下的，就是realloc函数，文档中如是写——

在这里插入图片描述

因此我们把 第一次申请空间 与 后期的调整空间 完美融合写在一起了，同时处理了没有空间和空间不够两种情况。

2.1.2 尾插

<img src=" title="">

void SeqListPushBack(SL* ps, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    ps->a[ps ->size] = x;
    ps->size++;
}

2.1.3 尾删

:key: 删除数据就要考虑是不是删空了，没的删了，却还在调用这个函数，那就不对了

推荐直接断言暴力终止掉程序，毕竟，就是你用错了。

在这里插入图片描述

void SeqListPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);//断言暴力终止掉程序。若出现删多了的情况，就蹦出窗口终止程序
    ps->size--;
}

断言效果 ——
在这里插入图片描述

2.2 头插头删

2.2.1 头插

  • 插入数据依然要考虑扩容问题
  • 无论是头插还是头删，为了保证顺序表从开始位置连续，都需要挪动数据 —— 想好是从尾 还是 从头 开始挪动，保证数据不会被覆盖丢失。
  • 画好图，时刻注意边界

在这里插入图片描述

void SeqListPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

2.2.2 头删

  • 删除数据依然要考虑删空时，越界访问的情况
  • 画图注意边界

<img src=" title="">

void SeqListPushFront(SL* ps, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

2.3 指定位置插入、删除指定位置数据、查找

查找常和指定位置插入、指定位置删除搭配使用。

2.3.1 查找

//查找--找到了则返回x位置下标，没有找到则返回-1
int SeqListFind(SL* ps, SLDataType x)
{
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
        {
            return i;
        }
    }
    return -1;
}

2.3.2 指定位置插入

与头插完全类似

<img src=" title="">

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

2.3.3 删除指定位置数据

与头删完全类似

<img src=" title="">

void SeqListErase(SL* ps, int pos)
{
    assert(ps);
    assert(ps->size);
    int start = pos + 1;
    while (start < ps->size)
    {
        ps->a[start - 1] = ps->a[start];
        start++;
    }
    ps->size--;
}

2.3.4 复用

有了指定位置插入和指定位置删除，就可以复用这些接口，完成头插头删尾插尾删 ——

//尾插
void SeqListPushBack(SL* ps, SLDataType x)
{
    SeqListInsert(ps, ps->size, x);
}

//尾删
void SeqListPopBack(SL* ps)
{
    SeqListErase(ps, ps->size - 1);
} 

//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
    SeqListInsert(ps, 0, x);
}   

//头删
void SeqListPopFront(SL* ps)
{
    SeqListErase(ps, 0);
}

分分钟搞定。

3. 顺序表的问题及思考

  • [ ] 顺序表优点 ——

    支持随机访问，方便做查找。

  • [ ] 顺序表缺陷 ——
  1. 空间不够需要增容，增容是要付出代价的。
  2. 为了避免频繁扩容，我们基本都是按倍数去扩（扩2倍），可能会造成一定的空间浪费。
  3. 顺序表要求数据从开始位置保持连续，那么中间和头部的插入，就需要挪动数据，时间复杂度为O(N)，效率不高。

针对顺序表的缺陷，引出了下一节 —— 链表

未完待续@边通书

附：源代码

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//条件为真-没事，条件为假-终止程序

typedef int SLDataType;


//动态顺序表
typedef struct SeqList
{
    SLDataType* a;
    int size;        //表示数组中存储多少个数据
    int capacity;    //数组实际能存数据的容量
}SL;


//接口函数--命名风格跟着STL走，方便后续学习STL
void SeqListInit(SL* ps);
void SeqListPrint(SL* ps);
void SeqListDestroy(SL* ps);
void SeqListCheckCapacity(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SLDataType x);
//尾删
void SeqListPopBack(SL* ps);
//头插
void SeqListPushFront(SL* ps, SLDataType x);
//头删
void SeqListPopFront(SL* ps);
//指定位置插入
void SeqListInsert(SL* ps, int pos, SLDataType x);
//删除指定位置的数据
void SeqListErase(SL* ps, int pos);

//查找--找到了则返回x位置下标，没有找到则返回-1
int SeqListFind(SL* ps, SLDataType x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void SeqListInit(SL* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

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

void SeqListDestroy(SL* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;
}

void SeqListCheckCapacity(SL* ps)
{
    assert(ps);
    if (ps->size == ps->capacity)
    {
        int newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->a,sizeof(SLDataType)*newcapacity);
        if (tmp == NULL)
        {
            printf("realloc failed\n");
            exit(-1);
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
}

void SeqListPushBack(SL* ps, SLDataType x)
{
    SeqListInsert(ps, ps->size, x);
    //assert(ps);
    //SeqListCheckCapacity(ps);
    //ps->a[ps->size] = x;
    //ps->size++;
}

void SeqListPopBack(SL* ps)
{
    SeqListErase(ps, ps->size - 1);
    //assert(ps);
    //assert(ps->size);
    //ps->size--;
}

void SeqListPushFront(SL* ps, SLDataType x)
{
    SeqListInsert(ps, 0, x);
    /*assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;*/
}

void SeqListPopFront(SL* ps)
{
    SeqListErase(ps, 0);
    //assert(ps);
    //assert(ps->size);
    //int start = 1;
    //while (start < ps->size)
    //{
    //    ps->a[start - 1] = ps->a[start];
    //    start++;
    //}
    //ps->size--;
}

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
    assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
    assert(ps);
    assert(ps->size);
    int start = pos + 1;
    while (start < ps->size )
    {
        ps->a[start - 1] = ps->a[start];
        start++;
    }
    ps->size--;
}

int SeqListFind(SL* ps, SLDataType x)
{
    assert(ps);
    int i = 0;
    for (i = 0; i < ps->size; i++)
    {
        if (ps->a[i] == x)
            return i;
    }
    return -1;
}

test.c

关于测试文件，就是随写随测，把每种情况都测到，这里主要是增容呀，删空时的越界访问呀，还有就是基本的逻辑，把我自己的贴出来

#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

//测试尾插尾删
void TestSeqList1()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);

    SeqListPrint(&sl);

    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    SeqListPopBack(&sl);
    //SeqListPopBack(&sl);
    //SeqListPopBack(&sl);

    SeqListPrint(&sl);
    SeqListDestroy(&sl);
}

//测试头插头删
void TestSeqList2()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);
    SeqListPrint(&sl);

    SeqListPushFront(&sl, 0);
    SeqListPushFront(&sl, -1);
    SeqListPushFront(&sl, -2);
    SeqListPrint(&sl);

    SeqListPopFront(&sl);
    SeqListPopFront(&sl);
    SeqListPrint(&sl);

    printf("%d\n", SeqListFind(&sl,3));

    SeqListDestroy(&sl);
}

//测试指定位置的插入删除
void TestSeqList3()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);

    SeqListInsert(&sl, 2, 30);
    SeqListInsert(&sl, 0, 0);
    SeqListInsert(&sl, sl.size, 80);

    SeqListPrint(&sl);
    
    //配合使用
    int pos = SeqListFind(&sl, 4);
    if (pos != -1)
    {
        SeqListInsert(&sl, pos, 40);
    }

    SeqListPrint(&sl);

    SeqListDestroy(&sl);

}

//复用SeqListInsert测试头插尾插
void TestSeqList4()
{
    SL sl;
    SeqListInit(&sl);

    SeqListPushBack(&sl, 1);
    SeqListPushBack(&sl, 2);
    SeqListPushBack(&sl, 3);
    SeqListPushBack(&sl, 4);
    SeqListPushBack(&sl, 5);

    SeqListPushFront(&sl, 1);
    SeqListPushFront(&sl, 2);
    SeqListPushFront(&sl, 3);
    SeqListPushFront(&sl, 4);
    SeqListPushFront(&sl, 5);
    SeqListPrint(&sl);

    SeqListPopFront(&sl);
    SeqListPopFront(&sl);

    SeqListPopBack(&sl);
    SeqListPopBack(&sl);

    SeqListPrint(&sl);

    //假如我要删3
    int pos = SeqListFind(&sl, 3);
    if (pos != -1)
    {
        SeqListErase(&sl, pos);
    }
    SeqListPrint(&sl);

    SeqListDestroy(&sl);
}
int main()
{
    //TestSeqList1();
    //TestSeqList2();
    //TestSeqList3();
    TestSeqList4();

    return 0;
}
文章标签：
存储
@浮光掠影
目录
相关文章
提问的橘子
|
9天前
浅谈顺序表基本操作
浅谈顺序表基本操作
提问的橘子
31 1
阿熊不会编程
|
4月前
|
存储 C语言 开发者
顺序表操作详解
顺序表操作详解
阿熊不会编程
28 0
阿甘兄
|
5月前
06 顺序表操作
06 顺序表操作
阿甘兄
14 0
阿甘兄
|
5月前
|
存储
05 顺序表的结构与实现
05 顺序表的结构与实现
阿甘兄
14 0
KOBE0824BRYANT
|
10月前
|
存储
顺序表（增删查改）
顺序表（增删查改）
KOBE0824BRYANT
41 0
KOBE0824BRYANT
|
10月前
|
存储
单链表（增删查改）
单链表（增删查改）
KOBE0824BRYANT
31 0
游客6nmtzqmqofvbk
|
11月前
|
存储 缓存
【数据结构】实现顺序表的增删查改
实现顺序表的增删查改
游客6nmtzqmqofvbk
47 0
诺诺的包包
|
存储
【线性表】—动态顺序表的增删查改实现
【线性表】—动态顺序表的增删查改实现
诺诺的包包
92 0
鲲志说
|
存储 编译器
数据结构：线性表中顺序表和单链表的比较
数据结构：线性表中顺序表和单链表的比较
鲲志说
151 0
数据结构：线性表中顺序表和单链表的比较
子夜的星
|
存储
【数据结构】顺序表—纯C实现顺序表
【数据结构】顺序表—纯C实现顺序表
子夜的星
59 0
【数据结构】顺序表—纯C实现顺序表

热门文章

最新文章

  • 1
    理解事务的4种隔离级别
  • 2
    疑犯追踪第一季/全集Person Of Interest迅雷下载
  • 3
    简单实用的数据建模工具PDManer
  • 4
    详细讲解！Canal+Kafka实现MySQL与Redis数据同步！
  • 5
    71.7. Script for automatic startup on boot
  • 6
    关于Oracle客户端显示乱码问题
  • 7
    PHPWAMP站点管理的“域名模式”和“端口模式”详解、均支持自定义
  • 8
    jsHelper
  • 9
    学校里学不到的东西(一)
  • 10
    Python 3 教程一:入门
  • 1
    Python的装饰器
    32
  • 2
    R语言用潜类别混合效应模型(Latent Class Mixed Model ,LCMM)分析老年痴呆年龄数据
    20
  • 3
    数据分享|R语言用logistic逻辑回归和AFRIMA、ARIMA时间序列模型预测世界人口
    15
  • 4
    【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享（下）
    20
  • 5
    【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享（上）
    26
  • 6
    数据分享|数据探索电商平台用户行为流失可视化分析
    28
  • 7
    电商平台数据可视化分析网红零食销量
    18
  • 8
    R语言线性回归模型拟合诊断异常值分析家庭燃气消耗量和卡路里实例带自测题
    15
  • 9
    数据分享|R语言GLM广义线性模型：逻辑回归、泊松回归拟合小鼠临床试验数据（剂量和反应）示例和自测题
    12
  • 10
    数据分享|R语言逻辑回归、线性判别分析LDA、GAM、MARS、KNN、QDA、决策树、随机森林、SVM分类葡萄酒交叉验证ROC（下）
    16

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）