1. 数据结构剖析
我们举一个形象的例子来理解数据结构的作用:
战场:程序运行所需的软件、硬件环境
敌人:项目或模块的功能需求
指挥官:编写程序的程序员
士兵和装备:一行一行的代码
战术和策略:数据结构
上图:没有战术,打仗事倍功半
上图:有战术,打仗事半功倍
总结:简单来说,数据结构,就是一种程序设计优化的方法论,研究数据的逻辑结构
和物理结构
以及它们之间相互关系,并对这种结构定义相应的运算
,目的是加快程序的执行速度、减少内存占用的空间。
具体研究对象如下:
1.1 研究对象一:数据间逻辑关系
数据的逻辑结构指反映数据元素之间的逻辑关系,而与数据的存储无关,是独立于计算机的。
-
集合结构:数据结构中的元素之间除了“
同属一个集合
” 的相互关系外,别无其他关系。集合元素之间没有逻辑关系。 -
线性结构:数据结构中的元素存在
一对一
的相互关系。比如:排队。结构中必须存在唯一的首元素和唯一的尾元素。体现为:一维数组、链表、栈、队列 -
树形结构:数据结构中的元素存在
一对多
的相互关系。比如:家谱、文件系统、组织架构 -
图形结构:数据结构中的元素存在
多对多
的相互关系。比如:全国铁路网、地铁图
2. 一维数组
2.1 数组的特点
-
在Java中,数组是用来存放同一种数据类型的集合,注意只能存放同一种数据类型。
//只声明了类型和长度
数据类型[] 数组名称 = new 数据类型[数组长度];//声明了类型,初始化赋值,大小由元素个数决定
数据类型[] 数组名称 = {数组元素1,数组元素2,......}
例如:整型数组
例如:对象数组
-
物理结构特点:
-
申请内存:一次申请一大段连续的空间,一旦申请到了,内存就固定了。
-
不能动态扩展(初始化给大了,浪费;给小了,不够用),插入快,删除和查找慢。
-
存储特点:所有数据存储在这个连续的空间中,数组中的每一个元素都是一个具体的数据(或对象),所有数据都紧密排布,不能有间隔。
-
3. 链表
3.1 链表的特点
-
逻辑结构:线性结构
-
物理结构:不要求连续的存储空间
-
存储特点:链表由一系列结点node(链表中每一个元素称为结点)组成,结点可以在代码执行过程中动态创建。每个结点包括两个部分:一个是存储数据元素的
数据域
,另一个是存储下一个结点地址的指针域
。
- 常见的链表结构有如下的形式:
3.2 自定义链表
3.2.1 自定义单向链表
/*
单链表中的节点。
节点是单向链表中基本的单元。
每一个节点Node都有两个属性:一个属性:是存储的数据。另一个属性:是下一个节点的内存地址。*/
public class Node {// 存储的数据Object data;// 下一个节点的内存地址Node next;public Node(){}public Node(Object data, Node next){this.data = data;this.next = next;}
}
/*
链表类(单向链表)*/
public class Link<E> {// 头节点Node header;private int size = 0;public int size(){return size;}// 向链表中添加元素的方法(向末尾添加)public void add(E data){//public void add(Object data){// 创建一个新的节点对象// 让之前单链表的末尾节点next指向新节点对象。// 有可能这个元素是第一个,也可能是第二个,也可能是第三个。if(header == null){// 说明还没有节点。// new一个新的节点对象,作为头节点对象。// 这个时候的头节点既是一个头节点,又是一个末尾节点。header = new Node(data, null);}else {// 说明头不是空!// 头节点已经存在了!// 找出当前末尾节点,让当前末尾节点的next是新节点。Node currentLastNode = findLast(header);currentLastNode.next = new Node(data, null);}size++;}/*** 专门查找末尾节点的方法。*/private Node findLast(Node node) {if(node.next == null) {// 如果一个节点的next是null// 说明这个节点就是末尾节点。return node;}// 程序能够到这里说明:node不是末尾节点。return findLast(node.next); // 递归算法!}/*// 删除链表中某个数据的方法public void remove(Object obj){//略}// 修改链表中某个数据的方法public void modify(Object newObj){//略}// 查找链表中某个元素的方法。public int find(Object obj){//略}*/
}
3.2.2 自定义双向链表
/*
双向链表中的节点。*/
public class Node<E> {Node prev;E data;Node next;Node(Node prev, E data, Node next) {this.prev = prev;this.data = data;this.next = next;}
}
/*** 链表类(双向链表)* @author 尚硅谷-宋红康* @create 15:05*/
public class MyLinkedList<E> implements Iterable<E>{private Node first; //链表的首元素private Node last; //链表的尾元素private int total;public void add(E e){Node newNode = new Node(last, e, null);if(first == null){first = newNode;}else{last.next = newNode;}last = newNode;total++;}public int size(){return total;}public void delete(Object obj){Node find = findNode(obj);if(find != null){if(find.prev != null){find.prev.next = find.next;}else{first = find.next;}if(find.next != null){find.next.prev = find.prev;}else{last = find.prev;}find.prev = null;find.next = null;find.data = null;total--;}}private Node findNode(Object obj){Node node = first;Node find = null;if(obj == null){while(node != null){if(node.data == null){find = node;break;}node = node.next;}}else{while(node != null){if(obj.equals(node.data)){find = node;break;}node = node.next;}}return find;}public boolean contains(Object obj){return findNode(obj) != null;}public void update(E old, E value){Node find = findNode(old);if(find != null){find.data = value;}}@Overridepublic Iterator<E> iterator() {return new Itr();}private class Itr implements Iterator<E>{private Node<E> node = first;@Overridepublic boolean hasNext() {return node!=null;}@Overridepublic E next() {E value = node.data;node = node.next;return value;}}
}
自定义双链表测试:
public class MyLinkedListTest {public static void main(String[] args) {MyLinkedList<String> my = new MyLinkedList<>();my.add("hello");my.add("world");my.add(null);my.add(null);my.add("java");my.add("java");my.add("atguigu");System.out.println("一共有:" + my.size());System.out.println("所有元素:");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("查找java,null,haha的结果:");System.out.println(my.contains("java"));System.out.println(my.contains(null));System.out.println(my.contains("haha"));System.out.println("-------------------------------------");System.out.println("替换java,null后:");my.update("java","JAVA");my.update(null,"songhk");System.out.println("所有元素:");for (String s : my) {System.out.println(s);}System.out.println("-------------------------------------");System.out.println("删除hello,JAVA,null,atguigu后:");my.delete("hello");my.delete("JAVA");my.delete(null);my.delete("atguigu");System.out.println("所有元素:");for (String s : my) {System.out.println(s);}}
}
4. 栈
4.1 栈的特点
-
栈(Stack)又称为堆栈或堆叠,是限制仅在表的一端进行插入和删除运算的线性表。
-
栈按照
先进后出(FILO,first in last out)
的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶。每次删除(退栈)的总是删除当前栈中最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。
-
核心类库中的栈结构有Stack和LinkedList。
-
Stack就是顺序栈,它是Vector的子类。
-
LinkedList是链式栈。
-
-
体现栈结构的操作方法:
-
peek()方法:查看栈顶元素,不弹出
-
pop()方法:弹出栈
-
push(E e)方法:压入栈
-
-
时间复杂度:
-
索引:
O(n)
-
搜索:
O(n)
-
插入:
O(1)
-
移除:
O(1)
-
-
图示:
4.2 Stack使用举例
public class TestStack {/** 测试Stack* */@Testpublic void test1(){Stack<Integer> list = new Stack<>();list.push(1);list.push(2);list.push(3);System.out.println("list = " + list);System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());/*System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/while(!list.empty()){System.out.println("list.pop() =" + list.pop());}}/** 测试LinkedList* */@Testpublic void test2(){LinkedList<Integer> list = new LinkedList<>();list.push(1);list.push(2);list.push(3);System.out.println("list = " + list);System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());System.out.println("list.peek()=" + list.peek());/*System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/while(!list.isEmpty()){System.out.println("list.pop() =" + list.pop());}}
}
5. 队列
-
队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。
-
队列是逻辑结构,其物理结构可以是数组,也可以是链表。
-
队列的修改原则:队列的修改是依
先进先出(FIFO)的原则
进行的。新来的成员总是加入队尾(即不允许"加塞"),每次离开的成员总是队列头上的(不允许中途离队),即当前"最老的"成员离队。 -
图示:
6. 树与二叉树
6.1 树的理解
专有名词解释:
结点
:树中的数据元素都称之为结点
根节点
:最上面的结点称之为根,一颗树只有一个根且由根发展而来,从另外一个角度来说,每个结点都可以认为是其子树的根
父节点
:结点的上层结点,如图中,结点K的父节点是E、结点L的父节点是G
子节点
:节点的下层结点,如图中,节点E的子节点是K节点、节点G的子节点是L节点
兄弟节点
:具有相同父节点的结点称为兄弟节点,图中F、G、H互为兄弟节点
结点的度数
:每个结点所拥有的子树的个数称之为结点的度,如结点B的度为3
树叶
:度数为0的结点,也叫作终端结点,图中D、K、F、L、H、I、J都是树叶
非终端节点(或分支节点)
:树叶以外的节点,或度数不为0的节点。图中根、A、B、C、E、G都是
树的深度(或高度)
:树中结点的最大层次数,图中树的深度为4
结点的层数
:从根节点到树中某结点所经路径上的分支树称为该结点的层数,根节点的层数规定为1,其余结点的层数等于其父亲结点的层数+1
同代
:在同一棵树中具有相同层数的节点
6.2 二叉树的基本概念
二叉树(Binary tree)是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树,且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式,二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。
6.3 二叉树的遍历
-
前序遍历:中左右(根左右)
即先访问根结点,再前序遍历左子树,最后再前序遍历右子 树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。
-
中序遍历:左中右(左根右)
即先中前序遍历左子树,然后再访问根结点,最后再中序遍 历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。
-
后序遍历:左右中(左右根)
即先后序遍历左子树,然后再后序遍历右子树,最后访问根 结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。
前序遍历:ABDHIECFG
中序遍历:HDIBEAFCG
后序遍历:HIDEBFGCA
6.4 经典二叉树
1、满二叉树
: 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。 第n层的结点数是2的n-1次方,总的结点个数是2的n次方-1
2、完全二叉树
: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧。
3、二叉排序/查找/搜索树
:即为BST (binary search/sort tree)。满足如下性质:
(1)若它的左子树不为空,则左子树上所有结点的值均小于它的根节点的值;
(2)若它的右子树上所有结点的值均大于它的根节点的值;
(3)它的左、右子树也分别为二叉排序/查找/搜索树。
对二叉查找树进行中序遍历,得到有序集合。便于检索。
4、平衡二叉树
:(Self-balancing binary search tree,AVL)首先是二叉排序树,此外具有以下性质: (1)它是一棵空树或它的左右两个子树的高度差的绝对值不超过1 (2)并且左右两个子树也都是一棵平衡二叉树 (3)不要求非叶节点都有两个子结点
平衡二叉树的目的是为了减少二叉查找树的层次,提高查找速度。平衡二叉树的常用实现有红黑树、AVL、替罪羊树、Treap、伸展树等。
6、红黑树
:即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的,但它的操作有着良好的最坏情况运行时间
,并且在实践中是高效的
:它可以在 O(log n)时间内做查找,插入和删除, 这里的 n 是树中元素的数目。
红黑树的特性:
-
每个节点是红色或者黑色
-
根节点是黑色
-
每个叶子节点(NIL)是黑色。(注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点)
-
每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
-
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(确保没有一条路径会比其他路径长出2倍)
当我们插入或删除节点时,可能会破坏已有的红黑树,使得它不满足以上5个要求,那么此时就需要进行处理,使得它继续满足以上的5个要求:
1、recolor
:将某个节点变红或变黑
2、rotation
:将红黑树某些结点分支进行旋转(左旋或右旋)
红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据,它的时间复杂度是O(logN),效率非常之高。