Java数据结构与算法

置顶 | | ， | | | 3.1k

学习总结:尚硅谷2019java数据结构和算法

线性结构和非线性结构


线性结构

  • 是一个有序数据元素的集合。 其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
  • 常用的线性结构有：线性表，栈，队列，双队列，数组，串。
  • 特点：
    • 1．集合中必存在唯一的一个”第一个元素”；
    • 2．集合中必存在唯一的一个”最后的元素”；
    • 3．除最后元素之外，其它数据元素均有唯一的”后继”；
    • 4．除第一元素之外，其它数据元素均有唯一的”前驱”。
    • 5．数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。

非线性结构

  • 各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。
  • 根据关系的不同，可分为层次结构和群结构。
  • 常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。（其中多维数组是由多个一维数组组成的，所以不再是线性结构）
  • 特点：
    • 非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后继

稀疏数组和队列

稀疏数组

  • 稀疏数组介绍

  • 图示

  • 应用实例


  • 代码实现

    • SparseArray.java：与二维数组的转换，包括二维转稀疏，和稀疏转二维。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      package cn.blue;

      import java.util.Arrays;
      import java.util.stream.IntStream;

      /**
       * @author Blue
       * 稀疏数组思路分析：与二维数组的转换，包括二维转稀疏，和稀疏转二维
       */
      public class SparseArray {

          public static void main(String[] args) {
              //创建一个原始的二维数组11*11: 0：没有棋子，1表示黑子，2表示蓝子
              int[][] chessArr1 = new int[11][11];
              chessArr1[1][2] = 1;
              chessArr1[2][3] = 2;
              chessArr1[4][5] = 2;

              //输出原始的二维数组
      //        int[] arr = new  int[]{1,2,3};
      //        System.out.println(Arrays.toString(arr));
      //        System.out.println(Arrays.deepToString(chessArr1));

              //输出原始的二维数组
              System.out.println("原始的二维数组：");
              for (int[] row : chessArr1) {
                  for (int data : row) {
                      System.out.printf("%d\t", data);
                  }
                  System.out.println();
              }

              //将二维数组 转 稀疏数组
              //1、先遍历二维数组，得到非0数据的个数
              int sum = 0;
              for (int i = 0; i < chessArr1.length; i++) {
                  for (int j = 0; j < chessArr1[i].length; j++) {
                      if (chessArr1[i][j] != 0) {
                          sum++;
                      }
                  }
              }
              System.out.println("输出的值个数" + sum);

              //2、创建对应的稀疏数组
              int[][] sparseArr = new int[sum + 1][3];
              //给稀疏数组列中的行赋值
              sparseArr[0][0] = chessArr1.length;
              //给稀疏数组列中的列赋值
              sparseArr[0][1] = chessArr1[0].length;
              //给稀疏数组列中的值赋值
              sparseArr[0][2] = sum;
              System.err.println("赋值第一行后的稀疏数组：" + Arrays.deepToString(sparseArr));

              //2.遍历二维数组，将非0的值存放到稀疏数组中。
              //用于记录是第几个非0数据
              int count = 0;
              for (int i = 0; i < chessArr1.length; i++) {
                  for (int j = 0; j < chessArr1[i].length; j++) {
                      if (chessArr1[i][j] != 0) {
                          count++;
                          sparseArr[count][0] = i;
                          sparseArr[count][1] = j;
                          sparseArr[count][2] = chessArr1[i][j];
                      }
                  }
              }
              System.err.println("赋值后的稀疏数组：" + Arrays.deepToString(sparseArr));

              //输出稀疏数组的完整样式
              System.err.println("======输出稀疏数组的完整样式: sparseArr.length == 4,获取的是二维数组的列数长度");
              //1.
              IntStream.range(0, sparseArr.length).forEach(i ->
                      System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]));
              //2.
              for (int[] sparse : sparseArr
              ) {
                  System.out.println(Arrays.toString(sparse));
              }
              //3.
              int k = 0;
              while (k < sparseArr.length) {
                  System.out.printf("%d\t%d\t%d\t\n", sparseArr[k][0], sparseArr[k][1], sparseArr[k][2]);
                  k++;
              }
              //4.
              for (int i = 0; i < sparseArr.length; i++) {
                  System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
              }

              //将稀疏数组 转 二维数组：读取稀疏数组的行列
              int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
              //再读取稀疏数组后几行的数组，并赋给原始的二维数组即可。
              for (int i = 1; i < sparseArr.length; i++) {
                  chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
              }
              System.out.println("换成二维数组后的：" + Arrays.deepToString(chessArr2));

              //输出还原后的二维数组
              int i = 0;
              while (i < chessArr2.length) {
                  for (int j = 0; j < chessArr2[i].length; j++) {
                      System.out.printf("%d\t" , chessArr2[i][j]);
                  }
                  System.out.println();
                  i++;
              }
          }
      }
  • 代码总结
    • 二维数组.length == 二维数组列的长度
    • 使用占位符输出System.out.printf(“%d\t” , 值);

  • 课后练习

队列

  • 引入

    • 先进先出，有序列表
    • 可用数组或链表实现。数组（顺序存储），链表（链式存储）。
    • 图示：使用数组模拟队列

  • 数组模拟队列

    • 问题：
      • 目前数组不能复用，一次性。
      • 使用取模的环形队列来改进
    • 代码实现：
      ArrayQueueDemo.java：用数组实现队列的五个小功能，并通过主函数验证(因为还不是环形队列，存在一些缺陷）

  • 数组模拟环形队列

    • 分析
      • 重新设置rear和front的初始值均为0，且front指向第一个元-素，rear指向最后一个元素的后一个位置，并且预留一个空格-的位置，即若只剩一个空，视为满。
      • 队满：(rear+1)%maxSize == front;
      • 队空：rear==front
      • 元素个数：(rear-front+maxSize)%maxSize
    • 图示

    • 代码实现
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      63
      64
      65
      66
      67
      68
      69
      70
      71
      72
      73
      74
      75
      76
      77
      78
      79
      80
      81
      82
      83
      84
      85
      86
      87
      88
      89
      90
      91
      92
      93
      94
      95
      96
      97
      98
      99
      100
      101
      102
      103
      104
      105
      106
      107
      108
      109
      110
      111
      112
      113
      114
      115
      116
      117
      118
      119
      120
      121
      122
      123
      124
      125
      126
      127
      128
      129
      130
      131
      132
      133
      134
      135
      136
      137
      138
      139
      140
      141
      142
      143
      144
      145
      146
      147
      148
      149
      150
      151
      152
      153
      154
      155
      156
      157
      158
      159
      160
      package cn.blue;


      import java.util.Scanner;

      /**
      * @author Blue
      * @date 2020/1/10
      * 队列：
      * 重新设置rear和front的初始值均为0，且front指向第一个元素，rear指向最后一个元素的后一个位置，并且预留一个空格的位置，
      * 即若只剩一个空，视为满。
      * 队满：(rear+1)%maxSize == front;
      * 队空：rear==front
      * 元素个数：(rear-front+maxSize)%maxSize
      **/
      public class ArrayQueueDemo {
          public static void main(String[] args) {
              //创建一个队列
              ArrayQueue arrayQueue = new ArrayQueue(3);
              //用来接收输入的值
              char value = ' ';
              Scanner scanner = new Scanner(System.in);
              boolean loop = true;
              while (loop) {
                  System.out.println("s(show)：显示队列");
                  System.out.println("a(add)：添加数据到队列");
                  System.out.println("g(get)：从队列中获取元素");
                  System.out.println("h(head)：查看队列头的数据");
                  System.out.println("e(exit)：退出程序");
                  System.err.println("请选择如下的操作:");
                  value = scanner.next().charAt(0);
                  switch (value) {
                      case 's':
                          arrayQueue.showQueue();
                          break;
                      case 'a':
                          System.err.print("请输入需要添加的值：");
                          int addValue = scanner.nextInt();
                          arrayQueue.addQueue(addValue);
                          break;
                      case 'g':
                          try {
                              int res = arrayQueue.getQueue();
                              System.out.printf("取出的数据是%d\n",res);
                          } catch (Exception e) {
                              System.out.println(e.getMessage());
                          }
                          break;
                      case 'h':
                          try {
                              int res = arrayQueue.showHead();
                              System.out.printf("取出的数据是%d\n",res);
                          } catch (Exception e) {
                              System.out.println(e.getMessage());
                          }
                          break;
                      case 'e':
                          System.exit(0);
                          loop = false;
                          break;
                      default:
                          break;
                  }
              }
          }
      }

      package cn.blue;

      /**
      * @author Blue
      * @date 2020/1/10
      **/
      public class ArrayQueue {
          /**
          * 数组的最大容量
          */
          private int maxSize;
          /**
          * 队列头
          */
          private int front;
          /**
          * 队列尾
          */
          private int rear;
          /**
          * 用于存放数据
          */
          private int[] arr;

          public ArrayQueue(int capacity) {
              maxSize = capacity;
              arr = new int[maxSize];
              // 指向队列头部，分析出front是指向队列头的前一个位置
              front = -1;
              //指向队列尾，指向队列尾的数据（即队列最后一个数据）
              rear = -1;

          }

          public boolean isEmpty() {
              return front == rear;
          }

          public boolean isFull() {
              return rear == maxSize - 1;
          }

          /**
          * 添加数据到队列
          */
          public void addQueue(int value) {
              if (isFull()) {
                  System.err.println("队列已满，不能加入数据");
                  return;
              }
              rear++;
              arr[rear] = value;
          }


          /**
          * @return 获得队列的数据
          */
          public int getQueue() {
              if (isEmpty()) {
                  throw new RuntimeException("队列数据不能为空");
              }
              //front后移,出列
              front++;
              return arr[front];
          }

          /**
          * 显示队列的所有数据
          */
          public void showQueue() {
              //判断是否是空的
              if (isEmpty()) {
                  System.err.println("目前队列数据为空，请先添加");
                  return;
              }
              //遍历
              for (int i = 0; i < arr.length; i++) {
                  System.err.printf("arr[%d]=%d\n", i, arr[i]);
              }
          }

          /**
          * 显示队列的头数据，注意不是取出
          */
          public int showHead() {
              if (isEmpty()) {
                  throw new RuntimeException("队列数据不能为空");
              }
              //注意：front指向的是队列头的前一个数据。（更小的一个位置）
              return arr[front + 1];
          }
      }
      以上代码实现只能带我们初步认识队列，具体参考

链表

链表(LinkedList)介绍

链表是有序的列表，但是它在内存中是存储如下

小结:

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含 data 域， next 域：指向下一个节点.
  3. 如图：发现链表的各个节点不一定是连续存储.
  4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表

单链表介绍

单链表(带头结点) 逻辑结构示意图如下

单链表的应用实例

使用带head头的单向链表实现 –水浒英雄排行榜管理 完成对英雄人物的增删改查操作

解题思路:

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
package com.company;

import java.util.LinkedList;

/**
 * @author Blue
 * 单链表的应用实例
 * 使用带head头的单向链表实现 –水浒英雄排行榜管理 完成对英雄人物的增删改查操作
 */
public class SingleLinkedListDemo {

    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "鲁智深", "花和尚");
        HeroNode heroNode2 = new HeroNode(2, "李逵", "黑旋风");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(heroNode1);
        singleLinkedList.addByOrder(heroNode4);
        singleLinkedList.addByOrder(heroNode2);
        singleLinkedList.addByOrder(heroNode3);
        singleLinkedList.list();
        HeroNode heroNode5 = new HeroNode(4, "smile", "豹子头~~");
        System.out.println("修改后的链表");
        singleLinkedList.update(heroNode5);
        singleLinkedList.list();
    }


    static class SingleLinkedList {
        //创建一个空的头结点：头结点的Data域可以不设任何信息，也可以记录表长等相关信息
        private HeroNode head = new HeroNode(0, " ", " ");

        //返回头结点
        public HeroNode getHead() {
            return head;
        }

        //链表按序号顺序添加数据
        public void addByOrder(HeroNode node) {
            HeroNode temp = head;
            //标示编号是否存在
            boolean flag = false;
            while (true) {
                //用来判断链表是否为空，已经如果现有链表中没有比要插入的数据大的id，可以通过此来跳出循环
                if (temp.getNext() == null) {
                    break;
                }
                if (temp.getNext().getId() > node.getId()) {
                    // 1 ,3 , 2, 4.由于1小于3，故插入在1 2 之间
                    break;
                } else if (temp.getNext().getId() == node.getId()) {
                    flag = true;
                    break;
                }
                temp = temp.getNext();
            }
            if (flag) {
                //链表为空
                System.out.printf("准备插入的英雄编号%d已经存在，不能插入", head.getId());
            } else {
                node.setNext(temp.getNext());
                temp.setNext(node);
            }
        }

        //展示链表所有数据
        public void list() {
            //判断链表是否为空
            if (head.getNext() == null) {
                System.out.println("链表为空");
                return;
            }
            HeroNode temp = head.getNext();
            while (true) {
                if (temp == null) {
                    System.out.println("遍历结束");
                    break;
                }
                System.out.println(temp);
                temp = temp.getNext();
            }
        }

        //修改链表存在的数据
        public void update(HeroNode node) {
            HeroNode temp = head.getNext();
            boolean flag = false;
            while (true) {
                if(temp == null){
                    //遍历结束
                    System.out.println("没有找到该节点");
                    break;
                }
                if (temp.getId() == node.getId()) {
                    //链表中已存在相同编号的数据
                    flag = true;
                }
                if (flag) {
                    temp.setId(node.getId());
                    temp.setName(node.getName());
                    temp.setNikeName(node.getNikeName());
                    break;
                }
                temp = temp.getNext();
            }
        }
    }

    /**
     * 节点对象
     */
    static class HeroNode {
        /**
         *
         */
        private int id;
        private String name;
        private String nikeName;
        /**
         * 下一节点
         */
        private HeroNode next;

        public HeroNode(int id, String name, String nikeName) {
            this.id = id;
            this.name = name;
            this.nikeName = nikeName;
        }

        public void setId(int id) {
            this.id = id;
        }

        public void setName(String name) {
            this.name = name;
        }

        public void setNikeName(String nikeName) {
            this.nikeName = nikeName;
        }

        public void setNext(HeroNode next) {
            this.next = next;
        }

        public int getId() {
            return id;
        }

        public String getName() {
            return name;
        }

        public String getNikeName() {
            return nikeName;
        }

        public HeroNode getNext() {
            return next;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    ", nikeName='" + nikeName + '\'' +
                    '}';
        }
    }
}

面试题

1.求单链表中有效节点的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int getLength(HeroNode head) {
    HeroNode temp = head;
    int count = 0;
    if (temp.getNext() == null) {
        return 0;
    }
    while (true) {
        if (temp == null) {
            break;
        }
        if (temp.getNext() != null) {
            count++;
        }
        temp = temp.getNext();
    }
    System.out.println("length: " + count);
    return count;
}

2.查找单链表中的倒数第k个结点 【新浪面试题】

  • 代码实现：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    /**
        * 查找单链表中的倒数第k个结点 【新浪面试题】
        * @param index 倒数第k个
        * @return 结点
        */
    public HeroNode getNodeByIndex(int index){
        HeroNode temp = head;
        int size = 0;
        while(true){
            if(temp.getNext() == null){
                break;
            }
            size++;
            temp = temp.getNext();
        }
        //校验给出的索引
        HeroNode node = head.getNext();
        if(index > size || index < 0){
            System.out.println("输入数据不合理");
            return null;
        }
        int cur = 0;
        HeroNode nodeByIndex = head.getNext();
        while (true){
            if(cur == size - index){
                return nodeByIndex;
            }
            if(nodeByIndex.getNext() == null){
                System.out.println("遍历结束，未找到索引对应的结点");
            }
            cur++;
            nodeByIndex = nodeByIndex.getNext();
        }
    }

3.单链表的反转【腾讯面试题，有点难度】

  • 代码实现:
    1
    2


相关文章
点击查看

本文标题:Java数据结构与算法

文章作者:Liuyang

发布时间:2020年01月09日 - 23:40:28

最后更新:2020年01月14日 - 09:43:59

原始链接:http://yoursite.com/2020/01/09/Java%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%