图解数据结构(Java语言实现)

Author Avatar
wshunli 8月 29, 2018
  • 在其它设备中阅读本文章

数据结构与算法一直是比较薄弱的地方,不仅在面试的时候会问相关问题、手写代码,而且在笔试的时候发挥重要作用。

这次选择看的书籍是 《图解数据结构-使用Java》 ,先入门,后面再深入学习。

算法的时间复杂度,用来度量算法的运行时间,记作: T(n) = O(f(n))。它表示随着 输入大小 n 的增大,算法执行需要的时间的增长速度可以用 f(n) 来描述。

线性表是 n 个元素的有限序列(n >= 0),是计算机科学中一种相当基础的数据结构。

数组

数组 其实是一排紧密相邻的可读内存,并提供一个能够 直接访问 单一数据内容的计算方法。

这样能够直接通过计算,并访问任一位置的数据,即所谓的数组的 随机读取

当 Java 数组声明时会在内存中分配一定的暂存空间,空间大小以数据类型和数组数量为依据。

一维数据、二维数组、三维数组、n 维数组。

数组可用于矩阵、多项式等的运算。

链表

链表 是由许多相同数据类型的元素按照特定顺序排列而成的线性表,其在内存中是不连续与随机存储的。

这样就不能像数组那样随机读取数据,而要 按照顺序 找到所需数据。

单向链表

单向链表是由节点组成,指针方向相同的链表。其中节点由数据字段和链接字段组成。

在 Java 中,声明节点:

public class Node {
    int data;
    Node next;
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

而 Java 中没有指针的概念,我们声明两个对象分别指向第一个和最后一个节点:

public class LinkedList {
    private Node first;
    private Node last;
    ...
}

1、单向链表的创建

下面创建简单单向链表类:

public class LinkedList {

    private Node first;
    private Node last;

    public boolean isEmpty() {
        return first == null;
    }
    public void insert(int data) {
        Node node = new Node(data);
        if (this.isEmpty()) {
            first = node;
            last = node;
        } else {
            last.next = node;
            last = node;
        }
    }
    public void print() {
        Node current = first;
        while (current != null) {
            System.out.println("current.data=" + current.data);
            current = current.next;
        }
    }
}

然后实例化链表对象即可:

public class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.insert(99);
        linkedList.insert(90);
        linkedList.insert(95);
        linkedList.print();
    }
}

这样所有节点都知道下个节点在哪里,只要有首节点的存在,就可以对整个列表进行遍历、插入及删除节点等动作。

2、单向链表节点的删除

将欲删除节点的前一个节点的指针指向欲删除节点的下一个节点即可。

如果删除 首节点,将首节点的下个节点设置为首节点;如果删除 末节点,将前一个节点指向 null 即可。

  public void delete(Node node) {
      Node newNode;
      Node temp;
      if (first.data == node.data) {
          first = first.next;
      } else if (last.data == node.data) {
          temp = first;
          while (temp.next != last) {
              temp = temp.next;
          }
          temp.next = last.next; // temp.next = null;
          last = temp; // 设置末节点
      } else {
          newNode = first;
          temp = first;
          while (temp.data != node.data) {
              newNode = temp;
              temp = temp.next;
          }
          newNode.next = temp.next;
      }
  }

这样删除有点弊端,根据 node 节点的值判断是否是同一节点,并且没有对节点是否存在做判断。

3、单向链表节点的添加

添加节点和删除节点有点类似,将前一个节点指向新添加的节点,然后将新添加节点指向下一个节点即可。

如果添加为 首节点 ,将欲添加节点指向首节点;如果添加为 末节点 ,将原末节点指向新节点即可。

public void insert(Node node) {
    Node newNode;
    Node temp;
    if (node.next == first) {
        node.next = first;
        first = node;
    } else if (node.next == null) {
        last.next = node;
        node.next = null;
    } else {
        newNode = first;
        temp = first;
        while (node.next != newNode.next) {
            temp = newNode;
            newNode = newNode.next;
        }
        temp.next = node;
        node.next = newNode;
    }
}

这样在节点位置的判断上还是有弊端的。

4、单向链表的反转

面试有时候会让手写这个代码。

遍历法: 从链表头部开始,逐个反转节点。

public Node reverse(Node head) {

    if (head == null) return null;      // 空链表
    if (head.next == null) return head; // 一个元素的链表

    Node preNode = null;
    Node nowNode = head;

    while (nowNode != null) {
        Node nextNode = nowNode.next;   // 保存下一个结点
        nowNode.next = preNode;         // 当前结点指向前一个结点
        preNode = nowNode;              // 前任结点 到现任节点
        nowNode = nextNode;             // 现任节点到下一结点
    }
    return preNode;
}

递归法:从链表尾部开始,逐个反转节点。

public Node reverse(Node node) {
    if (node == null || node.next == null) return node;
    Node headNode = reverse(node.next);
    node.next.next = node;
    node.next = null;
    return headNode;
}

以上算法都需要传入链表的头部节点,打印时需要注意头部和尾部节点引用。

5、单向链表的串联

将列表的首位节点相连即可。

public LinkedList connect(LinkedList list1, LinkedList list2) {
    LinkedList list = list1;
//  while (list.last.next != null) {
//     list.last = list.last.next;
//  }
    list.last.next = list2.first;
    return list;
}

环形链表

我们把单向链表的尾部指向头部,整个链表就成为单向环形结构。

这里创建链表、插入节点、删除节点、链表串联都很类似。

双向链表

双向链表基本结构和单项连链表类似,至少一个节点存放数据,另外它有两个字段存放指针。

堆栈

堆栈是一种抽象的数据结构:只能从堆栈的 顶端 访问数据;数据访问符合 后进先出 的原则。

堆栈的数组实现

class StackByArray { //以数组模拟堆栈的类声明
    private int[] stack; //在类中声明数组
    private int top;  //指向堆栈顶端的索引

    //StackByArray类构造函数
    public StackByArray(int stack_size) {
        stack = new int[stack_size]; //建立数组
        top = -1;
    }
    //类方法:push
    //存放顶端数据,并更正新堆栈的内容
    public boolean push(int data) {
        if (top >= stack.length) { //判断堆栈顶端的索引是否大于数组大小
            System.out.println("堆栈已满,无法再加入");
            return false;
        } else {
            stack[++top] = data; //将数据存入堆栈
            return true;
        }
    }
    //类方法:empty
    //判断堆栈是否为空堆栈,是则返回true,不是则返回false
    public boolean empty() {
        if (top == -1) return true;
        else return false;
    }
    //类方法:pop
    //从堆栈取出数据
    public int pop() {
        if (empty()) //判断堆栈是否为空,如果是则返回-1值
            return -1;
        else
            return stack[top--]; //先将数据取出后,再将堆栈指针往下移
    }
}

堆栈的链表实现

class Node //链接节点的声明
{
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class StackByLink {
    public Node front; //指向堆栈底端的指针
    public Node rear;  //指向堆栈顶端的指针

    //类方法:isEmpty()
    //判断堆栈如果为空堆栈,则front==null;
    public boolean isEmpty() {
        return front == null;
    }

    //打印堆栈内容
    public void output_of_Stack() {
        Node current = front;
        while (current != null) {
            System.out.print("[" + current.data + "]");
            current = current.next;
        }
        System.out.println();
    }

    //在堆栈顶端加入数据
    public void insert(int data) {
        Node newNode = new Node(data);
        if (this.isEmpty()) {
            front = newNode;
            rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }

    //在堆栈顶端删除数据
    public void pop() {
        Node newNode;
        if (this.isEmpty()) {
            System.out.print("===目前为空堆栈===\n");
            return;
        }
        newNode = front;
        if (newNode == rear) {
            front = null;
            rear = null;
            System.out.print("===目前为空堆栈===\n");
        } else {
            while (newNode.next != rear)
                newNode = newNode.next;
            newNode.next = rear.next;
            rear = newNode;
        }
    }
}

堆栈的应用

二叉树及森林的遍历;图形的深度优先遍历;递归程序的调用及返回等等。

队列

队列是一种抽象的数据结构:只能从队列的 两端 访问数据;数据访问符合 先进先出 的原则。

队列的数组实现

public class ArrayQueue {
    private int[] data;
    private int size;//元素个数
    private int front;//队列中第一个对象的位置
    private int rear;//队列中当前对象的位置

    public ArrayQueue() {
        data = new int[10];
        size = 0;
        front = 0;
        rear = 0;
    }

    public void add(int t) {
        if (isFull()) {
            resize();
            front = 0;
        }
        rear = (front + size) % data.length;
        System.out.println(rear);
        data[rear] = t;
        size++;
    }

    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空!");
        }
        int tempData = data[front];
        data[front] = 0;
        front = (front + 1) % (data.length);
        size--;
        return tempData;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == data.length;
    }

    public void resize() {
        /*注意重新扩容的时候并不需要去设置size
         * 队列的大小并不能通过数组的大小直观的显示出来。
         * 但是栈就可以直观的通过数组的大小显示出来*/
        int[] tmp = new int[data.length * 2];
        System.arraycopy(data, 0, tmp, 0, data.length);
        data = tmp;
        tmp = null;//引用置为空,便于gc处理  
    }
}

队列的链表实现

class QueueNode                 // 队列节点类
{
    int data;                    // 节点数据
    QueueNode next;              // 指向下一个节点

    //构造函数
    public QueueNode(int data) {
        this.data = data;
        next = null;
    }
}

class Linked_List_Queue { //队列类
    public QueueNode front; //队列的前端指针
    public QueueNode rear;  //队列的尾端指针

    //构造函数
    public Linked_List_Queue() {
        front = null;
        rear = null;
    }

    //方法enqueue:队列数据的存入
    public boolean enqueue(int value) {
        QueueNode node = new QueueNode(value); //建立节点
        //检查是否为空队列
        if (rear == null)
            front = node; //新建立的节点成为第一个节点
        else
            rear.next = node; //将节点加入到队列的尾端
        rear = node; //将队列的尾端指针指向新加入的节点
        return true;
    }

    //方法dequeue:队列数据的取出
    public int dequeue() {
        int value;
        //检查队列是否为空队列
        if (!(front == null)) {
            if (front == rear) rear = null;
            value = front.data; //将队列数据取出
            front = front.next; //将队列的前端指针指向下一个
            return value;
        } else return -1;
    }
} //队列类声明结束

环形队列、优先队列、双向队列

树状结构

树是一种用来表述有 分支 的数据结构,是由一个或者一个以上的节点组成的有限集合。

树的专有名词

结点度:结点子树的个数;树的度:树中最大的结点度。

叶子节点:没有子节点的节点,即度为 0 的节点。

二叉树

二叉树最多有两个子节点,即度 <= 2 的树。

特殊的二叉树

1、满二叉树,树的高度为 h 树的节点为 $2^h-1$ 我们称为满二叉树。

2、完全二叉树,树的高度为 h 树的节点小于 $2^h-1$ ,但是其节点和满二叉树从左到右,从上到下的顺序一一对应。

特殊的二叉树

3、歪二叉树,当一个二叉树完全没有右节点/左节点时。

4、严格二叉树,每个二叉树都有非空的左右子树。成为严格二叉树。

二叉树的存储方式

1、数组表示法

首先将二叉树想象为满二叉树,然后依次存放入数组中,空位为 null 即可。

以数组建立二叉树,要求小于父节点的值放在左子节点,反之放在右边。

public class CH06_01 {
    public static void main(String args[]) throws IOException
    {
        int i, level;
        int data[] = {6, 3, 5, 9, 7, 8, 4, 2}; /*原始数组*/
        int btree[] = new int[16];
        for (i = 0; i < 16; i++) btree[i] = 0;
        System.out.print("原始数组内容: \n");
        for (i = 0; i < 8; i++)
            System.out.print("[" + data[i] + "] ");
        System.out.println();
        for (i = 0; i < 8; i++)                    /*把原始数组中的值逐一对比*/ {
            for (level = 1; btree[level] != 0; )   /*比较树根及数组内的值*/ {
                if (data[i] > btree[level])        /*如果数组内的值大于树根,则往右子树比较*/
                    level = level * 2 + 1;
                else                               /*如果数组内的值小于或等于树根,则往左子树比较*/
                    level = level * 2;
            }                                      /*如果子树节点的值不为0,则再与数组内的值比较一次*/
            btree[level] = data[i];                /*把数组值放入二叉树*/
        }
        System.out.print("二叉树内容:\n");
        for (i = 1; i < 16; i++)
            System.out.print("[" + btree[i] + "] ");
        System.out.print("\n");
    }
}

2、链表表示法

二叉链表结构主要由一个数据域和两个分别指向左、右孩子的结点组成,其结构如下:

链表表示法

TreeNode 及 BinaryTree 声明如下:

class TreeNode {
    int value;
    TreeNode left_Node;
    TreeNode right_Node;
    // TreeNode构造函数
    public TreeNode(int value) {
        this.value = value;
        this.left_Node = null;
        this.right_Node = null;
    }
}
//二叉树类声明
class BinaryTree {
    public TreeNode rootNode; //二叉树的根节点

    //构造函数:利用传入一个数组的参数来建立二叉树
    public BinaryTree(int[] data) {
        for (int i = 0; i < data.length; i++)
            Add_Node_To_Tree(data[i]);
    }

    //将指定的值加入到二叉树中适当的节点
    void Add_Node_To_Tree(int value) {
        TreeNode currentNode = rootNode;
        if (rootNode == null) { //建立树根
            rootNode = new TreeNode(value);
            return;
        }
        //建立二叉树
        while (true) {
            if (value < currentNode.value) { //在左子树
                if (currentNode.left_Node == null) {
                    currentNode.left_Node = new TreeNode(value);
                    return;
                } else currentNode = currentNode.left_Node;
            } else { //在右子树
                if (currentNode.right_Node == null) {
                    currentNode.right_Node = new TreeNode(value);
                    return;
                } else currentNode = currentNode.right_Node;
            }
        }
    }
}

这样增删很容易,但是不容易找到父节点,除非增加字段。

二叉树的遍历

二叉树的遍历:即“访问树中所有节点各一次”。按照二叉树特性,一律从左向右。

根据访问根节点的顺序,二叉树的遍历规则主要有四种,先根次序遍历,中根次序遍历,后根次序遍历以及层次遍历。

// 中序遍历
public void InOrder(TreeNode node) {
    if (node != null) {
        InOrder(node.left_Node);
        System.out.print("[" + node.value + "] ");
        InOrder(node.right_Node);
    }
}
// 前序遍历
public void PreOrder(TreeNode node) {
    if (node != null) {
        System.out.print("[" + node.value + "] ");
        PreOrder(node.left_Node);
        PreOrder(node.right_Node);
    }
}
// 后序遍历
public void PostOrder(TreeNode node) {
    if (node != null) {
        PostOrder(node.left_Node);
        PostOrder(node.right_Node);
        System.out.print("[" + node.value + "] ");
    }
}

图形结构

图形结构是用来探讨两个顶点间是否相连的关系图,若在边上加权值,这类图成为“网络”。

图形介绍

图形有两种:有向图、无向图。

图形的专业术语:

度:一个顶点所拥有边的总数。
入/出度:在有向图中,定点为箭头终点的边的个数为入度;出度为起点边的个数。

图形的表示法

1、邻接矩阵法/相邻表法

2、相邻多元列表法/索引表格法

图形的遍历

图形的遍历方法有两种:深度优先遍历、广度优先遍历。

1、深度优先使用递归与 堆栈 的技巧

从图形的某一顶点开始遍历,被访问过的顶点就做上已访问的记号,接着遍历此顶点的所有相邻且未访问过的顶点中的任意一个顶点,并做上已访问的记号,再以该点为新的起点继续进行先深后广的搜索。

图形-图的遍历

(1)从起点 1 开始,将相邻的 2 3 放入堆栈

3 2

(2)将 2 取出,并将与 2 相邻且未访问的 4 5 放入堆栈

3 5 4

(3)将 4 取出,并将与 4 相邻且未访问的 8 放入堆栈

3 5 8

(4)将 8 取出,并将与 8 相邻且未访问的 5 放入堆栈

3 5 5

(5)将 5 取出,发现与 5 相邻的节点都访问过了,这里就舍去

3

(6)将 3 取出,并将与 3 相邻且未访问的 6 7 放入堆栈

7 6

(7)最后将堆栈的节点逐个判断即可。

7 7

最终遍历顺序为:1 -> 2 -> 4 -> 8 -> 5 -> 3 -> 6 -> 7

public static void dfs(int current)
{
    run[current] = 1;
    System.out.print("[" + current + "]");

    while ((Head[current].first) != null) {
        if (run[Head[current].first.x] == 0) //如果顶点尚未遍历,就进行dfs的递归调用
            dfs(Head[current].first.x);
        Head[current].first = Head[current].first.next;
    }
}

2、广度优先使用递归与 队列 的技巧

从图形的某顶点开始遍历,被访问过的顶点就做上已访问的记号,接着遍历此顶点的所有相邻且未访问过的顶点中的任意个顶点,并做上已访问的记号,再以该点为新的起点继续进行先广后深的搜索。

图形-图的遍历

(1)从起点 1 开始,将相邻的 2 3 放入堆栈

2 3

(2)将 2 取出,并将与 2 相邻且未访问的 4 5 放入堆栈

3 4 5

(3)将 3 取出,并将与 3 相邻且未访问的 6 7 放入堆栈

4 5 6 7

(4)将 4 取出,并将与 4 相邻且未访问的 8 放入堆栈

5 6 7 8

(5)将 5 取出,并将与 5 相邻且未访问的 8 放入堆栈

6 7 8 8

(6)将 6 取出,并将与 6 相邻且未访问的 7 放入堆栈

7 8 8 7

(7)将 7 取出,发现与 7 相邻的节点都访问过了,这里就舍去

8 8 7

(8)最后将队列的节点逐个判断即可。

8 7

最终遍历顺序为:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

public void bfs(int current) {
    Node tempnode; //临时的节点指针
    enqueue(current); //将第一个顶点存入队列
    run[current] = 1; //将遍历过的顶点设定为1
    System.out.print("[" + current + "]"); //打印该遍历过的顶点
    while (front != rear) { //判断目前是否为空队列
        current = dequeue(); //将顶点从队列中取出
        tempnode = Head[current].first; //先记录目前顶点的位置
        while (tempnode != null) {
            if (run[tempnode.x] == 0) {
                enqueue(tempnode.x);
                run[tempnode.x] = 1; //记录已遍历过
                System.out.print("[" + tempnode.x + "]");
            }
            tempnode = tempnode.next;
        }
    }
}

生成树

一个图形的生成树以最少的边来连接图形中所有的顶点,且不造成回路(Cycle)的树状结构。

深度优先生成树、广度优先生成树。

MST 生成树,即在加权图(网络)上,计算路径成本最小的的生成树。有 Peim 算法和 Kruskal 算法等。

前面一直学习的数据结构,下面排序、查找属于算法的范畴了。

数据结构:https://www.wshunli.com/posts/850e5c53.html
算法:https://www.wshunli.com/posts/444e2c0f.html

参考资料
1、《图解数据结构-使用Java》
2、(数据结构)十分钟搞定时间复杂度(算法的时间复杂度) - 简书
https://www.jianshu.com/p/f4cca5ce055a
3、单链表反转的两种实现(Java) - CSDN博客
https://blog.csdn.net/acquaintanceship/article/details/73011169
4、data structures - Reversing a linked list in Java, recursively - Stack Overflow
https://stackoverflow.com/questions/354875/reversing-a-linked-list-in-java-recursively
5、【算法】如何判断链表有环 - CSDN博客
https://blog.csdn.net/u010983881/article/details/78896293
6、队列的实现(JAVA) - CSDN博客
https://blog.csdn.net/lcore/article/details/8868078
7、树和二叉树定义、基本术语和性质 - CSDN博客
https://blog.csdn.net/lsh_2013/article/details/43121373
8、java数据结构与算法之树基本概念及二叉树(BinaryTree)的设计与实现 - CSDN博客
https://blog.csdn.net/javazejian/article/details/53727333
9、data structures - Difference between “Complete binary tree”, “strict binary tree”,”full binary Tree”? - Stack Overflow
https://stackoverflow.com/questions/12359660/difference-between-complete-binary-tree-strict-binary-tree-full-binary-tre
10、数据结构 - 图的基本术语 - CSDN博客
https://blog.csdn.net/wangzi11322/article/details/45417081
11、《图论》——图的存储与遍历(Java) - CSDN博客
https://blog.csdn.net/Gamer_gyt/article/details/51498546
12、Java 与图 - 简书
https://www.jianshu.com/p/a47a147ec92c
13、DFS(深度优先搜索)和BFS(广度优先搜索) - 简书
https://www.jianshu.com/p/b086986969e6

如果本文对您有所帮助,且您手头还很宽裕,欢迎打赏赞助我,以支付网站服务器和域名费用。 https://paypal.me/wshunli 您的鼓励与支持是我更新的最大动力,我会铭记于心,倾于博客。
本文链接:https://www.wshunli.com/posts/850e5c53.html