数据结构——SimpleList的实现

这个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;
}

总结

该数据结构实现还是很简单的,纯属入门的练手之作。

源代码

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
161
162
163
164
165
166
167
168
169
import java.util.Arrays;
/**
* 用简单数组来实现表的数据结构
* 该数据结构只要涉及以下功能:
* 1.创建表;
* 2.删除表中所有数据;
* 3.查询表中数据元素个数;
* 4.在位置x插入数据元素;
* 5.删除位置x的数据元素;
* 6.在尾部追加数据元素;
* 7.修改某个位置的元素值;
* 8.获取某个位置的元素值;
* 9.判断表是否为空表;
* 10.输出数组当前所有元素.
*
* PS:本版本数组大小不可变.
* @author Bingo
* @version 0.1
*/
public class SimpleList {
private int[] elements;
private int size;
/**
* 默认表大小
*/
private final static int DEFAULT_CAPACITY = 8;
/**
* 默认构造函数,默认数组大小为64个数据元素
*/
public SimpleList(){
clear();
}
/**
* 根据用户的需求创建响应大小的表
* @param size 表元素个数
*/
public SimpleList(int size){
size = 0;
init(size);
}
/**
* 返回当前表中数据元素个数
* @return
*/
public int size(){
return size;
}
/**
* 判断表是否为空表
* @return 空表返回true,否则返回false
*/
public boolean isEmpty(){
return size == 0 ? true : false;
}
/**
* 初始化数组
* @param capacity 数组容量大小
*/
public void init(int capacity){
elements = new int[capacity];
}
/**
* 初始化所有数据为0
*/
public void clear(){
size = 0;
init(DEFAULT_CAPACITY);
}
/**
* 判断表是否已满
* @return 表满了返回true,否则返回false
*/
public boolean isFull(){
return size() == elements.length ? true : false;
}
/**
* 在位置idx插入一个元素,其中idx取值为0~size,
* idx为0则为在头部插入元素,idx为size则在尾部插入元素,
* 所以本插入函数为在idx位置的前面插入元素,size表示最后一个元素的后面.
* @param ele 待插入元素值
* @param idx 插入的位置
* @return 插入成功返回true,插入失败返回false
*/
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;
}
/**
* 在尾部追加一个元素.
* @param ele 元素值
* @return 追加元素成功返回true,否则返回false.
*/
public boolean append(int ele){
return insert(size(), ele);
}
/**
* 获取下标为idx的元素,取值范围是0~(size-1).
* @param idx 元素下标
* @return 返回获取的元素值
* @throws IllegalArgumentException 当pos取值范围不合法时抛出异常.
*/
public int getElementByPos(int idx) throws IllegalArgumentException{
if(idx < 0 || idx > size())
throw new IllegalArgumentException("The param idx is illegal.");
return elements[idx];
}
/**
* 给下标为idx的元素设置一个新的值.
* @param ele 新的元素值
* @param idx 元素的下标
* @throws IllegalArgumentException 当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;
}
/**
* 移除表中下标为idx的元素,idx的取值范围为0~(size-1).
* @param idx 元素下标
* @return 删除成功返回true,否则返回false
*/
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;
}
@Override
public String toString() {
return "ArrayTable [element=" + Arrays.toString(elements) + "] size=" + size;
}
}