小肥柴慢慢手写数据结构(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

相关文章

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Flutter打包APK的几种方式小结

《Flutter打包APK的几种方式小结》Flutter打包不同于RN,Flutter可以在AndroidStudio里编写Flutter代码并最终打包为APK,本篇主要阐述涉及到的几种打包方式,通... 目录前言1. android原生打包APK方式2. Flutter通过原生工程打包方式3. Futte

Docker镜像pull失败两种解决办法小结

《Docker镜像pull失败两种解决办法小结》有时候我们在拉取Docker镜像的过程中会遇到一些问题,:本文主要介绍Docker镜像pull失败两种解决办法的相关资料,文中通过代码介绍的非常详细... 目录docker 镜像 pull 失败解决办法1DrQwWCocker 镜像 pull 失败解决方法2总

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Ollama Python 使用小结

《OllamaPython使用小结》Ollama提供了PythonSDK,使得开发者能够在Python环境中轻松集成和使用本地运行的模型进行自然语言处理任务,具有一定的参考价值,感兴趣的可以了解一... 目录安装 python SDK启动本地服务使用 Ollama 的 Python SDK 进行推理自定义客

使用PyTorch实现手写数字识别功能

《使用PyTorch实现手写数字识别功能》在人工智能的世界里,计算机视觉是最具魅力的领域之一,通过PyTorch这一强大的深度学习框架,我们将在经典的MNIST数据集上,见证一个神经网络从零开始学会识... 目录当计算机学会“看”数字搭建开发环境MNIST数据集解析1. 认识手写数字数据库2. 数据预处理的

java String.join()的使用小结

《javaString.join()的使用小结》String.join()是Java8引入的一个实用方法,用于将多个字符串按照指定分隔符连接成一个字符串,本文主要介绍了javaString.join... 目录1. 方法定义2. 基本用法2.1 拼接多个字符串2.2 拼接集合中的字符串3. 使用场景和示例3