Java数据结构和算法笔记
篇一：Java数据结构和算法笔记
Java数据结构和算法
第0讲 综述
参考教材：Java数据结构和算法（第二版），[美] Robert lafore
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配套
二叉树的各遍历算法：
package com.job.basic;
import java.util.*;
public class BinaryTree {
//递归前序遍历
public void rPreOrder(Node root) {
if (root != null) System.out.print(root.data);
if (root.left != null)rPreOrder(root.left);
if (root.right != null) rPreOrder(root.right);
}
//前序遍历
public void preOrder(Node root) {
ArrayListstack = new ArrayList();// 使用ArrayList作为堆栈int top = -1;// 栈指针
Node current = 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;
}
}
}
// 递归中序遍历
public void rInOrder(Node root) {
if (root != null) {
if (root.left != null) rInOrder(root.left);
System.out.print(root.data);
if (root.right != null) rInOrder(root.right);
}
}
// 中序遍历
public void inOrder(Node root) {
if (root != null) {
ArrayListstack = new ArrayList();
int top = -1;
Node current = 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;
}
}
}
}
// 递归后续遍历
public void rPostOrder(Node root) {
if (root != null) {
if (root.left != null) rPostOrder(root.left);
if (root.right != null)rPostOrder(root.right);
System.out.print(root.data);
}
}
//后序遍历：可以被遍历的节点都要进栈出栈两次，所以添加第二个栈用来标示进栈次数 public void postOrder(Node root) {
if (root != null) {
ArrayListstack1 = new ArrayList();
ArrayListstack2 = new ArrayList();
int top = -1;
int tag;
Node current = 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);
}
}
}
class Node {
public int data;
} public Node right; public Node(int data) { this.data = data; } public Node(int data, Node le, Node ri) { this.data = data; this.left = le; this.right = ri; }
二、排序算法
数据结构排序算法：
package com.job.basic;
import java.util.Arrays;
public class Sort {
public static void main(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); } public static void print(int[] arr) { for (int i : arr) {System.out.print(i + " "); } System.out.println(); } public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 1、简单选择 public static void simpleSelectSort(int[] arr) { int len = arr.length; for (int i = 0; i < len; i++) {int minIndex = i;for (int j = i + 1; j < len; j++) { if (arr[minIndex] > arr[j]) minIndex = j;}if (minIndex != i) swap(arr, minIndex, i); } } // 2、直接插入 public static void Sort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) {int j = 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
1 Java容器类
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.3 List接口
有序的Collection，此接口用户可以对列表中每个元素的插入位置进行精确地控制，用户可以根据元素的整数索引（在列表中的.位置）访问元素，并搜索列表中的元素，与Set不同，列表通常允许重复的元素，更确切地讲，列表通常允许满足e1.equals(e2)的元素对e1和e2，并且如果列表本身允许null元素。其方法主要包括：
//添加
boolean add(E e);
void add(int index, E element);
boolean addAll(Collectionc);
boolean addAll(int index, Collectionc);
//删除
boolean remove(Object o);
E remove(int index);
boolean removeAll(Collection<> c);
//获取某个元素
E get(int index);
//获取某个元素的索引
int indexOf(Object o);
int lastIndexOf(Object o);
//是否相同
boolean equals(Object o);
//将某个元素指定添加到某个位置
E set(int index, E element);
//获取索引范围之内的元素
ListsubList(int fromIndex, int toIndex);
//迭代器
ListIteratorlistIterator();
ListIteratorlistIterator(int index);
(1) ArrayList
底层用数组实现的List，特点，查询效率高，增删效率低，线程不安全。
其扩容算法如下：
int newCapacity = (oldCapacity * 3)/2 + 1;
(2) Vector
底层用数组实现List，其实现方法与ArrayList类似，不同之处在于线程安全。其扩容算法如下： int newCapacity = (capacityIncrement > 0) (oldCapacity+capacityIncrement) : (oldCapacity * 2); capacityIncrement：设置的扩容步进值。
(3) LinkedList
底层采用双向链表实现的List，特点，查询效率低，增删效率高，线程不安全。链表是由若干个称作节点的对象组成的一种数据结构，每个节点含有一个数据和下一个节点对象的引用，或含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用(双向链表)。
LinkedList其实内部采用一个双向链表，如下图所示：
LinkedList继承了抽象的序列链表类，并实现了List、Queue、Cloneable、Serializable接口，使LinkedList可以像队列一样进行操作，同时可以克隆和串化，使其能保存到文件中。
【Java数据结构和算法笔记】相关文章：