常见的数据结构---数组、链表、栈的深入剖析
目录
一、数组(Array)
二、链表(Linked List)
三、栈(Stack)
四、总结
数据结构是算法的基石,是程序设计的核心基础。不同的数据结构适用于不同的场景和需求,选择合适的数据结构能显著提升程序的效率和可读性。在众多的数据结构中,数组、链表和栈是最基本、最常用的三种。它们各具特色,不仅应用广泛,也是更复杂数据结构的基础。
一、数组(Array)
1. 什么是数组
数组是一种用于存储一组具有相同数据类型元素的数据结构。这些元素在内存中按照顺序连续存储,可以通过索引访问每个元素。
定义:
int arr[5]; // 定义一个包含5个整数的数组
特点:
连续存储:所有元素占用的内存是连续的。
固定大小:数组声明后,其大小不能改变。
快速访问:可以通过索引快速访问任意元素,时间复杂度为 O(1)O(1)O(1)。
类型一致性:数组中的元素必须是相同的数据类型。
2. 数组的内存布局
数组在内存中是连续分配的。假设一个数组存储在地址 0x1000
开始,并且元素大小为 4 字节,则:
第一个元素的地址为 0x1000
第二个元素的地址为 0x1004
第 n 个元素的地址计算公式: 元素地址=基地址+(索引×元素大小)
示例:
int arr[3] = {1, 2, 3};
// 内存布局:
// 0x1000: 1
// 0x1004: 2
// 0x1008: 3
3. 数组的基本操作
3.1 声明与初始化
静态声明:
int arr[5]; // 声明大小为5的整型数组
int arr[5] = {1, 2, 3}; // 部分初始化,未赋值的元素默认为0
int arr[] = {4, 5, 6}; // 根据初始化列表自动推断大小
动态分配:
int *arr = (int *)malloc(sizeof(int) * 5); // 动态分配大小为5的整型数组
3.2 访问与修改
数组元素通过索引访问,索引从0开始:
int arr[3] = {10, 20, 30};
arr[1] = 40; // 修改第二个元素
printf("%d", arr[1]); // 输出40
3.3 遍历数组
使用循环遍历:
for (int i = 0; i < 5; i++) {printf("%d ", arr[i]);
}
4. 数组的种类
4.1 一维数组
最简单的数组类型,用来表示线性数据结构。
int arr[5] = {1, 2, 3, 4, 5};
4.2 多维数组
用于表示多维数据,如矩阵。
int matrix[3][3] = {{1, 2, 3},{4, 5, 6},{7, 8, 9}
};
printf("%d", matrix[1][2]); // 输出6
4.3 动态数组
通过指针动态分配内存的数组。
int *arr = (int *)malloc(sizeof(int) * 5);
// 使用完成后记得释放内存
free(arr);
5. 数组的优缺点
优点:
- 快速访问:通过索引可以直接访问任意元素。
- 存储效率高:由于元素连续存储,硬件可以高效缓存和访问。
- 简单易用:语法简单,操作直观。
缺点:
- 大小固定:声明后无法动态扩展或收缩。
- 插入与删除效率低:需要移动大量元素。
- 内存连续性要求高:对于大数组,可能会因内存碎片而分配失败。
6. 数组的应用场景与注意事项
- 数据存储与排序:适合存储大小固定的数据,并对其进行排序操作。
- 快速索引场景:如哈希表中的直接寻址。
- 矩阵操作:如图像处理中的像素存储。
- 实现其他数据结构:如栈、队列和字符串。
注意事项
- 数组越界:访问索引超出范围会导致未定义行为。
- 内存管理:动态数组需要手动释放分配的内存。
- 性能优化:频繁的插入或删除操作不适合使用数组。
7. 数组与其他数据结构的对比
8.小结
数组是一种高效的、简单的数据结构,适用于存储固定大小的数据并进行快速访问。然而,其固定大小和插入删除效率低的限制,在一些动态需求下需要其他数据结构(如链表、动态数组)替代。深入理解数组的特性和限制,可以帮助我们更好地在实际开发中合理使用这一基本工具。
二、链表(Linked List)
1. 什么是链表
链表是一种动态数据结构,由多个节点(Node)按线性顺序链接而成。每个节点包含两个部分:
- 数据域(Data):存储节点的数据。
- 指针域(Next):存储指向下一个节点的地址。
链表通过指针连接形成一个线性结构,常用于需要频繁插入或删除操作的场景。
节点结构:
struct Node {int data; // 数据域struct Node *next; // 指针域
};
2. 链表的分类
2.1 单向链表(Singly Linked List)
每个节点只有一个指针,指向下一个节点。
最后一个节点的指针为 NULL
,表示链表结束。
示例:
Head -> [Data | Next] -> [Data | Next] -> NULL
2.2 双向链表(Doubly Linked List)
每个节点包含两个指针:一个指向前驱节点,一个指向后继节点。
可以从任意节点向前或向后遍历。
示例:
NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL
2.3 循环链表(Circular Linked List)
链表的最后一个节点指向头节点,使链表形成一个环。可为单向或双向。
示例:
[Data | Next] -> [Data | Next] -> [Data | Next] -> ...↑----------------------------------------↑
3. 链表的基本操作
3.1 创建链表
通过动态分配内存创建节点,并将节点链接起来。
struct Node* createNode(int value) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = value;newNode->next = NULL;return newNode;
}
3.2 插入节点
- 头插法:在链表头部插入节点。
void insertAtHead(struct Node** head, int value) {struct Node* newNode = createNode(value);newNode->next = *head;*head = newNode; }
- 尾插法:在链表尾部插入节点。
void insertAtTail(struct Node** head, int value) {struct Node* newNode = createNode(value);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode; }
3.3 删除节点
- 按值删除:
void deleteByValue(struct Node** head, int value) {struct Node* temp = *head;struct Node* prev = NULL;// 若删除头节点if (temp != NULL && temp->data == value) {*head = temp->next;free(temp);return;}// 查找要删除的节点while (temp != NULL && temp->data != value) {prev = temp;temp = temp->next;}if (temp == NULL) return; // 值不存在// 重新链接并释放内存prev->next = temp->next;free(temp); }
3.4 遍历链表
void traverse(struct Node* head) {while (head != NULL) {printf("%d -> ", head->data);head = head->next;}printf("NULL\n");
}
3.5 反转链表
struct Node* reverseList(struct Node* head) {struct Node* prev = NULL;struct Node* current = head;struct Node* next = NULL;while (current != NULL) {next = current->next;current->next = prev;prev = current;current = next;}return prev;
}
4. 链表的优缺点
优点:
- 动态大小:不需要预先分配固定大小,可以动态增减节点。
- 高效插入与删除:不需要移动其他元素,时间复杂度为 O(1)O(1)。
- 节省内存:适合存储大小不确定的数据。
缺点:
- 随机访问效率低:无法通过索引直接访问元素,需从头遍历,时间复杂度为 O(n)O(n)。
- 额外内存开销:每个节点都需要存储指针。
- 实现复杂性高:操作链表需要处理指针,容易引发错误(如野指针、内存泄漏等)。
5. 链表的使用场景
- 动态内存需求:如实现队列、栈、哈希表等需要动态扩展的结构。
- 频繁插入与删除:如处理任务队列、缓冲区。
- 内存碎片化环境:连续存储难以满足时,链表可以更好地利用内存。
6. 链表与数组的对比
7. 注意事项
- 内存管理:动态分配的内存需要手动释放,防止内存泄漏。
- 指针处理:链表操作需要谨慎处理指针,避免野指针或空指针。
- 遍历复杂度:链表不适合需要频繁访问特定位置的场景。
8.小结
链表作为一种灵活且动态的数据结构,在处理动态数据、内存碎片化环境中非常实用。通过理解其基本操作与优缺点,开发者可以在合适的场景中高效地使用链表。同时,链表的概念是进一步学习更复杂数据结构(如树和图)的基础,非常重要。
三、栈(Stack)
1. 什么是栈
栈是一种抽象数据类型,遵循后进先出(LIFO, Last In First Out)**的线性数据结构。栈中的数据只能通过一端进行插入和删除,这一端被称为栈顶(Top)。
栈顶(Top):表示栈中最新加入的元素。
栈底(Bottom):表示栈中最早加入的元素。
关键操作:
入栈(Push):将数据插入栈顶。
出栈(Pop):从栈顶删除数据。
查看栈顶元素(Peek/Top):访问栈顶数据但不删除。
2. 栈的实现
2.1 使用数组实现栈
栈可以通过数组来实现,栈顶通过数组的索引表示。
示例代码:
#include <stdio.h>
#include <stdlib.h>
#define MAX 100typedef struct Stack {int arr[MAX];int top;
} Stack;// 初始化栈
void initStack(Stack* stack) {stack->top = -1;
}// 入栈
void push(Stack* stack, int value) {if (stack->top == MAX - 1) {printf("Stack Overflow\n");return;}stack->arr[++stack->top] = value;
}// 出栈
int pop(Stack* stack) {if (stack->top == -1) {printf("Stack Underflow\n");return -1;}return stack->arr[stack->top--];
}// 查看栈顶
int peek(Stack* stack) {if (stack->top == -1) {printf("Stack is empty\n");return -1;}return stack->arr[stack->top];
}
2.2 使用链表实现栈
链表实现栈可以动态调整大小,不受固定容量限制。
示例代码:
#include <stdio.h>
#include <stdlib.h>typedef struct Node {int data;struct Node* next;
} Node;// 入栈
void push(Node** top, int value) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = *top;*top = newNode;
}// 出栈
int pop(Node** top) {if (*top == NULL) {printf("Stack Underflow\n");return -1;}Node* temp = *top;int popped = temp->data;*top = temp->next;free(temp);return popped;
}// 查看栈顶
int peek(Node* top) {if (top == NULL) {printf("Stack is empty\n");return -1;}return top->data;
}
3. 栈的应用场景
3.1 函数调用栈
编程语言运行时会使用栈存储函数的局部变量、返回地址等信息。
函数的调用和返回严格遵循后进先出原则。
3.2 表达式求值
栈用于处理中缀表达式到后缀表达式的转换,以及后缀表达式的求值。
例如:算术表达式计算。
3.3 括号匹配
检查字符串中的括号是否成对匹配,常用于编译器和代码编辑器的语法检查。
3.4 深度优先搜索(DFS)
栈在实现深度优先搜索算法时用于存储路径信息。
3.5 撤销操作
栈记录用户操作的历史,用于实现撤销(Undo)功能。
4. 栈的优缺点
优点:
- 操作简单:只需要维护栈顶,插入和删除操作时间复杂度均为 O(1)O(1)。
- 内存管理:内存分配集中在栈顶,易于管理。
- 适用场景广泛:特别适合递归和后进先出的场景。
缺点:
- 容量有限:基于数组的栈需要预先分配固定大小,可能造成溢出。
- 非灵活访问:只能访问栈顶元素,无法随机访问栈中其他元素。
5. 栈的实现方式对比
- 数组实现:
- 使用一个数组来存储栈中的元素,并使用一个变量来跟踪栈顶的位置。
- 优点是访问速度快,因为直接通过索引访问;缺点是在预先定义的大小之外添加元素可能会导致问题。
- 链表实现:
- 使用链表来存储栈中的元素,每个节点包含元素值和指向下一个节点的指针。
- 优点是可以动态地增加或减少栈的大小;缺点是访问速度相对较慢,因为需要遍历链表。
6. 栈与队列的对比
7. 栈的注意事项
- 溢出问题:基于数组的栈在容量满时会发生溢出,需要提前处理。
- 递归深度限制:递归调用过深可能导致函数调用栈溢出。
- 内存管理:链表实现的栈需要手动释放节点内存,防止内存泄漏。
- 最小栈:在栈中以常数时间获取当前栈的最小值。
- 双栈模拟队列:使用两个栈实现队列操作。
- 多栈共享数组:一个数组同时存储多个栈的数据。
8.小结
栈是一种重要的数据结构,其后进先出的特性使得它在递归、表达式求值、括号匹配等场景中应用广泛。通过理解栈的基本操作和实现方式,可以帮助开发者灵活应用栈,并掌握其在算法和系统设计中的重要作用。
四、总结
数组、链表和栈是编程中最基础的数据结构,它们各具特色,适用于不同的场景:
数组提供高效的随机访问,但大小固定且不适合频繁增删。
链表适合动态存储和频繁插入删除,但随机访问效率较低。
栈专注于后进先出的顺序操作,应用场景广泛。
数组、链表和栈作为程序设计中最基础的数据结构,各自有着独特的优势与应用场景。数组因其固定的内存分配和高效的随机访问能力,适合用于数据规模确定的场景;链表因其灵活的内存管理,适用于频繁插入和删除的需求;而栈则以其后进先出的特性,在递归、表达式求值等领域扮演着不可或缺的角色。熟练掌握这三种数据结构,是深入理解算法和设计更高效程序的必经之路。
相关文章:

常见的数据结构---数组、链表、栈的深入剖析
目录 一、数组(Array) 二、链表(Linked List) 三、栈(Stack) 四、总结 数据结构是算法的基石,是程序设计的核心基础。不同的数据结构适用于不同的场景和需求,选择合适的数据结构能…...
前端开发:构建高质量用户体验的全方位指南(含实际案例与示例)
前端开发:构建高质量用户体验的全方位指南(含实际案例与示例) 在当今数字化时代,前端技术不仅是网页和应用的门面,更是连接用户与数字世界的桥梁。一个高质量的前端开发项目不仅能够提升用户体验(UX&#…...

Istio_05_Istio架构
Istio_05_Istio架构 ArchitectureControl PlanePilotCitadelGalley Data PlaneSidecarIstio-proxyPilot-agentMetadta Exchange Ambient Architecture 如: Istio的架构(控制面、数据面) Gateway: Istio数据面的出/入口网关 Gateway分为: Ingress-gateway、Egress-gateway外部访…...

MongoDB集群分片安装部署手册
文章目录 一、集群规划1.1 集群安装规划1.2 端口规划1.3 目录创建 二、mongodb安装(三台均需要操作)2.1 下载、解压2.2 配置环境变量 三、mongodb组件配置3.1 配置config server的副本集3.1.1 config配置文件3.1.2 config server启动3.1.3 初始化config …...
摄像头测距原理
以下是测距摄像头分类的 Markdown 格式输出,方便直接复制使用: 测距摄像头分类 1. 立体视觉(Stereo Vision)摄像头 原理:模仿人眼成像,利用两台摄像头获取不同视角的图像,通过视差计算场景深…...
基于centos7.9使用shell脚本部署k8s1.25平台
k8s 环境初始化安装Harbor安装k8s安装istio和kubevirt 使用脚本部署k8s1.25版本平台,网络插件使用flannel ,容器运行时ctr,部署包括harbor仓库,服务网格、kubevirt服务等 使用的centos7.9资源配置如下: 主机IP资源ma…...
11.29周五F34-Day10打卡
文章目录 1. 问问他能不能来。解析答案:【解析答案分析】【对比分析】【拓展内容】2. 问题是他能不能做。解析答案:【解析答案分析】3. 问题是我们能否联系得上她。(什么关系?动作 or 描述?)解析答案:【解析答案分析】【对比分析】4. 我们在讨论是否要开一个会。解析答案:…...

龙迅#LT8612UX适用于HDMI 转 HDMIVGA应用领域,分辨率高达4K60HZ,内置程序,方便调试!
1. 描述 LT8612UX 是一款 HDMI 转 HDMI&VGA 转换器,可将 HDMI2.0 数据流转换为 HDMI2.0 信号和模拟 RGB 信号。它还输出 8 通道 I2S 和 SPDIF 信号,可实现高质量的 7.1 通道音频。 LT8612UX 使用最新的 ClearEdge 技术,除了原始的 HDMI…...

C#学写了一个程序记录日志的方法(Log类)
1.错误和警告信息单独生产文本进行记录; 2.日志到一定内存阈值可以打包压缩,单独存储起来,修改字段MaxLogFileSizeForCompress的值即可; 3.Log类调用举例:Log.Txt(JB.信息,“日志记录内容”,"通道1"); usi…...
时间相关转换
Timestamp(date,type) { const zeroDate = new Date(date); if(type === startTime){ zeroDate.setHours(0, 0, 0, 0); } if(type === endTime){ zeroDate.setHours(23, 59, 59, 999); } return zeroDate.getTime(); }, //**时间戳转…...
服务器挖矿
文章目录 一、确定挖矿进程并停止二、查找并清除挖矿相关文件三、检查并修复系统漏洞四、加强安全防护 一、确定挖矿进程并停止 查找挖矿进程 在Linux系统中,可以使用命令如top或htop来查看系统资源占用情况。挖矿程序通常会占用大量的CPU或GPU资源。例如ÿ…...
mac maven编译出现问题
背景 进行maven install 命令,报错: [ERROR] COMPILATION ERROR : [INFO] ------------------------------------------------------------- [ERROR] No compiler is provided in this environment. Perhaps you are running on a JRE rather than a J…...

电磁兼容(EMC):磁性材料(永磁、软磁、功能磁)详解
目录 一、磁性材料概述 二、常用磁性材料分类 1. 永磁材料 2. 软磁材料 3. 功能性磁材 三、软磁材料特点 一、磁性材料概述 磁性材料是指由过渡元素铁(Fe)、钴(Co)、镍(Ni)及其合金等组成的能够直接…...
macOS 版本对应的 Xcode 版本,以及 Xcode 历史版本下载
注:当前页面的所有Xcode下载链接均为苹果官方下载链接 ,点击将直接转至苹果官网下载。 Xcode版本Xcode发布时间对应macOS版本macOS SDKsiOS SDKswatchOS SDKstvOS SDKs下载Xcode发布日志Xcode 15.413 May 2024macOS 14.014.5 (23F73)17.5 (21F77)10.5 (…...

从语法、功能、社区和使用场景来比较 Sass 和 LESS
一:可以从语法、功能、社区和使用场景来比较 Sass 和 LESS: 1:语法 原始的 Sass 采用的是缩进而不是大括号,后续的 Sass 版本与 LESS 一样使用与 CSS 类似的语法: address {.fa.fa-mobile-phone {margin: 0 3px 0 2…...

springboot-vue excel上传导出
数据库 device_manage表 字段,id,workshop,device_number,device_name,device_model,warn_time,expired_time device_warn表 字段,id,warn_time,expired_time 后端 实体类格式 device_manage Data TableName("device_manage"…...
CTF-PWN: ret2libc
plt表与got表是什么? PLT PLT (Procedure Linkage Table) 表在 ELF 文件中的代码段(.text)中,它看起来是这样的: .plt:0x00400530 <__libc_start_mainplt>:jmp QWORD PTR [rip 0x200602] # 0x601608 <__libc_start_maingot.plt>push 0x0jmp 0x4005100…...

SickOs: 1.1靶场学习小记
学习环境 kali攻击机:Get Kali | Kali Linux vulnhub靶场:https://download.vulnhub.com/sickos/sick0s1.1.7z 靶场描述: 这次夺旗赛清晰地模拟了在安全环境下如何对网络实施黑客策略从而入侵网络的过程。这个虚拟机与我在进攻性安全认证专…...

【ArcGIS Pro实操第10期】统计某个shp文件中不同区域内的站点数
统计某个shp文件中不同区域内的站点数 方法 1:使用“空间连接 (Spatial Join)”工具方法 2:使用“点计数 (Point Count)”工具方法 3:通过“选择 (Select by Location)”统计方法 4:通过“Python 脚本 (ArcPy)”实现参考 在 ArcGI…...
JavaScript中类数组对象及其与数组的关系
JavaScript中类数组对象及其与数组的关系 1. 什么是类数组对象? 类数组对象是指那些具有 length 属性且可以通过非负整数索引访问元素的对象。虽然这些对象看起来像数组,但它们并不具备真正数组的所有特性,例如没有继承 Array.prototype 上…...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...

QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...