C语言之单链表的实现以及链表的介绍

这篇具有很好参考价值的文章主要介绍了C语言之单链表的实现以及链表的介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、为什么会存在链表

因为我们常用的顺序表会存在以下的一些问题:

1. 中间/头部的插入删除,时间复杂度为O(N)
2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到
200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

针对以上顺序表中存在的问题,有人就设计出了链表这一结构。下面我将就链表中结构最简单的单链表做一个详细的介绍。

二、链表的介绍

2.1链表的概念和结构

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

结构:链表逻辑图和物理图的结合

C语言之单链表的实现以及链表的介绍

 从上图我们可以看出:链表的每一个结点都包含数据域和指针域,头结点存储的是第一个节点的地址,最后一个节点的指针域为空指针。从逻辑图上看,就好像每个结点间都有箭头指向下一个结点,从物理图上来看,就是因为每个结点都存储了下一个结点的地址。在链表的结构中需要注意的是:

1.从上图可以看出,链式结构在逻辑上是连续的,但是在物理上不一定连续。

2.现实中的结点一般都是在堆上申请出来的。

3.从堆上申请的空间,是按照一定策略来分配的,两次申请的空间可能连续也可能不连续。

2.2链表的分类

1.单向或双向

C语言之单链表的实现以及链表的介绍

2.带头或不带头

C语言之单链表的实现以及链表的介绍

3.循环或非循环

C语言之单链表的实现以及链表的介绍

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

C语言之单链表的实现以及链表的介绍

三、单链表的实现

见以下代码:


#pragma once
#include <stdio.h>
#include <stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;

//打印链表的数据域的内容
void SListPrint(SLTNode* phead);

//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x);

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x);

//尾删
void SListPopBack(SLTNode** pphead);

//头删
void SListPopFront(SLTNode** pphead);

//查找/修改结点的值
SLTNode* SListFind(SLTNode* phead, SLTDateType x);

//在pos位置之前插入一个结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

//在pos位置之后插入一个结点
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x);

//删除pos结点
void SListErase(SLTNode** pphead, SLTNode* pos);

//删pos的后一个结点
void SListEraseAfter(SLTNode* pos);

//销毁链表
void SListDestrory(SLTNode** pphead);
#include "Slist.h"

//创建一个新结点
SLTNode* BuyListNode(SLTDateType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

//打印链表的数据域的内容
void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur != NULL)
    {
        printf("%d->", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

//尾插
void SListPushBack(SLTNode** pphead, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next != NULL)
        {
            tail = tail->next;//找到最后一个结点
        }
        tail->next = newnode;
    }
    
}

//头插
void SListPushFront(SLTNode** pphead, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

//尾删
void SListPopBack(SLTNode** pphead)
{
    if (*pphead == NULL)
    {
        return;//链表为空直接返回
    }
    if ((*pphead)->next == NULL)//头结点就是尾节点
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* tail = *pphead;
        SLTNode* prev = NULL;//最后会走到倒数第二个结点
        while (tail->next != NULL)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        prev->next = NULL;
    }
}

//头删
void SListPopFront(SLTNode** pphead)
{
    if (*pphead == NULL)//链表为空直接返回
    {
        return;
    }
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;//头结点指向原来的第二个结点
}

//查找x出现的结点
SLTNode* SListFind(SLTNode* phead, SLTDateType x)
{
    SLTNode* cur = phead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        else
        {
            cur = cur->next;
        }
    }
    return NULL;
}

//在pos位置之前插入一个结点
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    if (*pphead == pos)//头结点就是pos的位置
    {
        //头插
        newnode->next = *pphead;
        *pphead = newnode;
    }
    //找到pos前一个位置
    else
    {
        SLTNode* posPrev = *pphead;
        while (posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = newnode;
        newnode->next = pos;
    }
}

//在pos位置之后插入一个结点
void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
    SLTNode* newnode = BuyListNode(x);
    //以下两行代码的顺序不能调换,若调换会形成类似互指的问题
    newnode->next = pos->next;
    pos->next = newnode;
}

//删除pos结点
void SListErase(SLTNode** pphead, SLTNode* pos)
{
    if (*pphead == pos)//头删
    {
        SListPopFront(pphead);
    }
    else
    {
        SLTNode* prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
        }
        prev->next = pos->next;
        free(pos);
    }
}

//删除pos结点后的一个结点
void SListEraseAfter(SLTNode* pos)
{
    SLTNode* next = pos->next;
    pos->next = next->next;
    free(next);
    next = NULL;
}

//销毁链表
void SListDestrory(SLTNode** pphead)
{
    SLTNode* cur = *pphead;
    while (cur)
    {
        SLTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}
#include "Slist.h"


void TestSList()
{
    SLTNode* plist = NULL;
    //尾插结点
    SListPushBack(&plist, 1);
    SListPushBack(&plist, 2);
    SListPushBack(&plist, 3);
    SListPushBack(&plist, 4);
    SListPrint(plist);

    //头插结点
    SListPushFront(&plist, 1);
    SListPushFront(&plist, 2);
    SListPushFront(&plist, 3);
    SListPushFront(&plist, 4);
    SListPrint(plist);

    //尾删结点
    SListPopBack(&plist);
    SListPopBack(&plist);
    SListPrint(plist);

    //头删结点
    SListPopFront(&plist);
    SListPrint(plist);

    //查找数值2出现的结点
    SLTNode* pos = SListFind(plist, 2);
    int i = 1;
    while (pos)
    {
        printf("第%d个pos结点:%p->%d\n", i++, pos, pos->data);
        pos = SListFind(pos->next, 2);
    }

    //在pos2结点前插入一个结点
    SLTNode* pos2 = SListFind(plist, 1);
    if (pos2)
    {
        SListInsert(&plist, pos2, 30);
    }
    SListPrint(plist);

    //在pos3结点后插入一个结点
    SLTNode* pos3 = SListFind(plist, 3);
    if (pos3)
    {
        SListInsertAfter(&plist, pos3, 20);
    }
    SListPrint(plist);

    //删除pos4结点
    SLTNode* pos4 = SListFind(plist, 2);
    SListErase(&plist, pos4);
    SListPrint(plist);

    //删除pos5结点的后一个结点
    SLTNode* pos5 = SListFind(plist, 3);
    SListEraseAfter(pos5);
    SListPrint(plist);

    //销毁链表
    SListDestrory(&plist);
}

int main()
{
    TestSList();
    return 0;

}

注:有人可能会不明白为什么有的参数传的是二级指针。当你需要对链表进行修改时,参数就需要传二级指针。如果需要对链表进行修改而你传参用的是一级指针,那么就相当于是形参重新开辟了一块空间来存放传过来的一级指针中的值。那么你在函数中对新开辟的空间中做修改就不会改变实参。如果需要在函数中对一级指针做修改,形参就需要传二级指针。文章来源地址https://www.toymoban.com/news/detail-429430.html

到了这里,关于C语言之单链表的实现以及链表的介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第1关:单循环链表的实现—链表的添加、遍历任务描述相关知识单循环链表添加操作遍历循环链表编程要求测试说明任务描述在操作单链表时,

    第1关:单循环链表的实现—链表的添加、遍历 200 任务要求 参考答案 评论42 任务描述 相关知识 单循环链表 添加操作 遍历循环链表 编程要求 测试说明 任务描述 在操作单链表时,我们有时希望从单链表中的任一结点出发都能遍历整个链表,但对于单链表来说,只有从头结点

    2024年02月06日
    浏览(47)
  • 解决单链表的缺陷:C 语言版实现

    本文介绍了单链表的概念、结构、分类以及 C 语言中的实现。单链表是一种非连续、非顺序的存储结构,通过指针链接实现数据元素的逻辑顺序。

    2024年02月04日
    浏览(44)
  • 数据结构:单链表的实现(C语言)

    个人主页 : 水月梦镜花 个人专栏 : 《C语言》 《数据结构》 本博客将要实现的无头单向不循环链表。 我们将节点定义为如下结构: 其成员变量有data,next。 将int重命名为STLDataType,方便我们以后修改数据域的内容。 动态申明一个空间,来放置数据。如下: 将data的内容置

    2024年02月14日
    浏览(59)
  • 数据结构——单链表的实现(c语言版)

    前言           单链表作为顺序表的一种,了解并且熟悉它的结构对于我们学习更加复杂的数据结构是有一定意义的。虽然单链表有一定的缺陷,但是单链表也有它存在的价值, 它也是作为其他数据结构的一部分出现的,比如在图,哈希表中。 目录 1.链表节点的结构 2.头插

    2024年02月13日
    浏览(60)
  • 基于单链表的通讯录C语言实现

     关于单链表的详细了解请见博主的另一篇博客,本文旨在对单链表进行应用,采用C语言编写。

    2024年04月15日
    浏览(55)
  • 单链表的基本操作代码实现(C语言版)

    目录 前言: 单链表的基本操作 准备工作(头文件、各种宏定义以及结构体定义) 一.较简单操作 1.单链表的初始化 2.判断单链表是否为空表 3.单链表的销毁 4.单链表的清空 5.求单链表的表长 二.较重要操作 1.单链表的取值 2.单链表元素的查找 3.单链表的结点插入 4.单链表的结

    2024年04月11日
    浏览(42)
  • 数据结构上机练习——单链表的基本操作、头文件、类定义、main函数、多种链表算法的实现,含注释

      头文件和源文件分开有很多好处:可以提高编译速度、提高代码的可维护性、提高代码的可重用性和可扩展性,同时也可以使代码结构更清晰,方便代码的管理和维护。 LinkList.h test.cpp                  (下面所有函数都默认在类中实现)   我们以

    2024年02月07日
    浏览(58)
  • 【数据结构】反转链表、链表的中间节点、链表的回文结构(单链表OJ题)

    正如标题所说,本文会图文详细解析三道单链表OJ题,分别为:  反转链表 (简单)  链表的中间节点 (简单)  链表的回文结构 (较难) 把他们放在一起讲的原因是:  反转链表 和  链表的中间节点 是  链表的回文结构 的基础 为什么这样说?请往下看: 目录 1. 反转链

    2024年02月13日
    浏览(72)
  • 【数据结构】单链表的增删查改(C语言实现)

    在上一节中我们提到了顺序表有如下缺陷: 在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低; 增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗; 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容

    2024年02月06日
    浏览(62)
  • 【数据结构】C语言实现单链表的基本操作

    大家好,很高兴又和大家见面啦!!! 在上一篇中,我们详细介绍了单链表的两种创建方式——头插法与尾插法,相信大家现在对这两种方式都已经掌握了。今天咱们将继续介绍单链表的基本操作——查找、插入与删除。在开始今天的内容之前,我们先通过尾插法创建一个单

    2024年02月03日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包