線性表的定義
線性表的邏輯特征：
- ①有且僅有一個(gè)稱為開(kāi)始元素的a1，她沒(méi)有前趨，僅有一個(gè)后繼結(jié)點(diǎn)a2；
- ②有且僅有一個(gè)稱為終端元素的an,他沒(méi)有后繼，只有一個(gè)直接前驅(qū)a(n-1)；
- ③其余元素ai(2≤i≤n-1)稱為內(nèi)部元素，他們都有且僅有一個(gè)直接前驅(qū)a(i-1)和直接后繼a(i+1)。
線性表的圖像表示
線性表的基本運(yùn)算
- 線性表初始化
- 求表長(zhǎng)
- 按索引值查找元素
- 按值查找
- 插入元素
- 刪除
線性表的存儲(chǔ)之順序存儲(chǔ)
線性表順序存儲(chǔ)的定義：線性表的順序存儲(chǔ)指的是將線性表的數(shù)據(jù)元素按其邏輯次序依次存入一組連續(xù)的存儲(chǔ)單元里，用這種方式存儲(chǔ)的線性表稱為順序表。
定義線性表
定義線性表的默認(rèn)空間大小，定義一個(gè)數(shù)組，定義數(shù)組的長(zhǎng)度，初始化一個(gè)size用來(lái)保存里面元素的個(gè)數(shù)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/** 定義線性表默認(rèn)空間大小 */private final Integer ListSize=100;/**定義數(shù)組長(zhǎng)度*/private Integer Len;/** 定義線性表保存的數(shù)據(jù)類型 * 使用泛型*/private Object[] list;/**存一個(gè)當(dāng)前元素的個(gè)數(shù)*/private Integer size=0;/**定義默認(rèn)線性表*/public SeqList(){ Len = ListSize; this.list = new Object[Len]; size++;} |
初始化線性表
把線性表里面的元素全部置空
|
1
2
3
4
5
6
7
|
/**清空線性表*/public void clear(){ for (int i = 0; i < size; i++) { list[i]=null; } size=0;} |
添加元素
這里采用尾插法，即每次默認(rèn)將元素放在最后面
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
/**添加元素到指定位置*/public void insert(T element , int index){ if(index>=Len || index<0){ throw new IndexOutOfBoundsException("輸入的索引值超過(guò)了線性表的范圍"); } Capacity(size+1); //將添加元素的元素往后移一位 for (int i = size-2; i >= index-1; i--) { list[i+1]=list[i]; } list[index-1]=element; size++;}/**添加元素到末尾*/public void add(T element){ insert(element,size);} |
查找元素
這個(gè)模塊分為按索引值查找，和按元素值查找
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/**線性表的查找 * 按索引值查找*/public T getNode(int index){ return (T)list[index-1];}/**按元素值查找返回索引值*/public int LocateNode(T t){ for(int i=0;i<list.length;i++){ if(list[i].equals(t)){ return i+1; } } System.out.println("沒(méi)有找到該元素！"); return -1;} |
刪除元素
刪除元素，又分為刪除指定元素，和刪除最后一個(gè)元素
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/**刪除指定位置的元素*/public T delete(int index){ if(!OutIndex(index)){ throw new IndexOutOfBoundsException("刪除位置不在線性表的索引范圍內(nèi)！"); } for (int i = index-1; i < size-1; i++) { list[i]=list[i+1]; } /*if(size - index >0){ System.arraycopy(list,index,list,index-1,size-index); }*/ list[size-1]=null; size--; return (T) list;}/**刪除最后一個(gè)元素*/public T remove(){ return delete(size-1);} |
打印線性表
打印線性表，其實(shí)就是重寫一個(gè)toString方法，將線性表打印出來(lái)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
/**循環(huán)打印線性表*/ @Override public String toString(){ StringBuilder sb = new StringBuilder(); if(isEmpty()){ return "[]"; } else { sb.append("["); for (int i = 0; i < size-1; i++) { int a=0; if(list[i]!=null){ sb.append(list[ i ]); } else { break; } sb.append(","); } sb.append("]"); sb.deleteCharAt(sb.indexOf(",]")); } return sb.toString(); } |
實(shí)現(xiàn)的完整代碼
|
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
156
157
158
159
160
|
class SeqList<T>{ /** 定義線性表默認(rèn)空間大小 */ private final Integer ListSize=100; /**定義數(shù)組長(zhǎng)度*/ private Integer Len; /** 定義線性表保存的數(shù)據(jù)類型 * 使用泛型*/ private Object[] list; /**存一個(gè)當(dāng)前元素的個(gè)數(shù)*/ private Integer size=0; /**定義默認(rèn)線性表*/ public SeqList(){ Len = ListSize; this.list = new Object[Len]; size++; } /**定義自定義長(zhǎng)度的線性表*/ public SeqList(int length){ Len = length; list = new Object[Len]; size++; } /**獲取當(dāng)前線性表的長(zhǎng)度*/ public int getLen(){ return Len; } /**獲取當(dāng)前線性表元素的個(gè)數(shù)*/ public int getSize(){ return size; } /**根據(jù)元素查找在線性表中的位置，未找到返回-1*/ public int getIndex(T element){ for (int i = 0; i < size; i++) { if(list[i].equals(element)){ return i; } } return -1; } /**判斷是否表滿或表空*/ private boolean OutIndex(int index){ //return size==Len;//不擴(kuò)容的話，可以這樣寫，但是怕擴(kuò)容 if(index>size || index<0){ return false; } else { return true; } } /**根據(jù)索引值返回元素*/ private T getElement(int index){ if(!OutIndex(index)){ throw new IndexOutOfBoundsException("輸入的索引值超過(guò)了線性表的范圍"); /* System.out.println("輸入索引超過(guò)了線性的范圍"); return null; */ } return (T)list[index]; } /**擴(kuò)容*/ private T Capacity(int capacity){ if(capacity<Len){ Len = Len+(Len+1)/2; if(capacity<Len){ Capacity(Len); } else { list = Arrays.copyOf(list,Len); return (T) list; } } return (T)list; } /**添加元素到指定位置*/ public void insert(T element , int index){ if(index>=Len || index<0){ throw new IndexOutOfBoundsException("輸入的索引值超過(guò)了線性表的范圍"); } Capacity(size+1); //將添加元素的元素往后移一位 for (int i = size-2; i >= index-1; i--) { list[i+1]=list[i];// System.out.println("i="+i); } list[index-1]=element; size++; } /**添加元素到末尾*/ public void add(T element){ insert(element,size); } /**判斷元素表是否為空*/ public boolean isEmpty(){ return size==0; } /**刪除指定位置的元素*/ public T delete(int index){ if(!OutIndex(index)){ throw new IndexOutOfBoundsException("刪除位置不在線性表的索引范圍內(nèi)！"); } for (int i = index-1; i < size-1; i++) { list[i]=list[i+1]; } /*if(size - index >0){ System.arraycopy(list,index,list,index-1,size-index); }*/ list[size-1]=null; size--; return (T) list; } /**刪除最后一個(gè)元素*/ public T remove(){ return delete(size-1); } /**清空線性表*/ public void clear(){ for (int i = 0; i < size; i++) { list[i]=null; } size=0; } /**線性表的查找 * 按索引值查找*/ public T getNode(int index){ return (T)list[index-1]; } /**按元素值查找返回索引值*/ public int LocateNode(T t){ for(int i=0;i<list.length;i++){ if(list[i].equals(t)){ return i+1; } } System.out.println("沒(méi)有找到該元素！"); return -1; } /**循環(huán)打印線性表*/ @Override public String toString(){ StringBuilder sb = new StringBuilder(); if(isEmpty()){ return "[]"; } else { sb.append("["); for (int i = 0; i < size-1; i++) { int a=0; if(list[i]!=null){ sb.append(list[ i ]); } else { break; } sb.append(","); } sb.append("]"); sb.deleteCharAt(sb.indexOf(",]")); } return sb.toString(); }} |
測(cè)試一下
測(cè)試代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public static void main(String[] args) { SeqList<String> seqList = new SeqList<String>(); //添加一個(gè)元素 seqList.add("pier"); seqList.add("真好看"); seqList.add("90度點(diǎn)頭"); System.out.println("添加后的線性表為\n\t"+seqList.toString()); seqList.insert("pipi",1); System.out.println("在位置1的地方添加元素后的線性表為\n\t"+seqList.toString()); seqList.delete(1); System.out.println("刪除第二個(gè)元素后的線性表為\n\t"+seqList.toString()); System.out.println("pier時(shí)第"+seqList.LocateNode("pier")+"個(gè)元素"); System.out.println("第1個(gè)元素是"+seqList.getNode(1)+"。");} |
運(yùn)行結(jié)果
到此這篇關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)線性表之順序存儲(chǔ)詳解原理的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)結(jié)構(gòu) 內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/qq_43325476/article/details/120919973
