文章目录
-
- 1.数组
-
- 1.1数组的特点
- 1.2自定义数组
- 2.链表
-
- 2.1链表的特点
- 2.2自定义链表
-
- 2.2.1自定义单向链表
- 2.2.2自定义双向链表
- 3.栈
-
- 3.1栈的特点
- 3.2 Stack使用举例
- 3.3 自定义栈
- 4. 队列
- 5. 树与二叉树
-
- 5.1 树的理解
- 5.2 二叉树的基本概念
- 5.3 二叉树的遍历
- 5.4 经典二叉树和红黑树
- 5.5 二叉树及其结点的表示
1.数组
1.1数组的特点
在Java中，数组是用来存放同一种数据类型的集合，并且只能存放同一种数据类型。
//只声明了类型和长度
数据类型[] 数组名称 = new 数据类型[数组长度];
//声明了类型，初始化赋值，大小由元素个数决定
数据类型[] 数组名称 = {数组元素1，数组元素2，......}
例如：整型数组
例如：对象数组
- 物理结构特点：
- 申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。
- 不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入快，删除和查找慢。
- 存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。
- 如下图：
1.2自定义数组
class Array {
private Object[] elementData;
private int size;
public Array(int capacity){
elementData = new Object[capacity];
}
/**
* 添加元素
* @param value
*/
public void add(Object value){
if(size >= elementData.length){
throw new RuntimeException("数组已满，不可添加");
}
elementData[size] = value;
size++;
}
/**
* 查询元素value在数组中的索引位置
* @param value
* @return
*/
public int find(Object value){
for (int i = 0; i size; i++) {
if(elementData[i].equals(value)){
return i;
}
}
return -1;
}
/**
* 从当前数组中移除首次出现的value元素
* @param value
* @return
*/
public boolean delete(Object value){
int index = find(value);
if(index == -1){
return false;
}
for(int i = index;i size - 1;i++){
elementData[i] = elementData[i + 1];
}
elementData[size - 1] = null;
size--;
return true;
}
/**
* 将数组中首次出现的oldValue替换为newValue
* @param oldValue
* @param newValue
* @return
*/
public boolean update(Object oldValue,Object newValue){
int index = find(oldValue);
if(index == -1){
return false;
}
elementData[index] = newValue;
return true;
}
/**
* 遍历数组中所有数据
*/
public void print(){
System.out.print("{");
for (int i = 0; i size; i++) {
if(i == size - 1){
System.out.println(elementData[i] + "}");
break;
}
System.out.print(elementData[i] + ",");
}
}
}
//测试类
public class ArrayTest {
public static void main(String[] args) {
Array arr = new Array(10);
arr.add(123);
arr.add("AA");
arr.add(345);
arr.add(345);
arr.add("BB");
arr.delete(345);
arr.update(345,444);
arr.print();
}
}
2.链表
2.1链表的特点
- 逻辑结构：线性结构
- 物理结构：不要求连续的存储空间
- 存储特点：链表由一系列结点node（链表中每一个元素称为结点）组成，结点可以在代码执行过程中动态创建。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
- 常见的链表结构有如下的形式：
2.2自定义链表
2.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 LinkE> {
// 头节点
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){
//略
}*/
}
2.2.2自定义双向链表
/*
双向链表中的节点。
*/
public class NodeE> {
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 MyLinkedListE> implements IterableE>{
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;
}
}
@Override
public IteratorE> iterator() {
return new Itr();
}
private class Itr implements IteratorE>{
private NodeE> node = first;
@Override
public boolean hasNext() {
return node!=null;
}
@Override
public E next() {
E value = node.data;
node = node.next;
return value;
}
}
}
自定义双链表测试：
public class MyLinkedListTest {
public static void main(String[] args) {
MyLinkedListString> my = new MyLinkedList>();
my.add("hello");
my.add("world");
my.add(null);
my.add(null);
my.add("java");
my.add("java");
my.add("xiaoyang");
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，xiaoyang后：");
my.delete("hello");
my.delete("JAVA");
my.delete(null);
my.delete("xiaoyang");
System.out.println("所有元素：");
for (String s : my) {
System.out.println(s);
}
}
}
3.栈
3.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)
- 如图所示：
3.2 Stack使用举例
public class TestStack {
/*
* 测试Stack
* */
@Test
public void test1(){
StackInteger> 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
* */
@Test
public void test2(){
LinkedListInteger> 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());
}
}
}
3.3 自定义栈
public class MyStack {
// 向栈当中存储元素，我们这里使用一维数组模拟。存到栈中，就表示存储到数组中。
// 为什么选择Object类型数组？因为这个栈可以存储java中的任何引用类型的数据
private Object[] elements;
// 栈帧，永远指向栈顶部元素
// 那么这个默认初始值应该是多少。注意：最初的栈是空的，一个元素都没有。
//private int index = 0; // 如果index采用0，表示栈帧指向了顶部元素的上方。
//private int index = -1; // 如果index采用-1，表示栈帧指向了顶部元素。
private int index;
/**
* 无参数构造方法。默认初始化栈容量10.
*/
public MyStack() {
// 一维数组动态初始化
// 默认初始化容量是10.
this.elements = new Object[10];
// 给index初始化
this.index = -1;
}
/**
* 压栈的方法
* @param obj 被压入的元素
*/
public void push(Object obj) throws Exception {
if(index >= elements.length - 1){
//方式1：
//System.out.println("压栈失败，栈已满！");
//return;
//方式2：
throw new Exception("压栈失败，栈已满！");
}
// 程序能够走到这里，说明栈没满
// 向栈中加1个元素，栈帧向上移动一个位置。
index++;
elements[index] = obj;
System.out.println("压栈" + obj + "元素成功，栈帧指向" + index);
}
/**
* 弹栈的方法，从数组中往外取元素。每取出一个元素，栈帧向下移动一位。
* @return
*/
public Object pop() throws Exception {
if (index 0) {
//方式1：
//System.out.println("弹栈失败，栈已空！");
//return;
//方式2：
throw new Exception("弹栈失败，栈已空！");
}
// 程序能够执行到此处说明栈没有空。
Object obj = elements[index];
System.out.print("弹栈" + obj + "元素成功，");
elements[index] = null;
// 栈帧向下移动一位。
index--;
return obj;
}
// set和get也许用不上，但是你必须写上，这是规矩。你使用IDEA生成就行了。
// 封装：第一步：属性私有化，第二步：对外提供set和get方法。
public Object[] getElements() {
return elements;
}
public void setElements(Object[] elements) {
this.elements = elements;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
4. 队列
- 队列（
Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。 - 队列是逻辑结构，其物理结构可以是数组，也可以是链表。
- 队列的修改原则：队列的修改是依先进先出（FIFO）的原则进行的。新来的成员总是加入队尾（即不允许”加塞”），每次离开的成员总是队列头上的（不允许中途离队），即当前”最老的”成员离队。
- 图示：
5. 树与二叉树
5.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
- 同代：在同一棵树中具有相同层数的节点
5.2 二叉树的基本概念
二叉树（Binary tree）是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。许多实际问题抽象出来的数据结构往往是二叉树形式，二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。
5.3 二叉树的遍历
-
前序遍历：中左右（根左右）
即先访问根结点，再前序遍历左子树，最后再前序遍历右子 树。前序遍历运算访问二叉树各结点是以根、左、右的顺序进行访问的。 -
中序遍历：左中右（左根右）
即先中前序遍历左子树，然后再访问根结点，最后再中序遍 历右子树。中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。 -
后序遍历：左右中（左右根）
即先后序遍历左子树，然后再后序遍历右子树，最后访问根 结点。后序遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。
前序遍历：ABDHIECFG
中序遍历：HDIBEAFCG
后序遍历：HIDEBFGCA
5.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、伸展树等。
5、红黑树：即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(log n)时间内做查找，插入和删除， 这里的 n 是树中元素的数目。
红黑树的特性：
- 每个节点是红色或者黑色
- 根节点是黑色
- 每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点）
- 每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（确保没有一条路径会比其他路径长出2倍）
当插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理，使得它继续满足以上的5个要求：
1、recolor ：将某个节点变红或变黑
2、rotation ：将红黑树某些结点分支进行旋转（左旋或右旋）
红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据，它的时间复杂度是O(logN)，效率非常之高。
5.5 二叉树及其结点的表示
普通二叉树：
public class BinaryTreeE>{
private TreeNode root; //二叉树的根结点
private int total;//结点总个数
private class TreeNode{
//至少有以下几个部分
TreeNode parent;
TreeNode left;
E data;
TreeNode right;
public TreeNode(TreeNode parent, TreeNode left, E data, TreeNode right) {
this.parent = parent;
this.left = left;
this.data = data;
this.right = right;
}
}
}
TreeMap红黑树：
public class TreeMapK,V> {
private transient EntryK,V> root;
private transient int size = 0;
static final class EntryK,V> implements Map.EntryK,V> {
K key;
V value;
EntryK,V> left;
EntryK,V> right;
EntryK,V> parent;
boolean color = BLACK;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, EntryK,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
