小肥柴慢慢手写数据结构(C篇)(5-4 中场小结)

2024-02-19 08:52

本文主要是介绍小肥柴慢慢手写数据结构(C篇)(5-4 中场小结),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

小肥柴慢慢学习数据结构笔记(C篇)(5-4 中场小结)

  • 目录
    • 5-14 再看数据结构的基础问题
    • 5-15 接下来关于Tree你还需要学习和了解的内容
    • 参考文献和资料

目录

5-14 再看数据结构的基础问题

假设前面讨论的所有内容大家都已经自己编码实现了一遍,很容易作出以下推断:

(1)数据结构底层的具体存储结构无外乎两种,即:“数组”和“链表”,也就是很多资料/博客中描述的“顺序存储”和“链式存储”。

兜兜转转,咱们的讨论还是回到了第一次讨论数据结构的一个点,即:“数据的存储与组织”,算是扣题了。

(2)使用数组的优点:检索和修改快;使用数组的缺点:插入和删除操作慢,因为需要“挪位置”。

(3)使用链表的优点:插入和删除操作快,因为无需挪位置;实用链表的缺点:检索和修改慢。

【注】此处的“修改”,可以看做一种形式的“计算”;话说回来,计算机科学与技术的核心,不就是数据的“存储”与“计算”吗?巧不巧?哈哈哈…

而造成数组和链表优缺点相反的关键在于寻址机制的不同,有兴趣的话可以自行研究一下两者的汇编实现,引用他人的描述:

数组可以用基地址和偏移量访问的,有专门的汇编代码,move指令。而链表,对不起,单周机器指令不存在。

由此可知,数据结构在使用过程中应该根据实际需要选择合适的实现形式。但我们还是不禁要提出一个疑问:

【Q】有没有可能存在一种数据结构,它能够集合顺序存储和链式存储的优点呢?
【A】有,大家最熟悉的就是hash(散列表),且这个数据结构对应的数学理论研究和具体实现还在不断进化,譬如在JDK源码中HashMap的实现就非常有意思:
(1)它不仅能通过计算key值实现数据快速的查、取和尽可能的均匀、分散的存储。
(2)它还能根据同key节点上元素数量的变化,动态地将存储模式在单链结构和树形结构之间灵活切换,完全满足性能要求。

当然,这是后续章节需要讨论的内容,大家可以期待一下。

5-15 接下来关于Tree你还需要学习和了解的内容

主线任务先告一段落,对初学者我个人建议先绕后面的章节学习散列、堆、并查集和图论初步,因为从这儿开始之后的数据结构的复杂度(包括具体实现和数学推导)和学习难度陡增,需要投入更多的精力反复琢磨;但正式这些复杂的工具却往往是实际工程应用中最实用的基础部件,且在面试中属于面试官摸底的必选题库,属于典型的手搓费劲、用起来真香。以下有趣的高级数据结构,我们会逐一开贴讨论,莫急(讲真,数学推导已经把我捶打成小丑了)。

(1)有趣的伸展树(Splay Tree)
(2)经典的红黑树(RBTree)
(3)B树、B+树
(4)前缀树(Trie Tree 字典树)
(5)k-d树
(6)AA树
…(待补充)

【注】
(1)前四个是找工作的朋友必须掌握的,因为它们真的非常经典。
(2)treap树放在Heap(堆)中学习、讨论。

欲速不达,慢慢熟悉,慢慢打磨。

参考文献和资料

[1] labuladong相关博客
[2] liuyubobo相关博客
[3] 黑皮书
[4] 为什么数组索引数据那么快速、有效?
[5] 玩转《数据结构》顺序表和链表的比较
[6] 顺序存储和链式存储

这篇关于小肥柴慢慢手写数据结构(C篇)(5-4 中场小结)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/724161

相关文章

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,:本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式?2. Lambda表达式的基本语法例子1:最简单的Lambda表

Java中Scanner的用法示例小结

《Java中Scanner的用法示例小结》有时候我们在编写代码的时候可能会使用输入和输出,那Java也有自己的输入和输出,今天我们来探究一下,对JavaScanner用法相关知识感兴趣的朋友一起看看吧... 目录前言一 输出二 输入Scanner的使用多组输入三 综合练习:猜数字游戏猜数字前言有时候我们在

SQL BETWEEN 的常见用法小结

《SQLBETWEEN的常见用法小结》BETWEEN操作符是SQL中非常有用的工具,它允许你快速选取某个范围内的值,本文给大家介绍SQLBETWEEN的常见用法,感兴趣的朋友一起看看吧... 在SQL中,BETWEEN是一个操作符,用于选取介于两个值之间的数据。它包含这两个边界值。BETWEEN操作符常用

go 指针接收者和值接收者的区别小结

《go指针接收者和值接收者的区别小结》在Go语言中,值接收者和指针接收者是方法定义中的两种接收者类型,本文主要介绍了go指针接收者和值接收者的区别小结,文中通过示例代码介绍的非常详细,需要的朋友们下... 目录go 指针接收者和值接收者的区别易错点辨析go 指针接收者和值接收者的区别指针接收者和值接收者的

python uv包管理小结

《pythonuv包管理小结》uv是一个高性能的Python包管理工具,它不仅能够高效地处理包管理和依赖解析,还提供了对Python版本管理的支持,本文主要介绍了pythonuv包管理小结,具有一... 目录安装 uv使用 uv 管理 python 版本安装指定版本的 Python查看已安装的 Python

C#中DrawCurve的用法小结

《C#中DrawCurve的用法小结》本文主要介绍了C#中DrawCurve的用法小结,通常用于绘制一条平滑的曲线通过一系列给定的点,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 如何使用 DrawCurve 方法(不带弯曲程度)2. 如何使用 DrawCurve 方法(带弯曲程度)3.使用Dr

MySQL 分区与分库分表策略应用小结

《MySQL分区与分库分表策略应用小结》在大数据量、复杂查询和高并发的应用场景下,单一数据库往往难以满足性能和扩展性的要求,本文将详细介绍这两种策略的基本概念、实现方法及优缺点,并通过实际案例展示如... 目录mysql 分区与分库分表策略1. 数据库水平拆分的背景2. MySQL 分区策略2.1 分区概念