线性表之顺序存储结构（Java）

亦凉 2023-06-27 06:08 6阅读 0赞

**顺序存储**结构指的是用一段地址连续的存储单元一次存储线性表的数据元素，一般用一维数组来实现。

书中的线性表抽象数据类型定义如下（第45页）：

![format_png][]

![format_png 1][]

实现程序：

package SqList;
     
    /**
     *
     * 几个注意点：
     * 1.初始化时，应考虑数组大小为负的情况
     * 2.在各操作中，当涉及到位置i时，都应考虑i位置不合理的情况
     * 3.插入操作中，需考虑线性表已满的情况
     *   删除、获取操作中，需考虑线性表为空的情况
     * 4.插入删除操作中，均应考虑插入或删除位置为表尾情况（似乎没必要）
     * 5.插入删除操作中，别忘了最后要改变表长
     *
     * 几点困惑：
     * 1.插入删除位置为表尾时，没有判断语句，循环部分也不会执行，判断是否在表尾会不会显得画蛇添足？
     *   （《大话》一书中进行了该判断）
     * 2.RuntimeException类型在逻辑异常时使用，因为异常暂时还没学很好，用法是否正确？
     * 3.查找元素时，是否使用equals()方法比较合适？
     *
     * 拓展
     * 1.可进一步添加add方法，直接在表尾添加新的元素
     * 2.可添加整表打印输出的方法
     */
    public class SqList<E> {
        private Object[] data; //存储数据元素
        private int length; //线性表当前长度
        private int maxSize;//数组长度，即最大储存空间
         
        /**
         * 若初始化时未声明大小，则默认设置为20
         */
        public SqList(){
            //data=new Object[20];
            //length=0;
            /*直接利用this()更方便*/
            this(20);
        }
         
        /**
         * 初始化线性表
         */
        public SqList(int initialSize){
            if(initialSize<0) {
                throw new RuntimeException("数组大小为负，初始化失败！");               
            }
            else {
                this.maxSize =initialSize;
                this.data=new Object[initialSize];
                this.length=0;
                System.out.println("初始化成功！");
            }
        }
         
        /**
         * 判断线性表是否为空
         */
        public boolean IsEmpty(){
            if (this.length==0) {
                System.out.println("表为空");
                return true;
            }
            System.out.println("表不为空");
            return false;          
            //return this.length==0    也可以直接这样
        }
     
        /**
         * 清空线性表
         */
        public void ClearList() {
            this.length=0;
            System.out.println("线性表已清空！");
        }
         
        /**
         *获取第i个位置的元素值
         */
        public E GetElem(int i) {
            if(this.length==0) {
                throw new RuntimeException("空表，无法获取数据！");          
            }
            if(i<1||i>this.length) {
                throw new RuntimeException("数据位置错误！");
            }
            System.out.println("数据获取成功！");
            return (E) data[i-1];
        }
         
        /**
         * 查找元素,返回值为该元素位置，0代表查找失败
         */
        public int LocateElem(E e) {
            for(int i=1;i<=this.length;i++) {
                if(e==data[i-1]) { 
                    System.out.println("查找成功！");
                    return i;                            
                }
            }
            System.out.println("查找失败！");
            return 0;
        }
         
        /**
         * 在第i个位置插入新元素
         */
        public boolean ListInsert(int i,E e) {
            if(i<1||i>this.length+1) {
                throw new RuntimeException("插入位置错误:"+i);
            }
            if(this.length==this.maxSize) {
                /*1.无法继续插入*/
                //System.out.println("表已满，无法继续插入！");
                //return false;
                /*2.增加容量*/
                maxSize=maxSize+10;
                Object[] newdata=new Object[maxSize];
                for (int k=1;k<=this.length;k++)
                    newdata[k-1]=this.data[k-1];
                this.data=newdata;
            }
            if (i<=this.length) {  //插入数据不在表尾       **这个判断是否有必要呢？
                for(int j=this.length+1;j>i;j--)
                    this.data[j-1]=this.data[j-2];         
            }
            this.data[i-1]=e;  
            this.length++;  //表长改变勿忘
            System.out.println("插入成功！");
            return true;
        }
         
        /**
         * 删除第i个位置的元素，并用e返回其值
         */
        public E ListDelete(int i) {
            if(this.length==0) {
                throw new RuntimeException("空表，无法执行删除操作！");
            }          
            if(i<1||i>this.length) {
                throw new RuntimeException("删除位置错误！");
            }
            E e=(E) this.data[i-1];
            if(i<this.length) {   //删除数据不在表尾       **这个判断是否有必要呢？
                for(int j=i;j<this.length;j++) {
                    this.data[j-1]=this.data[j];
                }
            }
            this.length--;
            System.out.println("删除成功！");
            return e;
        }
         
        /**
         * 返回线性表的元素个数
         */
        public int ListLength() {
            return this.length;
        }  
    }

测试代码：

基本数据类型和引用类型各写了一个测试代码。

public class SqListTest {
        public static void main(String[] args) {
            //SqList<Integer> nums =new SqList<Integer>(-1);
            SqList<Integer> nums =new SqList<Integer>(5);
            nums.IsEmpty();
            //System.out.println("——————————插入几个位置错误的情况——————————");
            //nums.ListInsert(6, 6);
            //nums.ListInsert(3, 3);
            //nums.ListInsert(0, 0);
            System.out.println("——————————插入1到5,并读取内容——————————");
            for(int i=1;i<=5;i++)
                nums.ListInsert(i, i);
            nums.IsEmpty();
            int num;
            for(int i=1;i<=5;i++) {
                num=nums.GetElem(i);
                System.out.println("第"+i+"个位置的值为："+num);
            }
            System.out.println("——————————查找0、5、8是否在表中——————————");
            System.out.print("0的位置：");
            System.out.println(nums.LocateElem(0));    
            System.out.print("1的位置：");
            System.out.println(nums.LocateElem(1));
            System.out.print("5的位置：");
            System.out.println(nums.LocateElem(5));
            System.out.println("——————————删除2、5——————————");
            num=nums.ListDelete(2);
            System.out.println("已删除："+num);
            num=nums.ListDelete(4);
            System.out.println("已删除："+num);
            System.out.println("当前表长："+nums.ListLength());
            for(int i=1;i<=nums.ListLength();i++) {
                num=nums.GetElem(i);
                System.out.println("第"+i+"个位置的值为："+num);
            }
            nums.ClearList();
            nums.IsEmpty();    
        }
    }

public class SqListTest2 {
        public static void main(String[] args) {
            SqList<Student> students =new SqList<Student>();
            students .IsEmpty();
            System.out.println("——————————插入1到5,并读取内容——————————");
            Student[] stus= {new Student("小A",11),new Student("小B",12),new Student("小C",13),
                    new Student("小D",14),new Student("小E",151)};
            for(int i=1;i<=5;i++)
                students .ListInsert(i, stus[i-1]);
            students .IsEmpty();
            Student stu;
            for(int i=1;i<=5;i++) {
                stu=students .GetElem(i);
                System.out.println("第"+i+"个位置为："+stu.name);
            }
            System.out.println("——————————查找小A、小E、小龙是否在表中——————————");
            System.out.print("小A的位置：");
            stu=stus[0];
            System.out.println(students .LocateElem(stu));     
            System.out.print("小E的位置：");
            stu=stus[4];
            System.out.println(students .LocateElem(stu)); 
            System.out.print("小龙的位置：");
            stu=new Student("小龙",11);
            System.out.println(students .LocateElem(stu)); 
            System.out.println("——————————删除小E、小B——————————");
            stu=students .ListDelete(2);
            System.out.println("已删除："+stu.name);
            stu=students .ListDelete(4);
            System.out.println("已删除："+stu.name);
            System.out.println("当前表长："+students .ListLength());
            for(int i=1;i<=students .ListLength();i++) {
                stu=students .GetElem(i);
                System.out.println("第"+i+"个位置为："+stu.name);
            }
            students .ClearList();
            students .IsEmpty();       
        }
    }
     
    class Student{
        public Student(String name, int age) {
            this.name=name;
            this.age=age;
        }
        String name;
        int age;
    }

![format_png 2][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDUvMTQwNzMzMC0yMDE4MDUzMTExMTgyMjgxOC0xMTA0MTk3NTYwLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDUvMTQwNzMzMC0yMDE4MDUzMTExMTgzMTk4Ni0xNDcwNDM4Njc3LnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQwNzMzMC8yMDE4MDYvMTQwNzMzMC0yMDE4MDYwNDE2NTY1NzExOS0xODk2NjQ0OTQ2LnBuZw?x-oss-process=image/format,png