Java数据结构和算法笔记

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{

//递归前序遍历 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=roo

t;

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){

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;

}else{

current=stack.get(top);//取出栈顶节点，并继续遍历右子树stack.remove(top--);

System.out.print(current.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;

do{

while(current!=null){//将所有左子节点进栈

stack1.add(current);

stack2.add(1);

top++;

current=current.left;

}

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

current=stack1.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);

}

}

}

classNode{

publicintdata;

}publicNoderight;publicNode(intdata){this.data=data;}publicNode(intdata,Nodele,Noderi){this.data=data;this.left=le;this.right=ri;}

二、排序算法

数据结构排序算法：

packagecom.job.basic;

importjava.util.Arrays;

publicclassSort{

publicstaticvoidmain(String[]args){int[]arrsss={49,38,65,97,76,13,27,14,10};System.out.print("1、简单选择排序：");simpleSelectSort(arrsss);

print(arrsss);int[]arris={49,38,65,97,76,13,27,14,10};System.out.print("2、直接插入排序：");Sort(arris);

print(arris);int[]arrss={49,38,65,97,76,13,27,14,10};System.out.print("3、希尔排序：");

shellSort(arrss);

print(arrss);int[]arrbs={49,38,65,97,76,13,27,14,10};System.out.print("4、冒泡排序：");

bubbleSort(arrbs);

print(arrbs);int[]arrqs={49,38,65,97,76,13,27,14,10};System.out.print("5、快速排序：");quickSort(arrqs,0,arrqs.length-1);print(arrqs);int[]arrhs={49,38,65,97,76,13,27,14,10};System.out.print("6、堆排序：");

heapSort(arrhs);

print(arrhs);int[]arrms={49,38,65,97,76,13,27,14,10};System.out.print("7、归并排序：");

mergeSort(arrms,0,arrms.length-1);

int[]arrmjs={49,38,65,97,76,13,27,14,10};System.out.print("8、基数排序：");jishuSort(arrmjs,10,2);print(arrmjs);}publicstaticvoidprint(int[]arr){for(inti:arr){System.out.print(i+"");}System.out.println();}publicstaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}//1、简单选择publicstaticvoidsimpleSelectSort(int[]arr){intlen=arr.length;for(inti=0;i<len;i++){intminIndex=i;for(intj=i+1;j<len;j++){if(arr[minIndex]>arr[j])minIndex=j;}if(minIndex!=i)swap(arr,minIndex,i);}}//2、直接插入publicstaticvoidSort(int[]arr){intlen=arr.length;for(inti=1;i<len;i++){intj=i-1,temp=arr[i];for(;j>=0;j--){if(arr[j]>temp){arr[j+1]=arr[j];}else{break;}}arr[j+1]=temp;} 篇三：JAVA常用的数据结构和算法

JAVA基本数据结构和排序算法

Email:[emailprotected]

QQ: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.equals(e2)的元素对e1和e2，并且如果列表本身允许null元素。其方法主要包括：

//添加 booleanadd(Ee);

voidadd(intindex,Eelement);

booleanaddAll(Collectionc);

booleanaddAll(intindex,Collectionc);

//删除

booleanremove(Objecto);

Eremove(intindex);

booleanremoveAll(Collection<>c);

//获取某个元素

Eget(intindex);

//获取某个元素的索引

intindexOf(Objecto);

intlastIndexOf(Objecto);

//是否相同

booleanequals(Objecto);