[数据结构与算法]数据结构（三）-线性表-顺序存储结构（Java、C语言）

从今天开始，本专栏将进入数据结构的学习，由于我学的书是C语言版，但本人比较喜欢Java，并且这两种语言在使用上存在一点细微的差别，因此，我将会从Java与C语言同时进行学习。今天学习第一个数据结构——线性表

一、线性表的概念

什么是线性表呢？
前面我们学到，数据元素之间存在的关系就是数据结构，那么线性表中的元素存在什么关系呢？
线性表：线性表是零个或多个数据元素的有限序列

那我们可以看到，这个线性表是一个有序地序列，元素之间存在先后顺序。打个比方就像小朋友排队一样
每一个小朋友就是线性表中的数据元素，他们是有自己的位置，顺序不能颠倒。这个顺序描述了各数据元素之间的先后关系。

二、线性表的抽象数据类型

抽象数据类型可以帮助我们更好地理解线性表

ADT List{
    数据对象：D={ai|ai∈Elemset, i=1,2,…,n, n≥0}
    数据关系：R={<ai?1,ai>|ai?1,ai∈D, i=2,…,n}
    基本操作：
    InitList(&L)
        操作结果：构造一个空的线性表 L
    DestroyList(&L)
        初始条件：线性表已存在
        操作结果：销毁线性表L
    ClearList(&L)
        初始条件：线性表已存在
        操作结果：置线性表L为空表
    ListEmpty(L)
        初始条件：线性表已存在
        操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE
    ListLenght(L)
        初始条件：线性表已存在
        操作结果：返回线性表L数据元素个数
    GetElem(L, i, &e)
        初始条件：线性表已存在（1≥i≥ListLenght(L)）
        操作结果：用e返回线性表L中第i个数据元素的值
    locatElem(L, e, comare())
        初始条件：线性表已存在，comare()是数据元素判定函数
        操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序
    PriorElem(L, cur_e, &pre_e)
        初始条件：线性表已存在
        操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义
    NextElem(L, cur_e, &next_e)
        初始条件：线性表已存在
        操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
    ListInsert(&L, i, e)
        初始条件：线性表已存在（1≥i≥ListLenght(L)+1）
        操作结果：在线性表L中第i个数据元素之前插入新元素e，L长度加1
    ListDelete(&L, i, &e)
        初始条件：线性表已存在（1≥i≥ListLenght(L)）
        操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1
    ListTraverse(L, visit())
        初始条件：线性表已存在
        操作结果：依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败
}ADT List

以上是一些线性表的基本操作，如果要实现更加复杂的方法，则需要我们有上面的基本使用方法去进行组合。

三、线性表的顺序存储结构（C语言）

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
大家学过C语言，应该了解数据存储的方法，线性表的顺序存储结构就是将线性表中的数据存储在一段地址连续的存储单元内，而数组便是这样一个符合条件的方法，因此，线性表的顺序存储结构我们将采用数组来进行实现。
（书上有例程代码，但是以下是我根据自己习惯写的）

#difine MAXSIZE 30
typedef int dataType;//存储类型为int型
typedef struct
{
	dataType data[MAXSIZE];
	int length;
}SqList

这里我们发现描述顺序存储结构需要三个属性：

• 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量：数组长度MAXSIZE。
• 线性表的当前长度：length。

（有关于地址的计算，这部分内容属于C语言的部分，我就不写了）

下面是对线性表的顺序存储结构的一些简单操作：
（1）获取元素：这个很好理解，就是获取数组中特定的位置的元素，让它返回即可。
（2）插入操作：插入操作需要实现的算法要稍微复杂一点，它需要完成以下几点：

• ①如果插入位置不合适，抛出异常；
• ②如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
• ③从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置；
• ④将要插入元素填入位置处；
• ⑤表长加1；

（3）删除操作：与插入操作是两个相反的操作；
下面是实现代码

#include<stdio.h> 
#define Max 20
typedef int datatype;//存储int型数据
typedef struct
{
	datatype data[Max];
	int length;//当前长度 
}SqList;

//初始化线性表
int InitList(SqList *L) 
{
	L->length=0;
	return 1;
}
//判断线性表是否为空
int ListEmpty(SqList L)
{ 
	if(L.length==0)
		return 1;
	else
		return 0;
} 
//重置线性表 
int  ClearList(SqList *L)
{ 
    L->length=0;
    return 1;
} 
//获取当前长度 
int ListLength(SqList L)
{
	return L.length;
}
//获取第i个元素的值
int Getdata(SqList L,int i)
{
	if(L.length==0 || i<1 || i>L.length)
    printf("输入错误，请重新输入\n");
    return L.data[i-1];
} 
//插入操作
int ListInsert(SqList *L,int i,int e)
{ 
	int k;
	if (L->length==Max)  //线性表已满 
	{
		printf("线性表已满\n");
		return 0;
	}
	if (i<1 || i>L->length+1)// 当i比第一位置小或者比最后一位置后一位置还要大时 
	{
		printf("输入错误，请重新输入");
		return 0;
	}
	if (i<=L->length)        // 若插入数据位置不在表尾 
	{
		for(k=L->length-1;k>=i-1;k--)  //将要插入位置之后的数据元素向后移动一位
			L->data[k+1]=L->data[k];
	}
	L->data[i-1]=e;          // 将新元素插入 
	L->length++;
	return 1;
} 
//删除操作 
int  ListDelete(SqList *L,int i) 
{ 
    int k;
    if (L->length==0)               // 线性表为空 
	{
		printf("线性表是空的\n");
		return 0;
	}
    if (i<1 || i>L->length)         // 删除位置不正确 
    {
    	printf("删除位置不正确\n");
	}
    if (i<L->length)                // 如果删除不是最后位置 
    {
        for(k=i;k<L->length;k++)// 将删除位置后继元素前移 
			L->data[k-1]=L->data[k];
    }
    L->length--;
    return 1;
}

int main()
{
	SqList q;
	printf("进行初始化操作\n");
	if(InitList(&q)==1)
	{
		printf("初始化成功\n");
	}
	printf("\n");
	printf("判断是否为空\n");
	if(ListEmpty(q)==1)
	{
		printf("该线性表为空\n");
	}
	printf("\n");
	printf("进行插入操作\n");
	int i=0;
	for(i=0;i<5;i++)
	{
		ListInsert(&q,i,i);
	}
	printf("插入完成\n");
	printf("\n");
	printf("进行删除操作\n");
	ListDelete(&q,2);
	printf("删除成功\n");
	printf("\n");
	printf("当前线性表长度：%d",ListLength(q));
}

运行结果图：

四、线性表的顺序存储结构（Java）

在Java中是有线性表的源码的，就是ArrayList的源码，大家也可以自己打开源码去看一下。这里Java由于是完全面向对象的语言，因此我们在写线性表的时候，也是将其作为一个类来写，并且将对线性表的操作作为成员函数，提供外部接口，这样更有利于线性表的整体使用。并且，Java具有泛型这一概念，那我们将线性表进行泛型化后，这个线性表可以在创建的时候决定存储什么类型。这样写出来的代码也比较接近源码，这里我们只写常规的几种操作（插入、删除、判断是否为空等方法）。我借鉴了其他博主的一些思路。

public class SequenceList<T>{
    //默认长度
    private int DEFAULT_SIZE = 16;
    //定义一个数组用于保存线性表的长度
    private Object[] elementData;
    //用于保存数组长度
    private int capacity;
    //保存顺序表中当前元素的个数
    private int size = 0;
   //创建新的空线性表
    public SequenceList(){
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
    /**
     * 用一个初始化元素来创建线性表
     * @param element 初始化元素
     */
    public SequenceList(T element){
        this();
        elementData[0] = element;
        size++;
    }
    /**
     * 用一个元素和指定长度来创建线性表
     * @param element 元素
     * @param initSize 指定长度
     */
    public SequenceList(T element,int initSize){
        capacity = 1;
        if(capacity<initSize){
            capacity = initSize +2;
        }
        elementData = new Object[capacity];
        elementData[0] = element;
        size++;
    }

    /**
     * 向顺序表中插入元素
     * @param element   待插入的元素
     * @param index 待插入的位置
     */
    public void insert(T element,int index){
        if(index<0||index>size){
            throw new IndexOutOfBoundsException("数组越界异常");
        }
        ensureCapacity(size+1);
        //把index以后的元素都后移一位
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        elementData[index] = element; 
        size++;
    }
    /**
     * 表长
     * @return
     */
    public int length(){
        return size;
    }
    /**
     * 向表中添加元素
     * @param element
     */
    public void add(T element){
        insert(element, size);
    }
    /**
     * 得到线性表存储的对象
     * @param index 获得的位置
     * @return  得到的结果
     */
    public T get(int index){
        if(index<0||index>size)
            throw new IndexOutOfBoundsException("数组越界异常");
        return (T)elementData[index];

    }
    /**
     * 判断线性表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size==0;
    }
    /**
     * 清空线性表
     */
    public void clear(){
        Arrays.fill(elementData, null);
        size = 0;
    }
    /**
     * 获取指定位置的前一个元素
     * @param index 线性表位置，若是取线性表最后一个元素，必须index = size,
     * size为线性表元素个数
     * @return 
     */
    public T priorElem(int index){
        if(index>0&&index<size+1)
            return (T)elementData[index-1];
        else {
            throw new IndexOutOfBoundsException("数组越界异常");
        }
    }
    /**
     * 删除指定位置的元素
     * @param index
     */
    public void delete(int index){
        if(index<0||index>size-1){
            throw new IndexOutOfBoundsException("数组越界异常");
        }else{
            //把数组前移一位
            System.arraycopy(elementData, index+1, elementData, index, size-index-1);
            size--;
            //清空最后一个元素
            elementData[size]=null;
        }
    }

    /**
     * 获取指定线性表位置的后一个元素
     * @param index 线性表位置，若是取线性表第0个元素，必须index=-1
     * @return
     */
    public T nextElem(int index){
        if (index==-1) {
            return (T)elementData[0];
        }
        else if (index<size-1&&index>-1) {
            return (T)elementData[index+1];
        }else{
            throw new IndexOutOfBoundsException("数组越界异常");
        }
    }

    /**
     * 确保数组所需长度大于数组原有长度
     * @param mCapacity 数组所需长度
     */
    private void ensureCapacity(int mCapacity){
        if(mCapacity>capacity){
            capacity=mCapacity+2;
            elementData = Arrays.copyOf(elementData, capacity);
        }
    }
}

五、顺序存储结构的优缺点

优点：

• 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；
• 可以快速地存取表中任一位置的元素

缺点：

• 插入和删除需要移动大量的元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”

六、总结

无论是C语言还是Java，对线性表顺序存储结构的方法实现思路是一样的，都是通过数组进行实现和操作的，这两者之间存在一定细微的差别，无论是Java的泛型化还是接口。C语言也有其独特的地方（指针），下一次学习，我们就将看到C语言指针的使用。