一、線性表
原理：零個或多個同類數據元素的有限序列
原理圖：
特點 ：
1、有序性
2、有限性
3、同類型元素
4、第一個元素無前驅，最后一個元素無后繼，中間的元素有一個前驅并且有一個后繼
線性表是一種邏輯上的數據結構，在物理上一般有兩種實現 順序實現和鏈表實現
二、基于數組的 線性表順序實現
原理 ： 用一段地址連續的存儲單元依次存儲線性表數據元素。
原理圖：
算法原理：
1、初始化一個定長的數組空間 elementData[] , size 存儲長度 存儲元素
2、通過索引來快速存取元素
3、通過數組復制實現元素的插入和刪除
總結：
1、無需為表示表中元素之間的邏輯關系增加額外的存儲空間
2、可以快速存取表中任一位置元素
3、插入和刪除需要進行數組復制（即大量元素的移動）
4、線性表長度變化較大時，需要頻繁擴容，并造成存儲空間碎片
實現代碼：
接口定義：
|
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
|
package online.jfree.base;/** * author : Guo LiXiao * date : 2017-6-14 11:46 */public interface LineList <E>{ /** * lineList 是否為空 * @return */ boolean isEmpty(); /** * 清空 lineList */ void clear(); /** * 獲取指定位置元素 * @param index * @return */ E get(int index); /** * 獲取元素第一次出現的位置 * @param e * @return */ int indexOf(E e); /** * 判斷 lineList是否包含指定元素 * @param e * @return */ boolean contains(E e); /** * 設置指定位置數據，如數據已存在 則覆蓋原數據 * @param index * @param e * @return */ E set(int index, E e); /** * 移除指定位置元素 * @param index * @return */ E remove(int index); /** * 在lineList結尾插入元素 * @param e * @return */ E add(E e); /** * 在index后面插入元素 * @param index * @param e * @return */ E add(int index, E e); /** * 返回lineList長度 * @return */ int size();} |
算法實現：
|
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
|
package online.jfree.base;/** * author : Guo LiXiao * date : 2017-6-15 13:44 */public class OrderedLineList<E> implements LineList<E> { private static final int INIT_CAPACITY = 10; private transient E[] elementData; private transient int elementLength; private int size; public OrderedLineList() { this(0); } public OrderedLineList(int initCapacity) { init(initCapacity); } private void init(int initCapacity) { if (initCapacity >= 0) { this.elementData = (E[]) new Object[initCapacity]; this.elementLength = initCapacity; } else { throw new IllegalArgumentException("Illegal Capacity: " + initCapacity); } this.size = 0; } /** * 擴容 */ private void dilatation() { int oldCapacity = this.elementLength; int newCapacity = oldCapacity; if (oldCapacity <= this.size) { newCapacity = oldCapacity + INIT_CAPACITY; }else if(oldCapacity - INIT_CAPACITY > this.size){ newCapacity = oldCapacity - INIT_CAPACITY; } if (oldCapacity != newCapacity){ E[] newElementData = (E[]) new Object[newCapacity]; System.arraycopy(elementData, 0, newElementData, 0, oldCapacity); this.elementLength = newCapacity; this.elementData = newElementData; } } /** * 校驗列表索引越界 * @param index */ private void checkCapacity(int index){ if (index > this.size - 1 || index < 0) throw new IndexOutOfBoundsException(new StringBuffer("[index : ").append(index).append("] , [size : ").append(size).append("] ").toString()); } @Override public boolean isEmpty() { return this.size == 0; } @Override public void clear() { this.init(0); } @Override public E get(int index) { this.checkCapacity(index); return this.elementData[index]; } @Override public int indexOf(E e) { for (int i = 0; i < this.size; i++){ if (e == null && elementData[i] == null || e.equals(elementData[i])){ return i; } } return -1; } @Override public boolean contains(E e) { return this.indexOf(e) > 0; } @Override public E set(int index, E e) { this.checkCapacity(index); this.dilatation(); E oldElement = this.elementData[index]; this.elementData[index] = e; return oldElement; } @Override public E remove(int index) { this.dilatation(); E e = elementData[index]; if (index == size - 1) elementData[index] = null; else { int length = size - index - 1; System.arraycopy(elementData, index + 1, elementData, index, length); } size --; return e; } @Override public E add(E e) { return this.add(size, e); } @Override public E add(int index, E e) { this.dilatation(); if (index == size) elementData[index] = e; else { index++; int lastLength = size - index; E[] lastElementData = (E[]) new Object[lastLength]; System.arraycopy(elementData, index, lastElementData, 0, lastLength); elementData[index] = e; System.arraycopy(lastElementData, 0, elementData, index + 1, lastLength); } size ++ ; return e; } @Override public int size() { return this.size; }} |
以上這篇淺談線性表的原理及簡單實現方法就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
