数据结构之单链表的实现

　　在上一节：数据结构之顺序表

　　我们提到了顺序表的一些缺陷，那有没有什么数据结构可以减少这些问题呢？

　　答案自然就是今天我们所要说的链表。

本节大纲：

链表的概念与结构
单链表的实现
完整代码展示

一.链表的概念与结构

1.概念

　　链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

2.结构及种类

　　链表有好多种：单双向链表，带头不带头链表，循环非循环链表；它们两两组合可以组成 8 种链表结构，如下图所示：

数据结构之单链表的实现-LMLPHP

　　链表又包括 数据域 和 指针域。

数据结构之单链表的实现-LMLPHP

　虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

数据结构之单链表的实现-LMLPHP

　　1. 无头单向非循环链表：

　　　　结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

　　　　另外这种结构在笔试面试中出现很多。

　　2. 带头双向循环链表：

　　　　结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。

　　　　另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

　　所以我们今天从 无头单向非循环链表 开始：

三.单链表的实现

1.自定义数据类型

　　首先我们肯定要先创建一个自定义数据类型：

//进行自定义类型，方便修改
typedef int DataType;

//进行自定义数据类型
typedef struct SLTNode
{
    DataType data;//存放数据
    struct SLTNode* next;//指向下一块空间
}SLTNode;

2.打印函数

　　假设我们现在有一个数据完全的单链表，但是我们想在看到它的值，这时就需要一个打印函数了。

　　现在我们来想一想我们刚刚所提到的单链表结构，它是由数据域和指针域组合而成，而它中的指针指向的是下一块储存空间，如果该指针为NULL，就说明该链表已结束。

//单链表打印函数
void SLTPrint(SLTNode *p)
{
    if (p == NULL)//如果该链表为空
    {
        printf("该链表中并无值可供打印\n");
        return;//直接退出
    }
    //正常情况下

    //cur指向当前位置
    SLTNode *cur = p;
    while (cur)//如果cur是NULL，循环就停止
    {
        printf("%d -> ", cur->data);
        cur = cur->next;//cur指向下一块空间
    }
    printf("NULL\n");
}

　　在这会有一些人问：while 中的判断条件是否可以写为 cur->next ，我们来看一下: 数据结构之单链表的实现-LMLPHP

　　从上图中，我们可以明显看出：若循环条件为 cur->next ,这样循环到达最后一个节点就退出了，最后一个节点内的值并未打印，当然要是你在循环结束后，再加一句printf，那自然也没错

3.创建节点函数：

　　因后面的头插、尾插、任意位置插入，都需要去创建节点，所以在这就把它单独列一个模块：

//创建节点函数
SLTNode *BuySLTNode(DataType data)
{
    //动态开辟一块空间
    SLTNode *new_node = (SLTNode *) malloc(sizeof(SLTNode));
    if (new_node == NULL)//如果未开辟成功
    {
        perror("BuyNode Error!");//打印错误信息
        exit(-1);
    }
    else
    {
        //新结点的值为传进来的值
        new_node->data = data;
        new_node->next = NULL;
    }
    //返回新建立的节点
    return new_node;
}

4.单链表尾插

　　尾插，我们肯定要先找到该链表的尾，然后将尾的next指向我们新建立的结点，将新节点的next指向NULL；

//单链表尾插函数
void SLTPushBack(SLTNode *p, DataType InsertData)
{
    //创建一个新节点
    SLTNode *new_node = BuySLTNode(InsertData);
    if (p == NULL)//说明该链表为空
    {
        p = new_node;
    }
    else//非空就找尾
    {
        SLTNode *cur = p;
        while (cur->next)//循环遍历找尾，注意在这，我们的循环条件为cur->next，而非cur
            // 因为我们要用最后一个节点的next
            // 否则，若是cur的话，就直接走到NULL了，我们无法给将一个节点加在它上面
        {
            cur = cur->next;//指向下一个
        }
        cur->next = new_node;//尾插
    }
}

　　可是，上面这段代码有没有问题呢？我们来运行一下：

void test1()
{
    SLTNode *p = NULL;
    SLTPushBack(p,0);
    SLTPushBack(p,1);
    SLTPushBack(p,2);
    SLTPushBack(p,3);
    SLTPrint(p);
}

测试代码

数据结构之单链表的实现-LMLPHP

　　我们明明尾插了4次，最后为什么还是无值可供打印呢？我们再来调试一下：

数据结构之单链表的实现-LMLPHP

　　我们发现，它在函数里都换过了，却出了函数又变为了NULL。我们思来想去总觉得这种情形好像在哪见过 --- 哦，原来曾在这个例子中见过：

#include<stdio.h>

void swap(int a, int b)
{
    int c = a;
    a = b;
    b = c;
}

int main()
{
    int a = 2, b = 3;
    printf("before:\na=%d, b=%d\n", a, b);
    swap(a, b);
    printf("after:\na=%d, b=%d\n", a, b);
    return 0;
}

数据结构之单链表的实现-LMLPHP

　　当时，我们便已提到，改变其值时，要传值，但要改变其指向，要传址；

　　在举一个例子：

void change(char *p)
{
    p[0] = '!';
}

void change_2(char **p)
{
    static char *a = "12334";
    *p = a;
}

int main()
{
    char a[] = "dadasfsfa";
    char *p = a;

    //改变指针所指向的值
    change(p);
    printf("%s\n", p);//!adasfsfa

    //改变指针的指向
    change_2(&p);
    printf("%s\n", p);//12334
    return 0;
}

示例

　　所以正确的尾插怎么写呢:

　　　　1.函数参数为STLNode** ,即改为址传递，因为当 p为空的时候，我们需要改变其指向，指向我们新建的new_node

//单链表尾插函数
void SLTPushBack(SLTNode **p, DataType InsertData)
{
    //创建一个新节点
    SLTNode *new_node = BuySLTNode(InsertData);
    if (*p == NULL)//说明该链表为空
    {
        *p = new_node;//改变p的指向
    }
    else//非空就找尾
    {
        SLTNode *cur = *p;
        while (cur->next)//循环遍历找尾，注意在这，我们的循环条件为cur->next，而非cur
            // 因为我们要用最后一个节点的next
            // 否则，若是cur的话，就直接走到NULL了，我们无法给将一个节点加在它上面
        {
            cur = cur->next;//指向下一个
        }
        cur->next = new_node;//尾插
    }
}

5.单链表头插

　　现在有了之前的错误经验，是不是一下就知道这个肯定是传址啊：

//单链表头插函数
void SLTPushFront(SLTNode **p, DataType InsertData)
{
    SLTNode *new_node = BuySLTNode(InsertData);//创建新节点

    //在头插中，并不关心*p为不为空，反正最后它们的处理都是一样的

    //将原链表内容连接在new_node上
    new_node->next = *p;
    //改变指向
    *p = new_node;
}

6.单链表尾删

　　循环遍历找尾，释放，置NULL

//单链表尾删函数
void SLTPopBack(SLTNode **p)
{
    if (*p == NULL)//表示该链表为空
    {
        printf("该链表中并无值可供删除！\n");
        return;
    }
    else if ((*p)->next == NULL)//表示该链表中只有一个值，删除之后就为空
    {
        free(*p);//释放空间
        *p = NULL;//置为NULL；
    }
    else
    {
        //循环遍历找尾
        SLTNode *cur = *p;//指向当前位置
        SLTNode *prev = NULL;//指向前一个位置
        while (cur->next)
        {
            prev = cur;
            cur = cur->next;
        }
        free(cur);//释放空间
        cur = NULL;//及时置NULL
        //删除之后prev便是最后一个节点了
        prev->next = NULL;
    }
}

7.单链表头删

　　释放改指向

//单链表头删函数
void SLTPopFront(SLTNode **p)
{
    if (*p == NULL)//表示该链表为空
    {
        printf("该链表中并无值可供删除！\n");
        return;
    }
    else
    {
        SLTNode* pop_node=*p;//指向头节点
        *p=(*p)->next;//指向下一个元素
        free(pop_node);//释放空间
        pop_node=NULL;//及时置NULL
    }
}

8.单链表查找函数

　　循环遍历

//单链表查找函数
SLTNode *SLTFindNode(SLTNode *p, DataType FindData)
{
    assert(p);//确保传进来的指针不为空
    SLTNode *cur = p;
    while (cur)
    {
        if (cur->data == FindData)
        {
            return cur;//找到就返回该节点的地址
        }
        cur = cur->next;//循环遍历
    }
    return NULL;//找不到就返回NULL
}

9.单链表修改函数

//单链表修改函数
void SLTModify(SLTNode *pos, DataType ModifyData)
{
    assert(pos);//确保pos不为空
    pos->data = ModifyData;//修改
}

10.任意位置插入

　　1.单链表在pos位置之后插入insertdata

//单链表在pos位置之后插入InsertData
void SLTInsertAfter(SLTNode* pos,DataType InsertData)
{
    assert(pos);//保证pos不为NULL
    SLTNode* new_node=BuySLTNode(InsertData);//创建一个新节点
    //该节点的下一个指向原本该位置的下一个
    new_node->next=pos->next;
    //该位置的下一个就是new_node
    pos->next=new_node;
}

　　2.单链表在pos位置之前插入insertdata

　　　　这时就要考虑到若位置是第一个位置时，那就相当于头插了

　　　　此外，我们还得找到它的前一个位置

//单链表在pos位置之前插入InsertData
void SLTInsertBefore(SLTNode **p, SLTNode *pos, DataType InsertData)
{
    assert(pos);
    SLTNode *new_node = BuySLTNode(InsertData);
    if (pos == *p)//这就说明是第一个位置前插入
    {
        //头插
        new_node->next = *p;
        *p = new_node;
    }
    else
    {
        SLTNode *cur = *p;
        SLTNode *prev = NULL;
        //新节点的下一个指向这个位置
        new_node->next = pos;
        //循环遍历找到它的前一个位置
        while (cur != pos)
        {
            prev = cur;
            cur = cur->next;
        }
        //前一个位置指向新节点
        prev->next = new_node;
    }
}

　　　　除此之外，还有哦另外一种方法，可以不用去知道它链表的第一个位置

　　　　我们在传过去的那个位置，来进行一个后插，再交换这两个节点的数据 ，这也是一种方法：

//单链表在pos位置之前插入InsertData
void SLTInsertBefore_2(SLTNode *pos, DataType InsertData)
{
    assert(pos);

    SLTNode *new_node = BuySLTNode(InsertData);
    new_node->next = pos->next;
    pos->next = new_node;
    //进行了一个后插

    //交换这两个变量的值
    DataType tmp = pos->data;
    pos->data = new_node->data;
    new_node->data = tmp;
}

　　如图：

数据结构之单链表的实现-LMLPHP

11.任意位置删除

　　　1.删除pos位后的数据

//删除pos位后的数据
void SLTEraseAfter(SLTNode *pos)
{
    assert(pos);
    if (pos->next == NULL)
    {
        //说明后面并没有元素了
        printf("该位置后无数据可以删除\n");
    }
    else
    {
        //创建一个指针指向下一个位置
        SLTNode *next = pos->next;
        //原位置的下一个位置，指向 下一个位置 的下一个位置
        pos->next = next->next;
        //释放内存
        free(next);
        next = NULL;
    }
}

　　　　2.删除pos位的数据 --- 这就包含了头删

//删除pos位的数据 --- 含有头删
void SLTEraseCur(SLTNode **p, SLTNode *pos)
{
    assert(pos);
    if (*p == pos)
    {
        //说明是头删
        *p = pos->next;
        free(pos);
        pos = NULL;
    }
    else
    {
        //普通位置
        SLTNode *prev = *p;
        SLTNode *cur = *p;
        //找到头一个位置
        while (cur != pos)
        {
            prev = cur;
            cur = cur->next;
        }
        //头一个位置指向下下个位置
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

　　　　3.同样可以用之前所提到的方法进行带有头删的任意位置删除

　　　　　　1.把该位置后一个节点的数据存下；

　　　　　　2.删除该位置后的节点

　　　　　　3.将头节点的值改为之前存下的数据

　　 单链表的实现到这便就结束了

三.完整代码展示

//确保头文件只包含一次
#ifndef FINASLT_SLT_H
#define FINASLT_SLT_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <assert.h>


//进行自定义类型，方便修改
typedef int DataType;

//进行自定义数据类型
typedef struct SLTNode
{
    DataType data;//存放数据
    struct SLTNode *next;//指向下一块空间
} SLTNode;

//单链表打印函数
void SLTPrint(SLTNode *p);

//创建节点函数
SLTNode *BuySLTNode(DataType data);

//单链表尾插函数
void SLTPushBack(SLTNode **p, DataType InsertData);

//单链表头插函数
void SLTPushFront(SLTNode **p, DataType InsertData);

//单链表尾删函数
void SLTPopBack(SLTNode **p);

//单链表头删函数
void SLTPopFront(SLTNode **p);

//单链表查找函数
SLTNode *SLTFindNode(SLTNode *p, DataType FindData);

//单链表修改函数
void SLTModify(SLTNode *pos, DataType ModifyData);

//单链表在pos位置之后插入InsertData
void SLTInsertAfter(SLTNode *pos, DataType InsertData);

//单链表在pos位置之前插入InsertData
void SLTInsertBefore(SLTNode **p, SLTNode *pos, DataType InsertData);


//单链表在pos位置之前插入InsertData
void SLTInsertBefore_2( SLTNode *pos, DataType InsertData);

//删除pos位后的数据
void SLTEraseAfter(SLTNode *pos);

//删除pos位的数据 --- 含有头删
void SLTEraseCur(SLTNode **p, SLTNode *pos);

#endif //FINASLT_SLT_H

SLT.h

#include "SLT.h"

//单链表打印函数
void SLTPrint(SLTNode *p)
{
    if (p == NULL)//如果该链表为空
    {
        printf("该链表中并无值可供打印\n");
        return;//直接退出
    }
    //正常情况下

    //cur指向当前位置
    SLTNode *cur = p;
    while (cur)//如果cur是NULL，循环就停止
    {
        printf("%d -> ", cur->data);
        cur = cur->next;//cur指向下一块空间
    }
    printf("NULL\n");
}

//创建节点函数
SLTNode *BuySLTNode(DataType data)
{
    //动态开辟一块空间
    SLTNode *new_node = (SLTNode *) malloc(sizeof(SLTNode));
    if (new_node == NULL)//如果未开辟成功
    {
        perror("BuyNode Error!");//打印错误信息
        exit(-1);
    }
    else
    {
        //新结点的值为传进来的值
        new_node->data = data;
        new_node->next = NULL;
    }
    //返回新建立的节点
    return new_node;
}

////单链表尾插函数
//void SLTPushBack(SLTNode *p, DataType InsertData)
//{
//    //创建一个新节点
//    SLTNode *new_node = BuySLTNode(InsertData);
//    if (p == NULL)//说明该链表为空
//    {
//        p = new_node;
//    }
//    else//非空就找尾
//    {
//        SLTNode *cur = p;
//        while (cur->next)//循环遍历找尾，注意在这，我们的循环条件为cur->next，而非cur
//            // 因为我们要用最后一个节点的next
//            // 否则，若是cur的话，就直接走到NULL了，我们无法给将一个节点加在它上面
//        {
//            cur = cur->next;//指向下一个
//        }
//        cur->next = new_node;//尾插
//    }
//}

//单链表尾插函数
void SLTPushBack(SLTNode **p, DataType InsertData)
{
    //创建一个新节点
    SLTNode *new_node = BuySLTNode(InsertData);
    if (*p == NULL)//说明该链表为空
    {
        *p = new_node;//改变p的指向
    }
    else//非空就找尾
    {
        SLTNode *cur = *p;
        while (cur->next)//循环遍历找尾，注意在这，我们的循环条件为cur->next，而非cur
            // 因为我们要用最后一个节点的next
            // 否则，若是cur的话，就直接走到NULL了，我们无法给将一个节点加在它上面
        {
            cur = cur->next;//指向下一个
        }
        cur->next = new_node;//尾插
    }
}

//单链表头插函数
void SLTPushFront(SLTNode **p, DataType InsertData)
{
    SLTNode *new_node = BuySLTNode(InsertData);//创建新节点

    //在头插中，并不关心*p为不为空，反正最后它们的处理都是一样的

    //将原链表内容连接在new_node上
    new_node->next = *p;
    //改变指向
    *p = new_node;
}

//单链表尾删函数
void SLTPopBack(SLTNode **p)
{
    if (*p == NULL)//表示该链表为空
    {
        printf("该链表中并无值可供删除！\n");
        return;
    }
    else if ((*p)->next == NULL)//表示该链表中只有一个值，删除之后就为空
    {
        free(*p);//释放空间
        *p = NULL;//置为NULL；
    }
    else
    {
        //循环遍历找尾
        SLTNode *cur = *p;//指向当前位置
        SLTNode *prev = NULL;//指向前一个位置
        while (cur->next)
        {
            prev = cur;
            cur = cur->next;
        }
        free(cur);//释放空间
        cur = NULL;//及时置NULL
        //删除之后prev便是最后一个节点了
        prev->next = NULL;
    }
}

//单链表头删函数
void SLTPopFront(SLTNode **p)
{
    if (*p == NULL)//表示该链表为空
    {
        printf("该链表中并无值可供删除！\n");
        return;
    }
    else
    {
        SLTNode *pop_node = *p;//指向头节点
        *p = (*p)->next;//指向下一个元素
        free(pop_node);//释放空间
        pop_node = NULL;//及时置NULL
    }
}

//单链表查找函数
SLTNode *SLTFindNode(SLTNode *p, DataType FindData)
{
    assert(p);//确保传进来的指针不为空
    SLTNode *cur = p;
    while (cur)
    {
        if (cur->data == FindData)
        {
            return cur;//找到就返回该节点的地址
        }
        cur = cur->next;//循环遍历
    }
    return NULL;//找不到就返回NULL
}

//单链表修改函数
void SLTModify(SLTNode *pos, DataType ModifyData)
{
    assert(pos);//确保pos不为空
    pos->data = ModifyData;//修改
}

//单链表在pos位置之后插入InsertData
void SLTInsertAfter(SLTNode *pos, DataType InsertData)
{
    assert(pos);//保证pos不为NULL
    SLTNode *new_node = BuySLTNode(InsertData);//创建一个新节点
    //该节点的下一个指向原本该位置的下一个
    new_node->next = pos->next;
    //该位置的下一个就是new_node
    pos->next = new_node;
}

//单链表在pos位置之前插入InsertData
void SLTInsertBefore(SLTNode **p, SLTNode *pos, DataType InsertData)
{
    assert(pos);
    SLTNode *new_node = BuySLTNode(InsertData);
    if (pos == *p)//这就说明是第一个位置前插入
    {
        //头插
        new_node->next = *p;
        *p = new_node;
    }
    else
    {
        SLTNode *cur = *p;
        SLTNode *prev = NULL;
        //新节点的下一个指向这个位置
        new_node->next = pos;
        //循环遍历找到它的前一个位置
        while (cur != pos)
        {
            prev = cur;
            cur = cur->next;
        }
        //前一个位置指向新节点
        prev->next = new_node;
    }
}

//单链表在pos位置之前插入InsertData
void SLTInsertBefore_2(SLTNode *pos, DataType InsertData)
{
    assert(pos);

    SLTNode *new_node = BuySLTNode(InsertData);
    new_node->next = pos->next;
    pos->next = new_node;
    //进行了一个后插

    //交换这两个变量的值
    DataType tmp = pos->data;
    pos->data = new_node->data;
    new_node->data = tmp;
}

//删除pos位后的数据
void SLTEraseAfter(SLTNode *pos)
{
    assert(pos);
    if (pos->next == NULL)
    {
        //说明后面并没有元素了
        printf("该位置后无数据可以删除\n");
    }
    else
    {
        //创建一个指针指向下一个位置
        SLTNode *next = pos->next;
        //原位置的下一个位置，指向 下一个位置 的下一个位置
        pos->next = next->next;
        //释放内存
        free(next);
        next = NULL;
    }
}

//删除pos位的数据 --- 含有头删
void SLTEraseCur(SLTNode **p, SLTNode *pos)
{
    assert(pos);
    if (*p == pos)
    {
        //说明是头删
        *p = pos->next;
        free(pos);
        pos = NULL;
    }
    else
    {
        //普通位置
        SLTNode *prev = *p;
        SLTNode *cur = *p;
        //找到头一个位置
        while (cur != pos)
        {
            prev = cur;
            cur = cur->next;
        }
        //头一个位置指向下下个位置
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }

}

SLT.c

#include "SLT.h"

void test1()
{
    SLTNode *p = NULL;
    SLTPushBack(&p, 0);
    SLTPushBack(&p, 1);
    SLTPushBack(&p, 2);
    SLTPrint(p);

    SLTPushFront(&p, 0);
    SLTPushFront(&p, 1);
    SLTPushFront(&p, 2);
    SLTPrint(p);

    SLTPopBack(&p);
    SLTPrint(p);

    SLTPopFront(&p);
    SLTPrint(p);

    SLTNode *pos = SLTFindNode(p, 1);
    if (pos == NULL)
    {
        printf("该链表中无所查找的值！\n");
    }
    else
    {
        SLTModify(pos,123);
    }
    SLTPrint(p);

    SLTInsertAfter(pos,321);
    SLTPrint(p);

    SLTInsertBefore(&p,pos,000);
    SLTPrint(p);

    SLTInsertBefore_2(SLTFindNode(p,1),666);

    SLTPrint(p);

    SLTEraseAfter(SLTFindNode(p,1));
    SLTEraseAfter(SLTFindNode(p,666));
    SLTEraseCur(&p,SLTFindNode(p,0));
    SLTEraseCur(&p,SLTFindNode(p,123));
    SLTEraseCur(&p,SLTFindNode(p,321));
    SLTEraseCur(&p,SLTFindNode(p,0));
    SLTEraseCur(&p,SLTFindNode(p,0));
    SLTEraseCur(&p,SLTFindNode(p,666));
    SLTPrint(p);

}

int main()
{
    setbuf(stdout, NULL);
    test1();
    return 0;
}

main.c

|--------------------------------------------------------

关于单链表的知识到这便结束了

因笔者水平有限，若有错误，还望指正！

guguguhuha