线性表顺序存储结构

线性表的顺序存储是用一组地址连续的存储单元依次存储线性表的数据元素。假设线性表的每个数据元素需占用K个存储单元，并以元素所占的第一个存储单元的地址作为数据元素的存储地址。则线性表中序号为i的数据元素的存储地址LOC(a i )与序号为i+1 的数据元素的存储地址LOC(a i+1 )之间的关系为LOC(a i+1 ) = LOC(a i ) + K通常来说，线性表的i号元素a i 的存储地址为LOC(a i ) = LOC(a 0 ) + i×K 其中LOC(a 0 )为 0 号元素a 0 的存储地址，通常称为线性表的起始地址。

线性表的这种机内表示称作线性表的顺序存储。它的特点是，以数据元素在机内存储地址相邻来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储地址都和线性表的起始地址相差一个与数据元素在线性表中的序号成正比的常数。由此，只要确定了线性表的起始地址，线性表中的任何一个数据元素都可以随机存取，因此线性表的顺序存储结构是一种随机的存储结构。

　　由于高级语言中的数组具也有随机存储的特性，因此在抽象数据类型的实现中都是使用数组来描述数据结构的顺序存储结构。我们看到线性表中的数据元素在依次存放到数组中的时候，线性表中序号为 i 的数据元素对应的数组下标也为 i，即数据元素在线性表中的序号与数据元素在数组中的下标相同。 在这里需要注意的是，如果线性表中的数据元素是对象时，数组存放的是对象的引用，即线性表中所有数据元素的对象引用是存放在一组连续的地址空间中。如图 3-2 所示

　　在数组中添加数据元素，通常是在数组中下标为 i (0 ≤ i ≤ n)的位置添加数据元素，而将原来下标从 i 开始的数组中所有后续元素依次后移。整个操作过程可以通过图 3-3 说明。

使用 Java 语言实现整个操作过程的关键语句是 for (int j=n; j>i; j–)a[j] = a[j-1];a[i] = e;

　　与在数组中添加数据元素相对的是在数组中删除数据元素，与添加类似，删除操作也通常是删除数组中下标为 i (0 ≤ i < n)的元素，然后将数组中下标从 i+1 开始的所有后续元素依次前移。删除操作过程也可以通过图 3-4 说明

使用 Java 语言实现整个操作过程的关键语句是for (int j=i; j<n-1; j++)a[j] = a[j+1];

 List接口：
**
* 线性表
*/public interface List {
/**
*线性表的长度
*/public int size();
/**
* 判断线性表是否为空
*/public boolean isEmpty();
/**
* 判断线性表中是否包含某个元素
*/public boolean contains(Object element);
/**
* 判断线性表中是否包含某个元素
*/public int indexOf(Object element);
/**
*在表中插入元素
*/public void add(Object element);

/**
*在索引处插入元素
*/public void insert(int index,Object element) throws IndexOutOfBoundsException;
/**
*删除线性表中第一个与 e 相同的元素
*/public boolean remove(Object element);
/**
*在表中移除序号为i的某个元素
*/public Object remove(int i)throws IndexOutOfBoundsException;
/**
*返回线性表中序号为i的元素
*/public Object get(int i)throws IndexOutOfBoundsException;
} 
 
 顺序存储结构实现线性表
public class ListArray implements List {
private final int LEN = 8; //数组的默认大小
private int size; //线性表中数据元素的个数
private Object[] elements; //数据元素数组
public ListArray() {
size = 0;
elements = new Object[LEN];
}
@ Override 
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(Object element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element))
return true;
}
return false;
}
@Override
public int indexOf(Object element) {
for (int i = 0; i < size; i++) {
if (elements[i].equals(element))
return i;
}
return -1;
}
@Override
public void add(Object element) {
if (size >= elements.length)
expandSpace();
elements[++size]=element;
}
@Override
public void insert(int index, Object element) throws IndexOutOfBoundsException {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException();
if (size >= elements.length)
expandSpace();
for (int j = size; j > index; j--)
elements[j] = elements[j - 1];
elements[index] = element;
size++;
return;
}
private void expandSpace() {
Object[] a = new Object[elements.length * 2];
for (int i = 0; i < elements.length; i++) {
a[i] = elements[i];
elements = a;
}
}
@Override
public boolean remove(Object element) {
int i = indexOf(element);
if (i<0)return false;
remove(i);
return true;
}
@Override
public Object remove(int index) throws IndexOutOfBoundsException {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException();
Object obj=elements[index];
for (int j =index; j<size-1; j++)
elements[j] = elements[j+1];
elements[--size] = null;
return obj;

}
@Override
public Object get(int index) throws IndexOutOfBoundsException {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException();
return elements[index];
}
}  

线性表链式存储结构

链表 是一系列的存储数据元素的单元通过指针串接起来形成的，因此每个单元至少有两个域，一个域用于数据元素的存储，另一个域是指向其他单元的指针。这里具有一个数据域和多个指针域的存储单元通常称为 结点（node）。

　　在 Java 中没有显式的指针类型，然而实际上对象的访问就是使用指针来实现的，即在Java 中是使用对象的引用来替代指针的。因此在使用 Java 实现该结点结构时，一个结点本身就是一个对象。结点的数据域 data 可以使用一个 Object 类型的对象来实现，用于存储任何类型的数据元素，并通过对象的引用指向该元素；而指针域 next 可以通过节点对象的引用来实现。　　由于数据域存储的也是对象引用，因此数据实际上和图 3-2 中一样，是通过指向数据的物理存储地址来完成存储的，但是在后面叙述的方便，我们在图示中都将数据元素直接画到了数据域中，请读者注意实际的状态与之是有区别的。

上面的单链表结点结构是结点的一种最简单的形式，除此之外还有其他不同的结点结构，但是这些结点结构都有一个数据域，并均能完成数据元素的存取。为此在使用 Java 定义单链表结点结构之前先给出一个结点接口，在接口中定义了所有结点均支持的操作，即对结点中存储数据的存取。

 节点接口
public interface Node {
//获取结点数据域
public Object  getData ();
//设置结点数据域
public void setData(Object obj);
}

单链表节点
public class SLNode implements Node {
private Object element;
private SLNode next;
public SLNode() {
this(null,null);
}
public SLNode(Object ele, SLNode next){
this.element = ele;
this.next = next;
}
public SLNode getNext(){
return next;
}
public void setNext(SLNode next){
this.next = next;
}
/**************** Methods of Node Interface **************/public Object getData() {
return element;
}
public void setData(Object obj) {
element = obj;
}
}  

单链表实现

 public class ListSLinked implements List{
private SLNode head; //单链表首结点引用
private int size; //线性表中数据元素的个数
public ListSLinked () {
head = new SLNode();
size = 0;
}
//辅助方法：获取数据元素 e 所在结点的前驱结点
private SLNode getPreNode(Object e){
SLNode p = head;
while (p.getNext()!=null)
if (p.getNext().getData().equals(e)) return p;
else p = p.getNext();
return null;
}
//辅助方法：获取序号为 0<=i<size 的元素所在结点的前驱结点
private SLNode getPreNode(int i){
SLNode p = head;
for (; i>0; i--) p = p.getNext();
return p;
}
//获取序号为 0<=i<size 的元素所在结点
private SLNode getNode(int i){
SLNode p = head.getNext();

for (; i>0; i--) p = p.getNext();
return p;
}
//返回线性表的大小，即数据元素的个数。
public int getSize() {
return size;
}
//如果线性表为空返回 true，否则返回 false。
public boolean isEmpty() {
return size==0;
}
//判断线性表是否包含数据元素 e
public boolean contains(Object e) {
SLNode p = head.getNext();
while (p!=null)
if (p.getData().equals(e)) return true;
else p = p.getNext();
return false;
}
//返回数据元素 e 在线性表中的序号
public int indexOf(Object e) {
SLNode p = head.getNext();
int index = 0;
while (p!=null)
if (p.getData().equals(e)) return index;
else {index++; p = p.getNext();}
return -1;
}
//将数据元素 e 插入到线性表中 i 号位置
public void insert(int i, Object e) throws IndexOutOfBoundsException {
if (i<0||i>size)
throw new IndexOutOfBoundsException("错误，指定的插入序号越界。");
SLNode p = getPreNode(i);
SLNode q = new SLNode(e,p.getNext());
p.setNext(q);
size++;
return;
}

//删除线性表中序号为 i 的元素,并返回之
public Object remove(int i) throws IndexOutOfBoundsException {
if (i<0||i>=size)
throw new IndexOutOfBoundsException("错误，指定的删除序号越界。");
SLNode p = getPreNode(i);
Object obj = p.getNext().getData();
p.setNext(p.getNext().getNext());
size--;
return obj;
}
//删除线性表中第一个与 e 相同的元素
public boolean remove(Object e) {
SLNode p = getPreNode(e);
if (p!=null){
p.setNext(p.getNext().getNext());
size--;
return true;
}
return false;
}

//返回线性表中序号为 i 的数据元素
public Object get(int i) throws IndexOutOfBoundsException {
if (i<0||i>=size)
throw new IndexOutOfBoundsException("错误，指定的序号越界。");
SLNode p = getNode(i);
return p.getData();
}
}  

基于时间的比较 　　线性表的操作主要有查找、插入、删除三类操作。对于查找操作有基于序号的查找，即存取线性表中 i 号数据元素。由于数组有随机存取的特性，在线性表的顺序存储实现中可以在Θ(1)的时间内完成；而在链式存储中由于需要从头结点开始顺着链表才能取得，无法在常数时间内完成，因此顺序存储优于链式存储。查找操作还有基于元素的查找，即线性表是否包含某个元素、元素的序号是多少，这类操作线性表的顺序存储与链式存储都需要从线性表中序号为 0 的元素开始依次查找，因此两种实现的性能相同。综上所述，如果在线性表的使用中主要操作是查找，那么应当选用顺序存储实现的线性表。对于基于数据元素的插入、删除操作而言，当使用数组实现相应操作时，首先需要采用顺序查找定位相应数据元素，然后才能插入、删除，并且在插入、删除过程又要移动大量元素；相对而言链表的实现只需要在定位数据元素的基础上，简单的修改几个指针即可完成，因此链式存储优于顺序存储。对于基于序号的插入、删除操作，因为在顺序存储中平均需要移动一半元素；而在链式存储中不能直接定位，平均需要比较一半元素才能定位。因此顺序存储与链式存储性能相当。综上所述，如果在线性表的使用中主要操作是插入、删除操作，那么选用链式存储的线性表为佳。