Java数据结构和算法笔记.docx

Java数据结构和算法笔记

篇一：Java数据结构和算法笔记Java数据结构和算法第0讲综述参考教材：Java数据结构和算法（第二版），[美]Robertlafore1.数据结构的特性数据结构数组有序数组栈队列链表二叉树红-黑树2-3-4树哈希表堆图优点比无序的数组查找快提供后进先出方式的存取提供先进先出方式的存取插入快，删除快查找、插入、删除都快；树总是平衡的查找、插入、删除都快；树总是平衡的；类似的树对磁盘存储有用如果关键字已知，则存储极快；插入快插入、删除快；对大数据项的存取很快对现实世界建模缺点删除和插入慢，大小固定存取其他项很慢存取其他项很慢查找慢算法复杂算法复杂删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分对其他数据项存取慢有些算法慢且复杂插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定查找、插入、删除都快（如果树保持平衡）删除算法复杂2.经典算法总结查找算法：线性查找和二分查找排序算法：用表展示第一讲数组1.Java中数组的基础知识1）创建数组在Java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：一旦创建数组，数组大小便不可改变。2）访问数组数据项数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：3）数组的初始化当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。2.面向对象编程方式1）使用自定义的类封装数组2）添加类方法实现数据操作测试MyArray类方法：3.有序数组1）有序数组简介以及其优点有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素。有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。2）构建有序数组将2.1中自定义的类封装数组MyArray的方法改为如下：4.查找算法1）线性查找在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1中自定义的类封装数组MyArray的queryByValue方法，使用的就是线性查找。2）二分查找二分查找（又称折半查找），即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较：如果要查找的数中间数，则表明该数在数组的后半段；如果要查的数=中间数，则返回中间数。测试该二分查找方法：篇二：数据结构面试中常见算法小结一、二叉树遍历思想：1、非递归前序遍历List作栈，top为栈针While循环当前点非空，输出右子非空，入栈左子非空，入栈栈非空，栈顶为当前点，出栈；否则break2、非递归中序遍历List作栈，top为栈针While循环（但前点非空或栈非空）当前点非空，入栈，左子为当前点；否则，栈顶为当前点，出栈；输出，右子为当前点3、非递归后序遍历List1作数据栈，list2作标识栈，top为数据栈针，tag为标识作判断用Do循环While循环(当前点非空)入数据栈，标识栈对应设1；左子为当前点。（本内循环相当于把所有左子入栈）数据栈顶为当前点，标识栈顶为tag且出栈Tag为1，数字2进标识栈，右子为当前点否则为2，数据栈出栈顶，输出，当前点为null；While（当前点非空或数据栈非空）---与do配套二叉树的各遍历算法：packagecom.job.basic;importjava.util.*;publicclassBinaryTree{//递归前序遍历publicvoidrPreOrder(Noderoot){if(root!=null)System.out.print(root.data);if(root.left!=null)rPreOrder(root.left);if(root.right!=null)rPreOrder(root.right);}//前序遍历publicvoidpreOrder(Noderoot){ArrayListstack=newArrayList();//使用ArrayList作为堆栈inttop=-1;//栈指针Nodecurrent=root;while(true){if(current!=null)System.out.print(current.data);//右子节点进栈if(current.right!=null){stack.add(current.right);top++;}//左子节点进栈if(current.left!=null){stack.add(current.left);top++;}//如果栈内还有节点，栈顶节点出栈if(top>-1){current=stack.get(top);stack.remove(top--);}else{break;}}}//递归中序遍历publicvoidrInOrder(Noderoot){i