什么是顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元，依次存储线性表中的各个元素、使得线性表中再逻辑结构上响铃的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系；
常见的如数组：
在Java中顺序表一般体现为两种 数组 与 集合，数组是固定长度的顺序表，集合是动态长度的顺序表，这里实现动态长度的顺序表；
顺序表的实现(直接上代码)
| 类名 | SequenceList |
|---|---|
| 成员方法 | 1.public void clear()：清空顺序表 2.publicboolean isEmpty()：判断顺序表是否为空，是返回true，否返回false 3.public int length():获取顺序表中元素的个数 4.public T get(int i):读取并返回顺序表中的第i个元素的值 5.public void insert(T t)：往顺序表中添加一个元素； 6.public void insert(int i,T t)：在顺序表的第i个元素之前插入一个值为t的数据元素。 7.public T remove(int i):删除并返回顺序表中第i个数据元素。 8.public int indexOf(T t):返回顺序表中首次出现的指定的数据元素的位序号，若不存在，则返回-1 |
| 成员变量 | 1.private T [] eles:存储元素的数组 2.private int N:记录顺序表的长度 3. private int modCount : 记录顺序表的操作次数 |
public class SequenceList<T> implements Iterable<T>{
private T[] eles;
private int N;
private int modCount;
public SequenceList(){
// this.eles =(T[]) new Object[1];
this.N = 0;
}
public void clear(){
modCount ++;
for (int i = 0;i<this.N;i++) {
eles[i] = null;
}
this.N = 0;
}
public boolean isEmpty(){
return this.N==0;
}
public int length(){
return this.N;
}
public T get(int index){
if(index<0 || index>this.N){
System.out.println("异常");
return null;
}
return this.eles[index];
}
public void insert(T t){
this.modCount++;
ensureCapacityInternal(this.N+1);
this.eles[this.N++] = t;
}
public void insert(int index,T t){
this.modCount++;
if(index<0|| index>this.N){
System.out.println("异常");
return;
}
ensureCapacityInternal(this.N+1);
for (int i = this.N; i>index; i--) {
this.eles[i]= this.eles[i-1];
}
this.eles[this.N++] = t;
}
public T remove(int index){
this.modCount++;
if(index<=0|| index>this.N){
System.out.println("异常");
return null;
}
T t = eles[index];
for (int i = index; i<this.N-1; i++) {
this.eles[i]= this.eles[i+1];
}
ensureCapacityInternal(--this.N);
return t;
}
private void ensureCapacityInternal(int minCapacity){
if(this.N == 0){
this.eles = (T []) new Object[minCapacity];
}else{
T[] temp = (T []) new Object[minCapacity];
int num = minCapacity;
if(num >this.eles.length){
num =this.eles.length;
}
System.arraycopy(this.eles,0,temp,0,num);
this.eles = temp;
}
}
public int indexOf(T t){
for (int i = 0; i < this.N; i++) {
if(this.eles[i].equals(t)){
return i;
}
}
return -1;
}
@Override
public Iterator<T> iterator() {
return new MyIterator();
}
private class MyIterator implements Iterator<T>{
private int cur ;
private int num;
public MyIterator(){
this.cur = 0;
this.num = modCount;
}
@Override
public boolean hasNext() {
checkModCount();
return cur< N;
}
@Override
public T next() {
checkModCount();
return eles[cur++];
}
private void checkModCount(){
if(this.num != modCount){
throw new RuntimeException("不合法的操作，在遍历元素时修改数据是不安全的！");
}
}
}
}
网友评论