链表篇---单向链表的C语言实现

简介: 链表篇---单向链表的C语言实现

前言:

   应部分粉丝要求,专门抽出一个专题来讨论下链表相关的数据结构,今天这篇文章来简单探讨下单向链表,后面会陆续出单向循环链表、双向链表、双向循环链表,还没关注的小伙伴抓紧时间关注起来啦。


简介:

   链表也是一种数据结构,链表分为数据域和指针域

   数据域:存放当前节点的数据

   指针域:指向下一个节点,通过next指针把每个节点串联起来,形成一个链式的数据结构,因此得名链表。

链表和数组的区别:

   说到这里很多人可能都在想,链式串联起来的数据结构不是和数组很像吗?确实,他们两之间有共同点,也有各自的优缺点,下面我们就来剖析下两者的区别:

   从内存分配上:

       ·    数组是静态分配的内存空间

       ·    链表是程序员在堆区动态分配的内存
   
从内存的存储方面上:

       ·    数组在内存中是连续存储的会造成一定的内存浪费,在定义数组的长度的时候必须预先规定其大小,如果长度过大会造成内存浪费。

       ·    链表在内存中是不连续的,通过指针将每个节点串接起来,其内存利用率高,能灵活的拓展我们要使用的内存空间。

   从查找元素方面上:

        ·    数组有下标查询定位,能快速的访问元素,查找的事件复杂度是O(1)

         ·    链表通过遍历所有节点查找元素,时间复杂度O(n)        

   从插入和删除元素上:

         ·    数组插入和删除元素需要移动其他元素,时间复杂度O(n)  

         ·    链表则不需要移动其他元素,只需要该表指针的指向即可,时间复杂度O(1),链表的插入和删除的效率高

删除节点图示:

插入节点图示

   

链表中节点的定义:

struct stList_node
{
    int                 data;      /*! 数据域 */
    struct stList_node  *next;     /*! 指针域 */
};

  在使用单向链表的时候我们经常会定义一个头节点,该节点不存放数据,用于对整个链表的遍历查找,能方便的实现链表的遍历、头插、尾插等过程。


   下面小编整理了几个链表操作的常用接口,并针对这些接口实现了链表的代码。这些接口的作用通过函数名就能知道是什么作用了。下面来一个一个详细介绍下。

extern int        CreatListHead(struct stList_node **head);
extern eListType  ifListempty(struct stList_node *head);
extern void       List_Print(struct stList_node *head);
extern int        ListInsertByHead(struct stList_node *head, int data);
extern int        ListInsertByTail(struct stList_node *head, int data);
extern int        ListDeleteByHead(struct stList_node *head);
extern int        ListDeleteByTail(struct stList_node *head);
extern int        ListDeleteByData(struct stList_node *head, int data, eListType type);

list.h

#ifndef  __LIST_H__
#define  __LIST_H__
#include "stdio.h"
#include "stdlib.h"
struct stList_node
{
    int                 data;      /*! 数据域 */
    struct stList_node  *next;     /*! 指针域 */
};
typedef enum
{
    TYPE_NULL            = 0,
    DELETE_ALL_SAME_DATA = 1,
    DELETE_ONE_DATA      = 2,
    LIST_EMPTY           = 3,
    LIST_NOT_EMPTY       = 4, 
}eListType;
extern int        CreatListHead(struct stList_node **head);
extern eListType  ifListempty(struct stList_node *head);
extern void       List_Print(struct stList_node *head);
extern int        ListInsertByHead(struct stList_node *head, int data);
extern int        ListInsertByTail(struct stList_node *head, int data);
extern int        ListDeleteByHead(struct stList_node *head);
extern int        ListDeleteByTail(struct stList_node *head);
extern int        ListDeleteByData(struct stList_node *head, int data, eListType type);
#endif   /* __LIST_H__ */

list.c

#include "list.h"
/*
* 函数名称:CreatListHead
* 输入参数:{struct stList_node **} head:头节点
* 返 回 值:-1:创建失败,原因是内存申请失败    0:创建成功
* 作    者:Barry
* 功能描述:创建头链表的头指针并为其申请内存空间
* 修改记录:None
*/
int CreatListHead(struct stList_node **head)
{
    /* 创建头节点 */
    *head = (struct stList_node *)malloc(sizeof(struct stList_node));
    if(*head == NULL)
        return -1;
    (*head)->data = -1;
    (*head)->next = NULL;
    return 0;
}
/*
* 函数名称:ifListempty
* 输入参数:{struct stList_node **} head:头节点
* 返 回 值:TRUE:空链表   FALSE:非空链表
* 作    者:Barry
* 功能描述:通过头指针判断链表是否为空
* 修改记录:None
*/
eListType ifListempty(struct stList_node *head)
{
    if(head->next == NULL)
        return LIST_EMPTY;
    else
        return LIST_NOT_EMPTY;
}
/*
* 函数名称:List_Print
* 输入参数:{struct stList_node **} head:头节点
* 返 回 值:None
* 作    者:Barry
* 功能描述:通过头指针遍历链表节点并打印
* 修改记录:None
*/
void List_Print(struct stList_node *head)
{
    struct stList_node *p;
    /* 空链表走这个分支 */
    if(ifListempty(head) == LIST_EMPTY)
        return;
    for(p = head->next; p != NULL; p = p->next)
        printf("%d \t", p->data);
    printf("\r\n");
}
/*
* 函数名称:ListInsertByHead
* 输入参数:{struct stList_node **} head:头节点
           {int                  } data:待插入的数据
* 返 回 值:-1:节点内存申请失败   0:删除成功
* 作    者:Barry
* 功能描述:链表头插法,在链表的头部插入数据
* 修改记录:None
*/
int ListInsertByHead(struct stList_node *head, int data)
{
    /* 定义待插入的节点 */
    struct stList_node *node = NULL;
    /* 插入的节点申请内存空间 */
    node = (struct stList_node *)malloc(sizeof(struct stList_node));
    if(node == NULL)
        return -1;
    node->data = data;   
    node->next = head->next;
    head->next = node;
    return 0;
}
/*
* 函数名称:ListInsertByTail
* 输入参数:{struct stList_node **} head:头节点
           {int                  } data:待插入的数据
* 返 回 值:-1:节点内存申请失败   0:删除成功
* 作    者:Barry
* 功能描述:链表尾插法,在链表的尾部插入数据
* 修改记录:None
*/
int ListInsertByTail(struct stList_node *head, int data)
{
    /* 定义待插入的节点 */
    struct stList_node *node = NULL;
    /* 遍历链表 */
    struct stList_node *p = head;
    /* 插入的节点申请内存空间 */
    node = (struct stList_node *)malloc(sizeof(struct stList_node));
    if(node == NULL)
        return -1;
    node->data = data; 
    node->next = NULL; 
    while(p->next != NULL)
    {
        p = p->next;
    }
    p->next = node;
    return 0;
}
/*
* 函数名称:ListDeleteByHead
* 输入参数:{struct stList_node **} head:头节点
* 返 回 值:-1:删除失败,原因:链表为空   0:删除成功
* 作    者:Barry
* 功能描述:链表头删法,在链表的头部删除数据
* 修改记录:None
*/
int ListDeleteByHead(struct stList_node *head)
{
    struct stList_node *p = head->next;
    /* 空链表走这个分支 */
    if(ifListempty(head) == LIST_EMPTY)
        return -1;
    head->next = p->next;
    free(p); 
    return 0;
}
/*
* 函数名称:ListDeleteByTail
* 输入参数:{struct stList_node **} head:头节点
* 返 回 值:-1:删除失败,原因:链表为空   0:删除成功
* 作    者:Barry
* 功能描述:链表尾删法,在链表的尾部删除数据
* 修改记录:None
*/
int ListDeleteByTail(struct stList_node *head)
{
    /* 当前节点 */
    struct stList_node *cur = NULL;
    /* 上一个节点 */
    struct stList_node *prev = NULL;
    /* 空链表走这个分支 */
    if(ifListempty(head) == LIST_EMPTY)
        return -1;
    cur = head;
    while(cur->next != NULL)
    {
        prev = cur;
        cur = cur->next;
    }
    free(cur); 
    /* 将上一节点的next指针指向空,否则free cur节点后prev->next没有任何指向,导致程序异常 */
    prev->next = NULL;
    return 0;
}
/*
* 函数名称:ListDeleteByTail
* 输入参数:{struct stList_node **} head:头节点
           {int                  } data:待删除的数据
           {eListType            } type:删除方式  
                    DELETE_ALL_SAME_DATA:删除链表中所有的data数据
                    DELETE_ONE_DATA     :删除链表中遍历到的第一个data数据(从头部开始遍历)
* 返 回 值:-1:删除失败,原因:链表为空   0:删除成功
* 作    者:Barry
* 功能描述:删除指定数据的链表,删除单个数据或链表中所有等于data的节点
* 修改记录:None
*/
int ListDeleteByData(struct stList_node *head, int data, eListType type)
{
    struct stList_node *cur = NULL;
    struct stList_node *prev = NULL;
    struct stList_node *ptemp = NULL;
    /* 空链表走这个分支 */
    if(ifListempty(head) == LIST_EMPTY)
        return -1;
    cur = head;
    prev = head;
    ptemp = cur;
    while(cur != NULL)
    {
        if(cur->data == data)
        {
            prev->next = cur->next; 
            ptemp = cur;
            free(ptemp);
            /* 释放ptemp后cur没有指向任何内容,将其指向下一个要判断数据的节点 */
            cur = prev->next;
            if(type == DELETE_ONE_DATA)
                break;
        }
        else
        {
            prev = cur;
            /* 向后移动一个节点 */
            cur = cur->next;
        }
    }
    return 0;
}


   
有兴趣的想要深入学习的可以研究下上面的代码。如有问题也请评论区指出,小编修改更正。


来简单的测试下上面的几个接口:

main.c

#include "list.h"
struct stList_node *ListHead = NULL;
int main(void)
{
    CreatListHead(&ListHead);
    ListInsertByTail(ListHead, 4);
    ListInsertByTail(ListHead, 4);
    ListInsertByTail(ListHead, 1);
    ListInsertByTail(ListHead, 2);
    ListInsertByTail(ListHead, 3);
    ListInsertByTail(ListHead, 4);
    ListInsertByTail(ListHead, 3);
    ListInsertByTail(ListHead, 3);
    ListInsertByTail(ListHead, 4);
    List_Print(ListHead);
    ListDeleteByData(ListHead, 4, DELETE_ALL_SAME_DATA);
    List_Print(ListHead);
    return 0;
}

从上面的代码知道我们利用尾插法插入一些元素,并打印出来,再调用删除节点的接口删除指定数据,下面来看下运行结果吧!

由于我们上面删除的接口是删除链表中所有数据是4的节点,因此删除前后的打印是上图这样的。


我们修改一下传入的参数,修改成只删除一个数据即

ListDeleteByData(ListHead, 4, DELETE_ONE_DATA);

再看下效果吧!

这次就只删除了第一个数据为4的节点。


我们再来测试下其他的接口:

使用头插法插入数据,再通过尾删法删除一个数据

    ListInsertByHead(ListHead, 4);
    ListInsertByHead(ListHead, 3);
    ListInsertByHead(ListHead, 2);
    ListInsertByHead(ListHead, 1);
    List_Print(ListHead);
    ListDeleteByTail(ListHead);
    List_Print(ListHead);

运行结果如下:

每次插入数据都在头部插入数据,因此链表中的数据是1 2 3 4,数据4在插入完成后变成尾部,通过尾删法删除后的打印是1 2 3,结果也是符合预期的。


其他的接口小编都测试过了,在这里就不一一测试啦,有兴趣的小伙伴可以测试下。


上述的三个文件放到VS Code上就可以直接运行。


如果觉得本篇文章多少有点帮助的话大家不要忘了,点赞、关注、评论、转发哦,创作不易!你们的支持是小编创作的最大动力。

相关文章
|
11天前
|
C语言
对链表使用插入排序的C语言实现示例
对链表使用插入排序的C语言实现示例
|
1月前
【数据结构】单链表之--无头单向非循环链表
【数据结构】单链表之--无头单向非循环链表
|
1月前
|
C语言
C语言循环链表讲解
C语言循环链表讲解
19 0
|
1月前
|
存储 C语言
C语言线性链表讲解
C语言线性链表讲解
18 0
|
1月前
|
存储 C语言
C语言双向链表讲解
C语言双向链表讲解
16 0
|
1月前
|
C语言
基于链表实现的链式管理系统(C语言课设)
基于链表实现的链式管理系统(C语言课设)
|
28天前
|
存储 C语言 索引
在C语言中静态链表
在C语言中静态链表
17 1
|
28天前
|
存储 算法 C语言
在C语言中的动态链表
在C语言中的动态链表
8 0
|
28天前
|
前端开发 C语言
c语言中的链表
c语言中的链表
8 1
|
1月前
|
C语言
【C语言】Leetcode 206.反转链表
【C语言】Leetcode 206.反转链表
17 0