【数据结构】线性表之单链表

完整代码需结合前面一篇顺序表数据结构学习-线性表之顺序表各种操作
网易云课堂小甲鱼课程链接：数据结构与算法

线性表的链式存储结构

线性表的顺序存储结构，最大的缺点就是插入和删除时需要移动大量的元素，这显然需要耗费时间。导致这个问题的原因是在于相邻元素的存储位置具有邻居关系，它们在内存中的位置是紧挨着的，中间没有间隙，当然无法快速插入和删除。

定义

• 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表中的数据元素，这组存储单元可以存放在内存中未被占用的任意位置。
• 相比顺序存储结构，链式存储结构中，除了需要存储数据元素信息之外，还需要存储它的后继元素的存储地址(指针)。
• 数据域：存储数据元素信息的域，指针域：存储直接后继位置的域。指针域中存储的信息成为指针或链。这两部分信息组成数据元素成为存储映像，成为结点(Node)。
  结点结构node
• 链式结构：n个结点链接成一个链表，即为线性表(a1,a2,a3,...an)；
• 如果链表的每个结点中只包含一个指针域，那就叫做单链表。

单链表

小甲鱼视屏中的单链表

• 头指针：链表中的第一个结点的存储位置。
• 线性表中最后一个结点的指针域为空(NULL)。

• 看图说明:

  
  单链表的特点

头结点和头指针

• 头结点：

  • 头结点是加在单链表之前附设的一个头结点。
  • 头结点的数据域一般不存储任何信息，也可以存放一些关于线性表的长度的附加信息。
  • 头结点的指针域存放指向第一个结点的指针(即第一个结点的存储位置)。
  • 头结点不一定是链表的必要元素。

• 头指针：

  • 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
  • 头指针具有标识作用，所以常用头指针冠以链表的名字(指针变量的名字)。
  • 无论链表是否为空，头指针均不为空。

  • 头指针是链表的必要元素。

    
    

单链表的代码实现

#include <stdio.h>
#define OK 1;
#define ERROR 0;
#define TRUE 1;
#define FALSE 0;
#define MAXSIZE 20  /* 定义线性表可能达到的最大长度 */
typedef int  ElemType; /*  定义数据元素类型，类型名为ElemType，此处所定义的数据元素只包含一个int型的数据项*/
typedef struct { /* 定义顺序表类型，类型名为SqList,包含两个数据项：数组data,用于存放数据元素，整数length表示线性表当前长度*/
    
    ElemType data[MAXSIZE];   /*定义线性表占用的数组空间*/
    int length;         /*线性表当前长度*/
    
}SqList;

typedef int Status; /*Status是函数的类型，其值是函数结果状态码，如OK等*/

// 用结构指针描述单链表
typedef struct Node{
    
    ElemType data;  // 数据域
    struct Node *Next; // 指针域
    
}Node;

// 取别名
typedef struct Node *LinkList;

通过这种链式存储方式，若果p->data=ai,那么p->next->data=ai+1.

单链表的读取（工作指针后移）

• 获取链表第i个数据的算法思路：
  1.声明一个结点p指向链表的第一个结点，初始化j从1开始；
  2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j+1；
  3.若到链表末尾p为空，则说明第i个元素不存在；
  4.否则查找成功，返回结点p数据。
• 代码：

/**
 * 获取链表第`i`个数据的
 */
Status GetElem(LinkList L, int i, ElemType *e){
    
    int j;
    LinkList p;  // 声明指针p
    
    p = L->next;  // p指向链表L的第一个结点
    j = 1;      // 当前位置计数器设置为1
    
    while (p && j<i) {  // 当p不为空 切j<i时候 j继续向后找
        
        p = p->next;
        j++;
    }
    
    if (!p || j>i) return ERROR;  // 到达结尾且没找到
    
    *e = p->data;  // 获取倒找的结果
    
    return OK;
}

单链表的插入算法

• 算法思路：
  1.声明一结点p指向链表头结点，初始化j从1开始；
  2.当j<1时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1；
  3.若到链表末尾p为空，则说明第i个元素不存在；
  4.否则查找成功，在系统中生成一个空节点s;
  5.将数据元素e赋值给s->data；
  6.利用单链表插入语句插入:s->next = p->next; p->next = s;;
  7.返回成功。
• 代码：

/**
 * 单链表的插入
 */
Status ListInsert(LinkList *L, int i, ElemType e){
    
    int j;
    LinkList p,s;
    
    p = *L;
    j = 1;
    
    while (p && j<i) {  // 用于寻找第i个结点
        
        p = p->next;
        j++;
    }
    
    if (!p || j>i) return ERROR;  // 到达结尾且没找到
    
    s = (LinkList)malloc(sizeof(Node));  //生成一个空节点s
    
    // 插入语句
    s->next = p->next;
    p->next = s;
    
    return OK;
}

单链表的删除算法(前继结点的指针绕过绕过后继结点)

• 算法实现思路：p->next = p->next->next,即 q = p->next; p->next = q->next
  1.声明一结点p指向链表头结点，初始化j从1开始；
  2.当j<1时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1；
  3.若到链表末尾p为空，则说明第i个元素不存在；
  4.否则查找成功，将欲删除结点p->next赋值给q；
  5.单链表的删除标准语句：p->next = q->next;
  6.将结点中的数据赋值给e，作为返回；
  7.释放q结点。
• 代码：

/**
 * 单链表的删除
 */
Status ListDelete(LinkList *L, int i, ElemType e){
    
    int j;
    LinkList p,q;
    
    p = *L;
    j = 1;
    
    while (p && j<i) {  // 用于寻找第i个结点
        
        p = p->next;
        j++;
    }
    
    if (!p || j>i) return ERROR;  // 到达结尾且没找到
    
    q = p->next;
    
    // 删除语句
    p->next = q->next;
    free(q);
    
    return OK;
}

单链表的插入和删除图解
特点：先找到，再删除或者增加。时间复杂度为o(1);

单链表的整表创建

对于顺序存储结构的线性表的整表创建，可以用数组的初始化来直观理解。
但是对于单链表，和顺序存储结构就不一样，不像顺序存储结构数据这么几种，它的数据可以是分散在各个角落的，增长也是动态的。
对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需要及时生成。

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

1.声明一个结点p和计数器变量i;
2.初始化一个空链表L；
3.让L的头结点的指针指向NULL,即建立一个带头结点的单链表；
4.循环实现后继结点的赋值和插入。

一、头插法建立单链表

头插法从一个空表开始，生成新结点，读取数据存放到新节点的数据域中，然后将新结点插入到当前链表的表头，知道结束。

简单来说，就是把新加进的元素放在表头的第一个位置(如同插队)：

• 先让新节点的next指向头结点之后；

• 让后让表头的next指向新节点。

• 代码：

/**
 * 头插法
 */
void CreatListHead(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;
        p->next = (*L)->next;
        (*L)->next = p;
        
    }
}

这里使用了c语言里面的生成随机数的函数rand()来构造结点里面的数据。

二、尾插法建立单链表

头插法建立链表随让算法简单，但是生成的链表中结点的次序和输入的顺序相反。
若把新结点都插入到最后，那么这种算法就是尾插法。

• 代码：

/**
 * 尾插法
 */
void CreatListTail(LinkList *L, int n){
    
    LinkList p, r;
    int i;
    
    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));
    r = *L;
    
    for (i = 0; i < n; i++) {
        
        p = (Node *)malloc(sizeof(Node));
        p->data = rand()%100+1;
        r->next = p;
        r = p;
    }
    
    r->next = NULL;
}

尾插法图解

单链表的整表删除

• 单链表的整表删除的算法思路：
  1.声明结点p和q;
  2.将第一个结点赋值给p，下一结点赋值给q；
  3.循环执行释放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;
}

注意：整表删除的时候，需要一个个结点的删除。

单链表结构和顺序存储结构对比

存储分配方式：

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素；
• 单链表采用链式存储结构，用一组任意的储存单元存放线性表的元素；

时间性能：

• 查找：
  • 顺醋存储结构O(1);
  • 单链表O(n);
• 插入和删除：
  • 顺序存储结构需要平均移动表长一般的元素，时间为O(n)；
  • 单链表在计算机处某位置的指针后，插入和删除时间为O(1);

空间性能

• 顺序存储结构需要预分配存储空间，分大了，容易造成空间浪费，分小了，容易发生溢出。
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。