数据结构--JAVA2

线性表：

定义：

1、除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；

2、第一个数据元素没有前驱数据元素

3、最好一个数据元素没有后继数据元素

特点：可以在任意位置插入一个数据元素或删除一个数据元素。

实现：可以用顺序存储结构或链式存储结构实现

1、用顺序存储结构实现的线性表称为顺序表。

2、用链式存储结构实现的线性表称为链表。链表主要有单链表，循环单链表，循环双向链表。

 

线性表抽象数据类型

1、抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合，而类型是一组值的集合。

线性表的抽象数据类型主要包括两个方面：即数据集合和该数据集合上的操作集合

     1、数据集合：线性表的数据集合可以表示为序列，每个数据元素的数据类型可以是任意的类类型。

     2、操作集合：1、求当前数据元素个数 2、插入数据元素 3、删除数据元素   4、取数据元素 5、判断线性表是否为空isEmpty();

 

线性表抽象数据类型的JAVA接口定义如下：

public interface List｛

    public void insert(int i,Object obj) throws Exception;//插入

    public Object delete(int i) throws Exception ;//删除

    public Object getData(int i)throws Exception;//取数据元素

    public int size();//求元素个数

    public boolean isEmpty();//是否为空

｝

计算机的两种基本存储结构：

1、顺序存储结构

2、链式存储结构

实现顺序存储结构的方法是使用数组：

类包含成员变量和成员函数。

成员变量用来表示抽象数据类型中定义的数据集合

成员函数用来表示抽象数据类型中定义的操作集合

顺序表类实现接口List。顺序表类的public 成员函数主要是接口List中定义的成员函数。