Java基础知识(十)

Author Avatar
子语 2017 - 10 - 18
  • 在其它设备中阅读本文章

链表

链表是引用的加强应用.
知识点前提:依赖于引用传递;this表示当前对象。

链表基本概念

1.链表是一种简单的数据结构,功能是依靠引用关系实现多个数据的保存。
无法加载
根据上图编写代码:

要求:定义一个Node类,保存String类型数据,同时拥有下一个节点的引用。

  1. // 每个链表由多个节点组成
  2. class Node { // 定义节点类
  3. private String data; // 要保存的数据
  4. private Node next; // 要保存的下一个节点
  5. // 每个Node对象都必须保存相应的数据
  6. public Node(String data) { // 有数据才有Node
  7. this.data = data;
  8. }
  9. public void setNext(Node next) {
  10. this.next = next;
  11. }
  12. public Node getNext() {
  13. return this.next;
  14. }
  15. public String getData() {
  16. return this.data;
  17. }
  18. }

Node类专门负责保存节点关系,需要其他类负责Node之间的关系匹配。
范例:使用循环取出数据

  1. public class Demo {
  2. public static void main(String[] args) {
  3. // 1. 设置数据
  4. Node root = new Node("火车头");
  5. Node n1 = new Node("车厢A");
  6. Node n2 = new Node("车厢B");
  7. root.setNext(n1);
  8. n1.setNext(n2);
  9. // 2. 取出数据
  10. Node currentNode = root; //从根节点开始读取数据
  11. while (currentNode != null) { // 当前节点存在数据
  12. System.out.println(currentNode.getData());
  13. // 将下一节点设置为当前节点
  14. currentNode = currentNode.getNext();
  15. }
  16. }
  17. }

利用循环取出数据不够便捷,应使用递归。
范例:使用递归取出数据

  1. public class Demo {
  2. public static void main(String[] args) {
  3. // 1. 设置数据
  4. Node root = new Node("火车头");
  5. Node n1 = new Node("车厢A");
  6. Node n2 = new Node("车厢B");
  7. root.setNext(n1);
  8. n1.setNext(n2);
  9. print(root);
  10. }
  11. public static void print(Node current){
  12. if (current == null){ // 节点不存在
  13. return ; // 结束方法调用
  14. }
  15. System.out.println(current.getData());
  16. print(current.getNext()); // 递归调用
  17. }
  18. }

因为循环次数未知,所以使用while循环。节点操作中,递归比while循环更直观。

问题:为什么要设置Node类
答:数据本身不具有先后关系,因此需要使用Node类封装份数据,同时利用Node类指向下一节点。

链表基本实现

通过分析发现:

(1)用户操作过程中,Node类应该是不可见的,即用户无需关注Node类的结构
(2)Node之间的关系不应该由用户定义,而应该由一个专门的类处理。

范例:定义Link类,隐藏Node类
程序要描述的步骤如下:
第一步:
无法加载
第二步:
无法加载
第三步:
无法加载
第四步:
无法加载

  1. // 处理Node对象间关系
  2. class Link {
  3. private Node root; // 根节点
  4. // 设置数据
  5. public void add(String data) {
  6. // 为了设置数据的先后关系,将data包装在Node对象中
  7. Node newNode = new Node(data);
  8. if (this.root == null) { // 保存数据时,根节点不存在
  9. // 该判断执行一次,因为链表只有一个根节点
  10. this.root = newNode; // 将新节点设置为根节点
  11. } else { // 根节点存在
  12. // 新节点应交给Node决定
  13. // 从root之后设置合适的位置
  14. this.root.addNode(newNode);
  15. }
  16. }
  17. // 输出数据
  18. public void print() {
  19. if (this.root != null) {
  20. this.root.printNode();
  21. }
  22. }
  23. }

范例:根据Link类,修改Node类

  1. class Node {
  2. private String data;
  3. private Node next;
  4. public Node(String data) {
  5. this.data = data;
  6. }
  7. public void setNext(Node next) {
  8. this.next = next;
  9. }
  10. public Node getNext() {
  11. return this.next;
  12. }
  13. public String getData() {
  14. return this.data;
  15. }
  16. // 添加节点
  17. // 第一次Link调用: this = link.root
  18. // 第二次Node调用:this = link.root.next
  19. // 第三次Node调用:this = link.root.next.next
  20. public void addNode(Node newNode) {
  21. if (this.next == null) { // 当前节点的next为空
  22. this.next = newNode; // 保存为新节点
  23. } else {
  24. // 当前节点的next的next继续保存
  25. this.next.addNode(newNode);
  26. }
  27. }
  28. // 第一次Link调用: this = link.root
  29. // 第二次Node调用:this = link.root.next
  30. // 第三次Node调用:this = link.root.next.next
  31. public void printNode() {
  32. System.out.println(this.data); // 输出当前节点数据
  33. if (this.next != null) { // 当前节点有next
  34. this.next.printNode(); // 输出next节点信息
  35. }
  36. }
  37. }

范例:测试

  1. public class Demo {
  2. public static void main(String[] args) {
  3. Link link = new Link(); // 负责数据操作
  4. // 增加数据
  5. link.add("火车头");
  6. link.add("车厢A");
  7. link.add("车厢B");
  8. // 输出数据
  9. link.print();
  10. }
  11. }

由上述代码可知链表操作的基本特点:

(1)对于客户端而言Node是不可见的,只能利用Link中的方法
(2)Link类的功能是控制Node对象的产生和根节点的使用;
(3)Node类的功能是保存数据以及配置引用关系。

可用链表基本结构

1.可用链表指的是能实现数据的增删改查的链表。
2.可用链表开发要求:Node类负责节点数据的保存以及节点关系的匹配,因此Node类不能被单独使用,即外部不能绕过Link去使用Node
范例:修改Node结构,使得Node类只能被Link类使用

思路:将Node类变为private定义的内部类。

  1. class Link { // 链表类,外部可见
  2. // Node定义在内部让其只为Link服务
  3. private class Node {
  4. private String data; // 保存数据
  5. private Node next; // 引用关系
  6. public Node(String data) {
  7. this.data = data;
  8. }
  9. }
  10. // ====================以上为内部类=====================
  11. private Node root; // 根节点
  12. }

上述代码即为可用链表的基本结构,后续为其增加功能代码。

增加数据功能

思路:数据的增加应由Link负责节点对象的产生,以及根节点的维护。节点间的关系匹配,由Node类处理。

范例:Node类中添加addNode(),Link类中添加add()

  1. // 设置关系
  2. public void addNode(Node newNode) {
  3. if (this.next == null) {
  4. this.next = newNode;
  5. } else {
  6. this.next.addNode(newNode);
  7. }
  8. }
  9. public void add(String data) {
  10. if (data == null) { // 输入数据为空
  11. return;
  12. }
  13. Node newNode = new Node(data); // 要保存的数据
  14. if (this.root == null) { // 根节点不存在
  15. this.root = newNode; // 设为根节点
  16. } else { // 根节点存在,交由Node处理
  17. this.root.addNode(newNode);
  18. }
  19. }

范例:测试

  1. public class Demo {
  2. public static void main(String[] args) {
  3. Link link = new Link();
  4. link.add("火车头");
  5. link.add("车厢A");
  6. link.add("车厢B");
  7. }
  8. }

获取链表长度

思路:每个链表对象都只有一个root,可以在Link类中设置count属性,随后每次添加数据后,count自增。

范例:修改Link类
(1)增加count属性:private int count = 0; // 节点的个数
(2)在add()添加统计节点个数的操作

  1. public void add(String data) {
  2. if (data == null) {
  3. return;
  4. }
  5. Node newNode = new Node(data);
  6. if (this.root == null) {
  7. this.root = newNode;
  8. } else { //
  9. this.root.addNode(newNode);
  10. }
  11. this.count++; // 每次增加节点,count+1
  12. }

(3)添加获取链表长度的方法size()

  1. public int size() {
  2. return this.count;
  3. }

(4)判断链表是否为空,有两种方式,一是判断root是否为null,二是判断count是否为0,在此采用第二种方式,在Link类中添加isEmpty()

  1. public boolean isEmpty() {
  2. return this.count == 0;
  3. }

内容查询

思路:判断链表中是否存在某数据,以String为例,仅需遍历链表中的数据,与要查询的数据记性匹配(使用equals(String str)),如果匹配成功返回true,反之返回false。
无法加载
根据上图编写代码:
(1)Link中添加contains()

  1. public boolean contains(String data) {
  2. if (data == null || root == null) {
  3. return false;
  4. }
  5. return this.root.containsNode(data);
  6. }

Link从root节点开始查询数据是否存在,数据不存在,Node开始查询非根节点。
(2)Node中添加containsNode()

  1. public boolean containsNode(String data) {
  2. if (data.equals(this.data)) { // 当前数据等于要目标数据
  3. return true; // 结束查询
  4. } else { // 当前数据不等于目标数据
  5. if (this.next != null) { // 有后续节点
  6. return this.next.containsNode(data);
  7. } else {
  8. return false;
  9. }
  10. }
  11. }

(3)测试

  1. public class Demo {
  2. public static void main(String[] args) {
  3. Link link = new Link();
  4. link.add("火车头");
  5. link.add("车厢A");
  6. link.add("车厢B");
  7. System.out.println(link.contains("火车头"));
  8. }
  9. }

案例中使用的是String类型数据,所以判断数据使用equals(String str)。如果判断的是自定义类型数据,就需要定义一个对象比较的方法,方法名暂定为compare()。

根据索引取得数据

链表中保存有多个对象。数组也可以保存多个对象。链表和数组相比优势在于没有长度限制。因此链表相当于一个动态对象数组,具备像数组那样根据索引取得元素的功能。
由于是动态对象数组,所以元素的索引也是动态生成的。
无法加载
根据上图,编写代码:
(1)Link中增加foot属性,表示Node的索引:private int foot = 0; // 索引
每次查询前,应该重置为0.链表查询数据前应先判断要查询的索引小于索引总数。

  1. public String get(int index) {
  2. if (index > this.count) { // 超出查询范围
  3. return null;
  4. }
  5. this.foot = 0;
  6. return this.root.getNode(index); // 查询交给Node类
  7. }

(2)Node定义getNode(),内部类和外部类间可以方便地进行私有属性的访问。

  1. public String getNode(int index) {
  2. // 当前foot内容与要查询的索引比较
  3. // foot自增,目的是下次查询方便
  4. if (Link.this.foot++ == index) {
  5. return this.data;
  6. } else {
  7. return this.next.getNode(index);
  8. }
  9. }

修改链表数据

修改和查询思路差不多,不同的是查询是当满足索引值时,返回数据;修改是满足索引时,对数据重新赋值。

(1)Link添加set(int index, String data)

  1. public void set(int index, String data) {
  2. if (index > this.count) {
  3. return;
  4. }
  5. this.foot = 0; // 重置foot,作为索引
  6. this.root.setNode(index, data); // Node进行修改数据
  7. }

(2)Node添加setNode(int index, String data)

  1. public void setNode(int index, String data) {
  2. if (Link.this.foot++ == index) {
  3. this.data = data;
  4. } else {
  5. this.next.setNode(index, data);
  6. }
  7. }

删除链表数据

删除链表数据应分为两种情况:
(1)要删除的是根节点,root.next()变为root,在Link中处理,因为由Link来维护root;
(2)要删除的是非根节点,当前节点的上一节点.next()=当前节点.next(),即空出了当前节点。非根节点应交由Node处理。

1.Node添加removeNode(Node previous, String data)

  1. public void removeNode(Node previous, String data) {
  2. // 参数中传递上一个节点和要删除的数据
  3. if (data.equals(this.data)) {
  4. previous.next = this.next;
  5. } else {
  6. this.next.removeNode(this, data);
  7. }
  8. }
  1. Link添加remove(String data)
  1. public void remove(String data) {
  2. if (this.contains(data)) { // 判断数据是否存在
  3. if (data.equals(this.root.data)) { // 判断数据是否是root数据
  4. this.root = this.root.next;
  5. } else {
  6. // root是Node对象,此处直接访问内部类私有操作
  7. this.root.next.removeNode(this.root, data);
  8. }
  9. this.count -- ; // 删除后数据个数减少
  10. }
  11. }

对象数组转换

开发中,类中不应该有输出语句。想输出数据应将数据返回到调用处。链表属于动态数组,因此可以将链表以对象数组的形式返回。
无法加载
由上图可知,Link的toArray()要返回一个对象数组,且该数组也要由Node操作。因此该数组应定义为Link的属性。
(1)Link添加一个数组属性,便于Node和Link访问。添加toArray()

  1. private String[] retArray; // 返回的数组
  2. public String[] toArray() {
  3. if (this.root == null) {
  4. return null;
  5. }
  6. this.foot = 0; // 需要脚标控制
  7. this.retArray = new String[this.count]; // 根据保存内容开辟数组
  8. this.root.toArrayNode();
  9. return this.retArray;
  10. }

(2)Node添加toArrayNode()进行数组数据保存

  1. public void toArrayNode() {
  2. Link.this.retArray[Link.this.foot++] = this.data;
  3. if (this.next != null) {
  4. this.next.toArrayNode();
  5. }
  6. }

链表数据变为对象数组取出是重要功能!

链表使用

上述链表只能操作String数据。下面要使用链表操作自定义类,由于链表具有contains(),因此类中需定义对象比较的方法。

(1)定义Book类(setter/getter暂时省略)

  1. class Book {
  2. private String title;
  3. private double price;
  4. public Book(String title, double price) {
  5. this.title = title;
  6. this.price = price;
  7. }
  8. public String getInfo() {
  9. return "书名:" + this.title + ",价格" + this.price;
  10. }
  11. public boolean compare(Book book) {
  12. if (book == null) {
  13. return false;
  14. }
  15. if (this == book) {
  16. return true;
  17. }
  18. if (this.title.equals(book.title)
  19. && this.price == book.price) {
  20. return true;
  21. } else {
  22. return false;
  23. }
  24. }
  25. }

(2)修改链表

  1. class Link {
  2. private class Node { // 节点类
  3. private Book data; // 保存数据
  4. private Node next; // 引用关系
  5. public Node(Book data) {
  6. this.data = data;
  7. }
  8. // 设置关系
  9. public void addNode(Node newNode) {
  10. if (this.next == null) {
  11. this.next = newNode;
  12. } else {
  13. this.next.addNode(newNode);
  14. }
  15. }
  16. // 数据查询
  17. public boolean containsNode(Book data) {
  18. if (data.equals(this.data)) { // 当前数据等于要目标数据
  19. return true; // 结束查询
  20. } else { // 当前数据不等于目标数据
  21. if (this.next != null) { // 有后续节点
  22. return this.next.containsNode(data);
  23. } else { // 没有后续节点
  24. return false;
  25. }
  26. }
  27. }
  28. public Book getNode(int index) {
  29. // 当前foot内容与要查询的索引比较
  30. // foot自增,目的是下次查询方便
  31. if (Link.this.foot++ == index) {
  32. return this.data;
  33. } else {
  34. return this.next.getNode(index);
  35. }
  36. }
  37. // 修改节点信息
  38. public void setNode(int index, Book data) {
  39. if (Link.this.foot++ == index) {
  40. this.data = data;
  41. } else {
  42. this.next.setNode(index, data);
  43. }
  44. }
  45. // 删除非根节点
  46. public void removeNode(Node previous, Book data) {
  47. // 参数中传递上一个节点和要删除的数据
  48. if (data.equals(this.data)) {
  49. previous.next = this.next;
  50. } else {
  51. this.next.removeNode(this, data);
  52. }
  53. }
  54. public void toArrayNode() {
  55. Link.this.retArray[Link.this.foot++] = this.data;
  56. if (this.next != null) {
  57. this.next.toArrayNode();
  58. }
  59. }
  60. }
  61. // ====================以上为内部类=====================
  62. private Node root; // 根节点
  63. private int count = 0; // 节点的个数
  64. private int foot = 0; // 索引
  65. private Book[] retArray; // 返回的数组
  66. public void add(Book data) {
  67. if (data == null) { // 输入数据为空
  68. return;
  69. }
  70. Node newNode = new Node(data); // 要保存的数据
  71. if (this.root == null) { // 根节点不存在
  72. this.root = newNode; // 设为根节点
  73. } else { // 根节点存在,交由Node处理
  74. this.root.addNode(newNode);
  75. }
  76. this.count++; // 每次增加节点,count+1
  77. }
  78. // 获取链表长度
  79. public int size() {
  80. return this.count;
  81. }
  82. // 判断是否为空链表
  83. public boolean isEmpty() {
  84. return this.count == 0;
  85. }
  86. // 判断数据是否存在
  87. public boolean contains(Book data) {
  88. if (data == null || root == null) {
  89. return false;
  90. }
  91. return this.root.containsNode(data);
  92. }
  93. // 根据索引获取信息
  94. public Book get(int index) {
  95. if (index > this.count) { // 超出查询范围
  96. return null;
  97. }
  98. this.foot = 0;
  99. return this.root.getNode(index); // 查询交给Node类
  100. }
  101. // 设置信息
  102. public void set(int index, Book data) {
  103. if (index > this.count) {
  104. return;
  105. }
  106. this.foot = 0; // 重置foot,作为索引
  107. this.root.setNode(index, data); // Node进行修改数据
  108. }
  109. // 判断删除节点是否为root
  110. public void remove(Book data) {
  111. if (this.contains(data)) { // 判断数据是否存在
  112. if (data.equals(this.root.data)) { // 判断数据是否是root数据
  113. this.root = this.root.next;
  114. } else {
  115. // root是Node对象,此处直接访问内部类私有操作
  116. this.root.next.removeNode(this.root, data);
  117. }
  118. this.count--; // 删除后数据个数减少
  119. }
  120. }
  121. public Book[] toArray() {
  122. if (this.root == null) {
  123. return null;
  124. }
  125. this.foot = 0; // 需要脚标控制
  126. this.retArray = new Book[this.count]; // 根据保存内容开辟数组
  127. this.root.toArrayNode();
  128. return this.retArray;
  129. }
  130. }

(3)测试

  1. public class Demo {
  2. public static void main(String[] args) {
  3. Link all = new Link();
  4. all.add(new Book("Java开发", 69.8));
  5. all.add(new Book("JSP", 78.8));
  6. all.add(new Book("C++开发", 19.8));
  7. System.out.println("保存书的个数:" + all.size());
  8. System.out.println(all.contains(new Book("Java开发", 69.8)));
  9. all.remove(new Book("C++开发", 19.8));
  10. Book[] books = all.toArray();
  11. for (int x = 0; x < books.length; x++) {
  12. System.out.println(books[x].getInfo());
  13. }
  14. }
  15. }

链表的最佳应用就是横向替换对象数组。

在映射中使用链表

链表属于动态对象数组。之前进行数据表映射时,都会出现对象数组的概念,现在就用链表来进行对象保存。本节以一对多为例,即用前文中的省份-城市表为例:

(1)对于使用链表的类,要添加对象比较的方法

  1. class Province {
  2. private int pid;
  3. private String pname;
  4. private Link cities = new Link();
  5. public Link getCities() {
  6. return this.cities;
  7. }
  8. //getter/setter,无参构造方法略
  9. public Province(int pid, String pname) {
  10. this.pid = pid;
  11. this.pname = pname;
  12. }
  13. public boolean compare(Province province) {
  14. if (province == null) {
  15. return false;
  16. }
  17. if (this == province) {
  18. return true;
  19. }
  20. if (this.pid == province.pid && this.pname.equals(province.pname)) {
  21. return true;
  22. } else {
  23. return false;
  24. }
  25. }
  26. public String getInfo() {
  27. return "省份ID:" + this.pid + ",省份名称:" + this.pname;
  28. }
  29. }
  30. class City {
  31. private int cid;
  32. private String cname;
  33. private Province province;
  34. public void setProvince(Province province) {
  35. this.province = province;
  36. }
  37. public Province getProvince() {
  38. return this.province;
  39. }
  40. //getter/setter,无参构造方法略
  41. public City(int cid, String cname) {
  42. this.cid = cid;
  43. this.cname = cname;
  44. }
  45. public String getInfo() {
  46. return "城市ID:" + this.cid + ",城市名称:" + this.cname;
  47. }
  48. public boolean compare(City city) {
  49. if (city == null) {
  50. return false;
  51. }
  52. if (this == city) {
  53. return true;
  54. }
  55. if (this.cid == city.cid && this.cname.equals(city.cname)
  56. && this.province.compare(city.province)) {
  57. return true;
  58. } else {
  59. return false;
  60. }
  61. }
  62. }

此时只需将链表中的Book改为City即可。
在此时发现问题:每定义一个新的类,链表就需要重新进行修改。方法解决了代码重复问题。但是该问题不属于代码重复,属于数据类型不同意,该问题需要依靠面向对象的特性的来结局。

总结

(1)本章所讲的只是最基础的单向链表;
(2)链表中应有如下方法:

No. 方法名称 类型 作用
1 public void add(数据类型 变量) 普通 向链表中添加数据
2 public int size() 普通 取得链表中数据个数
3 public boolean isEmpty() 普通 判断是否为空链表
4 public boolean contains(数据类型 变量) 普通 判断数据是否存在
5 public 数据类型 get(int index) 普通 根据索引取得数据
6 public void set(int index,数据类型 变量) 普通 修改数据
7 public void remove(数据类型 变量) 普通 删除指定数据
8 public 数据类型 [] toArray() 普通 将链表以对象数组的形式转换

This blog is under a CC BY-NC-SA 3.0 Unported License
本文链接:http://yov.oschina.io/article/Java/Java Base/Java基础知识(十)/

Error: Comments Not Initialized