首页 > 编程语言 >13.双向链表的算法实现

13.双向链表的算法实现

时间：2023-06-10 21:23:11浏览次数：45  
标签：node 结点 return 13 next 链表 算法 prev 节点

  单链表中每个结点除了存储自身数据之后，还存储了下一个结点的地址，因此可以轻松访问 下一个结点，以及后面的后继结点，但是如果想访问前面的结点就不行了，再也回不去了。
  例如删除结点p时，要先找到它的前一个结点q，然后才能删掉p结点，单向链表只能往后走，不能向前走。如果需要向前走，怎么办呢？
  可以在单链表的基础上给每个元素附加两个指针域，一个存储前一个元素的地址，一个存储下一个元素的地址。这种链表称为双向链表。

1.定义

typedef struct _LinkNode
{
    int data; //结点的数据域
    struct _LinkNode *next; //下一个节点的指针域
    struct _LinkNode *prev; //上一个结点的指针域
}LinkNode, LinkList; //LinkList 为指向结构体LNode 的指针类型

2.双向链表的初始化

typedef struct _DoubleLinkNode
{
    int data; //结点的数据域 
    struct _DoubleLinkNode *next; //下一个节点的指针域
    struct _DoubleLinkNode *prev; //上一个结点的指针域
}DbLinkNode, DbLinkList; //LinkList 为指向结构体LNode 的指针类型

bool DbInit_List(DbLinkList* &L)//构造一个空的双向链表L
{
    L=new DbLinkNode; //生成新结点作为头结点，用头指针L指向头结点
    if(!L)return false; //生成结点失败
    L->next=NULL; //头结点的next 指针域置空
    L->prev=NULL; //头结点的指针域置空
    L->data = -1;
    return true;
}

3.双向链表增加元素

3.1前插法

//前插法
bool DbListInsert_front(DbLinkList* &L, DbLinkNode *node)
{
    if(!L || !node) return false;
    //1.只有头节点
    if(L->next==NULL)
    {
        node->next=NULL;
        node->prev=L; //新节点prev指针指向头节点
        L->next=node; //头节点next 指针指向新节点
    }
    else
    {
        L->next->prev=node; //第二个节点的prev指向新节点
        node->next = L->next; //新节点next指针指向第二个节点
        node->prev=L; //新节点prev 指针指向头节点
        L->next=node; //头节点next 指针指向新节点，完成插入
    }
    return true;
}

3.2尾插法

//尾插法
bool DbListInsert_back(DbLinkList* &L, DbLinkNode *node)
{
    DbLinkNode *last = NULL;
    if(!L || !node) return false;
    last = L;
    while(last->next) last = last->next;
    node->next = NULL;
    last->next = node;
    node->prev = last;      
    return true;
}

3.3任意位置插入

//指定位置插入
bool DbLink_Insert(DbLinkList* &L, int i, int &e)
{
    if(!L||!L->next) return false;
    if(i<1) return false;
    int j =0;
    DbLinkList *p, *s;
    p = L;
    while(p && j<i)
    {
        //查找位置为i的结点，p 指向该结点
        p = p->next;
        j++;
    }
    if(!p)//超出范围
    {
        cout<<"不存在节点："<<i<<endl;
        return false;
    }
    cout<<"p: "<<p<<endl;
    s=new DbLinkNode;//生成新节点
    s->data = e;
    s->next = p;
    s->prev = p->prev;
    p->prev->next = s;
    p->prev = s;
    return true;
}

3.4双向链表的遍历

//双向链表的遍历输出
void DbLink_Print(DbLinkList* &L )
{
    DbLinkNode *p = NULL;
    if(!L)
    {
        cout<<"链表为空."<<endl;
        return ;
    }
    p = L;
    while(p->next)
    {
        cout<<p->next->data<<"\t";
        p = p->next;
    }//p->next为NULL，所以p指向最后一个结点
    //逆向打印
    cout<<endl<<"逆向打印"<<endl;
    while(p)
    {
        cout<<p->data<<"\t";
        p = p->prev;
    }
    cout<<endl;
}

3.5双向链表获取元素

bool DbLink_GetElem(DbLinkList* &L, int i, int &e)//双向链表的取值
{
    //在带头结点的双向链表L 中查找第i 个元素
    //用e记录L中第i个数据元素的值
    int index;
    DbLinkList *p;
    if(!L || !L->next) return false;
    p = L->next;
    index = 1;
    while(p && index<i)//顺链表向后扫描，直到p 指向第i个元素或p
    {
        p = p->next; //p 指向下一个结点 
        index++; //计数器index 相应加1
    }
    if(!p || index>i)
    {
        return false; //i值不合法,i＞n 或i<=0
    }
    e=p->data;
    return true;
}

3.6双向链表删除元素

//任意位置删除
bool DbLink_Delete(DbLinkList* &L, int i) //双向链表的删除
{
    DbLinkList *p;
    int index = 0;
    if(!L || !L->next)
    {
        cout<<"双向链表为空!"<<endl;
        return false;
    }
    if(i<1) return false; //不能删除头节点
    p=L;
    while(p && index<i)
    {
        p = p->next;
        index++;
    }
    if(!p)
    { 
        //当节点不存在时，返回失败
        return false;
    }
    p->prev->next=p->next; //改变删除结点前驱结点的next 指针域
    if(p->next)
    {
        p->next->prev = p->prev; //改变删除节点后继节点的prev 指针域
    }
    delete p; //释放被删除结点的空间
    return true;
}

3.6双向链表销毁

void DbLink_Destroy(DbLinkList* &L) //双向链表的销毁
{
    //定义临时节点p 指向头节点
    DbLinkList *p = L;
    cout<<"销毁链表!"<<endl;
    while(p)
    {
        L=L->next;//L 指向下一个节点
        cout<<"删除元素: "<<p->data<<endl;
        delete p; //删除当前节点
        p = L; //p 移向下一个节点
     }
}

完整代码实现：

#include<iostream>
#include<string>
#include<stdlib.h>

using namespace std;

typedef struct _DoubleLinkNode 
{
    int data; //结点的数据域
    struct _DoubleLinkNode *next; //下一个节点的指针域
    struct _DoubleLinkNode *prev; //上一个结点的指针域
}DbLinkNode, DbLinkList; //LinkList 为指向结构体LNode 的指针类型

bool DbList_Init(DbLinkList* &L)//构造一个空的双向链表L
{
    L=new DbLinkNode; //生成新结点作为头结点，用头指针L 指向头结点
    if(!L)return false; //生成结点失败
    L->next=NULL; //头结点的next 指针域置空
    L->prev=NULL; //头结点的prev 指针域置空
    L->data = -1;
    return true; 
}
//前插法
bool DbListInsert_front(DbLinkList* &L, DbLinkNode *node)
{
    if(!L || !node) return false;
    //1.只有头节点
    if(L->next==NULL)
    {
        node->next=NULL;
        node->prev=L; //新节点prev 指针指向头节点
        L->next=node; //头节点next 指针指向新节点
    }
    else
    { 
        L->next->prev=node; //第二个节点的prev 指向新节点    
        node->next = L->next; //新节点next 指针指向第二个节点   
        node->prev=L; //新节点prev 指针指向头节点    
        L->next=node; //头节点next 指针指向新节点，完成插入
    }
    return true;
}

//尾插法
bool DbListInsert_back(DbLinkList* &L, DbLinkNode *node)
{
    DbLinkNode *last = NULL;
    if(!L || !node) return false;
    last = L;
    while(last->next) last = last->next;
    node->next = NULL;
    last->next = node;
    node->prev = last;
    return true;
}
//指定位置插入
bool DbLink_Insert(DbLinkList* &L, int i, int &e)
{
    if(!L||!L->next) return false;
    if(i<1) return false;
    int j =0;
    DbLinkList *p, *s; 
    p = L;
    while(p && j<i)
    {
        //查找位置为i 的结点，p 指向该结点
        p = p->next;
        j++;
    }
    if(!p || j!=i)
    {
        cout<<"不存在节点："<<i<<endl;
        return false;
    }
    cout<<"p: "<<p<<endl;
    s=new DbLinkNode;//生成新节点
    s->data = e;
    s->next = p;
    s->prev = p->prev;
    p->prev->next = s;
    p->prev = s;
    return true;
}
void DbLink_Print(DbLinkList* &L )
{
    DbLinkNode *p = NULL;
    if(!L)
    {
        cout<<"链表为空."<<endl;
        return;
    }
    p = L;
    while(p->next)
    {
        cout<<p->next->data<<"\t";
        p = p->next;
    }
    //逆向打印
    cout<<endl<<"逆向打印"<<endl;
    while(p)
    {
        cout<<p->data<<"\t";
        p = p->prev;
    }
    cout<<endl;
}
bool DbLink_GetElem(DbLinkList* &L, int i, int &e)//双向链表的取值
{
    //在带头结点的双向链表L 中查找第i 个元素
    //用e 记录L 中第i 个数据元素的值
    int index;
    DbLinkList *p;
    if(!L || !L->next) return false;
    p = L->next;
    index = 1;
    while(p && index<i)//顺链表向后扫描，直到p 指向第i个元素或p为空
    {
        p = p->next; //p 指向下一个结点
        index++; //计数器index 相应加1
    }
    if(!p || index>i)
    {
        return false; //i 值不合法,i＞n 或i<=0
    }
    e=p->data;
    return true;
}

bool DbLink_Delete(DbLinkList* &L, int i) //双向链表的删除
{
    DbLinkList *p;
    int index = 0;
    if(!L || !L->next)
    {
        cout<<"双向链表为空!"<<endl;
        return false;
    }
    if(i<1) return false; //不能删除头节点
    p=L;
    while(p && index<i)
    {
        p = p->next;
        index++;
    }
    if(!p) //当节点不存在时，返回失败
    {
        return false;
    }
    p->prev->next=p->next; //改变删除结点前驱结点的next 指针域
    p->next->prev = p->prev; //改变删除节点后继节点的prev 指针域
    delete p; //释放被删除结点的空间
    return true;
}
void DbLink_Destroy(DbLinkList* &L) //双向链表的销毁
{
    //定义临时节点p 指向头节点
    DbLinkList *p = L;
    cout<<"销毁链表!"<<endl;
    while(p)
    {
        L=L->next;//L 指向下一个节点
        cout<<"删除元素: "<<p->data<<endl;
        delete p; //删除当前节点
        p = L; //p 移向下一个节点
    }
}

int main(void)
{
    DbLinkList *L = NULL;
    DbLinkNode *s = NULL;
    //1. 初始化一个空的双向链表
    DbList_Init(L);
    //2. 使用前插法插入数据
    int n;
    cout<<"前插法创建双向链表"<<endl;
    std::cout<<"请输入元素个数n：";
    cin>>n;
    cout<<"\n 请依次输入 n 个元素：" <<endl;
    while(n>0)
    {
        s = new DbLinkNode; //生成新节点s
        cin>>s->data;
        DbListInsert_front(L, s);
        n--;
    }
    //3. 使用尾插法插入数据
    cout<<"尾插法创建双向链表"<<endl;
    std::cout<<"请输入元素个数n：";
    cin>>n;
    cout<<"\n 请依次输入n 个元素：" <<endl;
    while(n>0)
    {
        s = new DbLinkNode; //生成新节点s
        cin>>s->data;
        DbListInsert_back(L, s);       
        n--;
    }
    //4. 双向链表的输出
    DbLink_Print(L);
    //5. 任意位置插入元素
    for(int j=0; j<3; j++)
    {
        int i, x;
        cout << "请输入插入的位置和元素（用空格隔开）:";
        cin >> i;
        cin >> x;
        if(DbLink_Insert(L, i, x))
        {
            cout << "插入成功.\n\n";
        }
        else
        {
            cout << "插入失败!\n\n";
        }
        DbLink_Print(L);
    }
    //6. 双向链表根据位置获取元素
    int element = 0;
    if(DbLink_GetElem(L, 2, element))
    {
        cout<<"获取第二个元素成功, 值："<<element<<endl;    
    }
    else 
    {
        cout<<"获取第二个元素失败!"<<endl;
    }
    //7. 双向链表删除元素
    if(DbLink_Delete(L, 2))
    {
        cout<<"删除第2 个元素成功!"<<endl;
        DbLink_Print(L);
    }
    else 
    {
        cout<<"删除第2 个元素失败!"<<endl;
    }
    if(DbLink_Delete(L, 1))
    {
        cout<<"删除第1 个元素成功!"<<endl;
        DbLink_Print(L);
    }
    else
    {
        cout<<"删除第1 个元素失败!"<<endl;
    }
    //8. 销毁双向链表
    DbLink_Destroy(L);
    
    system("pause");
    return 0;
}

参考资料来源：

奇牛学院

标签：node,结点,return,13,next,链表,算法,prev,节点
From： https://www.cnblogs.com/codemagiciant/p/17471956.html

相关文章

  • 文心一言 VS 讯飞星火 VS chatgpt （37）-- 算法导论5.4 1题
    一、一个屋子里必须要有多少人，才能让某人和你生日相同的概率至少为1/2?必须要有多少人，才能让至少两个人生日为7月4日的概率大于1/2?文心一言：一个屋子里必须要有多少人，才能让某人和你生日相同的概率至少为1/2？答案：23人。证明：假设有n个人，生日都在一年365天当中，则某人和你的......
  • 3.5决策树算法
    1.认识决策树决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-then结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法怎么理解这句话？通过一个对话例子想一想这个女生为什么把年龄放在最上面判断！！！！！！！！！如何高效的进行决策？   特征的先后顺序2.决策树的原......
  • 反转链表
    头插法:classSolution{publicListNodereverseList(ListNodehead){ListNodenewHead=newListNode(0);newHead.next=null;ListNodep=head;ListNodeq;while(p!=null){q=p;p=p.next;......
  • 算法刷题记录：P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two
    题目链接：https://www.luogu.com.cn/problem/P1518题目分析这道模拟题很典型了，给定了一个固定的移动方式，去模拟即可，该题说：如果牛和农夫永远不会相遇输出0，我没想到很好的方法，不推荐我这样的写法。算勉强AC吧。AC代码//Problem:P1518[USACO2.4]两只塔姆沃斯牛TheTamwort......
  • 算法的引入
    算法解题四步走分析需求设计算法算法实现验证结果算法需要的特性输入：可以有一个或者多个输入输出：至少有一个正确的输出有穷性：确保算法执行的时间是理想确切性：确保算法的每一个步骤都是有意义的可行性：算法的每一步都是能执行的简单的案例#如果a+b+c=1000，且a^2+b^2......
  • 3.4 朴素贝叶斯算法
    1什么是朴素贝叶斯算法2概率基础2.1概率(Probability)定义概率定义为一件事情发生的可能性扔出一个硬币，结果头像朝上某天是晴天P(X):取值在[0,1]2.2女神是否喜欢计算案例在讲这两个概率之前我们通过一个例子，来计算一些结果：问题：一直小明是产品经理，体重超重，问......
  • 处理机典型调度算法
    日志返回日志列表处理机典型调度算法 编辑于 2023-2-1008:56 阅读(0)赞评论转载分享复制地址编辑上一篇 | 下一篇：元，角，分，厘，... 开通黄钻处理机典型调度算法 处理机典型调度算法 1.先来先服务算法作业调度、进程调度先来的......
  • 操作系统常用算法
    操作系统常用算法发布于2018-08-1713:16:23阅读 1.2K0 作业调度算法介绍：又称为高级调度或长程调度，调度对象是作业。根据作业控制块（JCB）中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为他们创建进程、分配......
  • 常用调度算法 总结
    常用调度算法总结 常用调度算法总结 1常见的批处理作业调度算法 1.1先来先服务调度算法（FCFS）: 就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满......
  • （进程管理）05.进程的调度算法
    （进程管理）05.进程的调度算法 进程调度，就是绪状态的进程获得CPU的使用权，进程由就绪状态转变成运行状态。进程调度可以分为：抢占式系统会根据进程的优先级高低来进行调度，进程之间可以插队非抢占式系统按照先来先服务的方式来调度，进程间不能插队进程调度算法有很多，......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99