【线性表的顺序存储从结构】
指的是用一段连续的存储单元一次储存线性表的数据元素。
【线性表的顺序存储的结构代码 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.会造成存储空间“碎片”。