这个SimepleList就是一个最简单的用数组实现的表。为了更好的表达表这个结构的特点，只实现存储int型数组的形式。并且没有结合泛型，接口等机制进行更高层次的抽象处理，不过以后我会在这个基础上编写一个类似JDK中的ArrayList类的数据结构。
这个SimpleList主要涉及以下功能点：
- 创建表；
- 重置表；
- 查询表中数据元素个数；
- 在位置x插入数据元素；
- 删除位置x的数据元素；
- 在尾部追加数据元素；
- 修改位置x的元素值；
- 获取位置x的元素值；
- 判断表是否为空表；
- 判断表是否已经满；
- 输出数组当前所有元素。
属性
- public static int DEFAULT_CAPACITY ： 默认表大小
- private int size ： 表中元素个数
- private int[] elements ： 元素数组
构造器
共有两个构造器，一个为使用默认容器大小来构造表，一个则是使用自定义大小。
clear()和init()函数功能见后，主要是用来初始化成员变量的。
public SimpleList(){
clear();
}
public SimpleList(int size){
size = 0;
init(size);
}
函数
inti()初始化元素数组。
public void init(int capacity){
elements = new int[capacity];
}
clear()函数用默认构造函数重置表的状态
public void clear(){
size = 0;
init(DEFAULT_CAPACITY);
}
接下来是典型的一行代码实现的功能。
public int size(){return size;}
public boolean isEmpty(){
return size == 0 ? true : false;
}
public boolean isFull(){
return size() == elements.length ? true : false;
}
insert()在指定位置idx插入一个元素，idx的取值范围为0~size. idx为size则在尾部插入元素,其余则是idx位置的前面插入元素。
在插入操作中，其花销是比较昂贵的。因为插入元素时，会涉及到元素的移动。最坏的情况则是在头部插入元素，则需要把原来的所有元素都后移一位，这个函数的时间复杂度是线性增长的。
public boolean insert(int idx, int ele){
/* 表已满 */
if(isFull())
return false;
/* 判断传入的参数pos是否合法 ,= =,这个和上面的可以合并？*/
if(idx < 0 || idx > size)
return false;
/* idx位置及其后所有数据后移一位 */
for(int i=size()-1; i >= idx; i--){
elements[i+1] = elements[i];
}
elements[idx] = ele;
size++;
return true;
}
append()复用insert()方法，只在数组尾部插入的元素。该方法的时间复杂度是常数，并不涉及元素的移动。
public boolean append(int ele){
return insert(size(), ele);
}
根据提供的索引获取对应元素的值，这里可能就会涉及到当提供的索引是非法的情况，本实现中该情况处理为抛出一个异常。
同样的根据索引设置新的元素值也是类似的。
public int getElementByPos(int idx) throws IllegalArgumentException{
if(idx < 0 || idx > size())
throw new IllegalArgumentException("The param idx is illegal.");
return elements[idx];
}
public void setElementByPos(int idx, int ele) throws IllegalArgumentException{
if(idx < 0 || idx > size())
throw new IllegalArgumentException("The param idx is illegal.");
elements[idx] = ele;
}
移除数组中的元素的时间复杂度也是线性增长的。当有元素被删除时，可能需要把该元素后的所有元素前移一位，最坏情况就是删除第一个元素。
public boolean remove(int idx){
/* 判断是否空表 */
if(isEmpty())
return false;
/* 判断idx是否合法 */
if(idx<0 || idx>size()-1)
return false;
/* idx往后的元素前移一位 */
for(int i=idx; i<size()-1; i++){
elements[i] = elements[i+1];
}
size--;
elements[size] = 0; /* 初始化移位产生的多余元素 */
return true;
}
这里重写了toString()方法，打印数组元素，只是为了方便测试看结果。哈哈哈哈哈。。。。
@Override
public String toString() {
return "ArrayTable [element=" + Arrays.toString(elements) + "] size=" + size;
}
总结
该数据结构实现还是很简单的，纯属入门的练手之作。
源代码
|
|