======线性表======
大话数据结构 笔记 第三章\\
<wrap em>我的笔记均包含大量个人理解内容，存在一定偏差。如果您发现错误，请留言提出，谢谢！</wrap>
----
====线性表的定义====
线性表（List）是指的<wrap em>零个或者多个数据元素组成的有限序列</wrap>。它的特点体现在<wrap em>有序</wrap>和<wrap em>有限</wrap>上。用数学描述则有：
\\
\\
**若将线性表记作 $(a_1, a_2, ..., a_{i-1}, a_i, a_{a+i}, ..., a_n)$, 则表中 $a_{i-1}$ 领先于 $a_i$, $a_i$ 领先于 $a_{i+1}$, 称 $a_{i_1}$ 是 $a_i$ 的直接前驱元素，$a_{i+1}$ 是 $a_i$ 的直接后继元素。 当 $ i = 2, 3, ..., n$ 时， $a_i$ 有且只有一个直接前驱**；如图所示：
\\
\\
{{ :dsa:notes:dahua_ds:screen_shot_2017-03-23_at_10.00.18_am.png?400 |}}
\\
线性表的元素有两个重要的特点：
  * 线性表中的元素可以是一个元素，也可以是多个元素的合集。
  * 线性表中的所有元素必须是相同的类型。
====线性表的抽象数据类型====
我们知道抽象数据类型包括有共性的数据和一系列对数据的操作。那线性表的 //ADT// 呢？设想我们有一个队列，首先我们需要排队的人，其次我们需要指挥排队的人加入，离开，统计排队的人总数等等。这其实就是一个线性表操作的合集。我们用前面的 //ADT// 格式来定义线性表就是：
<code>
ADT List
DATA
    线性表是一系列数据对象集合， 每个元素的类型均为 DataType。 除了第一个元素以外，其他元素有且只有一个直接前驱元素；除了最后一个元素外，每个元素有且只有一个直接后驱元素；元素之前的关系是一对一关系。
Operations
    InitList(*L): 初始化操作，建立一个空的List L。
    ListEmpty(L): 表空返回 true, 否则返回 false。
    ClearList(*L): 清空 List。
    GetElem(L,i,*e): 将 List 中的第 i 个元素返回给 e。
    LocateElem (L, e): 在 List 中查找与 e 相同的元素； 成功返回该元素，失败则返回 0。
    ListInsert(*L, i, *e): 在 List 的第 i 个位置插入新元素 e。 
    ListDelete(*L, i, *e): 删除 List 中第 i 个元素，用 e 返回被删除元素的值。
    ListLength(L): 返回 List 元素的个数。
end ADT
</code>
上述基本是最基本的操作，我们可由这些基本操作组合衍生出一系列复杂的运算。
====线性表的顺序存储结构====
线性表的顺序存储结构就是指用线性表中的元素在存储单元里是地址连续的。这样的存储方式需要有三个属性：
  * 起始内存位置。
  * 最大容量 //Capacity//。
  * 当前 //List// 长度。
容量和长度是两个概念。容量指 //List// 最多能容纳元素，既占用的内存空间；而长度是指现阶段元素的个数，很可能会增长或者减少。我们可以看出来，长度在任意时间都是小于等于容量的。
===地址计算方法===
线性表的起始元素下标为 '0' 。每个元素对应的存储单元都有自己的起始地址；因此我们可以通过这样计算出第 i 个元素的地址：
<code>
//LOC是求址函数, c表示元素所占内存单元个数
LOC(a(i+1)) = LOC(a(i)) + c;
LOC(a(i)) = LOC(a(1)) + (i - 1)*c;
</code>
我们可以看到无论存取哪个元素，只需要在常数时间内完成。我们通常把有这种特点的存储结构成为**随机存储结构**。
====顺序存储结构的插入与删除====
===获取元素===
要实现获取元的方法很简单，直接访问下标 ''i-1'' 即可。这个函数可以分两步骤设计：
  - 验证下标是否在有效范围以内。
  - 如果在范围内，返回结果。
<code cpp linenums:1>
if (L.length == 0 || i < 1 || i > L.length) {
    return -1;
    }
return L.data[i-1];
</code>
===插入操作===
有个很形象的词可以用来形容线性表的插入操作：**加塞**。想一想如果你加塞，那么你后面所有的排队的都得往后排一位。线性表的插入操作也是如此。我们来详细分析一下这个函数：
  - 有效性验证：如果插入位置不合法，跑出异常。
  - 如果线性表长度大于容器长度，抛出异常，或者动态增加容量。
  - 从最后一个元素开始，往前遍历到第 ''i'' 个元素，把这些元素分别往后移动一位。
  - 在 ''i'' 的位置插入新元素。
<code cpp linenums:1>
if(L.length == MAXSIZE) //check if list is full
    return -1;
if(i < 1|| i > L.length + 1) //check if i is out of range
    return -1;
if (i < L.length) {// i is in range and not the last element
    for (auto k = L.length -1; k >= i - 1; --k)
        L.data[k+1] = L.data[k]; //from end to i, move every element backward with 1 unit
}
L.data[i-1] = e; // insert data
++L.length; // renew the length
</code>
===删除操作===
还是刚才的例子。试想一下如果那个加塞的人被人赶出去了，那么所有的人都会往前站一位。\\
\\
算法的思路如下：
  * 如果删除位置不合理，抛出异常
  * 删除元素
  * 从被删除的元素开始遍历到表尾，分别把这区域的元素都往前移动一位。
  * 表长减去1。
<code cpp linenums:1>
if (i < 1 || i > L.length) //check if element is in range
    return -1;
if ( i < L.length) { if element is not at end of List.
    for (auto k = i; k < L.length, ++k)
        L.data[k-1] = L.data[k]; // move all element in range forward.
--L.length;
return 0;
</code>
===List操作的时间复杂度===
我们来看一看插入删除的各种情况：
  - 最好情况：插入删除的元素都在 //List// 的尾部，因此我们不需要挪动元素，算法复杂度为$O(1)$。
  - 最差情况：插入删除的元素都在第一位，那么所有的元素都要往前或者往后挪一位，算法复杂度为 $O(n)$。
  - 至于平均情况，最终平移的次数与中间的元素的移动次数相等，为 $\frac{n+1}{2}$, 算法复杂度为 $O(n)$。
显然 //List// 的读取存储操作都是 $O(1)$，而插入删除都是 $O(n)$。 这说明物理结构相邻的 //List// 更适用于元素不太变化，但会进行大量存取的应用。
\\
\\
引申一下，我们可以得知其主要优缺点：
  * 优点：
    * 不用占用额外空间用于维护逻辑结构
    * 快速存取
  * 缺点：
    * 插入删除开销非常大
    * 表长度变化较大时，存储空间容量不好确定，同时也容易造成存储空间的碎片。
====线性空间的链式存储结构==== 
相比起物理结构为线性的 //List//, 链式存储结构则采用了类似于上下线的关系来处理 //List// 的物理结构，也就是逻辑上连续，物理上不连续。为了表示 $a_i$ 和 $a_{i+1}$ 的关系，我们必须需要一个数据使得我们可以从 $a_i$ 找到 $a_{i+1}$ 。在 C 语言中这个信息被称为指针。所以链式存储中，我们的元素实际上分成了两部分：**数据部分**和**指针部分**。我们把每一个这样的元素称为一个节点（//node//）, 而所有这些节点串起来，就形成了一个链式的线性表，简称链表（//linked_list//)：
\\
\\
{{ :dsa:notes:dahua_ds:wx20170323-134151_2x.png?600 |}}
\\
\\
对于线性表来说，总会有头和有尾。我们把链表中第一个存储位置叫做头指针，**整个链表的存取必须从头指针这里开始**。而最后一个元素意味着不用再指向下一个元素，所以最后一个节点的里的指针应该是 //NULL// 指针。
\\
\\
实际操作中为了方便，我们会定义一个不带任何数据的头结点，只包含指针的信息（或者附带链表的长度信息等等）。
====链表的实现====
===链表的数据===
根据上面的描述，我们需要先定义链表的 Data 模型：具有数据部分和指针部分。我们可以用结构体 / 类来定义这个存储结构：
<code cpp linenums:1>
struct Node {
    int data; 
    struct Node *next; //next point to the element after i
}
</code>
===链表的创建===
从我们先前对链表的理解来看，它的存储结构很松散；而我们也注意到对链表的插入/删除并不会对其他节点造成内存地址上的改动。这些特性让我们可以对链表进行动态的数据分配，即可以以很小的代价对表进行扩大，缩小，而内存的分配也会按照需要的大小来添加删除。
\\
\\
因此，链表的穿件过程是一个动态生成的过程，我们需要从空表的状态出发，一个个的链接节点，直到满足我们的要求为止。
\\
\\
创建链表的思路大概如下：
  * 如果链表为空，建立初始节点（头节点）
  * 如果链表非空，建立新节点，并用前一个节点指向新节点。
<code cpp linenums:1>
Linklist p, r;
*L = （LinkList）malloc( sizeof(Node)); //apply memory for LinkList
r = *L; //r point to the tail note
for (i = 0; i < n; ++i) {
    p = (Node *) malloc(sizeof(Node)); //generate a new Node；
    p.data() = rand(); //assign a random value for p
    r -> next = p; // link currently node to the end;
    r = p;//renew the pointer to the end
}
r -> next = NULL; //linklist finished 
</code>
r -> next = p 在这里是将表尾终端的指针指向新的节点p。 而 ''r = p'' 是将 ''r'' 指向 ''p'' 所在的节点，从而保证了 ''r'' 始终指向尾节点。而循环结束后，我们需要将链表的指针域置空，所以有  r -> next = NULL。这样再次遍历的时候，我们就可以通过判断节点的指针是否非空，来判断它是不是尾部节点了。
===6.3.单链表的读取===
由于链表中的元素除了第一个元素，其他的元素都需要自己的前驱来确定自己的位置；因此**单链表的读取必须从头开始**，通过遍历来找到所需要的元素。我们的思路大概如下：
  - 声明一个节点 ''p''。这个节点用于读取第 ''i'' 个元素的内容。我们初始化的时候用该节点指向链表 ''L''的下一个节点。
  - 当目前元素还没有接近到目标元素（第 ''i'' 个)时，我们不断的移动 ''p'' 的指针，让 ''p'' 指向下一个节点。
  - 如果到了链表的尾部, ''p''的数据部分为空，那证明没有找到第 ''i'' 个元素。
  - 否则的话，''i'' 的元素应该存到了 ''p'' 里面，这时我们返回 ''p''的值就可以。
<code cpp linenums>
LinkList p;
p = (*L).next();
j = 1;
while(p && j < i) {
    p = p.next();
    ++j;
    if ( !p || j>i) {
       return -1; //element not exist
    }
    return p.data() // got element content from i 
}
</code>
===6.4.单链表的插入===
相比起链表的读取和存储，单链表的插入和删除操作都显得简单了许多：
\\
\\
{{ :dsa:notes:dahua_ds:insert.jpg?600 |}}
\\
\\
大致的顺序是：
  - 先将新节点指向目标节点。
  - 再将前驱结点指向新节点。
用代码可以表示为：
<code cpp linenums:1>
new -> next = front -> next; // copy the pointer info from front node to new node, use the info point to the rear node
front -> next = new; // then let front point to the new node
</code>
注意，这里**不能交换操作的顺序**。试想一下如果我们先让前驱结点指向新节点，那么指向 ''rear'' 的指针信息会被新节点的信息覆盖，从而造成链表断链。
\\
\\
实现链表插入第 $i$ 个数据的的流程如下：
  - 初始化：建立一个节点 ''p'' 并指向链表的第一个节点。
  - 声明自变量 ''j'', 当 ''j < i'' （未达到插入位置）的时候， 让 ''p'' 的指针向后移动，并累加 ''j''。
  - 如果找到链表末尾 ''p'' 依然为空，证明该链表没有第 ''i'' 个元素，返回错误。
  - 如果查找成功，则建立一个空节点 ''s''。
  - 将值赋予空节点 ''s''。
  - 对 ''s'' 进行插入操作（详见上述代码）。
  - 程序成功执行，返回 ''0''。
===6.5.单链表的删除===
单链表的删除则更简单了，只需要把要删除的节点的前驱结点直接指向要删除节点的后置节点就可以：
\\
\\
{{ :dsa:notes:dahua_ds:delete.jpg?600 |}}
\\
\\
用代码可以表示为：
<code cpp linenums:1>
front -> next = new -> next;
</code>
注意：<wrap em>被删除的节点必须要释放内存。</wrap>
实现链表删除第 $i$ 个数据的的流程如下：
  - 初始化：创建节点 ''p'' 指向链表第一个节点，初始化 ''j'' 从 ''1'' 开始。
  - 当 ''j < i'' 时就遍历链表，让 ''p'' 的指针往后移动，不断指向下一个节点， ''j'' 自加。
  - 如果到链表末尾 ''p'' 为空，证明第 ''i'' 个元素不存在。
  - 否则查找成功，删除节点。
  - 释放被删除节点的内存。
  - 返回成功。
===链表清空（销毁）===
链表的删除和创建一样也需要遍历，同时也需要挨个的释放节点的内存。算法思路大概如下：
  - 声明节点 ''p'' 和 节点 ''q''，''p'' 在这里总是代表当前需要释放的节点， ''q'' 则代表了下一个节点。
  - 用 ''p'' 指向第一个节点。
  - 循环：
    - 用''q'' 指向 ''p'' 指向的节点的下一个节点。
    - 释放 ''p'' 指向的节点。
    - 将 ''q'' 指向的节点给 ''p''，使该节点在下一轮循环中被释放。
====总结====
学习完了线性表和链表，我们可以明确几个注意点：
  - 需要频繁查找的时候，使用线性表；而需要频繁插入删除的时候，使用单链表。
  - 如果不知道元素有多少，那么用单链表。如果事先知道长度，那么用线性表。