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

}

?注意：虽然union(list)方法与addAll(list)方法功能相同，但不能将它们重载如下，因为，参数列表相同而返回值不同，产生二义性，编译器不能根据方法的参数列表确定执行重载方法中的哪一个。

public void addAll(SeqList list)

public SeqList addAll(SeqList list) //语法错，参数列表相同时不能重载

② 排序顺序表表示可重复的排序集合，元素按关键字大小排序。 SortedSeqList类继承SeqList类的以下成员方法：

public void addAll(SeqList list) //可用，参数list可引用SortedSeqList实例。

//其中，执行insert(x)方法运行时多态，当this引用子类实例时，执行排序顺序表按值插入

//合并结果this仍然是排序顺序表

public SeqList union(SeqList list) //算法正确，不可用。希望返回排序顺序表

//因为，当this引用子类实例时，声明result和创建的仍然是SeqList实例，无法创建子类

//实例，就无法实现运行时多态，总是执行SeqList类的插入

因此，SortedSeqList类需要覆盖union(list)方法如下：

//覆盖，返回值类型不同但赋值相容。能与父类实例运算 public SortedSeqList union(SeqList list) {

SortedSeqList result = new SortedSeqList(this); //创建子类实例。只此一句不同

result.addAll(list); //继承父类方法，运行时多态，排序顺序表合并，按值插入

return result; //返回SortedSeqList对象 }

- 8 -

综上所述，SeqList类对于集合并操作的“有所为，有所不为”原则如下。

? 声明void addAll(list)方法，子类继承，运行时多态。 ? 不声明SeqList union(list)方法，因为，无法运行时多态。 一个类为一个功能只需提供一种实现，至于是否返回对象，由调用者决定，通过深拷贝和addAll(list)方法可得到。

2.3 线性表的链式存储和实现

2.3.1 单链表

1. 单链表的结点

习2-6 写出图2.3所示数据结构的声明。

table∧?∧∧Node?∧

图2.3 一种数据结构

【答】table可声明为数组或顺序表，元素为结点或单链表，声明为以下4种之一：

Node table[]; //一维数组，元素为结点

SinglyList table[]; //一维数组，元素为单链表

SeqList> table; //顺序表，元素为结点

SeqList> table; //顺序表，元素为单链表

【习题2-8】单链表结点类问题讨论。 ① Node类声明构造方法

当一个类没有声明构造方法时，Java提供默认构造方法。例如：

- 9 -

public Node() //提供默认构造方法

{ super(); //默认调用父类的无参数构造方法

}

当一个类声明了构造方法时，Java不再提供默认构造方法。例如，当Node类声明了Node(T data,Node next)构造方法时，Java不再提供默认构造方法Node()。如果Node类需要Node()构造方法，必须自己声明。

Java方法参数没有默认值。例如，Node类可以声明以下构造方法：

public Node(T data) { this(data,null); }

但不能将Node(T data,Node next)构造方法声明为如下形式：

public Node(T data,Node next=null) ② Node类不需要声明析构方法

Node类从Object父类继承了析构方法，并且Java语言将自动释放不再使用的存储空间。因此，Node类不需要声明析构方法。

③ Node类不需要声明拷贝构造方法

Java不提供默认拷贝构造方法。Node类如果声明拷贝构造方法以下：

public Node(Node p) //拷贝构造方法，复制p引用的结点

{ this(p.data,p.next); }

相当于如下：

public Node(Node p)

{ this.data = p.data; //this.data引用p.data，对象引用赋值，两个结点引用同一个元素

this.next = p.next; //this.next指向p的后继结点，结点对象引用赋值，逻辑错误

}

由于Java的赋值=采用引用模型，执行结果如图2.4所示，this.next指向p的后继结点，并没有创建结点，只将p的后继结点作为当前结

- 10 -

结点的后继结点，产生逻辑错误。因此，Node类不能声明浅拷贝构造方法。

datanextp

this图2.4 Node类浅拷贝

由于创建结点是单链表执行的操作，所以，Node类不需要声明拷贝构造方法。

④ Node类可声明以下方法：

public boolean equals(Object obj) //比较两个结点值是否相等，覆盖Object类的equals(obj)方法

{

return obj==this || obj instanceof Node && this.data.equals(((Node)obj).data);

}

⑤ 比较对象大小

Node是单链表和排序单链表的结点类。

单链表不需要比较元素大小，所以Node类不能声明实现Comparable接口。

排序单链表需要比较元素大小，以下排序单链表类声明，约定能够比较T对象大小。

//排序单链表类（升序），继承单链表类，T或T的某个祖先类实现Comparable接口

public class SortedSinglyList> extends SinglyList

2. 单链表的基本操作

【思考题2-5】 遍历单链表，如果将

p=p.next语句写成p.next=p，结果

会怎样？画出示意图。

【答】语句p=p.next使p移动到后继结点，此时结点间的链接关系没有改变。如果写成p.next=p，则使p.next指向p结点自己，改变了结点间的链接关系，并丢失后继结点，如图2.5所示，遍历算法也变成死

- 11 -

循环。

pheada0a1?ai?an-1∧ 图2.5 p.next=p改变结点间的链接关系

front指向非空单链表中的某个结点，在front结点之

后插入p结点，执行以下语句结果会怎样？画出示意图。

Node p = new Node(x);

front.next = p; //① p.next = front.next; //②

【答】②句相当于p.next = p;，产生错误，结点间的链接关系如图2.6所示。

【思考题2-6】 设

datanextheada0a1?frontai①px②ai+1?an-1∧

图2.6 插入语句次序错误

错误原因：上述后两条语句次序颠倒。对front.next赋值将改变结点间的链接关系，从而丢失后继结点地址。因此，在改变结点链接关

系时，应该先获得front.next的值，再对其赋值。头插入存在同样问题。

3. 带头结点的单链表

【习2.1】 使用单链表求解Josephus环问题。

将例2.1程序中创建SeqList对象的语句替换为如下，其余代码不变，

则使用单链表也可求解Josephus环问题。

SinglyList list = new SinglyList();

上述程序虽然能够运行，但是，效率太低。一是，每次循环调用单链表的size()和remove(i)方法，都要从头开始再次遍历单链表，时间复杂度都是O(n)；再有，每次计数，欲删除第i个结点，需要再次查找使front指向第i个结点的前驱。

修改例2.1程序，使用单链表求解Josephus环问题，遍历次数最少。

//求解Josephus环，n（>0）指定长度；s指定计数的起始位置，

- 12 -