认识算法之数据结构（二）

通过上章节对数据结构的简单介绍，让我们有了个对数据结构的概念，那么，数据存储方式有哪几种呢，接下来的几篇章节将会对结构类型进行简单的介绍

通过上面的思维导图，我们可以大概知道了数据结构类型有以下这几种类型：

线性表：顺序表，链表，栈和队列
树结构：普通树，二叉树，线索二叉树
图：邻接矩阵表，邻接链表

顺序表

顺序表，我们可以简单地理解为数组 a[i]，通俗来讲我们可以将这些数组理解为由一节节载满数据车厢的火车，按顺序的一节节排列下去。而这些数组就像个火车一样在内存中跑下去，车厢的号码则是以a[i]来命名，a是数组的名字，中括号的i则代表数组中的第几个数据；假如这趟火车的某节车厢被人触发了警报器，乘务员需要查看情况的话，那么要怎么才能最快知道是哪里发生状况的呢？刚刚说了，数组可以比作一节节的火车，同理由于数据是存储在连续的空间内，所以我们只要知道内存地址是什么，就能直接访问目标数据（随机访问）。所以乘务员如果已经知道是数据C车厢发生了状况，那么只需直接去查看a[数据C]的车厢即可，也不需要从A车厢开始，一节一节车厢来仔细排除。

图（一）线性表数据存放示意图

在数组中新增数据

刚刚我们讲完了如何访问数组的数据，现在我们来讲一下如何新增和删除数据。其实这两个挺好理解的，继续以我们的火车为例。我们要把一个数据D搬上车厢，由于先前的a[1],a[2],a[3]车厢已经装了数据A，B，C所以不可能将数据D放在一起。所以我们要在数据C后面新增一节车厢a[4]，然后再将数据D放在新车厢a【4】中。

图（二）新增数据示意图

概括来讲就是在数组中如果需要添加数据的话，我们就需要新开辟一个内存的存储空间，再将数据存入相对应的数组空间中。同理，如果我们需要在数组任意一个地方插入数据，那么我们也需要在数组的末尾增加存储空间，然后在将已有数据一个个的往后挪，这样就可以腾出一个空的数组位置来存储数据。

在数组中删除数据

现在在来讲述一下如何删除数据，假如我们要删除数据B，那么我们首先需要将数据B搬出车厢，接下来将后面的数据一个接一个的往前移，先把数据C移动到a[2]车厢，接着再将数据D移动至a[2]车厢，这样下来，a[4]车厢也就成了空车厢，而这个空车箱将被回收，这样一来a[4]的空车箱与数据B便被删除了。

那么这里我也概括一下吧：先找到删除目标数组的数据（数据B），删除后便会成为一个空数组，但这个空数组并不会随着里面的数据消失而消失，而是会将空数组后面的数组按顺序往前递减，直到a[n+1]，当所有的数据移动完毕时，此时的空数组便变成了倒数的第一位，而这个倒数第一位的空数组a[n+1]则被删掉。

总结：数据结构中的数组就像一节线性排列下去的火车，新增和删除数据必须要呈线性形式展开，访问速度比较快，但删除和添加数据则比较麻烦和耗时间，添加则需要先增加数组的空间再将原有的数据其按顺序往后递增放置，如果是删除则数据则需要在把数据删除后将空余的数组空间往前递补，再删除后面因往前递补而空出来的数组空间。

总上所述我们可知线性表的基本特性为：

好了，刚刚说了那么多概念，现在我就用Java来简单的写一个线性表的增、删操作：

//添加数据操作
 public void add(String value) {
     if(length == arry.length) {
         String[] temp = new String[SIZE + N*SIZE];   //新增一个存储空间
         for (int i = 0; i < arry.length; i++) {    //往后递增
             temp[i] = arry[i];                    //交换长度
         }
         arry = temp;
     }
     arry[length++] = value;
 }

//删除以tip作标记的数据操作
    public boolean remove(int tip) {
        if(tip < 0 || tip> size()) {
            return false; //判断这个tip是否存在与数组中
        }
        for (int d = 0; d < size(); d++) {
            if(tip == d) {
                for(int k = d; k < size() - 1; k++ ) {
                    arry[d] = arry[d+1];   //将数组后面的数据往前递补
                }
                length--;    //最后再减去数组的长度
                return true; //返回true，作为删除完成的标记
            }
        }
        return false;

    }