精华内容
下载资源
问答
  • DS双向链表前驱后继 题目描述 在双向链表中,A有一个指针指向了后继节点B,同时,B又有一个指向前驱节点A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点,也能从链表尾节点开始遍历所有节点。 ...

    DS双向链表—前驱后继

    题目描述

    在双向链表中,A有一个指针指向了后继节点B,同时,B又有一个指向前驱节点A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点,也能从链表尾节点开始遍历所有节点。

    对于给定的一列数据,按照给定的顺序建立双向链表,按照关键字找到相应节点,输出此节点的前驱节点关键字及后继节点关键字。

    输入

    第一行两个正整数n(代表节点个数),m(代表要找的关键字的个数)。

    接下来输入n个整数为关键字key(数据保证关键字在数列中没有重复)。

    接下来有m个要查找的关键字,每个占一行。

    输出

    对给定的每个关键字,输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继,则不输出。给定关键字为每个输出占一行。

    样例输入

    10 3

    1 2 3 4 5 6 7 8 9 0

    3

    1

    0

    样例输出

    2 4

    2

    9 

    代码实现: 

    #include <iostream>
    using namespace std;
    class ListNode
    {
    public:
        int data;
        ListNode* prior;
        ListNode* next; 
       
        ListNode() { prior = NULL; next = NULL; }
    };
    
    int main()
    {
        int i, n, m, temp;
        cin >> n >> m;
        ListNode* p=NULL, * q, * r=NULL;
        for (i = 0; i < n; i++)
        {
            cin >> temp;
            if (!i)
            {
                p = new ListNode;
                p->data = temp;
                r = p;//如果是第一个数,那么就放在最前面
            }
            else//其他的都与前面的连接
            {
                q = new ListNode;
                q->data = temp;
                q->prior = r;//总是一个一个与前面相连
                r->next = q;
                r = r->next;//用r表示一个一个向后的指针,每次新存进来的指针是q
            }
        }
        for (i = 0; i < m; i++)
        {
            cin >> temp;
            q = p;
            while (q->data != temp)
                q = q->next;
            if (q->prior && q->next)
                cout << q->prior->data << ' ' << q->next->data << endl;
            else if (q->prior && !q->next)
                cout << q->prior->data << endl;
            else
                cout << q->next->data << endl;
        }
    }
    

    日常提神醒脑环节:

     

    展开全文
  • C++双向链表实现(前驱后继思想)

    千次阅读 2019-06-12 10:45:36
    if(ptr->doublelink_getlength(ptr)==0)//当双向链表只有一个头节点时 { root->next=nodeinsert;//待插入的节点 nodeinsert->pre=nodeinsert; nodeinsert->next=nodeinsert; ptr->length++; return 0; } ...

     

     

     

    #include <iostream>
    using namespace std;
    /*****************@copyright2019**************
     * Function:doublelink
     * Author:zjl
     * date:2019-6-12
     * Version:V1.0
     * *******************************************/
    /*************************************************
     *
     * 定义节点链表node
     *
     * ***********************************************/
    struct node
    {
        int data;
        node *pre;//前驱
        node *next;//后继
    };
    //建立一个空的链表
    class doublelink
    {
    public:
        //定义方法
        int doublelink_insert(doublelink *ptr,int position,int member);
        int doublelink_erase(doublelink *ptr,int position);
        void doublelink_display(doublelink *ptr,int num);
        int doublelink_getlength(doublelink *ptr);
        //结构体初始化
        doublelink()
        {
            root=new node; //动态开辟内存空间
            root->pre=NULL;
            root->next=NULL;
            length=0;
        }
    private:
        //定义字段
        int length;
        node* root;
    
    
    };
    //得到链表的长度
    int  doublelink::doublelink_getlength(doublelink *ptr)
    {
        return ptr->length;
    }
    /***********************具体方法实现***********************************/
    /********************************************************************
    
     * 函数名:int doublelink::doublelink_insert(doublelink *ptr, int position, int member)
     * 函数功能:在链表的指定位置插入数据
     * 入口参数:doublelink *ptr:链表  int position:插入的位置   int member:待插入的成员
     * 返回参数:
     * 函数调用:
     *
     *
     * *****************************************************************/
    int doublelink::doublelink_insert(doublelink *ptr, int position, int member)
    {
        node* nodeinsert =new node;//开辟一个节点空间
        nodeinsert->data=member;
        if(ptr->doublelink_getlength(ptr)==0)//当双向链表只有一个头节点时
        {
           root->next=nodeinsert;//待插入的节点
           nodeinsert->pre=nodeinsert;
           nodeinsert->next=nodeinsert;
           ptr->length++;
           return 0;
        }
        else
        {
            if(position==0)//在一个位置插入节点
            {
                nodeinsert->pre=root->next->pre;//前驱
                nodeinsert->next=root->next;//后继
                root->next->pre->next=nodeinsert;
                root->next->pre=nodeinsert;
                ptr->length++;
                return 0;
            }
            else  //在其他位置v插入数据
            {
                node *current=root->next;
                for(int i=0;i<position;i++)
                {
                    current=current->next;
    
                }
                nodeinsert->next=current;
                nodeinsert->pre=current->pre;
                current->pre->next=nodeinsert;
                current->pre=nodeinsert;
                ptr->length++;
                return 0;
    
            }
        }
    
    }
    //删除一个元素
    int doublelink::doublelink_erase(doublelink *ptr,int position)
    {
        if(ptr->doublelink_getlength(ptr)==0)
        {
            cout<<"链表为空"<<endl;
            return 0;
        }
        else
        {
            if(ptr->doublelink_getlength(ptr)==1)
            {
                ptr->root->next=NULL;
                ptr->length--;
            }
            else
            {
                node *deletenode=root->next;
                for(int i=0;i<position;i++)
                {
                    deletenode=deletenode->next;
                }
                deletenode->pre->next=deletenode->next;
                deletenode->next->pre=deletenode->pre;
                delete deletenode;
                ptr->length--;
            }
        }
    }
    //显示
    void doublelink::doublelink_display(doublelink *ptr,int num)
    {
       node* current=root->next;
       for(int i=0;i<num;i++)
       {
           cout<<current->data<<" ";
           current=current->next;
       }
       cout<<endl;
    }
    
    int  main()
    {
        doublelink* doublelink_ptr=new doublelink;
        for(int i=0;i<10;i++)
        {
            doublelink_ptr->doublelink_insert(doublelink_ptr,0,i);
    
        }
        doublelink_ptr->doublelink_display(doublelink_ptr,20);
        doublelink_ptr->doublelink_erase(doublelink_ptr,2);
        doublelink_ptr->doublelink_display(doublelink_ptr,20);
        return 0;
    }

     

    展开全文
  • 问题 C: DS双向链表前驱后继 时间限制: 1 Sec 内存限制: 128 MB 题目描述 在双向链表中,A有一个指针指向了后继节点B,同时,B又有一个指向前驱节点A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点,...

    问题 C: DS双向链表—前驱后继
    时间限制: 1 Sec 内存限制: 128 MB

    题目描述
    在双向链表中,A有一个指针指向了后继节点B,同时,B又有一个指向前驱节点A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点,也能从链表尾节点开始遍历所有节点。
    对于给定的一列数据,按照给定的顺序建立双向链表,按照关键字找到相应节点,输出此节点的前驱节点关键字及后继节点关键字。

    输入
    第一行两个正整数n(代表节点个数),m(代表要找的关键字的个数)。
    接下来输入n个整数为关键字key(数据保证关键字在数列中没有重复)。
    接下来有m个要查找的关键字,每个占一行。

    输出
    对给定的每个关键字,输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继,则不输出。给定关键字为每个输出占一行。

    样例输入
    10 3
    1 2 3 4 5 6 7 8 9 0
    3
    1
    0
    样例输出
    2 4
    2
    9

    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<string>
    #include<map>
    using namespace std;
    
    class List
    {
    public:
    	int number;
    	List* next;
    	List* pre;
    	List()
    	{
    		pre = NULL;
    		next = NULL;
    	}
    };
    
    class NList {
    	List* head;
    	int len;
    public:
    	NList()
    	{
    		head = new List();
    	}
    	~NList()
    	{
    		List* p, * q;
    		p = head;
    		while (p->next)
    		{
    			q = p->next;
    			delete p;
    			p = q;
    		}
    		delete p;
    	}
    	void insert(int item)
    	{
    		List* pre = NULL, * cur = NULL, * now = NULL;
    		cur = head;
    		now = new List();
    		now->number = item;
    		now->next = NULL;
    		while (cur->next != NULL)
    		{
    			pre = cur;
    			cur = cur->next;
    		}
    		if (cur == head)
    		{
    			cur->next = now;
    		}
    		else
    		{
    			cur->next = now;
    			now->pre = cur;
    		}
    		len++;
    	}
    	void display()
    	{
    		List* cur;
    		cur = head->next;
    		while (cur)
    		{
    			cout << " " << cur->number;
    			cur = cur->next;
    		}
    		cout << endl;
    	}
    	void fin(int item)
    	{
    		List* cur;
    		cur = head->next;
    		while (cur)
    		{
    			if (cur->number == item)break;
    			cur = cur->next;
    		}
    		if (cur->pre != NULL)
    		{
    			cout << cur->pre->number << " ";
    		}
    		if (cur->next != NULL)
    		{
    			cout << cur->next->number;
    		}
    		cout << endl;
    	}
    };
    
    int main()
    {
    
    	NList p;
    	int n, number,times;
    	cin >> n>>times;
    	for (int i = 0; i < n; ++i)
    	{
    		cin >> number;
    		p.insert(number);
    	}
    	//p.display();
    	for (int i = 0; i < times; ++i)
    	{
    		int item;
    		cin >> item;
    		p.fin(item);
    	}
    	return 0;
    }
    
    展开全文
  • 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
  • 双向链表

    千次阅读 2019-07-29 15:35:37
    双向链表:在单链表的结点中增加一个指向其前驱的pre指针;该链表中第一个结点的前趋结点为NULL,最后一个结点的后继结点为NULL 。 双向链表具有单链表的所有操作:创建、销毁、获取链表长度、清空、获取某个元素、...

    为什么需要双向链表?

    单链表的结点都只有一个指向下一个结点,单链表的数据元素无法直接访问其前驱元素,所以逆序访问单链表中元素极其耗时;

    思想有点类似使用空间复杂度换时间复杂度。
    双向链表:在单链表的结点中增加一个指向其前驱的pre指针;该链表中第一个结点的前趋结点为NULL,最后一个结点的后继结点为NULL 。

    双向链表示意图
    双向链表具有单链表的所有操作:创建、销毁、获取链表长度、清空、获取某个元素、插入元素、删除元素;

    定义双向链表类型结构

    typedef struct line{
    	struct line *prior;//指向直接前趋
    	int data;
    	struct line *next;//指向直接后继 
    }line;
    

    初始化双向链表

    line *initLine(line *head){
    	//给头结点分配内存 
    	head =(line *)malloc(sizeof(line));//创建链表第一个结点(首元结点)
    	//初始化头结点 
    	head->data =1;
    	head->prior = NULL;
    	head->next = NULL;
    	line *list =head;
    	int i;
    	for(i=2;i<=5;i++){
    		//初始化结点 
    		line *body = (line *)malloc(sizeof(line));  //创建并初始化一个结点 
    		body->data =i;
    		body->prior =NULL;
    		body->next = NULL;
    		//新增结点 
    		list->next = body; //直接将前趋结点的next指针指向新结点;@新增结点body为list的后继结点 
    		body->prior = list; //新结点指向直接前趋结点;@新增结点body的前趋为list 
    		list =list->next; //更新head后继指针的值,不更新的话,更改只是头结点的值 
    	}
    	return head;
    } 
    
    

    插入元素操作

    需要考虑插入元素位置,链表头部、中间、尾部
    插入中间位置示意图

    代码实现

    删除操作

    展开全文
  • 链表前驱后继插入概念解析代码分析 概念解析 原因来自我现在自学数据结构与算法,非科班靠着网课自学有点吃力,不过也只能这样了,毕竟考研也不读计算机,只是觉得必须要学好这些知识而已。 回归正题,这是我在学习...
  • 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
  • 单链表、双向链表、循环链表

    千次阅读 多人点赞 2019-07-26 14:26:09
    学习三种常见的链表结构,他们分别是:单链表、双向链表和循环链表。 单链表 单链表有两个较特殊节点,头结点尾节点。头结点用来记录链表的基地址,可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向...
  • 数据结构—双向链表

    2019-10-28 16:02:45
    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点,时间复杂度为O(1)。 双链表...
  • 1.问题描述 已知p指向双向循环链表中的...知道双向循环链表中的一个结点,与前驱交换涉及到四个结点(p结点,前驱结点,前驱前驱结点,后继结点)六条链。 void Change(LinkList p) { DLnode *q; q = p->...
  • 1.利用前驱后继 对于一个二叉树,可以将其分为左子树、根节点右子树三部分。根据题目要求可知将BST化为一个排好序的双向链表实际上就是将其中序遍历序列对应的各个节点连接起来。同时还可以知道若根的左右子树...
  • 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
  • 1.LinkedList实现的基本原理 LinkedList是一个双向链表,它主要有两个表示头尾节点的成员变量first 、last,因其有头尾两个节点,...如果要添加元素,则新建一个Node节点,保存这个元素,同时指定其前驱节点和后继节...
  • 前言单向链表和双向链表的优缺点及使用场景双向链表的简单实现及图示分析 前言 之前写了一些文章简单地介绍顺序表,链表的基础知识,还总结了几道链表的笔试题,今天继续开干,向老铁们简单地介绍一下无头双向循环...
  • 一、单链表单链表的插入与删除:假设我们有个节点ai,指向他的指针为p,有个节点为e,指向他的指针为s①插入:想要把e插入到ai的后面,只需要把s的next指向p的next,再把p的next指向e就可以了②删除:想要删除ai+1...
  • C++的双向链表实现

    2020-04-15 13:21:14
    代码基于标准C++,可以用vscode,vs,qt等IDE打开。具备基本的双链表操作,如头插尾插,前驱遍历和后继遍历,求长度等等。
  • 作者最近做数据结构的习题时发现了好多关于双向链表的问题,诸如双向链表非空的判定条件,双向链表插入一个结点的四条基本语句,双向链表删除一个结点的两条基本语句,判断双向链表是否为回文表的算法之类的练习题。...
  • 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
  • 双向链表的插入删除

    万次阅读 多人点赞 2018-09-21 17:23:50
    双向链表的插入 第一步:首先找到插入位置,节点 s 将插入到节点 p 之前 第二步:将节点 s 的前驱指向节点 p 的前驱,即 s-&gt;prior = p-&gt;prior; 第三步:将节点 p 的前驱后继指向节点 s 即 p-&...
  • 这样,当我们需要找到某个结点的前驱就没办法了。如何从链表中的任一结点出发,访问到链表的全部结点?循环链表就是解决这个麻烦的重要方法。 一、循环链表的定义 1、定义 将单链表中终端结点的指针端由空指针改...
  • 双向链表的基本概念 单链表的结点中,只有一个指针域,用来指示后继结点。由此,从某个结点出发只能顺时针向后寻找其他结点。若要寻找结点的前驱结点,则必须从表头指针出发。换言之,在单链表中,查找直接后继...
  • 详解双向链表的基本操作(C语言)

    万次阅读 多人点赞 2020-04-06 22:06:19
    学习之前先对单向链表和双向链表做个回顾。 单向链表特点:   1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.   2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾) 双向链表特点   1.每次在...
  • 双向链表及其用法

    万次阅读 多人点赞 2018-05-25 13:40:46
    所以我们从双向链表的任意一个结点开始都可以很方便的访问其前驱元素和后继元素。二、双向链表的存储结构双向链表也是采用的链式存储结构,它与单链表的区别就是每个数据结点中多了一个指向前驱元素...
  • 双向链表也是链表的一种,它每个数据结点中都有两个结点,分别指向其直接前驱和直接后继。所以我们从双向链表的任意一个结点开始都可以很方便的访问其前驱元素和后继元素。 双向链表的结构如下图所示: 双向链表的...
  • 一、向双向链表中插入新节点new 关于双向链表的插入问题,有些地方需要特别理解一下,有一个原则就是不能将原始链表弄丢,所以在断开原始连接之前, 我们应该先要将即将断开部分的前后连接保存下来,也就是链表...
  • 所谓双向链表是如果希望找直接前驱结点直接后继结点的时间复杂度都是 O(1),那么,需要在结点中设两个引用域,一个保存直接前驱结点的地址,叫 prev,一个直接后继结点的地址,叫 next,这样的链表就是双向链表...
  • 1.1 什么是链表链表是有序的列表,但是它在...链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定 单链表(带头结点) 逻辑结构示意图如下 1.2 单链表的应用实例 使用带head头的单向链表实现 –水...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,134
精华内容 5,653
关键字:

双向链表的前驱和后继