数据结构+算法 （原创：黑小子-余） 前言：小编我从小数学并不好，每次考试都是特码分数，跟小伙伴比算数也常常慢一拍，父亲常常恨子不成器。从小就不自信的我，觉得自己智商总比别人差一点，直到成年后，我发现真是如此，每个夜深人静的时候，深深地怀疑自己，哈哈！其实，小编我是一个很正能量的人，虽然踏出学堂、初入社会找工作并不顺利，而且生活中发生很多事也并不如意，找工作的那段时间，也懂得了很多，我相信这些经历都会...
1. 问题 : 链表的整体反转 题目 : 将链表整体进行反转 例如 : 链表 1 --> 2 --> 3 --> 4 --> 5 反转为 5 --> 4 --> 3 --> 2 --> 1 //算法思想 : 记录 当前遍历结点的前一个结点和后一个结点 确保每次向后遍历能够找到 //当前结点的前一个结点 以此完成链表的反转 同时时间复杂度最小 为O(n) listNode * listReverse_all(listNode * list) {listNode * nextNode = list->next; listNode * rNode = list;listNode * beforeNode = NUL...
5.1 树的逻辑结构 5.1.1 树的定义和基本术语 1、树的定义结点：树中的数据元素树：是n个结点的有限集合（当n=0时，称为空树）1? 有且仅有一个特定的称为“根”的结点 2? 当n > 1时，除根结点之外的其余结点被分成m（m > 0）个 互不相交 的有限集合T1、T2、…、Tm，其中每个集合又是一棵树，并称为这个根结点的子树（树的定义是递归的）每棵子树只能有一个根结点2、树的基本术语结点的度、树的度结点的度：某结点所拥有的 （直接）子...
题记：题主工作三年，前段时间面试bat被面试官算法“血虐”，差点心灰意冷，怀疑人生，但是幸好意志坚强，遂，决定发愤图强，学好算法。每天坚持学一些，每周坚持有深度学习四小时。先慢慢来，学好基本的概念，常用的数据结构和算法，但是图的话，就不涉猎了，因为真的比较难，学习成本太高，讲究性价比嘛。 之后主要是记录学习常用数据结构和算法。像栈，队列，树精要笔记。内容也不会过于基础，特别基础的会一带而过，主要是记录...
数据 – 程序的操作对象，用于描述客观事物 int a ,int b 数据的特点： 可以输入到计算机 可以被计算机程序处理 数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等 数据元素：组成数据的基本单位 array[1],array[2],这就是数据元素。 数据项：一个数据元素由若干数据项组成 数据对象 – 性质相同的数据元素的集合 数据的基本概念及研究意义 数据是一个抽象的概念，将其进行分类后得到程序...
1.问题概述 我们在介绍二分搜索树的时候提到时间复杂度为O(logn),但是这并不是绝对的，有些时候树可能退化为链表，时间复杂度回到O(n)级别，所以为了性能考虑，应尽量避免这种退化，这就用到了平衡树。2.什么是平衡二叉树 平衡二叉树的定义是，对于任意一个节点，左子树和右子树的高度差不能超过1，且平衡二叉树的高度和节点的数量之间的关系一是O(logn)的。我们前面介绍的满二叉树、完全二叉树和线段树都是平衡二叉树，如下图中的...
上篇介绍了AVL树的概述，这篇把AVL树的java代码实现贴出来 public class AVLTree<K extends Comparable<K>, V> {private class Node{public K key;public V value;public Node left, right;public int height; //树的高度public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;height = 1;}}private Node root; //根节点private int size; //元素个数public AVLTree(){root = null;size = 0;...
前面我们介绍了队列这种数据结构，不过我们在前面所介绍的队列只是一种普通的队列，即元素先进先出，其实队列还可以分优先级，优先级高的元素先出，比如操作系统的调度，会将优先级高的任务先调度执行，这种队列就叫做优先队列。 那么优先队列底层该如何实现呢？ 1.优先队列可以使用普通的线性结构，比如动态数组，入队时的时间复杂度为O(1),出队时需要遍历元素，找到优先级最大的元素出队，时间复杂度为O(n)。 2.使用顺序线性结构...
【一】Hash Table（哈希表）& Hash Function（哈希函数）& Collisions（哈希碰撞 / 冲突）Hash Table + Hash FunctionHash Collisions - 拉链法（在同一位置引出链表进行存储）【二】List（列表）vs Map（图）vs Set（集合）- 解释性的数据结构List：list_x = [1, 2, 3, 4] Map：map_x = { ‘jack’ : 100, ‘joyce’ : 90, ‘Eric’ : 80 } Set：set_x = { ‘jack’, ‘joyce’, ‘Eric’ } set_y = { [ ‘jack’, ‘joyce’, ‘...
一、栈的介绍栈作为一种数据结构，是一种只能在一端进行插入和删除操作。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈被使用于非常多的地方，例如浏览器中的后退按钮，文本编辑器中的撤销机制。进栈的时候是1先进，然后是2、3、4、5、6，出栈的时候是先6出，然后是5、4、3、2、1 二、栈中常用的方法 作为一个栈（用stack来表示...
代码中所用到的结构体 typedef struct arcnode {int weight;//边的权重int adjvex;//指向的下一个顶点struct arcnode *next;//指向这个点的另一条边 }Arcnode,*pArcnode;typedef struct vnode {pArcnode firstarc;//点所指向的第一条边 }Vnode,AdjList[30];typedef struct graph {int Vnum,Arcnum;//点的数目，边的数目AdjList vertice; }Graph,*pGraph;typedef struct edges {int begin;//边的一个端点int end;//边的另一个端点in...
一、什么是数据结构 数据结构，直白地理解，就是研究数据的存储方式。我们知道，数据存储只有一个目的，即为了方便后期对数据的再利用，就如同我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的值，因此，数据在计算机存储空间的存放，决不是胡乱的，这就要求我们选择一种好的方式来存储数据，而这也是数据结构的核心内容例如，要存储这样一组数据：{张三，张四，张五，张六，张七}，数据之间具有这样的关系：张三是张四、张五的...
红黑树规则：1、根节点与叶节点都是黑色节点2、每个红色节点的两个子节点都是黑色节点，反之，不做要求，换句话说就是不能有连续两个红色节点3、从根节点到所有叶子节点上的黑色节点数量是相同的 一般对红黑树的讲述都是先给出这样的定义，这样想对不太容易理解的，而在算法4一书中，直接跳过这些规则，而讲述了红黑树与2-3树的等价性 如果我们先了解2-3树，理解了红黑树与2-3树之间的关系，回过头就会发现红黑树不难 2-3树：2-3树...
在前面复习了三个简单排序Java数据结构和算法(三)--三大排序--冒泡、选择、插入排序，属于算法的基础，但是效率是偏低的，所以现在 学习高级排序 希尔排序：希尔排序因为计算机科学家Donald L. Shell而闻名，在插入排序的基础上，增加了一个特性，大大提高插入排序的执行效率忘记插入排序的，可以参考上面的链接 插入排序存在的问题：
本篇主要是<<数据结构和算法-王争>>教程笔记和python实现原理: 在一个有序数组中, 不断比较中间位置的数和目标数的大小, 如果中间位置数比目标数大, 则再用同样办法比较前半部分, 否则比较后半部分. 如果没有找到目标数的位置, 返回None, 否则返回该数的位置. 因为是不断把数组分为一半一半的找, 所以时间复杂度是O(logn). 时间复杂度: O(logn) 实现 注: 要注意边界情况 # coding:utf-8def binary_search(nums, value):low = 0high...