線性表是其組成元素間具有線性關(guān)系的一種數(shù)據(jù)結(jié)構(gòu)，對(duì)線性表的基本操作主要有，獲取元素，設(shè)置元素值，遍歷，插入，刪除，查找，替換，排序等。而線性表可以采用順序儲(chǔ)存結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)，本節(jié)主要講解順序表、單鏈表以及雙鏈表的各種基本操作。
1：線性表抽象的數(shù)據(jù)類型
線性表：是由n（n>=0）個(gè)數(shù)據(jù)相同的元素組成的有限序列。線性表的定義接口如下
|
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
|
public interface ilist<t> { /** * 是否為空 * @return */ boolean isempty(); /** * 表的長度 * @return */ int length(); /** * 根據(jù)索引獲取長度 * @param i * @return */ t get(int i); /** * 設(shè)置第i個(gè)元素值為x * @param i * @param x */ void set(int i,t x); /** * 在線性表最后插入x元素 * @param x */ void append(t x); /** * 異常第i個(gè)元素并返回值 * @param i * @return */ t remove(int i); /** * 刪除線性表中所有元素 */ void removeall(); /** * 查詢首次出現(xiàn)關(guān)鍵字為key的元素 * @param key * @return */ t search(t key); void insert(int i,t x); /** * 升序添加 * @param x */ void insert(t x); /** * 升序刪除 * @param x */ void remove(t x);} |
2：線性表順序表示和實(shí)現(xiàn)
線性表的順序存儲(chǔ)結(jié)構(gòu)是一組連續(xù)的內(nèi)存單元依次存放的線性表的數(shù)據(jù)元素，元素的物理地址和邏輯地址次序是相同的。我們叫做這種存儲(chǔ)方式為順序表。
由于數(shù)組只能進(jìn)行賦值和取值，而且長度是不可變化的，所以給我們的操作帶來很大的麻煩，但是用順序表就可以進(jìn)行刪除，插入等操作。其實(shí)順序表內(nèi)部同樣適用數(shù)組來表示的，只不過這個(gè)數(shù)據(jù)我們可以改變他的長度，這樣說來我們就好辦了，首先我們要為順序表定義一個(gè)數(shù)組，同時(shí)在定義一個(gè)值來記錄線性表的長度，所以第一步我們就有了如下
準(zhǔn)備事件做好了以后，我們肯定會(huì)對(duì)順序表進(jìn)行初始化，剛剛開始數(shù)組的長度肯定是0。但是我們必須要為數(shù)組開辟一個(gè)內(nèi)存空間，來存儲(chǔ)要插入的元素，如下
其他的都比較簡(jiǎn)單，我主要說下插入和刪除
插入一個(gè)元素的時(shí)候，如果插在第i個(gè)位置，那么意味著它后面所有的元素前部往后面移一位，但是我們必須把i個(gè)位置留出來給即將插入的元素。但是我們還必須考慮，如果這個(gè)數(shù)組滿了的情況。如果滿了，我們必須重新為順序表開辟內(nèi)存空間，然后把以前的元素進(jìn)行遷移到新的表中，java實(shí)現(xiàn)如下
代碼看出，我們把從第i個(gè)位置的元素全部往后移（包括第i個(gè)元素）然后在把第i個(gè)元素進(jìn)行賦值
刪除第i個(gè)元素，這個(gè)和上面的正好相反，如果刪除第i個(gè)元素意味著在i之后的元素前部往前移一位。
3：順序表操作效率分析
因?yàn)轫樞虮硎蔷哂兴饕模詆et()和set()效率極高，時(shí)間復(fù)雜度都是o(n)。
從上面發(fā)現(xiàn)，在插入和刪除的時(shí)候都是需要大量元素的移動(dòng)，因?yàn)樵诟鱾€(gè)位置插入元素的概率相同，所以平均插入一個(gè)元素要移動(dòng)的元素是2/n。那么它的時(shí)間復(fù)雜度就是o(n)，如果要容器滿了，那么就需要申請(qǐng)更大的容器來存儲(chǔ)新加入的元素，那么效率會(huì)更加的低下。所以順序表的靜態(tài)性好，動(dòng)態(tài)性就很差了，所以在選擇的時(shí)候就要注意一下。
4：?jiǎn)捂湵淼膶?shí)現(xiàn)
線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用若干地址分散的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，邏輯上相鄰的2個(gè)元素，物理地址不一定相同，這么說來就充分的利用了內(nèi)存中的地址。但是我們必須用附加信息來連接2個(gè)不同的數(shù)據(jù)元素，所以這里就引進(jìn)了2個(gè)概念，數(shù)據(jù)域(data)和地址域(next)，其中數(shù)據(jù)域存儲(chǔ)的是這個(gè)元素的值，地址域存儲(chǔ)下一個(gè)元素的地址。其中數(shù)據(jù)域和地址域聯(lián)合起來我們稱為節(jié)點(diǎn)（node）。如果只有后繼節(jié)點(diǎn)沒有前驅(qū)節(jié)點(diǎn)我們就稱為單鏈表，那么現(xiàn)在我們來看看單鏈表的實(shí)現(xiàn)。
首先我們要定義一個(gè)節(jié)點(diǎn)node
|
1
2
3
4
5
6
7
8
9
10
11
|
public class node<t> { public t data;//數(shù)據(jù)域 public node next;//地址域 public node() { this(null, null); } public node(t data, node next) { this.data = data; this.next = next; }} |
現(xiàn)在我們想象一下，a(x)和b(y)2個(gè)節(jié)點(diǎn)，其中a的后繼節(jié)點(diǎn)是b，那么我們?cè)趺幢硎灸?，如?/p>
|
1
2
3
|
node<string> a=new node<t>(x,null);node<string> b=new node<t>(y,null);a.next=b。 |
也可以把a(bǔ)寫成node<string> a=new node<t>(x,b);
ok現(xiàn)在我們正式開始實(shí)現(xiàn)一個(gè)帶有頭節(jié)點(diǎn)的單鏈表
我們可以把頭指針想象成一個(gè)指針來便于我們的操作，我們先看如何實(shí)現(xiàn)單鏈表的長度
|
1
2
3
4
5
6
7
8
9
|
public int length() { int i = 0; node<t> p = this.head.next; while (p != null) { p = p.next; i++; } return i; } |
因?yàn)檫@是一個(gè)鏈?zhǔn)降慕Y(jié)構(gòu)，我們無法得知長度，只能通過循環(huán)來知道鏈表中節(jié)點(diǎn)的個(gè)數(shù)，因?yàn)轭^指針的后繼節(jié)點(diǎn)就是我們鏈表中第一個(gè)節(jié)點(diǎn)，所以我們就可以這樣往下循環(huán)來得知。
獲取第i個(gè)節(jié)點(diǎn)的值
同樣我們無法直接獲取節(jié)點(diǎn)，這個(gè)時(shí)候同樣采用循環(huán)，如果循環(huán)第i個(gè)元素值等于我們i那么我們就獲取這個(gè)節(jié)點(diǎn)，然后得到值
|
1
2
3
4
5
6
7
8
9
10
11
12
|
public t get(int i) { if (i >= 0) { node<t> p = this.head; for (int j = 0; j <= i; j++) { p = p.next; } if (p!=null){ return p.data; } } return null; } |
在第i個(gè)位置插入一個(gè)節(jié)點(diǎn)
首先我們必須要找到要插入節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),然后前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向這個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向原來前驅(qū)節(jié)點(diǎn)的后繼節(jié)點(diǎn)。
從代碼看出我們是根據(jù)頭節(jié)點(diǎn)進(jìn)行循環(huán)的。加入p.next!=null的目的是為了當(dāng)循環(huán)到最后一個(gè)節(jié)點(diǎn)的時(shí)候就停止，不在繼續(xù)了。
移除第i個(gè)節(jié)點(diǎn)
如果我們要?jiǎng)h除第i個(gè)節(jié)點(diǎn)和上面差不多，同樣我們要找到這個(gè)第i個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，和上面代碼差不多。
在鏈表后追加一個(gè)節(jié)點(diǎn)。
如果傳統(tǒng)的話我們可以采取insert(this.length,x);但是這樣一來計(jì)算長度的時(shí)候就需要遍歷鏈表無疑速度減慢，只需要如下
insert(integer.max_value, x)即可，從插入代碼可以看到當(dāng)循環(huán)到最后一個(gè)節(jié)點(diǎn)就不會(huì)繼續(xù)了，然后把新的節(jié)點(diǎn)加入最后即可。
5：排序單鏈表
排序首先我們需要我們的元素要繼承comparable。
我們就說插入和刪除。先說插入
如果插入一個(gè)元素，我們先獲取要插入這個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。（x.compareto(y)<0 表示小于y）
其中p.data.next.compareto(x)<0如果跳出循環(huán)說明p節(jié)點(diǎn)值大于或等于x
如果刪除一個(gè)元素，和上面的基本一樣，但是要加上一個(gè)判斷如下
其中通過上面判斷我們知道p節(jié)點(diǎn)大于或等于x節(jié)點(diǎn)了，所以需要再次判斷。
6：?jiǎn)捂湵聿僮餍史治?/strong>
單鏈表在獲取元素和設(shè)置元素的時(shí)候都需要進(jìn)行遍歷所以時(shí)間復(fù)雜度o(n)
如果在p節(jié)點(diǎn)插入或刪除元素，只需要修改鏈的后繼節(jié)點(diǎn)的地址即可所以時(shí)間復(fù)雜度o(1),但是如果插入類似insert(i,x)就需要進(jìn)行遍歷了，那么時(shí)間復(fù)雜度就是o(n).
對(duì)單鏈表進(jìn)行插入和刪除只需要改變少量節(jié)點(diǎn)的鏈，不需要移動(dòng)元素，單鏈表的插入和刪除都是動(dòng)態(tài)申請(qǐng)和釋放的，不需要預(yù)先分配存儲(chǔ)空間，從而不會(huì)因?yàn)榇鎯?chǔ)空間不足而進(jìn)行擴(kuò)容，提高了運(yùn)行效率。
7：雙鏈表的實(shí)現(xiàn)
雙鏈表和單鏈表大多是相同的只不過多了前驅(qū)節(jié)點(diǎn)，現(xiàn)在我們先定義一下雙鏈表
我們這里來演示循環(huán)雙鏈表的實(shí)現(xiàn)?；竞蛦捂湵硐嗤徊贿^如果為空鏈表那么它的后繼節(jié)點(diǎn)就是頭節(jié)點(diǎn)。ok我們先來看
求雙鏈表的長度（基本和單鏈表一樣后面一樣的不在寫了）因?yàn)槭茄h(huán)雙鏈表最后一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)為
我們這里只說插入和刪除（其他基本一樣和單鏈表）
插入
同樣我們需要找到要插入的節(jié)點(diǎn)
其中p.next!=this.head表示如果是最后一個(gè)節(jié)點(diǎn)則跳出循環(huán)。其中要插入的節(jié)點(diǎn)在p節(jié)點(diǎn)之后，然后我們就好理解了。
刪除
和上面的差不多
8：循環(huán)雙鏈表
根本和單鏈表一樣。也是先找到節(jié)點(diǎn)的位置然后插入或刪除
總結(jié)：主要是回顧一下線性表，通過對(duì)線性表的了解，在以后我們看java容器源碼的時(shí)候會(huì)帶來極大的幫助
以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時(shí)也希望多多支持服務(wù)器之家！
