What & How & Why

大话数据结构 笔记 第三章
我的笔记均包含大量个人理解内容，存在一定偏差。如果您发现错误，请留言提出，谢谢！

线性表（List）是指的零个或者多个数据元素组成的有限序列。它的特点体现在有序和有限上。用数学描述则有：

若将线性表记作 $(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$ 有且只有一个直接前驱；如图所示：


线性表的元素有两个重要的特点：

• 线性表中的元素可以是一个元素，也可以是多个元素的合集。
• 线性表中的所有元素必须是相同的类型。

我们知道抽象数据类型包括有共性的数据和一系列对数据的操作。那线性表的 ADT 呢？设想我们有一个队列，首先我们需要排队的人，其次我们需要指挥排队的人加入，离开，统计排队的人总数等等。这其实就是一个线性表操作的合集。我们用前面的 ADT 格式来定义线性表就是：

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

线性表的顺序存储结构就是指用线性表中的元素在存储单元里是地址连续的。这样的存储方式需要有三个属性：

• 起始内存位置。
• 最大容量 Capacity。
• 当前 List 长度。

容量和长度是两个概念。容量指 List 最多能容纳元素，既占用的内存空间；而长度是指现阶段元素的个数，很可能会增长或者减少。我们可以看出来，长度在任意时间都是小于等于容量的。

线性表的起始元素下标为 '0' 。每个元素对应的存储单元都有自己的起始地址；因此我们可以通过这样计算出第 i 个元素的地址：

//LOC是求址函数, c表示元素所占内存单元个数
LOC(a(i+1)) = LOC(a(i)) + c;
LOC(a(i)) = LOC(a(1)) + (i - 1)*c;

要实现获取元的方法很简单，直接访问下标 i-1 即可。这个函数可以分两步骤设计：

1. 验证下标是否在有效范围以内。
2. 如果在范围内，返回结果。

if (L.length == 0 || i < 1 || i > L.length) {
    return -1;
    }
return L.data[i-1];

有个很形象的词可以用来形容线性表的插入操作：加塞。想一想如果你加塞，那么你后面所有的排队的都得往后排一位。线性表的插入操作也是如此。我们来详细分析一下这个函数：

1. 有效性验证：如果插入位置不合法，跑出异常。
2. 如果线性表长度大于容器长度，抛出异常，或者动态增加容量。
3. 从最后一个元素开始，往前遍历到第 i 个元素，把这些元素分别往后移动一位。
4. 在 i 的位置插入新元素。

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

还是刚才的例子。试想一下如果那个加塞的人被人赶出去了，那么所有的人都会往前站一位。

算法的思路如下：

• 如果删除位置不合理，抛出异常
• 删除元素
• 从被删除的元素开始遍历到表尾，分别把这区域的元素都往前移动一位。
• 表长减去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;

我们来看一看插入删除的各种情况：

1. 最好情况：插入删除的元素都在 List 的尾部，因此我们不需要挪动元素，算法复杂度为$O(1)$。
2. 最差情况：插入删除的元素都在第一位，那么所有的元素都要往前或者往后挪一位，算法复杂度为 $O(n)$。
3. 至于平均情况，最终平移的次数与中间的元素的移动次数相等，为 $\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)：



对于线性表来说，总会有头和有尾。我们把链表中第一个存储位置叫做头指针，整个链表的存取必须从头指针这里开始。而最后一个元素意味着不用再指向下一个元素，所以最后一个节点的里的指针应该是 NULL 指针。

实际操作中为了方便，我们会定义一个不带任何数据的头结点，只包含指针的信息（或者附带链表的长度信息等等）。

根据上面的描述，我们需要先定义链表的 Data 模型：具有数据部分和指针部分。我们可以用结构体 / 类来定义这个存储结构：

struct Node {
    int data; 
    struct Node *next; //next point to the element after i
}

从我们先前对链表的理解来看，它的存储结构很松散；而我们也注意到对链表的插入/删除并不会对其他节点造成内存地址上的改动。这些特性让我们可以对链表进行动态的数据分配，即可以以很小的代价对表进行扩大，缩小，而内存的分配也会按照需要的大小来添加删除。

因此，链表的穿件过程是一个动态生成的过程，我们需要从空表的状态出发，一个个的链接节点，直到满足我们的要求为止。

创建链表的思路大概如下：

• 如果链表为空，建立初始节点（头节点）
• 如果链表非空，建立新节点，并用前一个节点指向新节点。

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