Java数据结构和算法笔记

1、Java 数据结构和算法笔记篇一： Java 数据结构和算法笔记Java 数据结构和算法第 0 讲综述参考教材：Java数据结构和算法（第二版），美Robertlafore1. 数据结构的特性数据结构数组有序数组栈队列链表二叉树红 - 黑树 2-3-4 树哈希表堆图优点比无序的数组查找快提供后进先出方式的存取提供先进先出方式的存取插入快，删除快查找、 插入、 删除都快； 树总是平衡的查找、 插入、 删除都快；树总是平衡的；类似的树对磁盘存储有用如果关键字已知，则存储极快；插入快插入、删除快；对大数据项的存取很快对现实世界建模缺点删除和插入慢，大小固定存取其他项很慢存取其他项很慢查找慢算法复杂算法复杂删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分对其他数据项存取慢有些算法慢且复杂插入快；如果知道下标，可以非常快地存取查找慢，删除慢，大小固定查找、插入、删除都快（如果树保持平衡）删除算法复杂2. 经典算法总结查找算法：线性查找和二分查找排序算法：用表展示第一讲数组1 .Java 中数组的基础知识2 ）创建数组在 Java 中把数组当作对象来对待， 因此在创建数组时必须使用new操

2、作符：一旦创建数组，数组大小便不可改变。3 ）访问数组数据项数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：4 ）数组的初始化当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的 null 对象。2. 面向对象编程方式1 ）使用自定义的类封装数组2 ）添加类方法实现数据操作测试 MyArray 类方法：3. 有序数组1 ）有序数组简介以及其优点有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素。 有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。2 ）构建有序数组将 2.1 中自定义的类封装数组MyArray 的方法改为如下：4. 查找算法1 ）线性查找在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1 中自定义的类封装数组MyArray 的queryByValue 方法，使用的就是线性查找。2 ）二分查找二分查找 （又称折半查找） ， 即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较： 如果要查找的数中间数，则表明该数在数组的后半段； 如果要查的数=中

3、间数，则返回中间数。测试该二分查找方法：篇二：数据结构面试中常见算法小结一、二叉树遍历思想：1 、非递归前序遍历List 作栈， top 为栈针While 循环当前点非空，输出右子非空，入栈左子非空，入栈栈非空，栈顶为当前点，出栈；否则 break2 、非递归中序遍历List 作栈， top 为栈针While 循环（但前点非空或栈非空）当前点非空，入栈，左子为当前点；否则，栈顶为当前点，出栈；输出，右子为当前点3 、非递归后序遍历List1 作数据栈， list2 作标识栈， top 为数据栈针， tag 为标识作判断用Do 循环While 循环 （ 当前点非空）入数据栈，标识栈对应设1 ；左子为当前点。（本内循环相当于把所有左子入栈）数据栈顶为当前点，标识栈顶为 tag 且出栈Tag 为 1 ，数字 2 进标识栈，右子为当前点否则为2 ，数据栈出栈顶，输出，当前点为null ；While （当前点非空或数据栈非空） - 与 do 配套二叉树的各遍历算法：package.job.basic;importjava.util.*;publicclassBinaryTree/ 递归前序遍历p

4、ublicvoidrPreOrder(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.

5、remove(top-);elsebreak;/ 递归中序遍历publicvoidrInOrder(Noderoot)if(root!=null)if(root.left!=null)rInOrder(root.left);System.out.print(root.data);if(root.right!=null)rInOrder(root.right);/ 中序遍历publicvoidinOrder(Noderoot)if(root!=null)ArrayListstack=newArrayList();inttop=-1;Nodecurrent=root;while(current!=null|top-1)/ 一直寻找左孩子，将路上节点都进栈, 如果左孩子为 null ，返回父节点，再从右孩子找if(current!=null)stack.add(current);top+;current=current.left;elsecurrent=stack.get(top);/ 取出栈顶节点， 并继续遍历右子树stack.remove(top-);System.out.print(c

6、urrent.data);current=current.right;/ 递归后续遍历publicvoidrPostOrder(Noderoot)if(root!=null)if(root.left!=null)rPostOrder(root.left);if(root.right!=null)rPostOrder(root.right);System.out.print(root.data);/ 后序遍历：可以被遍历的节点都要进栈出栈两次，所以添加第二个栈用来标示进栈次数publicvoidpostOrder(Noderoot)if(root!=null)ArrayListstack1=newArrayList();ArrayListstack2=newArrayList();inttop=-1;inttag;Nodecurrent=root;dowhile(current!=null)/将所有左子节点进栈stack1.add(current);stack2.add(1);top+;current=current.left;/ 取出栈顶节点，并判断其标志位current=stack1

7、.get(top);tag=stack2.get(top);stack2.remove(top);if(tag=1)/tag 为 1, 表明该节点第一次进栈，还需要进栈一次，同时修改标志位 current=current.right;stack2.add(2);else/tag 不位 0, 表明非首次进栈，可以遍历了。stack1.remove(top);top-;System.out.print(current.data);current=null;while(current!=null|top!=-1);classNodepublicintdata;publicNoderight;publicNode(intdata)this.data=data;publicNode(intdata,Nodele,Noderi)this.data=data;this.left=l e;this.right=ri;二、排序算法数据结构排序算法：package.job.basic;importjava.util.Arrays;publicclassSortpublicstaticvoidmain(St

8、ringargs) intarrsss=49,38,65,97,76,13,27,14,10;System.out.print(1、简单选择排序： );simpleSelectSort(arrsss);print(arrsss);intarris=49,38,65,97,76,13,27,14,10;System.out.print(2直接插入排序： );Sort(arris);print(arris);intarrss=49,38,65,97,76,13,27,14,10;System.out.print(3希尔排序： );shellSort(arrss);print(arrss);intarrbs=49,38,65,97,76,13,27,14,10;System.out.print(4冒泡排序： );bubbleSort(arrbs);print(arrbs);intarrqs=49,38,65,97,76,13,27,14,10;System.out.print(5快速排序： );quickSort(arrqs,0,arrqs.length-1);print(arrqs);intarrhs=49,38,65,97,76,13,27,14,10;System.out.print(6堆排序： );heapSort(arrhs);print(arrhs);intarrms=49,38,65,97,76,13,27,14,10;System.out.print(7归并排序： );mergeSort(arrms,0,arrms.length-1);intarrmjs=49,38,65,97,76,13,27,14,10;System.out.print(8、基数排序：);jishuSort(arrmjs,10,2);print(arrmjs);publicstaticvoidprint(intarr)for(inti:arr)System.out.print(i+);System.out.println();publicstaticvoidswap(int

《Java数据结构和算法笔记》由会员鲁**分享，可在线阅读，更多相关《Java数据结构和算法笔记》请在金锄头文库上搜索。