首页 > 其他分享 >最全数据结构个人笔记【单向链表】

最全数据结构个人笔记【单向链表】

时间：2024-07-24 16:59:02浏览次数：13  
标签：node head struct 最全 pnew 链表 数据结构 节点

1.链表基本概念

链式存储的线性表，简称链表

链表其实是由一个或者多个结构体通过指针指向的关系构成
我们把每个结构体的变量称为节点,节点里面由两个成员组成
一个是数据域，另外一个是指针域，指针域是用于存放下一个节点的地址
以此类推，我们把这种存储方式称为链式存储

2.链表与顺序表差异

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

顺序表和链表在内存中基本状态如图所示：

​ 在这里插入图片描述

3.链表的分类

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

  1. 无头节点单向链表(LinkedList.c)
  2. 有头节点单向链表(LinkedListWithHead.c)

在这里插入图片描述

  1. 双向链表(BothwayLinkedList.c)
  2. 循环链表(LoopLinkedList.c)

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

在这里插入图片描述

上图中，所有的节点均保存一个指针，指向其逻辑上相邻的下一个节点（末尾节点指向空）。另外注意到，整条链表用一个所谓的头指针 head 来指向，由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针。

链表的基本操作，一般包括：

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

4.无头节点单链表节点设计

// 节点
struct node
{
	int data; //数据域 
    // 指针域，指向下一个节点(存放下一个节点的地址)
	struct node *next; 
};

在这里插入图片描述

5.节点的空间分配

​ 1.栈空间 ： 过了生命周期自动释放

​ 2.堆空间： malloc只需要保存地址即可，生命周期与程序保持一致

6.创建链表步骤

​ **1. 从无到有：**第一个节点的诞生，此时的首节点和尾节点都是它本身

​ 2 .从少到多(添加节点过程)：

​ 1. 在原来链表的后面添加新节点(尾插法)

​ 新节点接在尾节点后面，即尾节点指向新节点，原来的尾节点被新节点替代

​ 特点 ： 新接入的节点在前面，后接入的节点在后面

​ 2.在原来的链表的前面添加新节点(头插法)

​ 新节点接在原来链表的首节点前面，即新的节点指向原来的首节点，然后首节点被新节点替代

​ 特点：后接入的节点在前面，先接入的节点在后面

7.学习链表方法:

​ 一定要自己学会画图分析，再把思路转为代码，其实写代码要逻辑清晰才能写的快，切记你是怎么思考的就怎么写，没思考清除前别着急写。

demo：

​ 1.创建新节点

// 创建新节点
struct node *create_newNode(dataType data)
{
    struct node *pnew = malloc(sizeof(struct node));
    if(pnew == NULL)
        return NULL;

    // 将新数据写入到新节点
    pnew->data = data;
    pnew->next = NULL;
    return pnew;
}

2.创建新链表

// 创建新链表
struct node *create_list()
{
    dataType data;
    // 新节点指针，用于指向新节点
    struct node *pnew = NULL;
    // 指向首节点指针
    struct node *head = NULL;
    // 指向尾节点指针
    struct node *tail = NULL;

    while(1)
    {
        scanf("%d",&data);
        if(data == 0)
            break;
        
        // 创建新节点
        pnew = create_newNode(data);
        if(pnew == NULL)
        {
            perror("create newNode failed:");
            return NULL;
        }

        // 将新节点插入到链表
        if(head == NULL)// 从无到有，此时首节点和尾节点都是pnew
        {
            head = pnew;
            tail = pnew;
        }
        else // 从少到多
        {
            tail->next = pnew;
            tail = pnew;// 更新尾节点
        }
    }
    return head;
}

3.打印信息

// 打印信息
void showList(struct node *head)
{
    for(struct node *p = head; p != NULL; p = p->next)
        printf("%d  ",p->data);
    printf("\n");
}

练习：

​ 1.实现头插法

​ 2.实现链表的修改节点和删除节点

​ 3.实现链表数据在任意位置添加

8.带头节点的单向链表

1.图解

​ 在这里插入图片描述

// 定义数据节点
struct node
{
	dataType data; // 数据域
	struct node *next; // 指针域，存放(指向)下一个节点的地址
};
//-----------------------------------

// 定义头节点
struct headNode
{
	struct node *first; // 指向第一个数据节点
	struct node *last; // 指向最后一个数据节点
	int nodeNumber; // 记录链表节点数
};

demo:

创建头节点

struct headNode* create_new_headNode()
{
    struct headNode* head =  malloc(sizeof(struct headNode));
    if(head == NULL)
        return NULL;
    head->first = NULL;
    head->last = NULL;
    head->nodeNumber = 0;
    return head;
}

创建数据节点

// 创建新节点
struct node* create_new_node(dataType data)
{
    struct node* pnew =  malloc(sizeof(struct node));
    if(pnew == NULL)
        return NULL;
    pnew->data = data;
    pnew->next = NULL;
    return pnew;
}

尾插法

// 尾插法
void addTail(struct headNode *head,struct node* pnew)
{
    head->last->next = pnew;
    head->last = pnew;
}

创建链表

struct headNode* create_list()
{
    // 创建头节点
    struct headNode* head = create_new_headNode();
    if(head == NULL)
        return NULL;
    
    dataType data = -1;

    while(1)
    {
        scanf("%d",&data);
        if(data == 0)
            break;
        // 创建新节点
        struct node* pnew = create_new_node(data);
        if(pnew == NULL)
            return NULL;

        // 从无到有
        if(head->first == NULL)
        {
            head->first = pnew;
            head->last = pnew;
        }
        else // 从少到多
        {
            // 尾插法
            addTail(head,pnew);
        }
        // 更新节点
         head->nodeNumber++;
    }

    return head;
}

显示链表

void showList(struct headNode* head)
{
    if(head->first == NULL)
    {
        printf("链表为空\n");
        return;
    }
    for(struct node* p = head->first;p != head->last->next;p = p->next)
    {
        printf("%d\t",p->data);
    }
    printf("\n");
    printf("链表节点数为：%d\n",head->nodeNumber);
}
demo——带头结点单链表——汇总
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef int dataType;

// 节点结构体
struct node
{
    dataType data;
    struct node *next;
};

// 链表管理结构体
struct headNode
{
    struct node *first; // 指向有效的首节点
    struct node *last;  // 指向有效的尾节点
    int nodeNumber;     // 记录链表节点数
};

// 初始化链表管理结构体
struct headNode *init_headNode(void)
{
    struct headNode *head = malloc(sizeof(struct headNode));
    if (head == NULL)
        return NULL;

    head->first = NULL;
    head->last = NULL;
    head->nodeNumber = 0;

    return head;
}

struct node *create_newNode(dataType data)
{
    struct node *pnew = malloc(sizeof(struct node));
    if (pnew == NULL)
        return NULL;

    pnew->data = data;
    pnew->next = NULL;

    return pnew;
}

void addTail(struct headNode *head, struct node *pnew)
{

    head->last->next = pnew;
    head->last = pnew;
}
void addHead(struct headNode *head, struct node *pnew)
{

    pnew->next = head->first;
    head->first = pnew;
}

/*
* create_list : 创建链表
* 参数：
*   无
* 返回值：
*    成功： head
*    失败： NULL
*/
struct headNode *create_list(void)
{
    // 初始化头节点
    struct headNode *head = init_headNode();
    if (head == NULL)
        return NULL;

    while (1)
    {
        dataType data;
        if (scanf("%d", &data) == 0)
        {
            break;
        }

        // 创建新节点
        struct node *pnew = create_newNode(data);
        if (pnew == NULL)
            return NULL;

        if (head->first == NULL) // 从无到有
        {
            head->first = pnew;
            head->last = pnew;
        }
        else // 从少到多
        {
            
            #if 1
            addTail(head, pnew);       // 尾插法
            #else 
            add_node_head(head,pnew);  //头插法
            #endif
        }

        head->nodeNumber++;
    }

    return head;
}

// 判断链表为空
bool isEmpty(struct headNode *head)
{
    return head->nodeNumber == 0;
}

void show_list(struct headNode *head)
{
    if (isEmpty(head))
    {
        printf("此表为空\n");
        return;
    }

    for (struct node *p = head->first; p != NULL; p = p->next)
    {
        printf("%d\t", p->data);
    }
    printf("\n");
}


/*
* add_node_head : 头插法添加节点
* 参数：
*   head  ：链表管理结构体
*   data  : 插入的数据
* 返回值：
*    无
*/
void add_node_head(struct headNode *head, dataType data)
{
    struct node *pnew = create_newNode(data);

    if (head->last == NULL) // 链表为空时
    {
        head->first = pnew;
        head->last = pnew;
    }
    else
    {
        pnew->next = head->first;
        head->first = pnew;
    }

    head->nodeNumber++;

}

/*
* renew_node : 更新节点
* 参数：
*   head  ：   链表管理结构体
*   OldDate  : 待更新旧数据
*   newData  : 新数据
* 返回值：
*    无
*/
void  renew_node(struct headNode *head, dataType OldDate, dataType NewDate)
{
    if (isEmpty(head))
    {
        printf("此表为空\n");
        return;
    }

    struct node *p = head->first;
    while (p)
    {
        if (p->data == OldDate)
        {
            p->data = NewDate;
        }
        else
            p = p->next;
    }

}
/*
* add_node : 插入节点
* 参数：
*   head  ：   链表管理结构体
*   data  :    待插入数据
* 返回值：
*    无
*/
void  renew_node(struct headNode *head, dataType data)
{
    //创建新节点
    struct node *pnew = create_newNode(data);
    if (pnew==NULL)
    {
        return NULL;
    }
    //找位置
    struct node *pre = head->first;
    struct node *p = head->first;

    while (p)
    {
        if (p->data == data)
        {
            break;
        }
        else
        {
            pre = p;
            p = p->next;
        }
        
    }
    if (p==NULL)
    {
        addTail(head,pnew);
    }
    else if (p->data == head->first->data)
    {
        addHead(head,pnew);
    }
    else
    {
        pnew->next = p;
        pre->next = pnew;
    }
    
    
    return head;

}
/*
* delete_node : 删除节点
* 参数：
*   head  ：   链表管理结构体
*   OldDate  : 待删除数据
* 返回值：
*    无
*/
void delete_node(struct headNode *head,dataType data)
{
    if (isEmpty(head))
    {
        printf("此表为空\n");
        return;
    }
    struct node *pre = NULL;
    struct node *p = head->first;
    // 找节点
    while (p)
    {
        if (p->data == data)
        {
            break;
        }
        else
        {
            pre = p;
            p = p->next;
        } 
    }
    if (p == NULL)
    {
        printf("无删除节点\n");
        return ;
    }
    else if(p->data == head->first->data)
    {
        head->first = p->next;
        p->next = NULL;
        free(p);
    }
    else if(p->next == NULL && p->data == data)
    {
        pre->next = NULL;
        free(p);
    }
    else // 删除中间节点
    {
        pre->next = p->next;
        p->next = NULL;
        free(p);
    }
    
    head->nodeNumber--;
}


/*
* destroy_list : 销毁链表
* 参数：
*   head  ：   链表管理结构体
* 返回值：
*    无
*/
void destroy_list(struct headNode *head)
{
    if (isEmpty(head))
    {
        printf("此表为空\n");
        return;
    }

    struct node *tmp = NULL;
    struct node *p = head->first;
    while (p != NULL)
    {
        tmp = p;
        p = p->next;
        free(tmp);
    }
    
    // 将链表头节点的指针设置为NULL，表示链表已被销毁
    head->first = NULL;
    head->last = NULL;
    head->nodeNumber = 0;
    free(head);
}


int main(int argc, char const *argv[])
{
    // 创建链表
    struct headNode *head = create_list();
    if (head == NULL)
    {
        perror("create list failed:");
        return -1;
    }

    printf("原始数据：\n");
    show_list(head);
    
    // 更新节点-将3更新为999
    printf("更新节点-将3更新为999\n");
    renew_node(head,3,999);
    show_list(head);

    // 添加节点-将888头插
    printf("添加节点-将888头插\n");
    add_node_head(head,888);
    show_list(head);

    // 删除节点-将为1的节点删除
    printf("删除节点-将为1的节点删除\n");
    delete_node(head,1);

    // 显示链表节点
    show_list(head);

    // 销毁链表
    destroy_list(head);
    


    return 0;
}

在这里插入图片描述

标签：node,head,struct,最全,pnew,链表,数据结构,节点
From： https://blog.csdn.net/qq_58204972/article/details/140666614

相关文章

  • PART1-Oracle关系数据结构-索引和索引组织表
    3.索引组织表3.1.索引概述索引是与表或表簇关联的可选结构，有时可以加快数据访问速度。通过在表的一个或多个列上创建索引，在某些情况下，您可以从表中检索一小部分随机分布的行。索引是减少磁盘I/O的众多方法之一。如果堆组织表没有索引，那么数据库必须执行全表扫描才能找到一个......
  • 数据结构（Java）：Map集合&Set集合&哈希表
    目录1、介绍1.1 Map和Set1.2模型2、Map集合2.1Map集合说明2.2 Map.Entry<K，V>2.3Map常用方法2.4Map注意事项及实现类 3、Set集合3.1Set集合说明 3.2 Set常用方法 3.3Set注意事项及其实现类4、TreeMap&TreeSet4.1集合类TreeMap（Key-Value模型）4.1.1底......
  • 【数据结构】：用Java实现链表
    在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。因此：java集合中又引入了LinkedList，即链表结构。概念顺序表是物理上连续，逻辑上也是连续的链表......
  • 【数据结构】队列详解和模拟实现
    大家好，今天我们学习队列，本篇博客主要涉及一般队列，环形队列和双端队列，每个队列应用场景均有所差异，下面我们一起来看看吧。队列(Queue)一，概念队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特性入队列：进行插入操作的一端称为队尾（Ta......
  • 数据结构实验二——单链表的基本操作（2021级zzu）
    ps:滴~打卡第二天，好困啊~~~~~~数据结构实验二——单链表的基本操作一、实验目的二、实验内容（选其中之一写实验报告）三、问题描述四、数据结构定义五、算法思想及算法设计5.1实验内容（1）5.1.1理论实现和代码实现5.2实验内容（2）5.2.1代码实现六、运行示例七、实验代......
  • [杂项] [算法] [数据结构] 暑期专题狂补
    或曰，有学长两天授吾以十专题，吾顿感日月之紧迫，以专题竟不能以吾之所有，遂成此文，以记之语文确实没学好本文可能涵盖多个知识点，故每个的讲解比较简略，仅供参考一.2-SAT$2-SAT$用于求解一个变量只有两种情况的适应性问题（就是有没有解以及输出一种方案）；其实可以类比二分图最大......
  • 【数据结构与算法—基础篇1】
    1、基础知识1、数据结构三要素：逻辑结构、存储结构、数据的运算；其中逻辑结构包括线性结构（线性表、栈、队列）和非线性结构（树、图、集合）2、数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。3、数据元素是数据的基本......
  • redis原理之底层数据结构-跳表
    1.什么是跳表1.1链表及其不足链表是在程序设计中最常见的数据结构之一，它通过指针将多个链表节点连接起来，这样就可以将逻辑上同一类的数据存储到不连续的内存空间上。链表结构如下：但是链表有一个问题，就是当链表需要查询一个元素的时候，需要从链表头部开始遍历，时间复杂度为o(......
  • 《Java初阶数据结构》----3.＜线性表---LinkedList与链表＞
    目录前言一、链表的简介1.1链表的概念1.2链表的八种结构 重点掌握两种1.3单链表的常见方法三、单链表的模拟实现四、LinkedList的模拟实现（双链表）4.1 什么是LinkedList4.2LinkedList的使用五、ArrayList和LinkedList的区别 前言   大家好，我目前在学习......
  • 史上最全的xpath 、CSS定位方法
    史上最全的xpath、CSS定位方法   Xpath常用的定位方法相信做过seleniumUI自动化的朋友都知道，工作中大部分的元素定位都是使用xpath进行定位，所以xpath是UI自动化工作中非常重要的一个环节，所以我单独整理出来一篇博客出来~~希望对大家有帮助~相对定位相对定位是两个......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99