1.单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据。链表中的数据是以节点来表示的，每个节点由元素和指针构成，元素就是存储数据的存储单元，指针就是连接每个元素的地址数据。在单链表中指针只指向他的后继节点。

2.单链表的实现

2.1 定义一些辅助元素

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

2.2 设计单链表的节点

节点.png
由上图可知一个单链表的节点由元素(数据域)和指针（指针域）两个部分组成，元素存储数据，指针存储该节点指向的下一个节点的地址数据。

实现代码：

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

2.3 设计一个单链表

单链表.png
带头结点的单链表

一个单链表的基本结构可以由上图所示。在设计单链表的时候我们可以给单链表初始化一个头结点，头结点不存储数据，可以存储一些辅助信息，例如链表的长度。头结点的指针域可以指向首元节点，在后续的链表增删的时候会很方便，不用修改首指针所指向的地址。便于空表和非空表的处理。

初始化单链表的代码实现：

/// 初始化一个带头结点的单链表
/// @param L 单链表
Status InitLinkList(LinkList *L){
    // 分配内存
    *L = (LinkList)malloc(sizeof(Node));
    // 分配失败，报错
    if (*L==NULL) { return ERROR; }
    // 头结点指针置空
    (*L)->next = NULL;
    
    return OK;
}

2.4 遍历打印单链表

代码实现：

void PrintLinkList(LinkList L){
    LinkList p = L->next;
    // 判断一下首元节点是否有值，有值在遍历打印
    if (p == NULL) { return; }
    while (p) {
        printf("该节点的值是：%d\n",p->data);
        p = p->next;
    }
}

2.5 指定位置插入新节点

由于我们引入了头结点的概念，所以插入变的相对简单，不用在插入第一个位置的时候修改链表起始位置的指针。

插入新节点.png

核心算法：

• 1.找到要插入位置的前一个节点
• 2.将新节点的next指向前一个节点的next
• 3.将前一个节点的next指向新节点

实现代码：

/// 在指定位置插入新节点
/// @param L 单链表
/// @param location 位置
/// @param e 新节点的数据
Status InsertLinkList(LinkList *L, int location, ElemType e){
    //取出头节点的指针
    LinkList p = *L;
    // 记录位置的中间变量
    int j = 1;
    // 如果指针一直有值就可以继续寻找，直到找到要插入的位置的前一个节点
    while (p && j<location) {
        p = p->next;
        j++;
    }
    // p为NULL或者位置的值大于要插入的位置则直接报错
    if (!p || j>location) { return ERROR; }
    // 创建要插入的节点
    LinkList new = (LinkList)malloc(sizeof(Node));
    new->data = e;
    new->next = p->next;
    // 前一个位置的next指向新的
    p->next = new;
    
    return OK;
}

2.6 根据指定位置获取元素

这个查找没什么难的，由于我们引入了头结点，遍历可以从1开始，找到要找的位置返回该节点的值即可。相关容错处理在代码中可见。
实现代码：

/// 根据指定位置获取元素
/// @param L 链表
/// @param location 位置
/// @param e 取到的值
Status GetElemFromList(LinkList L, int location, ElemType *e) {
    
    // 初始化一些临时变量
    LinkList p = L->next;
    int j = 1;
    // 查找要取值得位置
    while (p && j<location) {
        p = p->next;
        j++;
    }
    // 没取到或者位置不合法就报错
    if (!p || j>location) { return ERROR; }
    // 返回取到的值
    *e = p->data;
    
    return OK;
}

2.7 根据指定位置删除节点

由于引入了头结点的概念，我们从头结点开始就是可能待删除节点的前驱，一直遍历查找到前一个几点。

删除指定位置的节点.png

核心算法：

• 1.找到待删除位置的前一个节点
• 2.将前一个节点的next指向待删除节点的next
• 3.释放待删除节点的内存
  实现代码：

/// 删除指定位置的节点
/// @param L 链表
/// @param location 位置
/// @param e 返回删除的数据
Status DeleteLinkList(LinkList *L, int location, ElemType *e){
    
    // 初始化一些辅助变量
    LinkList p = (*L);
    LinkList q;
    // 要找要删除节点的前一个节点，所以从0开始，如果要删除首元节点的时候，其实他的前一个节点是头结点（辅助节点）
    int j = 0;
    
    // 查找要删除节点的前一个节点
    while (p->next && j<(location-1)) {
        p = p->next;
        j++;
    }
    // 没找到要删除的节点，或者位置非法就报错
    if (!p->next && j>(location-1)) { return ERROR; }
    
    // 临时存放要删除的节点
    q = p->next;
    // 要删除的前一个节点的next指向要删除节点的next
    p->next = q->next;
    // 返回删除的数据
    *e = q->data;
    // 释放节点内存
    free(q);
    
    return OK;
}

2.8 清空链表

清空主要是把链表恢复到初始状态，删除所有的除去头节点的节点，并把头结点的next置为NULL。

/// 清空单链表
/// @param L 单链表
Status ClearLinkList(LinkList *L){
    // 找到第一个节点
    LinkList p = (*L)->next;
    // 头结点的next置空
    (*L)->next = NULL;
    // 辅助节点
    LinkList q;
    // 循环遍历清空
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }

    return OK;
}

2.9 单链表头插法

头插法，顾名思义，就是一直在最前面插入数据，所以如果一组有序的数据插入完成后就是倒序的。
核心算法：

• 1.将新节点的next指向头结点的next
• 2.将头结点的next指向新节点

实现代码：

/// 创建单链表，头插法
/// @param L 链表
/// @param n 初始长度
void CreateLinkListHeader(LinkList *L, int n) {
    // 分配内存
    *L = (LinkList)malloc(sizeof(Node));
    // 头结点指针置空
    (*L)->next = NULL;
    
    LinkList p;
    for (int i = 1; i<=n; i++) {
        // 创建新节点
        p = (LinkList)malloc(sizeof(Node));
        // 新节点赋值
        p->data = i;
        //新节点的next指向头结点的next
        p->next = (*L)->next;
        // 头结点的next指向新节点
        (*L)->next = p;
    }
}

2.9 单链表尾插法

跟头插法一样，尾插法就是将新数据一直插入到单链表的尾部，所以如果一组有序的数据插入完成后就是正序的。
核心算法：

• 1.开辟一个辅助节点，不断存储新的尾节点初始化为头结点
• 2.将辅助节点的next指向新节点
• 3.将新节点赋值给辅助节点

实现代码：

/// 尾插法
/// @param L 链表
/// @param n 长度
void CreateLinkListTail(LinkList *L, int n) {
    // 分配内存
    *L = (LinkList)malloc(sizeof(Node));
    // 头结点指针置空
    (*L)->next = NULL;
    LinkList p,r;
    r = *L;
    for (int i = 1; i<=n; i++) {
        // 创建新节点
        p = (LinkList)malloc(sizeof(Node));
        // 新节点赋值
        p->data = i;
        // 新节点的next为NULL
        p->next = NULL;
        // 辅助节点的next指向新节点
        r->next = p;
        // 将新节点赋值给辅助节点
        r = p;
    }
}