当前位置：主页 > 查看内容

单链表全解(从零开始)——数据结构(C语言)

发布时间：2021-07-10 00:00| 有位朋友查看

简介：数据结构C语言——单链表的创建及基本功能的实现 1. 链表类型 2. 单链表的定义单链表是由一连串的 “结点” 组成的这里我们可以把每一个 “结点” 理解为一个小盒子这个盒子内部由两部分组成一部分用来储存数据我们把它称为 “数据域” 另一部分用来存放指……

数据结构（C语言）——单链表的创建及基本功能的实现

1. 链表类型

在这里插入图片描述

2. 单链表的定义

单链表是由一连串的 “结点” 组成的，这里我们可以把每一个 “结点” 理解为一个小盒子，这个盒子内部由两部分组成：一部分用来储存数据，我们把它称为 “数据域” ，另一部分用来存放指针，及指向下一个结点的地址，我们把它称为 “指针域” 。像这样，我们从某一个结点访问其指针域即可以找到下一个节点。像这样通过寻找地址的方式进行链式连接，即构成了单链表。

1.单链表结构示意图（头部）：

在这里插入图片描述

2. 单链表结构图示（中间部分）：

在这里插入图片描述
3.单链表结构示意图（尾部）：

3.单链表的存储结构

单链表为链式储存结构，与顺序表不同，链表不限制数据的物理存储状态，换句话说，使用链表存储的数据元素，其物理存储位置是随机的。

4.学习单链表须弄明白的一些基本概念

一. 单链表必须元素（如下图）
在这里插入图片描述

1. 头指针

头指针，顾名思义，即为一个指针，指向的是头结点的地址

2. 头结点

a. 在单链表中设置头节点的作用是为了方便单链表的特殊操作（如：简化插入、删除操作），这样可以保持单链表操作的统一性。
b. 头结点同样包含了数据域和指针域，其数据域中可存值或者不存值，其指针域指向第一个结点

3. 中间结点

包含数据域指针域，通过结点地址以链式相连。

4.尾结点

注意尾结点的指针域为空(NULL)。

5.数据域

数据域包含多种类型，可以为整型，或者数组型，结构体型等等。

6.指针域

头结点指针域内的指针指向第一个结点的地址，第一个结点指针域的指针域指向第二个结点的地址，直到最后指向尾结点的空(NULL)。

5.代码部分

1.创建结点类型

a.数据域为int型

typedef int ElemType;            //定义ElemType为int型，这里的类型根据实际情况而定(可以为数组或者结构体类型)，这里假设为int
typedef struct LinkList          //定义结点类型，即LinkList型
{
    ElemType data;               //数据域，这里用的int形代替（这样声明是为了方便修改数据类型）
    struct LinkList *next;       //指针域，指向LinkList型的结点
}LinkListNode;                   //定义结点变量,名称为LinkListNode

b.数据域为结构体类型

typedef struct ElemType          //定义结构体类型的数据域，名称为Elemtype
{
    int ElemType_1;              //ElemType类型中包含的元素
    char ElemType_2;
    double ElemType_3;
}Elem;                           //变量名为Elem
typedef struct LinkList          
{
    Elem data;                   //该处的数据域为一个结构体类型
    struct LinkList *next;      
}LinkListNode;

2.创建结点函数

LinkListNode *LinkListNodeCreat(ElemType e)                               //随机读入一个类型为ElemType的值(这里是int型)
{
/************************************************************************************************/
    LinkListNode *pTmp = (LinkListNode*)malloc(sizeof(LinkListNode));     //为结点随机分配内存空间
    if(!pTmp)
    {
        printf("节点内存分配失败！\n");
        return NULL;                                                      //判空操作
    }
    memset(pTmp,0x00,sizeof(LinkListNode));                               //初始化分配的内存空间为0
/************************************************************************************************/
//以上是一套基本的创建结点的操作

    pTmp->data = e;                //将int型数据域存入该结点
    pTmp->next = NULL;             //记住一定将新节点的指针域赋为空！！
    return pTmp;                   //返回指针
}

3.1插入函数(头插法)

这里我们要将一个新结点插入到头结点之后，让该节点作为第一个结点。

int LinkListHeadInsert(LinkListNode *L,ElemType e)//这里L是头结点
{
    LinkListNode *NewNode = LinkListNodeCreat(e); //这里先创建一个名叫NewNode的新结点

    NewNode->next = L->next;//将头结点中指针域的值赋给新结点的指针域中   PS:此时头结点的指针域有两种情况   1.头结点后无节点，此时相当于将NULL赋给新节点的指针域   2.头结点的指针域指向原链表的第一个结点，此时将头结点的指针域的值赋给新结点指针域，让新结点指针域指向原链表的第一个结点
    L->next = NewNode;      //再将新结点指针域的值赋给头结点的指针域，使头结点的下一个结点为新结点

    return OK;
}

3.2输入函数

int LinkListInput(LinkListNode *L)  
{
    int i = 0,ElemNum = 0,Element = 0;
    printf("请输入要插入结点的个数：\n");  //插入多少个循环多少次
    scanf("%d",&ElemNum);
    printf("请输入链表当中的元素：\n");
    for(i=0 ;i<ElemNum;i++)
    {
        scanf("%d",&Element);
        LinkListHeadInsert(L,Element); //直接调用头插法函数，头插法在调用创建结点
    }
    return OK;
}

4.输出函数
先判断链表是否为空，为空则不能打印输出！

int LinkListPrint(LinkListNode *L)
{
    if(L->next==NULL)            //判断头结点是否为空，是则不打印
    {
        printf("当前链表为空\n");
        system("pause");
        return 0;
    }
    LinkListNode *pTmp = L->next;//将pTmp的地址赋值为第一个结点的地址,若没有结点则为NULL
    printf("当前链表元素为：\n");
    while (pTmp)                 //判断是否有结点
    {
        printf("%d ",pTmp->data);//打印出数据域的值
        pTmp = pTmp->next;       //位移至下一个结点的地址
    }
    printf("\n");
    system("pause");
    return OK;
}

5.删除所有元素函数
先判断链表是否为空，为空则不能删除！

int ListDelete(LinkListNode *L)
{
    if(L->next==NULL)            //判断头结点是否为空，是则无法删除
    {
        printf("当前链表无元素\n");
        system("pause");
        return FALSE;
    }
    LinkListNode *HeadTmp = L;   //将头指针的值赋给HeadTmp，作用是循环，直至空
    LinkListNode *TestTmp;       //中间过渡暂存指针
    while(HeadTmp)
    {
        TestTmp=HeadTmp;
        HeadTmp=HeadTmp->next;   
        free(TestTmp);           //清除结点
    }
    L->next=NULL;                //记住这里将头结点的指针域赋值为空！！  否则使用上面的输出函数会报错，因为之后的结点已经被free了，但L还指向的是一个已经被清除的结点
    printf("删除成功！\n");
    system("pause");
    return OK;
}

6.退出函数
这里和上面删除所有元素函数思想一样，只是把头结点也给free了

int OutList(LinkListNode *L)
{
    if(L->next==NULL)
    {
        return OK;
    }
    LinkListNode *HeadTmp = L;
    LinkListNode *TestTmp;
    while(HeadTmp)
    {
        TestTmp=HeadTmp;
        HeadTmp=HeadTmp->next;
        free(TestTmp);
    }
    free(L);                        //free掉头结点
    return OK;
}

全部代码：
这里主要看一下菜单函数和主函数

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

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

//创建结点类型
typedef int ElemType;            //定义ElemType为int型，这里的类型根据实际情况而定(可以为数组或者结构体类型)，这里假设为int
typedef struct LinkList          //定义结点类型，即LinkList型
{
    ElemType data;               //数据域，这里用的int形代替（这样声明是为了方便修改数据类型）
    struct LinkList *next;       //指针域，指向LinkList型的结点
}LinkListNode;


//************************************************
//创建节点函数
LinkListNode *LinkListNodeCreat(ElemType e)                               //随机读入一个类型为ElemType的值(这里是int型)
{
    LinkListNode *pTmp = (LinkListNode*)malloc(sizeof(LinkListNode));     //为结点随机分配内存空间
    if(!pTmp)
    {
        printf("节点内存分配失败！\n");
        return NULL;                                                      //判空操作
    }
    memset(pTmp,0x00,sizeof(LinkListNode));                               //初始化分配的内存空间为0
    pTmp->data = e;                //将int型数据域存入该结点
    pTmp->next = NULL;             //记住一定将新节点的指针域赋为空！！
    return pTmp;                   //返回指针
}
//************************************************
//头插功能函数
int LinkListHeadInsert(LinkListNode *L,ElemType e)//这里L是头结点
{
    LinkListNode *NewNode = LinkListNodeCreat(e); //这里先创建一个名叫NewNode的新结点

    NewNode->next = L->next;//将头结点中指针域的值赋给新结点的指针域中   PS:此时头结点的指针域有两种情况   1.头结点后无节点，此时相当于将NULL赋给新节点的指针域   2.头结点的指针域指向原链表的第一个结点，此时将头结点的指针域的值赋给新结点指针域，让新结点指针域指向原链表的第一个结点
    L->next = NewNode;//再将新结点指针域的值赋给头结点的指针域，使头结点的下一个结点为新结点

    return OK;
}
//*************************************************
//输入函数
int LinkListInput(LinkListNode *L)
{
    int i = 0,ElemNum = 0,Element = 0;
    printf("请输入要插入结点的个数：\n");  //插入多少个循环多少次
    scanf("%d",&ElemNum);
    printf("请输入链表当中的元素：\n");
    for(i=0 ;i<ElemNum;i++)
    {
        scanf("%d",&Element);
        LinkListHeadInsert(L,Element); //直接调用头插法函数，头插法在调用创建结点
    }
    return OK;
}
//*************************************************
//输出函数
int LinkListPrint(LinkListNode *L)
{
    if(L->next==NULL)            //判断头结点是否为空，是则不打印
    {
        printf("当前链表为空\n");
        system("pause");
        return 0;
    }
    LinkListNode *pTmp = L->next;//将pTmp的地址赋值为第一个结点的地址,若没有结点则为NULL
    printf("当前链表元素为：\n");
    while (pTmp)                 //判断是否有结点
    {
        printf("%d ",pTmp->data);//打印出数据域的值
        pTmp = pTmp->next;       //位移至下一个结点的地址
    }
    printf("\n");
    system("pause");
    return OK;
}
//************************************************
//删除所有元素函数
int ListDelete(LinkListNode *L)
{
    if(L->next==NULL)            //判断头结点是否为空，是则无法删除
    {
        printf("当前链表无元素\n");
        system("pause");
        return FALSE;
    }
    LinkListNode *HeadTmp = L;   //将头指针的值赋给HeadTmp，作用是循环，直至空
    LinkListNode *TestTmp;       //中间过渡暂存指针
    while(HeadTmp)
    {
        TestTmp=HeadTmp;
        HeadTmp=HeadTmp->next;
        free(TestTmp);           //清除结点
    }
    L->next=NULL;                //记住这里将头结点的指针域赋值为空！！  否则使用上面的输出函数会报错，因为之后的结点已经被free了，但L还指向的是一个已经被清除的结点
    printf("删除成功！\n");
    system("pause");
    return OK;
}
//************************************************
//退出函数
int OutList(LinkListNode *L)
{
    if(L->next==NULL)
    {
        return OK;
    }
    LinkListNode *HeadTmp = L;
    LinkListNode *TestTmp;
    while(HeadTmp)
    {
        TestTmp=HeadTmp;
        HeadTmp=HeadTmp->next;
        free(TestTmp);
    }
    free(L);                        //free掉头结点
    return OK;
}
//************************************************
//菜单函数
int menu()
{
    int n;
    system("cls");
    printf("===============================链表的基本功能实现=============================\n|\t\t\t\t\t\t\t\t             |\n");
    printf("|\t    1.增添元素       2.删除所有元素       3.查看元素                 |\n");
    printf("|\t                                                                     |\n");
    printf("|\t                       +--------------+                              |\n");
    printf("|\t                       |    4.退出    |                              |\n");
    printf("|\t                       +--------------+                              |\n");
    printf("==============================================================================\n");
    printf("请输入指令[1-4]:");
    scanf("%d",&n);
    return n;
}

int main()
{
    int n;
    LinkListNode *L = LinkListNodeCreat(0);//创建头结点L,头指针(及为头结点的地址)
    do
    {
        n=menu();
        switch(n)
        {
            case 1:
            LinkListInput(L);
            break;
            case 2:
            ListDelete(L);
            break;
            case 3:
            LinkListPrint(L);
            break;
        }
    }
    while(n!=4);
    OutList(L);              //退出函数
    printf("退出成功!\n");
    system("pause");
    return 0;
}

最后：
链表属于数据结构中较简单的内容，学起来不难的,理解了之后就很容易了,不要被那些人说的吓到了。笔者目前计算机大一在读，水平有限，所写仅供参考学习，如有错误，请在评论区指正、讨论。ps:愿本萌新在以后的学习能多点思考不受禁锢，知识的学习也能跟得上发际线上移的速度~

；原文链接：https://blog.csdn.net/qq_51527951/article/details/115531195
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！

上一篇：PhpStorm+Xdebug开启PHP调试 下一篇：没有了

随机推荐

jquery实现拖拽添加元素功能

本文实例为大家分享了jquery实现拖拽添加元素的具体代码，供大家参考，具体内容...
PHP高级编程之消息队列原理与实现方法详

本文实例讲述了PHP高级编程之消息队列原理与实现方法。分享给大家供大家参考，具...
加粗<b>与<strong&

我们各位站长都知道在做网站优化的时候，文章的关键字加粗对优化是有极大的好处...
微软为 Edge 浏览器测试桌面小工具等功能

IT之家2月16日消息据外媒 WindowsLatest 消息，微软将在 Edge 浏览器的下个更新...
git设置用户名密码的示例代码

git设置用户名密码设置git用户名／邮箱 git config --global user.name [userna...
即时通讯软件在网页上启动临时对话的链接

旺旺临时对话的链接: wangwang:SendIM?对方的账号uid_t=对方的账号suid=自己的账...
php验证用户名是否以字母开头与验证密码

本文实例讲述了php验证用户名是否以字母开头与验证密码的方法。分享给大家供大家...
JSP自定义标签-标签属性_动力节点Java学

对自定义标签添加一些属性，可以使我们的标签功能更加灵活和复用。例如前一篇博...
巧用计划任务：为 Windows 10 添加定时备

前言由于最近在准备毕业设计，文件需要经常备份，为了防止误操作导致文件错误或...
还不懂分表分库？这篇文章值得阅读

一、数据库瓶颈不管是IO瓶颈，还是CPU瓶颈，最终都会导致数据库的活跃连接数增...

单链表全解(从零开始)——数据结构(C语言)

数据结构（C语言）——单链表的创建及基本功能的实现

1. 链表类型

2. 单链表的定义

3.单链表的存储结构

4.学习单链表须弄明白的一些基本概念

5.代码部分

推荐图文

web服务器程序运行出现乱码问题的解决方法

使用XSLT将XML数据转换成HTML

看完这篇，你就理解数据库并发控制了

面试记录贴

asp MD5加密方式使用建议

ADI最新基带处理芯片 ADRV9026, 4通道MIMO基带芯片

随机推荐

jquery实现拖拽添加元素功能

PHP高级编程之消息队列原理与实现方法详

加粗<b>与<strong&

微软为 Edge 浏览器测试桌面小工具等功能

git设置用户名密码的示例代码

即时通讯软件在网页上启动临时对话的链接

php验证用户名是否以字母开头与验证密码

JSP自定义标签-标签属性_动力节点Java学

巧用计划任务：为 Windows 10 添加定时备

还不懂分表分库？这篇文章值得阅读

关于我们