汕头制作网站软件,做公司网站需要备案吗,濮阳网站建设价格,自定义wordpress标题的分隔符概念#xff1a; 数据结构 : 数据用什么样的方式组合在一起。 数据结构是计算机存储数据的方式#xff0c;指相互之间存在一种或多种特定关系的数据元素集合 常见数据结构#xff1a; 数据存储的常用结构有#xff1a;栈、队列、数组、链表和红黑树。 栈#xff1a; stack…概念 数据结构 : 数据用什么样的方式组合在一起。 数据结构是计算机存储数据的方式指相互之间存在一种或多种特定关系的数据元素集合 常见数据结构 数据存储的常用结构有栈、队列、数组、链表和红黑树。 栈 stack,又称堆栈它是运算受限的线性表其限制是仅允许在标的一端进行插入和删除操作不允许在其 他任何位置进行添加、查找、删除等操作。 栈结构的特点 先进后出FILO 压栈(进栈)就是存元素。即把元素存储到栈的顶端位置栈中已有元素依次向栈底方向移动一个位置。弹栈(出栈)就是取元素。即把栈的顶端位置元素取出栈中已有元素依次向栈顶方向移动一个位置。 图解
队列结构: queue简称队它同堆栈一样也是一种运算受限的线性表其限制是仅允许在表的一端进行插入而在表的另一端进行删除。 队列结构的特点 先进先出FIFO,进和出是两个口比如我们排队是不是先排的先拿到号离开 数组结构 数组是一种查询快增删慢的模型 在内存中数组的数据连续存放数据长度固定这样知道数组开头位置和偏移量就可以直接计算出数据地址 查询数据通过地址值和索引定位查询任意数据耗时相同查询速度快 删除数据时要将原始数据删除同时后面每个数据前移删除速度慢 添加数据时添加位置的每个数据后移再添加元素添加速度慢 数组结构的特点
链表结构 链表linked list由一系列结点node链表中每一个元素称为结点组成结点可以在运行时动态生成。每个结点包括两个部分一个是存储数据元素的数据域另一个是存储下一个结点地址的指针域。我们常说的链表结构有单向链表与双向链表。 简单的说采用该结构的集合对元素的存取有如下的特点 查找元素慢想查找某个元素需要通过连接的节点依次向后查找指定元素增删元素快添加或者删除某个元素只要更换上一个节点和下一个节点就可以了 单向链表
双向链表 单向链表如果说是只能向右看那么双向链表就是可以左右看了它是前面记录上一个的地址后面是下一个的地址。 一般用双向链表比较多因为比较方便 总结 链表元素不是连续存放的上一个元素记录下一个元素的地址查慢、增删快 二叉树 二叉树是高度平衡的数据结构误差超过1就会旋转树的作用可以做排序可以做索引比较方便查找的时候呢可以说是二分搜索就是你每次找判断都砍掉一半无用的树每个节点不超过2左子树元素小右子树元素大节点: 在树结构中,每一个元素称之为节点度: 每一个节点的子节点数量称之为度 二叉树结构图
二叉查找树 二叉树和二叉查找树对比 二叉树没有规律而二叉查找树有规律任意的一个结点都是左小右大 二叉查找树添加原理 先和根节点比较再和子节点比较小存左、大存右、相同不存拿数据7、4、10三个数据举栗先存7作为根节点再存4存4的时候要判断4是大于7还是小于7小于就做位7的左子节点大于就做位7的右子节点。10也是一样。然后就是7为根节点4为左子节点10位右子节点。 二叉查找树的弊端 拿数据7、10、11、12举栗先存7作为根节点再存10存10的时候要判断4是大于7还是小于7然后就成为了7的右子节点。再存1112最后发现整棵树都是右子节点没有左子节点。那么查找的时候就要一个一个的去遍历效率低因为左子节点和右子节点高度差太大。 平衡树二叉树 二叉树左右两个子树的高度差不超过1任意节点的左右两个子树都是一颗平衡二叉树平衡二叉树存在的意义就是解决二叉树高度不一致的问题 旋转树 旋转树就是平衡机制存在就是保证二叉树的平衡旋转触发时机 只有平衡二叉树和红黑树会用到当添加节点破坏了平衡就会触发左右旋转 左旋 逆时针左旋转整体往左旋转右子节点变父节点原来的根节点降级成左子节点多余的左子节点给降级的左子节点当右子节点 右旋 顺时针右旋转整体往右旋转左子节点变父节点原来的根节点降级成右子节点多余的右子节点给降级的右子节点当左子节点 平衡二叉树旋转的四种情况
左左 当根节点左子树的左子树有节点插入,导致二叉树不平衡如何旋转: 直接对整体进行右旋即可4会做为根节点2为左子节点7为右子节点5为7的左子节点 左右 当根节点左子树的右子树有节点插入,导致二叉树不平衡如何旋转: 先在左子树对应的节点位置进行左旋,在对整体进行右旋先把圈起来的部分左旋然后如图二再右旋 右右 当根节点右子树的右子树有节点插入,导致二叉树不平衡如何旋转: 直接对整体进行左旋即可将10做为根节点7成为10的左子11为右子9为7的右子节点 右左 当根节点右子树的左子树有节点插入,导致二叉树不平衡如何旋转: 先在右子树对应的节点位置进行右旋,在对整体进行左旋先把10节点下的右旋然后如右图所示再整体左旋 红黑树 红黑树(平衡二叉B树每一个节点可以是红或者黑红黑树不是高度平衡的,它的平衡是通过自己的红黑规则进行实现的 红黑规则 每一个节点或是红色的,或者是黑色的根节点必须是黑色如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连 的情况)对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点 添加节点规则 添加节点的时候默认为红色效率高对应红黑规则跳转比较少红黑树添加节点后如何保持红黑规则 如果是根节点位置直接变为黑色 非根节点位置父节点为黑色不需要任何操作,默认红色即可父节点为红色叔叔节点为红色 将”父节点”设为黑色,将”叔叔节点”设为黑色 将”祖父节点”设为红色 如果”祖父节点”为根节点,则将根节点再次变成黑色叔叔节点为黑色 将”父节点”设为黑色 将”祖父节点”设为红色 以”祖父节点”为支点进行旋转
