AI 助理
备案控制台
开发者社区 云计算 文章 正文

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

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

@[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;
}
文章标签：
存储
@浮光掠影
目录
相关文章
chian-ocean
|
3月前
|
存储
顺序表以及实现（结构篇）
顺序表以及实现（结构篇）
chian-ocean
55 11
sky_qiyi
|
5月前
|
存储 算法
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
数据结构和算法学习记录——线性表之顺序表(顺序表概念、结构、顺序表接口函数-头插头删、尾插尾删)
sky_qiyi
27 0
提问的橘子
|
6月前
浅谈顺序表基本操作
浅谈顺序表基本操作
提问的橘子
44 1
pearlthriving
|
6月前
|
存储
实现顺序表的增删查改
现在让我们探索数据结构这个美妙的世界吧！
pearlthriving
34 0
阿熊不会编程
|
11月前
|
存储 C语言 开发者
顺序表操作详解
顺序表操作详解
阿熊不会编程
53 0
阿甘兄
06 顺序表操作
06 顺序表操作
阿甘兄
25 0
阿甘兄
|
存储
05 顺序表的结构与实现
05 顺序表的结构与实现
阿甘兄
37 0
KOBE0824BRYANT
|
存储
顺序表（增删查改）
顺序表（增删查改）
KOBE0824BRYANT
67 0
阿润菜菜
|
存储 缓存 内存技术
对于顺序表和链表的区别
对于顺序表和链表的区别
阿润菜菜
97 0
诺诺的包包
|
存储
【线性表】—动态顺序表的增删查改实现
【线性表】—动态顺序表的增删查改实现
诺诺的包包
130 0

热门文章

最新文章

  • 1
    Java 生成 UUID
  • 2
    一文读懂 Serverless 的起源、发展和落地实践
  • 3
    Fiddler抓包：下载、安装及使用
  • 4
    用CodeViz绘制函数调用关系图(call graph)
  • 5
    阿里AI上岗双11服装车间，能识别头发丝直径十分之一的瑕疵
  • 6
    SpringBoot开发案例之整合Dubbo提供者(一)
  • 7
    Dubbo架构介绍
  • 8
    警惕垃圾邮件借加沙新闻进行钓鱼攻击
  • 9
    美国博客刊文发布NetApp StoreVault停产通知
  • 10
    IntelliJ IDEA 12 创建Web项目 教程 超详细版
  • 1
    通义灵码与云计算平台的融合：基础与概述
    36
  • 2
    《深度解析：死锁的“前世今生”与防范之道》
    29
  • 3
    《探秘程序崩溃：核心转储（Core Dump）分析全攻略》
    34
  • 4
    今日 AI 开源｜共 12 项｜开源的DIY健康追踪项目，基于低成本的智能戒指构建私人的健康监测应用
    37
  • 5
    Open Interpreter：AI 赋能终端！在终端中对话AI模型进行编程，通过运行代码来完成各种计算机操作任务
    29
  • 6
    「Mac畅玩鸿蒙与硬件15」鸿蒙UI组件篇5 - Slider 和 Progress 组件
    39
  • 7
    ai断点怎么做?
    15
  • 8
    AI Shell：在命令行里“对话” AI ，微软推出将 AI 助手引入命令行的 CLI 工具，打造对话式交互命令行
    19
  • 9
    ai怎么设计迷宫字体效果?
    15
  • 10
    「Mac畅玩鸿蒙与硬件14」鸿蒙UI组件篇4 - Toggle 和 Checkbox 组件
    29

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    阿里云OSS设置跨域访问