顺序表基本操作全面解析

文章目录

  • 1.线性表
  • 2.顺序表分类
    • 2.1 静态顺序表
    • 2.2 动态顺序表
  • 3. 顺序表各接口实现
    • 1. 定义结构体`(Seqlist)`
    • 2. 结构体初始化`(SLInit)`
    • 3.检查容量 `(SLCheckCapacity)`
    • 4.打印数据 `(SLPrintf)`
    • 5.插入操作
      • 5.1 从数据头部插入`(SLPushFront)`
      • 5.2 从数据尾部插入`(SLPushBack)`
      • 5.3 从任意下标位置的插入`(SLInsert)`
    • 6.删除操作
      • 6.1 从数据头部删除`(SLPopFront)`
      • 6.2 从数据尾部删除`(SLPopBack)`
      • 6.3 从任意下标位置的删除`(SLErase)`
    • 7 销毁操作 `(SLDestroy)`
  • 4.完整代码
    • 4.1 SeqList.h文件
    • 4.2 SeqList.c文件
    • 4.3 Test.c文件

1.线性表

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

案例：蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合

2.顺序表分类

顺序表和数组的区别：
顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口

2.1 静态顺序表

静态顺序表概念：使用定长数组存储元素
缺点是定义空间小了不够用，定义大了浪费，不好把控。

在这里插入图片描述

2.2 动态顺序表

动态顺序表概念：使用动态开辟的数组存储。
动态顺序表 根据自己的需求调整大小，
在这里插入图片描述

3. 顺序表各接口实现

首先建立3个文件
1.SeqList.h头文件,用来声明函数
2.SeqList.c文件，用来定义函数
3.Test.c文件，用来测试函数

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

1. 定义结构体(Seqlist)

在SeqList.h头文件中

typedef int SLDataType;

typedef struct Seqlist
{
  SLDataType* a;
  int size;       // 有效数据
  int capacity;   // 空间容量
}SL;

2. 结构体初始化(SLInit)

注意下述代码皆是：
在SeqList.h头文件中定义函数
在SeqList.c文件中实现函数
在Test.c文件中测试函数

SeqList.h文件中
定义函数：
在这里插入图片描述
SeqList.c文件中
实现函数：

 void SLInit(SL *ps)     // 数据表初始化
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}

Test.c文件中
测试函数：

int main()
{
  SL s1;
  SLInit(&s1);
  return 0;
}

调试结果：
在这里插入图片描述

3.检查容量 (SLCheckCapacity)

定义函数：
在这里插入图片描述
实现函数：

void SLCheckCapacity(SL* ps)  // 检查内存是否足够，不够就扩容。
{
	//一般情况为了避免频繁插入数据而增容，或者一下开辟很大的空间，我们一般是每次增容2倍
	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)
      {
        perror("realloc fail");
        return;
      }
      ps->a = tmp;
      ps->capacity = newCapacity;
    }
}

测试函数：

int main()
{
  SL s1;
  SLInit(&s1);
  SLCheckCapacity(&s1);
  return 0;
}

调试结果：
在这里插入图片描述

4.打印数据 (SLPrintf)

定义函数：
在这里插入图片描述
实现函数：

void SLPrintf(SL* ps)   // 数据表打印
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}

5.插入操作

5.1 从数据头部插入(SLPushFront)

定义函数：
在这里插入图片描述
实现函数：

void SLPushFront(SL* ps, SLDataType x)  // 头插
{
  assert(ps);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
}

动图解析：
在这里插入图片描述

测试函数结果：
在这里插入图片描述

5.2 从数据尾部插入(SLPushBack)

定义函数：
在这里插入图片描述
实现函数：

void SLPushBack(SL* ps, SLDataType x)   // 尾插
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->a[ps->size++] = x;
}

动图解析：
在这里插入图片描述

测试函数结果：
在这里插入图片描述

5.3 从任意下标位置的插入(SLInsert)

定义函数：
在这里插入图片描述

实现函数：

void SLInsert(SL* ps, int pos, SLDataType x)  // 任意下标位置的插入
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

动图解析：
在这里插入图片描述

测试函数结果：
在这里插入图片描述

6.删除操作

6.1 从数据头部删除(SLPopFront)

定义函数：
在这里插入图片描述

实现函数：

void SLPopFront(SL* ps) // 头删
{
  assert(ps);
  assert(ps->size>0);
  int begin = 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

动图解析：
在这里插入图片描述

测试函数结果：
在这里插入图片描述

6.2 从数据尾部删除(SLPopBack)

定义函数：
在这里插入图片描述
实现函数：

void SLPopBack(SL* ps)  // 尾删
{
  assert(ps);
  assert(ps->size>0);
  ps->size--;
}

动图解析：
在这里插入图片描述

测试函数结果：
在这里插入图片描述

6.3 从任意下标位置的删除(SLErase)

定义函数：
在这里插入图片描述

实现函数：

void SLErase(SL* ps, int pos)    // 任意下标位置的删除
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);   
  // 这里删除不能用等于ps->size,ps->size看作下标的话相当于下标的最后一个位置+1
  
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

动图解析：
在这里插入图片描述

测试函数结果：
在这里插入图片描述

7 销毁操作 (SLDestroy)

定义函数：
在这里插入图片描述

实现函数：

void SLDestroy(SL* ps)  // 数据表销毁
{
  assert(ps);
  if (ps->a != NULL)
  {
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
  }
}

在这里插入图片描述

4.完整代码

4.1 SeqList.h文件

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;

typedef struct Seqlist
{
  SLDataType* a;
  int size;       // 有效数据
  int capacity;   // 空间容量
}SL;

void SLInit(SL *ps);    // 数据表初始化
void SLDestroy(SL *ps); // 数据表销毁

void SLPushFront(SL* ps, SLDataType x); // 头插
void SLPushBack(SL *ps ,SLDataType x);  // 尾插

void SLPopFront(SL* ps);  // 头删
void SLPopBack(SL* ps);   // 尾删


void SLCheckCapacity(SL* ps); // 检查内存是否足够，不够就扩容。
void SLPrintf(SL* ps);  // 数据表打印

void SLInsert(SL* ps, int pos, SLDataType x);  //任意下标位置的插入
void SLErase(SL* ps, int pos);  //任意下标位置的删除

4.2 SeqList.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void SLCheckCapacity(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)
      {
        perror("realloc fail");
        return;
      }
      ps->a = tmp;
      ps->capacity = newCapacity;
    }
}

void SLPrintf(SL* ps)   // 数据表打印
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
    printf("%d ", ps->a[i]);
  }
  printf("\n");
}


void SLInit(SL *ps)     // 数据表初始化
{
  assert(ps);
  ps->a = NULL;
  ps->size = 0;
  ps->capacity = 0;
}

void SLDestroy(SL* ps)  // 数据表销毁
{
  assert(ps);
  if (ps->a != NULL)
  {
    free(ps->a);
    ps->a = NULL;
    ps->size = 0;
    ps->capacity = 0;
  }
}

void SLPushFront(SL* ps, SLDataType x)  // 头插
{
  assert(ps);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= 0)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
}

void SLPushBack(SL* ps, SLDataType x)   // 尾插
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->a[ps->size++] = x;
}



void SLPopFront(SL* ps) // 头删
{
  assert(ps);
  assert(ps->size > 0);
  int begin = 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

void SLPopBack(SL* ps)  // 尾删
{
  assert(ps);
  assert(ps->size>0);
  ps->size--;
}

// pos是下标
void SLInsert(SL* ps, int pos, SLDataType x)  // 任意下标位置的插入
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

void SLErase(SL* ps, int pos)    // 任意下标位置的删除
{
  assert(ps);
  assert(pos >= 0 && pos < ps->size);   // 这里删除不能用等于ps->size,ps->size看作下标的话相当于下标的最后一个位置+1
  int begin = pos + 1;
  while (begin < ps->size)
  {
    ps->a[begin - 1] = ps->a[begin];
    begin++;
  }
  ps->size--;
}

4.3 Test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

void TestSL1()  // 头插,尾插
{
  printf("TestSL1:\n");
  SL s1;
  SLInit(&s1);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPrintf(&s1);  
}

void TestSL2()  // 头删,尾删
{
  printf("TestSL2:\n");
  SL s1;
  SLInit(&s1);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPrintf(&s1);
  SLPopBack(&s1);
  SLPopFront(&s1);
  SLPrintf(&s1);
}

void TestSL3()//任意下标位置的插入,删除测试
{
  printf("TestSL3:\n");
  SL s1;
  SLInit(&s1);
  SLPushFront(&s1, 10);
  SLPushBack(&s1, 30);
  SLPrintf(&s1);
  SLInsert(&s1, 1, 520);
  SLPrintf(&s1);
  SLErase(&s1, 2);
  SLPrintf(&s1);
}

int main()
{
  TestSL1();
  TestSL2();
  TestSL3();
}

运行结果如下：
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/183060.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ELK企业级日志分析平台——kibana数据可视化

ELK企业级日志分析平台——kibana数据可视化

部署 新建虚拟机server5&#xff0c;部署kibana [rootelk5 ~]# rpm -ivh kibana-7.6.1-x86_64.rpm [rootelk5 ~]# cd /etc/kibana/[rootelk5 kibana]# vim kibana.ymlserver.host: "0.0.0.0"elasticsearch.hosts: ["http://192.168.56.11:9200"]i18n.local…
阅读更多...
项目管理套路：看这一篇绝对够用❤️

项目管理套路：看这一篇绝对够用❤️

写论文必不可少的&#xff0c;就是创建代码并进行实验。好的项目管理可以让实验进行得更加顺利。本篇博客以一次项目实践为例&#xff0c;介绍项目管理的方法&#xff0c;以及可能遇到的问题&#xff0c;并提供一些可行的解决方案。 目录 项目管理工具开始第一步版本管理十分关…
阅读更多...
ATFX汇市：11月美联储会议纪要提振美指，但中期跌势或将延续

ATFX汇市：11月美联储会议纪要提振美指，但中期跌势或将延续

ATFX汇市&#xff1a;11月21日公布的11月美联储利率决议会议纪要提到&#xff1a;过去一年通胀有所缓和&#xff0c;但目前通胀仍然高得令人无法接受&#xff0c;远高于委员会 2% 的长期目标&#xff1b;在消费者支出激增的推动下&#xff0c;第三季度实际 GDP 出人意料地强劲增…
阅读更多...
【C++干货铺】适配器 | stack | queue

【C++干货铺】适配器 | stack | queue

个人主页点击直达&#xff1a;小白不是程序媛 C系列学习专栏&#xff1a;C干货铺 代码仓库&#xff1a;Gitee 目录 stack的介绍和使用 stack的介绍 stack的使用 queue的介绍和使用 queue的介绍 queue的使用 容器适配器 什么是适配器 STL中stack和queue的底层结构 d…
阅读更多...
Python 使用XlsxWriter操作Excel

Python 使用XlsxWriter操作Excel

在数据处理和报告生成的领域中&#xff0c;Excel 文件一直是广泛使用的标准格式。为了让 Python 开发者能够轻松创建和修改 Excel 文件&#xff0c;XlsxWriter 库应运而生。XlsxWriter 是一个功能强大的 Python 模块&#xff0c;专门用于生成 Microsoft Excel 2007及以上版本&a…
阅读更多...
外部中断为什么会误触发？

外部中断为什么会误触发？

今天在写外部中断的程序的时候&#xff0c;发现中断特别容易受到干扰&#xff0c;我把手放在对应的中断引脚上&#xff0c;中断就一直触发&#xff0c;没有停过。经过一天的学习&#xff0c;找到了几个解决方法&#xff0c;所以写了这篇笔记。如果你的中断也时不时会误触发&…
阅读更多...
人工智能教程（一）：基础知识

人工智能教程（一）：基础知识

目录 前言 什么是人工智能&#xff1f; 教学环境搭建 向量和矩阵 前言 如果你是关注计算机领域最新趋势的学生或从业者&#xff0c;你应该听说过人工智能、数据科学、机器学习、深度学习等术语。作为人工智能系列文章的第一篇&#xff0c;本文将解释这些术语&#xff0c;并搭…
阅读更多...
Spring事务的实现方式和实现原理；事务声明的方式，Spring的事务传播行为，spring事务的实现原理

Spring事务的实现方式和实现原理；事务声明的方式，Spring的事务传播行为，spring事务的实现原理

Spring事务的实现方式和实现原理 Spring事务的本质其实就是数据库对事务的支持&#xff0c;没有数据库的事务支持&#xff0c;spring是无法提供事务功能的。真正的数据库层的事务提交和回滚是通过binlog或者redo log实现的。 什么是事务 数据库事务是指作为单个逻辑工作单元执…
阅读更多...
Ubuntu安装CUDA驱动

Ubuntu安装CUDA驱动

Ubuntu安装CUDA驱动 前言官网安装确认安装版本安装CUDA Toolkit 前言 CUDA驱动一般指CUDA Toolkit&#xff0c;可通过Nvidia官网下载安装。本文介绍安装方法。 官网 CUDA Toolkit 最新版&#xff1a;CUDA Toolkit Downloads | NVIDIA Developer CUDA Toolkit 最新版文档&…
阅读更多...
【【Linux系统下常用指令学习 之 二 】】

【【Linux系统下常用指令学习 之 二 】】

Linux系统下常用指令学习 之 二 文件查询和搜索 文件的查询和搜索也是最常用的操作&#xff0c;在嵌入式 Linux 开发中常常需要在 Linux 源码文件中查询某个文件是否存在&#xff0c;或者搜索哪些文件都调用了某个函数等等。 1、命令 find find 命令用于在目录结构中查找文件…
阅读更多...
Dubbo3使用Zookeeper作为注册中心的方案讨论！详解DubboAdmin与PrettyZoo来监控服务的优劣！

Dubbo3使用Zookeeper作为注册中心的方案讨论！详解DubboAdmin与PrettyZoo来监控服务的优劣！

文章目录 一&#xff1a;Dubbo注册中心的基本使用 二&#xff1a;Zookeeper注册中心的使用 1&#xff1a;依赖引入 2&#xff1a;实际开发 三&#xff1a;Zookeeper作为注册中心的使用展示 1&#xff1a;启动注册Zookeeper服务 2&#xff1a;引入注册中心 (一)&#xf…
阅读更多...
Qt实现自定义IP地址输入控件（百分百还原Windows 10网络地址输入框）

Qt实现自定义IP地址输入控件（百分百还原Windows 10网络地址输入框）

在开发网络相关的程序时，我们经常需要输入IP地址，例如源地址和目标地址。Qt提供了一些基础的控件，如QLineEdit，但是它们并不能满足我们对IP地址输入的要求，例如限制输入的格式、自动跳转到下一个输入框、处理回车和退格键等。因此，我们需要自己编写一个自定义的IP地址输入…
阅读更多...
【MySQL】内连接和外连接

【MySQL】内连接和外连接

内连接和外连接 前言正式开始内连接外连接左外连接右外连接 前言 前一篇讲多表查询的时候讲过笛卡尔积&#xff0c;其实笛卡尔积就算一种连接&#xff0c;不过前一篇讲的时候并没有细说连接相关的内容&#xff0c;本篇就来详细说说表的连接有哪些。 本篇博客中主要用到的还是…
阅读更多...
设计模式之建造者（Builder）模式

设计模式之建造者（Builder）模式

目录 1、什么是建造者Builder模式&#xff1f; 2、建造者Builder模式的利与弊 3、建造者Builder模式的应用场景 4、建造者模式中的指导者&#xff08;Director&#xff09;有什么作用&#xff1f; 5、建造者Builder模式与其他模式的关系 小结 1、什么是建造者Builder模式…
阅读更多...
【华为OD题库-037】跳房子2-java

【华为OD题库-037】跳房子2-java

题目 跳房子&#xff0c;也叫跳飞机&#xff0c;是一种世界性的儿童游戏游戏。参与者需要分多个回合按顺序跳到第1格直到房子的最后一格&#xff0c;然后获得一次选房子的机会&#xff0c;直到所有房子被选完&#xff0c;房子最多的人获胜。 跳房子的过程中&#xff0c;如果有踩…
阅读更多...
外部网关协议_边界网关协议BGP

外部网关协议_边界网关协议BGP

一.边界网关协议BGP的基本概念 边界网关协议(Border Gateway Protocol&#xff0c;BGP&#xff09;属于外部网关协议EGP这个类别&#xff0c;用于自治系统AS之间的路由选择协议。由于在不同AS内度量路由的“代价”(距离、带宽、费用等&#xff09;可能不同&#xff0c;因此对于…
阅读更多...
SQL Server 百万数据查询优化技巧三十则

SQL Server 百万数据查询优化技巧三十则

点击上方蓝字关注我 互联网时代的进程越走越深&#xff0c;使用MySQL的人也越来越多&#xff0c;关于MySQL的数据库优化指南很多&#xff0c;而关于SQL SERVER的T-SQL优化指南看上去比较少&#xff0c;近期有学习SQLSERVER的同学问到SQL SERVER数据库有哪些优化建议&#xff1f…
阅读更多...
【基础知识】AB软件RSLinx的版本说明

【基础知识】AB软件RSLinx的版本说明

哈喽&#xff0c;大家好&#xff0c;我是雷工&#xff01; 之前对AB的软件了解比较少&#xff0c;在工作中未接触过&#xff0c;最近一次现场勘察时&#xff0c;有很多中控系统都是AB的&#xff0c;借此机会对AB软件有了些许了解。 一、RSLinx是什么软件&#xff1f; RSLinx是…
阅读更多...
微服务实战系列之签名Sign

微服务实战系列之签名Sign

前言 昨日恰逢“小雪”节气&#xff0c;今日寒风如约而至。清晨的马路上&#xff0c;除了洋洋洒洒的落叶&#xff0c;就是熙熙攘攘的上班族。眼看着&#xff0c;暖冬愈明显了&#xff0c;叶子来不及泛黄就告别了树。变化总是在不经意中发生&#xff0c;容不得半刻糊涂。 上集博…
阅读更多...
洛谷 P1883 函数

洛谷 P1883 函数

P1883 函数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) Error Curves - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 这两题是一模一样的&#xff0c;过一题水两题。 分析 主要难点在于证明F(x)是一个单峰函数可以被三分&#xff0c;但是我随便画了几个f(x)之后发现好像…
阅读更多...
最新文章

Copyright @ 2022~2023