chapter_array_and_linkedlist/array/

[giscus[bot]]

chapter_array_and_linkedlist/array/

动画图解、一键运行的数据结构与算法教程

https://www.hello-algo.com/chapter_array_and_linkedlist/array/

[gltianwen]

缓存局部性:简单的说是和命中率有关系，分时间局部性和空间局部性

[N1connys]

很不错，数组的插入和删除理解的重点是在索引

[yanmingl]

删除索引 index 元素时，可在代码中，循环结束后，将 nums 最后位置元素重置为 0，nums[-1] = 0, 使之与图片中的末尾元素无意义概念一致。

另外，插入元素时，Python 代码中，索引是否正确？ 我的理解： for i in range(len(nums) - 1, index +1, -1).

[krahets]

哈喽，感谢反馈！图中的末尾也未置 0 ，因为被看作是无意义的元素，因此值为多少无所谓～
插入元素应该为 for i in range(len(nums) - 1, index, -1) ，Python 里面的操作区间一般都是左闭右开的

[deyu9999]

删除元素时，如果不把最后一位置为0，数组长度还是不变的啊
应该要加一句：remove nums[len(nums)-1]

[krahets]

@deyu9999 这一节我们讨论的是严格意义上的“静态数组”，它的长度不可变

[nosqlcoco]

已fork，正着手编写数组的Go示例

[suvueCoder]

数组中首个元素对应数组的内存地址偏移量是0，所以数组索引从0开始算起，学到了，感谢！！！

[EddieChan1993]

/* 初始化数组 */
var arr []int
nums := []int{1, 3, 2, 5, 4}
案例中的数组定义有问题吧，这个明显是切片的定义方式
nums:=[5]int{1, 3, 2, 5, 4}
这才是数组的定义

[krahets]

谢谢反馈，您说的是对的，但本文用 slice 代替 array 的原因如下：

Go 中的数组被设计为在编译时确定长度，因此只能用常量来指定长度。由于这种设计，我们无法使用 Go 的数组来实现文中的数组扩容 extend() 方法。因此，我们选择将 slice 看作数组。

而以 Java 举例，new 出来的数组是存储在 heap 上的，因此可以用变量来指定长度，也就可以实现文中的 extend() 方法了。其他语言也是类似的。

[yemiaobing]

数组遍历 C++ 代码示例，只是 count++，没有遍历数组，是不是本来要写成 count += nums[i]？

[krahets]

哈喽，文中 count 是在统计循环次数，count += nums[i] 当然也可以，示例只是讲解两种循环方式～

[xBLACKICEx]

代码示例 应该加一下语言的语法糖写法？ 比如 rust 很多情况是不用 for的 根据情况编译后的效率也比for循环高效
https://kaisery.github.io/trpl-zh-cn/ch13-04-performance.html

虽然有些矛盾。 但是我觉得可以列出两种实现方式， 一个是for 理解原理另一个是如何更简便的写法。

[krahets]

哈喽，我觉得也要考虑几个点：是否常用、易用性、差距多大。若既不常用、差距也不大，那么我觉得也可以不加。因为本书主要讲算法，语言相关的知识不是最重要的考虑方面。

[xlcodes]

个人观点：学习算法的目的之一就是为了更好的理解语言的语法糖写法，很多语法的所谓的语法糖，本质就是数据结构和算法的实现。感觉在本书中罗列语法糖有点本末倒置了。

[yqlydcjm]

这个网站怎么没有记录功能，是因为没有后端用户服务器吗，，

[wangfumin]

作者您好，为什么在这里会强调“相同类型的元素”，而在下一章链表中却没有强调同类型呢？

[krahets]

那是不是python列表的实现是用链表实现的呢？

Hi! Python 中的 List 是动态数组，底层也是基于数组实现的

[zhangweiii]

那是不是python列表的实现是用链表实现的呢？

盲猜是数组，但数组元素可能是指针，指针指向真实数据，指针大小是固定的，所以可以寻址。猜的，不清楚对不对。

[GyBernstein]

使用了python

arr = [0]
print(hex(id(arr[0])))
arr.append(1)
print(hex(id(arr[0])))

这样显示的一样，似乎地址没变，没扩容

[08822407d]

举个例子，在linux内核中链表都是侵入式的，链表节点本身不包含承载的数据内容，而是反过来由数据内容内嵌一个链表节点。所以侵入式链表可以串起不同的数据类型，虽然这么用没啥实际意义，内核还有另外一种玩法是用void *指向一个数据，然后由相应业务代码把他强制转换成正确的类型指针。

[syd168]

数组元素的相邻依靠内存单元的相邻，而链表的“相邻”关系是靠指针的指向。数组中的元素类型必须相同，这样方便索引，链表靠指针访问元素，无需元素类型相同。

数组是在元素较少，所需连续空间充足的情况下使用，链表是在数据类型复杂，所需空间比较大，而且频繁插入删除的情况下使用更方便。

[BrookZhao]

之前都是在用，没有看到这么底层
index是在内存中偏移量，以及插入、删除（数据丢失）

[zzkgggg]

“数组有多种初始化写法。根据实际需要，选代码最短的那一种就好。” k神，个人感觉这句话有点奇怪，
下面代码中
/* 初始化数组 /
int arr = new int[5];
int* nums = new int[5] { 1, 3, 2, 5, 4 };
是在堆上创建，而大部分情况应该最好都是在栈上创建吧。

[krahets]

谢谢建议，这句话确实对 C/C++ 欠考虑了，已更新！

[lqs-blog]

请问计算内存地址那里为什么元素长度为4呢？我看数组长度为5，为什么不是5呢

[krahets]

Hi ！“元素长度”指的是“单个元素占用的内存空间”，比如 int 是 4 bytes 。“数组长度”指“元素数量”，图中数组长度是 5 。

[lqs-blog]

明白啦，谢谢k神

[HNUIsak]

您好还是不太理解c++数组删除那块，我知道有效长度-1之后最末尾的元素可以忽略掉（无意义），可是这在源代码中没有体现，请问这该如何实现呀？第二个问题是在插入的时候不应该先判断是否满数组再扩容吗？感谢解答

[krahets]

Hi! 一般我们会维护一个 size 变量，来记录数组内的有效元素数量，这个在下一节的列表实现中有体现。
第二个问题，本节没有涉及数组扩容操作，而是留到“列表”章节讲解。

[HNUIsak]

十分感谢您的耐心解答！！！

[ThxGodNovember]

看评论看到了疑惑被解答 😄

[Ding-Jiaxiong]

Hello! K大，想问下您的图都是怎么画的啊，感觉也太整齐美观了，想学习一下

[krahets]

谢谢鼓励～用 Keynote PPT 或者其他软件都能画

[Dynamite2003]

写的真好，看书看不下去，看作者写的感觉很清晰

[BITuser1]

在【随机访问数组元素】中，C++的代码：

/* 随机访问元素 */
int randomAccess(int *nums, int size) {
    // 在区间 [0, size) 中随机抽取一个数字
    int randomIndex = rand() % size;
    // 获取并返回随机元素
    int randomNum = nums[randomIndex];
    return randomNum;
}

randomAccess 函数确实返回一个随机索引处的数字，但是程序没有初始化随机数生成器。每次运行程序时，都会得到相同的随机数，因为随机数生成器使用相同的种子来生成随机数。
用srand初始化一下比较好，不然一直都是同一个数字。

[QuantumCipherMaster]

还真是，我跑了几次的结果都是一样的😭

[syd168]

/* 随机访问元素 */
int randomAccess(int *nums, int size) {

srand((unsigned int)time(NULL));

// 在区间 [0, size) 中随机抽取一个数字
int randomIndex = rand() % size;
// 获取并返回随机元素
int randomNum = nums[randomIndex];
return randomNum;

}

[RocGit]

"值得注意的是，由于数组的长度是固定的，因此插入一个元素必定会导致数组尾部元素“丢失”。我们将这个问题的解决方案留在“列表”章节中讨论。"

关于“丢失”，目前为止“列表”章节中好像还没有提到呢

[WalkerInAI]

Python
“数组存储在连续的内存空间内，且元素类型相同”
列表是数组，可是我在列表里存放整形数，字符串，那这个列表还算数组吗？如果不算数租，那它和数组有什么不一样的地方呢？

[krahets]

Python 中列表的底层实现是数组，只是实现方式比较特殊。能够存储不同基本类型，是由于 Python 列表中的每个元素实际上是一个指向对象的指针；这意味着列表存储的是指针的集合，这些指针指向存储在其他地方的实际数据对象。

[estarpro1022]

缓存局部性，死去的计组知识开始复活。

[1435646097]

无处不在的空间局部性合时间局部性原理

[deyu9999]

def traverse(nums: list[int]):
    """遍历数组"""
    count = 0
    # 通过索引遍历数组
    for i in range(len(nums)):
        count += nums[i]
    # 直接遍历数组元素
    for num in nums:
        count += num
    # 同时遍历数据索引和元素
    for i, num in enumerate(nums):
        count += nums[i]
        count += num

为什么不用两个变量区分次数求和和元素求和，演示的count应该分段清零

[krahets]

这里代码没有实际含义，只是展示不同的遍历方式～

[moonpoet]

写的很清晰哦，点赞

[chinatsu-yan]

关于删除元素有些不理解，末尾元素无意义但是仍然是客观存在的，如果要做遍历之类的操作依然逃不开这个无意义的元素，还是说在届时会记录一个有效长度来规避这个问题？

[krahets]

是的，我们会用一个变量来记录数组的有效长度。列表章节包含具体实现

[1435646097]

就算不删除元素，初始化一个int类型数组的时候，默认都会填充0，但是会有一个变量来记录数组的有效长度，被填充的0是会被忽略的

[ruomu007]

不懂就问： int *res = new int[size + enlarge]。 res 是一个地址指针 ，为什么可以res[i] 这样像数组一样来使用res。 res只是获得了新建数组的首地址，就有了数组的功能了吗？

[syd168]

res 是一个地址指针，则res[i] 和*(res+i) 都是访问偏移res为i的元素,效果是一样的。也就是可以用res[i]访问，但i不能超出数组下标范围，否则可能产生异常。C/C++中，数组下标是靠程序员维护的，语言本身不维护。如下面的代码一般可以正常执行：
int a=100;
int p=&a;
printf ("%d\n",p[1]);
printf ("%d\n",*(p+1));

[ruomu007]

呼唤大神： int *extend (int *nums, int size, int enlarge) 里面参数 int * nums 可以改成 int nums[]吗？ 这有什么不同？

[ruomu007]

但是 大佬说 int * nums 和 int nums[] 是有区别的哦， 不知道啥区别

[hanwinbi]

C++编程 里的第八章，8.1.1节的内容或许更加准确。你可以看看

[xiaobawang001]

本质是不同的，int*是传进来的数组的地址，他指向传进来的数组，在进行完扩容后，这个指针被释放，传进来的数组内容被定义为未知的值，指针还是指向该地址，但是该地址的内容无法访问，int[]则是创建了一个副本复制传进来的数组内容

[ruomu007]

谢谢各位

[syd168]

在函数传递中， int arr[]被编译器编译为 int *arr，所以，作为参数传递，int *arr和int arr[]是一样的；
但作为普通变量，int *arr和int arr[]是不一样的，*arr是一个指针，可以被赋值，指向其它整数变量的地址；arr是一个数组名，指向数组的第一个元素，arr所指向的地址是只读的，不能被修改。

[yxsongbo]

random_index = random.randint(0, len(nums) - 1) 这行代码生成成的随机数终止值为什么要减去1

[wuyange]

不减一会超出列表最大长度，索引从0开始的

[Duuckjing]

这应该是列表...

import array
arr = array.array('i', [1, 3, 2, 5, 4]) # 'i'表示数组中存储的是有符号整数
是数组

[krahets]

array 的确更符合数组的定义，但它太常用。在这里我们把列表（底层实现为动态数组）看作数组，以避免不必要的复杂性

[nyang9]

array.py是不是有一点问题，插入之后会丢失原数组中最后一个元素

[nyang9]

我的锅，没看到数组长度不可变

[kangouba]

想问一下各位前端的小伙伴们，用js学习这个算法合适嘛，我怎么感觉看起来有点怪怪的呢

[BruisesL]

大佬，扩容数组那里的Java代码不知道是不是有问题

int[] extend(int[] nums, int enlarge) {
}

以上这一段，方法名定义为extend，但是这个是Java关键字，不能用作命名，会报错。

[krahets]

Java 的这个关键字是 extends 吧？

[SUPERMEduck]

这里用的是定义方法，extend为方法名。这里的JAVA代码没有问题。

[BruisesL]

我的，那天看错了，没看清没s（