首页 > 其他分享 >数据结构——链表

数据结构——链表

时间:2024-08-27 21:23:30浏览次数:12  
标签:NODE head return 链表 数据结构 data 节点

单链表

基本概念

  • 顺序表:顺序存储的线性表。
  • 链式表:链式存储的线性表,简称链表。

既然顺序存储中的数据因为挤在一起而导致需要成片移动,那很容易想到的解决方案是将数据离散地存储在不同内存块中,然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表,就是所

谓的链表。

顺序表和链表在内存在的基本样态如下图所示:

请添加图片描述

链表的分类

根据链表中各个节点之间使用指针的个数,以及首尾节点是否相连,可以将链表细分为如下种类:

  1. 单向链表
  2. 单向循环链表
  3. 双向循环链表

这些不同链表的操作都是差不多的,只是指针数目的异同。以最简单的单向链表为例,其基本示意图

如下所示:

请添加图片描述

上图中,所有的节点均保存一个指针,指向其逻辑上相邻的下一个节点(末尾节点指向空)。另外注

意到,整条链表用一个所谓的头指针 head 来指向,由 head 开始可以找到链表中的任意一个节点。

head 通常被称为头指针。

链表的基本操作,一般包括:

  1. 节点设计
  2. 初始化空链表
  3. 增删节点
  4. 链表遍历
  5. 销毁链表

下面着重针对这几项常见操作,讲解单向链表的处理。

单链表节点设计

单向链表的节点非常简单,节点中除了要保存用户数据之外(这里以整型数据为例),只需要增加一

个指向本类节点的指针即可,如下所示:

typedef int DATA;
typedef struct Node
{
    DATA data; // 存储数据---数据域
    struct Node *next; // 存储下一个节点的地址---指针域
} NODE;

单链表初始化

首先,空链表有两种常见的形式。一种是带所谓的头结点的,一种是不带头结点的。所谓的头结点是

不存放有效数据的节点,仅仅用来方便操作,如下:

请添加图片描述

而不带头结点的空链表如下所示:

请添加图片描述

注意:

  • 头指针 head 是必须的,是链表的入口
  • 头节点是可选的,为了方便某些操作

由于头结点是不存放有效数据的,因此如果空链表中带有头结点,那么头指针 head 将永远不变,这会给以后的链表操作带来些许便捷。

下面以带头结点的链表为例,展示单向链表的初始化的示例代码:

int slist_create(NODE** head,DATA data)
{
    NODE* p = (NODE*)malloc(sizeof(NODE));
    if(!p)
    {
        return -1;
    }
    p -> data = data;
    p -> next = NULL;
    *head = p;
    return 0;
}

单链表增删节点

相对于顺序表需要整片移动数据,链表增删节点只需要修改几个相关指针的指向,动作非常快速。与顺序表类似,可以对一条链表中的任意节点进行增删操作,示例代码是:

int slist_addHead(NODE **head, DATA data)
{
    NODE *p = (NODE *)malloc(sizeof(NODE));
    if (!p)
    {
        return -1;
    }
    p->data = data;
    p->next = *head;
    *head = p;
    return 0;
}
int slist_addTail(NODE **head, DATA data)
{
    NODE *pNew = (NODE *)malloc(sizeof(NODE));
    if (!pNew)
    {
        return -1;
    }
    pNew->data = data;
    pNew->next = NULL;
    NODE *p = *head, *q = NULL;
    if (!p)
    {
        *head = pNew;
        return 0;
    }
    while (p)
    {
        q = p;
        p = p->next;
    }
    q->next = pNew;
    return 0;
}
int slist_insert(NODE **head, DATA pos, DATA data)
{
    NODE *pNew = (NODE *)malloc(sizeof(NODE));
    if (!pNew)
        return -1;
    pNew->data = data;
    pNew->next = NULL;
    NODE *p = *head, *q = NULL;
    if (!p)
    {
        *head = pNew;
        return 0;
    }
    if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0)
    {
        pNew->next = *head;
        *head = pNew;
        return 0;
    }
    while (p)
    {
        if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0)
        {
            pNew->next = p;
            q->next = pNew;
            return 0;
        }
        q = p;
        p = p->next;
    }
    q->next = pNew;
    return 0;
}
int slist_update(const NODE *head, DATA old, DATA newdata)
{
    NODE *p = NULL;
    if (!(p = slist_find(head, old)))
        return -1;
    p->data = newdata;
    return 0;
}
int slist_delete(NODE **head, DATA data)
{
    NODE *p = *head, *q = NULL;
    if (!p)
        return -1;
    if (memcmp(&(p->data), &data, sizeof(DATA)) == 0)
    {
        *head = p->next;
        free(p);
        return 0;
    }
    while (p)
    {
        if (memcmp(&(p->data), &data, sizeof(DATA)) == 0)
        {
            q->next = p->next;
            free(p);
            return 0;
        }
        q = p;
        p = p->next;
    }
    return -1;
}

注意:

删除链表的节点并不意味着释放其内存,而是将其剔除出链表

单链表的遍历

遍历的意思就是逐个访问每一个节点,对于线性表而言,由于路径唯一的选择就是从头走到尾。因此相当而言比较简单。

下面是单向链表的遍历示例代码,假设遍历每个节点并将其整数数据输出:

NODE* slist_find(const NODE* head,DATA data)
{
    const NODE* p = head;
    while(p)
    {
        if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
    {
        return (NODE*)p;
    }
    p = p -> next;
    }
    return NULL;
}
void slist_showAll(const NODE* head)
{
    const NODE* p = head;
    while(p)
    {
        printf("%d ",p -> data);
        p = p -> next;
    }
    printf("\n");
}

单链表的销毁

由于链表中的各个节点被离散地分布在各个随机的内存空间,因此销毁链表必须遍历每一个节点,释放每一个节点。

注意:

销毁链表时,遍历节点要注意不能弄丢相邻节点的指针

void slist_destroy(NODE** head)
{
    NODE* p = *head, *q = NULL;
    while(p)
    {
        q = p;
        p = p -> next;
        free(q);
    }
    *head = NULL;
}

完整代码

  • singList.h
#ifndef __SEQLIST_H
#define __SEQLIST_H

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

// 定义顺序表的结构体
typedef struct
{
    int capacity;// 顺序表的容量(顺序表本质上是数组)
    int last;    // 末元素的下标
    int *data;   // 数据,其实是一个存放多个int的容器
} seqList;

// 创建顺序表(顺序表的初始化)
seqList *initList(int cap);

// 向顺序表的表头插入一个新数据
bool insert(seqList *list,int data);

// 判断顺序表是否满了
bool isFull(seqList *list);

// 遍历顺序表中的元素
void show(seqList *list);

// 将顺序表中指定的某个元素删除
bool removeNode(seqList *list,int data);

// 销毁顺序表
void destroy(seqList *s);
#endif

slist.c

#include "slist.h"

/*
@function:   int slist_create(NODE** head,DATA data);
@berif:      创建单项链表
@argument:   head: 指向头指针变量的地址,用来接收首节点地址
             data: 存储在节点中的数据
@return :    成功返回 0
             失败返回 -1
*/
int slist_create(NODE **head, DATA data)
{
    // 申请内存
    NODE *p = (NODE *)malloc(sizeof(NODE));
    // 校验
    if (!p)
    {
        return -1;
    }
    // 赋值操作
    p->data = data;
    p->next = NULL;

    *head = p;

    return 0;
}

/*
@function:   int slist_addHead(NODE** head,DATA data);
@berif:      向链表头部插入一个节点数据(头插法)
@argument:   head: 指向头指针变量的地址,用来接收首节点地址
             data: 存储在新节点中的数据
@return :    成功返回 0
             失败返回 -1
*/
int slist_addHead(NODE **head, DATA data)
{
    // 创建一个新节点(申请内存)
    NODE *p = (NODE *)malloc(sizeof(NODE));
    // 校验
    if (!p)
    {
        return -1;
    }
    // 给节点添加新数据(创建节点的目的是存储数据)
    p->data = data;
    // 新节点指向原本的head节点
    p->next = *head;

    // 我们要让p作为我们新的head
    *head = p;

    return 0;
}

/*
@function:   int slist_addTail(NODE** head,DATA data);
@berif:      向链表尾部插入一个节点数据(尾插法)
@argument:   head: 指向头指针变量的地址,用来接收首节点地址
             data: 存储在新节点中的数据
@return :    成功返回 0
             失败返回 -1
*/
int slist_addTail(NODE **head, DATA data)
{
    // 创建一个新节点(申请内存)
    NODE *pNew = (NODE *)malloc(sizeof(NODE));
    // 校验
    if (!pNew)
    {
        return -1;
    }

    // 赋值操作
    pNew->data = data; // 存数据
    pNew->next = NULL; // 因为是最后一个节点,所有没有指向

    // 获取尾部节点,默认head头结点就是尾结点,p用来保存真实的尾结点
    NODE *p = *head, *q = NULL;
    if (!p)
    {
        // 如果说头节点不存在,我们直接将新节点作为头结点,一般不会发生
        *head = pNew;
        return 0;
    }

    // 通过一个循环,找尾结点
    while (p)
    {
        // 为什么要定义q,因为p是在变化的
        q = p;
        p = p->next;// 指针向下指
    }

    // 让原本的尾结点指向新插入的的节点,此时新插入的节点变成了尾结点
    q->next = pNew;
    

    return 0;
}


/*
@function:   int slist_insert(NODE** head,DATA pos ,DATA data);
@berif:      向链表节点值为pos的位置插入一个节点数据data
@argument:   head: 指向头指针变量的地址
             pos:  插入节点位置的节点数据
             data: 存储在新节点中的数据
@return :    成功返回 0
             失败返回 -1
*/
int slist_insert(NODE** head,DATA pos,DATA data)
{
    // 创建一个新节点,并申请内存
    NODE *pNew = (NODE*)malloc(sizeof(NODE));
    if(!pNew)
    {
        perror("内存申请失败!");
        return -1;
    }
    // 给新节点赋初值
    pNew->data = data;
    pNew->next = NULL;

    // 声明变量,p是pos对应位置的节点,默认是头结点,q是pos对应节点的上一个节点
    NODE *p = *head,*q = NULL;

    // 第一种情况:头结点不存在
    if(!p)
    {
        // 新节点pNew作为头结点
        *head = pNew;
        return 0;
    }
    // 第二种情况:只有头结点
    if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0)
    {
        // 头插法
        // 新节点的next指向head节点
        pNew->next = *head;
        // 改变指向,将pNew作为新的头结点
        *head = pNew;
        return 0;
    }
    // 第三种情况:既有头结点,也有普通节点
    while (p)
    {
        // 找pos对应位置的节点
        if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0)
        {
            // pNew在p前
            pNew->next = p;
            // pNew在q后
            q->next = pNew;
            return 0;
        }
        q = p;// q在p的前一位,一前(q)一后(p)
        p = p ->next;
    }
    // 尾插法
    q->next = pNew;
    
    return 0;
}

/*
@function:   NODE* slist_find(const NODE* head,DATA data);
@berif:      查找链表数据data
@argument:   head: 指向头指针变量
             data: 待查找的数据
@return :    成功返回节点的地址
             失败返回NULL
*/
NODE* slist_find(const NODE *head,DATA data)
{
    // 创建一个变量,用来接收链表
    const NODE* p = head;

    while(p)
    {
        if(memcmp(&(p->data),&data,sizeof(DATA))==0)
        {
            return (NODE*)p;
        }
        // 移动节点
        p = p->next;
    }
    return NULL;
}

/*
@function:   int slist_update(const NODE* head,DATA old_data,DATA new_data);
@berif:      更新链表数据old_data 为 new_data
@argument:   head: 指向头指针变量
             old_data:  待更新的节点数据
             new_data: 更新后的节点数据
@return :    成功返回  0
             失败返回  -1
*/
int slist_update(const NODE* head,DATA old_data,DATA new_data)
{
    NODE* p = NULL;
    if(!(p = slist_find(head,old_data)))
    {
        return -1;
    }
    p->data = new_data;

    return 0;

}

/*
@function:   void slist_showAll(const NODE* head);
@berif:      遍历链表数据
@argument:   head: 指向头指针变量
@return :    无
*/
void slist_showAll(const NODE* head)
{
    // 创建一个变量用来接收链表
    const NODE* p = head;

    // 遍历链表
    while (p)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

/*
@function:   int slist_delete(NODE** head,DATA data);
@berif:      删除链表中节点值为data的节点
@argument:   head: 指向头指针变量的地址
             data: 删除节点中的数据
@return :    成功返回 0
             失败返回 -1
*/
int slist_delete(NODE** head,DATA data)
{
    // 指针尾随
    NODE *p = *head,*q = NULL;
    
    // 第一种情况:头结点不存在(链表本身不存在),无法操作
    if(!p)
    {
       return -1; 
    }
    // 第二种情况:只有一个节点
    if(memcmp(&(p->data),&data,sizeof(DATA)) == 0)
    {
        *head = p -> next;
        free(p);
        return 0;
    }
    // 第三种情况:有多个节点
    while (p)
    {
        if(memcmp(&(p->data),&data,sizeof(DATA)) == 0)
        {
            q->next = p->next;// p的上一个节点的next指向p的下一个节点
            // 这个回收不会影响到链表的删除
            free(p);
            return 0;
        }

        q = p;
        p = p->next;// p->next代表的是p的下一个节点,将p的下一个节点赋值给p,相当于p移动了一位
    }

    return -1;
}

/*
@function:   void slist_destroy(NODE** head);
@berif:      回收链表
@argument:   head: 指向头指针变量的地址
@return :    无
*/
void slist_destroy(NODE** head)
{
    // 指针尾随
    NODE *p = *head,*q = NULL;

    while(p)
    {
        q = p;// 12
        p = p->next;// 13
        // 回收前一个节点
        free(q);
    }
    *head = NULL;

}

链表优缺点

链式存储中,所有节点的存储位置是随机的,他们之间的逻辑关系用指针来确定,跟物理存储位置无

关,因此从上述示例代码可以很清楚看到,增删数据都非常迅速,不需要移动任何数据。另外,又由

于位置与逻辑关系无关,因此也无法直接访问某一个指定的节点,只能从头到尾按遍历的方式一个个

找到想要的节点。简单讲,链式存储的优缺点跟顺序存储几乎是相对的。

总结其特点如下:

  • 优点

    1. 插入、删除时只需要调整几个指针,无需移动任何数据

    2. 当数据节点数量较多时,无需一整片较大的连续内存空间,可以灵活利用离散的内存

    3. 当数据节点数量变化剧烈时,内存的释放和分配灵活,速度快

  • 缺点

    1. 在节点中,需要多余的指针来记录节点之间的关联。

    2. 所有数据都是随机存储的,不支持立即访问任意一个随机数据。

循环单向链表

所谓的循环,指得是将链表末尾节点循环地指向链表表头。比如,单向链表变成循环链表的示意图如下所示:

请添加图片描述

循环链表的操作跟普通链表操作基本上是一致的,只要针对循环特性稍作修改即可

标签:NODE,head,return,链表,数据结构,data,节点
From: https://blog.csdn.net/qixi_ao/article/details/141612920

相关文章

  • 数据结构学习笔记
    李超线段树学习笔记模板传送门从模板题就能看出来嗷,李超线段树非常牛逼。\bx从名字中就能看出来嗷,这玩意儿是个线段树。那么考虑在线段树上维护一堆线(一次函数)。对于每个点,存所有线中,使这个线段$mid$的点的线。对于加入一个点,根节点递归,扫到一个点时,若这个点在$mid$......
  • 算法与数据结构——哈希表
    哈希表哈希表(hashtable),又称散列表,它通过建立键key与值value之间的映射,实现高效的元素查询。具体而言,我们向哈希表中输入一个键key,则可以在O(1)时间内获取对应的值value。除哈希表外,数组和链表也可以实现查询功能,他们的效率对比如下表:添加元素:仅需将元素添加至数组(链表)的尾部......
  • 算法与数据结构——队列
    队列队列(queue)是一种遵循先入先出规则的线性数据结构。队列模拟了排队现象,即新来的人不断加入队列尾部,而队列头部的人逐个离开。如图所示,我们将队列头部称为“队首”,尾部称为“队尾”,将把元素加入队列尾部的操作称为“入队”,删除队首元素的操作称为“出队”。队列常用操作......
  • 链表-单链表的基本操作及C语言代码实现
    1.遍历单链表(打印,修改)便利的概念想必大家都不会陌生,即就是从链表的头开始,逐步向后进行每一个元素的访问,这就是遍历,对于遍历操作,我们可以衍生出很多常用的数据操作,比如说查询元素,修改元素,获取元素个数,打印整个链表数据等等。进行遍历的思路极其简单,只需要建立一个指向链表L的......
  • 链表-双向链表的基本设计(C语言代码实现)
    1.双向链表的简介&概念单链表在很多时候已经可以胜任很多优秀的操作了,但是,单链表任然存在不足,所谓‘单链表’,是指结点中只有一个指向其后继的指针,具有单向性,有时需要搜索大量数据的时候,就必须要多次进行从头开始的遍历,这样的搜索不是很便利。图:单链表示意图对此在单链表的......
  • javascript怎么实现链表?
    在JavaScript中实现链表通常涉及定义一个链表节点类(通常称为ListNode)和一个链表类(例如LinkedList),然后在这个链表类中实现各种操作链表的方法,如添加节点、删除节点、遍历链表等。以下是使用JavaScript实现单向链表的一个基本示例:链表节点类(ListNode)首先,我们定义一个链表节点......
  • 【数据结构】二叉树的顺序结构,详细介绍堆以及堆的实现,堆排序
    目录1.二叉树的顺序结构2.堆的概念及结构3.堆的实现3.1堆的结构3.2堆的初始化3.3堆的插入 3.4堆的删除3.5获取堆顶数据3.6堆的判空3.7堆的数据个数3.8堆的销毁4.堆的应用4.1堆排序4.1.1向下调整建堆的时间复杂度 4.1.2向上调整建堆的时间复杂......
  • 【数据结构篇】~链式二叉树(附源码)
    链式二叉树前言(含头文件)头文件1.链式二叉树的组成2.前、中、后、层序遍历1.前序遍历2.中序遍历3.后序遍历3.结点个数以及高度等​4.判断二叉树是否为完全二叉树前言(含头文件)之前的堆是特殊的二叉树是顺序结构的二叉树,而链式二叉树使用队列实现的。二叉树的实现大......
  • Python数据结构实战:列表、字典与集合的高效使用
    在日常的编程工作中,选择合适的数据结构对于提高程序效率至关重要。Python提供了丰富的内置数据结构,其中最常用的就是列表(List)、字典(Dictionary)和集合(Set)。本文将深入探讨这些数据结构,并介绍它们的内部实现以及如何高效地使用它们。1.列表(List)1.1定义与创建列表是......
  • Python数据结构精要:选择与应用
    数据结构是计算机科学中一个重要的概念,它涉及到如何组织和存储数据以便于高效地访问和修改。Python作为一种高级编程语言,提供了多种内置的数据结构来满足不同的需求。本文旨在介绍Python中常见的几种数据结构,并通过实例来说明它们的使用场景和优缺点。Python中的基本数......