数据结构--可排序单链表 淡淡的烟草味﹌ 2021-08-13 21:05 425阅读 0赞 ### 可排序单链表 ### ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70] ### 实现 ### package pers.zhang.linearList; /** * @author zhang * @date 2020/1/14 - 14:22 * * 按升序排序的单链表类，继承单链表类，T必须实现Comparable<T>接口，支持对象可比较大小 */ public class SortedSinglyLinkedList<T extends Comparable<T>> extends SinglyLinkedList<T> { public SortedSinglyLinkedList(){ //默认构造方法 super(); //调用父类默认构造方法，默认调用，可省略 } //将elements数组中所有对象插入构造排序的单链表，直接插入排序 public SortedSinglyLinkedList(T[] element){ super(); //创建空单链表，调用父类默认构造方法，默认调用，可省略 for (int i = 0; i < element.length; i++) //若element==null，抛出空对象异常 this.insert(element[i]); //插入一个结点，根据值的大小决定插入位置 } //插入值为x结点，根据x值大小插入在合适位置 //重载父类的insert(i,x)方法，因参数不同没有覆盖父类的insert(i,x)方法 public void insert(T x){ if (x == null) return; //不能插入空对象 Node<T> front = this.head, p = front.next; //front是p的前驱结点 while (p != null && p.data.compareTo(x) < 0){ //寻找插入位置 front = p; p = p.next; } front.next = new Node<T>(x, p); //创建结点插入在front之后，p之前 } //不支持父类的insert(int i, T x)和append(T x)方法，将其覆盖并抛出异常。 public void insert(int i, T x){ throw new UnsupportedOperationException("insert(int i, T x)"); //本类不支持该方法 } public void append(T x){ throw new UnsupportedOperationException("append(T x)"); //本类不支持该方法 } //删除首次出现的值为x结点，若没找到指定结点则不删除。O(n) //重载父类的remove(T x)方法，因参数不同没有覆盖父类的remove(T x)方法 public void remove(T x){ if (x == null) return; Node<T> front = this.head, p = front.next; //front是p的前驱结点 while (p != null && p.data.compareTo(x) < 0){ //寻找待删除的结点 front = p; p = p.next; } if (p != null && p.data.compareTo(x) == 0) front.next = p.next; //删除p结点 } //深拷贝构造方法，复制单链表 public SortedSinglyLinkedList(SortedSinglyLinkedList<T> list){ super(list); //调用父类同参数的构造方法，不可省略 } //深拷贝构造方法，由单链表list构造排序单链表，直接插入排序 /* public SortedSinglyLinkedList(SinglyLinkedList<T> list){ super(); //创建空单链表 for (Node<T> p = list.head.next; p != null; p = p.next) this.insert(p.data); //根据值的大小决定插入位置，调用排序单链表类的插入方法 }*/ //顺序查找关键字为key元素，返回首次出现的元素，若查找不成功返回null //key可以只包含关键字数据项，由T类的compareTo()提供比较对象大小和相等的依据 //覆盖父类SinglyLinkedList的同名方法 public T search(T key){ if (key == null) return null; for (Node<T> p = this.head.next; p != null && p.data.compareTo(key) <= 0; p = p.next) if (p.data.compareTo(key) == 0) //由compareTo()提供比较对象大小和相等的依据 return p.data; return null; } //深拷贝构造方法，由单链表list构造排序单链表，直接选择排序 /* //第3版程序，每趟寻找最小值结点，交换到前面，通过删除、插入结点方式实现交换 public SortedSinglyLinkedList(SinglyLinkedList<T> list) { super(list); //深拷贝list单链表 Node<T> srear=head; //指向排序单链表尾 while (srear.next!=null) //原单链表不空 { Node<T> mfront=srear, min=mfront.next; //min指向最小值结点，mfront指向min的前驱 Node<T> pfront=min, p=min.next; //p遍历单链表，pfront指向p的前驱结点 while (p!=null) { if (p.data.compareTo(min.data)<0) //比较，min记住最小值结点 { mfront = pfront; //mfront是min的前驱结点 min = p; } pfront = p; //pfront是p的前驱结点 p = p.next; } if (mfront!=srear) { mfront.next = min.next; //从链表原位置删除min结点 min.next=srear.next; //将min结点插入srear之后 srear.next = min; } srear = min; //srear指向排序单链表尾 } }*/ //深拷贝构造方法，由单链表list构造排序单链表，直接选择排序 //第4版改进程序，n-1趟，每趟遍历单链表寻找到最小值结点，交换结点元素到前面，不删除和插入结点 public SortedSinglyLinkedList(SinglyLinkedList<T> list) { super(list); //深拷贝list单链表 for (Node<T> first=head.next; first!=null; first=first.next) //first指向待排序单链表第一个结点 { //n-1趟，每趟遍历单链表寻找到最小值结点，交换结点元素到前面 Node<T> min=first; //min指向最小值结点 for (Node<T> p=min.next; p!=null; p=p.next) //遍历单链表一趟，找出最小值结点 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(SortedSinglyLinkedList<T> list) { Node<T> front=this.head, p=front.next; //p指向this单链表的第一个结点 Node<T> q=list.head.next; //q指向list单链表的第一个结点 while (p!=null && q!=null) if ((p.data).compareTo(q.data)<0) //比较两个单链表当前结点值 { front = p; //front指向p的前驱结点 p = p.next; } else { //将q结点插入到front结点之后 front.next = q; q = q.next; front = front.next; front.next = p; } if (q!=null) //将list链表中剩余结点并入当前链表尾 front.next=q; list.head.next=null; //设置list单链表设置为空链表 } } 测试： package pers.zhang.linearList; /** * @author zhang * @date 2020/1/14 - 14:28 */ public class SortedSinglyLinkedList_ex { public static Integer[] random(int n) //返回产生n个随机数的数组，同例2.3 { Integer[] elements = new Integer[n]; for (int i=0; i<n; i++) elements[i] = (int)(Math.random()*100); //产生随机数 return elements; } public static void main(String args[]) { /* SortedSinglyLinkedList<Integer> list1 = new SortedSinglyLinkedList<Integer>(random(9)); // list1.insert(-1, -1); //覆盖单链表类的方法，抛出异常 list1.insert(-2); //插入指定值结点，调用排序单链表类的方法 System.out.println("list1: "+list1.toString()); SortedSinglyLinkedList<Integer> list2=new SortedSinglyLinkedList<Integer>(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()); System.out.println("list2: "+list2.toString()); SinglyLinkedList<Integer> list3 = new SinglyLinkedList<Integer>(random(9));//单链表 System.out.println("list3: "+list3.toString()); SortedSinglyLinkedList<Integer> list4=new SortedSinglyLinkedList<Integer>(list3);//由单链表构造排序单链表 System.out.println("list4: "+list4.toString());*/ //由单链表list构造排序单链表，直接选择排序 SinglyLinkedList<Integer> list1 = new SinglyLinkedList<Integer>(random(7)); System.out.println("单链表list1: "+list1.toString()); SortedSinglyLinkedList<Integer> list2 = new SortedSinglyLinkedList<Integer>(list1); System.out.println("排序单链表list2: "+list2.toString()); // list1.set(0, new Integer(list1.get(0).intValue()+100)); // System.out.println("list1: "+list1.toString()); // System.out.println("list2: "+list2.toString()); // list1.merge(list2); //归并两条排序单链表 // System.out.println("归并，list1: "+list1.toString()); // System.out.println("list2: "+list2.toString()); } } 输出如下： list1: (-2, 1, 21, 21, 23, 44, 59, 65, 83, 95) list2: (-2, 1, 21, 21, 23, 44, 59, 65, 83, 95) list1: (1, 21, 21, 23, 44, 59, 65, 83) list2: (-2, 1, 21, 21, 23, 44, 59, 65, 83, 95) //习题2 list3: (92, 98, 45, 74, 66, 0, 87, 45, 2) list4: (0, 2, 45, 45, 66, 74, 87, 92, 98) 归并，list1: (11, 12, 20, 24, 29, 34, 35, 40, 51, 55, 78, 86, 89) list2: () list1: (1, 7, 8, 34, 36) list2: (27, 78, 85, 90) 归并，list1: (1, 7, 8, 27, 34, 36, 78, 85, 90) list2: () //第9章，由单链表list构造排序单链表，选择排序 list1: (95, 22, 99, 9, 28, 67, 71, 82, 86) list2: (9, 22, 28, 67, 71, 82, 86, 95, 99) list1: (70, 45, 53, 48, 11, 1, 4) list2: (1, 4, 11, 45, 48, 53, 70) list1: (170, 45, 53, 48, 11, 1, 4) list2: (1, 4, 11, 45, 48, 53, 70) //第4版改进程序 单链表list1: (95,79,41,26,45,92,82) (26,79,41,95,45,92,82) (26,41,79,95,45,92,82) (26,41,45,95,79,92,82) (26,41,45,79,95,92,82) (26,41,45,79,82,92,95) (26,41,45,79,82,92,95) (26,41,45,79,82,92,95) 排序单链表list2: (26,41,45,79,82,92,95) 程序调试情况如下： SinglyLinkedList<Object> list3 = new SinglyLinkedList<Object>(); // SortedSinglyLinkedList<Object> list4 = new SortedSinglyLinkedList<Object>(); //编译错，Object类不能作为E的实际参数，没有实现实现Comparable<E>接口 SortedSinglyLinkedList<Integer> list4 = new SortedSinglyLinkedList<Integer>(); // list4.insert(new Object()); //编译错，参数类型不匹配 */ [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/4388e08091eb48e5b66e90b833a15acf.png
还没有评论，来说两句吧...