程序员经验分享-hwhale

002 数据结构_顺序表的实现过程——“C”

2023-11-20

引入

什么是顺序表

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

  1. 静态顺序表：使用定长数组存储元素。
  2. 动态顺序表：使用动态开辟的数组存储。

什么是malloc与realloc内存函数

1、
void *malloc( size_t size );
void *返回类型
size_t size字节数

 psl->array =(int*)malloc(sizeof(SLDataType)*4);

这句代码的含义是通过malloc函数返回一个指向16字节的空间的int*指针然后为了接收这个指针，我们定义了一个int *array指针，通过这个指针接收malloc的返回值
malloc 函数用于在堆上分配一块指定大小的内存空间，并返回一个指向该内存块起始地址的指针。为了接收这个指针，我们需要定义一个相应类型的指针变量并将 malloc 函数的返回值赋给它。
2、
void *realloc( void *memblock, size_t size );

   SLDataType*tmp= (int*)realloc(psl->array,sizeof(SLDataType) *psl->capacity*2);

realloc函数需要接收两个参数：第一个参数是指向原始内存块指针的指针，第二个参数是所需的新内存块大小。ps：第二个参数是新增后的字节数大小

实现步骤

1.构建结构体

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* array;
    //定义一个结构体指针，类型为SLDataType(int)
    size_t size;//当前已存储的数量
    size_t capacity;//当前最大容量
}SeqList;

2.顺序表——初始化

void SeqListInit(SeqList* psl)  
{
    assert(psl);
    断言：利于找出bug，防范指针为空
    不为空就通过，为空就报错
    psl->array =(int*)malloc(sizeof(SLDataType)*4);
    //开辟动态内存空间
    if(psl->array==NULL) //如果开辟空间失败
    {
        perror("malloc fail");//打印错误信息
        return;
    }
    psl->size = 0;
    psl->capacity = 4;
}

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

3.顺序表——销毁

void SeqListDestory(SeqList* psl)
{
    assert(psl);
    free(psl->array);  
   // 通过free()函数释放指针所指向的动态分配的内存空间
    psl->array = NULL;   
    psl->size = 0;   
    psl->capacity = 0;
}

4.顺序表——打印

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

5.顺序表——扩容

void CheckCapacity(SeqList* psl)
{
    assert(psl);
    if (psl->size == psl->capacity)
   {
   SLDataType*tmp= (int*)realloc(psl->array,sizeof(SLDataType) *psl->capacity*2);
      if (tmp == NULL)  //如果开辟空间失败
        {
       perror("realloc fail");  //打印错误信息
       return;
         }  
    psl->array = tmp;
    psl->capacity *= 2;
   }

6.顺序表——插入

头插：将数组中的元素全部向后移动一位，空出第一的位置留给头插
尾插：开辟动态内存空间后，直接在最后插入元素
在任意位置插入：插入的位置为pos，将在pos位置的元素以及pos位置后的元素全部向后移动一位，用x覆盖pos处元素

顺序表头插

void SeqListInsert(SeqList* psl, int pos, SLDataType x)
{
    assert(psl);
    assert(0 <= pos && pos <= psl->size);
    //断言：保证插入的数字在内存空间内
    
    CheckCapacity(psl);
    //插入需要开辟内存空间
    for (int end = psl->size; end >= pos; end--)
    {
        psl->array[end] = psl->array[end - 1];
    }
    psl->array[pos] = x;
    psl->size++;
}

在这里插入图片描述

顺序表尾插

void SeqListPushBack(SeqList* psl, SLDataType x)
{
    assert(psl);
    CheckCapacity(psl);
    //psl->array[psl->size] = x;
    //psl->size++;
    SeqListInsert(psl, psl->size, x);
}

在这里插入图片描述

任意位置的插入

void SeqListInsert(SeqList* psl, int pos, SLDataType x)
{
    assert(psl);
    assert(0 <= pos && pos <= psl->size);
    //保证插入的数字在内存空间内
    CheckCapacity(psl);
    for (int end = psl->size; end >= pos; end--)
    {
        psl->array[end] = psl->array[end - 1];
    }
    psl->array[pos] = x;
    psl->size++;
}

在这里插入图片描述

7.顺序表——删除

头删：将第一位以后的元素全部向前移动一位，将第一位元素覆盖掉
尾删：利用size–影响数组下标，打印的时候直接会把最后一位漏掉

顺序表头删

void SeqListPopFront(SeqList* psl)
{
    assert(psl);
    assert(psl->size > 0);
    断言：当删除到个数小于0时报错
    int start = 0;
    while (start < psl->size)
    {
        psl->array[start] = psl->array[start + 1];
        start++;
    }
    psl->size--;
}

在这里插入图片描述

顺序表尾删

void SeqListPopBack(SeqList* psl)
{
    assert(psl);
    assert(psl->size > 0);//真就过，假报错、
断言：当删除到个数小于0时报错
    psl->size--;
    //直接通过size--来删去最后一个元素
}

在这里插入图片描述

8.顺序表——查找 

int SeqListFind(SeqList* psl, SLDataType x)
{
    assert(psl);
 //   assert(x >=0 && x < psl->size);
    for (int start = 0; start < psl->size; start++)
    {
        if (psl->array[start] == x)
        {
            return start;
        }
    }  
    return -1;
}

9.测试用例

void test_1()
{
    SeqList a;
    SeqListInit(&a);//初始化
    CheckCapacity(&a);//检查空间
    SeqListPushBack(&a, 1);//尾插
    SeqListPushBack(&a, 2);//尾插
    SeqListPushBack(&a, 3);//尾插
    SeqListPushBack(&a, 4);//尾插
    SeqListPushBack(&a, 5);//尾插
    SeqListPrint(&a);

    SeqListPopBack(&a);//尾删
    SeqListPopBack(&a);//尾删
    SeqListPopBack(&a);//尾删
    SeqListPopBack(&a);//尾删
    SeqListPrint(&a);
    SeqListPopBack(&a);//尾删
    SeqListPrint(&a);
    //SeqListPopBack(&a);//尾删
    //SeqListPopBack(&a);//尾删

    SeqListPushBack(&a, 1);//尾插
    SeqListPushFront(&a, -1);//头插
    SeqListPushFront(&a, -2);//头插
    SeqListPushFront(&a, -3);//头插
    SeqListPushFront(&a, -4);//头插
    SeqListPrint(&a);

    SeqListPopFront(&a);//头删
    SeqListPopFront(&a);//头删
    SeqListPopFront(&a);//头删
    SeqListPopFront(&a);//头删
    SeqListPrint(&a);
    SeqListPopFront(&a);//头删
    //SeqListPopFront(&a);//头删
    //SeqListPopFront(&a);//头删
    SeqListPrint(&a);

    SeqListInsert(&a, 0, 1000);//任意插入
    SeqListPrint(&a);
    SeqListInsert(&a, 0, 1000);//任意插入
    SeqListInsert(&a, 1, -1000);//任意插入
    SeqListInsert(&a, 2, -800);//任意插入
    SeqListInsert(&a, 0, 8000);//任意插入
    SeqListPrint(&a);

    SeqListErase(&a, 0);//任意删除
    SeqListErase(&a, 0);//任意删除
    SeqListPrint(&a);
    SeqListErase(&a, 2);//任意删除
    SeqListPrint(&a);
    SeqListErase(&a, 0);//任意删除
    SeqListPrint(&a);
    SeqListErase(&a, 0);//任意删除
    SeqListPrint(&a);

    SeqListInsert(&a, 0, 8000);//任意插入
    SeqListPrint(&a);
    SeqListInsert(&a, 0, 100);//任意插入
    SeqListPrint(&a);
    SeqListInsert(&a, 1, -100);//任意插入
    SeqListPrint(&a);
    SeqListAmend(&a, 1, 2);//修改
    SeqListPrint(&a);
    SeqListAmend(&a, 0, 1);//修改
    SeqListPrint(&a);
    SeqListAmend(&a, 2, 3);//修改
    SeqListPrint(&a);

    printf("%d\n", SeqListFind(&a, 3));//查找
    printf("%d\n", SeqListFind(&a, 4));//查找

    SeqListDestory(&a);//销毁
}
void test_2()
{
    SeqList sl;//创建顺序表变量
    SeqListInit(&sl);//初始化顺序表
    SeqListPushBack(&sl, 1);//尾插
    SeqListPushBack(&sl, 2);//尾插
    SeqListPushBack(&sl, 3);//尾插
    SeqListPushFront(&sl, 0);//头插
    SeqListPrint(&sl);//打印
    SeqListPopFront(&sl);//头删
    SeqListPopBack(&sl);//尾删
    SeqListPrint(&sl);//打印
    SeqListDestory(&sl);//销毁顺序表
}
void test_3()
{
    SeqList sl;//创建顺序表变量
    SeqListInit(&sl);//初始化顺序表
    SeqListPushBack(&sl, 1);//尾插
    SeqListPushBack(&sl, 2);//尾插
    SeqListPushBack(&sl, 3);//尾插
    SeqListInsert(&sl, 0, 0);//任意插入
    SeqListInsert(&sl, 2, 10);//任意插入
    SeqListErase(&sl, 4);//任意删除
    SeqListAmend(&sl, 1, 20);//任意修改
    SeqListPrint(&sl);//打印
    SeqListDestory(&sl);//销毁
}
void test_4()
{
    SeqList sl;
    SeqListInit(&sl);//初始化
    for (int i = 0; i < 10; i++)
    {
        SeqListPushBack(&sl, i);//循环尾插
    }
    SeqListPrint(&sl);//打印
    SeqListPushBack(&sl, 10);//尾插
    SeqListPrint(&sl);//打印
    SeqListDestory(&sl);//销毁
}
void test_5()
{
    SeqList sl;
    SeqListInit(&sl);//初始化
    for (int i = 0; i < 10; i++)
    {
        SeqListPushFront(&sl, i);//循环尾插
    }
    SeqListPrint(&sl);//打印
    SeqListPushFront(&sl, 10);//头插
    SeqListPrint(&sl);//打印
    SeqListDestory(&sl);//销毁
}
void test_6()
{
    SeqList sl;
    SeqListInit(&sl);//初始化
    SeqListPushBack(&sl, 1);//尾插
    SeqListPushBack(&sl, 2);//尾插
    SeqListPushBack(&sl, 3);//尾插
    printf("%d\n", SeqListFind(&sl, 2));//查找成功
    printf("%d\n", SeqListFind(&sl, 4));//查找失败
    SeqListDestory(&sl);
}
int main()
{
    test_1();
    test_2();
    test_3();
    test_4();
    test_5();
    test_6();
    return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Fan数据结构与算法学习之路

数据结构

c语言

002 数据结构_顺序表的实现过程——“C” 的相关文章

  • 编码技巧——校验器（职责链+抽象模版）

    日常开发中可能遇到这样的业务场景 请求从入口进来 需要经过层层的校验 通过校验后才会执行业务操作 写操作 RPC 异步消息 这里前置的多层校验流程中 从类型上看 部分是基本参数校验 部分是包含业务逻辑的校验 并且部分校验是可以并行 部分是有

  • 矩阵的分解——LU分解

    LU分解 LU分解是矩阵分解的一种 将一个矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积 有时需要再乘上一个置换矩阵 LU分解可以被视为高斯消元法的矩阵形式 在数值计算上 LU分解经常被用来解线性方程组 且在求逆矩阵和计算行列式中都是一个关

  • OSQP二次规划求解库使用说明

    OSQP二次规划求解库使用说明 贺志国 2023 5 10 1 凸二次规划的一般表达式 m i n 1 2 x

  • 微信API接口访问慢

    场景 项目需要调用微信API接口获得微信用户信息 本地开发和公司测试环境中测试十分顺利 但是在部署到现场环境中 接口调用经常会很慢 需要几分钟的时间才能返回值 现场环境的服务器因为客户原因 只能指定申请特定个别IP访问 无法开放微信接口域名

  • MySQL中常用工具

    作者 小刘在C站 个人主页 小刘主页 努力不一定有回报 但一定会有收获加油 一起努力 共赴美好人生 学习两年总结出的运维经验 以及思科模拟器全套网络实验教程 专栏 云计算技术 小刘私信可以随便问 只要会绝不吝啬 感谢CSDN让你我相遇 目录

  • vue3使用事件委托实现选项卡的切换

    选项卡是js写的 不是组件 ul li item li ul

  • 虚拟机不能上网，ifconfig显示只有lo

    1 开启虚拟机后无法上网 ifconfig查询发现只有本地环回网口 2 使用 ifconfig a 命令查三腊鉴看是否存在网卡 3 查询结果显示系统中存在ens33和ens37网卡 解决方法就是要启动ens33网卡 并配置其IP地址等信息

  • JavaScript面向对象：类的几种继承方式

    面向对象 类的几种继承方式 类与实例 类的声明 生成实例 类与继承 如何实现继承 继承的几种方式 前端小白记录学习笔记 不做他用 类与实例 类的声明 用构造函数模拟类 传统写法 function Person1 name this name

  • Java实现PDU编码

    代码一 package com zte test import java io UnsupportedEncodingException PDU编码实现 7bit 8bit 以及UCS2编码 代码主体是网上来源 Url我忘记了 很遗憾 自己

随机推荐

  • Python3 入门教程

    Python3 SMTP发送邮件 在Python3 中应用的SMTP Simple Mail Transfer Protocol 即简单邮件传输协议 它是一组用于由源地址到目的地址传送邮件的规则 由它来控制信件的中转方式 python的 s

  • 打印出数组重复的数字/数值个数

    题目 有一个长度为n的数组 里面所有元素的值都为整数 且范围为0到n 1 请列出数组中整数元素出现的次数 例 输入数组 1 6 5 3 12 2 3 2 0 1 7 4 5 打印 1 2 6 1 5 2 3 2 12 1 2 2 0 1 7

  • 学习C语言的一些比较重要的要点

    C语言笔记10 20 d 打印整型 f 打印浮点型 打小数 p 以地址的形式打印 c 打印字符型 x 打印十六进制数字 s 打印字符串 一个字节 8个比特位 字节 char 1 short 2 long 4 long long 8 floa

  • 用OpenSSL 做HMAC（C++）

    参考 http www askyb com cpp openssl hmac hasing example in cpp 名词解释 HMAC Hash based Message Authentication Code 即基于Hash的消息

  • 计算机什么是符号健,在电脑健盘上怎么打:符号

    在电脑健盘上怎么打 符号以下文字资料是由 历史新知网www lishixinzhi com 小编为大家搜集整理后发布的内容 让我们赶快一起来看一下吧 在电脑健盘上怎么打 符号 Shift L键的右侧就是 就可以 按住Shift 然后再按 L

  • Ebay账号关联怎么办？如何防关联？店铺多开干货

    Ebay是明确不允许一个卖家有多个ebay账户的 做跨境电商的朋友为了 不在一颗树上吊死 大家都想多注册几个账号开几个店铺来拦截更多流量和分摊风险 但是eBay平台规定是只允许一个卖家一个账号的 一旦检测到多开账户的情况 eBay会地把你的

  • osgEarth的shadowMap看下shadowcaster

    在application中 有osgEarth lights ShadowCaster caster osgEarth findTopMostNodeOfType

  • Ubuntu18.04 下安装CUDA，cuDNN及pytorch-gpu版本过程

    第一步 安装显卡驱动 首先添加ppa源 sudo add apt repository ppa graphics drivers ppa 更新一下 sudo apt get update 安装驱动 友情提示 如果BIOS有开启Secure

  • （esp-idf）一文看懂u8g2库点亮OLED

    github仓库地址 HawkJ02 esp32 oled github com 首先丢一个u8g2库的地址 olikraus u8g2 U8glib library for monochrome displays version 2 gi

  • JDBC基本概念

    什么是JDBC JDBC概念 JDBC Java DataBase Connectivity 是一套统一的基于Java语言的关系数据库编程接口规范 该规范允许将SQL语句作为参数通过JDBC接口发送给远端数据库 远端数据库接收到SQL语句后

  • tcp 三次握手 四次挥手

    四次挥手 为什么 和 不一起发 因为 需要服务器close客户端的套接字 但不是及时的 为了保证响应及时 就需要 比 早发 为什么是客户端先发送关闭请求 close 按图上所示 第一个发送close 的一边会在最后等待一段时间来接收对面的可

  • mysql之操作数据库的DDL语句

    1 退出mysql exit 或 quit 2 显示当前所有数据库 show databases 3 创建数据库 create database 数据库名 4 删除库文件 drop database 数据库名 5 切换正在使用的数据库 us

  • SimMIM：一种更简单的MIM方法

    自从何恺明的MAE 点击蓝字查看文章详情 出来之后 基于MIM Masked Image Modeling 的无监督学习方法越来越受到关注 这里介绍一篇和MAE同期的工作 SimMIM A Simple Framework for Mask

  • 【文件上传 后端】文件上传 后端 Part2 —— base64文件流方式

  • 大四了还在学机器学习

    依然是课程笔记 感谢杨晓春老师的指导 文章目录 绪论 概念 有监督学习无监督学习半监督学习增强学习 假设空间与特征向量的空间映射 概念学习 决策树 决策树的概念表示和适用条件 基本算法与最优分类属性的确定 信息增益 增益率 基尼指数 3种机

  • n选m

    思路 从1遍历到n 对于一个数字要么选要么不选 拿到m个数时停止 def dfs i n m res if len res m print join map str res else if i lt n res append i dfs i

  • dfs玄学剪枝法集锦

    题解 第一题 邮票面值设计问题 这道题是一道比较经典的题目 在NOIP初赛 伤心 试卷上也出现过 由于这道题没有什么比较强的剪枝 因此就不介绍了 主要思路就是枚举最大值 完全背包问题 第二题 木棒 这道题我一开始是直接上爆搜的 由于只有两组

  • day04-编程题

    知识点 数组 题目1 训练 请创建一个长度为6的整数数组 并为数组中的元素赋值 遍历数组 打印所有元素 元素之间用空格隔开 比如 数组为 1 2 3 4 5 打印结果 1 2 3 4 5 训练提示 1 数组中的元素有索引 开始索引和结束索引

  • 字节福利又刷屏了，难怪大家都说“字节三个月，人间抵一年”

    谈到大厂 内推问题无疑是绕不开的一个话题 就算没去大厂实习过 大多数同学印象中的大厂也应该是工资高 给钱痛快 福利待遇好吧 关于大厂我们最常见的进入方式想必就是内推了吧 不知道你馋了没有 如果没有 一起来欣赏下大厂的薪资和福利待遇吧 那么具

  • 002 数据结构_顺序表的实现过程——“C”

    引入 什么是顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构 一般情况下采用数组存储 在数组上完成数据的增删查改 顺序表一般可以分为 静态顺序表 使用定长数组存储元素 动态顺序表 使用动态开辟的数组存储 什么是mall

热门标签