线性结构与非线性结构 数据结构包括：线性结构和非线性结构。 线性结构 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系 线性结构有两种不同的存储结构，即顺序存储结构(数组)和链式存储结构(链表)。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续(地址连续)的 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息 线性结构常见的有：数组、队列、链表和栈 非线性结构非线性结构包括：二维数组，多维数组，广义表，树结构，图结构 稀疏数组当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。 稀疏数组的处理方法是: 记录数组一共有几行几列，有多少个不同的值 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模 二维数组转稀疏数组的思路： 遍历原始的二维数组，得到有效数据的个数sum 根据sum就可以创建稀疏数组sparseArr int[sum+1][3] 将二维数组的有效数据存入到稀疏数组 稀疏数组转原始的二维数组的思路： 先读取稀疏数组的第一行，根据第一行 ...

图图基本介绍为什么要有图 前面我们学了线性表和树 线性表局限于一个直接前驱和一个直接后继的关系 树也只能有一个直接前驱也就是父节点 当我们需要表示多对多的关系时， 这里我们就用到了图 图的举例说明图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图： 图的常用概念 1)顶点(vertex) 2)边(edge) 3)路径 4)无向图(上图) 5)有向图 6)带权图 无向图： 顶点之间的连接没有方向，比如A-B, 即可以是 A-> B 也可以 B->A . 路径: 比如从 D -> C 的路径有 D->B->C D->A->B->C 图的表示方式图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。 邻接矩阵邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1….n个点。 邻接表1)邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失. 2)邻接表的实现只关心存在的边，不关心不存在的边。 ...

双向链表双向链表使用带head头的双向链表实现——水浒英雄排行榜 管理单向链表的缺点分析： 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找 单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，前面单链表删除节点时，总是找到temp，temp时待删除节点的前一个节点 分析双向链表的遍历，添加，修改，删除的操作思想 遍历方式和单链表一样，只是可以向前，也可以向后查找 添加（默认添加到双向链表的最后） 先找到双向链表的最后这个节点 temp.next=newHeroNode newHeroNode.pre=temp 修改思路和单向链表一样 删除 因为是双向链表，因此可以实现自我删除某个节点 直接找到要删除的节点 temp.pre.next=temp.next temp.next.pre=temp.pre 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556 ...

树二叉树为什么需要树这种数据结构 数组存储方式的分析 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 [示意图] 链式存储方式的分析 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。 缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 树存储方式的分析 能提高数据存储，读取的效率, 比如利用 **二叉排序树(Binary Sort Tree)**，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。 树示意图** 树的常用术语(结合示意图理解): 节点 根节点 父节点 子节点 叶子节点 (没有子节点的节点) 节点的权(节点值) 路径(从root节点找到该节点的路线) 层 子树 树的高度(最大层数) 森林 :多颗子树构成森林 二叉树的概念 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。 二叉树的子节点分为左节点和右节点。 如果 ...

十大算法二分查找算法（非递归）二分查找算法(非递归)介绍 前面我们讲过了二分查找算法，是使用递归的方式，下面我们讲解二分查找算法的非递归方式 二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找 二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7) 二分查找算法(非递归)代码实现数组 {1,3, 8, 10, 11, 67, 100}, 编程实现二分查找， 要求使用非递归的方式完成. 12345678910111213141516171819202122232425262728293031323334public class BinarySearchNoRecur { public static void main(String[] args) { //测试 int[] arr =
...

排序算法排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。 排序的分类： 内部排序: 指将需要处理的所有数据都加载到内部存储器中进行排序。 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。 常见的排序算法分类 算法的时间复杂度度量一个程序（算法）执行的时间的两种方法 事后统计的方法这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, *这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法*速度更快**。 事前估算的方法通过分析某个算法的时间复杂度来判断哪个算法更优. 时间频度时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 例：计算1-100所有数字之和 `````int total=0;int end=100;for(int i ...

哈希表哈希表的基本介绍散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。15 111 % 15 google公司的一个上机题:有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的id时,要求查找到该员工的 所有信息. 要求:不使用数据库,,速度越快越好=>哈希表(散列)添加时，保证按照id从低到高插入 [课后思考：如果id不是从低到高插入，但要求各条链表仍是从低到高，怎么解决?]使用链表来实现哈希表, 该链表不带表头[即: 链表的第一个结点就存放雇员信息]思路分析并画出示意图代码实现[增删改查(显示所有员工，按id查询)]

递归递归需要遵循的重要规则 执行一个方法时，就创建一个新的受保护的独立空间（栈空间） 方法的局部变量是独立的，不会相互影响 如果方法中使用的是引用类型变量（数组），就会共享该引用类型的数据 递归必须向退出递归的条件逼近，否则就是无限递归，死龟了 当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕 递归-迷宫问题12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970public class MiGong { public static void main(String[] args) { //先创建一个二维数组，模拟迷宫地图 int[][] map=new int[8][7]; //使用1表示墙 //上下全部置为1 ...

单向环形链表单向环形链表Josephu（约瑟夫）问题Josephu问题为：设编号为1,2,3，…，n的n个人围坐在一全圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，以此类推，直到所有人出列为止，由此产生一个出队编号的序列 提示：用一个不带头节点的循环链表来处理Josephu问题：先构成一个有n个节点单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后再从被删除的节点的下一个节点又从1开始计数，直到最后一个节点从链表中删除，算法结束 构建一个单向环形链表思路 先构建第一个节点，让first指向该节点，并形成环形 后面当我们每创建一个节点，就把该节点，加入到已有的环形链表中即可 遍历该环形链表 先让一个辅助指针（变量）curBoy，指向first节点 然后通过一个while循环遍历该环形链表即可，curBoy.next=first结束 出圈思路 需要创建一个辅助指针（变量）helper，事先应该指向环形链表的最后这个节点 补充：小孩报数前，先让fi ...