线性表的顺序存储实现(Java版)

清疚 2022-12-18 14:54 171阅读 0赞

顺序表:用一组地址连续的存储单元依次存储各个元素，使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表

package algorithm.datastructure.seqlist;
    
    
    
    /*顺序表 * * 用一组地址连续的存储单元依次存储各个元素，使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表 * */
    public class SeqList { 
    
        private int length;//顺序表长度
        private int[] list;//数组，连续的存储空间
    
        //初始化，构造一个空的线性表
        public SeqList(int listLength) { 
            list = new int[listLength];
        }
        //销毁表
        public void destroyList() { 
            list = null;
            this.length = 0;
        }
        //将线性表置为空表
        public void clearList() { 
            for (int i = 0; i < getLength(); i++) { 
                list[i] = 0;
            }
        }
    
        //判断线性表是否未空表
        public Boolean isEmpty() { 
            return getLength() == 0;
        }
    
        //获取线性表元素个数
        public int getLength() { 
            return length;
        }
    
        //根据下标获取线性表元素
        public int getElem(int i) { 
            if (i < 0 || i >= getLength()) { 
                try { 
                    throw new Exception("线性表下标越界");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
            return list[i];
        }
    
    
        //返回某元素(第一个)的前驱
        public Integer priorElem(int element) { 
            for (int i = 0; i < getLength(); i++) { 
                if (element == list[i]) { 
                    if (i == 0) { 
                        return null;
                    } else { 
                        return list[i - 1];
                    }
                }
            }
            return null;
        }
    
        //获取某元素(第一个)的后继
        public Integer nextElem(int element) { 
            for (int i = 0; i < getLength(); i++) { 
                if (element == list[i]) { 
                    if (i == getLength() - 1) { 
                        return null;
                    } else { 
                        return list[i + 1];
                    }
                }
            }
            return null;
        }
    
        //扩容，这里设置容量变为原来两倍
        public void ensureCapacity(int capacity) { 
            if (capacity >= list.length) { //扩容
                int tempList[] = new int[list.length * 2];
                for (int i = 0; i < list.length; i++) { 
                    tempList[i] = list[i];
                }
                list = tempList;
            }
        }
    
        //在指定位置插入元素
        public Boolean insertElement(int index, int element) { 
            if (index < 0 || index >= list.length) { 
                try { 
                    throw new Exception("下标错误");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
            if (index == getLength()) { 
                return insertTailElement(element);
            }
            for (int i = 0; i < getLength(); i++) { 
                if (i == index) { 
                    ensureCapacity(getLength() + 1);
                    //index位置后面的元素后移
                    for (int j = getLength() - 1; j >= index; j--) { 
                        list[j + 1] = list[j];
                    }
                    list[index] = element;
                    length++;
                }
            }
            return true;
        }
    
        //尾部插入元素
        public Boolean insertTailElement(int element) { 
            ensureCapacity(length + 1);
            list[++length] = element;
            return true;
        }
        //删除尾部元素
        public int deleteTailElement() { 
            if (getLength() == 0) { 
                try { 
                    throw new Exception("下标错误");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
            int tailElement = list[getLength() - 1];
            list[getLength() - 1] = 0;
            length--;
            return tailElement;
        }
    
        //删除元素
        public int deleteElement(int index) { 
            if (index < 0 || index >= list.length) { 
                try { 
                    throw new Exception("下标错误");
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
            if (index == getLength()) { 
                return deleteTailElement();
            }
            for (int i = 0; i < getLength(); i++) { 
                if (i == index) { 
                    int tailElement = list[index];
                    //index位置后面的元素前移
                    for (int j = index; j < getLength() - 1; j++) { 
                        list[j] = list[j + 1];
                    }
                    list[getLength() - 1] = 0;
                    length--;
                    return tailElement;
                }
            }
            return 0;
        }
    
        //遍历顺序表
        public void traverseList() { 
            for (int i = 0; i < getLength(); i++) { 
                System.out.println(list[i]);
            }
        }
    
    
    
        public static void main(String[] args) { 
            //测试
            SeqList seqList = new SeqList(2);
            System.out.println(seqList.insertTailElement(1));
            System.out.println(seqList.insertTailElement(2));
            System.out.println(seqList.insertTailElement(3));
            System.out.println(seqList.insertTailElement(4));
            System.out.println(seqList.getElem(0));
            System.out.println(seqList.getElem(1));
            System.out.println(seqList.getElem(2));
            System.out.println(seqList.getElem(3));
    
            System.out.println(seqList.insertElement(0, 4));
            System.out.println(seqList.getElem(0));
            System.out.println(seqList.getElem(1));
            System.out.println(seqList.getElem(2));
            System.out.println(seqList.getElem(3));
            System.out.println(seqList.getElem(4));
            System.out.println(seqList.priorElem(3));
            System.out.println(seqList.priorElem(4));
            System.out.println(seqList.nextElem(4));
            System.out.println(seqList.nextElem(3));
    // System.out.println(seqList.deleteTailElement());
    // System.out.println(seqList.deleteTailElement());
    // System.out.println(seqList.deleteTailElement());
    // System.out.println(seqList.deleteTailElement());
    // System.out.println(seqList.deleteTailElement());
    // System.out.println(seqList.deleteTailElement());
            System.out.println(seqList.deleteElement(0));
            System.out.println(seqList.deleteElement(1));
            seqList.traverseList();
        }
    }

以上就是用Java简单实现的顺序表，在Java中，如果要实现功能更复杂，性能更高的顺序表，可参考ArrayList源码。