04
27

发表于 • • 被 636 人看爆

顺序表的概念：

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中

用Java实现顺序表：

  1. 接口list的代码
package list;

/**
 * @author pms
 * @version 1.0
 * @ClassName IList
 * @Description 顺序表的接口
 * @createTime 2021/4/27 : 20:53
 */
public interface IList {
    /**
     *
     * @Desc 置空操作
     * @Author pms
     * @param
     * @Return void
     * @Date 2021/4/27
     */
    public void clear();
    
    /**
     *
     * @Desc 判空操作
     * @Author pms
     * @param
     * @Return boolean 如果为空则返回true，不为空返回false
     * @Date 2021/4/27
     */
    public boolean isEmpty();

    /**
     *
     * @Desc 取表长度
     * @Author pms
     * @param
     * @Return int
     * @Date 2021/4/27
     */
    public int length();

    /**
     *
     * @Desc 取表的元素
     * @Author pms
     * @param i	顺序表的下标
     * @Return java.lang.Object
     * @Date 2021/4/27
     */
    public Object get(int i) throws Exception;

    /**
     *
     * @Desc 插入操作
     * @Author pms
     * @param i	要插入顺序表的位置的下标
     * @param x	要插入顺序表的元素
     * @Return void
     * @Date 2021/4/27
     */
    public void insert(int i, Object x) throws Exception;

    /**
     *
     * @Desc 删除操作
     * @Author pms
     * @param i	要删除的元素的下标
     * @Return void
     * @Date 2021/4/27
     */
    public void remove(int i) throws Exception;

    /**
     *
     * @Desc 查找操作
     * @Author pms
     * @param x	要查找的元素
     * @Return int 返回的下标,没有查到就返回-1
     * @Date 2021/4/27
     */
    public int Indexof(Object x);

    /**
     *
     * @Desc 显示（打印顺序表的所有元素）
     * @Author pms
     * @param
     * @Return void
     * @Date 2021/4/27
     */
    public void display();
}

2.顺序表类SqList的代码

package list;

/**
 * @author pms
 * @version 1.0
 * @ClassName SqList
 * @Description TODO 顺序表
 * @createTime 2021/4/27 : 22:04
 */
public class SqList implements IList{
    //线性表存储空间
    public Object[] listElem;
    //线性表当前长度
    private int curlen;

    //顺序表构造函数，构造一个长度为maxSize的线性表
    public SqList(int maxSize){
        curlen = 0;
        listElem = new Object[maxSize];
    }

    //置空操作
    @Override
    public void clear() {
        curlen = 0;
    }

    //判断当前长度是否为0,为0即为空表
    @Override
    public boolean isEmpty() {
        return curlen == 0;
    }

    //取表长度，返回curlen当前长度即可
    @Override
    public int length() {
        return curlen;
    }

    //取表元素
    @Override
    public Object get(int i) throws Exception {
        //判断i是否合法
        if(i < 0 || i > curlen -1){
            throw new Exception("第" + i + "个元素不存在");
        }
        return listElem[i];
    }

    //插入操作
    @Override
    public void insert(int i, Object x) throws Exception {
        //判断顺序表是否已经满了
        if(curlen == listElem.length){
            throw new Exception("顺序表已经满了");
        }
        //判断i是否合法
        if(i < 0 || i > curlen){
            throw new Exception("插入位置不合法");
        }
        //从尾部往前扫
        for(int j = curlen; j > i; j++){
            listElem[j] = listElem[j - 1];
        }
        listElem[i] = x;
        //插入成功后，表长度+1
        curlen ++;
    }

    //删除操作
    @Override
    public void remove(int i) throws Exception {
        //判断i是否合法
        if(i < 0 || i > curlen -1){
            throw new Exception("删除位置不合法");
        }
        //下标移动要删除的i处
        for(int j = i; j < curlen - 1; j++){
            listElem[j] = listElem[j++];
        }
        //删除成功后，表长度-1
        curlen --;
    }

    //查找操作,找到就返回下标，否则返回-1
    @Override
    public int Indexof(Object x) {
        //遍历查找
        for(int j = 0; j < curlen; j++){
            //找到就返回下标
            if(listElem[j].equals(x)){
                return j;
            }
        }
        //没有找到返回-1
        return -1;
    }

    //显示操作
    @Override
    public void display() {
        //遍历线性表
        for(int i = 0; i < curlen; i++){
            System.out.print(listElem[i]+", ");
        }
    }
}
分享到：