線性表的鏈式存儲與實現
實現線性表的另一種方法是鏈式存儲，即用指針將存儲線性表中數據元素的那些單元依次串聯在一起。這種方法避免了在數組中用連續的單元存儲元素的缺點，因而在執行插入或 刪除運算時，不再需要移動元素來騰出空間或填補空缺。然而我們為此付出的代價是，需要在每個單元中設置指針來表示表中元素之間的邏輯關系，因而增加了額外的存儲空間的開銷.
單鏈表
鏈表是一系列的存儲數據元素的單元通過指針串接起來形成的，因此每個單元至少有兩個域，一個域用于數據元素的存儲，另一個域是指向其他單元的指針。這里具有一個數據域和多個指針域的存儲單元通常稱為結點（node）.
結點接口
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
package com.wjy.Data_Structure.linearlist.common;public interface Node { /** * 獲取結點數據域 * * @return */ public Object getData(); /** * 設置結點數據域 * * @param obj */ public void setData(Object obj);} |
單鏈表結點定義
|
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
|
package com.wjy.Data_Structure.linearlist.common;//單鏈表結點定義public class SLNode implements Node { private Object element; private SLNode next; public SLNode() { } public SLNode(Object ele, SLNode next) { this.element = ele; this.next = next; } public SLNode getNext() { return next; } public void setNext(SLNode next) { this.next = next; } /******** Methods of Node Interface **********/ @Override public Object getData() { return element; } @Override public void setData(Object obj) { element = obj; }} |
線性表的單鏈表實現
在使用單鏈表實現線性表的時候，為了使程序更加簡潔，我們通常在單鏈表的前面添 加一個啞元結點，也稱為頭結點。在頭結點中不存儲任何實質的數據對象，其 next 域指向 線性表中 0 號元素所在的結點，頭結點的引入可以使線性表運算中的一些邊界條件更容易處理。
|
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
|
package com.wjy.Data_Structure.linearlist.listslinkimpl;import com.wjy.Data_Structure.linearlist.common.DefaultStrategy;import com.wjy.Data_Structure.linearlist.common.List;import com.wjy.Data_Structure.linearlist.common.SLNode;import com.wjy.Data_Structure.linearlist.common.Strategy;import com.wjy.Data_Structure.linearlist.exception.OutOfBoundaryException;//線性表的單鏈表實現public class ListSLinked implements List { private Strategy strategy; // 數據元素比較策略 private SLNode head; // 單鏈表首結點引用 private int size;// 線性表中數據元素的個數 public ListSLinked() { this(new DefaultStrategy()); } public ListSLinked(Strategy strategy) { this.strategy = strategy; head = new SLNode(); size = 0; } /** * 輔助方法： 獲取數據元素 e 所在結點的前驅結點 * * @param e * @return */ private SLNode getPreNode(Object e) { SLNode p = head; while (p.getNext() != null) if (strategy.equal(p.getNext().getData(), e)) return p; else p = p.getNext(); return null; } /** * 輔助方法： 獲取序號為 0<=i<size 的元素所在結點的前驅結點 * * @param i * @return */ private SLNode getPreNode(int i) { SLNode p = head; for (; i > 0; i--) p = p.getNext(); return p; } /** * 輔助方法： 獲取序號為 0<=i<size 的元素所在結點 * * @param i * @return */ private SLNode getNode(int i) { SLNode p = head.getNext(); for (; i > 0; i--) p = p.getNext(); return p; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public boolean contains(Object e) { return indexOf(e) != -1; } @Override public int indexOf(Object e) { SLNode p = head.getNext(); int index = 0; while (p != null) if (strategy.equal(p.getData(), e)) { return index; } else { index++; p = p.getNext(); } return -1; } @Override public void insert(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i > size) throw new OutOfBoundaryException("錯誤，指定的插入序號越界"); SLNode p = getPreNode(i); SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return; } @Override public boolean insertBefore(Object obj, Object e) { SLNode p = getPreNode(obj); if (p != null) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } return false; } @Override public boolean insertAfter(Object obj, Object e) { SLNode p = head.getNext(); while (p != null) if (strategy.equal(p.getData(), obj)) { SLNode q = new SLNode(e, p.getNext()); p.setNext(q); size++; return true; } else { p = p.getNext(); } return false; } @Override public Object remove(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("錯誤，指定的刪除序號越界。"); SLNode p = getPreNode(i); Object obj = p.getNext().getData(); p.setNext(p.getNext().getNext()); size--; return obj; } @Override public boolean remove(Object e) { SLNode p = getPreNode(e); if (p != null) { p.setNext(p.getNext().getNext()); size--; return true; } return false; } @Override public Object replace(int i, Object e) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("錯誤，指定的序號越界。"); SLNode p = getNode(i); Object obj = p.getData(); p.setData(e); return obj; } @Override public Object get(int i) throws OutOfBoundaryException { if (i < 0 || i >= size) throw new OutOfBoundaryException("錯誤，指定的序號越界。"); SLNode p = getNode(i); return p.getData(); }} |
簡單的測試用例
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
package com.wjy.Data_Structure.linearlist.listslinkimpl;import org.junit.Test;import com.wjy.Data_Structure.linearlist.listslinkimpl.ListSLinked;public class ListSLinkedTest { @Test public void testInsert() { ListSLinked list = new ListSLinked(); for (int i = 0; i < 10; i++) { list.insert(i, i + 1); } System.out.println("刪除：" + list.remove(0)); System.out.println(list.contains(1)); list.insertBefore(2, 100); list.insertAfter(2, 101); list.replace(list.getSize() - 1, 1000); for (int i = 0; i < list.getSize(); i++) { System.out.println(list.get(i)); } }} |
數據結構學習代碼倉庫：
https://git.oschina.net/wjyonlyone/DataStructure
以上就是本文的全部內容，希望本文的內容對大家的學習或者工作能帶來一定的幫助，同時也希望多多支持服務器之家！
原文鏈接：http://www.cnblogs.com/Onlywjy/p/6266612.html
