大话数据结构3-链表

发表于 2020-10-22 更新于 2021-01-10 分类于 1- 编程相关，数据结构与算法阅读次数： Valine：

除了使用线性存储结构外，还可以使用链式结构存储线性表。链表的思想就是不再固定元素的位置，而是让每个元素知道它的上一个元素和下一个元素分别在哪里，也就是每个元素不仅存储数据信息，还存储地址信息。我们把存储数据元素信息的域称为 数据域，存储指针元素的域称为 指针域，指针域中存储的信息称为指针或者链，数据域与指针域结合，称为结点（Node）。

I 单链表简介

如果每个链表的结点中只包含一个指向下个元素的指针，我们称之为 单链表。单链表的第一个结点前常附设一个 头结点，头结点数据域不存储信息或者存放线性表的长度等附加信息，头结点的指针域中存放指向第一个结点指针。此外，单链表的最后一个结点的指针域内容为 “NULL”。

注意，头指针是指向链表的第一个结点的指针，若链表有头结点，则头指针指向头结点。头指针具有标识作用，常用头指针冠以链表的名字。无论链表是否为空，头指针不为空，他是链表的必要元素。

而 头结点 是为了操作方便而设立的，它可以使得在第一个元素结点前插入结点和删除第一个结点的操作与其他结点统一。但头结点不是链表的必备要素。

使用C语言描述单链表结构(对象的属性Properties)：

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;

II 单链表的读取

获取第i个数据的算法思路：

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

Status GetElem(LinkList L, int i, ElemType *e){
    int j;
    LinkList p;  //声明一个结点 p
    p = L->next;    //让p指向L 的第一个结点
    j = 1;

    while(p && j < i){
        p = p->next;
        ++j;
    }
    if (!p || j>i)  //p为 null 或者 j>i. 输入不合法（i<1）或者i太大
        return ERROR;   
    
    *e = p->data;

    return OK;
}

Note: ++j 与 j++ 的区别。前一个是先执行再判断，后一个是先判断再执行。

III 单链表的插入与删除

单链表的插入只需要更改两个元素的指针域的内容即可。具体的算法步骤思路如下：

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

代码如下：

Status ListInsert(LinkList *L, int i, ElemType e){
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while(p && j < i){
        p = p->next;
        ++j;
    }

    if (!p || j > i )   //数据输入错误，either i 太小 or 太大
        return ERROR;

    s = (LinkList)malloc(sizeof(Node) );    //生成新结点
    s->data = e;
    s->next = p->next;
    p->next = s;

    return OK;
}

类似的，单链表的删除操作也只要操作待删除结点及其关联结点。操作思路为：

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

Status ListDelete(LinkList *L, int i, ElemType *e){
    int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while( p->next && j < i){      //遍历，首先找到需要删除的结点
        p = p->next;
        ++j;
    }

    if (!(p->next) || j > i )   //数据输入错误，either i 太小 or 太大
        return ERROR;

    q = p->next;        //删除及释放内存
    p->next = q->next;
    *e = q->data;
    free(q);

    return OK;
}

Remark：

注意是 while(p->next && j < i), 即找到的p结点的下一个不为空，因为要删除的是p结点的下一个元素。
有点奇怪的是，q->next 即 ->next 里的东西，（seems是地址域）既可以赋值给 LinkList 对象（q）, 也可以赋值给 LinkList 对象的 ->next (地址域)；
删除元素后，要回收空间。

如果需要增删多个元素，或者频繁增删操作，单链表的效率优势明显。

IV 单链表的创建

单链表的存储空间可以很散，每个链表的存储空间不需要预先分配。单链表的创建可以分为两种方式，1- 从头部开始创建；2- 从尾部开始创建。下面，我们分别进行展示。

头插法

直接上代码：

void CreateListHead (LinkList *L, int n){
    LinkList p;
    int i;
    srand(time(0));     //初始化随机数种子
    *L = (LinkList)malloc(sizeof(Node));    //为链表的头结点分配存储空间
    (*L)->next = NULL;
    for (i = 0; i < n; i++){
        p = (LinkList)malloc(sizeof(Node));     //生成新结点
        p->data = rand()%100 + 1;       //随机生成100以内的数字
        p->next = (*L)->next;       //新生成的结点指向原先的第一个元素
        (*L)->next = p;         //让头结点指向新生成的结点p
    }
}

尾插法

void CreateListTail (LinkList *L, int n){       //创建长度为n的新的链表
    LinkList p,r;
    int i;
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));    //为链表的头结点分配空间
    r = *L;                               //r为指向尾部的结点
    for(i = 0; i < n; i++){
        p = (Node *)malloc(sizeof(Node));   //生成新的结点
        p->data = rand()%100 + 1;
        r->next = p;        //p放在 r 的下一个元素，也就是p现在变为了最后一个结点
        r = p;              //重新让 r 变为最后一个结点
    }
    r->next = NULL;     //循环结束，让最后一个指针指向空
}

Note:

(C语法)需要注意，L 是指整个单链表，而 头插法 中的 p 和 尾插法 中的 p,r 都是指向某个结点的变量。
尾插法一定要注意，在最后的时候要让尾部的结点指向 NULL，以便遍历的时候可以通过这个确认链表到达了结尾。

V 单链表的整表删除

当我们不再需要使用一个链表，我们需要对该链表中每个元素所使用的空间（内存）进行释放。

Status ClearList (LinkList *L){
    LinkList p,q;
    p = (*L)->next;     //让p指向第一个结点
    
    while(p){       //如果不是NULL，说明没有到达链表尾部
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;      //删除完链表后，让头结点的指针为空
    return OK;
}

Remark：

这里必须引入一个暂存变量，因为将链表中元素释放掉之后，就无法读取它的下一个元素了。

VI 线性表的优缺点

从下面几个方式比较线性表的优缺点：

由于单链表的存储方式更加自由，不需要分配存储空间，因此避免了顺序存储结构需要预先分配存储空间的尴尬：大了浪费，小了容易发生溢出；
时间性能上，单链表的查找的时间复杂度为 $O(n)$,相较于顺序存储结构$O(1)$成本更高。但其插入和删除操作在找到需要增删的位置后，时间复杂度仅为 $O(1)$, 比顺序结构时间成本低。

VII 单链表的拓展

静态链表

C 语言可以使用指针来简单的实现链表，对于java 等高级语言，则是通过对象引用的机制来实现。而对于一些早起语言，例如 Basic, Fortran，由于不具备上述两者的功能，则使用数组来描述链表，称之为静态链表。对于静态链表，数组的每个下标都对应一个 data 和一个 cur，data 为数据域用来存放元素；cur 为游标相当于单链表中的 next 指针。

循环链表

将单链表的终端结点指针由空指针改为指向头结点，就使整个单链表形成一个环，称为循环链表（circular linked list）。它的好处是从链表中的任何一个点出发，都可以访问到链表中的全部结点。

双向链表

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

typedef struct DuLNode{
    ElemType data;
    struct DuLNode *prior;      //直接前驱指针
    struct DuLNode *next;       //直接后驱指针
} DuLNode, * DuLinkList;

双向链表方便了查询操作，但是在插入删除元素时，需要增加处理前驱指针的代码。