空间复杂度
案例：指定的数组进行反转，并返回反转的内容
解法一：
public static int[] reverse1(int[] arr) {
int n = arr.length; //申请4个字节
int temp; //申请4个字节
for (int start = 0, end = n - 1; start <= end; start++, end--) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
return arr;}解法二：
public static int[] reverse2(int[] arr) {
int n = arr.length; //申请4个字节
int[] temp = new int[n]; //申请n*4个字节+数组自身头信息开销24个字节
for (int i = n - 1; i >= 0; i--) {
temp[n - 1 - i] = arr[i];
}
return temp;}根据大O推导法则，算法一的空间复杂度为0(1),算法二的空间复杂度为0(n)，所以从空间占用的角度讲，算法一要优于算法二。
由于java中有内存垃圾回收机制，并且jvm对程序的内存占用也有优化(例如即时编译) , 我们无法精确的评估一个java程序的内存占用情况，但是了解了java的基本内存占用，使我们可以对java程序的内存占用情况进行估算。
由于现在的计算机设备内存一般都比较大，基本上个人计算机都是4G起步，大的可以达到32G ，所以内存占用一般情况下并不是我们算法的瓶颈，普通情况下直接说复杂度，默认为算法的时间复杂度。
但是，如果你做的程序是嵌入式开发，尤其是一些传感器设备上的内置程序,由于这些设备的内存很小, 一般为几kb，这个时候对算法的空间复杂度就有要求了，但是一般做java开发的，基本上都是服务器开发, 一般不存在这样的问题。
第2章 数组
2.1 数组概念
数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。这里我们要抽取出三个跟数组相关的关键词：线性表，连续内存空间，相同数据类型；数组具有连续的内存空间，存储相同类型的数据，正是该特性使得数组具有一个特性：随机访问。但是有利有弊，这个特性虽然使得访问数组边得非常容易，但是也使得数组插入和删除操作会变得很低效，插入和删除数据后为了保证连续性,要做很多数据搬迁工作。
查找数组中的方法有两种：
线性查找：线性查找就是简单的查找数组中的元素
二分法查找：二分法查找要求目标数组必须是有序的。
2.2 无序数组
public class MyArray {
//声明一个数组
private long[] arr;
//有效数据的长度
private int elements;
//无参构造函数，默认长度为50
public MyArray(){
arr = new long[50];
}
public MyArray(int maxsize){
arr = new long[maxsize];
}
//添加数据
public void insert(long value){
arr[elements] = value;
elements++;
}
//显示数据
public void display(){
System.out.print("[");
for(int i = 0;i < elements;i++){
System.out.print(arr[i] + " ");
}
System.out.println("]");
}
//根据下标查找数据
public long get(int index){
if(index >= elements || index < 0){
throw new ArrayIndexOutOfBoundsException();
}else{
return arr[index];
}
}
/**
* 根据值查询
* @param value 需要被查询的值
* @return 被查询值的下标
*/
public int search(int value){
//声明一个变量i用来记录该数据的下标值
int i ;
for(i = 0;i < elements;i++){
if(value == arr[i]){
break;
}
}
//如果查询到最后一个元素依然没有找到
if(i == elements){
return -1;
}else{
return i;
}
}
//根据下标删除数据
public void delete(int index){
if(index >= elements || index < 0){
throw new ArrayIndexOutOfBoundsException();
}else{
//删除该元素后，后面所有元素前移一位
for(int i = index; i < elements;i++){
arr[i] = arr[i+1];
}
elements--;
}
}
/**
* 替换数据
* @param index 被替换的下标
* @param newvalue 新的数据
*/
public void change(int index,int newvalue){
if(index >= elements || index < 0){
throw new ArrayIndexOutOfBoundsException();
}else{
arr[index] = newvalue;
}
} }2.3 有序数组
public class MyOrderArray {
private long[] arr;
private int elements;
public MyOrderArray(){
arr = new long[50];
}
public MyOrderArray(int maxsize){
arr = new long[maxsize];
}
//添加数据
public void insert(int value){
int i;
for(i = 0;i < elements;i++){
if(arr[i] > value){
break;
}
}
for(int j = elements;j > i;j--){
arr[j] = arr[j -1];
}
arr[i] = value;
elements++;
}
//删除数据
public void delete(int index){
if(index >=elements || index <0){
throw new ArrayIndexOutOfBoundsException();
}else{
for(int i = index;i < elements; i++){
arr[i] = arr[i+1];
}
elements--;
}
}
//修改数据
public void change(int index,int value){
if(index >= elements || index < 0){
throw new IndexOutOfBoundsException();
}else{
arr[index] = value;
}
}
//根据下标查询数据
public long get(int index){
if(index >= elements || index < 0){
throw new IndexOutOfBoundsException();
}else{
return arr[index];
}
}
//展示数据
public void display(){
System.out.print("[");
for(int i = 0; i < elements;i++){
System.out.print(arr[i] + " ");
}
System.out.println("]");
}
//二分法查找数据
public int binarySearch(long value){
//声明三个指针分别指向数组的头，尾，中间
int low = 0;
int pow = elements;
int middle = 0;
while(true){
middle = (low + pow) / 2;
//如果中指针所指的值等于带查询数
if(arr[middle] == value){
return middle;
}else if(low > pow){
return -1;
}else{
if(arr[middle] > value){
//待查询的数在左边,右指针重新改变指向
pow = middle-1;
}else{
//带查询的数在右边，左指针重新改变指向
low = middle +1;
}
}
}
}}优点：查询快（时间复杂度为：O(logn)）
缺点：增删慢（时间复杂度为：O(n)）
第三章 栈
3.1 栈概念
栈（stack），有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。没有了位置概念，保证任何时候可以访问、删除的元素都是此前最后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出的原理运作。
栈可以用顺序表实现，也可以用链表实现。
3.2 栈的操作
实现类：
package mystack;public class MyStack {
//栈的底层使用数组来存储数据
//private int[] elements;
int[] elements; //测试时使用
public MyStack() {
elements = new int[0];
}
//添加元素
public void push(int element) {
//创建一个新的数组
int[] newArr = new int[elements.length + 1];
//把原数组中的元素复制到新数组中
for (int i = 0; i < elements.length; i++) {
newArr[i] = elements[i];
}
//把添加的元素放入新数组中
newArr[elements.length] = element;
//使用新数组替换旧数组
elements = newArr;
}
//取出栈顶元素
public int pop() {
//当栈中没有元素
if (is_empty()) {
throw new RuntimeException("栈空");
}
//取出数组的最后一个元素
int element = elements[elements.length - 1];
//创建一个新数组
int[] newArr = new int[elements.length - 1];
//原数组中除了最后一个元素其他元素放入新数组
for (int i = 0; i < elements.length - 1; i++) {
newArr[i] = elements[i];
}
elements = newArr;
return element;
}
//查看栈顶元素
public int peek() {
return elements[elements.length - 1];
}
//判断栈是否为空
public boolean is_empty() {
return elements.length == 0;
}
//查看栈的元素个数
public int size() {
return elements.length;
}}测试类：
package mystack;public class Demo {
public static void main(String[] args) {
MyStack ms = new MyStack();
//添加元素
ms.push(9);
ms.push(8);
ms.push(7);
//取出栈顶元素// System.out.println(ms.pop()); //7// System.out.println(ms.pop()); //8// System.out.println(ms.pop()); //9
//查看栈顶元素
System.out.println(ms.peek()); //7
System.out.println(ms.peek()); //7
//查看栈中元素个数
System.out.println(ms.size()); //3
}}第4章 队列
4.1 队列概念
队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。
同栈一样，队列也可以用顺序表或者链表实现。
4.2 队列的操作
实现类：
public class MyQueue {
int[] elements;
public MyQueue() {
elements = new int[0];
}
//入队
public void enqueue(int element) {
//创建一个新的数组
int[] newArr = new int[elements.length + 1];
//把原数组中的元素复制到新数组中
for (int i = 0; i < elements.length; i++) {
newArr[i] = elements[i];
}
//把添加的元素放入新数组中
newArr[elements.length] = element;
//使用新数组替换旧数组
elements = newArr;
}
//出队
public int dequeue() {
if (isEmpty()) {
throw new RuntimeException("队空，无数据");
}
//把数组中第1个元素取出来
int element = elements[0];
//创建一个新数组
int[] newArr = new int[elements.length - 1];
//把原数组除了第一个数据，其他存入新数组
for (int i = 0; i < elements.length; i++) {
newArr[i] = elements[i + 1];
}
//新数组替换旧数组
elements = newArr;
return element;
}
//判断是否队空
public boolean isEmpty() {
return elements.length==0;
}
//获取队列长度
public int size() {
return elements.length;
}}测试类：
public class Demo {
public static void main(String[] args) {
MyQueue mq = new MyQueue();
//入队
mq.enqueue(1);
mq.enqueue(2);
mq.enqueue(3);
//出队
System.out.println(mq.dequeue()); //1
System.out.println(mq.dequeue()); //2
System.out.println(mq.dequeue()); //3
}}第5章 链表
5.1 单链表
单链表概念
单链表也叫单向链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个链接域。这个链接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
表元素域data用来存放具体的数据。
链接域next用来存放下一个节点的位置
单链表操作
实现类：
//一个节点public class Node {
//节点内容
int data;
//下一个节点
Node next;
public Node(int data) {
this.data = data;
}
//为节点追加节点
public Node append(Node node) {
//当前节点
Node currentNode = this;
//循环向后找
while (true) {
//取出下一个节点
Node nextNode = currentNode.next();
//如果下一个节点为null，当前节点已经是最后一个节点
if (nextNode == null) {
break;
}
//赋给当前节点，无线向后找
currentNode = nextNode;
}
//把需要追加的节点，追加为找到的当前节点（最后一个节点）的下一个节点
currentNode.next = node;
return this;
}
//显示所有节点信息
public void show() {
Node currentNode = this;
while (true) {
System.out.print(currentNode.data + " ");
//取出下一个节点
currentNode = currentNode.next;
//如果是最后一个节点
if (currentNode == null) {
break;
}
}
System.out.println();
}
//插入一个节点作为当前节点的下一个节点
public void after(Node node) {
//取出下一个节点，作为下下一个节点
Node nextNext = next;
//把新节点作为当前节点的下一个节点
this.next = node;
//把下下一个节点设置为新节点的下一个节点
node.next = nextNext;
}
//删除下一个节点
public void removeNode() {
//取出下下一个节点
Node newNext = next.next;
//把下下一个节点设置为当前节点的下一个节点
this.next = newNext;
}
//获取下一个节点
public Node next() {
return this.next;
}
//获取节点中的数据
public int getData() {
return this.data;
}
//判断节点是否为最后一个节点
public boolean isLast() {
return next == null;
}}测试类：
public class Demo {
public static void main(String[] args) {
//创建节点
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
//追加节点
n1.append(n2).append(n3);
//取出下一个节点数据
System.out.println(n1.next().next().getData()); //3
//判断节点是否为最后一个节点
System.out.println(n1.isLast()); //false
System.out.println(n1.next().next().isLast()); //true
//显示所有节点信息
n1.show(); //1 2 3
//删除一个节点// n1.next.removeNode();// n1.show(); //1 2
//插入一个新节点
n1.next.after(new Node(0));
n1.show(); //1 2 0 3
}}5.2 循环链表
循环链表概念
单链表的一个变形是单向循环链表，链表中最后一个节点的 next 域不再为 None，而是指向链表的头节点。
循环链表操作
实现类：
//表示一个节点public class LoopNode {
//节点内容
int data;
//下一个节点
LoopNode next = this; //与单链表的区别，追加了一个this，当只有一个节点时指向自己
public LoopNode(int data) {
this.data = data;
}
//插入一个节点
public void after(LoopNode node) {
LoopNode afterNode = this.next;
this.next = node;
node.next = afterNode;
}
//删除一个节点
public void removeNext() {
LoopNode newNode = this.next.next;
this.next = newNode;
}
//获取下一个节点
public LoopNode next() {
return this.next;
}
//获取节点中的数据
public int getData() {
return this.data;
}}测试类：
public class Demo {
public static void main(String[] args) {
//创建节点
LoopNode n1 = new LoopNode(1);
LoopNode n2 = new LoopNode(2);
LoopNode n3 = new LoopNode(3);
LoopNode n4 = new LoopNode(4);
//增加节点
n1.after(n2);
n2.after(n3);
n3.after(n4);
System.out.println(n1.next().getData()); //2
System.out.println(n2.next().getData()); //3
System.out.println(n3.next().getData()); //4
System.out.println(n4.next().getData()); //1
}}5.3 双向循环链表
双向循环链表概念
在双向链表中有两个指针域，一个是指向前驱结点的prev，一个是指向后继结点的next指针
双向循环链表操作
实现类：
public class DoubleNode {
//上一个节点
DoubleNode pre = this;
//下一个节点
DoubleNode next = this;
//节点数据
int data;
public DoubleNode(int data) {
this.data = data;
}
//增加节点
public void after(DoubleNode node) {
//原来的下一个节点
DoubleNode nextNext = next;
//新节点作为当前节点的下一个节点
this.next = node;
//当前节点作为新节点的前一个节点
node.pre = this;
//原来的下一个节点作为新节点的下一个节点
node.next = nextNext;
//原来的下一个节点的上一个节点为新节点
nextNext.pre = node;
}
//获取下一个节点
public DoubleNode getNext() {
return this.next;
}
//获取上一个节点
public DoubleNode getPre() {
return this.pre;
}
//获取数据
public int getData() {
return this.data;
}}测试类：
public class Demo {
public static void main(String[] args) {
//创建节点
DoubleNode n1 = new DoubleNode(1);
DoubleNode n2 = new DoubleNode(2);
DoubleNode n3 = new DoubleNode(3);
//追加节点
n1.after(n2);
n2.after(n3);
//查看上一个，自己，下一个节点内容
System.out.println(n2.getPre().getData()); //1
System.out.println(n2.getData()); //2
System.out.println(n2.getNext().getData()); //3
System.out.println(n1.getPre().getData()); //3
System.out.println(n3.getNext().getData()); //1
}}第6章 树结构基础
6.1 为什么要使用树结构
线性结构中不论是数组还是链表，他们都存在着诟病；比如查找某个数必须从头开始查，消耗较多的时间。使用树结构，在插入和查找的性能上相对都会比线性结构要好
6.2 树结构基本概念
示意图
1、根节点：最顶上的唯一的一个；如：A
2、双亲节点：子节点的父节点就叫做双亲节点；如A是B、C、D的双亲节点，B是E、F的双亲节点
3、子节点：双亲节点所产生的节点就是子节点
4、路径：从根节点到目标节点所走的路程叫做路径；如A要访问F，路径为A-B-F
5、节点的度：有多少个子节点就有多少的度（最下面的度一定为0，所以是叶子节点）
6、节点的权：在节点中所存的数字
7、叶子节点：没有子节点的节点，就是没有下一代的节点；如：E、F、C、G
8、子树：在整棵树中将一部分看成也是一棵树，即使只有一个节点也是一棵树，不过这个树是在整个大树职中的，包含的关系
9、层：就是族谱中有多少代的人；如：A是1，B、C、D是2，E、F、G是3
10、树的高度：树的最大的层数：就是层数中的最大值
11、森林：多个树组成的集合
6.3 树的种类
无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
6.4 树的存储与表示
顺序存储：将数据结构存储在固定的数组中，然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。
链式存储：
由于对节点的个数无法掌握，常见树的存储表示都转换成二叉树进行处理，子节点个数最多为2
6.5 常见的一些树的应用场景
1、xml，html等，那么编写这些东西的解析器的时候，不可避免用到树
2、路由协议就是使用了树的算法
3、MySQL数据库索引
4、文件系统的目录结构
5、所以很多经典的AI算法其实都是树搜索，此外机器学习中的decision tree也是树结构
第7章 二叉树大全
7.1 二叉树的定义
任何一个节点的子节点数量不超过 2，那就是二叉树；二叉树的子节点分为左节点和右节点，不能颠倒位置
7.2 二叉树的性质(特性)
性质1：在二叉树的第i层上至多有2^(i-1)个结点（i>0）
性质2：深度为k的二叉树至多有2^k - 1个结点（k>0）
性质3：对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
性质4：具有n个结点的完全二叉树的深度必为 log2(n+1)
性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）
7.3 满二叉树与完全二叉树
满二叉树： 所有叶子结点都集中在二叉树的最下面一层上，而且结点总数为：2^n-1 (n为层数 / 高度）
完全二叉树： 所有的叶子节点都在最后一层或者倒数第二层，且最后一层叶子节点在左边连续，倒数第二层在右边连续（满二叉树也是属于完全二叉树）（从上往下，从左往右能挨着数满）
7.4 链式存储的二叉树
创建二叉树：首先需要一个树的类，还需要另一个类用来存放节点，设置节点；将节点放入树中，就形成了二叉树；（节点中需要权值，左子树，右子树，并且都能对他们的值进行设置）。
树的遍历：
查找节点：先对树进行一次遍历，然后找出要找的那个数；因为有三种排序方法，所以查找节点也分为先序查找，中序查找，后序查找；
删除节点：由于链式存储，不能找到要删的数直接删除，需要找到他的父节点，然后将指向该数设置为null；所以需要一个变量来指向父节点，找到数后，再断开连接。
代码实现：
public class BinaryTree {
TreeNode root;
//设置根节点
public void setRoot(TreeNode root) {
this.root = root;
}
//获取根节点
public TreeNode getRoot() {
return root;
}
//先序遍历
public void frontShow() {
if (root != null) {
root.frontShow();
}
}
//中序遍历
public void middleShow() {
if (root != null) {
root.middleShow();
}
}
//后序遍历
public void afterShow() {
if (root != null) {
root.afterShow();
}
}
//先序查找
public TreeNode frontSearch(int i) {
return root.frontSearch(i);
}
//删除一个子树
public void delete(int i) {
if (root.value == i) {
root = null;
} else {
root.delete(i);
}
}}public class TreeNode {
//节点的权
int value;
//左儿子
TreeNode leftNode;
//右儿子
TreeNode rightNode;
public TreeNode(int value) {
this.value = value;
}
//设置左儿子
public void setLeftNode(TreeNode leftNode) {
this.leftNode = leftNode;
}
//设置右儿子
public void setRightNode(TreeNode rightNode) {
this.rightNode = rightNode;
}
//先序遍历
public void frontShow() {
//先遍历当前节点的值
System.out.print(value + " ");
//左节点
if (leftNode != null) {
leftNode.frontShow(); //递归思想
}
//右节点
if (rightNode != null) {
rightNode.frontShow();
}
}
//中序遍历
public void middleShow() {
//左节点
if (leftNode != null) {
leftNode.middleShow(); //递归思想
}
//先遍历当前节点的值
System.out.print(value + " ");
//右节点
if (rightNode != null) {
rightNode.middleShow();
}
}
//后续遍历
public void afterShow() {
//左节点
if (leftNode != null) {
leftNode.afterShow(); //递归思想
}
//右节点
if (rightNode != null) {
rightNode.afterShow();
}
//先遍历当前节点的值
System.out.print(value + " ");
}
//先序查找
public TreeNode frontSearch(int i) {
TreeNode target = null;
//对比当前节点的值
if (this.value == i) {
return this;
//当前节点不是要查找的节点
} else {
//查找左儿子
if (leftNode != null) {
//查找的话t赋值给target，查不到target还是null
target = leftNode.frontSearch(i);
}
//如果target不为空，说明在左儿子中已经找到
if (target != null) {
return target;
}
//如果左儿子没有查到，再查找右儿子
if (rightNode != null) {
target = rightNode.frontSearch(i);
}
}
return target;
}
//删除一个子树
public void delete(int i) {
TreeNode parent = this;
//判断左儿子
if (parent.leftNode != null && parent.leftNode.value == i) {
parent.leftNode = null;
return;
}
//判断右儿子
if (parent.rightNode != null && parent.rightNode.value == i) {
parent.rightNode = null;
return;
}
//如果都不是，递归检查并删除左儿子
parent = leftNode;
if (parent != null) {
parent.delete(i);
}
//递归检查并删除右儿子
parent = rightNode;
if (parent != null) {
parent.delete(i);
}
}}public class Demo {
public static void main(String[] args) {
//创建一棵树
BinaryTree binaryTree = new BinaryTree();
//
本文标题：Java数据结构与算法的示例分析
分享URL：http://njwzjz.com/article/gpecjc.html
