线性表

线性表的定义

线性表（List）： 零个或多个数据元素的有限序列

除了首尾两数据元素外，线性表的每个数据元素，都有一个 直接前驱 元素和一个 直接后继 元素。而首元素只有一个直接后继元素，没有直接前驱元素；尾元素只有一个直接前驱元素，没有直接后继元素

线性表元素的长度： 线性表中数据元素的个数

空表： 当线性表的长度为0时，即线性表中数据元素个数为0时，称该线性表为空表

在复杂的线性表中，一个数据元素可以由若干个数据项组成。

线性表的抽象数据类型

线性表的抽象数据类型如下：

ADT 线性表(List)
Data 
  线性表的数据对象为{a1,a2,a3,...,an}，每个数据元素的类型均为 Datatype 。
  其中，每一个数据元素之间的逻辑关系是一对一的关系。
Operation
  InitList(*L);    //初始化操作，创建一个空表
  ListEmpty(L);    //判断线性表是否为空表，是返回 true ，否返回 false 
  ClearList(*L);    //清空线性表
  GetElem(L, i, *e);    //获取线性表中第 i 个位置的数据元素的值并返回给 e 
  ListInsert(*L, i, e);    //插入数据元素 e 到线性表 L 的第 i 个位置
  ListDelete(*L, i, e);    //删除线性表中第 i 个位置的数据元素，并使用 e 返回其值
  ListLength;    //返回线性表的长度
endADT

注意，以上的 Operation 只是线性表的基本操作 。针对于更复杂的操作，完全可以使用基本操作的组合来完成。

上述函数参数为线性表的地址的，均是需要修改线性表长度的。

线性表的顺序存储结构

线性表的顺序存储结构： 指的是用一段 地址连续的存储单元 依次存储线性表的数据元素

线性表的顺序存储示意图

既然线性表的每个数据元素的类型都相同，所以可以 用一维数组来实现顺序存储结构 。

线性表的顺序存储的结构代码：

#define MAXSIZE 20    //设置存储空间初始分配量，这里假设为 20 个数据元素
typedef int ElemType;    //Elemtype 类型根据实际情况而定，这里假设为 int 
typedef struct {
  Elemtype data[MAXSIZE];        //数组存储数据元素，最大值为 MAXSIZE 
  int length;        //线性表当前长度，这里用 int 变量存储
}SqList;

或者可以使用 malloc 函数动态申请一片连续的存储空间，如何将空间地址返回给链表的头指针成员变量。

#define MAXSIZE 20    //设置存储空间初始分配量，这里假设为 20 个数据元素
typedef int ElemType;    //Elemtype 类型根据实际情况而定，这里假设为 int 
typedef struct {
  Elemtype *data;        //指向 malloc(MAXSIZE) 分配的空间的头指针
  int length;        //线性表当前长度，这里用 int 变量存储
}SqList;

然后在 InitList 函数里使用 malloc 函数分配空间给并将地址赋值给 data

由结构代码可得 描述顺序存储结构的三个属性：

存储空间的起始位置： 数组 data ，它的存储位置就是存储空间的起始位置。
线性表的最大存储容量： 数组长度 MAXSIZE
线性表（当前）长度： length

注意：数组长度 MAXSIZE 与线性表的长度 length 不同 ，数组的长度是指存放线性表数据元素的存储空间的长度。在任意时刻，线性表长度都小于或等于数组长度。

一般来说，数组长度 MAXSIZE 设置完后是不会改变的。而线性表的长度是可以改变的。

由于数组的下标是从0开始的，所以一般线性表的第 i 个元素存储在数组下标为 i-1 的位置。

存储器中的每个存储单元都有自己的编号，这个编号成为地址。

假设存储每个数据元素的空间大小为 c ，那么线性表中第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系（LOC 表示获得存储位置的函数）。

LOC(a_i+1) = LOC(a_i)+c

所以线性表中第 i 个元素 a_i 的存储位置由 a₁ 推导为：

LOC(a_i) = LOC(a₁)+(i-1)*c

示意图

通过这个公式可以随时算出线性表中任意位置的地址，且时间相同，其时间复杂度为 O(1) ，所以基于此之上的操作的时间复杂度都为 O(1) ，例如查找。

我们将具有 随时算出任意位置地址 的存储结构称为 随机存取结构 。

顺序存储结构的插入与删除

对于线性表的顺序存储结构来说，我们要实现 GetElem 操作（将线性表中第 i 个元素的值返回）的方法很简单，只要 i 的数值在数组下标范围内，就是把数组第第 i-1 下标的值返回即可。

例子代码：

# OK 1
# ERROR 0
# TRUE 1
# FALSE 0
typedef int Status;    //Status 是函数的类型，其值是函数结果状态代码，如 OK 等

//初始条件：线性表 L 已存在
Status GetElem (Sqlist L, int i, Elemtype *e){
  //用于判断 L 是否为空表，i 是否在 1~MAXSIZE-1 内
  if(L.length == 0 || i<1 || i>L.length)
    return ERROR;
  *e = L.data[i-1];
  return OK;
}

注意： 要加上判断条件用于检测 L 和 i 是否符合要求 。

线性表的顺序存储结构的插入

插入算法的思路：

如果插入的位置不合理，抛出异常；
如果线性表长度已到最大，则抛出异常或动态增加容量；
从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置；
将要插入元素填入位置 i 处；
线性表长度+1

实现代码如下：

Status ListInsert(SqList *L, int i, Elemtype e){
    if(L->length == MAXSIZE)
        return ERROR;
    if(i < 1 || i>L->length + 1)
        return ERROR;
    if(i <= L->length){
        for(int k = L->length; k >= i-1; k--)
            L->data[k+1] = L->data[k];
    }
    L->data[i-1] = e;
    L->length++;
    return OK;
}

线性表的顺序存储结构的删除

删除算法的思路：

如果删除位置不合理或线性表为空，则抛出异常；
取出删除元素；
从删除元素位置遍历到最后一个元素，分别将其向前移动一个位置；
线性表长度-1

实现代码如下：

Status ListDelete(SqList *L, int i, Elemtype *e){
    if(L->length == 0)
        return ERROR;
    if(i < 1 || i > L->length)
        return ERROR;
    if(i < L->length){
        for(int k = i; k < L->length; k++)
            L->data[k-1] = L->data[k];
    }
    L->length--;
    return OK;
}

线性表顺序存储结构的优缺点

时间复杂度： 查找操作为 O(1) ，删除和查找为 O(n)

其中造成存储空间的“碎片”指的是，当线性表长度小于数组长度时，会造成存储空间的浪费。

线性表的链式存储结构

由于线性表的顺序存储结构在进行删除和插入操作时，往往需要花费大量时间。所以可以采用线性表的链式存储结构来解决这一问题。

线性表的链式存储结构： 用一组任意的存储单元存储线性表的数据元素，且数据元素是一对一的关系， 其中存储单元可以是连续的，也可以是不连续的 。

为了表示每个数据元素 a_i 与其直接后继元素 a_i+1 之间的线性逻辑关系，数据元素 a_i 除了要存储自身的数据 data 外，还要存储其直接后继数据元素的位置（比如地址）。我们把存储数据的域称为 数据域 ，并把存储直接后继元素的位置的域称为 指针域 。其中存储的位置信息称为 指针或链 。这两部分信息组成的数据元素 a_i 被称为 结点（Node） 。

n 个结点链结成一个链表，即为线性表的链式存储结构。因为此链表的每个结点中只包含一个指向直接后继元素的指针域，所以叫做 单链表 。

头指针： 链表中第一个结点的存储位置。
注意头指针不是第一个结点的指针域。

程序员一般约定线性链表的最后一个结点的指针域为空（也就是值为 NULL ）

注意头指针和第一个结点的关系

为了方便和统一对链表进行操作，一般 会在单链表的第一个结点前附设一个结点，称为头结点 ，但头结点并不是链表的必须要素。

头结点的数据域可以不存储任何数据，也可以存储线性表的长度之类等附加信息。头结点的指针域存储着头指针。

若链表有头结点，那么头指针指向的则是头结点。

头指针与头结点的区别

若线性表为空表，则头结点的指针域为空，值为 NULL 。

在 C 中的单链表代码描述如下：

typedef struct Node{
    Elemtype data;    //data 存储 Elemtype 类型的数据元素 
    struct Node* next;    //next 存储直接后继元素的位置
}Node, *LinkList;

单链表的读取

注意：该链表具有头结点

获取链表第 i 个数据元素的算法思路：

声明一个结点指针 p 指向链表第一个结点，初始化 j 从 1 开始；
当 j < i 时，就遍历链表，让 p 向后移动，不断指向下一结点， j 不断递增1；
若到链表末尾 p 值为 NULL ，则说明第 i 个元素不存在；
否则查找成功，返回结点指针 p 指向的结点的数据 p->data

单链表的插入和删除

注意：该链表具有头结点

单链表第 i 个数据插入结点的算法思路：

声明一结点指针 p 指向链表第一个结点，初始化 j 为1；
当 j < i 时，就遍历链表，让 p 向后移动，沿着链不断指向下一结点，j 递增1；
若到链表末尾 p 为空，则说明第 i 个元素不存在， return ERROR。或者当 i 为0或负数时， return ERROR ；
否则查找成功，并在系统中通过生成一个空结点 s ；
将数据元素 e 赋值给 s->data ；
单链表的插入标准语句： s->next = p->next; p->next = s ；
return OK;

实现代码如下：

Status ListInsert(LinkList *L, int i, Elemtype e){
    int j = 1;
    LinkList s, p = *L;
    while(p && j < i){
        p = p->next;
        j++;
    }
    if(!p || j > i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

虽然这里用到了指向指向链表的指针的指针 L ，但是其实没必要，因为我们并没有修改 L 的值。

插入的示意图

单链表第 i 个数据插入结点的算法思路：

声明一个结点 p 指向链表的第一个结点，初始化 j 为1；
当 j < i 时，就遍历链表，让 p 的向后移动，不断指向下一个结点，j 不断递增 1 ；
若到链表末尾 p 为空，则说明第 i 个元素不存在， return ERROR。或者当 i 为0或负数时， return ERROR ；
否则查找成功，将要删除的结点 p->next 赋值给 q ；
单链表的删除标准语句： p->next = q->next;
将结点 q 中的数据赋值给 e 用于返回；
释放 q 结点；
return OK;

实现代码如下：

Status ListDelete(LinkList *L, int i, Elemtype *e){
    int j = 1;
    LinkList p = *L;
    while(p->next && j < i){
        p = p->next;
        j++;
    }
    if(!(p->next) || j > i)
        return ERROR;
    LinkList q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

对于单链表来说，删除和插入的时间复杂度都是 O(n) 。但是在删除和插入频率高的情况下，单链表的效率会比顺序存储结构要高很多。 假设要在第 i 个数据元素插入10个元素，单链表只需要找到并通过赋值每次移动两次结点的指针域，而顺序存储结构需要每次移动后面全部的数据元素。

单链表的创建

单链表的创建的算法思路：

声明一个结点 p 和计数器变量 i ；
初始化一空链表；
让 L 的头结点的指针指向 NULL ，即建立一个带头结点的单链表；
循环以下步骤：①生成一新结点赋值给 p ②令每一个数据元素的 data 都为 0 ③将 p 插入到头结点与前一新结点之间

实现代码如下：

void CreateListHead(LinkList *L, int n){
    LinkList p;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for(int i = 0; i < n; i++){
        p = (LinkList)malloc(sizeof(Node));
        p->data = 0;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

我们在这里采用了头插法来插入新结点。 头插法 是指始终让新结点位于数据元素的第一位，当有头结点时，新结点从紧跟着头结点后的位置插入。

头插法示意图

当然，我们也可以采用尾插法。 尾插法 指的是每次都把新结点插到终端结点的后面。

实现代码如下：

void CreateListHead(LinkList *L, int n){
    LinkList p, r;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    r = *L;  // r 指向终端结点
    for(int i = 0; i < n; i++){
        p = (LinkList)malloc(sizeof(Node));
        p->data = 0;
        r->next = p;
        r = p;
    }
    r->next = NULL;  //让终端结点的指针域为空
}

关于 r->next = p; 和 r = p; 的示意图

最后将终端结点的指针域置空。

单链表的整表删除

单链表的整表删除的算法思路如下：

声明一结点指针 p 和 q；
将第一个结点的地址赋值给 p ；
循环：①将下一结点赋值给 p ②释放 p ③将 q 赋值给 p

实现代码如下：

Status ClearList(LinkList *L){
    LinkList p, q;
    p = (*L)->next;
    while(p){
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

这里最后得到的是空表，如果不想使用这个空表，只需要再把头指针指向的空间释放即可。

单链表与顺序存储结构的优缺点

静态链表

静态链表（游标实现法）： 就是通过 用数组替代指针来描述链表 ，让数组的元素具有两个数据域—— data 和 cur 。其中 data 存储数据元素， cur 相当于链表的 next ，存储该元素的直接后继元素在数组中的下标。

同时，为了方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以便于插入而不溢出。

静态链表的实现代码：

#define MAXSIZE 1000
typedef struct {
    Elemtype data;
    int cur;    //游标（cursor），为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

其中，我们要把数组 StaticLinkList 中的 首尾两元素作为特殊元素处理，不存数据元素 。
我们通常将 StaticLinkList 中尚未使用的数组元素称为 备用链表 。而数组中第一个元素（即下标为0）的 cur 就存放备用链表的第一个结点的下标；而数组的最后一个元素的 cur 则存放第一个有数据元素的元素的下标，相当于单链表中的头结点。所以，当整个静态链表为空表时，则为 0² 。

初始化静态链表的代码实现如下：

Status InitList(StaticLinkList space){
    for(int i = 0; i < MAXSIZE; i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;
    return OK;
}

其中， 静态链表最后一个存放数据元素的元素的 cur 的值为0 ，表示下一位置数据为空，相当于 NULL 。

当静态链表的备用链表为空时，数组的首元素的 cur 的值为0。

例子

静态链表的插入与删除

为了辨明数组 StaticLinkList 中有哪些分量未被使用，解决的方法是将所有未被使用过的以及已经被删除的分量用游标链成一个备用的链表 ，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

取得备用链表上第一个新结点的游标 的代码实现：

//若备用链表非空，则返回备用链表分配的结点下标，否则返回 0 
int Malloc_SLL(StaticLinkList space){
    int i = space[0].cur;
    if(space[0].cur)
        space[0].cur = space[i].cur;
    return i;
}

其中 space[0].cur = space[i].cur; 表示将下一个新结点作为备用链表的表头。

静态链表的数据元素个数获取 的代码实现：

//初始条件： L 的已存在
int ListLength(StaticLinkList L){
    int j = 0, i = L[MAXSIZE-1].cur;
    while(i){
        i = L[i].cur;
        j++;
    }
    return j;
}
//操作结果：返回 L 中数据元素的个数

静态链表的插入算法 的代码实现：

//在 L 中第 i 个元素的位置插入新的数据元素 e
Status ListInsert(StaticLinkList L,int i, Elemtype e){
    int k = MAXSIZE - 1;
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
    int j = Malloc_SLL(L);
    if(j){
        L[j].data = e;
        for(int l = 1; l <= i-1; l++)
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

静态链表的删除算法 代码实现：

//删除在 L 中第 i 个数据元素
Status ListDelete(StaticLinkList L, int i){
    int k = MAXSIZE - 1;
    if(i < 1 || i > ListLength(L))
        return ERROR;
    for(int j = 1; j <= i-1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L, j);
    return OK;
}

//回收下标为 k 的空闲结点到备用链表里
void Free_SSL(StaticLinkList space, int k){
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

静态链表的优缺点：

优点

在插入和删除操作时，只需要修改游标，不需要移动元素，改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。

缺点

没有解决连续存储分配(数组)带来的表长难以确定的问题。

失去了顺序存储结构随机存取的特性

循环链表

循环列表（circular linked list）： 只要将单链表中终端结点的指针域由空指针改为指向头结点 ，就可以使得整个单链表形成一个环，这种头尾相连的单链表被称为单循环链表，简称循环列表。

同样的，为了使得循环列表的空链表和非空链表的操作统一，我们可以像单链表一样设置一个头结点，但同样的，头结点对于循环链表并不是必需的。

循环链表的空表

循环链表的非空表

对于有头结点的循环链表，判断非空的条件为： p->next != p 为真，则循环列表非空，反之为空。

对于这样的循环链表，我们只需要 O(1) 的时间即可访问到头结点和第一个元素。然后我们将头指针修改为指向终端元素的指针，就可以只需要 O(1) 的时间即可访问到头结点和第一个元素，以及终端结点。

头指针指向终端结点的循环链表

当头指针指向终端结点时，要将两循环链表合并，操作会方便很多。

头指针指向终端结点的循环链表的合并操作 代码实现：

p = rearA->next;
q = rearB->next;
rearA->next = rearB->next-next;
rearB->next = p;
free(q);

双向链表

双向链表（double linked list）： 是指在单链表的每个结点中再设置一个指针域，用于指向其直接前驱元素。

双向链表的代码实现如下：

typedef struct DulNode{
    Elemtype data;
    struct DulNode *next;    //直接后继
    struct DulNode *prior;    //直接前驱
}DulNode, *DulNodeList;

同样地，双向链表也有循环链表。

相比于单链表，双向链表多了反向遍历的操作。不过插入和删除的代码复杂度会高一些。

双向链表插入算法的代码实现如下：

//假设 s 是要插入的结点的地址
s->prior = p;
s->next = p->next;
s->next->prior = s;
p->next = s;

插入

双向链表删除算法的代码实现如下：

//假设 s 是要删除的结点的地址
s->prior->next = s->next;
s->next->prior = s->prior;
free(s);

删除

3.线性表

3.线性表

线性表

线性表的定义

线性表的抽象数据类型

线性表的顺序存储结构

顺序存储结构的插入与删除

线性表的顺序存储结构的插入

线性表的顺序存储结构的删除

线性表顺序存储结构的优缺点

线性表的链式存储结构

单链表的读取

单链表的插入和删除

单链表的创建

单链表的整表删除

单链表与顺序存储结构的优缺点

静态链表

静态链表的插入与删除

循环链表

双向链表