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

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

结点类型定义

#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时,就表示此事链表为空,只剩下一个哨兵位结点了。该结点不存数据。


线性表之双向链表(下)

目录
相关文章
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
7天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
7天前
|
机器学习/深度学习 数据采集 监控
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
**神经网络与AI学习概览** - 探讨神经网络设计,包括MLP、RNN、CNN,激活函数如ReLU,以及隐藏层设计,强调网络结构与任务匹配。 - 参数初始化与优化涉及Xavier/He初始化,权重和偏置初始化,优化算法如SGD、Adam,针对不同场景选择。 - 学习率调整与正则化,如动态学习率、L1/L2正则化、早停法和Dropout,以改善训练和泛化。
7 0
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
|
12天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
23天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
17天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
23天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
27 5
|
23天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
|
24天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
27 1
|
12天前
|
API
用栈翻转字符串
用栈翻转字符串
15 0