精华内容
下载资源
问答
  • 本文解法基于性质:二叉搜索树中序遍历 递增序列 。 将 二叉搜索树 转换成一个 “排序循环双向链表” ,其中包含三个要素...3.循环链表: 设链表头节点 head 和尾节点 tail ,则应构建 head.left = tail 和 tai.

    在这里插入图片描述
    本文解法基于性质:二叉搜索树的中序遍历为 递增序列 。

    将 二叉搜索树 转换成一个 “排序的循环双向链表” ,其中包含三个要素:
    1.排序链表: 节点应从小到大排序,因此应使用 中序遍历
    2.“从小到大”访问树的节点。 双向链表: 在构建相邻节点的引用关系时,设前驱节点 pre 和当前节点 cur ,
    不仅应构建 pre.right= cur ,也应构建 cur.left = pre 。
    3.循环链表: 设链表头节点 head 和尾节点 tail ,则应构建 head.left = tail 和 tail.right = head 。

    双指针:

    class Solution {
    private:
        Node* head, * pre = NULL;
    public:
        Node* treeToDoublyList(Node* root) {//双指针做法
            if (!root) return NULL;
            inorder(root);
            head->left = pre;
            pre->right = head;
            return head;
        }
        void inorder(Node* root)
        {
            if (root == NULL)return;
            inorder(root->left);
            root->left = pre;
            if (pre)
                pre->right = root;
            else head = root;
            pre = root;
            inorder(root->right);
        }
    };
    

    数组方法:很简单就不做介绍了,就是先把节点都放进数组然后在建立联系。

    Node* treeToDoublyList(Node* root) {
            if (!root) return NULL;
            vector<Node*> nodelist;
            inorder(nodelist, root);
            int l = nodelist.size();
            if (l == 1)
            {
                nodelist[0]->right = nodelist[0];
                nodelist[0]->left = nodelist[0];
                return nodelist[0];
            }
            for (int i = 1; i < l - 1; i++) {
                nodelist[i]->left = nodelist[i - 1];
                nodelist[i]->right = nodelist[i + 1];
            }
            nodelist[0]->left = nodelist[l - 1];
            nodelist[0]->right = nodelist[1];
            nodelist[l - 1]->right = nodelist[0];
            nodelist[l - 1]->left = nodelist[l - 2];
            return nodelist[0];
        }
        void inorder(vector<Node*>& nodelist, Node* root)
        {
            if (root == NULL)return;
            inorder(nodelist, root->left);
            nodelist.push_back(root);
            inorder(nodelist, root->right);
        }
    
    展开全文
  • 双向循环链表的实现

    千次阅读 2010-11-28 20:55:00
    对于单链表来说,每个结点都有一个引用域,即next域,用来指向下一个结点,即该结点的后继结点,因此链表中的最后一个节点的引用域必定空,单链表的这种存储... (2)双向循环链表的head指针的prior指向最后

    对于单链表来说,每个结点都有一个引用域,即next域,用来指向下一个结点,即该结点的后继结点,因此链表中的最后一个节点的引用域必定为空,单链表的这种存储方式决定了它的访问方式,只能从单链表的表头进行遍历。而双向循环链表是由双向链表和循环链表组合而成的,双向链中的数据结构中有三个域,前驱指针域,数据域,后继指针域。而循环链表的尾指针指向头指针。双向循环链表具有以下特点:

    (1) 判空条件:head.next==head为空。

    (2)双向循环链表的head指针的prior指向最后一个结点,而next指向第一个结点。而尾结点的next域指向头指针head.

    双向循环链表的实现类,有结点类和链表类。

    下面是双向循环链表的java实现:

     

    Dlnode结点类:

     

    /**


     * Dlnode用来定义双向循环链表 双向循环链表应该包括一个数据域,一个前驱域和一个数据域 最后一个节点指向第一个首节点
     *
     * @author Administrator
     *
     */
    public class Dlnode {

     Object data;// 数据域
     Dlnode prior;// 指向前驱的指针域
     Dlnode next;// 指向后继的指针域

     public Dlnode(Dlnode prior, Object data, Dlnode next) {
      this.prior = prior;
      this.data = data;
      this.next = next;
     }

     public Dlnode() {
      this(null, null, null);
     }

     public Object getData() {
      return data;
     }

     public void setData(Object data) {
      this.data = data;
     }

     public Dlnode getNext() {
      return next;
     }

     public void setNext(Dlnode next) {
      this.next = next;
     }

     public Dlnode getPrior() {
      return prior;
     }

     public void setPrior(Dlnode prior) {
      this.prior = prior;
     }
    }

     

     链表类的实现:

     /**
     * 此类是实现双向循环链表 双向循环链表的特点: (1)空结点:只有一个首结点,其前驱与后继都指向自身。 (2)非空:后一个结点的前驱指向前一个节点
     * 前一个节点的后继指向后一个节点 最后一个节点的后继指向首节点 首节点的前驱指向最后一个节点
     *
     * @author Administrator
     *
     */
    public class DlList {

     Dlnode dlhead;// 链表表头
     int size;

     public DlList() {
      dlhead = new Dlnode();
      dlhead.prior = dlhead;
      dlhead.next = dlhead;
      size = 0;
     }// 构造一个空表

     public DlList(Object[] a) {// 用数组a构造一个双向循环链表
      dlhead = new Dlnode();
      dlhead.prior = dlhead;
      dlhead.next = dlhead;
      Dlnode p = null;
      for (int i = a.length - 1; i >= 0; i--) {
       p = new Dlnode(dlhead, a[i], dlhead.next);
       dlhead.next.setPrior(p);
       dlhead.setNext(p);

      }

      size = a.length;

     }

     public void clear() {
      dlhead = new Dlnode();
      dlhead.prior = dlhead;
      dlhead.next = dlhead;
     }

     /**
      * 找到双向循环链表中第i个节点 首节点是第0个节点,然后 是第1个节点,依次类推
      *
      * @param i
      * @return
      */
     public Dlnode index(int i) {
      Dlnode p;
      int j;
      if (i < 0 || i > size)
       p = null;
      else if (i == 0)
       p = dlhead;
      else {
       p = dlhead.next;
       j = 1;
       while (j < i && p != null) {
        p = p.next;
        j++;

       }

      }

      return p;

     }

     /**
      * 得到第i个节点的data值
      *
      * @param i
      * @return
      */
     public Object get(int i) {
      Dlnode p;
      if (i <= 0 || i > size)
       return null;
      else {
       p = index(i);
       return p.getData();

      }

     }

     /**
      * 计算双向循环链表的长度
      *
      */

     public int len() {
      return size;
     }

     /**
      * 得到data域为el的节点索引号
      *
      * @param el
      * @return
      */
     public int loc(Object el) {
      Dlnode p;
      int j = 1;
      p = dlhead.next;
      while (!p.data.equals(el) && p != dlhead) {// 双向循环链表结束的条件是尾结点的下一个指针是否指向头结点
       j++;
       p = p.next;

      }

      if (p != dlhead)
       return j;
      else
       return 0;

     }

     /**
      * 第一个参数是插入的位置 第二个参数是插入节点的data值
      *
      * @param loc
      * @param el
      * @return
      */
     public boolean insert(int loc, Object el) {
      if (loc < 1 && loc > size + 1)
       return false;
      Dlnode p = index(loc - 1);
      Dlnode q = new Dlnode(p, el, p.next);
      p.next.setPrior(q);
      p.setNext(q);
      size++;

      return true;

     }

     /**
      * 删除结点,提供删除节点的索引号
      *
      */

     public Object delete(int i) {
      if (size == 0 || i < 1 || i > size)
       return null;
      Dlnode p = index(i);
      Object data = p.getData();
      p.prior.setNext(p.next);
      p.next.setPrior(p.prior);
      size--;
      return data;

     }

     public boolean empty() {
      return dlhead.next == dlhead;
     }

    }

     

     

     测试类:

     

    public class TestDllist {

     /**
      * @param args
      */
     public static void main(String[] args) {

      DlList dl = new DlList();

      for (int i = 0; i < 10; i++)
       dl.insert((i + 1), new Integer(i + 1));
      print(dl);

     }

     public static void print(DlList dl) {
      System.out.println("双向循环链表遍历结果:");
      Dlnode p;
      p = dl.dlhead.next;
      while (p != dl.dlhead) {
       System.out.print(p.getData() + " ");
       p = p.next;
      }

     }

    }

     双向循环链表插入与删除时间复杂度的分析:

    双向循环链表的插入与删除的时间复杂度都为O(1).由于删除时寻找前驱结点只需要p->prior即可。

     

     

    展开全文
  • 链表,双向循环链表

    2018-03-05 03:16:30
    循环单链表 只要将单链表最后一个指针域(空指针)指向链表中第一个结点即可(这里之所以说第一个结点而不说是结点是因为,如果循环单链表是带头结点则最后一个结点的指针域要指向...双向循环链表 循环双链表...

    循环单链表

    只要将单链表的最后一个指针域(空指针)指向链表中第一个结点即可(这里之所以说第一个结点而不说是头结点是因为,如果循环单链表是带头结点的则最后一个结点的指针域要指向头结点;如果循环单链表不带头结点,则最后一个指针域要指向开始结点)。

    带头结点的循环单链表当head等于head->next时链表为空; 不带头结点的循环单链表当head等于null时链表为空。

    双向循环链表

    循环双链表的构造源自双链表,即将终端结点的nnext指针指向链表中第一个结点,将链表中第一个结点的prior指针指向终端结点。

    带头结点的循环双链表当head->next和heaad->prior两个指针都等于head时链表为空。 不带头结点的循环双链表当head等于null的时候为空。

    转载于:https://juejin.im/post/5a9cb602f265da238c3a25cc

    展开全文
  • 双向链表及循环链表

    2019-05-13 16:43:55
    双链表和单链表相比,多了一个指向尾指针(tail),双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作,双链表结点的首结点的head指向null,tail指向下一个节点的tail;尾结点的head指向...

    双向链表及循环链表

    双向链表

    双链表和单链表相比,多了一个指向尾指针(tail),双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作,双链表结点的首结点的head指向为null,tail指向下一个节点的tail;尾结点的head指向前一个结点的head,tail 指向为null,是双向的关系
    双向链表图

    双向链表代码

    import java.util.Iterator;
    
    public class TwoWayLink implements Iterable {
    
      Node head = null;
      Node tail = null;
    
      int size;
    
      class Node {
        Node next = null;
        Node previous = null;
        int data;
    
        public Node(int data) {
          this.data = data;
        }
    
        @Override
        public String toString() {
          return "data:" + data;
        }
      }
    
      public void addNode(int d) {
        Node newNode = new Node(d);
        if (head == null) {
          head = newNode;
          tail = newNode;
          size = 1;
          return;
        }
    
        Node tailTmp = tail;
        tailTmp.next = newNode;
        newNode.previous = tailTmp;
        tail = newNode;
        size++;
      }
    
      public Node getNode(int index) {
        if (index == 0) {
          return head;
        }
        if (index + 1 == size) {
          return tail;
        }
        int i = 1;
        Node curNode = head.next;
        while (curNode != null) {
          if (i == index) {
            return curNode;
          }
          curNode = curNode.next;
          i++;
        }
        return null;
      }
    
      public Node removeNode(Node remove) {
        Node previous = remove.previous;
        Node next = remove.next;
        if (remove.equals(head)) {
          next.previous = null;
          head = next;
        } else if (remove.equals(tail)) {
          previous.next = null;
          tail = previous;
        } else {
          previous.next = next;
          next.previous = previous;
        }
        size--;
        return remove;
      }
    
      public int size() {
        return size;
      }
    
      @Override
      public Iterator iterator() {
        return new Iterator() {
          int cursor;
          int lastRet = -1;
    
          @Override
          public boolean hasNext() {
            return cursor != size;
          }
    
          @Override
          public Object next() {
            lastRet = cursor;
            cursor++;
            return getNode(lastRet);
          }
        };
      }
    
      public static void main(String[] args) {
        TwoWayLink twoWayLink = new TwoWayLink();
        twoWayLink.addNode(1);
        twoWayLink.addNode(2);
        twoWayLink.addNode(3);
        System.out.println(twoWayLink.size());
        Iterator iterator = twoWayLink.iterator();
        while (iterator.hasNext()) {
          System.out.println(iterator.next());
        }
      }
    }
    

    循环链表

    节点自身数值data以及所指向的下一个节点next

    package circularLinkedList;
     
    public class Node {
    	//元素类型为int的节点
    	private int data;
    	private Node next;
    	//定义构造器
    	public Node(int i, Node nt){
    		data = i;
    		next = nt;
    	}
    	public Node(int i){
    		this(i,null);
    	}
    	public Node(){
    		this(0,null);
    	}
    	//更改元素数值
    	public void setData(int i){
    		data = i;
    	}
    	//读取元素数值
    	public int getData(){
    		return data;
    	}
    	//更改元素的指向
    	public void setNext(Node nt){
    		next = nt;
    	}
    	//读取元素的指向
    	public Node getNext(){
    		return next;
    	}
    

    关键要素是指定链表的头节点head、尾节点tail以及链表大小size;该数据结构支持在头部增加节点、在尾部增加节点,从头部删除节点及从尾部删除节点

    package circularLinkedList;
     
    public class Linkedlst {
    	private Node head;
    	private Node tail;
    	int size;
    	//构造器
    	public Linkedlst(){
    		tail = head = null;
    		size = 0;
    	}
    	
    	//在链表头部增加节点
    	public void addHead(Node hd){
    	//如果使用该方法增加链表的第一个节点,则head=tail=hd,且next指向自身。
    		if(size==0){
    			hd.setNext(hd);
    			tail = head = hd;
    			size++;
    		}
    		else{
    				tail.setNext(hd);
    				hd.setNext(head);
    				head = hd;
    				size++;
    		}
    	}
    	
    	//在链表尾部增加节点
    	public void addTail(Node tl){
    	//如果使用该方法增加链表的第一个节点,则tail=head= hd,且next指向自身。
    		if(size==0){
    			tl.setNext(tl);
    			tail = head = tl;
    			size++;
    		}
    		else{
    			tail.setNext(tl);
    			tl.setNext(head);
    			tail = tl;
    			size++;
    		}
    	}
    	
    	//删除头部节点,被删掉的head将被自动回收
    	public void delHead(){
    		if(size>1){
    			head = head.getNext();
    			tail.setNext(head);
    			size--;
    		}
    		else if(size==1){
    			head = tail = null;
    			size--;
    		}
    		else{
    			System.out.println("There is no elements in the linked list.");
    		}
    	}
    	
    	//删除尾部节点
    	public void delTail(){
    		if(size>1){
    			Node nd = new Node();
    			nd = head;
    			while(nd.getNext()!=tail){
    				nd = nd.getNext();
    			}
    			nd.setNext(head);
    			size--;
    		}
    		else if(size==1){
    			head = tail = null;
    			size--;
    		}
    		else{
    			System.out.println("There is no elements in the linked list.");
    		}		
    	}
    	
    	//打印全部节点
    	public void printList(){
    		Node nd = new Node();
    		nd = head;
    		try{
    			while(nd.getNext()!=head){
    				System.out.print(nd.getData());
    				System.out.print("->");
    				nd = nd.getNext();
    			}		
    			System.out.print(nd.getData());
    			System.out.print("->");
    			System.out.print(head.getData());
    		}
    		catch(Exception e){			
    			e.printStackTrace();
    		}
    		
    	}
    }
    

    原文:https://blog.csdn.net/elecjack/article/details/51019875

    展开全文
  • 将单链表终端结点的指针端由空指针指向结点,就使整个单链表形成了一个环,这种头尾相连单链表称为单循环链表。 单循环链表和单链表主要差异就在于循环判断条件上,原来是判断p->next是否空,...
  • 漫漫学习数据结构之路(1.链表) 博客代码根据《数据结构》教材思路 我(新手上路)觉得链表的理解和...我比较习惯有头指针head。 首先是链表的构建: #include<stdio.h> #include<stdlib.h> #i...
  • 链表的结构 解析: 每一个结点都有一个数据域,两个指针域。其中一个指针域指向它的直接后继,另外一个指向它的直接前驱。 对于结点来说,它的直接前驱是最后一个结点;对于最后一个结点来说,它的直接后继是...
  • 双向链表双(向)链表中有两条方向不同的链,即每个结点中...将结点和尾结点链接起来,双(向)循环链表双向链表的结点结构和形式描述结点结构(见上图)形式描述如下:typedef char ElemType; struct NodeType2 {
  • 思路 以中序遍历遍历一棵...每次递归调用时候,更新当前遍历结点right指针让其指向结点head,同时更新结点head的left指针让其指向当前遍历结点。 代码void treeToDoubleList(Node p,Node prev,Node head){
  • 删除循环双向链表中的第一个节点,有两种...通过将链表的头指针指定null并释放头指针来简单地完成。head = NULL;free(head);在第二种情况下,链表包含有多个元素(节点),因此条件head->next == head将变为fa...
  • 剑指 Offer 36. 二叉搜索树与双向链表 输入一棵二叉搜索树,将该二叉搜索树...对于双向循环链表,第一个节点前驱是最后一个节点,最后一个节点后继是第一个节点。 下图展示了上面二叉搜索树转化成链表。“head
  • 循环链表:将单链表中终端节点的指针端由null改指向结点,使得整个单链表形成一个环、头尾相接,即单循环链表循环链表)。 循环链表和单链表主要差异在于循环判断条件上: (1)单链表:node.next == ...
  • VS2010显示的错误“0xC0000005: 读取位置 0xfeeefeee 时发生访问冲突”,求大神指教,是否是我新建链表的函数或宏定义中new和delete函数使用错误,还是我新建双向循环链表的算法有问题啊,望不吝赐教!!! 以下是...
  • 循环链表是在线性链表的基础上,将最后一个结点的next设置为头指针。即 |empty – first| -> |data1 – second| -> |data2 – head| 双向链表 定义与结构 双向链表是在线性链表的基础上加入一个指向直接前驱的...
  • 按照上一篇博客的方式用head头结点的话,那构建环形链表的方式就是 1.去掉头节点, 2.将最后一个结点的指针域(原来是NULL)改成指向第一个结点 这时作为函数节点的就是原本最后的一个结点。(因为这样保证了...
  • 链表概念 链表是一种物理存储结构上非连续、非顺序的存储结构,...我们可得 8 种链表的构造方法,接下来,我们将对单向无头非循环链表的构造方法及基本操作进行描述 首先要定义两个结构体,一个代表以 _head 第...
  • 1.4双向链表 ...3、带头双向循环链表的判空条件为head->prior==head或head->next==head; 代码实现: DLinkList.h #pragma once #include <stdio.h> #include <stdlib.h> typ
  • 判断一个链表是否条件head->next==head (头指针) 判断*p最后一个节点条件:p->next=head [cpp] view plaincopy #include  using namespace std;    /*双链表结构*/  ty
  • //*******************双向循环链表**********************// ``` #include"myhead.h" ```typedef struct dou_list_node { int data; struct dou_list_node *next; struct dou_list_node *prev; }dou...
  • 链表

    2021-01-16 22:05:57
    链表链表单链表不带头结点单链表带结点单链表循环单链表双向链表双向不循环链表带头结点的双向不循环链表双向循环链表带头结点的双向循环链表带头结点的双向循环链表的实现 链表 由字面意义可知,链表即链式链接而...
  • 如何实现双向链表的插入、删除操作  循环单链表的出现,虽然能够实现从任一结点出发沿着链能找到其前驱结点,但是时间复杂度O(N)。如果希望能从链表中快速确定某一个结点的前驱,另一个解决方法就是在单链表的每...
  • 输出:双向链表的头结点head 这道题的思路不太困难;我们知道二叉搜索树的中序遍历会得到升序的结果,所以转换有序的链表我们需要进行中序遍历;但由于是双向链表我们需要一个节点保存我们正在遍历的节点的前...
  • 快慢指针在链表中的使用 链表毫无疑问是数据结构中最重要的知识点...给定一个带有结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例1: 输入:[1,2,3,4,5] 输出:...
  • 1 双向链表详解和实现 1.1 双向链表详解 双(向)链表中有两条方向不同链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域... ③将结点和尾结点链接起来,双(向)循环链表。...
  • [C语言]单向链表的构建以及翻转算法 一、基本概念  单向链表的链接方向是单向的,其中每个结点都有指针成员变量指向链表中... 其中head为头结点(不存储数据)、data节点存储数据、pNext存储下一节点的地址。...
  • 判断一个链表是否条件head->next==head (头指针) 判断*p最后一个节点条件:p->next=head [cpp] view plaincopy #include  using namespace std;    /*双链表...
  • 假设pos2,先定义一个指针p指向head结点,用pos作为循环条件,找到pos位置前驱结点; 接着插入,让新结点next指向p后继结点,新结点prior指向p,这样新结点两个指针就安排好了; 接着继续链接p
  • 双向链表,单链表

    2013-09-11 15:55:51
    双链表就是双向链表,就是在单链表每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向链。由头指针head惟一确定。 双链表也可以头尾相链接构成双(向)循环链表。 双链表上插入和删除时间...

空空如也

空空如也

1 2 3 4
收藏数 61
精华内容 24
关键字:

双向循环链表的头指针为head