第0讲 综述
参考教材：java数据结构和算法（第二版），[美] robert lafore
数据结构 数组 有序数组 栈 队列 链表 二叉树 红-黑树 2-3-4树 哈希表 堆 图
优点
比无序的数组查找快 提供后进先出方式的存取 提供先进先出方式的存取 插入快，删除快
查找、插入、删除都快；树总是平衡的 查找、插入、删除都快；树总是平衡的；类似的树对磁盘存储有用
如果关键字已知，则存储极快；插入快 插入、删除快；对大数据项的存取很快 对现实世界建模
缺点
删除和插入慢，大小固定 存取其他项很慢 存取其他项很慢 查找慢 算法复杂 算法复杂
删除慢，如果不知道关键字则存储很慢，对存储空间使用不充分 对其他数据项存取慢 有些算法慢且复杂
插入快；如果知道下标，可以非常快地存取 查找慢，删除慢，大小固定
查找、插入、删除都快（如果树保持平衡） 删除算法复杂
查找算法：线性查找和二分查找 排序算法： 用表展示
第一讲 数组
1. java中数组的基础知识
1）创建数组
在java中把数组当作对象来对待，因此在创建数组时必须使用new操作符：
一旦创建数组，数组大小便不可改变。
2）访问数组数据项
数组数据项通过方括号中的下标来访问，其中第一个数据项的下标是0：
3）数组的初始化
当创建数组之后，除非将特定的值赋给数组的数据项，否则它们一直是特殊的null对象。
1）使用自定义的类封装数组
2）添加类方法实现数据操作
测试myarray类方法：
1）有序数组简介以及其优点
有序数组是一种数组元素按一定的顺序排列的数组，从而方便使用二分查找来查找数组中特定的元素。有序数组提高了查询的效率，但并没有提高删除和插入元素的效率。
2）构建有序数组
将2.1中自定义的类封装数组myarray的方法改为如下：
4. 查找算法
1）线性查找
在查找过程中，将要查找的数一个一个地与数组中的数据项比较，直到找到要找的数。在2.1中自定义的类封装数组myarray的querybyvalue方法，使用的就是线性查找。
2）二分查找
二分查找（又称折半查找），即不断将有序数组进行对半分割，每次拿中间位置的数和要查找的数进行比较：如果要查找的数<中间数，则表明要查的数在数组的前半段；如果要查的数>中间数，则表明该数在数组的后半段；如果要查的数=中间数，则返回中间数。
测试该二分查找方法：
一、二叉树遍历思想：
list作栈，top为栈针
while循环
当前点非空，输出
右子非空，入栈
左子非空，入栈
栈非空，栈顶为当前点，出栈；否则break
list作栈，top为栈针
while循环（但前点非空 或 栈非空）
当前点非空，入栈，左子为当前点；
否则，栈顶为当前点，出栈；输出，右子为当前点
list1作数据栈，list2作标识栈，top为数据栈针，tag为标识作判断用
do循环
while循环(当前点非空)
入数据栈，标识栈对应设1；左子为当前点。（本内循环相当于把所有左子入栈）数据栈顶为当前点，标识栈顶为tag且出栈
tag为1，数字2进标识栈，右子为当前点
否则为2，数据栈出栈顶，输出，当前点为null；
while（当前点非空 或 数据栈非空）---与do配套
二叉树的各遍历算法：
package ;
import .*;
public class binarytree {
//递归前序遍历
public void rpreorder(node root) {
if (root != null) ();
if ( != null)rpreorder();
if ( != null) rpreorder();
}
//前序遍历
public void preorder(node root) {
arrayliststack = new arraylist();// 使用arraylist作为堆栈int top = -1;// 栈指针
node current = roo
t;
while (true) {
if (current != null) ();
// 右子节点进栈
if ( != null) {
();
top++;
}
// 左子节点进栈
if ( != null) {
();
top++;
}
// 如果栈内还有节点，栈顶节点出栈
if (top > -1) {
current = (top);
(top--);
} else {
break;
}
}
}
// 递归中序遍历
public void rinorder(node root) {
if (root != null) {
if ( != null) rinorder();
();
if ( != null) rinorder();
}
}
// 中序遍历
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) {
(current);
top++;
current = ;
} else {
current = (top);// 取出栈顶节点，并继续遍历右子树(top--);
();
current = ;
}
}
}
}
// 递归后续遍历
public void rpostorder(node root) {
if (root != null) {
if ( != null) rpostorder();
if ( != null)rpostorder();
();
}
}
//后序遍历：可以被遍历的节点都要进栈出栈两次，所以添加第二个栈用来标示进栈次数 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) { //将所有左子节点进栈
(current);
(1);
top++;
current = ;
}
//取出栈顶节点，并判断其标志位
current = (top);
tag = (top);
(top);
if (tag == 1) {
// tag为1,表明该节点第一次进栈，还需要进栈一次，同时修改标志位current = ;
(2);
} else {
// tag不位0,表明非首次进栈，可以遍历了。
(top);
top--;
();
current = null;
}
} while (current != null || top != -1);
}
}
}
class node {
public int data;
} public node right; public node(int data) { = data; } public node(int data, node le, node ri) { = data; = le; = ri; }
二、排序算法
数据结构排序算法：
package ;
import .arrays;
public class sort {
public static void main(string[] args) {
int[] arrsss = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };("1、简单选择排序：");
simpleselectsort(arrsss);
print(arrsss);
int[] arris = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };("2、直接插入排序：");
sort(arris);
print(arris);
int[] arrss = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };("3、希尔排序：");
shellsort(arrss);
print(arrss);
int[] arrbs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };("4、冒泡排序：");
bubblesort(arrbs);
print(arrbs);
int[] arrqs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };("5、快速排序：");
quicksort(arrqs, 0, - 1);
print(arrqs);
int[] arrhs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };("6、堆排序：");
heapsort(arrhs);
print(arrhs);
int[] arrms = { 49, 38, 65, 97, 76, 13, 27, 14, 10 };("7、归并排序：");
mergesort(arrms, 0, - 1);
int[] arrmjs = { 49, 38, 65, 97, 76, 13, 27, 14, 10 }; ("8、基数排序："); jishusort(arrmjs, 10, 2); print(arrmjs); } public static void print(int[] arr) { for (int i : arr) {(i + " "); } n(); } 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 = ; 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 = ; 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数据结构和算法书精选
文件夹