数据结构学习二——顺序表
程序员文章站
2022-07-13 13:39:46
...
上节对数据结构有了一个概览，这节我们来对每种常见的数据结构进行一个庖丁解牛般的描述。这节论述的是最简单的数据结构——顺序表。
何为顺序表，顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。
将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。
采用顺序存储结构的线性表简称为“ 顺序表”。顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 1≤i≤n 其中，L是元素占用存储单元的长度。
有了这样理论知识，我们用代码实现相应的顺序表。在java中最典型的顺序表就是array。我们就自己实现一个array。
要实现顺序表，我们需要实现基本增删改查的操作，相应的结思维导图如下：
然后我将代码贴出来，然后一一进行分析。
首先是增加操作，代码如下：
/**
* Adds the specified object at the end of this {@code ArrayList}.
*
* @param object
* the object to add.
* @return always true
*/
@Override public boolean add(E object) {
Object[] a = array;
int s = size;
if (s == a.length) {
Object[] newArray = new Object[s +
(s < (MIN_CAPACITY_INCREMENT / 2) ?
MIN_CAPACITY_INCREMENT : s >> 1)];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
a[s] = object;
size = s + 1;
modCount++;
return true;
}
/**
* Inserts the specified object into this {@code ArrayList} at the specified
* location. The object is inserted before any previous element at the
* specified location. If the location is equal to the size of this
* {@code ArrayList}, the object is added at the end.
*
* @param index
* the index at which to insert the object.
* @param object
* the object to add.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location > size()}
*/
@Override public void add(int index, E object) {
Object[] a = array;
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
if (s < a.length) {
System.arraycopy(a, index, a, index + 1, s - index);
} else {
// assert s == a.length;
Object[] newArray = new Object[newCapacity(s)];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + 1, s - index);
array = a = newArray;
}
a[index] = object;
size = s + 1;
modCount++;
}
/**
* Adds the objects in the specified collection to this {@code ArrayList}.
*
* @param collection
* the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
*/
@Override public boolean addAll(Collection<? extends E> collection) {
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int s = size;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize > a.length) {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, s);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, s, newPartSize);
size = newSize;
modCount++;
return true;
}
/**
* Inserts the objects in the specified collection at the specified location
* in this List. The objects are added in the order they are returned from
* the collection's iterator.
*
* @param index
* the index at which to insert.
* @param collection
* the collection of objects.
* @return {@code true} if this {@code ArrayList} is modified, {@code false}
* otherwise.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location > size()}
*/
@Override
public boolean addAll(int index, Collection<? extends E> collection) {
int s = size;
if (index > s || index < 0) {
throwIndexOutOfBoundsException(index, s);
}
Object[] newPart = collection.toArray();
int newPartSize = newPart.length;
if (newPartSize == 0) {
return false;
}
Object[] a = array;
int newSize = s + newPartSize; // If add overflows, arraycopy will fail
if (newSize <= a.length) {
System.arraycopy(a, index, a, index + newPartSize, s - index);
} else {
int newCapacity = newCapacity(newSize - 1); // ~33% growth room
Object[] newArray = new Object[newCapacity];
System.arraycopy(a, 0, newArray, 0, index);
System.arraycopy(a, index, newArray, index + newPartSize, s-index);
array = a = newArray;
}
System.arraycopy(newPart, 0, a, index, newPartSize);
size = newSize;
modCount++;
return true;
}首先是在末尾插入元素的操作，判断他是否达到了数组最大容量，如果达到数组的最大长度，就进行扩容，扩容步骤就是判断此时数组中的元素个数是否大于6个，大于6个的话，就将数组的长度+此时个数*2，小于6个的话，就将数组长度+12.然后将数组指针+1。
然后是在指定位置插入元素。首先判断插入位置是否合法，如果合法的话，就在指定位置进行插入，然后将指定位置的后述元素进行++，同样有扩容操作，与上述一样，不做过多赘述。最后将数组指针+1.
紧接着就是添加元素的集合，获取要添加元素长度，然后循环遍历集合，将这个集合中的元素一一添加到老的集合中去。然后将数组指针+集合长度。
最后是在指定的位置添加元素，步骤和上述一样，不同的是将原集合的元素一一后移元素集合的位置。最后数组指针+集合长度。
这是顺序表增加操作。然后删除的操作。上代码：
/**
* Removes the object at the specified location from this list.
*
* @param index
* the index of the object to remove.
* @return the removed object.
* @throws IndexOutOfBoundsException
* when {@code location < 0 || location >= size()}
*/
@Override public E remove(int index) {
Object[] a = array;
int s = size;
if (index >= s) {
throwIndexOutOfBoundsException(index, s);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
System.arraycopy(a, index + 1, a, index, --s - index);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return result;
}
@Override public boolean remove(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
System.arraycopy(a, i + 1, a, i, --s - i);
a[s] = null; // Prevent memory leak
size = s;
modCount++;
return true;
}
}
}
return false;
}
@Override protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex == toIndex) {
return;
}
Object[] a = array;
int s = size;
if (fromIndex >= s) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " >= size " + size);
}
if (toIndex > s) {
throw new IndexOutOfBoundsException("toIndex " + toIndex
+ " > size " + size);
}
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException("fromIndex " + fromIndex
+ " > toIndex " + toIndex);
}
System.arraycopy(a, toIndex, a, fromIndex, s - toIndex);
int rangeSize = toIndex - fromIndex;
Arrays.fill(a, s - rangeSize, s, null);
size = s - rangeSize;
modCount++;
}
这包括三个方法。
①移除相应索引位置的元素，要判断索引是否超过数组的索引，如果满足要求的话，就相应索引位置的元素取出来，进行删除。然后将此位置后的元素进行前移 。
②移除数组中相应元素。判断此元素是否在数组中，如果在数组中的话，就将其元素取出来，进行删除。然后将此位置后的元素进行前移 。
③将一个区间段的元素进行移除。我们来判断要移除元素范围是否在数组中。如果满足条件，就将这个范围内元素删除，然后将其后续元素进行前移。
然后是修改操作。上代码：
public E set(int index, E object) {
Object[] a = array;
if (index >= size) {
throwIndexOutOfBoundsException(index, size);
}
@SuppressWarnings("unchecked") E result = (E) a[index];
a[index] = object;
return result;
}最后是查询操作，上代码：
/**
* Searches this {@code ArrayList} for the specified object.
*
* @param object
* the object to search for.
* @return {@code true} if {@code object} is an element of this
* {@code ArrayList}, {@code false} otherwise
*/
@Override public boolean contains(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return true;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return true;
}
}
}
return false;
}
@Override public int indexOf(Object object) {
Object[] a = array;
int s = size;
if (object != null) {
for (int i = 0; i < s; i++) {
if (object.equals(a[i])) {
return i;
}
}
} else {
for (int i = 0; i < s; i++) {
if (a[i] == null) {
return i;
}
}
}
return -1;
}
首先，是是否包含元素操作，遍历数组，看值是否相应元素是否相等，相等返回真，否则返回假。
接着，是获取索引的操作，遍历元素，看值是否相等，相等返回相应的索引，否则返回-1.
最后，是获取最后索引的操作，从后往前遍历元素，相等返回相应的索引，否则返回-1。
说完了增删改查的操作。我们还讨论这几个方法：
清空的方法，上代码：
@Override public void clear() {
if (size != 0) {
Arrays.fill(array, 0, size, null);
size = 0;
modCount++;
}
}扩容的方法，上代码：
public void ensureCapacity(int minimumCapacity) {
Object[] a = array;
if (a.length < minimumCapacity) {
Object[] newArray = new Object[minimumCapacity];
System.arraycopy(a, 0, newArray, 0, size);
array = newArray;
modCount++;
}
}当然，这个arraylist的方法还有很多，大家还可以自行分析，这里进一个抛砖引玉作用。
这就是我对顺序表一种总结。