详解数据结构之-「数组篇」

详解数据结构之-「数组篇」

太久没有写算法了，最近在回顾数据结构和算法，准备把这块重新捡起来，给自己立一个flag，每周花时间练习算法，写一篇总结。

数组

数组数据结构（英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。

简单归纳下，数组是一种线性数据结构，用一段连续的存储空间，用来存储一类相同数据类型的元素。

线性表

线性表（Linear List）是一种基本的数据结构，它是由n（n≥0）个数据元素构成的有限序列。数据元素之间存在着一种顺序关系，可以理解成这些数据之间连成了一条线。

常见的线性表数据结构有以下这些：数组、链表（单链表、双向链表、循环链表）、栈、队列。

非线性表

和线性表相反，非线性表是一种没有顺序的，准确的说非线性表的结构不局限于一对一的关系，而是可以是一对多、多对一或多对多的关系。即一个数据元素可能有多个直接前驱元素或直接后继元素。

常见的非线性表数据结构有：二叉树、堆、图、hash表等。

连续的内存空间

数组的内存空间是连续的，内存分配后是一段连续的地址。写几行代码验证下。

func TestArray(t *testing.T) {
	var x int
	size := unsafe.Sizeof(x)
	fmt.Printf("int 占用 %d 个字节\n", size)

	tp := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
	for i := 0; i < len(tp); i++ {
		fmt.Println(fmt.Sprintf("16进制地址=%p,10进制地址=%d，值=%+v", &tp[i], uintptr(unsafe.Pointer(&tp[i])), tp[i])) // 以10和16进制方式打印
	}
}

int 占 8 个字节

上段代码结果输出如下：

=== RUN   TestArray
int 占用 8 个字节
16进制地址=0xc00011e240,10进制地址=824634892864，值=1
16进制地址=0xc00011e248,10进制地址=824634892872，值=2
16进制地址=0xc00011e250,10进制地址=824634892880，值=3
16进制地址=0xc00011e258,10进制地址=824634892888，值=4
16进制地址=0xc00011e260,10进制地址=824634892896，值=5
16进制地址=0xc00011e268,10进制地址=824634892904，值=6
16进制地址=0xc00011e270,10进制地址=824634892912，值=7
16进制地址=0xc00011e278,10进制地址=824634892920，值=8
16进制地址=0xc00011e280,10进制地址=824634892928，值=9
16进制地址=0xc00011e288,10进制地址=824634892936，值=10
16进制地址=0xc00011e290,10进制地址=824634892944，值=11
16进制地址=0xc00011e298,10进制地址=824634892952，值=12
--- PASS: TestArray (0.00s)
PASS

10进制地址可以看出，起始地址是：824634892864，后续的地址依次加 8，就是下一个元素的地址。

数组的最强杀招，“下标随机访问”。直接通过元素的下标来获取数组中的元素，不需遍历整个数组。所以，数组在查找、访问和修改特定元素时具有高效性，时间复杂度为 O(1)。

但是，数组的某些操作也会非常慢，比如：插入、删除、移动，为了保证连续性，会移动大量元素。如果，你的业务不需要保证连续性，那性能也可以非常高的。

数组寻址

上段代码打印了数组的连续内存地址，你看出来数组是怎么寻址的？

举一个简单例子，创建一个长度为5的数组，假设起始地址（基地址）为0xc0000b8000，连续的内存空间0xc0000b8000-0xc0000b8020，这个是16进制看起来不是很方便，可以用 10 进制好算一些。

计算机会给每个内存单元分配一个地址，通过地址来访问内存中的数据。当计算机需要通过数组下标访问数组中的某个数据时，需要通过下面的公式计算。（注：你在使用数组过程中基本都是通过下标或者遍历得到了最终值，复杂的寻址过程语言层面已经帮你处理好了。）

address=基地址+i*type_size
  1. type_size 是数组中每个元素的字节大小，也就是数组中存储的数据类型的大小；
  2. i 是数组中要访问的元素的索引，即下标值；
  3. 基地址 是数组的起始内存地址，即数组中第一个元素的地址；

划重点：数组数组结构的特性是支持下标随机访问，根据下标随机访问的时间复杂度为 O(1)。非下标访问的方式如果用二分查找时间复杂度是O(logn)，若通过遍历的方式，最好时间复杂度为O(1)，最坏时间复杂度为O(n)。

聊聊数元素组插入

假设一个数组长度是 x，我们要在 y 的位置插入一个数据 v，需要把 y～x 位置的数据分别往后挪动1位。我们先分析下时间复杂度。

1. 最好情况时间复杂度：如果在数组的末尾(x-1)进行插入操作，即插入位置是数组的尾部，那么时间复杂度为 O(1)。在这种情况下，不需要移动其他元素，只需将新元素直接放在数组的末尾。
2. 最坏情况时间复杂度：在数组头（0位置）插入，需要把所有移动移动一个位置，不考虑扩容假设内存空间够用。时间复杂度为O(n)。
3. 平均时间复杂度：平均情况下的时间复杂度取决于插入位置的分布情况。如果插入位置随机分布在数组中，那么平均情况下的时间复杂度仍然为 O(n)，因为大约一半的情况下会需要移动一半的元素。

当然，我上面讲过，如果你不在乎替换后数组的连续性，可以按下面这种操作。时间复杂度为O(1)。

聊聊数组元素的删除

数组元素删除和插入都是类似的，当插入元素是，元素可能会后移；删除元素时，因为删除下标空出来了，所以元素会往前移。有人会问了，如果不移元素会怎么样？不移动元素就会出现空洞，内存不连续。下面我们分析下时间复杂度。

1. 最好情况时间复杂度：如果删除操作是针对数组末尾（x-1）的元素进行的，那么时间复杂度为 O(1)。因为在这种情况下，只需要将数组的长度减一即可，不需要移动其他元素。
2. 最坏情况时间复杂度：如果删除操作是针对数组开头的元素进行的，或者是数组中间的元素进行的，那么需要将删除位置之后的所有元素向前移动一个位置，以填补删除元素留下的空缺，时间复杂度为 O(n)。
3. 平均时间复杂度：平均情况下的时间复杂度取决于删除位置的分布情况。如果删除位置随机分布在数组中，那么平均情况下的时间复杂度仍然为 O(n)。

数组的删除操作是需要移动元素的，因此在时间复杂度上并不能提高效率。但，有一种技巧可以提高数组删除操作的效率，即使用“标记删除”而非真正的物理删除。

大概思路是下面这样的：当需要删除一个元素时，并不立即移动其它元素来填补删除位置，而是将该位置的元素标记为已删除状态。在进行元素访问时，忽略已标记为删除状态的元素。当数组中已删除元素的数量达到一定阈值时，再执行一次真正的物理删除并进行数组重排，以释放不必要的内存空间。

数组越界问题

数组越界在 go 中是非常严重的，会导致 Panic，所以在使用过程中一定要注意。看下面这段代码。

func main() {
	tp := []int{1, 2, 3, 4, 5}
	v := tp[6]
	print(v)
}

结果输出如下：

panic: runtime error: index out of range [6] with length 5

代码实战

package slice

import (
	"errors"
	"fmt"
	"sync/atomic"
)

var (
	indexOutOfRange = errors.New("index out of range")
	arrayIsFull     = errors.New("array is full")
)

type Slices[T any] struct {
	data     []T           // 容器
	len      atomic.Uint32 // 长度
	capacity uint32        // 容量
}

// NewSlices 初始化数组
func NewSlices[T any](capacity uint32) *Slices[T] {
	return &Slices[T]{data: make([]T, capacity), capacity: capacity}
}

func (a *Slices[T]) Insert(index uint32, v T) error {
	if a.Len() >= a.capacity {
		return arrayIsFull
	}

	if a.isIndexOutOfRange(index) {
		return indexOutOfRange
	}

	// 元素后移
	for i := a.Len(); i > index; i-- {
		a.data[i] = a.data[i-1]
	}

	a.len.Add(1)
	a.data[index] = v
	return nil
}

func (a *Slices[T]) Insert2Head(v T) error {
	return a.Insert(0, v)
}

func (a *Slices[T]) Insert2Tail(v T) error {
	return a.Insert(a.Len(), v)
}

func (a *Slices[T]) Delete(index uint32) (T, error) {
	var v T
	if ok := a.isIndexOutOfRange(index); ok {
		return v, indexOutOfRange
	}

	v = a.data[index]
	l := a.Len() - 1

	// 元素前移
	for i := index; i < l; i++ {
		a.data[i] = a.data[i+1]
	}

	// 设置零值
	var zero T
	a.data[l] = zero

	d := int32(-1)
	a.len.Add(uint32(d))
	return v, nil
}

// Find 下标随机查询
func (a *Slices[T]) Find(index uint32) (T, error) {
	var out T
	if ok := a.isIndexOutOfRange(index); ok {
		return out, indexOutOfRange
	}

	out = a.data[index]
	return out, nil
}

func (a *Slices[T]) Len() uint32 {
	return a.len.Load()
}

func (a *Slices[T]) Print() {
	for _, v := range a.data {
		fmt.Println(v)
	}
}

func (a *Slices[T]) isIndexOutOfRange(index uint32) bool {
	// 长度大于容量说明数组越界了
	return index >= a.capacity
}

测试用例如下：

package slice

import (
	"fmt"
	"testing"
	"unsafe"
)

func FuzzInsert2Tail(f *testing.F) {
	testcases := []uint32{0, 1, 2, 3, 4}
	for _, tc := range testcases {
		f.Add(tc)
	}

	slices := NewSlices[int](11)
	f.Fuzz(func(t *testing.T, index uint32) {
		err := slices.Insert(index, int(index))
		if err != nil {
			panic(err)
		}
	})

	slices.Insert2Tail(20)
	slices.Print()
}

func FuzzInsert2Head(f *testing.F) {
	testcases := []uint32{0, 1, 2, 3, 4}
	for _, tc := range testcases {
		f.Add(tc)
	}

	slices := NewSlices[int](11)
	f.Fuzz(func(t *testing.T, index uint32) {
		err := slices.Insert(index, int(index))
		if err != nil {
			panic(err)
		}
	})

	slices.Insert2Head(20)
	slices.Print()
}

func FuzzFind(f *testing.F) {
	testcases := []uint32{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	for _, tc := range testcases {
		f.Add(tc)
	}

	slices := NewSlices[int](11)
	f.Fuzz(func(t *testing.T, index uint32) {
		err := slices.Insert(index, int(index))
		if err != nil {
			panic(err)
		}
	})

	f.Log(slices.Find(0))
	f.Log(slices.Find(1))
	f.Log(slices.Find(2))
	f.Log(slices.Find(8))
}

func FuzzInsertAndDelete(f *testing.F) {
	testcases := []uint32{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	for _, tc := range testcases {
		f.Add(tc)
	}

	slices := NewSlices[int](11)
	f.Fuzz(func(t *testing.T, index uint32) {
		err := slices.Insert(index, int(index))
		if err != nil {
			panic(err)
		}
	})

	err := slices.Insert(3, int(20))
	if err != nil {
		panic(err)
	}

	r, err := slices.Delete(5)
	if err != nil {
		panic(err)
	}
	f.Log(r)
}

func TestArray(t *testing.T) {
	var x int
	size := unsafe.Sizeof(x)
	fmt.Printf("int 占用 %d 个字节\n", size)

	tp := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
	for i := 0; i < len(tp); i++ {
		fmt.Println(fmt.Sprintf("16进制地址=%p,10进制地址=%d，值=%+v", &tp[i], uintptr(unsafe.Pointer(&tp[i])), tp[i])) // 以10和16进制方式打印
	}
}

总结

  1. 数组一旦初始化就是连续的内存空间，用来存储一类相同数据类型的元素。
  2. 数组数据结构的特性是支持下标随机访问，最好时间复杂度为O(1)，最坏时间复杂度为O(n)。
  3. 数组的寻址公式是：
address=基地址+i*type_size

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

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

相关文章

Mysql学习2

Mysql学习2

目录 一.数据库&#xff1a; 1.创建数据库&#xff1a; 2.查看数据库&#xff1a; 3.备份恢复数据库&#xff1a; 二.表 1.创建表指令&#xff1a; 2.MySQL常用数据类型&#xff1a; 3.删除与修改表&#xff08;重点&#xff09;&#xff1a; 4.数据库CRUD语句&#xf…
阅读更多...
网络 (TCP/IP 四层协议中常见网络协议)

网络 (TCP/IP 四层协议中常见网络协议)

应用层 DNS (Domain Name System) 域名系统. DNS 是一整套从域名映射到 IP的系统 NAT 技术 解决 IP 地址不够用的问题. 可以实现私有 IP 和全局 IP 的相互转换 NAPT 技术 使用 IP Port 唯一确定局域网中的主机 传输层 TCP 协议 (Transmission Control Protocol 传输控制协议…
阅读更多...
C++:范围-based for 循环

C++:范围-based for 循环

范围-based for 循环是 C11 引入的一种循环语法&#xff0c;它简化了遍历容器和数组等序列的操作&#xff0c;使代码更加清晰和简洁。它通常用于遍历容器类&#xff08;如数组、向量、列表等&#xff09;中的元素&#xff0c;或者以范围的形式遍历初始化列表。 范围-based for …
阅读更多...
AI大模型探索之路-实战篇1：基于OpenAI智能翻译助手实战落地

AI大模型探索之路-实战篇1：基于OpenAI智能翻译助手实战落地

文章目录 前言一、需求规格描述二、系统架构设计三、技术实施方案四、核心功能说明五、开源技术选型六、代码实现细节1.图形用户界面&#xff08;GUI&#xff09;的开发2.大型模型调用的模块化封装3.文档解析翻译结果处理 总结 前言 在全球化的浪潮中&#xff0c;语言翻译需求…
阅读更多...
HarmonyOS NEXT 使用Canvas实现模拟时钟案例

HarmonyOS NEXT 使用Canvas实现模拟时钟案例

介绍 本示例介绍利用 Canvas 和定时器实现模拟时钟场景&#xff0c;该案例多用于用户需要显示自定义模拟时钟的场景。 效果图预览 使用说明 无需任何操作&#xff0c;进入本案例页面后&#xff0c;所见即模拟时钟的展示。 使用说明 无需任何操作&#xff0c;进入本案例页…
阅读更多...
20240330-2-XGBoost面试题

20240330-2-XGBoost面试题

XGBoost面试题 1. RF和GBDT的区别 相同点&#xff1a; 都是由多棵树组成&#xff0c;最终的结果都是由多棵树一起决定。 不同点&#xff1a; 集成学习&#xff1a; R F RF RF属于 B a g g i n g Bagging Bagging思想&#xff0c;而 G B D T GBDT GBDT是 B o o s t i n g Bo…
阅读更多...
【数据结构2-线性表】

【数据结构2-线性表】

数据结构2-线性表 1 线性表-数组2 线性表-单链式结构2.1 前插顺序单链表2.2 后插顺序单链表2.3 循环单链表2.4 双向链表 总结 线性表、栈、队列、串和数组都属于线性结构。 线性结构的基本特点是除第一个元素无直接前驱&#xff0c;最后一个元素无直接后继之外&#xff0c;其他…
阅读更多...
Django中间件的源码解析流程（上）——中间件载入的前置

Django中间件的源码解析流程（上）——中间件载入的前置

目录 1. ​前言​ 2. 请求的入口 3. 中间件加载的入口 4. 源码中的闭包实现 5. 最后 1. 前言 哈喽&#xff0c;大家好&#xff0c;我是小K,今天咋们分享的内容是&#xff1a;在学会Django中间件之后&#xff0c; 我们继续深入底层源码。 在执行中间件时请求到来总是从前往后…
阅读更多...
第三方应用类---Phpmyadmin 后台 Getshell 操作

第三方应用类---Phpmyadmin 后台 Getshell 操作

免责声明:本节仅做技术交流学习. 目录 什么是Phpmyadmin? getshell前提条件: 详细步骤: 1-搜集到开放phpmyadmin的web,然后访问进去 2-执行SQL命令查看是否开启了读写权限 3-开启了读写权限-->继续 没有开读写权限--->鸡鸡 4-有读写权限之后,执行SQL语句导出文件…
阅读更多...
【Python】函数进阶(纯干货版)

【Python】函数进阶(纯干货版)

目录 函数的多返回值 多个参数的传递 缺省参数 不定长参数 位置不定长参数传参举例 关键字不定长参数举例 函数作为参数传递 匿名函数 函数的多返回值 在Python中允许一个函数带回多个返回值&#xff0c;写法是一个return 返回值1&#xff0c;返回值2 在接收的时候同样…
阅读更多...
快速入门Spring Data JPA

快速入门Spring Data JPA

Spring Data JPA是Spring Data框架的一小部分&#xff0c;它能够让开发者能够更加简单的对数据库进行增删改查。 由于Spring Data JPA可以自动生成SQL代码所以一般情况下&#xff0c;简单的增删查改就可以交给Spring Data JPA来完成&#xff0c;而复杂的动态SQL等用MyBatis来完…
阅读更多...
软考 系统架构设计师系列知识点之大数据设计理论与实践（14）

软考 系统架构设计师系列知识点之大数据设计理论与实践（14）

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之大数据设计理论与实践&#xff08;13&#xff09; 所属章节&#xff1a; 第19章. 大数据架构设计理论与实践 第4节 Kappa架构 19.4.3 Kappa架构的实现 下面以Apache Kafka为例来讲述整个全新架构的过程。 部署Apach…
阅读更多...
解线性方程组——直接解法：LU分解、PLU分解(类似列主元消去法) | 北太天元

解线性方程组——直接解法：LU分解、PLU分解(类似列主元消去法) | 北太天元

L: lower triangular 下三角 U: upper triangular 上三角 LU 分解&#xff0c;顾名思义&#xff0c;为 把一个 矩阵 分成 一个下三角矩阵 乘上一个上三角矩阵的形式。 Example 为什么可以这样 几个基本的初等行变换&#xff0c;可以自己验算一下&#xff0c;等式的左边与右边…
阅读更多...
Linux管道共享内存

Linux管道共享内存

前言 进程虽然是独立运行的个体&#xff0c;但它们之间有时候需要协作才能完成一项工作&#xff0c;比如有两个进程需要同步数据&#xff0c;进程 A 把数据准备好后&#xff0c;想把数据发往进程 B&#xff0c;进程 B 必须被提前通知有数据即将到来&#xff0c;或者进程 A 想发…
阅读更多...
腾讯EdgeOne产品测评体验—金字塔般的网络安全守护神

腾讯EdgeOne产品测评体验—金字塔般的网络安全守护神

作为一名对网络安全和性能优化充满热情的用户&#xff0c;我决定体验腾讯云下一代 CDN 服务 - EdgeOne。这款引以为傲的全方位服务如数来到&#xff0c;从域名解析、动静态智能加速到四层加速及DDoS/CC/Web/Bot 防护&#xff0c;一应俱全。随着时代风云变幻&#xff0c;日均数千…
阅读更多...
kubernetes1.28版本的二进制安装

kubernetes1.28版本的二进制安装

前言 二进制部署 Kubernetes&#xff08;K8s&#xff09;集群相对于其他部署方式&#xff08;如基于发行版的包管理器、容器化部署工具等&#xff09;具有一些优势&#xff0c;主要包括&#xff1a; 灵活性&#xff1a;二进制部署方式更加灵活&#xff0c;您可以根据自己的需…
阅读更多...
冯喜运：4.21黄金市场失去正常反应？下周黄金原油解析

冯喜运：4.21黄金市场失去正常反应？下周黄金原油解析

【黄金消息面解析 】&#xff1a;周五(4月19日)&#xff0c;伊朗媒体似乎淡化了以色列袭击的影响&#xff0c;表明地缘政治风险降低&#xff0c;导致避险资产需求放缓&#xff0c;金价回吐涨幅。本周现货黄金价格上涨超2%。美国黄金期货收盘上涨0.7%&#xff0c;至2413.8美元。…
阅读更多...
基于SpringBoot的“火车订票管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“火车订票管理系统”的设计与实现（源码+数据库+文档+PPT)

基于SpringBoot的“火车订票管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SpringBoot 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 前台首页功能界面图 登录、用…
阅读更多...
Shapley量化调峰成本？高比例可再生能源电力系统的调峰成本量化与分摊模型程序代码！

Shapley量化调峰成本？高比例可再生能源电力系统的调峰成本量化与分摊模型程序代码！

前言 在能源安全、环境污染和气候变化的大背景下&#xff0c;大力发展可再生能源是应对全球气候变化&#xff0c;实现“碳达峰、碳中和”和可持续发展的重大需求。截至2020年底&#xff0c;中国风电总装机容量为281GW&#xff0c;风力发电466.5TWh&#xff0c;同比增长约15%&a…
阅读更多...
运动想象 (MI) 分类学习系列 (10) :iWSGL-CSP

运动想象 (MI) 分类学习系列 (10) :iWSGL-CSP

运动想象分类学习系列:iWSGL-CSP 0. 引言1. 主要贡献2. 提出的方法3. 结果3.1 在3个数据集上的效果3.2 基线比较 4. 总结欢迎来稿 论文地址&#xff1a;https://www.sciencedirect.com/science/article/abs/pii/S0957417423027884 论文题目&#xff1a;Improvement of motor im…
阅读更多...
最新文章

Copyright @ 2022~2023