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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4