第三章线性表2（链接表）

3.5.2 链接表接口

链接表可以看成是一组结点序列以及基于结点进行操作的线性结果的抽象，或则说是对链表的抽象。

链接表的接口：

 1 package com.datastructure.chapter03.interfaces;
 2 
 3 import com.datastructure.chapter03.exception.InvalidNodeException;
 4 import com.datastructure.chapter03.exception.OutOfBoundaryException;
 5 
 6 /** 
 7  * @ClassName: LinkedList 
 8  * @Description: 链接表接口
 9  * @author 
10  * @date 2018年3月15日 下午9:18:35 
11  *  
12  */
13 public interface LinkedList {
14     //查询链接表当前的规模
15     public int getSize();
16     
17     //判断列表是否为空
18     public boolean isEmpty();
19     
20     //返回第一个结点
21     public Node first() throws OutOfBoundaryException;
22     
23     //返回最后一个结点
24     public Node last() throws OutOfBoundaryException;
25     
26     //返回p之后的结点
27     public Node getNext(Node p) throws InvalidNodeException,OutOfBoundaryException;
28     
29     //返回p之前的结点
30     public Node getPre(Node p) throws InvalidNodeException,OutOfBoundaryException;
31 
32     //将e作为第一个元素插入链接表，并返回e所在结点
33     public Node insertFirst(Object e);
34     
35     //将e作为最后一个元素插入列表，并返回e所在结点
36     public Node insertLast(Object e);
37     
38     //将e插入至p之后的位置，并返回e所在结点
39     public Node insertAfter(Node p,Object e) throws InvalidNodeException;
40     
41     //将e插入至p之前的位置，并返回e所在结点
42     public Node insertBefore(Node p) throws InvalidNodeException;
43     
44     //删除首元素，并返回之
45     public Object remove(Node p) throws InvalidNodeException;
46     
47     //删除首元素，并返回之
48     public Object removeFirst() throws InvalidNodeException;
49     
50     //删除末元素，并返回之
51     public Object removeLast() throws OutOfBoundaryException;
52     
53     //将处于给定位置的元素替换为新元素，并返回被替换的元素
54     public Object replace(Node p,Object e) throws InvalidNodeException;
55     
56     //元素迭代器
57     public Iterateor elements();
58     
59     
60 }

View Code

其中迭代器Iterator的接口：

package com.datastructure.chapter03.interfaces;

/** 
 * @ClassName: Iterateor 
 * @Description: 迭代器
 * @author 
 * @date 2018年3月15日 下午9:35:16 
 *  
 */
public interface Iterateor {
    
    //移动到第一个元素
    public void first();
    
    //移动到下一个元素
    public void next();
    
    //检查迭代器中是否还有剩余的元素
    public boolean isDone();
    
    //返回当前元素
    public Object currentItem();
    
}

View Code

还有一个异常类InvalidNodeException：

 1 package com.datastructure.chapter03.exception;
 2 
 3 /** 
 4  * @ClassName: InvalidNodeException 
 5  * @Description: 
 6  * 产生这个异常：
 7  * 结点p==null
 8  * p在链接表中不存在
 9  * 在调用getPre(p),p已经是第一个存有数据的结点
10  * 在调用getNext(p),p已经是最后一个存有数据的结点
11  * @author 
12  * @date 2018年3月15日 下午9:40:44 
13  *  
14  */
15 @SuppressWarnings("serial")
16 public class InvalidNodeException extends RuntimeException {
17     
18     public InvalidNodeException(String err){
19         super(err);
20     }
21 }

View Code

基于双向链表思想的链接表

  1 package com.datastructure.chapter03.interfacesImpl;
  2 
  3 import com.datastructure.chapter03.exception.InvalidNodeException;
  4 import com.datastructure.chapter03.exception.OutOfBoundaryException;
  5 import com.datastructure.chapter03.interfaces.Iterater;
  6 import com.datastructure.chapter03.interfaces.LinkedList;
  7 import com.datastructure.chapter03.interfaces.Node;
  8 
  9 /** 
 10  * @ClassName: LinkedListDLNode 
 11  * @Description: 基于双向链表实现的链接表
 12  * @author mao
 13  * @date 2018年3月15日 下午9:53:07 
 14  *  
 15  */
 16 public class LinkedListDLNode implements LinkedList {
 17 
 18     private int size; //规模
 19     
 20     private DLNode head;//头节点，哑元节点
 21     
 22     private DLNode tail;//尾节点，哑元节点
 23     
 24     public LinkedListDLNode() {
 25         size = 0;
 26         head = new DLNode();
 27         tail = new DLNode();
 28         head.setNext(tail);
 29         tail.setPre(head);
 30     }
 31     
 32     /* (非 Javadoc) 
 33      * <p>Title: getSize</p> 
 34      * <p>Description: 查询链接表当前的规模</p> 
 35      * @return 
 36      * @see com.datastructure.chapter03.interfaces.LinkedList#getSize() 
 37      */
 38     @Override
 39     public int getSize() {
 40         return size;
 41     }
 42 
 43     /* (非 Javadoc) 
 44      * <p>Title: isEmpty</p> 
 45      * <p>Description: 判断链接表是否为空</p> 
 46      * @return 
 47      * @see com.datastructure.chapter03.interfaces.LinkedList#isEmpty() 
 48      */
 49     @Override
 50     public boolean isEmpty() {
 51         return size == 0;
 52     }
 53 
 54     /* (非 Javadoc) 
 55      * <p>Title: first</p> 
 56      * <p>Description: 返回第一个结点</p> 
 57      * @return
 58      * @throws OutOfBoundaryException 
 59      * @see com.datastructure.chapter03.interfaces.LinkedList#first() 
 60      */
 61     @Override
 62     public Node first() throws OutOfBoundaryException {
 63         if(isEmpty())
 64             throw new OutOfBoundaryException("错误，链接表为空!");
 65         return head.getNext();
 66     }
 67 
 68     /* (非 Javadoc) 
 69      * <p>Title: last</p> 
 70      * <p>Description: 返回最后一个结点</p> 
 71      * @return
 72      * @throws OutOfBoundaryException 
 73      * @see com.datastructure.chapter03.interfaces.LinkedList#last() 
 74      */
 75     @Override
 76     public Node last() throws OutOfBoundaryException {
 77         if(isEmpty())
 78             throw new OutOfBoundaryException("错误，链接表为空!");
 79         return tail.getPre();
 80     }
 81 
 82     /* (非 Javadoc) 
 83      * <p>Title: getNext</p> 
 84      * <p>Description: 返回p之后的结点</p> 
 85      * @param p
 86      * @return
 87      * @throws InvalidNodeException
 88      * @throws OutOfBoundaryException 
 89      * @see com.datastructure.chapter03.interfaces.LinkedList#getNext(com.datastructure.chapter03.interfaces.Node) 
 90      */
 91     @Override
 92     public Node getNext(Node p) throws InvalidNodeException,
 93             OutOfBoundaryException {
 94         DLNode node = checkPosition(p);
 95         node = node.getNext();
 96         if(node == tail)
 97             throw new OutOfBoundaryException("错误：已经是链接表尾端。");
 98         return node;
 99     }
100 
101     
102 
103     /* (非 Javadoc) 
104      * <p>Title: getPre</p> 
105      * <p>Description: 返回p之前的结点</p> 
106      * @param p
107      * @return
108      * @throws InvalidNodeException
109      * @throws OutOfBoundaryException 
110      * @see com.datastructure.chapter03.interfaces.LinkedList#getPre(com.datastructure.chapter03.interfaces.Node) 
111      */
112     @Override
113     public Node getPre(Node p) throws InvalidNodeException,
114             OutOfBoundaryException {
115         DLNode node = checkPosition(p);
116         node = node.getPre();
117         if(node == head)
118             throw new OutOfBoundaryException("错误：已经是链接表前端。");
119         return node;
120     }
121 
122     /* (非 Javadoc) 
123      * <p>Title: insertFirst</p> 
124      * <p>Description: 将e作为第一个元素插入链接表</p> 
125      * @param e
126      * @return 
127      * @see com.datastructure.chapter03.interfaces.LinkedList#insertFirst(java.lang.Object) 
128      */
129     @Override
130     public Node insertFirst(Object e) {
131         
132         DLNode node = new DLNode(e, head, head.getNext());
133         head.getNext().setPre(node);
134         head.setNext(node);
135         size++;
136         return node;
137     }
138 
139     @Override
140     public Node insertLast(Object e) {
141         DLNode node = new DLNode(e, tail.getPre(), tail);
142         tail.getPre().setNext(node);
143         tail.setPre(node);
144         size++;
145         return node;
146     }
147 
148     /* (非 Javadoc) 
149      * <p>Title: insertAfter</p> 
150      * <p>Description: 将e插入至p之后的位置，并返回e所在结点</p> 
151      * @param p
152      * @param e
153      * @return
154      * @throws InvalidNodeException 
155      * @see com.datastructure.chapter03.interfaces.LinkedList#insertAfter(com.datastructure.chapter03.interfaces.Node, java.lang.Object) 
156      */
157     @Override
158     public Node insertAfter(Node p, Object e) throws InvalidNodeException {
159         
160         DLNode node = checkPosition(p);
161         DLNode newNode = new DLNode(e, node, node.getNext());
162         node.getNext().setPre(newNode);
163         node.setNext(newNode);
164         size++;
165         return newNode;
166     }
167 
168     /* (非 Javadoc) 
169      * <p>Title: insertBefore</p> 
170      * <p>Description: 将e插入p之前，并返回e所在结点</p> 
171      * @param p
172      * @param e
173      * @return
174      * @throws InvalidNodeException 
175      * @see com.datastructure.chapter03.interfaces.LinkedList#insertBefore(com.datastructure.chapter03.interfaces.Node, java.lang.Object) 
176      */
177     @Override
178     public Node insertBefore(Node p,Object e) throws InvalidNodeException {
179         DLNode node = checkPosition(p);
180         DLNode newNode = new DLNode(e,node.getPre(),node);
181         node.setPre(newNode);
182         node.getPre().setNext(newNode);
183         size++;
184         return newNode;
185     }
186 
187     /* (非 Javadoc) 
188      * <p>Title: remove</p> 
189      * <p>Description: 删除给定位置处元素，并返回之</p> 
190      * @param p
191      * @return
192      * @throws InvalidNodeException 
193      * @see com.datastructure.chapter03.interfaces.LinkedList#remove(com.datastructure.chapter03.interfaces.Node) 
194      */
195     @Override
196     public Object remove(Node p) throws InvalidNodeException {
197         DLNode node = checkPosition(p);
198         Object obj = node.getData();
199         node.getPre().setNext(node.getNext());
200         node.getNext().setPre(node.getPre());
201         size--;
202         return obj;
203     }
204 
205     
206     /* (非 Javadoc) 
207      * <p>Title: removeFirst</p> 
208      * <p>Description: 移除第一个结点</p> 
209      * @return
210      * @throws InvalidNodeException 
211      * @see com.datastructure.chapter03.interfaces.LinkedList#removeFirst() 
212      */
213     @Override
214     public Object removeFirst() throws InvalidNodeException {
215         return remove(head.getNext());
216     }
217 
218     /* (非 Javadoc) 
219      * <p>Title: removeLast</p> 
220      * <p>Description: 移除最后一个结点</p> 
221      * @return
222      * @throws OutOfBoundaryException 
223      * @see com.datastructure.chapter03.interfaces.LinkedList#removeLast() 
224      */
225     @Override
226     public Object removeLast() throws OutOfBoundaryException {
227         return remove(tail.getPre());
228     }
229 
230     /* (非 Javadoc) 
231      * <p>Title: replace</p> 
232      * <p>Description: 将处于给定位置元素替换为新元素，并返回被替换的元素</p> 
233      * @param p
234      * @param e
235      * @return
236      * @throws InvalidNodeException 
237      * @see com.datastructure.chapter03.interfaces.LinkedList#replace(com.datastructure.chapter03.interfaces.Node, java.lang.Object) 
238      */
239     @Override
240     public Object replace(Node p, Object e) throws InvalidNodeException {
241         DLNode node = checkPosition(p);
242         Object obj = node.getData();
243         node.setData(e);
244         return obj;
245     }
246 
247     @Override
248     public Iterater elements() {
249         return new LinkedListIterator(this);
250     }
251     
252     /** 
253      * @Title: checkPosition 
254      * @Description:  判断p是否合法，合法则转换为DLNode
255      * @param @param p
256      * @param @return
257      * @param @throws InvalidNodeException  
258      * @return DLNode   
259      * @throws 
260      */
261     protected DLNode checkPosition(Node p) throws InvalidNodeException{
262         if(null == p)
263             throw new InvalidNodeException("错误：p为空。");
264         if(p == head)
265             throw new InvalidNodeException("错误：p指向头结点，非法。");
266         if(p == tail)
267             throw new InvalidNodeException("错误：p指向尾节点，非法。");
268         DLNode node = (DLNode) p;
269         return node;
270     }
271 
272 }

View Code

迭代器的实现类：

 1 package com.datastructure.chapter03.interfacesImpl;
 2 
 3 import com.datastructure.chapter03.exception.OutOfBoundaryException;
 4 import com.datastructure.chapter03.interfaces.Iterater;
 5 import com.datastructure.chapter03.interfaces.LinkedList;
 6 import com.datastructure.chapter03.interfaces.Node;
 7 
 8 /** 
 9  * @ClassName: LinkedListIterator 
10  * @Description: 链接表的迭代器
11  * @author 
12  * @date 2018年3月15日 下午10:39:29 
13  *  
14  */
15 public class LinkedListIterator implements Iterater {
16 
17     private LinkedList list;//链接表
18     
19     private Node current;//当前结点
20     
21     public LinkedListIterator(LinkedList list) {
22         this.list = list;
23         if(list.isEmpty())
24             current = null;
25         else
26             current = list.first();
27     }
28     
29     /* (非 Javadoc) 
30      * <p>Title: first</p> 
31      * <p>Description: 移动到第一个个元素</p>  
32      * @see com.datastructure.chapter03.interfaces.Iterater#first() 
33      */
34     @Override
35     public void first() {
36         if(list.isEmpty())
37             current = null;
38         else
39             current = list.first();
40     }
41 
42     /* (非 Javadoc) 
43      * <p>Title: next</p> 
44      * <p>Description: 移动到下一个元素</p> 
45      * @throws OutOfBoundaryException 
46      * @see com.datastructure.chapter03.interfaces.Iterater#next() 
47      */
48     @Override
49     public void next() throws OutOfBoundaryException{
50         if(isDone())
51             throw new OutOfBoundaryException("错误：已经没有元素。");
52         if(current == list.last()) current = null;//当前元素后面没有更多元素
53         else current = list.getNext(current);
54         
55     }
56 
57     /* (非 Javadoc) 
58      * <p>Title: isDone</p> 
59      * <p>Description:检查迭代器中是否还有剩余元素 </p> 
60      * @return 
61      * @see com.datastructure.chapter03.interfaces.Iterater#isDone() 
62      */
63     @Override
64     public boolean isDone() {
65         return current == null;
66     }
67 
68     /* (非 Javadoc) 
69      * <p>Title: currentItem</p> 
70      * <p>Description: 返回当前元素</p> 
71      * @return 
72      * @see com.datastructure.chapter03.interfaces.Iterater#currentItem() 
73      */
74     @Override
75     public Object currentItem() {
76         if(isDone())
77             throw new OutOfBoundaryException("错误：已经没有元素了");
78         return current.getData();
79     }
80 
81 }

View Code

第三章 线性表2（链接表）

第三章线性表2（链接表）