链表大型攻略

首先我们为什么要用链表？

1、使用数组之前要声明长度，但是有时候你并不知道你要的数据有多长

2、插入和删除数组数据比较难操作

3、无法在数组中加入不同类型的数据

链表就如同手表链。。每一个小节都与相邻的另外两小节首尾相接，也就是上一个节点的指针指向下一个节点的头部，

当然了，单向链表的头部和尾部（头节点、尾节点）是会空出来的。

每一个节点大概长这样

 无论他数据有多少种，有多少byte 我们都把他归类为data段

剩下那部分就是指针了，用来指向下一个节点的指针

指针就是用来连接每两个不同地址的数据段的，数组的地址肯定是连续的，链表的就不一定了，所以要用指针连起来

在一个链表中，前面的就叫头节点，最后一个就是尾节点，中间可以有很多个都是中间节点

现在他们已经连起来了，但是我得找到链表的头节点才能找到这个链表，所以需要有一个头指针指向头节点，

而尾节点已经是最后一个了，不需要指向任何地方了

所以我们把这个图完善一下：

 这样一个单向链表就完成了。

---

原理就是这样，接下来我们实现一下：

首先定义一个结构体，包含我们刚才所说的数据段和指针段。

struct List
{
    int data;           //存放数据
    struct List *list_p_next;  //指向下一个节点的指针
};

根据我们之前学习的动态内存分配操作，去实现对头节点的创建

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

struct List
{
    int data;           //存放数据
    struct List *list_p_next;  //指向下一个节点的指针
};

typedef struct List list;


int main(int argc, char *argv[])
{
     //定义一个头指针 并对其分配内存
    list *list_p_head = NULL;    
    list_p_head = (list*)malloc(sizeof(list));
    if(list_p_head == NULL)
    {
        printf("list_p_head malloc failed");
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_head, 0, sizeof(list));

    //链表节点数据赋值
    list_p_head->data = 100;
    //链表里指针置空
    list_p_head->list_p_next = NULL;

    printf("%d
", list_p_head->data);

    free(list_p_head);

    return 0;
}

把刚才的main函数中的东西封装成一个独立的创建新节点的函数

传入参数即 data 数据

返回值为指向他的指针

这样以后我们再有需要创建新节点，就可以直接调用这个创建函数了

list *create_list(int data)
{
     //定义一个头指针 并对其分配内存
    list *list_p_head = NULL;    
    list_p_head = (list*)malloc(sizeof(list));
    if(list_p_head == NULL)
    {
        printf("list_p_head malloc failed");
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_head, 0, sizeof(list));

    //链表节点数据赋值
    list_p_head->data = 100;
    //链表里指针置空
    list_p_head->list_p_next = NULL;

 //   printf("%d
", list_p_head->data);

    return list_p_head;
}

把函数放进去，使用一下，没有问题。大功告成

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

struct List
{
    int data;           //存放数据
    struct List *list_p_next;  //指向下一个节点的指针
};

typedef struct List list;

list *create_list(int data);

int main(int argc, char *argv[])
{

    int data = 100;
    list *list_p = create_list(data);
    printf("list_p->data = %d
", list_p->data);
    printf("list_p->list_p_next = %d
", list_p->list_p_next);

    free(list_p);

    return 0;
}


//输入参数为该节点数据
//返回值为改节点指针
list *create_list(int data)
{
     //定义一个头指针 并对其分配内存
    list *list_p_head = NULL;    
    list_p_head = (list*)malloc(sizeof(list));
    if(list_p_head == NULL)
    {
        printf("list_p_head malloc failed");
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_head, 0, sizeof(list));

    //链表节点数据赋值
    list_p_head->data = 100;
    //链表里指针置空
    list_p_head->list_p_next = NULL;

 //   printf("%d
", list_p_head->data);

    return list_p_head;
}

---

 现在我们已经可以创建一个节点了，但是刚才节点的创建是单独的，只是有了一个节点而已，并没有把节点串起来组成链表。

那么我们要对这个创建节点的函数稍作修改

 首先要明确一点：我要在原有链表的末尾，新创建一个节点，并跟原有链表连接起来

那么有一种可能性要考虑， 如果原来根本呢没有链表呢？只有一个光秃秃的头指针呢？那我新节点就要连接在头指针后作为头节点

 逻辑就是这样的：

    if(head == NULL)
    {
        //如果头指针为空，说明此时该链表内没有任何节点
        //则头指针指向新创建的节点，并将该节点作为头节点
        head = list_p_create;
    }
    else
    {
        //如果头指针不为空，则需要在链表末尾添加刚才创建的节点
        //用while找到本链表的末节点，并将刚创建的节点接在最后
        while(list_p_tmp->next != NULL)
        {
            //如果list_p_tmp的下一个不是空，则将tmp指针替代为指向下一个节点的指针
            list_p_tmp = list_p_tmp->next;
        }
        //当list_p_nest为空，证明找到了末尾节点
        //则用该节点的next指针指向新创建的节点，连接起来
        list_p_tmp->next = list_p_create;
    }

那么根据上述逻辑，我们把刚才的创建节点函数修改一下：

/*
***************************************************************
*函数作用：创建节点函数
*输入参数：头指针,新节点数据
*返 回 值：头指针
*备    注：
***************************************************************
*/
list *create_list(list *head,int data)
{
    //定义一个结构体指针 并对其分配内存
    //该指针即为我们新创建的节点
    list *list_p_create = NULL;    
    list_p_create = (list*)malloc(sizeof(list));
    if(list_p_create == NULL)
    {
        printf("list_p_create malloc failed");
        exit(0);
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_create, 0, sizeof(list));

    //声明一个临时指针，通过临时指针对指针域赋值
    list *list_p_tmp = head;

    if(head == NULL)
    {
        printf("创建了头节点
");
        //如果头指针为空，说明此时该链表内没有任何节点
        //则头指针指向新创建的节点，并将该节点作为头节点
        head = list_p_create;
    }
    else
    {
        printf("头节点不为空
");
        //如果头指针不为空，则需要在链表末尾添加刚才创建的节点
        //用while找到本链表的末节点，并将刚创建的节点接在最后
        while(list_p_tmp->next != NULL)
        {
            printf("指向下一个节点
");
            //如果list_p_tmp的下一个不是空，则将tmp指针替代为指向下一个节点的指针
            list_p_tmp = list_p_tmp->next;
        }
        //当list_p_nest为空，证明找到了末尾节点
        //则用该节点的next指针指向新创建的节点，连接起来
        list_p_tmp->next = list_p_create;
    }

    //链表节点数据赋值
    list_p_create->data = data;
    //链表里指针置空
    list_p_create->next = NULL;

    return head;
}

为了更清楚的看到我们创建链表是否成功，所以写一个打印函数，使链表从头到尾打印出所有数据

/*
***************************************************************
*函数作用：打印整个链表
*输入参数：头指针
*返 回 值：
*备    注：
***************************************************************
*/
void disaplay_list(list *head)
{
    list *p_tmp = head;
    int i = 1;
    while (p_tmp != NULL)
    {
        printf("第%d个节点的值为:%d
",i,p_tmp->data);
        p_tmp = p_tmp->next;
        i += 1;
    }
}

下面把刚才的代码组装起来，测试一下是否成功

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

struct List
{
    int data;           //存放数据
    struct List *next;  //指向下一个节点的指针
};
typedef struct List list;

list *create_list(list *head,int data);     //创建节点函数
void disaplay_list(list *head);             //打印链表


int main(int argc, char *argv[])
{

    list *list_head = NULL;                             //链表头节点
    list_head = create_list(list_head,100);             //创建第一个节点
    disaplay_list(list_head);
    printf("----------------
");
    list_head = create_list(list_head,200);             //创建第二个节点
    disaplay_list(list_head);
    printf("----------------
");
    list_head = create_list(list_head,300);             //创建第三个节点
    disaplay_list(list_head);

    return 0;
}


/*
***************************************************************
*函数作用：创建节点函数
*输入参数：头指针,新节点数据
*返 回 值：头指针
*备    注：
***************************************************************
*/
list *create_list(list *head,int data)
{
    //定义一个结构体指针 并对其分配内存
    //该指针即为我们新创建的节点
    list *list_p_create = NULL;    
    list_p_create = (list*)malloc(sizeof(list));
    if(list_p_create == NULL)
    {
        printf("list_p_create malloc failed");
        exit(0);
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_create, 0, sizeof(list));

    //声明一个临时指针，通过临时指针对指针域赋值
    list *list_p_tmp = head;

    if(head == NULL)
    {
        printf("创建了头节点
");
        //如果头指针为空，说明此时该链表内没有任何节点
        //则头指针指向新创建的节点，并将该节点作为头节点
        head = list_p_create;
    }
    else
    {
        printf("头节点不为空
");
        //如果头指针不为空，则需要在链表末尾添加刚才创建的节点
        //用while找到本链表的末节点，并将刚创建的节点接在最后
        while(list_p_tmp->next != NULL)
        {
            printf("指向下一个节点
");
            //如果list_p_tmp的下一个不是空，则将tmp指针替代为指向下一个节点的指针
            list_p_tmp = list_p_tmp->next;
        }
        //当list_p_nest为空，证明找到了末尾节点
        //则用该节点的next指针指向新创建的节点，连接起来
        list_p_tmp->next = list_p_create;
    }

    //链表节点数据赋值
    list_p_create->data = data;
    //链表里指针置空
    list_p_create->next = NULL;

    return head;
}


/*
***************************************************************
*函数作用：打印整个链表
*输入参数：头指针
*返 回 值：
*备    注：
***************************************************************
*/
void disaplay_list(list *head)
{
    list *p_tmp = head;
    int i = 1;
    while (p_tmp != NULL)
    {
        printf("第%d个节点的值为:%d
",i,p_tmp->data);
        p_tmp = p_tmp->next;
        i += 1;
    }
}

输出结果如下：

在运行第一次create_list()时，在头指针后面接了了一个新节点；

在运行第二次create_list()时，在判断头指针不为空后，在头节点后面接了了一个新节点；

在运行第三次create_list()时，头指针不为空，头节点的next指针也不为空，再找到next为空后，在尾节点后面接了了一个新节点。

---

细心的同学可能已经发现了，刚才我主函数中没有free()释放内存;

如果让我free(p1);free(p2);free(p3)这样显然太过麻烦，那么我们想个办法，一次性释放整个链表的空间

/*
***************************************************************
*函数作用：释放链表内存
*输入参数：头指针
*返 回 值：
*备    注：
***************************************************************
*/
void free_list(list *head)
{
    //p_tmp从头节点开始一路往后指，遇到不为空(需要free)的节点便将该节点交给p_free释放
    list *p_tmp = head,*p_free = NULL;
    while(p_tmp != NULL)
    {
        p_free = p_tmp;
        p_tmp = p_tmp->next;
        free(p_free);
    }
}

把这段代码放进去，运行成功，没有问题。

刚才介绍的是从尾部添加新节点，那如果我想从中间插入呢？

 

 

 刚才这个图只表示了插入的一种情况，就是有头有尾的链表，我在中间插入一个节点。

但是

1、如果我在插入的时候，甚至连头节点都没有呢？

2、如果我想插在头节点之前呢？

3、在尾节点后插入新节点？

4、我要插的位置，根本不存在。

所以在插入函数中，我们要考虑到这些种不同的情况

在写道这里，调试代码时，笔者注意到了一个问题，就是一般情况下，头节点是不存放数据的。

也就是说，头节点后面的通常被称为第一个元素。所以我也适当的调整了代码，但是之前的代码并无太多影响，就不做更改了。

/*
***************************************************************
*函数作用：插入一个节点
*输入参数：head 头指针
          data 节点内数据
          n    插到第几个节点前
          n = 1 时将数据放于第一位
*返 回 值：
*备    注：
***************************************************************
*/
int insert_list(list *head,int data,int n)
{
    list *p_tmp = head;
    int i = 0;
    //跟前面的方法一样定义一个指针 创建一个节点
    list *list_p_create = NULL;    
    list_p_create = (list*)malloc(sizeof(list));
    if(list_p_create == NULL)
    {
        printf("list_p_create malloc failed");
        exit(0);
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_create, 0, sizeof(list));
    //给新节点赋值
    list_p_create->data = data;
    list_p_create->next = NULL;

    if(n<1)
    {
        printf("插入位置错误
");
        exit(0);
    }

    //刚才说的第一种情况，如果没有头节点，则该节点作为头节点
    if(head == NULL)
    {
        printf("创建了头节点
");
        head = list_p_create;
    }
    else//下面是有头节点的情况
    {
/*        if(n == 1)//在头节点前新增节点（替换头节点）
        {
            printf("在第1个点前新增节点
");
            list_p_create->next = head->next;
            head->next = list_p_create;
            return 0;
        }
*/      while(i < n - 1)
        {
            p_tmp = p_tmp->next;
            i++;
            if(p_tmp->next == NULL)//该节点为尾节点
            {
                //在尾节点后加一个新节点
                printf("在尾节点后加一个新节点
");
                p_tmp->next = list_p_create;
                return 0;
            }
        }
        printf("在第%d个节点前新增节点
",n);
        list_p_create->next = p_tmp->next;
        p_tmp->next = list_p_create;
    }
    return 0;
}

看一下运行结果：

那么我们看看如何删除一个节点

定义两个指针，一个指针p_tmp_free用来寻找要被删除的节点，另一个指针p_tmp_before用来储存被删除节点的上一个位置

这样在p_tmp_free在被释放后，p_tmp_before可以连接其与下一个节点

/*
***************************************************************
*函数作用：删除节点 
*输入参数：head头指针   n要删除的第n个节点
*返 回 值：
*备    注：n = 1时删除头节点后的那个节点
***************************************************************
*/
void delete_list(list *head,int n) 
{
    int i = 0;
    //p_tmp_free最终将指向要被删除的节点，p_tmp_before用来存放被删的上一个节点
    list *p_tmp_free = head,*p_tmp_before = head;

    //n必须大于1
    if(n < 1)
    {
        printf("delete_list failed,Parameter error
");
        return;
    }
    while(i < n && p_tmp_free != NULL)
    {
        //两个指针向前走
        //如果p_tmp_free不是要被删除的那个，p_tmp_before就跟上
        //在遇到目标节点之前，这两个指针是一前一后的关系
        p_tmp_before = p_tmp_free;
        p_tmp_free = p_tmp_free->next;
        i++;
    }
    //遇到了目标指针时把p_tmp_before接在p_tmp_free后面的节点上
    //释放掉p_tmp_free
    if(p_tmp_free != NULL)
    {
        p_tmp_before->next = p_tmp_free->next;
        free(p_tmp_free);
    }
    else
    {
        printf("delete_list failed,The target doesn't exist
");
        return;
    }
}

接下来试试修改节点的数据：

/*
***************************************************************
*函数作用：链表的查询
*输入参数：head头指针   n要查询的第n个节点
*返 回 值：0成功
*备    注：n = 1时查询头节点后的那个节点
***************************************************************
*/
int find_list(list *head,int n)
{
    list *p_tmp = head;
    int i = 0;

    if(n < 1)
    {
        printf("find_list failed,Parameter error
");
        return 1;
    }
    while(i < n && p_tmp != NULL)
    {
        p_tmp = p_tmp->next;
        i++;
    }
    if(p_tmp != NULL)
    {
        printf("第%d个节点的数据为%d
",i,p_tmp->data);
    }
    else
    {
        printf("find_list failed,The target doesn't exist
");
        return 1;
    }
    return 0;
}

其实修改就没有任何难度了，跟删除几乎一样。

以上全部代码：

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

struct List
{
    int data;           //存放数据
    struct List *next;  //指向下一个节点的指针
};
typedef struct List list;

list *create_list(list *head,int data);     //创建节点函数
void disaplay_list(list *head);             //打印链表
void free_list(list *head);                 //free()
int insert_list(list *head,int data,int n);    //插入节点
int delete_list(list *head,int n);          //删除节点
int change_list(list *head,int n,int data); //修改节点
int find_list(list *head,int n);            //节点查询


int main(int argc, char *argv[])
{
    list *list_head = NULL;                             //链表头指针
    list_head = create_list(list_head,NULL);            //创建头节点

    list_head = create_list(list_head,100);             //创建第一个节点
    disaplay_list(list_head);
    printf("--------------------
");
    list_head = create_list(list_head,200);             //创建第二个节点
    disaplay_list(list_head);
    printf("--------------------
");
    list_head = create_list(list_head,300);             //创建第三个节点
    disaplay_list(list_head);

    printf("--------------------
");
    insert_list(list_head,150,2);
    disaplay_list(list_head);
    printf("--------------------
");
    insert_list(list_head,45,1);
    disaplay_list(list_head);
    printf("--------------------
");
    insert_list(list_head,845,5);
    disaplay_list(list_head);
    printf("--------------------
");
    insert_list(list_head,36,50);
    disaplay_list(list_head);

    printf("--------------------
");
    delete_list(list_head,1);
    disaplay_list(list_head);    
    printf("--------------------
");
    delete_list(list_head,25);
    disaplay_list(list_head);   
    printf("--------------------
");
    delete_list(list_head,6);
    disaplay_list(list_head);   

    printf("--------------------
");
    change_list(list_head,3,648);
    disaplay_list(list_head);   

    printf("--------------------
");
    find_list(list_head,3);


    free_list(list_head);
    return 0;
}


/*
***************************************************************
*函数作用：从尾部创建节点函数
*输入参数：头指针,新节点数据
*返 回 值：头指针
*备    注：
***************************************************************
*/
list *create_list(list *head,int data)
{
    //定义一个结构体指针 并对其分配内存
    //该指针即为我们新创建的节点
    list *list_p_create = NULL;    
    list_p_create = (list*)malloc(sizeof(list));
    if(list_p_create == NULL)
    {
        printf("list_p_create malloc failed");
        exit(0);
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_create, 0, sizeof(list));

    //声明一个临时指针，通过临时指针对指针域赋值
    list *list_p_tmp = head;

    if(head == NULL)
    {
        printf("创建了头节点
");
        //如果头指针为空，说明此时该链表内没有任何节点
        //则头指针指向新创建的节点，并将该节点作为头节点
        head = list_p_create;
    }
    else
    {
        printf("头节点不为空
");
        //如果头指针不为空，则需要在链表末尾添加刚才创建的节点
        //用while找到本链表的末节点，并将刚创建的节点接在最后
        while(list_p_tmp->next != NULL)
        {
            printf("指向下一个节点
");
            //如果list_p_tmp的下一个不是空，则将tmp指针替代为指向下一个节点的指针
            list_p_tmp = list_p_tmp->next;
        }
        //当list_p_nest为空，证明找到了末尾节点
        //则用该节点的next指针指向新创建的节点，连接起来
        list_p_tmp->next = list_p_create;
    }

    //链表节点数据赋值
    list_p_create->data = data;
    //链表里指针置空
    list_p_create->next = NULL;

    return head;
}


/*
***************************************************************
*函数作用：打印整个链表
*输入参数：头指针
*返 回 值：
*备    注：
***************************************************************
*/
void disaplay_list(list *head)
{
    list *p_tmp = head;
    int i = 0;
    while (p_tmp != NULL)
    {
        printf("第%d个节点的值为:%d
",i,p_tmp->data);
        p_tmp = p_tmp->next;
        i++;
    }
}



/*
***************************************************************
*函数作用：释放链表内存
*输入参数：头指针
*返 回 值：
*备    注：
***************************************************************
*/
void free_list(list *head)
{
    //p_tmp从头节点开始一路往后指，遇到不为空(需要free)的节点便将该节点交给p_free释放
    list *p_tmp = head,*p_free = NULL;
    while(p_tmp != NULL)
    {
        p_free = p_tmp;
        p_tmp = p_tmp->next;
        free(p_free);
    }
}


/*
***************************************************************
*函数作用：插入一个节点
*输入参数：head 头指针
          data 节点内数据
          n    插到第几个节点前
          n = 1 时将数据放于第一位
*返 回 值：
*备    注：
***************************************************************
*/
int insert_list(list *head,int data,int n)
{
    list *p_tmp = head;
    int i = 0;
    //跟前面的方法一样定义一个指针 创建一个节点
    list *list_p_create = NULL;    
    list_p_create = (list*)malloc(sizeof(list));
    if(list_p_create == NULL)
    {
        printf("list_p_create malloc failed");
        exit(0);
    }
    //将刚定义的头指针指向的区域置0
    memset(list_p_create, 0, sizeof(list));
    //给新节点赋值
    list_p_create->data = data;
    list_p_create->next = NULL;

    if(n<1)
    {
        printf("插入位置错误
");
        exit(0);
    }

    //刚才说的第一种情况，如果没有头节点，则该节点作为头节点
    if(head == NULL)
    {
        printf("创建了头节点
");
        head = list_p_create;
    }
    else//下面是有头节点的情况
    {
/*        if(n == 1)//在头节点前新增节点（替换头节点）
        {
            printf("在第1个点前新增节点
");
            list_p_create->next = head->next;
            head->next = list_p_create;
            return 0;
        }
*/      while(i < n - 1)
        {
            p_tmp = p_tmp->next;
            i++;
            if(p_tmp->next == NULL)//该节点为尾节点
            {
                //在尾节点后加一个新节点
                printf("在尾节点后加一个新节点
");
                p_tmp->next = list_p_create;
                return 0;
            }
        }
        printf("在第%d个节点前新增节点
",n);
        list_p_create->next = p_tmp->next;
        p_tmp->next = list_p_create;
    }
    return 0;
}



/*
***************************************************************
*函数作用：删除节点 
*输入参数：head头指针   n要删除的第n个节点
*返 回 值：
*备    注：n = 1时删除头节点后的那个节点
***************************************************************
*/
int delete_list(list *head,int n) 
{
    int i = 0;
    //p_tmp_free最终将指向要被删除的节点，p_tmp_before用来存放被删的上一个节点
    list *p_tmp_free = head,*p_tmp_before = head;

    //n必须大于1
    if(n < 1)
    {
        printf("delete_list failed,Parameter error
");
        return 1;
    }
    while(i < n && p_tmp_free != NULL)
    {
        //两个指针向前走
        //如果p_tmp_free不是要被删除的那个，p_tmp_before就跟上
        //在遇到目标节点之前，这两个指针是一前一后的关系
        p_tmp_before = p_tmp_free;
        p_tmp_free = p_tmp_free->next;
        i++;
    }
    //遇到了目标指针时把p_tmp_before接在p_tmp_free后面的节点上
    //释放掉p_tmp_free
    if(p_tmp_free != NULL)
    {
        p_tmp_before->next = p_tmp_free->next;
        free(p_tmp_free);
        return 0;
    }
    else
    {
        printf("delete_list failed,The target doesn't exist
");
        return 1;
    }
}


/*
***************************************************************
*函数作用：修改节点 
*输入参数：head头指针   n要修改的第n个节点  data 修改后的数据
*返 回 值：0成功
*备    注：n = 1时修改头节点后的那个节点
***************************************************************
*/
int change_list(list *head,int n,int data)
{
    list *p_tmp = head;
    int i = 0;

    if(n < 1)
    {
        printf("change_list failed,Parameter error
");
        return 1;
    }
    while(i < n && p_tmp != NULL)
    {
        p_tmp = p_tmp->next;
        i++;
    }
    if(p_tmp != NULL)
    {
        p_tmp->data = data;
    }
    else
    {
        printf("change_list failed,The target doesn't exist
");
        return 1;
    }
    return 0;
}



/*
***************************************************************
*函数作用：链表的查询
*输入参数：head头指针   n要查询的第n个节点
*返 回 值：0成功
*备    注：n = 1时查询头节点后的那个节点
***************************************************************
*/
int find_list(list *head,int n)
{
    list *p_tmp = head;
    int i = 0;

    if(n < 1)
    {
        printf("find_list failed,Parameter error
");
        return 1;
    }
    while(i < n && p_tmp != NULL)
    {
        p_tmp = p_tmp->next;
        i++;
    }
    if(p_tmp != NULL)
    {
        printf("第%d个节点的数据为%d
",i,p_tmp->data);
    }
    else
    {
        printf("find_list failed,The target doesn't exist
");
        return 1;
    }
    return 0;
}