数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数

简介: 数据结构和算法学习记录——线性表之双向链表(上)-结点类型定义、初始化函数、创建新结点函数、尾插函数、打印函数、尾删函数

结点类型定义

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
typedef int LTDataType;
 
typedef struct ListNode
{
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
}LTNode;

初始化函数

LTNode* ListInit()
{
    //哨兵位头结点
    LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    phead->next = NULL;
    phead->prev = NULL;
 
    return phead;
}

创建新结点函数

LTNode* BuyListNode(LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    newnode->data = x;
    newnode->next = NULL;
    newnode->prev = NULL;
    return newnode;
}

尾插函数

代码

void ListPushBack(LTNode* phead, LTDataType x)
{
    assert(phead);
 
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
 
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;
}

实现思路

为什么这个尾插函数不需要传入二级指针呢?

详细看我们的代码:


我们至始至终,有改变其值的,只有tail中的next指针、newnode的prev指针、newnode的next指针和phead的prev指针。

而phead本身的地址,或者说phead本身的值并没有被改变,所以就不需要传入二级指针来改变phead的值了。

打印双向链表函数

void ListPrint(LTNode* phead)
{
    assert(phead);
 
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

尾删函数

实现方式一

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
 
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    free(tail);
 
    tailPrev->next = phead;
    phead->prev = tailPrev;
}

实现方式二

void ListPopBack(LTNode* phead)
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* tail = phead->prev;
 
    phead->prev = tail->prev;
    tail->prev->next = phead;
    free(tail);
}


第二种赋值的语句先后顺序无影响

需要注意的是:不能把哨兵位结点也一起删了,即当phead->next == phead时,就表示此事链表为空,只剩下一个哨兵位结点了。该结点不存数据。


线性表之双向链表(下)

目录
相关文章
|
存储 算法
算法入门:专题二---滑动窗口(长度最小的子数组)类型题目攻克!
给定一个正整数数组和目标值target,找出总和大于等于target的最短连续子数组长度。利用滑动窗口(双指针)优化,维护窗口内元素和,通过单调性避免重复枚举,时间复杂度O(n)。当窗口和满足条件时收缩左边界,更新最小长度,最终返回结果。
|
算法 安全 机器人
【路径规划】基于遗传算法结合粒子群算法求解机器人在复杂不同类型下的路径规划研究(Matlab代码实现)
【路径规划】基于遗传算法结合粒子群算法求解机器人在复杂不同类型下的路径规划研究(Matlab代码实现)
361 4
简化数据结构的初始化过程
简化数据结构的初始化过程
307 0
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
856 5
|
机器学习/深度学习 算法 数据安全/隐私保护
基于深度学习网络的宝石类型识别算法matlab仿真
本项目利用GoogLeNet深度学习网络进行宝石类型识别,实验包括收集多类宝石图像数据集并按7:1:2比例划分。使用Matlab2022a实现算法,提供含中文注释的完整代码及操作视频。GoogLeNet通过其独特的Inception模块,结合数据增强、学习率调整和正则化等优化手段,有效提升了宝石识别的准确性和效率。
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
411 3
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
410 0
数据结构与算法学习五:双链表的增、删、改、查
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
3724 6