数据结构

一、线索二叉树应用案例应用案例说明：将下面的二叉树，进行中序线索二叉树，中序遍历的数列为}{8,3,10,1,14,6}思路分析：中序遍历的结果：{8,3,10,1,14,6}说明：当线索化二叉树后，Node节点的属性left和right,有如下情况：（1）left:指向的是左子树，也可能是指向的前驱节点。比如①节点left指向的左子树，而⑩节点的left指向的就是前驱节点。（2）right指向的是右子树，也可能是指向后继结点，比如①节点right指向的是右子树，而⑩节点的right指向的是后继节点。代码实现publicclassThreadedBinaryTreeDemo{publicsta

一、基本说明从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，看下面的示意图。要求：（1）上图的二叉树的结点，要求以数组的方式来存放arr:[1,2,3,4,5,6]（2）要求在遍历数组arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历顺序存储二叉树的特点：（1）顺序二叉树通常只考虑完全二叉树（2）第n个元素的左子结点为2*n+1（3）第n个元素的右子节点为2*n+2（4）第n个元素的父节点为(n-1)/2（5）n:表示二叉树中的第几个元素（按0开始编号如图所示）二、顺序存储二叉树遍历需求：给你一个数组{1,2,3,4,5,6,7

要求：（1）请编写前序查找，中序查找和后序查找的方法。（2）并分别使用三种查找方式，查找heroNO=5的节点（3）并分析各种查找方式，分别比较了多少次（4）思路分析图解使用前序，中序，后序的方式来查找指定的结点前序查找思路>>1.1.先判断当前结点的no是否等于要查找的>2.2.如果是相等，则返回当前结点>3.3.如果不等，则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找>4.4.如果左递归前序查找，找到结点，则返回，否则继续判断，当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找。>>中序查找思路>>1.1.判断

要求（1）如果删除的节点是叶子节点，则删除该节点（2）如果删除的节点是非叶子节点，则删除该子树（3）测试，删除掉5号叶子节点和3号子树（4）完全删除思路分析完成删除节点的操作（1）如果删除的节点是叶子节点，则删除该节点（2）如果删除的节点是非叶子节点，则删除该子树思路首先先处理：考虑如果树是空树root,如果只有一个root节点，则等价将二叉树置空//然后进行下面步骤1.因为我们的二叉树的是单向的，所以我们是判断当前结点的子节点需要删除结点，而不能去判断当前这个结点是不是需要删除结点。2.如果当前结点的左子结点不为空，并且左子结点就是删除结点，就将this.left=null;并且就返回结束递

应用实例和说明和思路分析二叉树的前序，中序，后续的遍历步骤1.创建一颗二叉树>>2.2.前序遍历>>2.1先输出当前节点（初始的时候是root节点）>>2.2如果左子节点不为空，则递归继续前序遍历>>2.3如果右子节点不为空，则递归继续前序遍历>>3.3.中序遍历>>3.1如果当前节点的左子节点不为空，则递归中序遍历>>3.2输出当前节点>>3.3如果当前节点的右子节点不为空，则递归中序遍历>>4.4.后序遍历>>4.1如果当前节点的左子节点不为空，则递归后序遍历>&g

一、二叉树1.1为什么需要树这种数据结构（1）数组存储方式的分析优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。缺点：如果要检索具体某个值，或者插入值（按一定顺序）会整体移动，效率较低画出操作示意图：（2）链式存储方式的分析优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好）。缺点：在进行检索时，效率仍然较低，比如（检索某个值，需要从节点开始遍历）操作示意图：（3）树存储方式的分析能提高数据存储，读取的效率，比如利用二叉排序树（BinarySortTree），即可以保证数据的检索速度，同时也可以保证

一、哈希表（散列）（1）看一个实际需求，google公司的一个上机题：（2）有一个公司，当有新的员工来报道时，要求将该员工的信息加入(id,性别,年龄,住址...),当输入该员工的id时，要求查找到该员工的所有信息。（3）要求：不使用数据库，尽量节省内存，速度越快越好=>哈希表（散列）二、哈希表的基本介绍散列表（Hashtable,也叫哈希表），是根据关键码值（Keyvalue）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。三、Google公司的一个上机题有一个公司,当有新的员工来报

一、基本介绍（1）黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不到的效果。（2）菲波那切数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618二、菲波那切（黄金分割法）原理菲波那切查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表菲波那切数列），如下图所示对F(

（1）插值查找原理介绍：插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。（2）将折半查找中的求mid索引的公式，low表示左边索引left,hight表示右边索引right.key就是前面我们讲的findVal（3）intmid=low+(high-low)*(key-arr[low])/(arr[high]-arr[low]);/插值索引/对应前面的代码公式：intmid=left+(right–left)*(findVal–arr[left])/(arr[right]–arr[left])（4）举例说明插值查找算法1-100的数组插值查找算法的举例说明>&g

一、二分查找请对一个有序数组进行二分查找{1,8,10,89,1000,1234},输入一个数看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。二、二分查找算法的思路分析：>>1.1.首先确定该数组的中间的下标>>mid=(left+right)/2>>2.2.然后让需要查找的数findVal和arr[mid]比较>>+findVal>arr[mid]:说明你要查找的数在mid的右边，因此需要递归的向右查找>+findVal<arr[mid]:说明你要查找的数在mid的左边，因此需要递归的向左

相关术语解释：>>1)稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；>>2)不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；>>3)内排序：所有排序操作都在内存中完成；>>4)外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；>>5)时间复杂度：一个算法执行所耗费的时间。>>6)空间复杂度：运行完一个程序所需内存的大小。>>7)n:数据规模>>8)k:“桶”的个数>>9)In-place:不占用额外内存>&g

一、基数排序（桶排序）介绍（1）基数排序（radixsort）属于“分配式排序”(distributionsort),又称"桶子法"(bucketsort)或binsort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用（2）基数排序法是属于稳定性的排序，基数排序法是效率高的稳定性排序法（3）基数排序(RadixSort)是桶排序的扩展（4）基数排序是1887年赫尔曼.何乐礼发明的，它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。二、基数排序基本思想将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，

一、快速排序法介绍快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。二、快速排序法示意图三、快速排序法应用实例要求：对[-9,78,0,23,-567,70]进行从小到大的排序，要求使用快速排序法。【测试8w和800w】说明[验证分析]：（1）如果取消左右递归，结果是-9-5670237870（2）如果取消右递归，结果是-567-90237870（3）如果取消左递归，结果是-9-56

一、归并排序介绍归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）二、归并排序思想示意图1-基本思想三、归并排序思想示意图2-合并相邻有序子序列再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤四、归并排序的应用

一、简单插入排序存在的问题我们看简单的插入排序可能存在的问题.数组arr={2,3,4,5,6,1}这时需要插入的数1(最小),这样的过程是：{2,3,4,5,6,6}{2,3,4,5,5,6}{2,3,4,4,5,6}{2,3,3,4,5,6}{2,2,3,4,5,6}{1,2,3,4,5,6}结论:当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响.二、希尔排序法介绍希尔排序是希尔（DonaldShell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。三、希尔排序法基本思想希尔排序是把记录按下标的一定

一、插入排序介绍插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。二、插入排序法思想插入排序(InsertionSorting)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，元素表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。三、插入排序思路图四、插入排序法应用实例有一群小牛，考试成绩分别是101,34,119,1请从小到大排序代码publicclassInsertSort{publicsta

一、基本介绍选择排序属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。二、选择排序的思想选择排序（selectsorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0]~arr[n-1]中选取最小值，与arr[0]交换，第二次从arr1~arr[n-1]中选取最小值，与arr1交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…,第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过

一、基本介绍冒泡排序(BubbleSorting)的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。优化：因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。二、演示冒泡排序过程冒泡排序规则（1）一共进行数组的大小-1次大的循环（2）每一趟排序的次数在逐渐的减少（3）如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序示例：将五个无序的数：3,

1.排序算法的介绍排序也称排序算法(SortAlgorithm),排序是将一组数据，依指定的顺序进行排序的过程。2.排序的分类：（1）内部排序：指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。（2）外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序。（3）常见的排序算法分类：3.算法的时间复杂度3.1度量一个程序（算法）执行时间的两种方法（1）事后统计的方法这种方法可行,但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素,这种方式，要在同一台计算机的相同状态下运行，才能比较

一、八皇后问题介绍八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。二、八皇后问题算法思路分析（1）第一个皇后先放第一行第一列（2）第二个皇后放在第二行第一列、然后判断是否OK,如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适的（3）继续第三个皇后，还是第一列、第二列......直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解（4）当得到一个正确解时，在栈回退到上一个栈时，就会开

迷宫问题代码实现publicclassMiGong{publicstaticvoidmain(String[]args){//先创建一个二维数组，模拟迷宫//地图int[][]map=newint[8][7];//使用1表示墙//上下全部置为1for(inti=0;i<7;i++){map[0][i]=1;map[7][i]=1;}//左右全部置为1for(inti=0;i<8;i++){map[i][0]=1;map[i][6]=1;}//设置挡板1表示map[3][1]=1;map[3][2]=1;/*map[1][2]=1;map[2][2]=1;*///输出地图System

一、递归应用场景看个实际应用场景，迷宫问题(回溯)，递归(Recursion)二、递归的概念简单的说：递归就是方法自己调用自己，每次调用时传入不同的变量，递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。三、递归调用机制两个递归调用案例：（1）打印问题（2）阶乘问题使用图解方式说明递归调用机制代码示例publicclassRecursionTest{publicstaticvoidmain(String[]args){test(4);intres=factorial(3);System.out.println("res="+res);}//打印问题publicstat

前言大家看到，后缀表达式适合计算机进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将中缀表达式转成后缀表达式。步骤1.初始化两个栈：运算符栈s1和储存中间结果的栈s2;2.从左至右扫描中缀表达式;3.遇到操作数时，将其压s2;4.遇到运算符时，比较其与s1栈顶运算符的优先级;4.1如果s1为空，或栈顶运算符为左括号"(",则直接将此运算符入栈;4.2否则，若优先级比栈顶运算符的高，也将运算符压入s1;4.3否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较;5.遇到括号时：5.1如果是左括号&quot

完成一个逆波兰计算器，要求完成如下任务：（1）输入一个逆波兰表达式（后缀表达式），使用栈(Stack),计算其结果（2）支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。思路分析：例如:(3+4)×5-6对应的后缀表达式就是34+5×6-,针对后缀表达式求值步骤如下:>>(1).从左至右扫描，将3和4压入堆栈；>>(2).遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；>>(3).将5入栈；>>(4).接下来是×运算符，因此弹出5和7，计算出7×5=35

一、前缀表达式（1）前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前（2）举例说明：(3+4)×5-6对应的前缀表达式就是-×+3456前缀表达式的计算机求值从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果例如：(3+4)X5-6对应的前缀表达式就是-X+3456,针对前缀表达式求值步骤如下：1.从右至左扫描，将6、5、4、3压入堆栈2.遇到+运算符，因此弹出3和4(3为栈顶元素，4为次顶元素)，计算出3+4的值，得7，再将7入栈3

使用栈来实现综合计算器思路图解使用栈完成表达式的计算思路通过一个index值（索引），来遍历我们的表达式如果我们发现是一个数字,就直接入数栈如果发现扫描到是一个符号,就分如下情况3.1如果发现当前的符号栈为空，就直接入栈3.2如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈.当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数和符号，并运行.最后在数栈只有一个数字，就是表达式的结果代

一、栈的一个实际需求请输入一个表达式计算式:[7*2*2-5+1-5+3-3]点击计算【如下图】请问:计算机底层是如何运算得到结果的？注意不是简单的把算式列出运算,因为我们看这个算式7*2*2-5,但是计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)，我们讨论的是这个问题**。->**栈二、栈的介绍（1）栈的英文为(stack)>>（2）栈是一个先入后出(FILO-FirstInLastOut)的有序列表。>>（3）栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶

一、单向环形链表的应用场景Josephu(约瑟夫、约瑟夫环)问题Josephu问题为：设编号为1，2，…n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。提示：用一个不带头结点的循环链表来处理Josephu问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。二、单向环形链表介绍三、Josephu问题约瑟夫问题的

一、管理单向链表的缺点分析（1）单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找（2）单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们在单链表删除节点时，总是找到temp,temp是待删除节点的前一个节点二、双向链表如何完成遍历，添加，修改和删除示意图思路：>>1.1.遍历方法和单链表一样，只是可以向前，也可以向后查找>>2.2.添加（默认添加到双向链表的最后）>>+先找到双向链表的最后这个节点>>+temp.next=newHeroNode>>+newHeroNode.pre=temp

前言本篇将讲述之前新浪、百度、腾讯的单链表的面试题单链表面试题（1）求单链表中有效节点的个数代码//方法：获取到单链表的节点的个数（如果是带头节点的链表，需求不统计头节点）publicstaticintgetLength(HeroNodehead){if(head.next==null){//空链表return0;}intlength=0;//定义一个辅助的变量，这里我们没有统计头节点HeroNodecur=head.next;while(cur!=null){length++;cur=cur.next;//遍历}returnlength;}需在SingleLinkedList.class类中