数据结构(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 -