第二章：线性表

（一）概述

               线性表：是一种最常用、最简单，也是最基本的数据结构。

               线性表是由n(n>= 0)个数据元素所构成的有限序列，且数据类型相同。

               线性表中数据元素之间具有一种线性的或“一对一”的逻辑关系。线性表是一种线性结构。

               线性表可以用顺序存储和链式存储两种存储结构来表示。

                       使用顺序存储的线性表称为顺序表。

                       使用链式存储的线性表称为链表。

                       链表的分类：单链表、双向链表、循环链表。

（二）线性表的抽象数据类型描述

线性表的结构简单，其长度可以动态的增长或收缩。可对表中任何数据元素进行访问和查找。

               求线性表中指定数据元素的前驱和后继：

                       方法一：将两个线性表合并成一个线性表。

                       方法二：将一个线性表拆分成两个或多个线性子表。

               线性表中的几种主要的基本操作：

clear() : 清空，将线性表置为空表。

isEmpty() : 判断表是否为空，若为空，返回true;反之返回false。

length() : 求表中数据元素的个数，并返回个数的值。

get(i) : 读取并返回表中第i个数据元素的值。其 i 的取值范围为0 <= i <= length() - 1【表的最大索引长度】

insert(i,x):在表的第 i 个元素之前插入一个值为x的数据元素。i 的取值范围为0 <= i <= length()【表的长度】。当i=0 时，在表头插入x,当i=length()时，在表尾插入x 。

remove(i): 删除并返回表的第i个数据元素。i 的取值范围为0<= i <= length() 1  。

indexOf(x) : 返回表中首次出现指定元素x的位序号【索引】，若表中没有该数据，就返回-1。

display(): 输出表中的各个元素的值。

               线性表的抽象数据Java接口描述：

public interface Ilist{
    public void clear() ;  //清空
    public boolean isEmpty();  //判断是否为空
    public int length();   // 表的长度
    public Object get(int i) ; //获取元素的值
    public void insert(int i , Object x) ; //在指定位置，插入指定元素
    public void remove(int i ); //删除指定元素
    public int indexOf(Object x) ;  //查找指定元素第一次出现的位置
    public void display() ;  //输出元素的值
}

ava实现以上接口的两种实现方法：

                       基于顺序存储的实现

                       基于链式存储的实现

（三）线性表的顺序存储

1.定义

顺序表，就是顺序存储的线性表。

       顺序存储是用一组地址连续的存储单元依次存放线性表中各个数据元素的存储结构。

               在逻辑上，数据ABCD是连续

               在物理上，地址也是连续的

可以使用数组来描述数据结构中的顺序存储结构。

2.地址公式

//第i的地址 = 第一个地址 + 第几个 *   存储单位

Loc(ai)   =  Loc(a0) +    i   *   c

Loc(a0）：a0的存储地址（此地址也称为线性表的基地址）

Loc(ai) ：表示第i个元素的地址

c : 表示一个数据元素的 存储单元

—— 即顺序表具有按数据元素的位序号随机存取的特点。

3.  顺序表特点

在线性表中逻辑上相邻的数据元素，在物理存储位置上也是相邻的。

存储密度高。但需要预先分配“足够”的存储空间。

存储密度 = 数据元素存储空间 / 数据元素实际占用空间

在顺序表中，存储密度为1。

便于随机存储。（数组中可以通过下标进行存储）

不便于插入和删除操作。两种操作都会引起大量的数据移动

4. 顺序存储结构类的描述

       高级程序设计语言在程序编译时会为数组类型的变量分配到一片连续的存储区域，数据元素的值就可以依次存储在这片存储区域中。因数组类型也具有随机存储的特点，所以可以用数组来描述数据结构中的顺序存储结构。数组元素的个数对应存储区域的大小

       顺序存储结构在线性表Javav接口中的实现类：

                考虑到线性表的长度是可变的，且定义了变量curLen来记录线性表的实际长度。

public class SqList implements IList{
    private Object[] listElem ;    //线性表的存储空间
    private int curLen ;          //线性表的当前长度
}

5. 顺序表类的描述

顺序表类的Java语言描述代码—实现线性表IList接口，重写接口中方法。

package data.updateORadd;
public class SqList implements IList {
    private Object[] listElem ;    //线性表的存储空间
    private int curLen ;          //线性表的当前长度
    //顺序表类的构造函数，构造一个存储空间容量为maxSize的线性表
    public SqList(int maxSize) {
        curLen = 0 ;  //置顺序表的当前长度为0
        listElem = new Object[maxSize];  //为顺序表分配maxSize个存储单元
    }
    //将一个一存在的线性表置为空表
    @Override
    public void clear() {
        curLen = 0 ;   //置顺序表的当前长度为0
    }
    //判断线性表的数据元素的个数是否为0 ，若为0则返回true,反之返回false
    @Override
    public boolean isEmpty() {
        return curLen == 0;
    }
    //求线性表中的数据元素的个数并返回值
    @Override
    public int length() {
        return curLen;
    }
    //读取到线性表中的第i个数据元素并有函数返回其值。其中i的取值范围为：0 <= i <= length()-1
    //若i 值不在此范围则抛出异常
    @Override
    public Object get(int i) throws Exception {
        if (i < 0 || i > curLen -1 ) {  //i 小于或者大于表长-1
            throw new Exception("第"+i+"个元素不存在");  //抛出异常
        }else {
            return listElem[i] ;  //返回顺序表中的第i个元素
        }
    }
    //在线性表的第i个数据元素之前插入一个值为x的数据元素
    @Override
    public void insert(int i, Object x) {
        //{...}
    }
    //删除并返回线性表中的第i个数据
    @Override
    public void remove(int i) {
        //{...}
    }
    //返回线性表在首次出现指定的数据元素的位序号，若线性表在不包括此元素，则返回-1
    @Override
    public int indexOf(Object x) {
        //{...}
        return 0;
    }
    //输出线性表中的数据元素
    @Override
    public void display() {
        for (int i = 0; i < curLen; i++) {
            //输出
            System.out.println(listElem[i]+" ");
        }
    }
}

注：代码中的“ //{...} ” 表示实现方法，会在后面具体操作中实现。