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 设计的。哈希表是使用数组、链表、二叉树等这些数据结构实现的。

[CodingGorit]

打卡

[DarKnightL]

Stack and Queue

Stack:
Principle: LIFO (Last In, First Out) - The last item to be inserted into a stack is the first one to be deleted from it.
Real-world analogy: Think of a stack like a stack of plates on a table. The last plate you put on the top of the stack is the first plate you would remove if you were unstacking them.
Operations:
Push: Adds an item onto the stack. If the stack is full, then it is considered a stack overflow condition.
Pop: Removes an item from the stack. Items are removed in the reverse order of their addition (LIFO). If the stack is empty, trying to pop an element could lead to a stack underflow condition.
Usage: Stacks are used in scenarios like function calls (call stacks), undo mechanisms in text editors, and for depth-first search algorithms in data structures like trees or graphs.

Queue:
Principle: FIFO (First In, First Out) - The first item to be inserted into a queue is the first one to be deleted from it.
Real-world analogy: Think of a queue as a line of people waiting to buy tickets at a ticket counter. The person who has been in line the longest (first in) gets served first (first out).
Operations:
Enqueue: Adds an item to the end of the queue. If the queue is full, then it is considered a queue overflow condition.
Dequeue: Removes an item from the front of the queue. If the queue is empty, trying to dequeue an element could lead to a queue underflow condition.
Usage: Queues are used in scenarios like breadth-first search algorithms in data structures like trees or graphs, managing tasks in printers, process scheduling, and in simulations of real-world systems (like customers standing in lines).
In summary, the main difference lies in the order of element retrieval: stacks retrieve elements in the reverse order of their addition (LIFO), while queues retrieve elements in the same order as their addition (FIFO). This fundamental characteristic makes them suitable for different kinds of operations in computing and programming.

[Xj1567589354]

daka

[lizhuangShen]

逻辑结构：
线性：数组，链表，栈，队列，哈希表
非线性：树，图，堆，哈希表

线性结构：元素之间是一对一的顺序关系 数组，链表，栈，队列，哈希表
树形结构：元素之间值一对多的关系 树，堆，哈希表
网状结构：元素之间是多对多的关系 图

物理结构：
所有的数据结构都是基于数组或链表实现的

基于数组：栈，队列，哈希表，树，图，堆，矩阵，张量（维度>=3的数组）
基于链表：栈，队列，哈希表，树，图

[lihuangshuaige]

堆和树有啥区别？

[krahets]

请看这里

[java-pakchoi]

基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度>=3的数组）等

请问一下，数组不是线性结构嘛，怎么实现非线性的树呢？
难道是多维数组或者借助其他引用类型？

[hemingguo]

应该取决于具体的树的类型，比如二叉树，前缀树就可以用数组实现

[QiuShui-666]

大顶堆也是树的一种，堆那块就是用数组实现的

[krahets]

Hi，在本书的这个章节有讲

[brycenhe]

请问文中的配图是使用什么软件制作的呢？感觉很棒！

[krahets]

谢谢～Keynote 或者 Powerpoint 都可以画

[Keekuun]

打卡

[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语言里应该是指向下一个节点首元素的地址，图里应该只是为了看起来好看，指向中间可能会因为对齐之类的原因取值比较麻烦。

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