在線性表接口的實現(xiàn)_Java中，我們實現(xiàn)了線性表的接口，今天北大青鳥北京學(xué)校老師講解實現(xiàn)線性表的順序存儲結(jié)構(gòu)——順序表類。
北大青鳥北京學(xué)校老師首先說明了順序表的定義：
線性表的順序存儲是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存儲次序與它們在線性表中的邏輯次序相同，即元素ai與其直接前驅(qū)ai-1及直接后繼ai+1的存儲位置相鄰。順序存儲的線性表也成為順序表(sequential list)。
順序表類SeqList提供線性表基于順序存儲結(jié)構(gòu)的一種實現(xiàn)，它有兩個私有成員變量table和n，table是一個存放元素的對象數(shù)組；n為線性表長度，n≤table.length。SeqList聲明如下，它實現(xiàn)了線性表的接口LList。
1. package dataStructure.linearList;
2. import dataStructure.linearList.LList;
3.
4. public class SeqList<E> implements LList<E> //順序表類，實現(xiàn)線性表接口
5. {
6. private Object[] table; //對象數(shù)組，私有成員
7. private int n; //順序表長度
8.
9. public SeqList(int capacity) //構(gòu)造方法，創(chuàng)建置頂容量的空表
10. {
11. this.table = new Object[Math.abs(capacity)];
12. this.n = 0;
13. }
14.
15. public SeqList() //指定空表的默認(rèn)容量
16. {
17. this(16); （北大青鳥北京）
18. }
19.
20. public boolean isEmpty() //判斷順序表是否為空，若空返回true
21. {
22. return this.n == 0;
23. }
24.
25. public int length() //返回順序表長度
26. {
27. return this.n;
28. }
29.
30. public E get(int index) //返回index(初值為0)位置的對象，若序號無效，返回null
31. {
32. if(index>=0 && index < this.n) （北大青鳥北京）
33. {
34. return (E)this.table[index];
35. }
36. return null;
37. }
38.
39. public E set(int index,E element) //設(shè)置index位置的對象為element，若操作成功，放回原對象，否則返回null （北大青鳥北京）
40. {
41. if(index >= 0 && index < this.n && element != null)
42. {
43. E old =(E)this.table[index];
44. this.table[index] = element;
45. return old;
46. }
47. return null;
48. }
49.
50. public boolean add(int index,E element) //在index位置插入element對象，若操作成功返回true，不能插入null
51. {
52. if(element == null) //不能插入null
53. {
54. return false;
55. }
56. if(this.n == table.length) //若數(shù)組滿，則需要擴(kuò)充順序表容量
57. {
58. Object[] temp = this.table;
59. this.table = new Object[temp.length*2]; //重新申請一個容量更大的數(shù)組
60. for(int i = 0;i < temp.length;i++)
61. {
62. this.table[i] = temp[i];
63. } （北大青鳥北京）
64. }
65.
66. if(index < 0) //下標(biāo)容錯
67. {
68. index = 0;
69. }
70. if(index > this.n)
71. {
72. index =this.n;
73. }
74. for(int j = this.n-1;j >= index;j--) //元素后移，平均移動n/2
75. {
76. this.table[j+1] = this.table[j];
77. }
78. this.table[index] = element;
79. this.n++; （北大青鳥北京）
80. return true;
81. }
82.
83. public boolean add(E element) //在順序表最后插入element對象
84. {
85. return add(this.n,element);
86. }
87.
88. public E remove(int index) //移去index位置的對象，若操作成功，則返回被移去的對象，否者返回null
89. {
90. if(this.n != 0 && index >= 0 && index < this.n)
91. {
92. E old = (E)this.table[index];
93. for(int j = index;j < this.n-1;j++) //元素前移，平均移動n/2
94. {
95. this.table[j] = this.table[j + 1];
96. }
97. this.table[this.n - 1] = null;
98. this.n--;
99. return old;
100. }
101. return null;
102. } （北大青鳥北京）
103.
104. public void clear() //清空順序表
105. {
106. if(this.n != 0)
107. {
108. for(int i = 0;i < this.n;i++)
109. {
110. this.table[i] = null;
111. }
112. this.n=0;
113. }
114. }
115. public String toString() //返回顯示所有元素的字符串，形式為(,)
116. {
117. String str = "(";
118. if(this.n != 0)
119. {
120. for(int i = 0;i < this.n - 1;i++)
121. {
122. str += this.table[i].toString()+",";
123. }
124. str += this.table[this.n - 1].toString();
125. }
126. return str + ")";
127. }
128.}
package dataStructure.linearList;
import dataStructure.linearList.LList;
public class SeqList<E> implements LList<E> //順序表類，實現(xiàn)線性表接口
{
private Object[] table; //對象數(shù)組，私有成員
private int n; //順序表長度
public SeqList(int capacity) //構(gòu)造方法，創(chuàng)建置頂容量的空表
{
this.table = new Object[Math.abs(capacity)];
this.n = 0;
}
public SeqList() //指定空表的默認(rèn)容量
{
this(16);
}
public boolean isEmpty() //判斷順序表是否為空，若空返回true
{
return this.n == 0;
}
public int length() //返回順序表長度
{
return this.n;
}
public E get(int index) //返回index(初值為0)位置的對象，若序號無效，返回null
{
if(index>=0 && index < this.n)
{
return (E)this.table[index];
}
return null;
}
public E set(int index,E element) //設(shè)置index位置的對象為element，若操作成功，放回原對象，否則返回null
{
if(index >= 0 && index < this.n && element != null)
{
E old =(E)this.table[index];
this.table[index] = element;
return old;
}
return null;
}
public boolean add(int index,E element) //在index位置插入element對象，若操作成功返回true，不能插入null
{
if(element == null) //不能插入null
{
return false;
}
if(this.n == table.length) //若數(shù)組滿，則需要擴(kuò)充順序表容量
{
Object[] temp = this.table;
this.table = new Object[temp.length*2]; //重新申請一個容量更大的數(shù)組
for(int i = 0;i < temp.length;i++)
{
this.table[i] = temp[i];
}
}
if(index < 0) //下標(biāo)容錯
{
index = 0;
}
if(index > this.n)
{
index =this.n;
}
for(int j = this.n-1;j >= index;j--) //元素后移，平均移動n/2
{
this.table[j+1] = this.table[j];
}
this.table[index] = element;
this.n++;
return true;
}
public boolean add(E element) //在順序表最后插入element對象
{
return add(this.n,element);
}
public E remove(int index) //移去index位置的對象，若操作成功，則返回被移去的對象，否者返回null
{
if(this.n != 0 && index >= 0 && index < this.n)
{
E old = (E)this.table[index];
for(int j = index;j < this.n-1;j++) //元素前移，平均移動n/2
{
this.table[j] = this.table[j + 1];
}
this.table[this.n - 1] = null;
this.n--;
return old;
}
return null;
}
public void clear() //清空順序表
{
if(this.n != 0)
{
for(int i = 0;i < this.n;i++)
{
this.table[i] = null;
}
this.n=0;
}
}
public String toString() //返回顯示所有元素的字符串，形式為(,)
{
String str = "(";
if(this.n != 0)
{
for(int i = 0;i < this.n - 1;i++)
{
str += this.table[i].toString()+",";
}
str += this.table[this.n - 1].toString();
}
return str + ")";（北大青鳥北京）
}
}
順序表是一種隨即存取結(jié)構(gòu)，存取任何一個元素的get()、set()方法的時間復(fù)雜度是O(1)。 （北大青鳥北京）
對順序表進(jìn)行插入或刪除操作是，算法所花費的時間主要用于移動元素。在等概率情況下，插入一個元素平均需要移動一半的元素，時間復(fù)雜度為O(n)。同里，刪除一個元素的時間復(fù)雜度亦為O(n)。（北大青鳥北京）
綜上所述，順序表具有下列特點：
①：元素的物理存儲順序直接反映表中元素的邏輯順序，可以隨機(jī)存取元素。
②：插入和刪除的操作效率很低。每插入或刪除一個元素，可能需要移動大量元素，其平均移動次數(shù)是順序表長度的一半。再者，數(shù)組容量不可更改，存在因容量小造成數(shù)據(jù)溢出，或因容量過大造成內(nèi)存資源浪費的問題。解決數(shù)據(jù)溢出的方法是，申請另一個更大容量的數(shù)組，并進(jìn)行數(shù)組元素復(fù)制，但插入操作效率很低。
（北大青鳥北京）
