本文主要内容：线性表的逻辑结构和存储结构以及相应算法；

1. 定义和特点

1. 定义：

由N（N>=0）个数据特性相同的元素构成的有限序列称为线性表。N为线性表长度，当N为0时就是空表。

非空线性表或是线性结构，其的特点是：

线性表的顺序表示和实现
线性表的顺序表：指的是用一组地址连续的存储单元依次存储线性表的数据元素。（这种表示又叫线性表的顺序存储结构或顺序映像）Sequential List

2. 特点**：

逻辑上相邻的元素，物理上也相邻 ；

公式：Loc（ai）=Loc(a0）+（i-1）x L
所以只要确定了一个元素的位置，表中任意元素都可以随机存取，因此线性表是一种随机存取的存储结构。
存取的时间复杂度为O(1).

缺点：插入和删除费时，需要移动大量的元素，长度固定。

3. 线性表的算法时间复杂度

4. 线性表的链式表示和实现

线性表的链式存储结构的特点：
用一组任意的存储单元（可连续可不连续）存储线性表的数据元素，存储时需要额外的存储单元存储后继元素的信息。

每个存储的元素称为节点（Node），它由两部分组成：

• 数据域：存储数据元素信息的区域；
• 指针域：存储直接后继元素的位置；（称为：指针或链）

由n个节点链结成一个链表，即为链式的线性表。

根据链表所含的指针个数，指针指向，指针连接方式，将链表分为：

其中单链表、循环链表、双向链表用于实现线性表的链式存储结构，其他链表多用于实现树和图等非线性结构。

4.1 单链表
单链表的存取必须从头指针开始进行，头指针指示链表的第一个节点，最后一个元素的指针为空NULL。
特点：

• 元素之间的关系有指针域指示；
• 逻辑上相邻元素，物理上不一定相邻；
• 存储结构为非顺序印象，是链式映像；

一般为了处理方便，会在单链表的第一个节点之前设置一个头结点，该头结点的数据域可以不存储任何信息，也可以存储线性表的长度信息或其它附加信息，头结点的指针域存储指向第一个节点的指针。

示例：
指针头: H –>31，如果H指向null表示为空表；

要取得第i个数据元素必须从头指针出发顺链进行寻找,所以单链表是顺序存取的存取结构。

查找算法：

• 按序号查找第i个元素，时间复杂度为O(n);
• 按值查找值为e的元素，时间复杂度为O(n);

插入算法：
将值为e的节点插入到第一个节点的位置上即ai-1和ai之间 - 找到ai-1节点，并有指针p指向该节点；

• 生成新节点s；
• 设置新节点s的数据域设置为e，指针域设置为ai；
• 设置ai-1的指针域指向新节点s；
  时间复杂度为O（n），主要时间是查找ai-1

删除算法： 时间复杂度为O（n），主要时间在查找ai-1

单链表的创建：
链表从一个空表开始，动态的不断插入数据，形成链表；

此时的根据节点的插入位置不同分为：前插法和后插法；

• 前插法：通过将新节点逐个插入链表的头部（头节点之后），来创建链表；
• 后插法：为了使新节点能够插入到尾部，需要增加一个指针r指向链表的未节点，初始时r也指向头节点。

前插法创建链表：前插法创建一个N个元素的值的链表，时间复杂度为O(n);
后插法创建链表：时间复杂度为O(n)；

4.2 循环链表
另一种链式存储，特点是表中的最后一个节点的指针，指向头节点，整个链表的形式形成一个环。从表中任意节点出发都可以找到其他节点。
合并两个循环链表时，只需要表1的尾->表2的第一个节点（释放表2的头节点），表2的尾指针->表1的头节点。

4.3 双向链表
修改节点的结构，之前的节点只有后继指针，现在给节点添加上前驱指针
双向链表的节点结构：

双向链表也有循环链表叫双向循环链表

5.线性表的应用

两个线性表La和Lb: La长度为m,Lb 的长度为n；

1. 合并两个线性表：

for(int i=0;i<Lb.length;i++){
    GetElem(Lb,i,e);
    if(LocateElem(La,e)){
        ListInsert(La,++La_len,e);
    }
}

假设GetElem和ListInsert与表长无关，LocateElem执行的时间与表长成正比，则时间复杂度为O（m*n）

2. 有序表的合并：

public class MergeOrderedList {

    String TAG = "MergeOrderedList";
    //顺序存储结构的两个有序线性表
    int[] LA = {3, 5, 8, 11, 23};
    int[] LB = {1, 2, 5, 7, 11, 15, 20, 28};


    int[] LC = new int[LA.length + LB.length];//new 空表
    int len = LA.length > LB.length ? LB.length : LA.length;


    public void megre() {

        if (len <= 0) {
            return;
        }

        int pa = 0, pb = 0;
        int pa_last = LA.length - 1, pb_last = LB.length - 1;
        int pc = 0;

        while (pa <= pa_last && pb <= pb_last) {

            //依次取LA和LB中小的值到LC表中，知道一中一个表到最后一个元素
            if (LA[pa] < LB[pb]) {
                LC[pc] = LA[pa];
                pa++;
            } else if (LA[pa] > LB[pb]) {
                LC[pc] = LB[pb];
                pb++;
            }else{
                LC[pc] = LA[pa];
                pa++;
                pb++;
            }

            pc++;

        }

        while (pa <= pa_last) {
            LC[pc] = LA[pa];
            pc++;
            pa++;
        }

        while (pb <= pb_last) {
            LC[pc] = LB[pb];
            pc++;
            pb++;
        }

    }

    public void printLC() {

        if (LC.length <= 0) {
            return;
        }


        for (int i : LC) {
            Log.e(TAG, "i>>>>" + i);
        }

    }


}

调用

MergeOrderedList m = new MergeOrderedList();
m.megre();
m.printLC();

结果

image.png

时间复杂度O(mn）；
需要开辟新的辅助空间，所以空间复杂度也为O（mn）；

3. 链式有序表的合并
   时间复杂度为O(m*n)；
   空间复杂度为O（1）；