重生之“我打数据结构，真的假的？”--1.顺序表（无习题）

在这里插入图片描述

C语言中的顺序表详细总结

1. 概述

顺序表（Sequential List）是一种线性数据结构，用于存储具有相同数据类型的一组元素。顺序表采用一段连续的存储空间，使用数组来实现，能够高效地支持随机访问操作。在 C 语言中，顺序表的实现通常基于数组，并且用户需要手动管理内存。顺序表适合用来解决需要快速访问元素的场景，尤其是当元素的数量较为稳定、不需要频繁插入或删除时。本文将详细讨论顺序表的定义、实现、各种操作的具体实现代码，以及顺序表的优缺点和实际应用场景。

2. 顺序表的基本概念

2.1 顺序表的定义

顺序表是一种存储线性表的顺序存储结构，其存储单元采用一段连续的内存区域，可以直接通过索引来访问任意元素。这使得顺序表在进行随机访问时效率非常高，时间复杂度为 O(1)。然而，由于内存是连续的，所以在插入或删除元素时，可能需要移动大量的数据，因此插入和删除操作的时间复杂度较高。

2.2 顺序表的特点

  • 连续存储：顺序表的元素存储在连续的内存空间中。
  • 随机访问：可以通过下标直接访问元素，时间复杂度为 O(1)。
  • 内存分配：顺序表的内存大小通常在初始化时分配，若需要动态扩展，则需要重新分配内存。

3. 顺序表的基本操作实现

顺序表的基本操作包括初始化、插入、删除、查找和遍历。以下我们通过 C 语言代码实现这些操作，以帮助理解顺序表的工作原理。

3.1 顺序表的数据结构定义

首先，定义顺序表的结构体。该结构体包含一个指针指向存储数据的数组，以及顺序表的当前长度和最大容量。

#include <stdio.h>
#include <stdlib.h>#define INITIAL_CAPACITY 10// 顺序表结构体定义
typedef struct {int *data;       // 存储数据的数组int length;      // 当前顺序表的长度int capacity;    // 顺序表的容量
} SequentialList;

在上述代码中，我们定义了一个名为 SequentialList 的结构体，其中 data 是一个指向 int 类型数组的指针，length 表示当前顺序表中的元素个数，capacity 表示顺序表的最大容量。

3.2 初始化顺序表

接下来，实现初始化顺序表的函数。该函数分配一段内存作为顺序表的存储空间，并初始化其长度和容量。

// 初始化顺序表
SequentialList* initList(int capacity) {SequentialList *list = (SequentialList*)malloc(sizeof(SequentialList));if (list == NULL) {printf("内存分配失败\n");exit(1);}list->data = (int*)malloc(sizeof(int) * capacity);if (list->data == NULL) {printf("内存分配失败\n");free(list);exit(1);}list->length = 0;list->capacity = capacity;return list;
}

该函数首先为 SequentialList 结构体本身分配内存，然后为数据数组分配内存，并设置初始长度为 0，容量为传入的参数值。

3.3 插入元素

顺序表支持在指定位置插入元素。如果插入的位置无效或者顺序表已满，则需要进行相应处理。

// 插入元素
int insertElement(SequentialList *list, int index, int value) {if (index < 0 || index > list->length) {printf("插入位置无效\n");return 0;}// 如果顺序表已满，扩展容量if (list->length == list->capacity) {int newCapacity = list->capacity * 2;int *newData = (int*)realloc(list->data, sizeof(int) * newCapacity);if (newData == NULL) {printf("内存扩展失败\n");return 0;}list->data = newData;list->capacity = newCapacity;}// 从插入位置开始，向后移动元素for (int i = list->length; i > index; i--) {list->data[i] = list->data[i - 1];}// 插入新元素list->data[index] = value;list->length++;return 1;
}

该函数首先检查插入位置是否合法，然后判断顺序表是否已满，若已满则通过 realloc 扩展顺序表的容量。接着，将插入位置之后的元素依次后移，最后将新元素插入到指定位置。

3.4 删除元素

顺序表的删除操作同样涉及到移动元素。删除指定位置的元素后，需要将后续元素前移，以保持顺序表的连续性。

// 删除元素
int deleteElement(SequentialList *list, int index) {if (index < 0 || index >= list->length) {printf("删除位置无效\n");return 0;}// 从删除位置开始，向前移动元素for (int i = index; i < list->length - 1; i++) {list->data[i] = list->data[i + 1];}list->length--;return 1;
}

该函数首先检查删除位置是否合法，然后将删除位置之后的所有元素向前移动一个位置，最后减少顺序表的长度。

3.5 查找元素

查找元素的操作可以分为按值查找和按索引查找。

  • 按值查找：找到指定值在顺序表中的位置。
// 查找元素（按值查找）
int findElementByValue(SequentialList *list, int value) {for (int i = 0; i < list->length; i++) {if (list->data[i] == value) {return i;  // 返回找到的索引}}return -1;  // 未找到
}

该函数遍历顺序表中的所有元素，找到与指定值匹配的元素，并返回其索引。如果没有找到，返回 -1。

  • 按索引查找：获取指定索引处的元素。
// 查找元素（按索引查找）
int getElementByIndex(SequentialList *list, int index, int *value) {if (index < 0 || index >= list->length) {printf("索引无效\n");return 0;}*value = list->data[index];return 1;
}

该函数检查索引是否合法，然后通过索引获取元素的值。

3.6 遍历顺序表

遍历顺序表中的所有元素并打印出来。

// 遍历顺序表
void traverseList(SequentialList *list) {for (int i = 0; i < list->length; i++) {printf("%d ", list->data[i]);}printf("\n");
}

该函数从头到尾遍历顺序表中的所有元素，并将它们打印到控制台。

4. 顺序表的优缺点

4.1 优点

  1. 随机访问效率高：顺序表支持通过下标访问任意元素，时间复杂度为 O(1)，这使得其在需要频繁随机访问的场景中表现优异。
  2. 内存紧凑：顺序表中的元素存储在连续的内存空间中，因此不存在指针的额外内存开销。
  3. 遍历效率高：由于顺序表使用连续的存储空间，遍历顺序表时可以很好地利用 CPU 缓存，提高访问效率。

4.2 缺点

  1. 插入和删除效率低：在顺序表中插入或删除元素时，可能需要移动大量的元素，时间复杂度为 O(n)。
  2. 内存分配不灵活：顺序表需要预先分配连续的内存，当需要扩展容量时，可能需要重新分配内存并复制原有数据，成本较高。
  3. 空间利用率问题：如果预分配的容量过大，会造成内存浪费；如果容量不足，需要频繁扩展，会影响性能。

5. 顺序表的应用场景

顺序表适用于以下场景：

  • 频繁随机访问：顺序表支持 O(1) 的随机访问，适合需要频繁访问任意位置元素的场景。
  • 元素数量相对固定：如果元素数量相对固定，不需要频繁插入和删除，顺序表是一个较好的选择。
  • 需要遍历操作：由于顺序表的元素存储在连续的内存空间中，遍历顺序表时可以充分利用 CPU 缓存，提高效率。

6. 示例代码汇总

下面是一个完整的示例代码，展示了顺序表的基本操作，包括初始化、插入、删除、查找和遍历。

#include <stdio.h>
#include <stdlib.h>#define INITIAL_CAPACITY 10// 顺序表结构体定义
typedef struct {int *data;int length;int capacity;
} SequentialList;// 初始化顺序表
SequentialList* initList(int capacity) {SequentialList *list = (SequentialList*)malloc(sizeof(SequentialList));if (list == NULL) {printf("内存分配失败\n");exit(1);}list->data = (int*)malloc(sizeof(int) * capacity);if (list->data == NULL) {printf("内存分配失败\n");free(list);exit(1);}list->length = 0;list->capacity = capacity;return list;
}// 插入元素
int insertElement(SequentialList *list, int index, int value) {if (index < 0 || index > list->length) {printf("插入位置无效\n");return 0;}if (list->length == list->capacity) {int newCapacity = list->capacity * 2;int *newData = (int*)realloc(list->data, sizeof(int) * newCapacity);if (newData == NULL) {printf("内存扩展失败\n");return 0;}list->data = newData;list->capacity = newCapacity;}for (int i = list->length; i > index; i--) {list->data[i] = list->data[i - 1];}list->data[index] = value;list->length++;return 1;
}// 删除元素
int deleteElement(SequentialList *list, int index) {if (index < 0 || index >= list->length) {printf("删除位置无效\n");return 0;}for (int i = index; i < list->length - 1; i++) {list->data[i] = list->data[i + 1];}list->length--;return 1;
}// 查找元素（按值查找）
int findElementByValue(SequentialList *list, int value) {for (int i = 0; i < list->length; i++) {if (list->data[i] == value) {return i;}}return -1;
}// 查找元素（按索引查找）
int getElementByIndex(SequentialList *list, int index, int *value) {if (index < 0 || index >= list->length) {printf("索引无效\n");return 0;}*value = list->data[index];return 1;
}// 遍历顺序表
void traverseList(SequentialList *list) {for (int i = 0; i < list->length; i++) {printf("%d ", list->data[i]);}printf("\n");
}// 主函数
int main() {SequentialList *list = initList(INITIAL_CAPACITY);insertElement(list, 0, 10);insertElement(list, 1, 20);insertElement(list, 2, 30);traverseList(list);deleteElement(list, 1);traverseList(list);int index = findElementByValue(list, 30);if (index != -1) {printf("元素 30 的索引为: %d\n", index);}int value;if (getElementByIndex(list, 1, &value)) {printf("索引 1 处的元素为: %d\n", value);}// 释放内存free(list->data);free(list);return 0;
}

7. 总结

顺序表是一种使用连续内存存储线性数据的结构，适合需要快速随机访问的应用场景。通过本文的总结，介绍了顺序表的定义、实现、基本操作、优缺点及应用场景。顺序表的实现虽然简单，但其对内存的要求较高，适用于元素数量固定、插入和删除操作较少的情况。在实际开发中，顺序表是基础数据结构之一，可以有效帮助理解和构建更复杂的数据结构。

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

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

相关文章

Unity--AssestBundles--热更新

Unity--AssestBundles--热更新

使用Node.js搭建AssestBundle服务器并验证AB包热更新 一、服务器部分 使用NodeJs作为服务器&#xff0c; 使用Express为基础网页模版。 当然&#xff0c; 使用其他的FTP&#xff0c;http服务器也可以&#xff0c; 基础逻辑是存放资源的位置。 1.下载Node.js 下载地址:https…
阅读更多...
AI动漫翻唱项目玩法拆解，起号涨粉咔咔猛，实操干货分享

AI动漫翻唱项目玩法拆解，起号涨粉咔咔猛，实操干货分享

最近&#xff0c;一种把AI技术和动漫翻唱结合起来的视频&#xff0c;在各大平台火了起来&#xff0c;成了社交媒体的新热门。 下面&#xff0c;我们就来聊聊这种视频的制作方法和赚钱技巧&#xff0c;希望能给你的副业加点料。 一、AI动漫翻唱视频的魅力 AI动漫翻唱视频能迅…
阅读更多...
[Luogu 4630] APIO2018 铁人两项（广义圆方树）

[Luogu 4630] APIO2018 铁人两项（广义圆方树）

铁人两项 求满足存在 x → y x \rightarrow y x→y 和 y → z y \rightarrow z y→z 的不相交简单路径的有序点对 ( x , y , z ) (x, y, z) (x,y,z) 的方案数。 即&#xff0c;选择的路径只经过同一个点至多一次。 线性做法。 广义圆方树 可以解决一些“每个点至多经过…
阅读更多...
MySQL进阶之（十一）MySQL事务日志-redo log

MySQL进阶之（十一）MySQL事务日志-redo log

十一、MySQL事务日志-redo log 11.1 Buffer Pool11.1.1 缓存的重要性11.1.2 InnoDB 的 Buffer Pool11.1.3 InnoDB 存储引擎线程 11.2 redo 日志引入11.3 redo 日志的好处和特点11.3.1 好处11.3.2 特点 11.4 redo 日志的组成11.5 redo 日志的整体流程11.6 redo 日志的刷盘策略11…
阅读更多...
nodejs 实现docker 精简可视化控制

nodejs 实现docker 精简可视化控制

地址 https://github.com/xiaobaidadada/filecat 说明 使用react 和nodejs 实现的非常轻量的服务docker管理。
阅读更多...
YOLOv11改进-卷积-引入小波卷积WTConv 解决多尺度小目标问题

YOLOv11改进-卷积-引入小波卷积WTConv 解决多尺度小目标问题

本篇文章将介绍一个新的改进机制——WTConv&#xff08;小波卷积&#xff09;&#xff0c;并阐述如何将其应用于YOLOv11中&#xff0c;显著提升模型性能。YOLOv11模型相比较于前几个模型在检测精度和速度上有显著提升&#xff0c;但其仍然受卷积核感受野大小的限制。因此&#…
阅读更多...
【Wireshark笔记】如何在Wireshark中使用过滤器去除TCP Dup ACK

【Wireshark笔记】如何在Wireshark中使用过滤器去除TCP Dup ACK

【Wireshark笔记】如何在Wireshark中使用过滤器去除TCP Dup ACK 在网络分析和故障排查中&#xff0c;Wireshark是最常用的工具之一。当分析TCP流量时&#xff0c;我们经常会遇到TCP Dup ACK&#xff08;重复ACK&#xff09;包。这些包通常意味着网络中的丢包或重传&#xff0c…
阅读更多...
JRT怎么从IRIS切换到PostGreSql库

JRT怎么从IRIS切换到PostGreSql库

1.执行M导出得到建库脚本文件 2.下载生成的脚本到本地D盘 3.修改驱动为PostGreSql 4.修改连接串 5.到PostGreSql里面创建一个jrtlis的数据库&#xff0c;模式为jrt 6.启动网站点击导入脚本按钮 导入完成了就可以正常使用PostGreSql库了
阅读更多...
QToolButton工具按钮控件

QToolButton工具按钮控件

QToolButton是Qt框架中的一个特殊且功能丰富的控件&#xff0c;它主要用于工具栏或类似场景中&#xff0c;为用户提供快速访问命令或选项的按钮。通常是文字或图片或者图片文字&#xff01; 构造函数 explicit QToolButton(QWidget *parent nullptr); 初始化添加图片 QToolB…
阅读更多...
Redis中String类型常见的应用场景

Redis中String类型常见的应用场景

目录 一. 缓存功能什么是缓存?Redis的工作原理热点数据的过期策略是什么? 二. 计数功能三. 会话(session)共享Session会话是用来解决什么问题的使用Redis集中管理Session 一. 缓存功能 什么是缓存? 缓存是一种用于存储数据的计算机硬件或软件组件. 缓存核心功能是加快数据…
阅读更多...
VSCODE 导入cubeide工程

VSCODE 导入cubeide工程

1.下载vscode及插件STM32 VS Code Ectersion 版本号1.0.0&#xff0c;之后这个有导入功能。 2.等待自动安装对应插件&#xff0c;提示缺少什么就补什么 3.在左侧出现stm32图标。点击Import a local project导入本地项目。 4.报错 [{"resource": "/f:V11/cmak…
阅读更多...
批量合并同名Labelme标注文件内容

批量合并同名Labelme标注文件内容

假如一批数据&#xff0c;分两批分别标注了分割和关键点的json数据&#xff0c;或是分别标注了不同的类别&#xff0c;使用时如果要合并使用&#xff0c;就需要对两个同名的json文件进行合并。 json1: json2: 合并后json&#xff1a; 脚本内容如下&#xff1a; import os imp…
阅读更多...
HubSpot的AI技术：企业营销和销售的好帮手

HubSpot的AI技术：企业营销和销售的好帮手

现在做生意&#xff0c;竞争真挺大的。大家都想找到更好的方法来做营销和销售。HubSpot的AI技术&#xff0c;就像是给我们企业配了个智能小助手&#xff0c;让营销和销售变得更加轻松、高效。 推荐你喜欢的东西&#xff0c;购物更开心 企业老板肯定知道&#xff0c;让客户开心…
阅读更多...
html 登入界面，用户注册界面相关的标签及案例

html 登入界面，用户注册界面相关的标签及案例

案例效果图 以上界面的完整代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</titl…
阅读更多...
C++ 游戏开发：从基础到进阶

C++ 游戏开发：从基础到进阶

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…
阅读更多...
Mistral AI推超强边缘AI模型Ministral 8B，支持128000个token

Mistral AI推超强边缘AI模型Ministral 8B，支持128000个token

最近&#xff0c;法国人工智能初创公司 Mistral AI 宣布了他们的新一代语言模型 ——Ministral3B 和 Ministral8B。 这两款新模型是 “Ministraux” 系列的一部分&#xff0c;专为边缘设备和边缘计算场景而设计&#xff0c;支持高达128&#xff0c;000个 token 的上下文长度。…
阅读更多...
Leetcode 字符串解码

Leetcode 字符串解码

该代码的算法思想可以分为以下几个步骤&#xff1a; 1. 使用栈来处理嵌套结构&#xff1a; 我们需要处理像 k[encoded_string] 这种格式&#xff0c;其中的 encoded_string 可能是嵌套的&#xff0c;即像 3[a2[c]] 这样的输入。因此&#xff0c;我们可以借助 栈&#xff08;S…
阅读更多...
springboot 项目集成spring security（极简版）

springboot 项目集成spring security（极简版）

背景 当服务需要暴露于公网的时候&#xff0c;经常需要有登录功能。通过sping security 进行一个简单的登录功能。 导入依赖 <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web<…
阅读更多...
Android Framework AMS（06）startActivity分析-3(补充：onPause和onStop相关流程解读)

Android Framework AMS（06）startActivity分析-3(补充：onPause和onStop相关流程解读)

该系列文章总纲链接&#xff1a;专题总纲目录 Android Framework 总纲 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;本章节主要解读AMS通过startActivity启动Activity的整个流程的补充&#xff0c;更新了startActivity流程分析部分。 一般来说&#xff0c;有Activ…
阅读更多...
第 2 章 ROS通信机制

第 2 章 ROS通信机制

机器人是一种高度复杂的系统性实现&#xff0c;在机器人上可能集成各种传感器(雷达、摄像头、GPS...)以及运动控制实现&#xff0c;为了解耦合&#xff0c;在ROS中每一个功能点都是一个单独的进程&#xff0c;每一个进程都是独立运行的。更确切的讲&#xff0c;ROS是进程&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023