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

法中super(data,next);语句对super.next赋值。如此声明，没有意义。

习2-12 DoubleNode类是否需要声明析构方法和拷贝构造方法？为什么？

【答】参见前述【习题2-8】。

2. 双链表

【思考题2-11<2>】设p指向双链表某个结点，写出在p结点之后插入值为x结点的语句。

【答】语句如下：

DoubleNode q = new DoubleNode(x,p,p.next); //插入在p结点之后

if (p.next!=null) //中间插入 p.next.prev = q; //① p.next = q; //② 再问：如果后两条语句次序颠倒，将会怎样？

【答】导致错误，如图2.10所示，p.next.prev = q相当于q.prev = q。

prevdatanexthead∧pa0①q②xa1?an-1∧

图2.9 双链表后插入结点时语句次序错误

3. 循环双链表

习2-13 循环双链表类能否声明为如下继承单链表类，继承head

成员变量？为什么？

public class CirDoublyList extends SinglyList //循环双链表类，继承单链表类

【答】不能。因为，如果继承，等价于以下声明：

public class CirDoublyList extends SinglyList //循环双链表类，继承单链表类

{ Node head; //继承父类的成员变量，数据类型错误

- 18 -

};

其中，head的数据类型是Node，指向单链表结点，类型错误。应该是DoubleNode。

再者，循环双链表和单链表是实现线性表的两种存储结构，两者之间没有关联，不是继承关系。可以只有循环双链表，而没有单链表。

【习2.3】 循环双链表的迭代方法。

以下4个方法实现循环双链表的迭代功能，时间复杂度都是O(1)，这就是设计循环双链表的目的。

public DoubleNode first() //返回循环双链表第一个结点，O(1)

{ return (head.next==head) ? null : head.next; }

public DoubleNode next(DoubleNode p) //返回p的后继结点，O(1)

{ return (head.next==head || p==null || p==head || p==head.prev) ? null : p.next;

}

public DoubleNode previous(DoubleNode p) //返回p的前驱结点，O(1)

{ return (head.next==head || p==null || p==head || p==head.next) ? null : p.prev;

}

public DoubleNode last() //返回循环双链表最后一个结点，O(1)

{ return (head.prev==head) ? null : head.prev; }

【习2.4】 循环双链表合并连接。

CirDoublyList类声明以下成员方法，设已创建两条循环双链表，

将它们首尾相接实现合并连接，算法描述如图2.11所示。

//在this循环双链表之后，合并连接list中所有结点，并设置list为空

public void addAll(CirDoublyList list)

- 19 -

rearthis.headablist.head（a）两条循环双链表cdxyz

cdxyrearzthis.headablist.head（b）将两条循环双链表首尾相接合并，设置list为空链表图2.10 合并连接两条循环双链表

- 20 -

第3章 串

目的：串作为特殊线性表的实现与应用。

内容：字符串的基本概念，串抽象数据类型，顺序和链式两种存储结

构存储串的特点；采用顺序存储结构实现串的各种操作算法；

Brute-Force算法和KMP算法。 两种串的模式匹配算法及应用：

要求：掌握顺序串类的基本操作实现方法，掌握串的模式匹配算法及

应用。

重点：串数据类型的各种操作实现，两种串的模式匹配算法及应用。

KMP模式匹配算法，next数组在KMP算法中的作用及产生过难点：

程。

实验：顺序串类的基本操作及串的模式匹配算法。

3.1 串抽象数据类型

\有什么差别？

【答】\是空串，长度为0；\ \是空格串。

3-2 什么是串？串和线性表在概念上有何差别？串操作的主要特点有哪些？

【答】字符串（string，简称串）是数据元素的数据类型为字符的线性表。

从逻辑结构看，串是一种特殊的线性表，其特殊性在于线性表中的每个元素是一个字符。作为一种抽象数据类型，串有自己的一组操作，其操作特点与线性表不同。

3-3 串的存储结构有几种？串通常采用什么存储结构？

【答】串可采用顺序存储结构和链式存储结构，串通常采用顺序存储结构。

3-4 哪些操作会改变串的长度？当串的存储空间不够时，应该如何处理？

【答】插入、删除子串会改变串的长度。当串的存储空间不够时，

应该申请一个容量更大的数组，并将原串中的所有字符复制到新串中。

3-1 \和\

- 21 -

3.2 串的存储和实现

3.2.1 串的存储结构

语言的'a'和\有什么差别？它们的存储结构有什么不同？

【答】数据类型不同，存储结构不同。'a'是char字符常量，占用2个字节存储字符的Unicode编码；\是字符串常量，数据类型是java.lang.String类，采用字符数组存储。

3.2.2 常量字符串类

1. 设计字符串类的必要性

【习3.1】 C/C++语言，string.h中的strcpy()和strcat()函数存在下标越

3-5 Java

界错误。

本题目的：strcpy()和strcat()函数存在下标越界错误；设计字符串类的必要性。

#include using namespace std; #include int main() {

char src[]=\

p = strcpy(dest,src); //复制src串（包括'\\0'）到dest，返回dest地址

cout<<\;

return 0; }

程序运行结果如下，复制前后src和dest两个字符串占用的存储单元如图3.1所示。

src=\ //有错误

- 22 -