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