本文共 6920 字，大约阅读时间需要 23 分钟。

排序循环双链表

实现

package pers.zhang.linearList;/** * @author zhang * @date 2020/1/15 - 15:16 * * 按升序排序的循环双链表类，继承循环双链表类，E必须实现Comparable
   
    接口，支持对象可比较大小 */public class SortedDoublyLinkedList
    
     > extends CirDoublyLinkedList
     
      {
       //默认构造方法，构造空循环双链表    public SortedDoublyLinkedList(){
           super();                                 //调用父类默认构造方法，构造空循环双链表，默认调用，可省略    }    //将数组中所有对象插入构造排序单链表    public SortedDoublyLinkedList(T[] element){
           super();        for (int i = 0; i < element.length; i++)            this.insert(element[i]);             //插入，根据值的大小决定插入位置    }    //根据指定对象的大小插入在合适位置    public void insert(T x){
           if (x == null)            return;                    //不能插入空对象        if (this.head.pred != head && this.head.pred.data.compareTo(x) < 0){
   //最大值插入在头结点之前，即插入在链尾，O(1)            DLinkNode
      
        q = new DLinkNode
       
        (x, head.pred, head);            head.pred.next = q;            head.pred = q;        }        DLinkNode
        
          p = this.head.next; while (p != head && p.data.compareTo(x) < 0) //寻找插入位置 p = p.next; DLinkNode
         
           q = new DLinkNode
          
           (x, p.pred, p); //插入在p结点之前 p.pred.next = q; p.pred = q; } //不支持父类的insert(int i, T x)和append(T x)方法，将其覆盖并抛出异常。 @Override public void insert(int i, T x){ throw new UnsupportedOperationException("insert(int i, T x)"); //本类不支持该方法 } @Override public void append(T x){ throw new UnsupportedOperationException("append(T x)"); //本类不支持该方法 } //删除首次出现的值为x结点，若没找到指定结点则不删除。O(n) public void remove(T x){ if (x == null) return; DLinkNode
           
             p = this.head.next; while (p != head && p.data.compareTo(x) < 0) //将p定位到待删除的结点 p = p.next; if (p != head && p.data.compareTo(x) == 0){ p.pred.next = p.next; //删除p结点自己 p.next.pred = p.pred; } } //深拷贝构造方法，复制排序双链表list public SortedDoublyLinkedList(SortedDoublyLinkedList
            
              list){ super(list); //调用父类同参数的构造方法，不可省略 } //深拷贝构造方法，由单链表list构造排序循环双链表。直接插入排序，算法同由单链表构造排序单链表 public SortedDoublyLinkedList(SinglyLinkedList
             
               list){ super(); //创建空循环双链表 for (Node
              
                p = list.head.next; p != null; p = p.next) this.insert(p.data); //插入，根据值的大小决定插入位置 } //深拷贝构造方法，由循环单链表list构造排序循环双链表。 //算法不调用insert(x)方法，从双链表中某个结点p开始查找插入位置，如果插入值较大，则p向后走；否则向前走。 public SortedDoublyLinkedList(CirSinglyLinkedList
               
                 list){ super(); //创建空循环双链表 DLinkNode
                
                  p = this.head; for (Node
                 
                   q = list.head.next; q != list.head; q = q.next)//插入q.data，根据值的大小决定插入位置 { //将list单链表中结点依次逐个复制插入到this单链表中，根据q.data值的大小决定插入位置 DLinkNode
                  
                    t; if (p != this.head && q.data.compareTo(p.data) > 0){ while (p != this.head && q.data.compareTo(p.data) > 0) //q.data较大，p向后走 p = p.next; t = new DLinkNode
                   
                    (q.data, p.pred, p); //t插入在p结点之前 p.pred.next = t; p.pred = t; }else{ while (p != this.head && q.data.compareTo(p.data) < 0) //q.data较小，p向前走 p = p.pred; t = new DLinkNode
                    
                     (q.data, p, p.next); //t插入在p结点之后 p.next.pred = t; p.next = t; } p = t;// System.out.println(this.toString()+"，p="+p.data.toString()); } } //深拷贝构造方法，由循环双链表list构造排序循环双链表，直接选择排序，删除再插入算法/* public SortedDoublyLinkedList(CirDoublyLinkedList
                     
                       list) { super(list); //深拷贝list循环双链表 DLinkNode
                      
                        srear=head; //指向排序循环双链表尾 while (srear.next!=head) //原循环双链表不空 { DLinkNode
                       
                         min=srear.next; //min指向最小值结点 for (DLinkNode
                        
                          p=min.next; p!=head; p=p.next) //p遍历循环双链表 if (p.data.compareTo(min.data)<0) //比较，min记住最小值结点 min = p; if (min.pred!=srear) { min.pred.next = min.next; //从链表原位置删除min结点 min.next.pred = min.pred; min.next=srear.next; //将min结点插入srear之后 min.pred=srear; srear.next.pred = min; srear.next = min; } srear = min; //srear指向排序循环双链表尾 } }*/ //深拷贝构造方法，由循环双链表list构造排序循环双链表，直接选择排序，交换元素算法 //n-1趟，每趟遍历单链表寻找到最小值结点，交换结点元素到前面，不删除和插入结点。算法同排序单链表 public SortedDoublyLinkedList(CirDoublyLinkedList
                         
                           list) { super(list); //深拷贝list循环双链表 for (DLinkNode
                          
                            first=head.next; first!=head; first=first.next) //first指向待排序双链表第一个结点 { //n-1趟，每趟遍历双链表寻找到最小值结点，交换结点元素到前面 DLinkNode
                           
                             min=first; //min指向最小值结点 for (DLinkNode
                            
                              p=min.next; p!=head; p=p.next) //p遍历循环双链表一趟，找出最小值结点 if (p.data.compareTo(min.data)<0) //比较，min记住最小值结点 min = p; if (min!=first) //交换min结点元素到前面 { T temp = min.data; min.data = first.data; first.data = temp; } System.out.println(this.toString()); } } //归并两条排序循环双链表，将list中所有结点归并到当前排序循环双链表中，合并后设置list为空 public void merge(SortedDoublyLinkedList
                             
                               list) { DLinkNode
                              
                                p=this.head.next; DLinkNode
                               
                                 q=list.head.next; while (p!=this.head && q!=list.head) if ((p.data).compareTo(q.data)<0) //比较两个链表当前结点值 p = p.next; else { //将q结点插入到结点之前 q.pred = p.pred; p.pred.next = q; p.pred = q; q = q.next; q.pred.next = p; } if (q!=list.head) //将list链表中剩余结点并入当前链表尾 { this.head.pred.next = q; q.pred = this.head.pred; while (q.next!=list.head) q = q.next; q.next = this.head; this.head.pred = q; } list.head.next=list.head; //合并后设置list为空 list.head.pred=list.head; }}
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

测试：

package pers.zhang.linearList;/** * @author zhang * @date 2020/1/15 - 15:24 */public class SortedDoublyLinkedList_ex {
       public static Integer[] random(int n)              //返回产生n个随机数的数组    {
           Integer[] elements = new Integer[n];        for (int i=0; i
   
     list1 = new SortedDoublyLinkedList
    
     (random(9));//        list1.insert(-1, -1);                    //覆盖单链表类的方法，没有执行操作//        list1.insert(-2);                        //插入指定值结点，调用排序单链表类的方法        System.out.println("list1: "+list1.toString());/*        SortedDoublyLinkedList
     
       list2 = new SortedDoublyLinkedList
      
       (list1);//深拷贝        System.out.println("list2: "+list2.toString());        list1.remove(list1.length()-1);          //删除最后结点，参数类型是int，调用单链表类的方法        list1.remove(list1.get(0));              //删除首个结点，参数类型是Integer，调用排序单链表类的方法        list1.remove(new Integer(50));           //删除指定值结点，可能没删除        System.out.println("list1: "+list1.toString());        list1.printPrevious();        System.out.println("list2: "+list2.toString());        list2.printPrevious();*/        //习题2        CirSinglyLinkedList
       
         list3 = new CirSinglyLinkedList
        
         (random(9));//单链表 System.out.println("list3: "+list3.toString()); SortedDoublyLinkedList
         
           list4=new SortedDoublyLinkedList
          
           (list3);//由单链表构造排序循环双链表 System.out.println("list4: "+list4.toString());/* //第9章， list3.merge(list4); //归并两条排序循环双链表 System.out.println("归并，list3: "+list3.toString()); list3.printPrevious(); System.out.println("list4: "+list4.toString());/* //第9章， 由循环双链表list构造排序循环双链表，直接选择排序 CirDoublyLinkedList
           
             list1 = new CirDoublyLinkedList
            
             (random(9)); System.out.println("list1: "+list1.toString()); SortedDoublyLinkedList
             
               list2 = new SortedDoublyLinkedList
              
               (list1); System.out.println("list2: "+list2.toString()); list2.printPrevious();*/ }}
              
             
            
           
          
         
        
       
      
     
    
   

程序运行结果如下：

list1: (-2, 0, 1, 4, 8, 34, 38, 67, 86, 88)list2: (-2, 0, 1, 4, 8, 34, 38, 67, 86, 88)list1: (0, 1, 4, 8, 34, 38, 67, 86)(86, 67, 38, 34, 8, 4, 1, 0)list2: (-2, 0, 1, 4, 8, 34, 38, 67, 86, 88)(88, 86, 67, 38, 34, 8, 4, 1, 0, -2)list3: (45, 6, 37, 8, 19, 86, 26, 77, 22)list4: (6, 8, 19, 22, 26, 37, 45, 77, 86)list3: (71,53,51,53,20,0,74,34,94)list4: (0,20,34,51,53,53,71,74,94)

转载地址：http://kypqb.baihongyu.com/