专栏首页相遇Linux三分钟了解数据结构

三分钟了解数据结构

程序要执行的快,数据结构一定要好,否则就会事倍功半。

在计算机世界中,通常有两种方法组织数据结构。

一种是大区块的结构,另一种是小区块的结构,大的块叫矩阵,

小的一块一块之间用线条穿起来。

对于矩阵结构,可以使用排序加二分查找,加快搜索速度。

对于小块的结构,方法有三种:

一个连一个

一个连两个

一个连多个

一个连一个,叫链表:

一个连两个,叫二叉树:

一个连多个的结构叫多叉树:

这些结构都必须要有相对应的增删改查算法。

有大块和小块的结构,就有混合结构.

hash表就是一种混合大块和小块的结构:

Hash = hashfunc(key)

index = hash % array_size

而其他数据结构则是上述结构的改良:

像红黑树就是一种自动平衡的二叉树,让树的层数尽量变小,不会太多倾斜导致搜索变慢。

而radix tree在linux kernel中有用于根据给定的index,查找对应的page结构:

本篇改编自中国台湾作者陈钟诚的用十分钟学会《资料结构、演算法和计算理论》

本文分享自微信公众号 - 相遇Linux(LinuxJeff),作者:JeffXie

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 使用crash工具看懂slab

    struct kmem_cache *sock_inode_cache 的地址为 ffff881020880fc0

    jeff xie
  • Linux内核入门回答

    要回答这个问题,我非常同意郭健(郭大侠)的观点,有一次他在一次linux深圳聚会上分享了他的观点:

    jeff xie
  • Linux内核红黑树使用

    我现正在linux kernel 4.4.1中新增一个类sysfs文件系统,取名jefffs,

    jeff xie
  • 推荐一个代码生成器 原

        想偷懒,那这个神器首先不能太复杂,鼠标点点,代码就出来了,其次功能要丰富,或者使用灵活,能生成任何语言的代码。

    尚浩宇
  • Tapestry 教程(四)探索项目结构 原

    l Web应用程序文件放在 src/main/webapp(包括src/main/webapp/WEB-INF)

    LeoXu
  • 使用root用户连接Ubuntu16.04时,提示SSH连接被拒绝

    (1)查看ip地址是否冲突 我在单位的虚拟机ip地址是192.168.8.85,与其它机器冲突了。改成了192.168.8.83 (2)关闭Ubu...

    似水的流年
  • 使用root用户连接Ubuntu16.04时,提示SSH连接被拒绝

    (1)查看ip地址是否冲突 我在单位的虚拟机ip地址是192.168.8.85,与其它机器冲突了。改成了192.168.8.83 (2)关闭Ubuntu16.0...

    似水的流年
  • 产品的原型应该如何去测试?

    产品的原型设计是产品设计开发的必要过程之一,而且原型设计在扮演着越来越重要的角色。原型设计的成功与否,有时会直接影响到这款产品的最终质量。同时一个合格的原型可...

    奔跑的小鹿
  • ssh password and passphrase

    ssh password and passphrase 1、ssh-keygen -t rsa     采用默认路径,输入passphrase。  2、scp ...

    joshua317
  • 最流行的编程语言JavaScript能做什么?

    首先很遗憾的一点是,“PHP虽然是最好的语言”,但是它不是最流行的语言。 ? 对不起的还有刚刚在4月TIOBE编程语言排行榜上榜的各个语言: ? 你们都很棒,...

    Phodal

扫码关注云+社区

领取腾讯云代金券