欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构顺序表——用Java实现顺序表(接口以及接口的实现)

程序员文章站 2024-03-20 13:59:28
...

1,接口的定义

package seqlist;
 interface SeqList {
// 打印顺序表    
 public void display() ;
// 在 pos 位置新增元素    
 public void add(int pos, int data);
// 判定是否包含某个元素    
 public boolean contains(int toFind);
// 查找某个元素对应的位置    
 public int search(int toFind);
// 获取 pos 位置的元素    
 public int getPos(int pos) ;
// 给 pos 位置的元素设为 value    
 public void setPos(int pos, int value) ;
// 删除第一次出现的关键字key    
 public void remove(int toRemove);
// 获取顺序表长度    
 public int size() ;
// 清空顺序表    
    public void clear() ;
}

2,顺序表类的定义以及实现接口

package seqlist;

import java.util.Arrays;

public class SeqListImpl implements SeqList {
    private int[] elemant;
    private int usedSide;

    public SeqListImpl() {
        this.elemant = new int[10];
        this.usedSide = 0;
    }
    // 打印顺序表  
    @Override
    public void display() {
        if (this.isEmpty()) {
            System.out.println("顺序表为空!");
        }
        for (int i = 0; i <this.usedSide ; i++) {
            System.out.print(this.elemant[i]+" ");
        }
        System.out.println();
    }
    //判断数组是否满
    private boolean isFull() {
        return this.usedSide == this.elemant.length;
    }

    // 在 pos 位置新增元素
    @Override
    public void add(int pos, int data) {
        //判断pos的合法性
        if (pos < 0 || pos > this.usedSide) {
            System.out.println("输入不合法!");
        }
        //如果为满,使原来数组扩大为原来的2倍
        if (isFull()) {
            this.elemant = Arrays.copyOf(this.elemant,this.elemant.length*2);
        }
        //使pos之后的元素都向后移动
        for (int i = usedSide - 1; i >=pos ; i--) {
            elemant[i+1] = elemant[i];
        }
        elemant[pos] = data;
        usedSide++;
    }
    // 判定是否包含某个元素  
    @Override
    public boolean contains(int toFind) {
        for (int i = 0; i < this.usedSide; i++) {
            if (elemant[i] == toFind) {
                return true;
            }
        }
        return false;
    }
    //判断是否为空
    public boolean isEmpty() {
        return this.usedSide == 0;
    }
    // 查找某个元素对应的位置
    @Override
    public int search(int toFind) {
        if (isEmpty()) {
            return -1;
        }
        for (int i = 0; i < this.usedSide; i++) {
            if (elemant[i] == toFind) {
                return i;
            }
        }
        return -1;
    }
    // 获取 pos 位置的元素  
    @Override
    public int getPos(int pos) {
        return this.elemant[pos];
    }
    // 给 pos 位置的元素设为 value    
    @Override
    public void setPos(int pos, int value) {
        elemant[pos] = value;
    }
    // 删除第一次出现的关键字key    
    @Override
    public void remove(int key) {
        if (contains(key)) {
            int index = search(key);
            for (int i = index; i < this.usedSide -1; i++) {
                this.elemant[i] = this.elemant[i+1];
            }
            this.elemant[this.usedSide - 1] = 0;
            this.usedSide--;
        }
    }
    // 获取顺序表长度
    @Override
    public int size() {
        return this.elemant.length;
    }
    // 清空顺序表
    @Override
    public void clear() {
        for (int i = 0; i < this.usedSide ; i++) {
            this.elemant[i] = 0;
        }
        this.usedSide = 0;
    }
}

3,测试类

package seqlist;

public class TestSeqList {
    public static void main(String[] args) {
        SeqListImpl seqList = new SeqListImpl();
        for (int i = 0; i < 6; i++) {
            seqList.add(i,i+1);
        }
        seqList.display();
        System.out.println("判断是否包含数字2:"+seqList.contains(2));
        System.out.println(seqList.getPos(2));
        System.out.println(seqList.search(3));
        seqList.remove(2);
        seqList.display();
        seqList.remove(1);
        seqList.display();
        seqList.remove(3);
        seqList.display();
        seqList.clear();
        seqList.display();
    }
}

4,运行结果

1 2 3 4 5 6 
判断是否包含数字2true
3
2
1 3 4 5 6 
3 4 5 6 
4 5 6 
顺序表为空!


Process finished with exit code 0