0≤s public Josephus(int n, int s, int d) { if (n<=0 || s<0 || s>=n || d<=0 || d>=n) throw new java.lang.IllegalArgumentException(\,s=\,d=\//无效参数异常 System.out.print(\,\ SinglyList for (int i=n-1; i>=0; i--) list.insert(0, (char)('A'+i)+\ //单链表头插入,O(1) System.out.println(list.toString()); //输出单链表的描述字符串,O(n) //以下求解Josephus环 Node for (int j=0; front!=null && j front = front.next; while (n>1) //多于一个元素时循环 { for (int j=1; j { front = front.next; if (front==null) //实现循环计数 front = list.head.next; } if (front.next==null) //若front指向最后一个结点,则删除第0个结点 front = list.head; System.out.print(\删除\,\ - 13 - front.next = front.next.next; //删除front的后继结点,包括头、中间/尾删除 n--; System.out.println(list.toString()); } System.out.println(\被赦免者是\ //get(0)获得元素,O(1) } 执行new Josephus(5,0,3),单链表的变化过程如图2.7所示。 datanextheadABfrontCDE∧(a) 从A开始计数,删除C结点;front指向C结点的前驱B,中间删除frontheadABDE∧(b) 从D开始计数,删除A,循环计数;头删除frontheadBDE∧ (c) 从B开始计数,删除E;尾删除frontheadBD∧headD∧(e) 一个结点的单链表(d) 从B开始计数,删除B,循环计数图2.7 使用单链表求解Josephus(5,0,3)环问题的执行过程 【习2.2】 集合并运算,单链表深拷贝的应用。 本题目的:① 单链表作为方法参数与返回值,传递对象引用;② 单链表深拷贝应用。 当对象作为方法的参数或返回值时,参数传递原则同赋值,“引用参数传递对象引用”,即形式参数获得实际参数的对象引用。 SinglyList //在this单链表之后连接list的所有结点,集合并;设置list为空,O(n) public void concat(SinglyList - 14 - Node while (rear.next!=null) //寻找this单链表的最后一个结点 rear = rear.next; rear.next = list.head.next; //尾插入list单链表 list.head.next=null; //设置list为空,否则逻辑错。方法体内可改变参数list引用的单链表 } //复制list所有结点插入到this单链表之后,集合并,不改变list public void addAll(SinglyList this.concat(new SinglyList } //返回复制this和list合并连接的单链表,并集,不改变this和list public SinglyList SinglyList result.addAll(list); return result; //返回result引用的单链表,释放result变量 } 设创建单链表lista和listb,分别调用上述方法,算法描述如图2.14所示。 实际参数形式参数headlistathislistbdatanexta∧xby∧rearc list(a) 调用lista.concat(listb),传递对象引用,this、list分别引用lista、listb对象; 在this之后链接list,则两条单链表共用x、y结点,逻辑错;设置list为空- 15 - listathislistblistheadax∧xbyy∧∧rearc (b) 调用lista.addAll(listb),list深拷贝listb,this连接的是list。释放list,不改变listbheadlistathisresultlistblist∧aaxxbbyy∧∧cc∧rear (c) 调用lista.union(listb),result(深拷贝this)连接list(深拷贝listb), 返回result引用的单链表。释放result和list,不改变lista、listb图2.8 集合并运算,单链表深拷贝的应用 4. 循环单链表 【思考题2-10】能否使用以下语句创建循环单链表的头结点?为什么? head = new Node 2.3.2 双链表 1. 双链表结点 习2-11 DoubleNode类能否声明如下,继承单链表结点类Node?为什么? public class DoubleNode { public DoubleNode } - 16 - 【答】不能。① 虽然该声明没有语法错,但有语义错,因为从父类继承来的next类型为Node public class DoubleNode { public T data; public Node public DoubleNode 此处需要next指向双链表结点,类型是DoubleNode ② 虽然从语法上DoubleNode public class DoubleNode public DoubleNode public data,DoubleNode { // super(data,next); //语义错,赋值super.next(类型为Node super(data,null); this.next = next; //赋值this.next(类型为DoubleNode this.prev = prev; } } ?注意:此时DoubleNode类有两个next,使用this和super引用可区分两者,从父类继承来的super.next类型为Node - 17 -