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示例

[ayanioX]

数组中首个元素对应数组的内存地址偏移量是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 或者其他软件都能画

[HappyCJ343]

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

[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是等价的。

[xbsheng]

在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是等价的。

大佬解答的一个小笔误~ ：最后的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)

[githubcookies]

我宣布你已经不是小白了！

[rui-project]

准备去集中刷一下数组的题，巩固一下所学哒。加油！

[yxltql]

day3,争取一天一章

[xzx1302]

数组的长度不可变，结构紧凑，所以适用于查找搜索而不适用于元素的删增

[TheFayyrr]

求教，这个在线看怎么找到自己的评论啊，发出去 的找不到

[void-placid]

Ctrl ➕F 查找自己的id试试

[etgintur]

这个里面的拓展数组容量中c语言的写法是不是有点错误，初始化扩展后的空间应该在将原数组中的所有元素复制到新数组的前面吧

[Hacker-C]

Java 实现数组类型

import java.lang.reflect.Array;

public class MyArray<T> {
    private T[] array;

    @SuppressWarnings("unchecked")
    public MyArray(int len, Class<T> clazz) {
        this.array = (T[]) Array.newInstance(clazz, len);
    }

    public T get(int index) {
        indexChecker(index);
        return array[index];
    }

    public void set(int index, T t) {
        indexChecker(index);
        array[index] = t;
    }

    public int lenth() {
        return array.length;
    }

    public void insert(int index, T t) {
        indexChecker(index);
        for (int i = lenth() - 1; i > index; i--) {
            array[i] = array[i - 1];
        }
        array[index] = t;
    }

    public void remove(int index) {
        indexChecker(index);
        for (int i = index; i < lenth() - 1; i++) {
            array[i] = array[i + 1];
        }
    }

    public int find(T target) {
        for (int i = 0; i < lenth(); i++) {
            if (get(i) == target) {
                return i;
            }
        }
        return -1;
    }

    public void trarverse(ArrayConsumer<T> consumer) {
        for (int i = 0; i < lenth(); i++) {
            consumer.accept(array[i], i);
        }
    }

    public MyArray<T> extend(int enlarge, Class<T> clazz) {
        MyArray<T> newArray = new MyArray<>(lenth() + enlarge, clazz);
        trarverse((value, index) -> {
            newArray.set(index, value);
        });
        return newArray;
    }

    private void indexChecker(int index) {
        if (index < 0 || index >= lenth()) {
            throw new ArrayIndexOutOfBoundsException("out of index: " + index);
        }
    }
}

[Limit1996]

C#备忘

namespace _1.Console;

public class CustomArray<T>(int size)
{
    public const string Description = "自定义数组实现";

    private readonly T[] _array = new T[size];

    public int Length => _array.Length;

    public T this[int index]
    {
        get
        {
            IsValidIndex(index);
            return _array[index];
        }
        set
        {
            IsValidIndex(index);
            _array[index] = value;
        }
    }

    private void IsValidIndex(int index)
    {
        if (index < 0 || index >= _array.Length)
            throw new IndexOutOfRangeException("索引超出数组范围");
    }

    public void Insert(int index, T value)
    {
        IsValidIndex(index);
        for (int i = _array.Length - 1; i > index; i--)
            _array[i] = _array[i - 1];
        _array[index] = value;
    }

    public void Remove(int index)
    {
        IsValidIndex(index);
        for (int i = index; i < _array.Length - 1; i++)
            _array[i] = _array[i + 1];
        // 将最后一个元素置为默认值
        _array[^1] = default!;
    }
}

[MarsToken]

public void remove(int index) {
if (index < 0 || index > array.length - 1) {
throw new IndexOutOfBoundsException("index is " + index + ",length is " + array.length);
}
for (int i = index; i < this.array.length - 1; i++) {
array[i] = array[i + 1];
}
// 建议最后一位赋值0，要不最后一位没变动
array[array.length - 1] = 0;
}

[Limit1996]

_array[^1] = default!;同等效果，由于是泛型且没有约束，所以要赋default

[xiaozhuge123]

day03

[djR-dj]

为什么怎么看这都是数组求和：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

[jidaojiuyou]

是求和。不过他想表示的三个重点是 for。而非 for 下面的内容

• 索引遍历

for i in range(len(nums)):
    pass

• 直接遍历

for num in nums:
    pass

• 同时遍历数据索引和元素

for i, num in enumerate(nums):
    pass

[main520]

我看看怎么在评论区展示代码

print('学hello-algo的都是大帅比')

[main520]

print('为什么你们的代码可以高亮')

[Changkeyii]

day4

[clione12]

哈喽作者大大，我觉得python的代码，insert list 那里不合理，应该先扩容的，不然最后一个元素在insert后会丢失的，这是改进后的代码

def insert(nums, num, index):
nums.append(None) # 先扩容，长度 +1
for i in range(len(nums) - 1, index, -1):
nums[i] = nums[i - 1]
nums[index] = num

[clione12]

sorry没看到后面的数组长度固定这一条，我这里没问题了

[zhengads]

有点抽象，感觉概念突脸还是太难理解了，慢慢来吧