数据结构实训（Java实验一 线性表-顺序表的基本操作）_顺序表实验报告java

问题描述：

实验目的：

1.掌握线性表的顺序存储结构

2.验证顺序表及其基本操作的实现

3.理解算法与程序的关系，能够将顺序表算法转换为对应的程序

实验内容：

1.创建顺序表类及基本运算方法

2.建立含有若干个元素的顺序表

3.对已经建立的顺序表实现插入、删除、查找等基本操作

4.对于一个整数顺序表，设计一个尽可能高效的算法将所有负整数元素移到其他元素的前面，并给出其时间复杂度和空间复杂度。例如：L=（1，2，-1，-2，3，-3，4）移动后L=(-1，-2，-3，2，3，1，4)（选做）

实验提示：

定义顺序表类——顺序表类SqList，在SqList基础上实现基于顺序表的的插入、删除、查找等基本操作，为了便于查看结果，设计一个输出函数依次输出顺序表的元素。要求学生：

1. 创建顺序表L，存放1，2，-1，-2，3，-3，4实现输出顺序表L、求顺序表L的长度，输出顺序表的第3个元素，输出元素3的位置，在第4个元素位置上插入7元素，删除顺序表第3个元素。
2. 重新给定测试数据，验证抛出异常机制。

实验程序：

在编程环境下，新建工程，并新建相应文件，文件包括顺序表类：成员变量、基本运算方法，、建立顺序表、遍历顺序表、按值查找、插入、删除操作等类方法的定义。范例程序可参考教材P42~P47。

解答：

1.建立顺序表泛型类（用来包含基本运算方法）

假设线性表的元素类型为E，设计顺序表泛型类为SqListClass<E>,主要包含date动态泛型数组，size成员变量表示实际的元素个数。

E: 泛型数据类型，用于设置 objectName 的数据类型，只能为引用数据类型，objectName: 对象名。

代码如下：

public static class SqListClass <E>             //顺序表泛型类
    {
        final int initcapacity = 10;                //顺序表的初始容量（常量）
        public E[] date;                            //存放顺序表中的元素
        public int size;                            //存放顺序表的长度
        private int capacity;                       //存放顺序表的容量
        public SqListClass()                        //构造方法，实现date和length的初始化
        {   date = (E[])new Object[initcapacity];   //强制转化为E类型数组
            capacity = initcapacity;
            size = 0;
        }
        //线性表的基本运算方法
    }

线性表一旦采用顺序表存储，就可以用Java语言实现线性表的各种基本运算。在动态分配顺序表的空间时将初始容量设置为initcapacity,添加或者插入元素可能需要扩大容量，删除元素可能需要减少容量。为此设计以下私有方法将其容量更新为newcapacity：

private void updatecapacity(int newcapacity)            //改变顺序表的容量为newcapacity
        {   E[] newdate = (E[])new Object[newcapacity];
            for(int i=0;i<size;i++)                             //复制原来的元素
                newdate[i] = date[i];
            capacity = newcapacity;                             //设置新的容量
            date = newdate;                                     //仍由date标识数组
        }

解析：该算法是放在顺序表泛型类为SqListClass<E>中，该算法首先新建一个容量为newcapacity的动态数组newdate，再将date中所有的元素复制到newdate中，所有元素的序号和长度不变，最后将指向newdate。

2.顺序表的基本运算方法

1.整体建立顺序表

public void Creatlist(E[] a)                        //由a整体建立顺序表
        {
            size = 0;
            for(int i=0;i<a.length;i++){
                if(size == capacity)                        //出现上溢时
                    updatecapacity(2*size);     //扩大容量
                date[size] = a[i];
                size++;                                     //添加的元素个数增加 1
            }
        }

解析：该算法是由含若干个元素的数组a的全部元素整体创建顺序表，即依次将a中的元素添加到date数组的末尾，当出现上溢时按照实际元素个数size的两倍扩大容量。

本算法的时间复杂度为O(n)，其中 n 表示顺序表中元素的个数。

2.扩容

private void updatecapacity(int newcapacity)            //改变顺序表的容量为newcapacity
        {   E[] newdate = (E[])new Object[newcapacity];
            for(int i=0;i<size;i++)                             //复制原来的元素
                newdate[i] = date[i];
            capacity = newcapacity;                             //设置新的容量
            date = newdate;                                     //仍由date标识数组
        }

3.添加字符

public void ADD(E e){//添加字符
            if(size == capacity)
                updatecapacity(2*size);
            date[size] = e;
            size++;
        }

4.求顺序表大小

        public int size(){
            return size;
        }//求顺序表大小

5.设置顺序表的长度

        public void setSize(int nlen) {
            if(nlen<0 || nlen<size)
                throw new IllegalArgumentException("设置:位置n不在有效范围内");
            size = nlen;
        }//设置长度

6.查找某一位置的元素

        public E GetElem(int i){//查找某一位置的元素
            if(i<0 || i>size-1)
                throw new IllegalArgumentException("查找:位置i不在有效范围内");
            return (E)date[i];
        }

7.将i位置的元素设置为e

        public void SetElem(int i,E e){
            if(i<0 || i>size-1)
                throw new IllegalArgumentException("设置:位置i不在有效范围内");
            date[i] = e;
        }//将i位置的元素设置为e

8.寻找元素e的位置

        public int GetNo(E e){
            int i=0;
            while(i<size && !date[i].equals(e))
                i++;
            if(i>=size)
                return -1;
            else
                return i;
        }//寻找元素e的位置

9.交换i和j位置的元素

        public void swap(int i,int j){
            E tmp = date[i];
            date[i] = date[j];
            date[j] = tmp;
        }//交换i和j位置的元素

10.插入元素，在i位置插入元素e

        public void Insert(int i,E e){//插入元素，在i位置插入元素e
            if(i<0 ||i>size)
                throw new IllegalArgumentException("插入:位置i不在有效范围内");
            if(size==capacity)
                updatecapacity(2*size);
            for(int j=size;j>i;j--)
                date[j] = date[j-1];
            date[i] = e;
            size++;
        }

11.删除 i 位置的元素

        public void delete(int i){//删除i位置的元素
            if(i<0 || i>size-1)
                throw new IllegalArgumentException("删除:位置i不在有效范围内");
            for(int j=i;j<size-1;j++)
                date[j] = date[j+1];
            size--;
            if(capacity>initcapacity && size==capacity/4)
                updatecapacity(capacity/2);
        }

12.转换为字符形式输出

        public String toString(){
            String ans = "";
            for(int i=0;i<size;i++)
                ans+=date[i].toString()+" ";
            return ans;
        }
    }

13.将顺序表中的负数放在前面

    //将负数放在前面
    public static void Move(SqListClass<Integer> L1){
        int i=-1,j=0;
        while(j<L1.size())
        {
            if(L1.GetElem(j)<0)
            {
                i++;
                if(i!=j)
                    L1.swap(i,j);
            }
            j++;
        }
    }

3.主函数测试代码：

    public static void main(String[] args) {
        System.out.println("————————————测试1——————————————");
        Integer [] a = {1,2,-1,-2,3,-3,4,5};
        SqListClass<Integer> L1 = new SqListClass<Integer>();
        L1.Creatlist(a);
        System.out.println("L1："+L1.toString());
        System.out.println("将负数移动到其他元素前面：");
        Move(L1);
        System.out.println("L1："+L1.toString());
        System.out.println("L1长度="+L1.size());
        L1.ADD(10);
        System.out.println("L1："+L1.toString());
//        System.out.println("求每个序号的元素值:");
//        for (int i=0;i<L1.size();i++)
//            System.out.println(" 序号"+i+"的元素值:"+L1.GetElem(i));
        int i=4;
        Integer x=7;
        System.out.println("在序号"+i+"位置插入"+x);
        L1.SetElem(i,x);
        System.out.println("L1："+L1.toString());
        i=3;
        System.out.println("顺序表序号为"+i+"的元素的值："+L1.GetElem(i));
        System.out.println("删除序号"+i+"的元素");
        L1.delete(i);
        System.out.println("L1："+L1.toString());
        i=2;x=-5;
        System.out.println("设置序号"+i+"的元素值为"+x);
        L1.SetElem(i,x);
        System.out.println("L1："+L1.toString());
        x=3;
        System.out.println("值为"+x+"的元素序号为"+L1.GetNo(x));
        System.out.println("-----------测试2：验证抛异常机制-------------");
        i=12;
        System.out.println("顺序表序号为"+i+"元素的值为"+L1.GetElem(i));
    }
}