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

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

文章目录

- 一、线性表的概念
- 二、线性表的抽象数据类型
- 三、线性表的顺序存储结构（C语言）
- 四、线性表的顺序存储结构（Java）
- 五、顺序存储结构的优缺点
- 六、总结

一、线性表的概念

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

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

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

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

ADT List{
    数据对象：D={ai|ai∈Elemset, i=1,2,…,n, n≥0}
    数据关系：R={|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 
#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 (ilength)                // 如果删除不是最后位置 
    {
        for(k=i;klength;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{
    //默认长度
    private int DEFAULT_SIZE = 16;
    //定义一个数组用于保存线性表的长度
    private Object[] elementData;
    //用于保存数组长度
    private int capacity;
    //保存顺序表中当前元素的个数
    private int size = 0;
   //创建新的空线性表
    public SequenceList(){
        capacity = DEFAULT_SIZE;
        elementData = new Object[capacity];
    }
    
    public SequenceList(T element){
        this();
        elementData[0] = element;
        size++;
    }
    
    public SequenceList(T element,int initSize){
        capacity = 1;
        if(capacitysize){
            throw new IndexOutOfBoundsException("数组越界异常");
        }
        ensureCapacity(size+1);
        //把index以后的元素都后移一位
        System.arraycopy(elementData, index, elementData, index+1, size-index);
        elementData[index] = element; 
        size++;
    }
    
    public int length(){
        return size;
    }
    
    public void add(T element){
        insert(element, size);
    }
    
    public T get(int index){
        if(index<0||index>size)
            throw new IndexOutOfBoundsException("数组越界异常");
        return (T)elementData[index];

    }
    
    public boolean isEmpty(){
        return size==0;
    }
    
    public void clear(){
        Arrays.fill(elementData, null);
        size = 0;
    }
    
    public T priorElem(int index){
        if(index>0&&indexsize-1){
            throw new IndexOutOfBoundsException("数组越界异常");
        }else{
            //把数组前移一位
            System.arraycopy(elementData, index+1, elementData, index, size-index-1);
            size--;
            //清空最后一个元素
            elementData[size]=null;
        }
    }

    
    public T nextElem(int index){
        if (index==-1) {
            return (T)elementData[0];
        }
        else if (index-1) {
            return (T)elementData[index+1];
        }else{
            throw new IndexOutOfBoundsException("数组越界异常");
        }
    }

    
    private void ensureCapacity(int mCapacity){
        if(mCapacity>capacity){
            capacity=mCapacity+2;
            elementData = Arrays.copyOf(elementData, capacity);
        }
    }
}

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

优点：

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

缺点：

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

六、总结

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

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

C/C++/C#相关栏目本月热门文章