数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数

简介: 数据结构和算法学习记录——线性表之双向链表(下)-头插函数、头删函数、查找函数、pos位置之前插入结点、pos位置删除结点及其复用、销毁链表函数

线性表之双向链表(上)

头插函数

头插的思路比较简单,创建一个新结点,在哨兵位结点和第一个结点之间链接起来就可以。头插函数在链表为空时不会出问题,所以不需要多加断言。

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

头删函数

代码

void ListPopFront(LTNode* phead)
{
    assert(phead);
    //链表为空
    assert(phead->next != phead);
 
    LTNode* next = phead->next;
    LTNode* nextNext = next->next;
 
    phead->next = nextNext;
    nextNext->prev = phead;
    free(next);
}

简单思路

查找函数

查找函数实现起来十分简单,直接遍历就可以了。思路与打印函数是一致的。

LTNode* ListFind(LTNode* phead, LTDataType x)
{
    assert(phead);
 
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

pos位置之前插入结点

第一种方法(更好)

我们不使用大部分教材上的方法,即不多创建一个结点,直接进行指针的改变;这样就需要对指针改变的顺序有极大的要求,一旦指针改变的顺序不一样,就不能实现插入。

这里使用的是创建一个结点记录下pos位置的前一个结点,好处是在进行指针改变时不用考虑改变顺序。

代码

//pos位置之前插入结点
void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* posPrev = pos->prev;
    LTNode* newnode = BuyListNode(x);
 
    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;
 
}

第二种方法

思路

像这样没创建一个posPrev则需要考虑改变的顺序。

同时,实现了pos位置之前插入结点的这个函数之后,就可以复用到头插和尾插当中了。

pos位置删除结点

void ListErase(LTNode* pos)
{
    assert(pos);
 
    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
 
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}

复用到尾删

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;
    ListErase(phead->prev);
}

复用到头删

void ListPopFront(LTNode* phead)
{
    assert(phead);
    //链表为空
    assert(phead->next != phead);
 
    //LTNode* next = phead->next;
    //LTNode* nextNext = next->next;
 
    //phead->next = nextNext;
    //nextNext->prev = phead;
    //free(next);
    ListErase(phead->next);
}

双向链表销毁

void ListDestroy(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);
}

如果传入一级指针则存在野指针的隐患,即销毁完空间之后没有把指针置空

但从设计上考虑,为了保持接口函数的一致性,就统一使用一级指针了。

所以我们就在外面将指针置为空

ListDestroy(phead);
phead = NULL;
目录
相关文章
|
1月前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
28 0
|
10天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
|
10天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机分类模型(SVC算法)项目实战
|
10天前
|
机器学习/深度学习 数据采集 监控
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
**神经网络与AI学习概览** - 探讨神经网络设计,包括MLP、RNN、CNN,激活函数如ReLU,以及隐藏层设计,强调网络结构与任务匹配。 - 参数初始化与优化涉及Xavier/He初始化,权重和偏置初始化,优化算法如SGD、Adam,针对不同场景选择。 - 学习率调整与正则化,如动态学习率、L1/L2正则化、早停法和Dropout,以改善训练和泛化。
9 0
算法金 | DL 骚操作扫盲,神经网络设计与选择、参数初始化与优化、学习率调整与正则化、Loss Function、Bad Gradient
|
1月前
|
算法 搜索推荐 JavaScript
算法学习:快速排序
算法学习:快速排序
19 1
|
15天前
|
Dart 算法 JavaScript
C#数据结构与算法入门教程,值得收藏学习!
C#数据结构与算法入门教程,值得收藏学习!
|
1月前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
|
17天前
|
机器学习/深度学习 存储
sdut pta 链表3(优化)-----7-3 sdut-C语言实验-链表的结点插入
sdut pta 链表3(优化)-----7-3 sdut-C语言实验-链表的结点插入
8 0
|
23天前
|
算法 Java
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
13 0
|
24天前
|
机器学习/深度学习 人工智能 算法
技术经验解读:【转】完美洗牌算法学习
技术经验解读:【转】完美洗牌算法学习
10 0

热门文章

最新文章