【数据结构 Java 版】玩转顺序表
判断顺序表是否已满
public boolean isFull(){
return this.usedSize == capacity;
}
在 pos 位置新增元素
public void add(int pos, int data){
if(pos<0 || pos>this.usedSize){
System.out.println("pos 位置不合法");
return;
}
if(isFull()){
// 扩容
this.elem=Arrays.copyOf(this.elem, 2*capacity);
capacity*=2;
}
for(int i = this.usedSize;i>pos;i--){
this.elem[i]=this.elem[i-1];
}
this.elem[pos]=data;
this.usedSize++;
}
打印顺序表
public void display(){
for(int i=0;i<this.usedSize;i++){
System.out.print(this.elem[i]+" ");
}
}
判断顺序表是否为空
public boolean isEmpty(){
return this.usedSize==0;
}
判断是否包含某个元素
public boolean contains(int toFind){
if(isEmpty()){
return false;
}
for(int i=0;i<this.usedSize;i++){
if(this.elem[i]==toFind){
return true;
}
}
return false;
}
查找某个元素的第一次出现的位置
public int search(int toFind){
if(isEmpty()){
return -1;
}
for(int i=0;i<this.usedSize;i++){
if(this.elem[i]==toFind){
return i;
}
}
return -1;
}
获取 pos 位置的元素
public int getPos(int pos){
if(isEmpty()){
return -1;
// throw new RuntimeException("顺序表为空");
}
if(pos<0 || pos>=this.usedSize){
throw new RuntimeException("顺序不合法");
}
return this.elem[pos];
}
其实上述代码返回 -1 其实是不一定的，因为在已知该数组不可能等于-1 的情况下，我们可以这样处理，但是如果能等于-1.就是错的，就需要换其他值（这相当于具体情况对业务进行处理）
也可以使用注释里的
throw new RuntimeException("顺序表为空");，这其实是手打抛出错误（异常）
获取顺序表长度
public int size(){
return this.usedSize;
}
给 pos 的位置的元素设为 value
public void setPos(int pos, int value){
if(pos<0 || pos>=this.usedSize){
throw new RuntimeException("pos 不合法")
}
this.elem[pos]=value;
}
删除第一次出现的关键字 key
public void remove(int toRemove){
if(isEmpty()){
System.out.println("数组为空");
return;
}
int index=search(toRemove);
if(indfex==-1){
System.out.println("没用你要删除的数字");
return;
}
for(int i =index;i<this.usedSize-1;i++){
this.elem[i]=this.elem[i+1];
}
this.usedSize--;
}
其实在循环中是不能删除最后一个元素的，因为
i < this.usedSize，但是上述代码是可以直接删除最后一个元素，因为 usedSize 自减后，就相当于删除最后一个元素了
清空顺序表
public void clear(){
for(int i=0;i<this.usedSize;i++){
this.elem[i]=0;
}
this.usedSize=0;
}
3. 增、删、改、查的时间复杂度
既然我们实现了以上接口，我们可以根据上述代码思考下，顺序表中增删改查的时间复杂度为多少
评论