数据结构(Java版)-习题解答与实验指导

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 list = new 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 front = list.head; //front指向头结点

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 list) {

- 14 -

Node rear=this.head;

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 list) {

this.concat(new SinglyList(list)); //先执行单链表深拷贝，再连接复制的list

}

//返回复制this和list合并连接的单链表，并集，不改变this和list

public SinglyList union(SinglyList list) {

SinglyList result = new SinglyList(this); //深拷贝this单链表

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(null, head); //创建循环单链表的头结点 【答】不能。因为申请结点存储空间时head没有初始化，不是null。实际语义需要的是将该结点地址作为其next域值，做不到。

2.3.2 双链表

1. 双链表结点

习2-11 DoubleNode类能否声明如下，继承单链表结点类Node？为什么？

public class DoubleNode extends Node //双链表结点类，继承单链表结点类

{

public DoubleNode prev; //指向前驱结点的地址域

}

- 16 -

【答】不能。① 虽然该声明没有语法错，但有语义错，因为从父类继承来的next类型为Node，仍然指向单链表结点，等价于以下声明：

public class DoubleNode //双链表结点类

{

public T data;

public Node next; //逻辑错误

public DoubleNode prev; };

此处需要next指向双链表结点，类型是DoubleNode，两者结点结构不同。

② 虽然从语法上DoubleNode可以声明如下，将next重新声明为DoubleNode类型，但是双链表结点与单链表结点无关，并不是两个具有包含关系的概念。

public class DoubleNode extends Node {

public DoubleNode prev,next; //prev指向前驱结点，next指向后继结点

public data,DoubleNode DoubleNode(T prev,DoubleNode next)

{

// 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；子类重新声明的this.next类型为DoubleNode，this.next隐藏super.next，构造方

- 17 -