Java数据结构与算法----数组与链表
数据类型
5.1 单链表介绍
5.2 链表的创建
5.3 节点的修改
5.4 节点的删除
5.5 代码实现
5.6 单链表面试题
5.6.1 求单链表中有效节点的个数
5.6.2 查找单链表中的倒数第k个节点
5.6.3 从尾到头打印单链表（反向遍历）
4.1 思路分析
4.2 注意
4.3 代码实现
3.1 队列介绍
3.2 数组模拟队列
3.3 思路分析
3.4 代码实现
3.5 存在的问题
2.1 引入实例
2.2 稀疏数组的基本介绍
2.3 应用实例
2.4 思路分析
1 数据类型介绍
2 数据类型之——稀疏数组
3 单向队列
4 数组模拟队列的改进——环形队列
5 单链表
数据类型
1 数据类型介绍
数据类型的分类（按照结构划分）：线性结构和非线性结构
线性结构：
线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系
线性结构有两种不同的存储结构，即顺序存储结构（数组）和 链式存储结构（链表），顺序存储的线性表为顺序表，顺序表中存储的元素是连续的
链式存储结构的线性表称为链表，链表中的存储的元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息
吸纳行结构常见的有：数组，队列，链表，栈
非线性结构：
非线性结构包括：二维数组，多维数组，广义表，树结构，图结构
2 数据类型之——稀疏数组
2.1 引入实例
分析问题：因为该二维数组的很多值都是默认值0，因此记录了很多没有意义的数据，所以要用到稀疏数组来节省空间
2.2 稀疏数组的基本介绍
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组
稀疏数组的处理方式是：
记录数组一共有几行几列，有多少个不同的值
把具有不同值的元素的行列和值记录在一个小规模的数组中，从而缩小程序的规模
3
2.3 应用实例
使用稀疏数组来保存类似前面的二维数组（棋盘，地图等）
把稀疏数组存盘，并且可以重新恢复原来的二维数组
2.4 思路分析
二维数组转稀疏数组的思路
1） 遍历原始的二维数组，得到有效数据的个数 sum
2） 根据sum就可以创建稀疏数组 sparsArr int[sum + 1][3]
3） 将二维数组的有效数据存入到稀疏数组稀疏数组转原始的二维数组的思路
1） 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的chessArr = int[11][11]
2） 再读取稀疏数组后面几行的内容，并赋给原始的二位数组即可
public class SparseArray { public static void main(String[] args) { //创建一个棋盘（原始的二维数组11*11） //0：表示没有棋子，1：表示黑色棋子，2：表示蓝色棋子 int[][] chessArr = new int[11][11]; chessArr[1][2] = 1; chessArr[2][3] = 2; chessArr[4][5] = 2; //输出原始的二维数组 System.out.println('原始的二维数组'); for (int[] row : chessArr) {//对二维数组中的整行遍历 for (int data : row) { System.out.printf('%d\t', data); } System.out.println(); } //将二维数组转稀疏数组的思想 //1.先遍历二维数组，得到非0数据的个数 int sum = 0; for (int[] row : chessArr) { for (int data : row) { if (data != 0) { sum++; } } } System.out.println('sum=' + sum); //创建对应的稀疏数组 int[][] sparsArr = new int[sum + 1][3]; //给稀疏数组赋值 sparsArr[0][0] = chessArr.length; sparsArr[0][1] = chessArr[0].length; sparsArr[0][2] = sum; //遍历二维数组，将非0的值存放到稀疏数组中 int count = 1;//计数器，用于记录是第几个非零数据 for(int i = 0; i<chessArr.length; i++){ for (int j =0; j<chessArr[0].length;j++){ if (chessArr[i][j]!=0){ sparsArr[count][0] = i; sparsArr[count][1] = j; sparsArr[count][2] = chessArr[i][j]; count++; } } } //输出稀疏数组 System.out.println('稀疏数组'); for (int[]row:sparsArr){ for (int data:row){ System.out.printf('%d\t',data); } System.out.println(); } System.out.println('还原的二维数组'); //将稀疏数组恢复成原始的二维数组 //1.根据sparsArr第一行创建二维数组 int[][] chessArr2 = new int[sparsArr[0][0]][sparsArr[0][1]]; //2.再读取稀疏数组的后几行的数据（从第二行开始），并赋值给新的二维数组即可 for (int i = 1; i<=sparsArr[0][2];i++){ chessArr2[sparsArr[i][0]][sparsArr[i][1]] = sparsArr[i][2]; } for (int[] row:chessArr2){ for (int data:row){ System.out.printf('%d\t',data); } System.out.println(); } }}3 单向队列
3.1 队列介绍
队列是一个有序列表，可以用
数组
或是
链表
来实现
遵循
先入先出
的原则，即：先存入队列的数据要先取出，后存入的要后取出
示意图（用数组模拟队列）
3.2 数组模拟队列
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如上图所示，其中maxSize是该队列的最大容量
因为队列的输出、输入是分别从前后端来处理的，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，rear会随着数据的插入而改变
3.3 思路分析
我们将数据存入队列的时候称为“addQueue”，addQueue的处理需要有两个步骤
将尾指针（rear）往后移: rear + 1 （队列为空时：rear == front）
若为指针rear小于队列的最大下标，maxSize-1， 则将数据存入rear所指的数组元素中，否则无法存入数据。（队列满时：rear == maxSize-1）
3.4 代码实现
import java.util.Scanner;public class ArrayQueueDemo { public static void main(String[] args) { ArrayQueue arrayQueue = new ArrayQueue(5); Scanner s = new Scanner(System.in); boolean loop = true; while (loop){ System.out.println('a(add):添加数据'); System.out.println('g(get):得到数据'); System.out.println('s(show):显示数据'); System.out.println('q(quit):退出程序'); char text = s.next().charAt(0); switch (text){ case 'a': System.out.println('请输入要添加的数据'); arrayQueue.addQueue(s.nextInt()); break; case 'g': try{ System.out.println('得到的数据为'); arrayQueue.getQueue(); }catch (Exception e){ System.out.println(e.getMessage()); } break; case 's': arrayQueue.show(); break; case 'q': s.close();//关闭输入器防止异常 loop = false; break; } } }}//创建数组队列类class ArrayQueue{ private int maxSize;//表示数组的最大容量 private int front;//头指针 private int rear;//尾指针 private int[] arr;//该数组用于存放数据，模拟队列 //创建数组队列的构造器 public ArrayQueue(int maxSize){ this.maxSize = maxSize; this.arr = new int[maxSize]; front = -1;//指向队列头部，分析出front是指向队列头的前一个位置 rear = -1;//指向队列尾部，指向队列尾（即队列最后一个数据） } //判断队列是否为空 public boolean isEmpty(){ return front == rear; } //判断队列是否满了 public boolean isFull(){ return rear == maxSize - 1; } //向队列中添加数据 public void addQueue(int n){ //如果满了则输出异常不添加数据 if (isFull()){ System.out.println('错误：队列已满不能再添加'); return; } //没满，则指针后移，向指针所指的格子中添加数据 rear++; arr[rear] = n; } //从队列中获得数据 public int getQueue(){ //如果队列是空的，抛出异常 if (isEmpty()){ throw new RuntimeException('队列是空的，不能取出数据'); } //指针后移返回数据 front++; return arr[front]; } //将队列格式化输出 public void show(){ if (isEmpty()){ System.out.println('队列是空的，没有数据'); return; } for (int i = 0; i<arr.length;i++){ System.out.printf('arr[%d] = %d\n',i,arr[i]); } }}
3.5 存在的问题
目前数组使用一次就不能继续用了，没有达到复用的效果，造成了空间浪费
将这个数组使用算法，改进成一个环形队列（用取模的方式%）
（类比钟表：maxSize为12）
4 数组模拟队列的改进——环形队列
4.1 思路分析
对front变量的含义做一个调整：front就指向队列的第一个元素，也就是说arr[front] 就是队列的第一个元素
front的初始值为0
对rear变量的含义做一个调整：rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间（
rear指向的空间
）做约定（该约定用来判断队列是不是满了）
rear 的初始值是0
当队列满时，条件为 (rear + 1)%maxSize == front【满了】
（该条算法是在判断rear节点的下一个节点是不是front，如果是，则这个环形队列满了)队列为空的条件是：rear == front【空的】
当我们这样分析，队列中的有效的数据个数(rear+maxSize-front)%maxSize
(类似于钟表，5点和16点在表盘上差了几点：(5+12-16)%12 = 1)
环形队列示意图
以上图片来源My-Sun-Shine
4.2 注意
约定的位置（内容永远为空的位置，最后一个数据位的下一个位置） 是在动态变化的，永远位于最后一个元素的后一个位置
（注意：环形队列是放不满的（在当前算法下），一定会有一个空余的位置）addQueue时和单向队列的区别
1）单向队列：先后移，再插入数据（rear指向的位置永远是有数据的）
2）环形队列：先插入数据，再后移（rear指向的位置永远是空的）getQueue时和单向队列的区别：
1）单向队列：front++，返回arr[front]（front的初始值是-1）
2）环形队列：返回arr[front]，front++（front的初始值是0）show（）和单向队列的区别
1）单向队列：从i=0，遍历到i=arr.length()（将数据全部打印出）
2）环形队列：从i=front，遍历到 i=front+size，（左闭右开）
（其中size = (rear + maxSize -front)%maxSize）isFull和单向队列的区别：
1）单向队列：rear == masSize-1
2）环形队列：(rear+1)%maxSize ==front
（rear的下一个元素是front，则说明该队列满了）环形队列满的条件
环形队列空的条件
以上图片来源My-Sun-Shine
4.3 代码实现
import java.util.Scanner;public class CircleArrayQueueDemo { public static void main(String[] args) { CircleArrayQueue circleArrayQueue = new CircleArrayQueue(5);//说明：设置4，但是有效数据最大是3，有一个空间是作为约定的 Scanner s = new Scanner(System.in); boolean loop = true; while (loop) { System.out.println('a(add):添加数据'); System.out.println('g(get):得到数据'); System.out.println('s(show):显示数据'); System.out.println('q(quit):退出程序'); System.out.println('h(head):查看队列的第一个数据'); char text = s.next().charAt(0); switch (text) { case 'a': System.out.println('请输入要添加的数据'); circleArrayQueue.addQueue(s.nextInt()); break; case 'g': try { System.out.println('得到的数据为' + circleArrayQueue.getQueue()); } catch (Exception e) { System.out.println(e.getMessage()); } break; case 's': circleArrayQueue.show(); break; case 'q': s.close();//关闭输入器防止异常 loop = false; break; case 'h': circleArrayQueue.headQueue(); break; } } }}//创建数组队列类class CircleArrayQueue { private int maxSize;//表示数组的最大容量 private int front;//头指针 private int rear;//尾指针 private int[] arr;//该数组用于存放数据，模拟队列 //创建数组队列的构造器 public CircleArrayQueue(int maxSize) { this.maxSize = maxSize; this.arr = new int[maxSize]; front = 0;//指向队列头部，即队列的第一个元素 rear = 0;//指向队列尾部，指向队列尾的后一个数据 } //判断队列是否为空 public boolean isEmpty() { return front == rear; } //判断队列是否满了 public boolean isFull() { //如果尾指针的下一个元素是front，则满了 return (rear + 1) % maxSize == front; } //向队列中添加数据 public void addQueue(int n) { //如果满了则输出异常不添加数据 if (isFull()) { System.out.println('错误：队列已满不能再添加'); return; } //没满，向当前位置所指的格子中添加数据(因为rear所指的格子是空的) arr[rear] = n; //指针后移 rear = (rear + 1) % maxSize;//防止出界 } //从队列中获得数据 public int getQueue() { //如果队列是空的，抛出异常 if (isEmpty()) { throw new RuntimeException('队列是空的，不能取出数据'); } //这里需要分析出front是指向队列的第一个元素 //先输出，再后移front //1. 先把front对应的值保留到一个临时变量 //2. 将front后移 //3. 将临时变量返回 int temp = arr[front]; front = (front + 1) % maxSize; return temp; } //将队列格式化输出 public void show() { if (isEmpty()) { System.out.println('队列是空的，没有数据'); return; } //思路：从front开始遍历，遍历多少个元素 for (int i = front; i < front + (rear - front + maxSize) % maxSize; i++) { System.out.printf('arr[%d] = %d\n', i % maxSize, arr[i % maxSize]); } } //显示队列的头数据，不是取出数据 public int headQueue() { if (isEmpty()) { throw new RuntimeException('队列是空的，没有数据'); } return arr[front]; }}5 单链表
5.1 单链表介绍
链表是有序的列表，但是它在内存中的存储如下
（实际在内存中的存储）
逻辑结构示意图如下
总结
链表是以结点的方式来存储的，链式存储
每个节点包含data域，next域：指向下一个节点
如图：发现在内存中链表的各个节点不一定是有序存储的
链表分带头节点和不带头结点的链表，根据实际需求来确定
5.2 链表的创建
按顺序直接在尾部添加
每个节点中的内容
添加（创建）的过程
1）先创建一个head头节点，作用是表示单链表的头（标明此链表的头部位置）
2）后面我们每添加一个节点，就直接加入到链表的最后
3）遍历：通过一个辅助节点遍历，帮助遍历整个链表按照编号顺序添加
根据排名将英雄插入到指定的位置，（如果该位置已经存在英雄，则添加失败）思路：
1）首先找到新添加的节点位置，是通过辅助变量（指针）找到的，通过遍历得到
2）新的节点.next = temp.next
3）temp.next = 新的节点
5.3 节点的修改
通过辅助（指针）遍历链表，发现节点内部编号相等，则与新的节点内容进行互换
5.4 节点的删除
思路：
我们先找到需要删除的节点的前一个结点
temp.next = temp.next.next
（不用考虑被删除的节点是最后一个的情况，temp.next = null和temp.next.next 在这种情况下是一样的）被删除的节点，将不会有其他的引用所指向，会被GC回收
5.5 代码实现
public class SingleLinkedListDemo { public static void main(String[] args) { //测试 //先创建节点 HeroNode hero1 = new HeroNode(1, '宋江', '及时雨'); HeroNode hero2 = new HeroNode(2, '卢俊义', '玉麒麟'); HeroNode hero3 = new HeroNode(3, '吴用', '智多星'); HeroNode hero4 = new HeroNode(4, '林冲', '豹子头'); //创建链表 SingleLinkedList singleLinkedList = new SingleLinkedList(); singleLinkedList.addByOrder(hero1); singleLinkedList.addByOrder(hero2); singleLinkedList.addByOrder(hero2); singleLinkedList.add(hero3); singleLinkedList.add(hero4); singleLinkedList.List(); singleLinkedList.delete(hero4); singleLinkedList.delete(hero3); singleLinkedList.delete(hero2); singleLinkedList.delete(hero1); System.out.println('删除后'); singleLinkedList.List(); }}class SingleLinkedList { //先初始化一个头结点，头节点不要动，不要存放具体的数值 HeroNode head = new HeroNode(0, '', ''); //添加节点到单向链表 //思路：当不考虑编号顺序时 //1. 找到当前链表的最后节点 //2. 将最后这个节点的next指向新的节点 public void add(HeroNode heroNode) { //因为head节点不能动，因此我们需要一个辅助遍历temp HeroNode temp = head; //遍历链表找到最后一个节点 while (true) { //找到最后一个节点，终止循环 if (temp.next == null) { break; } //如果没有找到，将temp向后移动 temp = temp.next; } //while退出时，temp已经指向的最后的节点 temp.next = heroNode; } public void addByOrder(HeroNode heroNode) { //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置 //因为单链表，因此我们找到的temp是位于添加位置的前一个结点，否则插入不进去 HeroNode temp = head;//辅助指针，初始值在head boolean flag = false;//标识：表示该插入的对象是否已经在链表中存在了，默认为false（没有存在） //遍历，从head开始到链表尾 while (true) { //如果已经在链表尾 if (temp.next == null) { break; } //如果找到位置，就在temp后面插入 if (temp.next.heroNo > heroNode.heroNo) {//temp的heroNo不大于，但是temp.next大于，说明插入位置在temp和temp.next之间 break;//找到位置，退出循环 } if (temp.next.heroNo == heroNode.heroNo) { flag = true;//说明该节点存在 break; } //如果以上条件都不满足，将temp后移 temp = temp.next; } //此时得到了一个flag值或者一个temp位置 //首先判断flag if (flag) { //说明该节点已经存在 System.out.printf('节点%d已经存在，不能再添加\n', heroNode.heroNo); } else { //该节点不存在的话，就在temp后面插入新的节点 heroNode.next = temp.next; temp.next = heroNode; } } //修改节点 public void update(HeroNode newHeroNode) { //首先确定一下链表是否为空 if (head.next == null) { System.out.println('链表为空，无法修改'); } //创建辅助结点来遍历链表 HeroNode temp = head.next; //创建flag变量，判断该节点是否找到 boolean flag = false; while (true) { //如果已经遍历到尾节点，终止 if (temp == null) { break; } if (temp.heroNo == newHeroNode.heroNo) { //找到该节点 flag = true; break; } else { temp = temp.next; } } //循环结束后通过flag值判断是否修改 if (flag) { temp.heroName = newHeroNode.heroName; temp.nickName = newHeroNode.nickName; //next和no都不用变 } else { System.out.printf('没有编号为%d的节点,无法修改\n', newHeroNode.heroNo); } } //删除节点 //思路： //1.head不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点 //2.说明我们在比较时，是temp.next.heroNo 和要删除的节点的heroNo比较 public void delete(HeroNode delHeroNode) { //如果链表为空，无法删除 if (head.next == null) { System.out.println('链表为空，无法删除\n'); return; } //构建辅助节点，帮忙遍历链表 HeroNode temp = head; //flag表示是否找到该节点的前一位，默认为false boolean flag = false; while (true) { //如果遍历到最后一位，说明该节点不存在，终止循环 if (temp.next == null) { break; } if (temp.next.heroNo == delHeroNode.heroNo) { //找到了要删除的节点的上一位 flag = true; break; } else { //没有找到，继续往后走 temp = temp.next; } } //循环终止后通过判断flag值决定是否删除节点 if (flag) { //如果要删除的节点在最后一位，则将上一位的next指向null /*if (temp.next.next==null){ temp.next = null; } else { //要删除的节点不在最后一位 temp.next = temp.next.next; }*/ //如果要删除的节点在最后一位，则temp.next.next本身就等于null，以上两种情况可以合并 temp.next = temp.next.next; } else { System.out.printf('没有编号为%d的节点，无法删除\n', delHeroNode.heroNo); } } public void List() { //判断链表是否为空 if (head.next == null) { System.out.println('链表为空'); return; } //因为头节点不能动，所以需要一个辅助节点来遍历 HeroNode temp = head.next; while (true) { //判断是否到链表最后 if (temp == null) { break; } //如果还没有遍历到最后 System.out.println(temp); //将temp后移 temp = temp.next; } }}//定义HeroNode，每一个HeroNode对象就是一个节点class HeroNode { public int heroNo; public String heroName; public String nickName; HeroNode next; public HeroNode(int heroNo, String heroName, String nickName) { this.heroNo = heroNo; this.heroName = heroName; this.nickName = nickName; } //为了显示方法，我们重写toString public String toString() { return 'HeroNode [no = ' + heroNo + ', name = ' + heroName + ', nickname = ' + nickName + ']'; }}
5.6 单链表面试题
5.6.1 求单链表中有效节点的个数
韩老师的方法写在了测试类中，为静态方法：
/** * * @param head 链表的头节点 * @return 返回链表的长度 */ public static int getLength(HeroNode head){ //空链表 if (head.next == null){ return 0; } int result = 0; //辅助接点遍历，将头节点排除在外 HeroNode cur = head.next; while (cur!=null){ result++; cur = cur.next; } return result; }//同时因为head为SingleLinkedList类中的private属性，所以在SingleLinkedList中添加一个getter方法public HeroNode getHead() { return head; } //==========================我写在了SingleLinkedList类中，为实例方法，不需要参数，可以直接使用对象调用
//方法：获取单链表的节点的个数（如果是带头节点的，需要不统计头节点） public int getLength2(){ int result = 0; HeroNode temp = head; while (true){ if (temp.next == null){ break; } temp = temp.next; result++; } return result; }
我感觉在实际情况中，韩老师的方法更对一些，因为SingleLinkedList在实际应用情况下是封装好的，外部是不能够更改内部的，所以应该用外部的方法取实现要求。
5.6.2 查找单链表中的倒数第k个节点
思路：
编写一个方法，接受head节点，同时接受一个index
index表示是倒数第index个节点
先把链表从头到尾遍历，得到链表的总长度getLength
得到size之后，我们从链表的第一个节点（非head）开始遍历（size-index）个，就可以得到
如果找到了，则返回该节点，否则返回null
示意图
代码示例：
/** * * @param head 链表的头节点 * @param k * @return 返回倒数第K个节点 */ public static HeroNode findLastKNode(HeroNode head, int k){ //如果链表为空，返回null if (head.next == null){ return null; } //找到链表的长度 int length = getLength(head); //先做一个index校验 if ( k <= 0 || k > length){ return null; } //辅助节点帮助遍历 HeroNode cur = head.next; //遍历K次 for (int i = 0; i < length - k; i++) { cur = cur.next; } return cur; }5.6.3 从尾到头打印单链表（反向遍历）
思路：
方式1：先将单链表进行反转操作，然后再遍历即可，但是这样做的问题会破坏原来的单链表的结构，不建议
方式2：利用栈数据结构，将各个节点压入到栈中，利用栈的先进后出的特点实现了逆序打印的效果