线性表的链式储存结构(java版)
线性表的链式存储结构(java版)
在前面,我们已经讲了线性表的顺序存储结构(java版) ,我们也知道了他的代码实现,在了解之后,我们很容易就能够发现他有一个最大的缺点,就是插入和删除需要移动大量的元素,这显然是很耗费时间的,于是,为了解决这个问题,就出现了链式存储结构。
我学习的时候是看程杰的《大话数据结构》的,同时结合我们的经典教材清华出版社的《数据结构》,但是在学习过程中,我不小心把“插入到第i个位置之后”理解成了“插入到第i个位置”,所以我后面的程序跟书上的范例有些不一样,但是万变不离其宗,它运用的始终是我们的数据结构——线性表的链式存储结构。
由于理解错了课本的一些意思,所以代码显得更复杂了一点点,好吧,言归正传,继续讲我们代码是如何实现的。
第一步,定义一个接口,其实这个接口跟前面顺序存储结构的接口定义是一样的,后面我只是改了下名字和重新更换了包名而已,但这不影响我们的代码:
package com.stucture.list; /** * 线性表顺序存储结构的接口 * 指的是用一段地址连续的存储单元一次存储线性表的数据元素 * @ClassName: ISqList * @author 小学徒 * @date 2013-2-27 */ public interface IList<T> { /** * 获得元素 * @param loc 需要获得的第loc个元素 * @return */ public T getElem(int loc); /** * 插入元素 * @param loc 元素的插入位置 * @param t 需要插入的元素 * @return 是否成功插入 */ public boolean insertElem(int loc, T t); /** * 删除元素 * @param i 需要删除元素的位置 * @return */ public T deleteElem(int i); }
第二步,定义我们的节点类:
package com.stucture.list.linkList; /** * 链表中的结点 * @ClassName: Node * @author 小学徒 * @date 2013-2-27 */ public class Node<T> { private T data; //需要存储的数据信息 private Node<T> next; //后继结点 public T getData() { return data; } public void setData(T data) { this.data = data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } }
第三步,定义我们的链表及其基本操作,代码如下:
package com.stucture.list.linkList; import com.stucture.list.IList; /** * 单链表 * @ClassName: LinkList * @author 小学徒 * @date 2013-2-27 */ public class LinkList<T> implements IList<T>{ private Node<T> head; //链表的结点 private int length; //链表的长度 public LinkList(Node<T> head) { this.head = head; } //获取元素 public T getElem(int loc) { int j = 1; //计数器 Node<T> n = head; //指向第一个结点 while(n != null) { //n不为空时,循环继续寻找第loc个结点 if(j == loc) { //找到第一个元素时返回 return n.getData(); } n = n.getNext(); j++; } return null; } //插入元素 public boolean insertElem(int loc, T t) { if(length + 1 < loc) { System.out.println("非法插入"); return false; } if(head == null && loc == 1) { //当第一次插入的时候 head = new Node<T>(); //第一次使用,必须创建对象 head.setData(t); length++; } else if(head != null && loc == 1) { //但不是第一次插入,但是插入的位置是第一个时 Node<T> tempNode = new Node<T>(); //生成一个新的结点 tempNode.setData(t); tempNode.setNext(head); head = tempNode; //把头换成新插入的结点 length++; } else { //当不是第一次插入并且插入的不是第一个时 Node<T> n = this.head; int j = 1; //计数器 while(n != null && j < loc - 1) { n = n.getNext(); j++; } Node<T> tempNode = new Node<T>(); //生成一个新的结点 tempNode.setData(t); tempNode.setNext(n.getNext()); //将n的后继结点赋值给新的结点的后继 n.setNext(tempNode); length++; } return true; } //删除元素 public T deleteElem(int loc) { if(head == null || loc > length) { System.out.println("非法删除"); return null; } T old; if(head != null && loc == 1) { old = head.getData(); head = head.getNext(); } else { Node<T> n = this.head; int j = 1; //计数器 while(n != null && j < loc - 1) { n = n.getNext(); j++; } old = n.getNext().getData(); n.setNext(n.getNext().getNext()); } length--; return old; } public Node<T> getHead() { return head; } public void setHead(Node<T> head) { this.head = head; } public int getLength() { return length; } public void setLength(int length) { this.length = length; } }
第四步,我们下面就写一个比较完善的代码测试,在下面的代码中,我是通过随机数来生成一些必要的数据来测试的,只要多运行几遍,还是能够测试比较完善的,不过封装的可能有点不太好,如果读者看了以后有什么更好的建议,还希望能够指出,当然因为该链式存储结构和顺序存储结构都是同一个接口的实现,所以测试方法是可以一样的,只是把实现类转换了而已。但是由于时间问题,我就没有去修改了,有兴趣的读者可以自行修改,有问题的可以在此留言共同讨论共同进步,我有空的时候也会更改并上传到博客的,下面继续代码:
package com.stucture.list.linkList; import java.util.Random; public class LinkListTest { final int MAX = 25; Random r = new Random(); LinkList<Integer> linkList; public LinkListTest() { initSeqList(); } //创建一个线性表顺序存储结构 public void initSeqList() { linkList = new LinkList<Integer>(null); int length = Math.abs(r.nextInt(MAX)); //使用Random随机产生一个25左右的值,使用Math.abs()函数来取绝对值 System.out.println("产生的链表长度为 :" + length); for (int i = 1; i <= length; i++) { //为生成的链表赋值,同时也测试了插入值的方法 int j =r.nextInt(MAX); System.out.print(j + " "); if(!linkList.insertElem(i, j)) { System.exit(0); } } System.out.println("\n原始链表是 :"); display(linkList); } //测试删除方法 public void deleteElem() { int i = r.nextInt(MAX); System.out.println("\n\n删除的位置是:" + i); Integer deleteNumber = linkList.deleteElem(i); if( deleteNumber == null) { System.exit(0); } else { System.out.println("删除的元素是 : " + deleteNumber); System.out.println("删除元素后链表是 :"); display(linkList); } } //测试随机插入方法 public void insertByRandom() { int i = r.nextInt(MAX); System.out.println("\n\n随机插入位置是 :" + i); int elem = r.nextInt(MAX); System.out.println("随机插入数据是 :" + elem); linkList.insertElem(i, elem); System.out.println("随机插入数据后链表是 :"); display(linkList); } //数据展示 public void display(LinkList<Integer> linkList) { Node<Integer> node = linkList.getHead(); while(node != null) { System.out.print(node.getData() + " "); node = node.getNext(); } System.out.println("链表的长度为 :" + linkList.getLength()); } //获取元素 public void getElem() { int i = r.nextInt(MAX); System.out.println("\n获取位置为 :" + i); System.out.println("获取到的元素为 : " + linkList.getElem(i)); } public static void main(String[] args) { LinkListTest s = new LinkListTest(); s.insertByRandom(); s.deleteElem(); s.getElem(); } }
运行结果同样我不一一把各种结果列出啦,读者可以自己运行多几遍来进行学习:
产生的链表长度为 :23 5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 原始链表是 : 5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 链表的长度为 :23 随机插入位置是 :24 随机插入数据是 :0 随机插入数据后链表是 : 5 19 18 12 6 12 15 19 16 21 13 16 5 4 18 9 9 18 17 13 16 6 17 0 链表的长度为 :24 删除的位置是:11 删除的元素是 : 13 删除元素后链表是 : 5 19 18 12 6 12 15 19 16 21 16 5 4 18 9 9 18 17 13 16 6 17 0 链表的长度为 :23 获取位置为 :12 5 19 18 12 6 12 15 19 16 21 16 5 获取到的元素为 : 5