线性顺序表(动态可变大小的数组存储)可以说是数据结构里最简单的模型了，但其重要性确不容忽视。Java中的ArrayList,Vector以及c++ vector , 我们都可以看线性顺序表的身影。它们都是基于线性顺序表的存储结构。那么，接下来，我们就结合类似的容器来了解线性顺序表。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @exception IllegalArgumentException if the specified initial capacity
* is negative
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
......
首先让我们来看下java 中ArrayList的源码，这里我本机的jdk的版本为1.6.0_29。可以看到默认ArrayList为10个大小的数组对象，elementData就是该数组的基址，当前数组中的元素个数为size。那么是如何做到大小可变，或者说动态增长呢？
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
可以看到当我们调用add方法添加元素时，会调用ensureCapacity，正如其名称一样，这个方法保证了ArrayList有足够的负载容量，如果容量不够用时，会将容量大小调整为newCapcity，它的大小总是(oldCapcity*3)/2+1,我们没必要深究该计算公式，只要知道调整完大小后，保证在调用add数次后不需要重新开辟空间，可以看做这是对程序性能的优化。接下来方法会调用arrays的待两个参数的copyof方法，其低层也是调用下面的copyof重载方法对容量进行调整。
Vector的实现跟ArrayList的实现大同小异，按照其ArrayList官方的说法，它跟vector的主要区别在于ArrayList是非同步的。当我们在多线程中使用ArrayList时，需要在外部进行同步。
/*(This class is roughly equivalent to
<tt>Vector</tt>, except that it is unsynchronized.)
.......
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access an <tt>ArrayList</tt> instance concurrently,
* and at least one of the threads modifies the list structurally, it
* <i>must</i> be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
* resizes the backing array; merely setting the value of an element is not
* a structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the list.
*/
不过，同Vector还有一个微小的差异，我们看看vector的类声明。
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* The array buffer into which the components of the vector are
* stored. The capacity of the vector is the length of this array buffer,
* and is at least large enough to contain all the vector's elements.
*
* <p>Any array elements following the last element in the Vector are null.
*
* @serial
*/
protected Object[] elementData;
/**
* The number of valid components in this {@code Vector} object.
* Components {@code elementData[0]} through
* {@code elementData[elementCount-1]} are the actual items.
*
* @serial
*/
protected int elementCount;
/**
* The amount by which the capacity of the vector is automatically
* incremented when its size becomes greater than its capacity. If
* the capacity increment is less than or equal to zero, the capacity
* of the vector is doubled each time it needs to grow.
*
* @serial
*/
protected int capacityIncrement;
......
vector提供了一个额外的成员变量来保存每次自动增长时的大小，这样就为我们提供了灵活的方式来提供每次增长的大小，而不像ArrayList那样提供一个固定的计算公式。至于好处当然就是可以更加合理的使用存储空间，特别对于存储器使用较为严格的程序。
最后，你也可以分析下STL中Vector的源码。其实关于线性顺序表的内容就这么简单，我们看下数据结构中，我们提供的顺序表结构及部分基本操作。
typedef struct tag_SqList
{
ElemType* elem;
size_t length;
size_t listsize;
}SqList,*pSqList;
基本操作如下：
//顺序存储线性表基本操作
//初始化顺序表
Status init_list(SqList* pL)
{
assert(pL);
pL->elem = (ElemType*) malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!(pL->elem)){
return -1;
}
pL->length = 0;
pL->listsize = LIST_INIT_SIZE;
}
//销毁顺序表
void destroy_list(Sqlist* pL)
{
assert(pL);
free(pL->elem);
L.elem = NULL;
L.length = 0;
L.listsize = 0;
}
void clear_list(SqList* pL)
{
assert(pL);
pL->length = 0;
}
Boolean is_empty(SqList* pL)
{
assert(pL);
if(L.length == 0)
return TRUE;
else
return FALSE;
}
size_t get_length(SqList* pL)
{
return pL->length;
}
Status get_elem(SqList* pL,int i,ElemType* pe)
{
assert(pL);
if(i<0 || i>pL->length)
return ERROR;
pe = &((pL->elem)[i]);
return OK;
}
//找到和元素e满足compare关系的第一个元素的位序
int locate_elem(SqList* pL,ElemType e,Status(*compare)(ElemType,ElemType))
{
assert(pL);
int i = 0;
ElemType* p = pL->elem;
while(i<pL.length && !compare(*p++,e)){
++i;
}
if(i<pL->length)
return i;
else
return -1;
}
//取得前序元素
Status prior_elem(SqList* pL,ElemType cur_e,ElemType* pre_e)
{
assert(pL);
int i = 1;
ElemType* p = pL->elem+1;
while(i<pL->length && *p!=cur_e){
++p;
++i;
}
if(i<pL->length){
pre_e = --p;
return OK;
}
return ERROR;
}
//取得后序元素
Status next_elem(SqList* pL,ElemType cur_e,ElemType* next_e)
{
assert(pL)
int i = 0;
ElemType* p = pL->Elem;
while(i<pL->length-1 && *p!=cur_e){
++p;
++i;
}
if(i<pL->length-1){
next == ++p;
return OK;
}
return ERROR;
}
Status insert_list(SqList* pL,int i,ElemType e)
{
assert(pL);
ElemType *newbase,*q,*p;
if(i<0 || i>pL->length-1)
return ERROR;
if(pL->length == pL->listsize){
newbase = (ElemType*)realloc(pL->elem,(pL->listsize+LIST_INCREMENT)*sizeof(ElemType))
if(!newbase)
return ERROR;
pL->elem = newbase;
pL->listsize += LIST_INCREMENT;
}
q = pL->elem+i;
for(p=pL->elem+(pL->length-1);p>=q;--p){
*(p+1) = *p;
}
*q = e;
++pL->length;
return OK;
}
Status delete_list(SqList* pL,int i,ElemType* pe)
{
assert(pL);
ElemType *p,*q;
if(i<0 || i>pL->length-1)
return ERROR;
p=pL->elem+i;
e=*p;
q=pL->elem+pL->length-1;
for(++p;p<=q;++p){
*(p-1) = *p;
}
pL->length--;
return OK;
}
完。
![树的基本概念(定义、基本术语、性质)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)