Java数据结构和算法笔记

本文格式为Word版，下载可任意编辑——Java数据结构和算法笔记Java数据布局和算法笔记

篇一：Java数据布局和算法笔记

Java数据布局和算法

第0讲综述

参考教材：Java数据布局和算法（其次版），[美]Robertlafore

1.数据布局的特性

数据布局数组有序数组栈队列链表二叉树红-黑树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循环

当前点非空，输出

右子非空，入栈

左子非空，入栈

栈非空，栈顶为当前点，出栈；否那么break

2、非递归中序遍历

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

//递归前序遍历

publicvoidrPreOrderNoderoot

ifroot!=nullSystem.out.printroot.data;

ifroot.left!=nullrPreOrderroot.left;

ifroot.right!=nullrPreOrderroot.right;

//前序遍历

publicvoidpreOrderNoderoot

ArrayListstack=newArrayList;//使用ArrayList作为堆栈inttop=-1;//栈指针

Nodecurrent=roo

t;

whiletrue

ifcurrent!=nullSystem.out.printcurrent.data;

//右子节点进栈

ifcurrent.right!=null

stack.addcurrent.right;

top++;

//左子节点进栈

ifcurrent.left!=null

stack.addcurrent.left;

top++;

//假设栈内还有节点，栈顶节点出栈

iftop-1

current=stack.gettop;

stack.removetop--;

else

break;

//递归中序遍历

publicvoidrInOrderNoderoot

ifroot!=null

ifroot.left!=nullrInOrderroot.left;

System.out.printroot.data;

ifroot.right!=nullrInOrderroot.right;

//中序遍历

publicvoidinOrderNoderoot

ifroot!=null

ArrayListstack=newArrayList;

inttop=-1;

Nodecurrent=root;

whilecurrent!=null||top-1

//一向探索左孩子，将路上节点都进栈,假设左孩子为null，返回父节点，再从右孩子找ifcurrent!=null

stack.addcurrent;

top++;

current=current.left;

else

current=stack.gettop;//取出栈顶节点，并持续遍历右子树stack.removetop--;

System.out.printcurrent.data;

current=current.right;

//递归后续遍历

publicvoidrPostOrderNoderoot

ifroot!=null

ifroot.left!=nullrPostOrderroot.left;

ifroot.right!=nullrPostOrderroot.right;

System.out.printroot.data;

//后序遍历：可以被遍历的节点都要进栈出栈两次，所以添加其次个栈用来标示进栈次数publicvoidpostOrderNoderoot

ifroot!=null

ArrayListstack1=newArrayList;

ArrayListstack2=newArrayList;

inttop=-1;

inttag;

Nodecurrent=root;

do

whilecurrent!=null//将全体左子节点进栈

stack1.addcurrent;

stack2.add1;

top++;

current=current.left;

//取出栈顶节点，并判断其标志位

current=stack1.gettop;

tag=stack2.gettop;

stack2.removetop;

iftag==1

//tag为1,说明该节点第一次进栈，还需要进栈一次，同时修改标志位current=current.right;

stack2.add2;

else

//tag不位0,说明非首次进栈，可以遍历了。

stack1.removetop;

top--;

System.out.printcurrent.data;

current=null;

whilecurrent!=null||top!=-1;

classNode

publicintdata;

publicNoderight;publicNodeintdatathis.data=data;publicNodeintdata,Nodele,Noderithis.data=data;this.left=le;this.right=ri;

二、排序算法

数据布局排序算法：

packagecom.job.basic;

importjava.util.Arrays;

publicclassSort

publicstaticvoidmainString[]args

int[]arrsss=49,38,65,97,76,13,27,14,10;System.out.print1、简朴选择排序：;

simpleSelectSortarrsss;

printarrsss;

int[]arris=49,38,65,97,76,13,27,14,10;System.out.print2、直接插入排序：;

Sortarris;

printarris;

int[]arrss=49,38,65,97,76,13,27,14,10;System.out.print3、希尔排序：;

shellSortarrss;

printarrss;

int[]arrbs=49,38,65,97,76,13,27,14,10;System.out.print4、冒泡排序：;

bubbleSortarrbs;

printarrbs;

int[]arrqs=49,38,65,97,76,13,27,14,10;System.out.print5、快速排序：;

quickSortarrqs,0,arrqs.length-1;

printarrqs;

int[]arrhs=49,38,65,97,76,13,27,14,10;System.out.print6、堆排序：;

heapSortarrhs;

printarrhs;

int[]arrms=49,38,65,97,76,13,27,14,10;System.out.print7、归并排序：;

mergeSortarrms,0,arrms.length-1;

int[]arrmjs=49,38,65,97,76,13,27,14,10;System.out.print8、基数排序：;jishuSortarrmjs,10,2;printarrmjs;publicstaticvoidprintint[]arrforinti:arrSystem.out.printi+;System.out.println;publicstaticvoidswapint[]arr,inti,intjinttemp=arr[i];arr[i]=arr[j];arr[j]=temp;//1、简朴选择publicstaticvoidsimpleSelectSortint[]arrintlen=arr.length;forinti=0;ilen;i++intminIndex=i;forintj=i+1;jlen;j++ifarr[minIndex]arr[j]minIndex=j;ifminIndex!=iswaparr,minIndex,i;//2、直接插入publicstaticvoidSortint[]arrintlen=arr.length;forinti=1;ilen;i++intj=i-1,temp=arr[i];for;j=0;j--ifarr[j]temparr[j+1]=arr[j];elsebreak;arr[j+1]=temp;

篇三：JAVA常用的数据布局和算法

JAVA根本数据布局和排序算法

Email:[emailprotected]

:448086006

1Java容器类

1.1容器作用和概念

1.1.1数组

数组是一种容器，以线性序列放置对象和根本类型数据，可快速访问数组元素，但不生动，容量务必事先定义好，不能随着需求的变化而扩容。基于此JAVA中供给容器类。

1.1.2容器的架构

其层次如下图，都是从Object派生而来。需要留神的是Set、List、Collcetion和Map都是接口，不是概括的类实现。

在Java中供给了Collection和Map接口。其中List和Set继承了Collection接口；同时用Vector、ArrayList、LinkedList三个类实现List接口，HashSet、TreeSet实现Set接口。直接有HashTable、HashMap、TreeMap实现Map接口。

List和set都是放单独的对象的，map那么是方一个名值对，就是通过一个key找到一个value；list存放东西是有序的，set是没有依次的;list允许重复存入，set不成以。

1.1.3List接口

有序的Collection，此接口用户可以对列表中每个元素的插入位置举行精确地操纵，用户可以根据元素的整数索引（在列表中的位置）访问元素，并探寻列表中的元素，与Set不同，列表通常允许重复的元素，更切当地讲，列表通常允许得志e1.equalse2的元素对e1和e2，并且假设列表本身允许null元素。其方法主要包括：

//添加

booleanaddEe;

voidaddintindex,Eelement;

booleanaddAllCollectionc;

booleanaddAllintindex,Collectionc;

//删除

booleanremoveObjecto;

Eremoveintindex;

booleanremoveAllCollectionc;

//获取某个元素

Egetintindex;

//获取某个元素的索引

intindexOfObjecto;

intlastIndexOfObjecto;

//是否一致

bool