数据结构 -- C语言实现链表(单链表)

min的技术小铺 2021-11-17

543

点击上方蓝字关注我

数据结构是计算机类的基础.曾经有一位大佬说过, 程序就是算法和数据结构做加法的产物, 接下来我会编写数据结构的相关内容, 仅供学习和参考.

接下来我们用C语言实现单链表.

前言

还是老生常谈的前言:

在实现之前我们要了解数据结构关注的是数据元素之间的关系, 有逻辑结构和物理结构, 还需要定义一些相关的运算.

我们通过逻辑结构来定义运算, 并依据具体的物理结构进行实现. 而每一种数据结构最基本同时也是核心的运算无非就是创销以及增删改查.

节点与单链表的创建

在链表中, 每一个数据元素称为节点, 通常用结构体来定义.

typedef int ElemType;

//定义单链表中的节点
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList; //定义两个名称 前者侧重于表示节点, 后者侧重于表示单链表

这里我们宏定义了一个关键字, 可以通过修改它来进行一个全局的数据类型的更改.

头插法建立单链表

顾名思义就是从头开始一次插入一个数据元素

//头插法建立单链表
LinkList List_HeadInsert(LinkList L)
{
    ElemType x = 0;
    LNode *s;
    L = (LinkList)malloc(sizeof(LNode)); //创建头节点
    L->next = NULL;
    for (ElemType i = 0; i < 5; i++) //初始化一个长度为5的链表
    {
        s = (LNode *)malloc(sizeof(LNode)); //创建新节点
        s->data = x; //输入节点的初始值
        s->next = L->next; //新节点的后向指针指向头节点的后向指针
        L->next = s; //头节点的后向指针指向新节点 , 完成头插
        x++; // 指定数据＋1, 此处可DIY 
 
    }
    return L;
}

一般来说, 建立单链表我们会首先创建一个头节点, 它并不存储数据, 只有一个指向下一节点的指针域, 它就相当于数组下标0代表的元素, 有了它的存在, 我们就无需对第一个节点进行特殊的处理, 也统一了元素位置与其在链表中的序号的一致性.

尾插法建立单链表

和头插法差不多, 就是从链表的尾部依次插入数据

//尾插法建立单链表
LinkList List_TailInsert(LinkList L)
{
    ElemType x = 0;
    LNode *s, *T; // T为表尾指针
    L = (LinkList)malloc(sizeof(LNode)); // 创建头节点
    s, T = L; //先初始化指向头节点 
    for (ElemType i = 0; i < 5; i++)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        T->next = s; // 此处是让前节点的后向指针指向新节点
        T = s; // T指向新的表尾节点
                    
    }
    T->next = NULL; //表尾指向NULL
    return L;
}

尾插法的与头插法的不同在于, 多了一个指针, 一直指向尾部的节点.

基本运算

接下来我们来看看单链表的基本运算如何实现, 也就是所谓增删改查

在写代码之前先思考, 在链表中, 实现插入, 更改, 删除的操作, 是不是都要先进行查找呢?

答案的是肯定的, 链表并不具有顺序表随机存储的特性, 必须要遍历才可以找到某个节点, 然后再进行相应操作, 所以我们先实现查找.

//按序号查找节点值
LNode *GetElem(LinkList L, int i){
    int count = 1; // 计数变量
    LNode *p = L->next; // 头节点next赋给P
    if (i == 0){
        return L; // i = 0返回头节点
    }
    if(i < 1){
         printf("%s", "warn input!");
        return NULL; // 错误序号
       
    }
    while(p&&count < i){ // 从第一个节点开始找, 查找第i个节点, 此处判断即是判断时候到最后null的时候任然没有找到节点.
        p=p->next;
        count++;
    }
    return p; 
}

这里注意, 要处理用户输入的非法序号, 增强程序的健壮性, while循环中巧妙的判断了p节点为空的情况.

插入元素

有了查找之后, 下面的实现变得轻松了很多
插入元素的实现就是:
查找第i-1个位置, 开辟一块空间给新节点, 新节点的next指向i-1的next, i-1的next指向新节点

//插入新数据元素 i:插入位置, elem:插入元素值
LNode *InsetElem(LinkList L, int i, ElemType elem){
//查找第i-1个位置, 开辟一块空间给新节点, 新节点的next指向i-1的next, i-1的next指向新节点
    LNode *pre_Node = GetElem(L, i-1);
    LNode *new_Node = (LNode*)malloc(sizeof(LNode));
    new_Node->data = elem;
    new_Node->next = pre_Node->next;
    pre_Node->next = new_Node;
    return L;
}

删除元素

找到第i-1个元素, 让它指向后第二个元素, 并且释放空间

//删除元素
LNode *delElem(LinkList L, int i){
    //找到第i-1个元素, 让它指向后第二个元素
    LNode *pre_Node = GetElem(L, i-1);
    pre_Node->next = pre_Node->next->next;
    free(pre_Node->next);
    return L;
}

更改(更新元素)

找到第i个元素, 并对其内容进行赋值覆盖即可

//更改(更新元素)
LNode *changeElem(LinkList L, int i, ElemType elem){
      //找到第i个元素, 并对其内容进行赋值覆盖即可
      LNode *Node = GetElem(L, i);
      Node->data = elem;
      return L;
}

至此, 我们已经完成增删改查的功能了, 以下附完整源码

#include <stdio.h>
#include <malloc.h>
typedef int ElemType;

//定义单链表中的节点
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList; //定义两个名称 前者侧重于表示节点, 后者侧重于表示单链表

//头插法建立单链表
LinkList List_HeadInsert(LinkList L)
{
    ElemType x = 0;
    LNode *s;
    L = (LinkList)malloc(sizeof(LNode)); //创建头节点
    L->next = NULL;
    for (ElemType i = 0; i < 5; i++) //初始化一个长度为5的链表
    {
        s = (LNode *)malloc(sizeof(LNode)); //创建新节点
        s->data = x; //输入节点的初始值
        s->next = L->next; //新节点的后向指针指向头节点的后向指针
        L->next = s; //头节点的后向指针指向新节点 , 完成头插
        x++; // 指定数据＋1, 此处可DIY 
 
    }
    return L;
}

//尾插法建立单链表
LinkList List_TailInsert(LinkList L)
{
    ElemType x = 0;
    LNode *s, *T; // T为表尾指针
    L = (LinkList)malloc(sizeof(LNode)); // 创建头节点
    s, T = L; //先初始化指向头节点 
    for (ElemType i = 0; i < 5; i++)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        T->next = s; // 此处是让前节点的后向指针指向新节点
        T = s; // T指向新的表尾节点
                    
    }
    T->next = NULL; //表尾指向NULL
    return L;
}


//按序号查找节点值
LNode *GetElem(LinkList L, int i){
    int count = 1; // 计数变量
    LNode *p = L->next; // 头节点next赋给P
    if (i == 0){
        return L; // i = 0返回头节点
    }
    if(i < 1){
         printf("%s", "warn input!");
        return NULL; // 错误序号
       
    }
    while(p&&count < i){ // 从第一个节点开始找, 查找第i个节点, 此处判断即是判断时候到最后null的时候任然没有找到节点.
        p=p->next;
        count++;
    }
    return p; 
}

//插入新数据元素 i:插入位置, elem:插入元素值
LNode *InsetElem(LinkList L, int i, ElemType elem){
//查找第i-1个位置, 开辟一块空间给新节点, 新节点的next指向i-1的next, i-1的next指向新节点
    LNode *pre_Node = GetElem(L, i-1);
    LNode *new_Node = (LNode*)malloc(sizeof(LNode));
    new_Node->data = elem;
    new_Node->next = pre_Node->next;
    pre_Node->next = new_Node;
    return L;
}

//删除元素
LNode *delElem(LinkList L, int i){
    //找到第i-1个元素, 让它指向后第二个元素
    LNode *pre_Node = GetElem(L, i-1);
    pre_Node->next = pre_Node->next->next;
    free(pre_Node->next);
    return L;
}

//更改(更新元素)
LNode *changeElem(LinkList L, int i, ElemType elem){
      //找到第i个元素, 并对其内容进行赋值覆盖即可
      LNode *Node = GetElem(L, i);
      Node->data = elem;
      return L; 
}

int main(int argc, char const *argv[])
{
    LinkList list;
    LinkList L = List_HeadInsert(list);
    LNode *Node1 = GetElem(L, 2);
    printf("%d", Node1->data);
    return 0;
}

点个在看你最好看

数据库

文章转载自min的技术小铺，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

数据结构 -- C语言实现链表(单链表)

评论