Java实现顺序表的操作

本文实例为大家分享了java实现顺序表的基本操作，供大家参考，具体内容如下

静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。

接口

package com.github.sqlist;

public interface isequence {
    // 在 pos 位置插入 val
    boolean add(int pos, object data);

    // 查找关键字 key 找到返回 key 的下表，没有返回 -1
    int search(object key);

    // 查找是否包含关键字 key 是否在顺序表当中（这个和search有点冲突）
    boolean contains(object key);

    // 得到 pos 位置的值
    object getpos(int pos);

    // 删除第一次出现的关键字 key
    object remove(object key);

    // 得到顺序表的长度
    int size();

    // 打印顺序表
    void display();

    // 清空顺序表以防内存泄漏
    void clear();
}

实现接口里的每个方法

package com.github.sqlist;

import java.util.arrays;

/*
 * 顺序表
 */
public class mysequenceimpl implements isequence {

    private object[] elem;
    // 有效数据个数
    private int usedsize;
    private static final int default_size = 10;

    public sqlist() {
        this.elem = new object[default_size];
        this.usedsize = 0;
    }

    /**
     * 判断是否为满
     * @return 满了返回true,否则返回false
     */
    private boolean isfull() {
        return this.elem.length == this.usedsize;
    }

    /**
     * 在 pos 位置插入 val
     * @param pos
     *        要插入的位置
     * @param data
     *        要插入的值
     * @return
     *        插入成功返回true，否则返回false
     */
    @override
    public boolean add(int pos, object data) {
        // 1. 判断pos位置的合法性
        if (pos < 0 || pos > this.elem.length) {
            return false;
        }

        // 2. 判断是否满了，如果满了进行扩容
        if (isfull()) {
            this.elem = arrays.copyof(this.elem, 2*this.elem.length);
        }

        // 3. 把pos位置以及之后的数全部向后挪一个位置
        for (int i = this.usedsize-1; i >= pos; i--) {
            this.elem[i+1] = this.elem[i];
        }

        // 4. 在 pos 位置插入 val
        this.elem[pos] = data;

        // 5. 更新长度
        this.usedsize++;

        return true;
    }

    /**
     * 判断是否为空
     * @return 表为空返回true，否则返回false
     */
    private boolean isempty() {
        return this.usedsize == 0;
    }

    /**
     * 查找关键字 key 找到返回 key 的下表，没有返回 -1
     * @param key 关键字的值
     * @return 查找成功返回true，失败返回false
     */
    @override
    public int search(object key) {
        // 1. 判断是否为空
        if (isempty()) {
            return -1;
        }

        // 2. 遍历查找
        for (int i = 0; i < this.elem.length; i++) {
            // 注意：判断条件不能写成：this.elem[i] == key
            if (this.elem[i].equals(key)) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 查找是否包含关键字 key 是否在顺序表当中（这个和search有点冲突）
     * @param key 关键字的值
     * @return 查找成功返回true，失败返回false
     */
    @override
    public boolean contains(object key) {
        // 1. 判断是否为空
        if (isempty()) {
            return false;
        }

        // 2. 遍历查找
        for (int i = 0; i < this.elem.length; i++) {
            // 注意：判断条件不能写成：this.elem[i] == key
            if (this.elem[i].equals(key)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 得到 pos 位置的值
     * @param pos 得到的值的位置
     * @return 成功得到 pos位置的值返回true，否则返回false
     */
    @override
    public object getpos(int pos) {
        // 1. 判断位置是否合法
        if (pos<0 || pos>=this.elem.length) {
            return null;
        }

        // 2. 位置合法
        return this.elem[pos];
    }

    /**
     * 删除第一次出现的关键字 key
     * @param key 关键字
     * @return
     */
    @override
    public object remove(object key) {
        // 1. 先查表看有没有这个关键字
        // index:关键字下标
        int index = search(key);

        // 2. 若表里没有这个关键字
        if (index == -1) {
            return null;
        }

        // 3. 表里有这个关键字
        object data = this.elem[index];
        int i;
        // 删除第一次出现的关键字 key,把key后面的数全部向前挪一个位置
        for (i = index; i < this.usedsize; i++) {
            elem[i] = elem[i+1];
        }
        this.usedsize--;
        this.elem[i+1] = null;
        return data;
    }

    /**
     * 得到顺序表的长度
     * @return 顺序表的长度
     */
    @override
    public int size() {
        return this.usedsize;
    }

    /**
     * 打印顺序表
     */
    @override
    public void display() {
        for (int i = 0; i < this.usedsize; i++) {
            system.out.print(this.elem[i] + " ");
        }
        system.out.println();
    }

    /**
     * 清空顺序表以防内存泄漏
     */
    @override
    public void clear() {
        for (int i = 0; i < this.usedsize; i++) {
            this.elem[i] = null;
        }
    }
}

测试方法的正确性

package com.github.sqlist;


public class testdemo1 {
    public static void main(string[] args) {
        mysequenceimpl mysequence = new mysequenceimpl();

        for (int i = 0; i < 10; i++) {
            mysequence.add(i,i);
        }
        system.out.println("在最大值10的范围内插入数据：");
        mysequence.display();
        system.out.println();

        for (int i = 10; i < 20; i++) {
            mysequence.add(i,i);
        }
        system.out.println("扩容：");
        mysequence.display();
        system.out.println();

        system.out.println("随机位置插入数据：");
        mysequence.add(9,"list");
        mysequence.display();
        system.out.println();

        system.out.println("search查找一个数据："+mysequence.search("list"));
        system.out.println("contains查找一个数据："+mysequence.contains("list"));
        system.out.println();

        system.out.println("查找某一个位置对应的值："+mysequence.getpos(9));
        system.out.println();

        system.out.println("删除一个数据："+mysequence.remove(8));
        mysequence.display();
        system.out.println();

        system.out.println("得到顺序表的长度:"+mysequence.size());
    }
}

测试结果：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。