链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)

简介: 在上一篇文章中,我们探索了顺序表这一基础的数据结构,它提供了一种有序存储数据的方法,使得数据的访 问和操作变得更加高效。想要进一步了解,大家可以移步于上一篇文章:探索顺序表:数据结构中的秩序之美今天,我们将进一步深入,探讨另一个重要的数据结构——链表链表和顺序表一样,都属于线性表,也用于存储数据,但其内部结构和操作方式有着明显的不同。通过C语言的具体实现,我们将会更加直观地理解它

在上一篇文章中,我们探索了顺序表这一基础的数据结构,它提供了一种有序存储数据的方法,使得数据的访 问和操作变得更加高效。想要进一步了解,大家可以移步于上一篇文章:探索顺序表:数据结构中的秩序之美

今天,我们将进一步深入,探讨另一个重要的数据结构——==链表==

链表和顺序表一样,都属于线性表,也用于存储数据,但其内部结构和操作方式有着明显的不同。通过C语言的具体实现,我们将会更加直观地理解它

源码可以打我的gitee里面查找:唔姆/比特学习过程2 (gitee.com)


[TOC]


一.链表的概念及结构

Snipaste_2023-12-18_19-32-10.png

链表是一种物理存储(实际上)结构上==非连续、非顺序==(杂乱随意排序)的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的

实际情况中:

Snipaste_2023-12-18_19-42-49.png

从上图可发现:

  1. 链表在逻辑上连续,在物理上是不连续的
  2. 各个节点(Node)一般都是从==堆==上面申请空间的
  3. 从堆上面申请的空间是有一定策略的,可能连续,可也能不连续

二.链表的分类

  • 单向或者双向

Snipaste_2023-12-18_20-20-19.png

>

  • 带头或者不带头

Snipaste_2023-12-18_20-24-52.png

>

  • 循环或者非循环

Snipaste_2023-12-18_20-25-02.png

>

三种情况随意组合起来就有==8种链表结构==

其中,最为常用的是:

无头单向非循环带头双向循环

Snipaste_2023-12-18_21-12-23.png

无头单向非循环链表:结构简单,但是一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等

Snipaste_2023-12-18_20-31-59.png

带头双向循环链表:结构最复杂,一般用在==单独存储数据==。实际中使用的链表数据结构,都是带头双向循环链表。这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现它反而简单了

这两种结果都会给大家实现的,今天先来==无头单向非循环链表==


三.无头单向非循环链表的实现

1.项目文件规划

Snipaste_2023-12-18_21-58-53.png

  • 头文件SList.h:用来基础准备(常量定义,typedef),链表表的基本框架,函数的声明
  • 源文件SList.h:用来各种功能函数的具体实现
  • 源文件test.c:用来测试功能是否有问题,进行基本功能的使用

2.基本结构及功能一览

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int SLDataType;

typedef struct SingleListNode
{
   
   
    int data;
    SingleListNode* next;
}SLNode;

void SLPrint(SLNode* phead);// 单链表打印

void SLPushBack(SLNode** pphead, int n);// 单链表尾插
void SLPushFront(SLNode** pphead, int n);// 单链表头插
void SLPopBack(SLNode** pphead);// 单链表尾删
void SLPopFront(SLNode** pphead);// 单链表尾删

SLNode* SLFind(SLNode* phead, int n);
SLNode* SLInsert(SLNode** pphead, SLNode* pos, int n);//在pos前面插入
SLNode* SLErase(SLNode** pphead, SLNode* pos);//删除pos前面那个

void SLInsertAfter(SLNode* pos, int n);//在pos后面插入
void SLEraseAfter(SLNode* pos);//在pos后面删除

void SLDestory(SLNode** pphead);

3.各功能接口具体实现

3.1打印单链表

void SLPrint(SLNode* phead)
{
   
   
    assert(phead);
    SLNode* cur = phead;
    while (cur != NULL)//与while(cur)同样的效果
    {
   
   
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

3.2尾插

SLNode* CreateNode(int n)
{
   
   
    SLNode* newNode= (SLNode*)malloc(sizeof(SLNode));
    if (newNode == NULL)
    {
   
   
        perror("malloc error");
        return -1;
    }
    newNode->data = n;
    newNode->next = NULL;
    return newNode;
}

void SLPushBack(SLNode** pphead, int n)
{
   
   
    assert(pphead);

    SLNode* newNode = CreateNode(n);//先把节点搞好
    //先考虑一下没有节点的情况
    if (*pphead == NULL)
    {
   
   
        *pphead = newNode;  //这就是传二级指针的原因:
                           //我们要改变 SLNode* phead本身的指向,就把他地址传过来
                          //当我们只是要改变指向的结构体里的内容时只要传SLNode* phead就行了
    }
    else
    {
   
   
        SLNode* tail = *pphead;
        while (tail->next != NULL)//找到最后一个节点
        {
   
   
            tail = tail->next;
        }
        tail->next = newNode;
    }
}
  1. 通过 CreateNode 函数创建了一个含有数值 n 的新节点 newNode
  2. 然后根据链表是否为空进行不同的操作:
  • 如果链表为空(即头指针指向空),则将新节点 newNode 赋值给头指针 *pphead
  • 如果链表不为空,则==需要找到链表末尾==的节点,通过遍历找到最后一个节点(tail),并将其 next 指针指向新节点 newNode,以将新节点插入到链表的末尾

为什么传入二级指针:

这种设计方式的原因在于需要修改指针本身的值,而不是只修改指针所指向的内容

考虑到单链表在插入节点时,可能会涉及链表头指针的修改,如果直接传递单级指针(指向头指针),在函数内部对头指针进行修改是不会反映到函数外部的==(形参是实参的临时拷贝)==。但如果使用二级指针,可以在函数内部修改指针的指向,这样修改后的指向会在函数外部保持

Snipaste_2023-12-19_21-13-28.png

3.3头插

void SLPushFront(SLNode** pphead, int n)
{
   
   
    assert(pphead);

    SLNode* newNode = CreateNode(n);//先把节点搞好
    if (*pphead == NULL)
    {
   
   
        *pphead = newNode;
    }
    else
    {
   
   
        newNode->next = (*pphead)->next;
        (*pphead)->next = newNode;
    }
    //或者
    //newNode->next = (*pphead);
    //*pphead = newNode;
}
  1. 通过 CreateNode 函数创建了一个含有数值 n 的新节点 newNode
  2. 接着,根据链表是否为空进行不同的操作:
    • 如果链表为空(即头指针指向空),则将新节点 newNode 赋值给头指针 *pphead
    • 如果链表不为空,则将新节点 newNodenext 指针指向当前头节点的下一个节点(原链表的第二个节点),然后将当前头节点的 next 指针指向新节点 newNode,以完成插入

注释部分显示了另一种写法,通过先设置新节点的 next 指针指向当前头节点,然后再将链表的头指针指向新节点,实现了同样的插入操作

Snipaste_2023-12-19_23-38-00.png

3.4尾删

void SLPopBack(SLNode** pphead)
{
   
   
    assert(pphead);
    assert(*pphead);//防止一个都没有还删
    if ((*pphead)->next == NULL)//只有一个
    {
   
   
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
   
   
        //找到倒数第二个
        SLNode* pre_tail = *pphead;
        while (pre_tail->next->next != NULL)
        {
   
   
            pre_tail = pre_tail->next;
        }
        free(pre_tail->next);
        pre_tail->next = NULL;
    }
}
  1. 检查链表头指针 *pphead 是否存在(不为 NULL),以及链表是否为空(只有一个节点)
    • 如果链表中只有一个节点,则直接释放该节点,并将链表头指针设置为 NULL,表示链表为空
    • 如果链表中有多个节点,则会==找到倒数第二个节点==,即指向最后一个节点的前一个节点。它通过遍历链表直到找到倒数第二个节点 pre_tail,然后释放最后一个节点,并将倒数第二个节点的 next 指针设置为 NULL,表示该节点成为新的末尾节点

3.5头删

void SLPopFront(SLNode** pphead)
{
   
   
    assert(pphead);
    assert(*pphead);//防止一个都没有还删

    SLNode* first = (*pphead)->next;//一个和多个都适用
    free(*pphead);
    *pphead = first;
}
  1. 创建了一个临时指针 first 来指向原链表的第二个节点(如果存在)。这是因为要删除的是链表的头节点,为了不断开链表,需要先保存第二个节点的地址
  2. 通过 free(*pphead) 释放掉原来的头节点,然后将链表的头指针 *pphead 更新为原头节点的下一个节点 first

3.6查找

SLNode* SLFind(SLNode* phead, int n)
{
   
   
    assert(phead);
    SLNode* cur = phead;
    while (cur != NULL)//与while(cur)同样的效果
    {
   
   
        if (cur->data == n)
        {
   
   
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

3.7插入pos前一个

void SLInsert(SLNode** pphead, SLNode* pos, int n)//在pos前面插入
{
   
   
    assert(pphead);
    assert(pos);
    SLNode* cur = *pphead;
    if (*pphead == pos)//在第一个节点前面插入
    {
   
   
        // 头插
        SLTPushFront(pphead, n);
    }
    else
    {
   
   
        while (cur->next != pos)
        {
   
   
            cur = cur->next;
        }
        SLNode* newNode = CreateNode(n);
        newNode->next = cur->next;
        cur->next = newNode;
    }
}
  • 如果要插入的位置 pos 就是链表的头节点 *pphead,即在==第一个节点前面插入==,则调用 SLTPushFront 函数,直接在链表头部插入新节点 newNode
  • 如果要插入的位置不是头节点,则通过循环遍历链表,直到找到 pos 的==前一个节点== cur,然后创建新节点 newNode 并将其插入到 pos 前面,完成节点的插入操作

3.8删除pos前一个

void SLErase(SLNode** pphead, SLNode* pos)
{
   
   
    assert(pphead);
    assert(pos);
    assert(*pphead != pos);//防止前面没有
    SLNode* cur = *pphead;
    SLNode* pre_cur = *pphead;
    while (cur->next != pos)
    {
   
   
        pre_cur = cur;
        cur = cur->next;
    }
    pre_cur->next = pos;
    free(cur);
    cur = NULL;
}

3.9插入pos后一个

void SLInsertAfter(SLNode* pos, int n)
{
   
   
    assert(pos);
    SLNode* newNode =CreateNode(n);
    newNode->next = pos->next;
    pos->next = newNode;
}
  1. 创建一个新节点 newNode,并将新节点的 next 指针指向 pos 节点原本的下一个节点,以保证链表的连续性
  2. pos 节点的 next 指针指向新节点 newNode,完成了在指定节点之后插入新节点的操作

3.10删除pos后一个

void SLEraseAfter(SLNode* pos)
{
   
   
    assert(pos);
    SLNode* next = pos->next->next;
    free(pos->next);
    pos->next = NULL;
    pos->next = next;
}

3.11销毁(避免内存泄露)

void SLDestory(SLNode** pphead)
{
   
   
    assert(pphead);
    SLNode* cur = *pphead;
    SLNode* next = *pphead;
    while (cur!=NULL)
    {
   
   
        next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

循环删除每一个Node,最后把原本的结构体指针指向NULL


好啦,这次知识就先到这里啦!下一次大概率是双向带头循环的代码实现了。

目录
相关文章
|
11月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
883 9
|
9月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
11月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
396 16
|
11月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
201 4
|
12月前
|
存储 自然语言处理 编译器
C语言编译和链接
C语言编译和链接
68 1
C语言编译和链接
|
11月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
690 8
|
11月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
822 4
|
11月前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
283 3
|
12月前
|
自然语言处理 编译器 Linux
C语言中抽象的编译和链接原理
C语言中抽象的编译和链接原理
89 1
|
12月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装,包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
96 0