数据结构——顺序表【C】

顺序表

  • 1. 顺序表的概念以及结构
    • 1.1概念
    • 1.2静态顺序表和动态顺序表
  • 2. 顺序表接口模拟实现
  • 接口总览
    • 2.1 初始化数据和销毁容器
  • 2.2 顺序表的尾插和尾删
    • 2.3 头插和头删
    • 2.4 任意位置插入和删除数据
    • 2.5 查找数据
  • 3. 顺序表的问题 :

1. 顺序表的概念以及结构

1.1概念

顺序表就是用一段物理地址连续空间储存元素的线性结构,在正常情况下采用数组存储,在数组上完成增删查改等操作。

1.2静态顺序表和动态顺序表

  1. 静态顺序表: 使用长数组存储数据(数组的长度是固定的)
  2. 动态顺序表: 动态开辟数组存储(根据需求来设定数组长度)

2. 顺序表接口模拟实现

接口总览

typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a; //指向动态开辟的数组int size;//数组中有效数据的个数int capacity;//容器空间大小
}SL;void SLInit(SL* psl); //顺序表初始化void SLDestory(SL* psl);//顺序表的销毁void SLPrint(SL* psl);//打印顺序表中的元素void SLPushBack(SL* psl, SLDatatype num);//尾插void SLPushFront(SL* psl, SLDatatype num);//头插void SLPopBack(SL* psl);//尾删void SLPopFront(SL* psl);//头删void SLInsert(SL* psl, int pos, SLDatatype num);//从任意位置插入数据int SLFind(SL* psl, SLDatatype num);//查找顺序表中的元素void SLErase(SL* psl, int pos);//删除任意位置的元素

2.1 初始化数据和销毁容器

初始化数据:
设置指向数组的指针为空,有效数据个数和容器空间大小设置为0。

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

销毁容器:
所释放动态开辟数组的空间,并设置指向的指针为空指针,有效数据个数和容器空间大小设置为0。

void SLDestory(SL* psl)
{assert(psl); //判断psl是否为空free(psl->a);psl->a = NULL;psl->size = psl->capacity = 0;}

2.2 顺序表的尾插和尾删

在尾插只前我们还要考虑容器是否有足够的空间,若是足够直接插入数据,若是不够则需要动态开辟数组。
注意我们这里默认开辟两倍的空间,在实际中要需要根据需求来开辟容器空间。

void SLCheckCapacity(SL* psl)
{assert(psl);if (psl->size == psl->capacity)//若是容器中的有效元素等于容器间就要扩容{int newcapacity = psl->capacity == 0 ? 4 : 2 * psl->capacity;SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * newcapacity);if (tmp == NULL){perror("realloc");return;}psl->a = tmp;psl->capacity = newcapacity;}
}

尾插:
首先我们要判断容器空间大小,不足则扩容,足够则插入数据。尾插十分容易直接在数组末尾插入数据即可,有效数据加一。
在这里插入图片描述

void SLPushBack(SL* psl, SLDatatype num)
{assert(psl);SLCheckCapacity(psl);psl->a[psl->size++] = num;
}

尾删:
同样的尾删也很容易,只需要将有效数据size-1即可。在这里插入图片描述

void SLPopBack(SL* psl)
{assert(psl);assert(psl->size > 0);psl->size--;
}

2.3 头插和头删

头插:
首先还是容器大小的老问题,不足则扩容,足够则插入数据。头插与尾插不同的是,需要挪动数据将数组中的每一个元素向后移动一位,然后我们在空出的头位置插入数据。
在这里插入图片描述

void SLPushFront(SL* psl, SLDatatype num)
{assert(psl);SLCheckCapacity(psl);int end = psl->size - 1;while (end >= 0){psl->a[end + 1] = psl->a[end];end--;}psl->a[0] = num;psl->size++;
}

头删:
头删也是同样的,让开始位置的后一个数据向前覆盖,将有效数据size-1即可。
在这里插入图片描述

void SLPopFront(SL* psl)
{assert(psl);int begin = 1;while (begin < psl->size){psl->a[begin - 1] = psl->a[begin];begin++;}psl->size--;
}

2.4 任意位置插入和删除数据

任意位置插入数据:
这里任意位置的数据就是容器中任意元素下标位置,同样的插入数据还使用挪动数据,将末尾到pos位置的数据向后挪动一位,在空出的pos位置插入数据。

void SLInsert(SL* psl,int pos, SLDatatype num)
{assert(psl);SLCheckCapacity(psl);int end = psl->size;while (end >= pos){psl->a[end] = psl->a[end - 1];end--;}psl->a[pos] = num;psl->size++; }

任意位置删除数据:
删除pos位置的数据,还是一样挪动覆盖。

void SLErase(SL* psl,int pos)
{assert(psl);int end = pos;while (end <= psl->size - 1){psl->a[end] = psl->a[end + 1];end++;}psl->size--;
}

2.5 查找数据

通过遍历容器中的元素,若是查到则返回元素下标,若是没有找到则返回-1。

int SLFind(SL* psl,SLDatatype num)
{assert(psl);for (int i = 0; i < psl->size; i++){if (psl->a[i] == num){return i;}}return -1;
}

3. 顺序表的问题 :

  1. 尾部插入的效率还行,头部或者中间插入删除(时间复杂度尾O(N))、需要挪动数据、效率低下。
  2. 满了以后只能扩容。扩容式有一定的消耗的,扩容一般是存在一定的空间浪费。
    (假设空间是100满了,扩容到200,但是只需要插入120个数据,因此有80个空间就浪费掉了,一次扩的越多,可能浪费的越多,一次扩少了,那么有可能就会频繁的扩容)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

利用亚马逊云科技云原生Serverless代码托管服务开发OpenAI ChatGPT-4o应用

今天小李哥继续介绍国际上主流云计算平台亚马逊云科技AWS上的热门生成式AI应用开发架构。上次小李哥分享​了利用谷歌云serverless代码托管服务Cloud Functions构建Gemini Pro API​&#xff0c;这次我将介绍如何利用亚马逊的云原生服务Lambda调用OpenAI的最新模型ChatGPT 4o。…

初识SpringBoot

1.Maven Maven是⼀个项⽬管理⼯具, 通过pom.xml⽂件的配置获取jar包&#xff0c;⽽不⽤⼿动去添加jar包 主要功能 项⽬构建管理依赖 构建Maven项目 1.1项目构建 Maven 提供了标准的,跨平台(Linux, Windows, MacOS等)的⾃动化项⽬构建⽅式 当我们开发了⼀个项⽬之后, 代…

LLM指令微调Prompt的最佳实践(六):基于ChatGPT搭建聊天机器人

文章目录 1. 前言2. Prompt定义3. 搭建聊天机器人Chatbot3.1 角色定义1. system2. assistant3. user4. 总结 3.2 初始函数3.3 讲笑话机器人3.4 订餐机器人 4. 参考 1. 前言 前情提要&#xff1a; 《LLM指令微调Prompt的最佳实践&#xff08;一&#xff09;&#xff1a;Prompt原…

Apache AGE 安装部署

AGE概述 概述 我们可以通过源码安装、拉取docker镜像运行、直接使用公有云三种方式中的任意一种来使用Apache AGE 获取 AGE 发布版本 可以在 https://github.com/apache/age/releases 找到发布版本和发布说明。 源代码 源代码可以在 https://github.com/apache/age 找到…

万字长文整理Java多线程相关面试题

目录 ​1. 什么是线程和进程&#xff1f; 线程与进程有什么区别&#xff1f; 那什么是上下文切换&#xff1f; 进程间怎么通信&#xff1f; 什么是用户线程和守护线程&#xff1f; 2. 并行和并发的区别&#xff1f; 3. 创建线程的几种方式&#xff1f; Runnable接口和C…

Codeforces Round 954 (Div. 3) F. Non-academic Problem

思路&#xff1a;考虑缩点&#xff0c;因为是无向图&#xff0c;所以双连通分量缩完点后是一棵树&#xff0c;我们去枚举删除每一条树边的答案&#xff0c;然后取最小值即可。 #include <bits/stdc.h>using namespace std; const int N 3e5 5; typedef long long ll; …

3-6 构建线性模型解决温度计示数转换问题

3-6 构建线性模型解决温度计示数转换问题 直接上源码 %matplotlib inline import numpy as np import torch torch.set_printoptions(edgeitems2, linewidth75)导入必要的库并设置 PyTorch 的打印选项&#xff0c;确保在打印张量时显示边缘项和行宽。 #%% t_c [0.5, 14.0,…

gpt-4o看图说话-根据图片回答问题

问题&#xff1a;中国的人口老龄化究竟有多严重&#xff1f; 代码下实现如下&#xff1a;&#xff08;直接调用openai的chat接口&#xff09; import os import base64 import requests def encode_image(image_path): """ 对图片文件进行 Base64 编码 输入…

phpexcel导入导出

前言&#xff1a; 如果你到处的excel软件打开有问题&#xff0c;下面有介绍解决办法 导入 1. composer init 初始化 2. 下载phpspreadsheet 这里需要注意php版本&#xff0c;需要大于7.2 composer require phpoffice/phpspreadsheet3. 编写代码 <?php require vendo…

Linux多进程和多线程(八)多线程

多线程 线程定义线程与进程线程资源 线程相关命令 pidstat 命令 top 命令ps 命令常见的并发方案 1. 多进程模式2. 多线程模式 创建线程 1. pthread_create() 示例:创建一个线程 2. pthread_exit() 退出线程3. pthread_join() 等待线程结束 示例: 线程分离 创建多个线程 示例 1:…

“郑商企航”暑期社会实践赴美丽美艳直播基地开展调研

马常旭文化传媒网讯&#xff08;记者张明辉报道&#xff09;导读&#xff1a;2024 年 7 月 3 日&#xff0c;商学院暑期社会实践团“郑商企航”在河南省郑州市新密市岳村镇美丽美艳直播基地&#xff0c;展开了一场意义非凡的考察活动&#xff0c;团队成员深度调研了直播基地的产…

CTF php RCE(二)

0x04 php伪协议 这种我们是先看到了include才会想到&#xff0c;利用伪协议来外带文件内容&#xff0c;但是有些同学会问&#xff0c;我们怎么知道文件名是哪个&#xff0c;哪个文件名才是正确的&#xff0c;那么这里我们就得靠猜了 include函数 因为 include 是一个特殊的语…

C++笔试强训3

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 一、选择题1-5题6-10题 二、编程题题目一题目二 一、选择题 1-5题 如图所示&#xff0c;如图所示p-3指向的元素是6&#xff0c;printf里面的是%s&#xff0c;从6开…

Python入门 2024/7/8

目录 数据容器 dict(字典&#xff0c;映射) 语法 定义字典字面量 定义字典变量 定义空字典 从字典中基于key获取value 字典的嵌套 字典的常用操作 新增元素 更新元素 删除元素 清空字典 获取全部的key 遍历字典 统计字典内的元素数量 练习 数据容器的通用操作…

SQLite 命令行客户端 + Windows 批处理应用

SQLite 命令行客户端 Windows 批处理应用 下载 SQLite 客户端1. Bat 辅助脚本1. 执行SQL.bat执行 2. 导出Excel.bat执行效果 3. 导出HTML.bat执行效果 4. 清空-订单表.bat5. 订单表.bat 2. 测试 SQL1. 创建订单表.sql2. 插入订单表.sql3. 查询订单表.sql4. 清空订单表.sql5. 删…

Sentinel-1 Level 1数据处理的详细算法定义(二)

《Sentinel-1 Level 1数据处理的详细算法定义》文档定义和描述了Sentinel-1实现的Level 1处理算法和方程&#xff0c;以便生成Level 1产品。这些算法适用于Sentinel-1的Stripmap、Interferometric Wide-swath (IW)、Extra-wide-swath (EW)和Wave模式。 今天介绍的内容如下&…

Vuforia AR篇(八)— AR塔防上篇

目录 前言一、设置Vuforia AR环境1. 添加AR Camera2. 设置目标图像 二、创建塔防游戏基础1. 导入素材2. 搭建场景3. 创建敌人4. 创建脚本 前言 在增强现实&#xff08;AR&#xff09;技术快速发展的今天&#xff0c;Vuforia作为一个强大的AR开发平台&#xff0c;为开发者提供了…

前端图表库G2快速上手

文档地址&#xff1a; https://g2-v3.antv.vision/zh/docs/manual/getting-started/ https://g2.antv.antgroup.com/ 安装&#xff1a; pnpm i antv/g2在vue3中使用&#xff1a; <script setup> import {Chart} from antv/g2; import {onMounted} from "vue"…

python_zabbix

zabbix官网地址&#xff1a;19. API19. APIhttps://www.zabbix.com/documentation/4.2/zh/manual/api 每个版本可以有些差异&#xff0c;选择目前的版本在查看对于的api接口#token接口代码 import requests apiurl "http://zabbix地址/api_jsonrpc.php" data {&quo…

五、保存数据到Excel、sqlite(爬虫及数据可视化)

五、保存数据到Excel、sqlite&#xff08;爬虫及数据可视化&#xff09; 1&#xff0c;保存数据到excel1.1 保存九九乘法表到excel&#xff08;1&#xff09;代码testXwlt.py&#xff08;2&#xff09;excel保存结果 1.2 爬取电影详情并保存到excel&#xff08;1&#xff09;代…