chapter_data_structure/classification_of_data_structure/

[giscus[bot]]

chapter_data_structure/classification_of_data_structure/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_data_structure/classification_of_data_structure/

[doo5]

请问：线性数据结构和非线性数据结构，哈希表为什么都存在。

[chenzhiwei54czw]

我觉得应该是因为哈希表在没有冲突之前，是用数组存储的，当出现哈希冲突之后，有各种解决冲突的方式，比如链地址法，所以两种逻辑结构都包括它，不像其他的数据结构都是只用数组或者只用链表实现的

[krahets]

好问题～这因为哈希表底层是数组，所以包含线性数据结构。而为了解决哈希冲突，我们可能会使用“链式地址”（后续散列表章节会讲）。在链式地址中，哈希表的每个桶（索引）都存储一个链表；当链表长度超过一定阈值时，又可能被转化为树（常为红黑树），以提升查询效率。因此，哈希表可能同时包含线性（数组、链表）和非线性（树）数据结构。

[TujinLee]

基于数组实现的数据结构也被称为「静态数据结构」，这意味着该数据结构在在被初始化后，长度不可变。

像JS的数组可以不断的push数据，长度也在变化吧，可能底层做了处理？

[krahets]

是的 Python List, Go Slice, JS/TS Array, C++ vector 都采用了类似的策略，用户最常用的是动态数组，底层实现了扩容机制。（语言没列全，现在一般都直接用动态数组了，方便）

[luckyamber1992]

2023.05转码打卡，看晕了

[krahets]

万事开头难，加油！

[Sakura11hoo]

算法小白，冲今年的秋招

[YuMiao316]

ヾ(◍°∇°◍)ﾉﾞ加油

[Tttdotd]

加油，你绝对没问题的

[chusifeng]

「物理结构」反映了数据在计算机内存中的存储方式，可分为数组的连续空间存储和链表的离散空间存储
---- 这个是指程序“看到的”虚拟内存是连续空间还是说虚拟映射的物理都是连续空间？

[krahets]

好问题！这里指的是虚拟内存。假设我们初始化一个很大的数组。在虚拟内存中，数组的内存空间是连续的。这样我们才能通过首元素地址加偏移量的方式来访问数组中的任何元素。

然而，在物理内存中，数组可能并不连续。虚拟内存到物理内存的映射涉及到分页（paging）技术。操作系统通过分页系统，将虚拟内存和物理内存都划分为大小相等的页。每个虚拟页都可以单独映射到物理内存中的任意一页。所以，一个大的数组（占据多个虚拟内存页）在物理内存中可能是分散的，每个虚拟页在物理内存中的位置可能不连续。

值得强调的是，虽然物理内存中的连续性可能会对性能有影响，但在实际应用中，这通常并不是主要的性能瓶颈。现代的计算机系统已经采用了许多优化技术，例如缓存、预取等，以尽可能减小这种影响。

[YuMiao316]

作者的链表的图看着很舒服，数据域和指针域感觉很清晰

[zhuasdfg]

节点和节点指针看着一目了然，链表就该长这样

[1ess]

Fig. 线性与非线性数据结构中队列的操作称为enqueue和dequeue比较合适吧

[krahets]

只有 C# 的入队出队方法是用 enqueue 和 dequeue 命名的。感觉这个不需要太纠结。

[1ess]

上文中哈希表被描述为既是线性结构还是树形结构，我认为其属于线性结构比较合理把

[1ess]

看了后面的QA，能理解想表达的意思，但是感觉这块描述还是不合理，这个地方还是应该要描述清楚。线性结构：...哈希表，元素之间是一对一的顺序关系。树形结构：... 哈希表，元素之间是一对多的关系。

[krahets]

从存储的角度来看，哈希表的底层是线性的数组结构。这个数组中的每一个槽位可能包含一个值，也可能包含一个链表或树（在解决哈希冲突时），因此也可能包含非线性数据结构。

[1ess]

Fig. 连续空间存储与离散空间存储中，链表箭头的起始位置和结束位置正确吗，我理解不应该是起始位置为指针域的中心，结束位置是下一个节点的数据域吗？

[iHaveFiveDogs]

图做的确实有新意。

[wangxiangnan]

逻辑结构和物理结构都有数组和链表的概念，这个如何区分呢？之前是通过顺序存储和链式存储区分的。

[krahets]

在逻辑结构中，数组和链表都属于线性结构。在物理结构中，数组是顺序存储（连续内存空间），链表是链式存储（离散内存空间）

[BenjiWu]

线性结构：数组、链表、队列、栈、哈希表，元素之间是一对一的顺序关系。
树形结构：树、堆、哈希表，元素之间是一对多的关系。
这里hash table出现在两个分类，是写错了还是都符合呢？

[krahets]

这个在小结的 Q&A 里有讲

[newcakes]

这让我回想起来c++中map容器和multimap容器的区别，map容器的key值不可以重复，而multimap容器是可以重叠的，这两个容器的底层应该是hash table，这会不会就是一对一和一对多的区别呢？@krahets

[krahets]

@newcakes 这里确实有一对一和一对多的逻辑关系。即使是一对一的普通哈希表，它的底层实现也可能包含非线性数据结构。

[yicijohncy]

遇到一样的疑问，hhhh，k 大，建议把Q&A那部分内容挪到分类讲解下方，也不会卡住，能理解的~

[Chenyuyang7]

大佬你好，在java中ArrayList底层采用hash表的存储方式，在jdk7之前hash表存储数据采用的是的数组加链表，jdk7之后采用数组加链表及红黑树的存储方式，那么我的问题是，hash表本身提供了这种数组加链表和红黑树的存储方式还是这种存储方式是java所设计的？

[krahets]

这种存储方式是 Java 设计的。哈希表是使用数组、链表、二叉树等这些数据结构实现的。

[Zswdhy]

基于数组实现的数据结构也被称为“静态数据结构”
这个存在歧义吧，栈，队列也是可以进行出栈、入栈等操作的呀

[krahets]

Hi，栈和队列确实可以实现动态的数据操作，但数据结构仍然是“静态”（长度不可变）的。尽管基于数组的数据结构可以动态地添加或删除元素，但它们的容量是固定的。如果数据量超出了预分配的大小，就需要创建一个新的更大的数组，并将老数组的内容复制到新数组中。

[Zswdhy]

在构建栈/队列的时候，未指定栈/队列的大小，怎么理解成“静态数据结构呢”

[krahets]

在高级编程语言中，我们无须人工指定栈/队列的初始容量，这个工作是由类内部自动完成的。例如，Java 的 ArrayList 的初始容量通常为 10 。另外，扩容操作也是自动实现的。详见本书的“列表”章节。

也就是说，基于数组实现的栈，底层实现是数组，仍然具有数组的静态性。只不过编程语言的内置库已经预先实现好了栈类的各种行为（初始化、扩容等），使得它看起来是动态的，使用起来是灵活的。

[LitchiLiy]

我记得C++容器好像未指定容量大小则默认为0, 当被添加元素时会将存储空间搬到其他地方并赋予一个合适的容量, 等容量再次被超出时会再次将存储空间搬到其他地方并再次赋予一个更大的容量.

[giftfm]

线性结构：数组、链表、队列、栈、哈希表，元素之间是一对一的顺序关系。
树形结构：树、堆、哈希表，元素之间是一对多的关系。
hash表为什么既可以一对一又可以多对一，hash表怎么多对一？

[ganxingrui]

按map理解，一对一就是key-value;一对多，把value换成链表

[krahets]

Hi，一对多的关系与“哈希冲突”概念相关。在链式地址哈希表中，冲突的元素被存储在一个链表中，这条链表还可能被优化为二叉树，以提升查找效率。

[HannahHathaway]

哦哦 明白啦 非常感谢

[ganxingrui]

逻辑结构：是抽象结构，理论上的结构；
物理结构：是存储在物理硬件上的真实结构；

[foreverpersistence]

逻辑结构： 元素逻辑关系，分线性和非线形。

• 线形结构： 数组、链表、堆、栈、哈希， 元素 一对一
• 非线形结构：树、图、哈希
  物理结构：连续 和 非连续
• 连续结构： 数组结构
• 非连续结构： 链表结构

所有的数据结构可以通过 数组和链表实现。

作者讲的很形象，赞

[LoganQiu]

k神，想问问这些图片是用什么工具制作的，看起来非常优雅

[krahets]

用 keynote 或 powerpoint 都可以画噢～

[HuaWang135608]

可以尝试一下 draw.io 哇

[CryusXin]

基于数组实现的数据结构也称“静态数据结构”，这意味着此类数据结构在初始化后长度不可变。

但是python中的数组通常是指list，这是一个动态数据结构，然后python中还有一个array模块，提供了一种数组类型

import array

# 创建一个整数数组（'i'是类型码，表示有符号整数）
int_array = array.array('i', [1, 2, 3, 4, 5])

array模块的数组与列表类似，也是动态的，可以在运行时改变大小

python中只有元组类型是静态数据结构

[krahets]

Hi，感谢反馈！文中的描述的确有歧义，我想想怎么改。

你提到的元祖静态、列表动态是从“逻辑结构”角度观察的。其实，如果从逻辑角度看，数组也可以是“动态”的：使用一个变量记录有效容量，我们就可以模拟出“动态性”了。

然而，文中提到的“静态”和“动态”概念，是从“物理结构”角度观察的。虽然列表（list）可以进行增删改查，但由于它的底层是数组，因此在扩容过程中仍然需要进行内存再分配、元素整体搬移的额外工作，即它的物理结构是“静态”的。

这个名词从不同角度观察会有不同的结果（我尚未找到标准定义，后面我再看看）。

[CryusXin]

我进行了一些简单的尝试

nums = [1, 2, 3, 4, 5]
print(f'nums内存地址：{hex(id(nums))}')
nums.insert(1, 6)
print(nums)
print(f'nums插入元素后的内存地址：{hex(id(nums))}')

输出
nums内存地址：0x24e220d9480
[1, 6, 2, 3, 4, 5]
nums插入元素后的内存地址：0x24e220d9480

这个插入操作并没有改变它的内存地址，如果说数组扩容的时候会进行内存再分配，那我的理解，只有一种可能，就是python列表的插入删除方法，实际上用空间换时间了，在我定义这个nums的时候，就已经默认可以插入100个或者更多的元素，当我插入的元素没有超过默认值的时候，其实并不需要进行内存再分配，只有空间不足以容纳新元素时，python的解释器才会去获取更大的内存空间，然后执行元素复制

[krahets]

是的，扩容机制在“列表”章节有介绍：系统会为数组初始化一个合理的长度，在到达这个长度限制之前，添加元素不会触发扩容；当超出长度限制时，则会进行扩容（内存再分配 + 元素搬移）。

由于 nums 是一个对象，因此即使扩容之后 id(nums) 输出的地址应该也不会改变（底层存储数据的数组的内存地址会发生变化）。

[yxsongbo]

从图中看不出堆和树的区别嘛

[anchorforG]

因为这个排版吧，理解为是则不是的状态。阅读后面内容可以消除了，只是没找到怎么删除这个评论了。

[krahets]

Hi，这是因为堆是一种树的特例情况

[NgxuAnGMH]

编程语言的标准包，都会将常用的数据结构封装好提供外部使用。虽然“数组”作为“静态数据结构”，但其实在一些编程语言中也已经考虑到了动态伸缩的设计。不过掌握该知识点还是很有必要的

• 数组可通过重新分配内存实现长度变化，从而具备一定的“动态性”。

[johnluck66]

您好！我有几个问题，请赐教：
问题1：
书中提到："当算法程序运行时，正在处理的数据主要存储在内存中。" ，我联想：
请问在CPU内部的寄存器、缓存，请问 是不是也有有 书中的 数据结构，和用到相关的算法？
这方面 有什么不一样吗？

问题2：
书中提到：“计算机根据特定规则为表格中的每个单元格分配编号，确保每个内存空间都有唯一的内存地址。”
我联想：
请问 （1）这个“特点规则” 有没有行业统一标准？
请问（2） 不同的操作系统、不同CPU、不同内存条，这个“特点规则” 是否不同？
（3）在电脑端的和手机移动端， 这个“特点规则” 有什么不一样？

问题3：
书中提到”所有数据结构都是基于数组、链表或二者的组合实现的“
我理解：
1、数组、链表 是物理存储的 两个最基本形态，即 连续 和 分散，也只有 这两种基本形态
2、其他所有 数据结构，是 根据 现实世界的需求（或者说 现实世界的问题 的抽象 及分类），人为创造出 各种数据结构， 像 初级语言 向 高级语言 的演进
请问我的理解是否对，请赐教

问题4：
书中”图3-3“ 中，存储链表，”存储节点值“ （横向）后面紧接 ”存储节点指针“，
请问（1）是不是所有（操作系统、CPU、内存） 中的 链表，都是这种设置？
（2）箭头 指向 的好像是 节点值 和节点指针 之间，请问这个是不是可以展开讲一讲?

[BLackWatch1118]

1：我的理解是算法实际上是一种思想，数据结构是实现你思想的载体，不同地方由于目的不同适用的思想也不同，比如缓存替换中可能有随机、FIFO、LRU之类的替换方法，你想实现这种方法就要选择合适的数据结构，比如在需要取得某链表节点的前一个节点时用单纯的单向链表就比较困难了。

2：这个比较复杂，我不是很确定，因为实际上内存机制包括虚拟内存和实际内存和缓存，虚拟内存提供一个对主存的抽象，让每一个进程都认为它享用一个巨大、一致、私有的地址空间，缓存是加速数据传输的中间层。cpu生成的虚拟地址通过地址翻译单元MMU来转换为物理地址，就是在主存上数据的实际储存位置，然后具体的过程中会有其他的机制来保证这个过程正确且高效的执行。我觉得这个是跟着操作系统走的，基本思路应该类似，但不同的操作系统的实现细节应该不太一样，32位和64位的系统起码地址空间就不一样。

3：不知道。我觉得都是为了解决问题找出的解决办法，需要啥用啥，我不太清楚初级和高级的定义。

4：仍然我按照之前想法，链表也是一种思路，核心就是每个节点都有找到下一个节点的方法，所以实现思路就是节点本身的值+到下一个节点的索引，至于这个索引是节点的指针还是其他标识方式都无所谓，能找到就行，看编程语言是怎么实现的。C语言里应该是指向下一个节点首元素的地址，图里应该只是为了看起来好看，指向中间可能会因为对齐之类的原因取值比较麻烦。

不确定我说的是不是对的，你可以多方求证下。

[oopfjp]

关于第四个问题的第二小点，鄙人是这么理解的：链表（这里举例单链表）的每个元素都包含一个值和一个指向下一个元素的指针，所以箭头就代表Next指针，指的就是下一个元素的内存地址，你说的指向节点值和节点指针中间，可能就是这么画的，只要理解原理就行了。

[lvmingq]

书中怎么没有提到线性表

[krahets]

线性表是一个中文社区特有的概念，它的英文翻译 Linear list 在英文社区并不常见，因此本书没有介绍这个概念。

详见 Wiki，线性表的词条只有中文版本：
https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E8%A1%A8

相对地，数组、链表、列表是中英文社区（以及其他语言）都广泛接受的概念。

[fr33bug]

内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。

-- 这个说法并不是太严谨，通常情况下是这样，但也存在共享内存的情况。

[lei-ctyh]

作者应该在文中说明了 "通常无法被其他程序同时使用了。"

[BeOneBetterGUO]

为什么线性结构和非线性结构中都有哈希表？？？

[BeOneBetterGUO]

omg我看见了回复了，这条评论能不能删掉？

[2oTA]

可惜没早点看到这个网站

[AritxOnly]

有的时候上课会提到的：堆区和栈区这个模型是否就是完全对应对应物理结构的连续与分散？还是可能有什么因为环境导致的区别？

[Umizhang0910]

henbuduo

[Stev1eL]

王长生，看到我没