数组(Array)
数组是实现顺序存储结构的基础,数组(Array)存储具有相同数据类型的元素集合.一维数组占用一块内存空间,数组的存储单元个数称为数组容量,也称为数组长度.
每个存储单元的地址是连续的,即每个元素连续存储,计算第i个元素地址所需时间是一个常量,时间复杂度是O(1),与元素序号i无关.存取任何一个元素的时间复杂度是O(1)的数据结构称为随机存取结构.因此,数据是数据存储结构.
数组通过下标识别元素,元素的下标是其存储单元序号,表示元素在数组中的位置.一维数组使用一个下标唯一确定一个元素.二维数组使用两个下标唯一确定一个元素.
数组一旦占用一片存储空间,其地址和容量就是确定的,不能更改.因此,数组只能进行赋值、取值两种随机存储操作，不能进行插入、删除操作。当数组容量不够时，不能就地扩容。
顺序表
线性表的顺序存储结构称为顺序表（Sequential List），它使用一维数组依次存放线性表从a0到an-1的数据元素（a0，a1，…，an-1），将ai（0≤i＜n）存放在数组的第i个元素，使得ai与其前驱ai-1及后继ai+1的存储位置相邻，如图所示：
因此，数据元素在内存的物理存储次序反映了线性表数据元素之间的逻辑次序。
设Loc（a0）表示a0的存储地址，每个元素占用c个字节，则ai的存储地址Loc（ai）=Loc（a0）+i×c，是ai在线性表中序号i的线性函数，计算元素地址的时间复杂度是O（1）。因此，顺序表也是随机存取结构。
当顺序表使用的数组容量不够时，解决数据溢出的办法是，申请另一个更大容量的数组并进行数组元素复制，这样扩充了顺序表的容量。
接下来我们来看下顺序表类的具体实现;
顺序表的初始化是为顺序表分配一个预定义大小的数组空间，无参数构造方法设置顺序表长度为maxSize，有参数方法设置顺序表数组长度为形参n。初始化代码如下：
public class SequenceArrays<T> {
// 默认初始值长度,2的幂
final int DEFAULT_MAX_SIZE=1<<4;
//存储元素的数组长度
private T[] listArray;
// 保存顺序表的当前长度,即线性表当前有多少个数据
private int length;
private int arraySize;
public SequenceArrays() {
// 线性表初始为空,即还没有数据
length=0;
// 创建数组,数组长度为默认长度16,即还可以放入16个数据
listArray = (T[]) new Object[DEFAULT_MAX_SIZE];
}
public SequenceArrays(int arraySize) {
//this.arraySize = arraySize;
if (arraySize<0){
throw new ArrayException("数组长度不能小于0");
}
// 线性表初始为空,即还没有数据
length=0;
// 创建数组,数组长度n,即还可以放入n个数据
listArray = (T[]) new Object[arraySize];
}
...
}
顺序表的插入是指在顺序表的第pos-1个元素和第pos个元素之间插入一个新的元素，此时，顺序表中插入位置前后的元素之间的逻辑关系将发生变化，除非pos=n+1，否则必须通过顺序移动数据元素的存储位置才能体现逻辑关系的变化。插入过程如下图所示：
一般情况下，在第pos（1≤pos≤length）个元素之前插入一个元素时，需将第length至第pos（共length-pos+1）个元素向后移动一个位置。顺序表插入代码如下：
/**
*
* @param obj 插入的元素 时间复杂度为O(n)
* @param pos 插入元素的位置,数组元素的下标为pos-1
* @return boolean true -插入成功, false- 插入失败
*/
public boolean add(T obj,int pos){
//插入地址非法
if ( pos<1 || pos>length+1){
throw new ArrayException("插入位置不合法");
}
//当前数组的位置已被数据填满
if (length==listArray.length){
//重新创建一个新的数组,数组长度为原长度的2倍
T[] p = (T[]) new Object[length*2];
//通过for循序把原数组的元素放入到新数组p中
for (int i=0;i<length;i++){
p[i]=listArray[i];
}
//把新数组p赋值给原listArray;
listArray=p;
}
// 需要插入元素的位置的后续元素向后挪一个位置,从最后一个元素开始挪, 数组的下标=数组中元素个数-1.
for (int i=length;i>=pos;i--){
listArray[i]=listArray[i-1];
}
// 在指定位置插入元素obj
listArray[pos-1]=obj;
// 数组中元素个数加1
length++;
return true;
}
从源码可知,顺序表插入需要的注意的点如下：
(1)要检验插入位置的有效性，这里pos的有效范围是：1≤pos≤length+1，其中length为原表长。
(2)顺序表中数据区域有listArray.length个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下需要申请容量为原数组容量*2的数组并进行数组元素复制。
(3)注意数据的移动方向。从表尾开始依次向前，一个一个地往后移动数据元素，最后把要插入的元素obj放到数组下标为pos-1的地方。
(4)注意数据的移动方向。从表尾开始依次向前，一个一个地往后移动数据元素，最后把要插入的元素obj放到数组下标为pos-1的地方。
顺序表的删除是指删除顺序表中的第pos个元素，删除操作也会导致被删除位置前后的元素之间的逻辑关系发生变化，因此，除非删除位置是表中的最后一个元素，否则也必须通过顺序移动数据元素的存储位置才能体现逻辑关系上的变化。删除过程如下：
一般情况下，删除第pos（1≤pos≤length）个元素时需将从第pos+1至第length（共n-i)个元素依次向前移动一个位置，删除代码如下：
/**
* 移除数组中的元素 时间复杂度为O(n)
* @param pos 需要移除的数组元素的位置,数组元素的下标为 pos-1
* @return
*/
public T remove(int pos){
//判断数组是否为空的
if (isEmpty()){
throw new ArrayException("数组为空,不能执行删除操作");
}else{
if (pos<1 || pos>length){
throw new ArrayException("数组下标越界了,pos值不合法");
}
T t= listArray[pos-1];
// 数组中的元素往前移动1外, 从下标为pos+1的元素开始移动
for (int i= pos;i<=length;i++){
listArray[i-1] =listArray[i];
}
//数组中元素个数需要减1
length--;
return t;
}
}
从源码可知，顺序表的删除需要注意如下几个点：
(1)当表空时不能做删除。
(2)删除第pos个元素，pos的取值为1≤pos≤length，否则第pos个元素不存在，因此，要检查删除位置的有效性。
(3)注意数据移动的方向。把删除位置pos之后的数据依次前移一个位置，最后顺序表的长度减1。
(4)注意数据移动的方向。把删除位置pos之后的数据依次前移一个位置，最后顺序表的长度减1。
当在顺序表中某个位置上插入或删除一个数据元素时，其时间主要耗费在移动元素上。在顺序表中插入或删除一个数据元素，平均约移动表中一半元素，算法add和remove的时间复杂度均为O(n)。
顺序表的查找是指在顺序表中查找某个值等于给定值的元素位置。在顺序表中查找是否存在和obj相同的数据元素的最简便的方法是：把obj和顺序表中的数据元素逐个比较，若顺序表中存在和obj相同的元素，则比较次数为i（1≤i≤length），否则为length，即算法find的时间复杂度为O(n)，则n=length。顺序表的查找代码如下：
/**
* 查找元素 时间复杂度为O(n)
* @param obj 需要查找的数组中的元素
* @return 返回的是数组中的第几个元素, -1 表示没有查找到元素
*/
public int find(T obj){
if (isEmpty()){
throw new ArrayException("数组为空");
}else{
// 通过for循环,从下标0 开始元素查找,主要是通过元素值比对的方式查找
for (int i=0;i<length;i++){
listArray[i].equals(obj);
return i+1;
}
}
return -1;
}
顺序表中第pos个元素存放在数组listArray下标为pos-1的位置，也就是当位置转换为下标时要进行一个减一的运算。算法中1≤pos≤length，当pos值有效时返回listArray[pos-1]，否则返回null，具体代码如下：
/**
* 获取数组的第pos个位置的元素
* @param pos 数组中元素的位置, 数组元素的下标为pos-1
* @return
*/
public T value(int pos){
if (isEmpty()){
throw new ArrayException("数组为空");
}else{
if (pos<1 || pos>length){
throw new ArrayException("数组下标越界了,pos值不合法");
}
return listArray[pos-1];
}
}
则顺序表实现的完整代码如下：
public class SequenceArrays<T> {
// 默认初始值长度,2的幂
final int DEFAULT_MAX_SIZE=1<<4;
//存储元素的数组长度
private T[] listArray;
// 保存顺序表的当前长度,即线性表当前有多少个数据
private int length;
private int arraySize;
public SequenceArrays() {
// 线性表初始为空,即还没有数据
length=0;
// 创建数组,数组长度为默认长度16,即还可以放入16个数据
listArray = (T[]) new Object[DEFAULT_MAX_SIZE];
}
public SequenceArrays(int arraySize) {
//this.arraySize = arraySize;
if (arraySize<0){
throw new ArrayException("数组长度不能小于0");
}
// 线性表初始为空,即还没有数据
length=0;
// 创建数组,数组长度n,即还可以放入n个数据
listArray = (T[]) new Object[arraySize];
}
/**
*
* @param obj 插入的元素 时间复杂度为O(n)
* @param pos 插入元素的位置,数组元素的下标为pos-1
* @return boolean true -插入成功, false- 插入失败
*/
public boolean add(T obj,int pos){
//插入地址非法
if ( pos<1 || pos>length+1){
throw new ArrayException("插入位置不合法");
}
//当前数组的位置已被数据填满
if (length==listArray.length){
//重新创建一个新的数组,数组长度为原长度的2倍
T[] p = (T[]) new Object[length*2];
//通过for循序把原数组的元素放入到新数组p中
for (int i=0;i<length;i++){
p[i]=listArray[i];
}
//把新数组p赋值给原listArray;
listArray=p;
}
// 需要插入元素的位置的后续元素向后挪一个位置,从最后一个元素开始挪, 数组的下标=数组中元素个数-1.
for (int i=length;i>=pos;i--){
listArray[i]=listArray[i-1];
}
// 在指定位置插入元素obj
listArray[pos-1]=obj;
// 数组中元素个数加1
length++;
return true;
}
/**
* 移除数组中的元素 时间复杂度为O(n)
* @param pos 需要移除的数组元素的位置,数组元素的下标为 pos-1
* @return
*/
public T remove(int pos){
//判断数组是否为空的
if (isEmpty()){
throw new ArrayException("数组为空,不能执行删除操作");
}else{
if (pos<1 || pos>length){
throw new ArrayException("数组下标越界了,pos值不合法");
}
T t= listArray[pos-1];
// 数组中的元素往前移动1外, 从下标为pos+1的元素开始移动
for (int i= pos;i<=length;i++){
listArray[i-1] =listArray[i];
}
//数组中元素个数需要减1
length--;
return t;
}
}
/**
* 查找元素 时间复杂度为O(n)
* @param obj 需要查找的数组中的元素
* @return 返回的是数组中的第几个元素, -1 表示没有查找到元素
*/
public int find(T obj){
if (isEmpty()){
throw new ArrayException("数组为空");
}else{
// 通过for循环,从下标0 开始元素查找,主要是通过元素值比对的方式查找
for (int i=0;i<length;i++){
listArray[i].equals(obj);
return i+1;
}
}
return -1;
}
/**
* 获取数组的第pos个位置的元素
* @param pos 数组中元素的位置, 数组元素的下标为pos-1
* @return
*/
public T value(int pos){
if (isEmpty()){
throw new ArrayException("数组为空");
}else{
if (pos<1 || pos>length){
throw new ArrayException("数组下标越界了,pos值不合法");
}
return listArray[pos-1];
}
}
/**
* 修改数组第pos个位置的元素
* @param obj 需要修改的值
* @param pos 第pos个位置,即数组元素的下标为pos-1
* @return
*/
public boolean modify(T obj,int pos){
if (isEmpty()){
throw new ArrayException("数组为空");
}else{
if (pos<1 || pos>length){
throw new ArrayException("数组下标越界了,pos值不合法");
}
listArray[pos-1]=obj;
return true;
}
}
/**
* 获取素组的长度
* @return
*/
public int size(){
return length;
}
/**
* 打印数组元素
*/
public void show(){
System.out.println("");
System.out.print("数组元素为:");
int lastelement = length-1;
// 打印所有数组元素
for (int i=0;i<length;i++) {
T element = listArray[i];
if(element !=null){
System.out.print(element);
if (i != lastelement){
System.out.print("、");
}
}
}
}
/**
* 清空数组
*
*/
public void clear(){
length=0;
}
/**
* 判断数组是否为空
* @return
*/
private boolean isEmpty() {
boolean emptyflag =false;
if(length==0 || listArray==null){
emptyflag = true;
}
return emptyflag;
}
public static void main(String[] args) {
int l,i;
int[] a ={10,12,3,8,6,4,9};
l=a.length;
SequenceArrays<Integer> arrays = new SequenceArrays<>();
for (i=0;i<l;i++){
arrays.add(a[i],i+1);
}
arrays.size();
arrays.show();
//插入元素
arrays.add(17,5);
arrays.size();
arrays.show();
//删除元素
arrays.remove(5);
arrays.size();
arrays.show();
//修改数组
arrays.modify(90,6);
arrays.size();
arrays.show();
}
}
在上述主函数中先初始化一个顺序表，再对该顺序表进行插入、删除、查找操作，程序运行结果如下：
顺序表具有的搜索方便，但插入或者删除某些元素就比较麻烦的特点。