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 或者其他软件都能画

[hakatazhou]

Pad看不了可视化
华为MatePad air

[LofiSu]

那个遍历数组错了吧，，，我输出的是累加和

[King-ysy]

代码就是累加的代码啊

[wozhendeshi]

通过遍历数组实现累加和

[crab78]

我想问一下对于一个初一的学生，二维数组是否可以理解为平面直角坐标系中的格点？下标对应坐标？

[shiyi-0x7f]

可以这样理解。不过在程序中，二维数组与坐标格点的直角坐标系方向并不是一一对应的，需要根据适当的情况进行转换。

[QingXian001]

就是前面说的偏移吗

[FrierenGreatDemonLord]

其实二维数组nums2d = [obj, obj, obj]，也相当于一维数组nums1d = [obj, obj, obj]

• 无非是一维数组里面存储对象（obj）对应的是一个个标量，如nums1d = [1, 2, 3]
• 反观二维数组里面存储的对象（obj）对应的是一个个数组，如num1d = [[1,2, 3,], [10, 20, 30], [100, 200, 300]]

obj0, obj1, obj2 = 1, 2, 3
nums1d = [obj0, obj1, obj2]

obj0, obj1, obj2 = [1, 2, 3], [10, 20, 30], [100, 200, 300]
nums2d = [obj0, obj1, obj2]

[ltysvip]

数组删除中间的元素为什么要将之后的元素都向前移动一位，将该值设置为null不就不用移动了吗？

[JustinLinCodeee]

基本数据类型怎么设置null，只有引用类型才可以是null

[lichenggong123]

上文讲到数组是连续的，我认为如果将值换成hull的话

[lichenggong123]

数组就不再连续了，

[FrierenGreatDemonLord]

可以这样理解，把数组理解成手里的一些牌

• 插入：有新牌进来，自然插入位置之后的牌要右移
• 删除：要出一张牌，这张牌之后的牌自然得要左移

[FrierenGreatDemonLord]

删除时直接赋值为null 或None，那不叫删除，叫修改update [Doge]

[liuzilongtest]

初始化数组
arr: list[int] = [0] * 5 # [ 0, 0, 0, 0, 0 ]
nums: list[int] = [1, 3, 2, 5, 4]
这个直接报错了.Subscript for class "list" will generate runtime exception; enclose type annotation in quotesPylance
哪个大佬说下?

[krahets]

书中 Python 代码需要在 Python >= 3.10 版本下运行

[Kaidaotum1]

我用mac自带的python3.9可以正常运行

[ccy-cugb]

数组扩容部分C++实现的方法中返回的res是在函数中定义的指针变量，函数执行结束之后，返回的res会被回收吗，如果被回收那么返回出来的指针是不是不可用

[GoLennLee]

res是new出来的，其在内存的堆区，只要你不手动释放就一直存在，so返回的res不会被自动回收。

[ccy-cugb]

我说的不可用的意思是，函数执行结束之后，定义的 int * res = new int[size+enlarge]这些内存会不会被回收

[ccy-cugb]

okok，感谢

[MaikieMaiky]

res是指向已申请的堆空间的指针,res这个指针是在栈区上而不是从堆区申请,
在学习C的时候,在函数中生成的变量,在返回时会被销毁,因此要避免返回在函数中创建的局部变量
而在C++中则有所不同我之前也遇到过这类代码,我询问过GPT,他给出的回答是C++的编译器进行了优化,使得这类返回可以进行,具体的实现你可以上网查一下

[MaikieMaiky]

不好意思说错了,指针的数值返回在C和C++中都是可以的,res在函数结束后被销毁了,但是你调用这个函数的时候使用指针接收返回值,依旧可以通过指针对在函数内部向堆区申请的空间进行操作

[suhq24]

环形链表的使用场景通常与循环访问、固定大小的数据管理或周期性任务相关。

[lwj6666]

二维数组这些内

[liaoruochenxin]

佬，删除元素那边是不是要把length-1啊，我看的是Java代码，如果不减的话最后一位元素是重复的吧

[FrierenGreatDemonLord]

可以通过指针变量returnSize 在函数内赋值数组长度$-1$，后续访问数组长度参照returnSize 即可

void removeItem(int *nums, int size, int index, int *retrunSize) {
    for (int i = index; i < size - 1; i++)
        nums[i] = nums[i + 1];
    *returnSize = size - 1;
}

[FrierenGreatDemonLord]

其实二维数组nums2d = [obj, obj, obj]，也相当于一维数组nums1d = [obj, obj, obj]

• 无非是一维数组里面存储对象（obj）对应的是一个个标量，如nums1d = [1, 2, 3]
• 反观二维数组里面存储的对象（obj）对应的是一个个数组，如nums2d = [[1,2, 3,], [10, 20, 30], [100, 200, 300]]

obj0, obj1, obj2 = 1, 2, 3
nums1d = [obj0, obj1, obj2]

obj0, obj1, obj2 = [1, 2, 3], [10, 20, 30], [100, 200, 300]
nums2d = [obj0, obj1, obj2]

[liaoruochenxin]

我明白你的意思，首先的话我不觉得多维护一个变量是个特别好的方法吧，个人认为，还有问二维数组的小哥是楼下哦

[liaoruochenxin]

我目前想到相对来说，我以Java讲吧，最近是用Java在刷，可以考虑用Integer类型的数组，在删除之后把原来的设为null

[ffmm520]

length-1 是无意义的，并不会实际修改数组长度。数组一旦创建，长度是无法更改的。如果是基本数据类型，可以将最后一个元素置为默认值。引用类型则置为 null，参考 ArrayList 的 remove(int index) 方法

[FrierenGreatDemonLord]

话说不知道这个评论有没有编辑或删除的功能，有的时候没注意检查写错字，或者回错人，结果不能修改或删除😭

[lasdads5ad]

一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2 对应 arr[2]=1，index[1]=0 对应 arr[0]=8，index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。

本题要求你编写一个程序，为任何一个电话号码生成这段代码 —— 事实上，只要生成最前面两行就可以了，后面内容是不变的。

输入格式：
输入在一行中给出一个由11位数字组成的手机号码。

输出格式：
为输入的号码生成代码的前两行，其中arr中的数字必须按递减顺序给出。

输入样例：
18013820100
输出样例：
int[] arr = new int[]{8,3,2,1,0};
int[] index = new int[]{3,0,4,3,1,0,2,4,3,4,4};
啊啊啊对于这道题下面是我的代码但是为什么答案不对呢，求求各位大佬们帮我看看

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_set>
using namespace std;
int v[11] = { 0 };
int w[11] = { 0 };
vector<int>z;//这个地方有可能出问题，以前写过，到时候看看
int main()
{
	unordered_set<int>u;

	for (int i = 0; i < 11; i++)
	{
		int num;
		cin >> num;
		v[i] = num;//v是电话号码
		u.insert(num);//u是为了去重
	}
	
	for (int i : u)
	{
		z.push_back(i);//放进z中为了方便下面使用
	}
	sort(z.begin(), z.end(), greater<int>());//递减

	int k = 0;
	for (int i : u)
	{
		z.push_back(i);//放进z中为了方便下面使用
	}
	for (int i=0;i<11;i++)
	{
		for (int j=0;j<z.size();j++)
		{
			if (v[i]==z[j])
			{
				w[k] = j;//为了记录下表
				k++;
		 }
		}
	}
	for (int i : z)
	{
		cout << i << " ";
	}
	cout << endl;
	for (int i : w)
	{
		cout << i << " ";
	}

	return 0;
}

麻烦各位了！！！

[lauvli]

insert函数如果定义为插入的话，代码实现感觉就有点出入了，因为丢掉了最后的元素：

def insert(nums: list[int], num: int, index: int) -> None:
    """在数组的索引index处插入元素num"""
    # 把索引index之后的所有元素先后移动一位
    length = len(nums)
    nums.append(0)
    for i in range(length, index, -1):
        nums[i] = nums[i - 1]

    nums[index] = num

[BrianChen666]

Python里面内置函数insert为插入，这个插入是在不改变原数组已有元素的，不会删除，直接将对应索引所在位置替换为自己想要插入的值，然后索引所在位置所有值都会后移，数组长度加一

[AskRoxy]

从地址计算公式的角度看，索引本质上是内存地址的偏移量。突然就醍醐灌顶了。

[TOKKOW]

作者大大您好，我是一个初学者，所以不太清楚c++的访问元素以及后续的代码中为什么要在括号里加入int *nums这一部分，我查到了这个是指针的意思，它的具体作用是什么嘞

[zhkzly]

我C++没怎么用过，但是可以作为参考:数组new出来后好像是给一个地址，把数组创建后赋值给指针的时候，指针实际上是首元素的地址。形参中，传入指针应该还和局部变量有关，如果传入的是普通的标量之类的，实际上在函数中修改变量，是不会修改原始的数据，相反传入指针和引用，就可以修改原始数据。也可以去问一下gpt之类的语言模型，基本可以解决问题

[Aldebaran-ls]

在c/c++中，当定义一个数组int arr[5] = {1, 2, 3, 4, 5};数组名arr表示数组首元素的地址，相当于一个指针常量，因此可以通过指针来访问数组中的元素。
定义一个指针变量 int *ptr = arr; 让它指向数组元素的首地址，此时就可以使用 ptr 去访问数组元素，输出*ptr等同于arr[0], *(ptr+1)等同于arr[1]。
使用指针变量时加上*为解指针，即获取指针指向的内容。
在函数参数传递时，c/c++函数参数的数组会被退化为指针，例如函数 int randomAccess(int *nums, int size)，也可以 int randomAccess(int nums[], int size) 这样传参，int nums[] 和int* nums是等价的。

[TOKKOW]

原来如此！非常感谢作者大大 发自我的iPhone

…

------------------ Original ------------------ From: Aldebaran-ls ***@***.***> Date: Fri,Nov 22,2024 0:12 AM To: krahets/hello-algo ***@***.***> Cc: TOKKOW ***@***.***>, Comment ***@***.***> Subject: Re: [krahets/hello-algo] chapter_array_and_linkedlist/array/(Discussion #84)