2.2_线性表的顺序存储结构

2.2_线性表的顺序存储结构_参考集合ArrayList

【线性表的顺序存储从结构】

指的是用一段连续的存储单元一次储存线性表的数据元素。

【线性表的顺序存储的结构代码 C语言版】

#define MAXSIZE 20               /*存储空间初始分配量*/
typedef int  ElemType;           /*ElemType类型依实际情况而定*/
typedef struct
{
    Element data[MAXSIZE];       /*数组存储数据元素，最大值为MAXSIZE*/
    int length;                  /*线性表当前长度为length*/
}SqlList;

【线性表的顺序存储结构需要的三个属性】

1.存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

2.线性表的最大存储容量：数组长度MaxSize

3.线性表的当前长度：length

【数组长度和线性表长度的区别】

数组的长度：存放线性表的存储空间的长度，存储分配后这个量一般是不变的。

线性表的长度：线性表中的数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。

当然，任意时候线性表的长度是小于数组的长度的。

【地址的计算方法】

存储器中的每个存储单元都有自己的编号，这个编号称为地址。

由于每个数据元素，不管是什么类型，都需要占用一定的存储空间的，假设占用的是c个存储单元，那么线性表中第i+1个数据元US的存储位置和第i个数据元素的存储位置满足下列关系：（LOC表示获得存储位置的函数）

对于第i个数据元素ai的存储位置可以由a1推算出来：

【java描述顺序线性表】

【整体工程截图】

【线性顺序表抽象数据类型 JAVA接口描述】

package com.Higgin.List;

public interface MyList<E> {
    int size();                       //返回线性表中的元素数量
    boolean isEmpty();              //判断线性表是否为空
    void clear();                      //将线性表清空
    E get(int index);                //返回线性表的第index个元素
    int indexOf(Object o);             //在线性表中查找与给定元素o相等的元素，查找成功，则返回对应的序号；否则，返回-1表示失败
    boolean add(E e);               //向线性表的尾部添加指定的元素e
    void add(int index,E element);  //向线性表的指定位置第index处添加指定的元素
    E remove(int index);            //移除线性表的第index处的元素，返回删除的元素的值
}

【具体的实现类】

package com.Higgin.List;

public class MyArrayList<E> implements MyList{
    private int size;
    private Object[] elementData;
    
    /**
     * 构造一个容量为initialCapacity的空顺序线性表
     */
    public MyArrayList(int initialCapacity){
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
        this.elementData=new Object[initialCapacity];
    }
    
    /**
     * 返回线性表中的元素数量
     */
    public int size() {
        return size;
    }
    
    /**
     * 判断线性表是否为空
     */
    public boolean isEmpty() {
        return size==0;
    }
    
    /**
     * 将线性表清空
     */
    public void clear() {
        for(int i=0;i<size;i++){ //所有元素置为null
            elementData[i]=null;
        }
        size=0; //线性表长度置为0
    }
    
    /**
     * 返回线性表的第index个元素
     */
    public Object get(int index) {
        if(index<0||index>=this.size){
             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+this.size);
        }
        return elementData[index];
    }
    /**
     * 在线性表中查找与给定元素o相等的元素，查找成功，则返回对应的序号；否则，返回-1表示失败
     */
    public int indexOf(Object o) {
        if(o==null){
            for(int i=0;i<size;i++){
                if(elementData[i]==null){
                    return i;
                }
            }
        }else{
            for(int i=0;i<size;i++){
                if(o.equals(elementData[i])){
                    return i;
                }
            }
        }
        return -1;
    }
    /**
     * 向线性表的尾部添加指定的元素e
     */
    public boolean add(Object e) {
        add(size,e);
        return true;
    }
    /**
     * 向线性表的指定位置第index处添加指定的元素
     */
    public void add(int index, Object element) {
        if (index > size || index < 0) //当index不在范围内
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        if(index<size){ //若插入的位置不在表尾
            for(int i=size;i>=index;i--){
                elementData[i+1]=elementData[i];
            }
        }
        elementData[index]=element;
        size++;
    }
    /**
     * 移除线性表的第index处的元素，返回删除的元素
     */
    public E remove(int index) {
        if(size==0){                  //如果此时线性表为空
             throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        }
        if (index >= size||index<0)   //如果移除的位置超出范围
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
        E oldValue=(E) elementData[index]; //存储被删除的值
        if(index<size-1){              //如果删除的位置不是最后的位置
            for(int i=index;i<size;i++){
                elementData[i]=elementData[i+1];
            }
        }
        elementData[size] = null;  //表尾元素置为null
        size--;  
        return oldValue;
    }
}

【思路：关于插入】

1.如果插入的位置不合理，抛出异常。

2.如果线性表长度大于等于数组的长度，抛出异常或动态增加容量。

3.从最后一个元素开始向前遍历到底index个位置，分别将他们向后移动1个位置（包括index位置）。

4.将要插入的元素填入位置index处。

5.表长size要加1。

【思路：关于删除】

1.如果表长度为0或删除的位置不合理，抛出异常。

2.取出要删除的元素。

3.从删除的元素的位置index处开始遍历到最后一个元素，分别将他们向前移动一个位置。

4.原先最后一个元素的位置要置为null。

5.表长size要减1。

【分析：线性表顺序存储结构的优缺点】

【优点】

1.无需为表中的元素之间的逻辑关系增加额外的存储空间（相对于链表）。

2.可以快速的取出表中任意位置的元素。

【缺点】

1.插入和删除操纵需要移动大量的元素，时间复杂度O(n)

2.当线性表长度变化较大时，难以确定存储空间的容量。

3.会造成存储空间“碎片”。