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

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

分布式系统的个人理解小结

分布式系统:分的微小服务,以小而独立的业务为单位,形成子系统。 然后分布式系统中需要有统一的调用,形成大的聚合服务。 同时,微服务群,需要有交流(通讯,注册中心,同步,异步),有管理(监控,调度)。 对外服务,需要有控制的对外开发,安全网关。

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre

Python 内置的一些数据结构

文章目录 1. 列表 (List)2. 元组 (Tuple)3. 字典 (Dictionary)4. 集合 (Set)5. 字符串 (String) Python 提供了几种内置的数据结构来存储和操作数据,每种都有其独特的特点和用途。下面是一些常用的数据结构及其简要说明: 1. 列表 (List) 列表是一种可变的有序集合,可以存放任意类型的数据。列表中的元素可以通过索

浙大数据结构:04-树7 二叉搜索树的操作集

这道题答案都在PPT上,所以先学会再写的话并不难。 1、BinTree Insert( BinTree BST, ElementType X ) 递归实现,小就进左子树,大就进右子树。 为空就新建结点插入。 BinTree Insert( BinTree BST, ElementType X ){if(!BST){BST=(BinTree)malloc(sizeof(struct TNo

【数据结构入门】排序算法之交换排序与归并排序

前言         在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。  一、交换排序 1.1 冒泡排序 冒泡排序是一种简单的排序算法。 1.1.1 基本思想 它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。 动画演示: 1.1.2 具体步

数据结构:线性表的顺序存储

文章目录 🍊自我介绍🍊线性表的顺序存储介绍概述例子 🍊顺序表的存储类型设计设计思路类型设计 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾” 和“内容共创官” ,现在我来为大家介绍一下有关物联网-嵌入