JAVA数据结构——顺序表

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

1. 在线性表中逻辑上相邻的元素在物理存储位置上也是相邻的。
2. 存储密度高:存储密度=数据元素原本需要的存储空间/实际占用空间
3. 便于随机存取
4. 不便于插入和删除操作,插入删除操作会引起大量数据元素的移动

 

二、利用JAVA实现顺序表:
1. 接口:
package com.usts.edu.list;
 
/**
 * Created by Guanzhong Hu
 * Date :2019/12/27
 * Description : 线性表
 * Version :1.0
 */
public interface Ilist {
    /**
     * 顺序表的特点
     * 1. 在线性表中逻辑上相邻的元素在物理存储位置上也是相邻的。
     * 2. 存储密度高:存储密度=数据元素原本需要的存储空间/实际占用空间
     * 3. 便于随机存取
     * 4。不便于插入和删除操作,插入删除操作会引起大量数据元素的移动
     */
 
//    将已存在的线性表置空
    public void clear();
 
//    判断是否为空
    public boolean isEmpty();
 
//    求线性表中数据元素个数并返回其值
    public int length();
 
//    读取第i个元素的值 区间:[0,length()-1]
    public Object get(int i) throws Exception;
 
//    插入元素,i表示插入的地址取值 区间:[0,length()-1],当为length()-1时,表示在表尾插入x
    public void insert(int i,Object x) throws Exception;
 
//    删除位于第i个的元素
    public void remove(int i) throws Exception;
 
//    返回线性表中元素第一次出现的index
    public int indexOf(Object x) throws Exception;
 
//    输出线性表中各个数据元素的值
    public void display();
 
 
}
2. 实现类:
package com.usts.edu.list;
 
/**
 * Created by Guanzhong Hu
 * Date :2019/12/27
 * Description : 顺序表实现
 * Version :1.0
 */
public class SqList implements Ilist {
 
    private Object[] listElem;
 
    private int curlen;
 
    public SqList( int maxLen) {
       listElem = new Object[maxLen];// 初始化最大空间
        this.curlen = 0; // 初始化0
    }
 
    @Override
    public void clear() {
        curlen = 0;
    }
 
    @Override
    public boolean isEmpty() {
        return curlen == 0;
    }
 
    @Override
    public int length() {
        return curlen;
    }
 
    @Override
    public Object get(int i) throws Exception {
 
        if(i<0 ||i>curlen-1) //如果越界或者小于0则不存在
            throw new Exception("第"+i+"个元素不存在");
        return listElem[i];
    }
 
    @Override
    public void insert(int i, Object x) throws Exception {
        if (curlen == listElem.length) throw new Exception("线性表已满");
        if(i<0 ||i>listElem.length) throw new Exception("插入位置不合法");
        for (int j = curlen; j > i; j--) {
            listElem[j] = listElem[j-1];
        }
        listElem[i] = x; // 位置空出来则存储
        curlen++;
    }
 
    @Override
    public void remove(int i) throws Exception{
        if(i<0 ||i>curlen-1) throw new Exception("删除位置不合法");
        for (int j = i; j<curlen-1;j++){
            listElem[j] = listElem[j+1];
        }
        listElem[length()-1] = null; // 将末尾置空
        curlen --;
    }
 
    @Override
    public int indexOf(Object x) {
        int index = 0;
        while (index < curlen && !listElem[index].equals(x))// 依次遍历,如果比较相等则判断为false跳出循环
            index++;
        if (index<curlen) return index;
 
        return -1; // -1表示不存在
    }
 
    @Override
    public void display() {
        if (curlen==0) System.out.println("线性表为空!");
       for (int i = 0; i < curlen  ; i++) {
            System.out.print("index:"+i+"  value:"+listElem[i]+"\t");
        }
    }
}
3. 测试类:
package com.usts.edu.list;
 
/**
 * Created by Guanzhong Hu
 * Date :2019/12/27
 * Description : 线性表测试
 * Version :1.0
 */
public class ExampleListTest {
 
    public static void main(String[] args) throws Exception{
        SqList sqList = new SqList(10);
        sqList.insert(0,0);
        sqList.insert(1,1);
        sqList.insert(2,2);
        sqList.insert(3,3);
        sqList.insert(4,4);
        System.out.println(sqList.length());
//        sqList.display();
//        sqList.remove(2);
        sqList.insert(2,7);
//        System.out.println(sqList.length());
 
//        sqList.display();
        sqList.remove(4);
        sqList.display();
    }
}

本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽,造成漏登,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。

  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息
  • 项目经理 点击这里给我发消息