線性表的鏈式存儲與實現(xiàn)
實現(xiàn)線性表的另一種方法是鏈式存儲，即用指針將存儲線性表中數(shù)據(jù)元素的那些單元依次串聯(lián)在一起。這種方法避免了在數(shù)組中用連續(xù)的單元存儲元素的缺點，因而在執(zhí)行插入或 刪除運算時，不再需要移動元素來騰出空間或填補空缺。然而我們?yōu)榇烁冻龅拇鷥r是，需要在每個單元中設(shè)置指針來表示表中元素之間的邏輯關(guān)系，因而增加了額外的存儲空間的開銷.
單鏈表
鏈表是一系列的存儲數(shù)據(jù)元素的單元通過指針串接起來形成的，因此每個單元至少有兩個域，一個域用于數(shù)據(jù)元素的存儲，另一個域是指向其他單元的指針。這里具有一個數(shù)據(jù)域和多個指針域的存儲單元通常稱為結(jié)點（node）.
結(jié)點接口
|
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 { /** * 獲取結(jié)點數(shù)據(jù)域 * * @return */ public Object getData(); /** * 設(shè)置結(jié)點數(shù)據(jù)域 * * @param obj */ public void setData(Object obj);} |
單鏈表結(jié)點定義
|
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;//單鏈表結(jié)點定義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; }} |
線性表的單鏈表實現(xiàn)
在使用單鏈表實現(xiàn)線性表的時候，為了使程序更加簡潔，我們通常在單鏈表的前面添 加一個啞元結(jié)點，也稱為頭結(jié)點。在頭結(jié)點中不存儲任何實質(zhì)的數(shù)據(jù)對象，其 next 域指向 線性表中 0 號元素所在的結(jié)點，頭結(jié)點的引入可以使線性表運算中的一些邊界條件更容易處理。
|
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;//線性表的單鏈表實現(xiàn)public class ListSLinked implements List { private Strategy strategy; // 數(shù)據(jù)元素比較策略 private SLNode head; // 單鏈表首結(jié)點引用 private int size;// 線性表中數(shù)據(jù)元素的個數(shù) public ListSLinked() { this(new DefaultStrategy()); } public ListSLinked(Strategy strategy) { this.strategy = strategy; head = new SLNode(); size = 0; } /** * 輔助方法： 獲取數(shù)據(jù)元素 e 所在結(jié)點的前驅(qū)結(jié)點 * * @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 的元素所在結(jié)點的前驅(qū)結(jié)點 * * @param i * @return */ private SLNode getPreNode(int i) { SLNode p = head; for (; i > 0; i--) p = p.getNext(); return p; } /** * 輔助方法： 獲取序號為 0<=i<size 的元素所在結(jié)點 * * @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)); } }} |
數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)代碼倉庫：
https://git.oschina.net/wjyonlyone/DataStructure
以上就是本文的全部內(nèi)容，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時也希望多多支持服務(wù)器之家！
原文鏈接：http://www.cnblogs.com/Onlywjy/p/6266612.html
