数据结构之顺序表（java版）

ゞ浴缸里的玫瑰 2022-07-15 02:20 129阅读 0赞

**要点：**  
顺序表：采用顺序存储结构的线性表  
顺序存储结构和链式存储结构不同，**强调的是存储元素在物理地址存储的上连续！可实现随机存取（只要知道第一个元素的内存地址，再通过简单的加减就能找到任意一个元素了）**  
![顺序表的存储结构][20161029193850335]  
顺序表耗时在对移动元素上，进行插入、删除时都需要移动元素

本人做顺序表的难点主要在于对顺序表进行插入时，需要多一个存储位，同时又要保存原来的数据 ，详情请看2的insert(int i, Object x)方法。

1、创建接口MyList  
主要实现了增、删、改、查

interface MyList{ 
        boolean isEmpty();
        int size();
        Object get(int i);
        void  set(int i, Object x);
        void insert(int i ,Object x);
        void remove(int i);              
        void clear();
        String toString();
    }

2、SeqList类 实现接口

public class SeqList implements MyList { 
        Object[] element;
        private int length = 0;
    
        public SeqList(Object[] o) {
            element = o;
            length = o.length;
        }
    
        @Override
        public boolean isEmpty() {
            if (length == 0) {
                return true;
            } else {
                return false;
            }
        }
    
        @Override
        public int size() {
            return this.length;
        }
    
        @Override
        public Object get(int i) {
            if (this.isEmpty()) {
                return null;
            }
            if (i < 0 || i > this.length) {
                System.out.println("查找位置不合法");
                return null;
            }
    
            return element[i - 1];
        }
    
        @Override
        public void set(int i, Object x) {
            if (i < 0 || i > this.length) {
                System.out.println("位置不合法");
                return ;
            }
    
            element[i]=x;
        }
    
        @Override
        public void insert(int i, Object x) {
            if (i < 0 || i > length) {
                System.out.println("插入位置不合法");
            }
            //用param暂时保存element的值
            Object[] param = this.element;
            // 由于插入 需要多一个存储位 同时长度加1
            element = new Object[++length];
            for (int j = 0; j < param.length; j++) {
                element[j] = param[j];
            }
            //插入处向后挪一位
            for (int j = element.length - 1; j > i; j--) {
                element[j] = element[j - 1];
            }
            element[i] = x;
    
        }
    
        @Override
        public void remove(int i) {
            if (i < 0 || i > length) {
                System.out.println("位置不合法");
            }
    
            for (int j = i+1; j <length; j++) {
               element[j-1]= element[j];
            }
            length--;
    
        }
    
    
    
        @Override
        public void clear() {
             element=null;
             length = 0;
        }
    
        @Override
        public String toString() {
            if (this.isEmpty()) {
                return null;
            }
            String str = "";
            for (int i = 0; i < length; i++) {
                str += element[i] + " ";
            }
            return str;
        }
    
        public static void main(String[] args) {
            SeqList sl = new SeqList(new String[] { "aa", "bb", "cc","hh" });
            System.out.println("raw :"+sl);
            sl.insert(1, "insert");
            System.out.println("insert :" + sl);
            sl.remove(2);
            System.out.println("remove :" + sl);
            System.out.println(sl.get(3));
            sl.set(2, "set");
            System.out.println("remove :" + sl);
        }
    }

[20161029193850335]: /images/20220715/c4dce54d929f41d39385bdf649d2b830.png