图片来自互联网
数据结构
研究应用程序数据之间的逻辑关系，存储方式及其操作，还要分析各种数据结构在时间开销，空间开销的优劣。
数据元素之间存在的关联关系被称为数据的逻辑结构，应用程序中的逻辑结构大致有4中：
集合：数据元素之间只有“同属一个集合”的关系。
线性结构：数据元素之间存在一个对一个的关系。
树形结构：数据元素之间存在一个对多个的关系。
图状结构或网状结构：数据元素之间存在多个对多个的关系。
而对于数据不同的逻辑结构，计算机在物理磁盘上有两种物理存储结构：
顺序存储结构
链式存储结构
线性结构——线性表的顺序存储结构
线性表的顺序存储结构是指用一组地址连续的存储单元一次存放线性表的元素。
当程序采用顺序存储结构来实现线性表时，线性表中相邻元素对应的存储地址也是相邻的。
用java实现顺序线性表代码如下：
import java.util.Arrays;
/**
* 线性表
* 定义：线性表是由n（n>=0）个数据元素（节点）a1，a2，...an组成的有限序列
*
* @author LENOVO
*
*/
public class SequenceList<T> {
private int DEFAULT_SIZE = 16;
//保存数组长度
private int capacity;
//定义一个数组用于保存顺序线性表的元素
private Object[] elementData;
//保存顺序表中当前元素的个数
private int size = 0;
//以默认数组长度创建空顺序线性表
public SequenceList() {
capacity = DEFAULT_SIZE;
elementData = new Object[capacity];
}
//以初始化元素创建顺序线性表
public SequenceList(T element){
this();
elementData[0] = element;
size++;
}
/**
* 以指定长度的数组来创建顺序线性表
* @param element 指定顺线性表中的第一个元素
* @param initsize 指定顺序线性表底层数组的长度
*/
public SequenceList(T element,int initsize){
capacity = 1;
//吧capacity设为大于initsize的最小的2的n次方
while(capacity<initsize){
capacity<<=1;
}
elementData = new Object[capacity];
elementData[0] = element;
size++;
}
/**
* 获取顺序线性表的大小
* @return
*/
public int length(){
return size;
}
/**
* 获取顺序线性表中索引为i处的元素
* @param i
* @return
*/
public T get(int i){
if(i<0||i>size-1){
throw new IndexOutOfBoundsException("线性表索引越界");
}
return (T)elementData[i];
}
/**
* 查找顺序线性表中指定元素的索引
* @param element
* @return
*/
public int locate(T element){
for(int i=0;i<size;i++){
if(elementData[i].equals(element)){
return i;
}
}
return -1;
}
/**
* 向顺序线性表中指定位置插入一个元素
* @param element
* @param index
*/
public void insert(T element,int index){
if(index<0||index>size){
new IndexOutOfBoundsException("线性表索引越界");
}
ensureCapacity(size+1);
//将指定索引处之后的所有元素都向后移动
System.arraycopy(elementData, index, elementData, index+1, size-index);
elementData[index] = element;
size++;
}
/**
* 在顺序线性表的开始处添加一个元素
* @param element
*/
public void add(T element){
insert(element,size);
}
/**
* 扩充数组长度
* @param minCapacity
*/
private void ensureCapacity(int minCapacity) {
//如果数组原有长度小于目前所需要长度
if(minCapacity>capacity){
//不断的将capacity乘以2直到capacity大于minCapacity
while(capacity<minCapacity){
capacity<<=1;
}
elementData = Arrays.copyOf(elementData, capacity);
}
}
/**
* 删除指定索引处的元素
* @param index
* @return
*/
public T delet(int index){
if(index<0||index>size-1){
throw new IndexOutOfBoundsException("线性表索引越界");
}
T oldValue = (T)elementData[index];
int numMoved = size-index-1;
if(numMoved>0){
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
elementData[--size] = null;
return oldValue;
}
/**
* 删除线性表中最后一个元素
* @return
*/
public T remove(){
return delet(size-1);
}
/**
* 判断线性表是否为空
* @return
*/
public boolean empty(){
return size==0;
}
/**
* 清空线性表
*/
public void clear(){
//将底层数组所有元素赋值为null；
Arrays.fill(elementData, null);
size = 0;
}
public String toString(){
if(size==0){
return "[]";
}else{
StringBuilder sb = new StringBuilder("[");
for(int i=0;i<size;i++){
sb.append(elementData[i].toString()+",");
}
int len = sb.length();
return sb.delete(len-1, len).append("]").toString();
}
}
}
测试类及运行结果如图：
从运行结果上看SequenceList类实现了部分ArrayList类的功能，其实就是简化版的ArrayList。