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

数据结构——链表

时间：2024-08-27 21:23:30浏览次数：7  
标签：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中的基本数......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99