Week 2 - Linked Lists, Trees, and Beyond

Update

本周题目更新说明：

1. 实现树的时候，insert_after函数和delete_node也适合使用递归实现。因此如果你不使用类实现树，这两个函数的形式修改为void insert_after(TNode *node, int x, int y)和void delete_node(TNode *node, int x)。（如果你使用类实现，函数形式不做修改。不在要求的函数接口中加入引用参数的原因是根节点的指针应该是对类的用户不可见的；此时你可以用额外的私有成员函数进行递归。）PPT和网站内容已经更新，修改的内容已经标红。按照旧版本实现的同学不扣分。
2. 题目使用命令加参数的形式作为输入的本意是保持可读性的同时简化输入输出的处理。鉴于同学们对这种类型的输入处理方式不够熟练，以第一题为例，这里提供一种简便的输入处理方式。强烈建议大家把提交的程序改成这种方式处理输入。

int main() {
	LinkedList l;
	string s;  // std::string类
	int x, y;
	while (cin >> s) {
    	if (s == "insert_at_beginning") {
        	cin >> x;
        	l.insert_at_beginning(x);
    	} else if (s == "insert_at_ending") {
        	cin >> x;
        	l.insert_at_ending(x);
    	} else if (s == "insert_after") {
        	cin >> x >> y;
        	l.insert_after(x, y);
    	} else if (s == "delete") {
        	cin >> x;
        	l.delete_node(x);
    	} else if (s == "print") {
        	cin >> x;
        	l.print(x);
    	} else if (s == "reverse_print") {
        	cin >> x;
        	l.reverse_print(x);
    	}
	}
	return 0;
} 

3. 以cin >> s作为while语句的判断条件是什么意思？简而言之，>>是一种操作符（类似加号），功能是读入，返回值是其第一个操作数（此处即为cin）。因此while(cin >> s)这行代码的意思是先读入字符串s，再用cin作为while的判断条件。cin是一个“输入流”，当其用作判断条件时，如果还有剩余内容可以读取，则相当于true，如果内容已经读取完毕，则相当于false。因此，这个while循环将会不断执行直到“输入结束”。当使用文件输入，“输入结束”意味着文件末尾；若使用标准输入（命令行输入），Windows下命令行使用Ctrl-Z，Linux/MacOS下使用Ctrl-D快捷键表示输入结束。在Visual Studio下，这个快捷键可能无法正常工作，你可以使用Ctrl-C强制停止程序。

题目 1 - 链表与递归回顾

1 题目要求

本次练习要求实现一个单链表，实现插入、删除和正逆序输出功能。链表每个节点存储一个数字（int）。请注意按照实现要求一节的要求完成。

题目要求程序读入一系列命令，按照命令构造链表或输出链表内容。命令的格式如下：

• insert_at_beginning <x>：在链表头插入数字x；
• insert_at_ending <x>：在链表尾插入数字x；
• insert_after <x> <y>：寻找链表中第一次出现数字x的位置，如果x存在，在后面插入y；
• delete <x>：寻找链表中第一次出现数字x的位置，如果存在，将其删除；
• print <n>：依次输出链表前n个数字（空格隔开，结尾换行）；特别地，如果n == -1，输出整个链表；
• reverse_print <n>：逆序输出链表前n个数字（空格隔开，结尾换行）；特别地，如果n == -1，输出整个链表。

2 实现要求

本次题目要求实现以下函数（每个函数功能请严格按照要求完成，不要修改）：

• struct Node;
• void insert_at_beginning(int x);按照上面命令描述实现；
• void insert_at_ending(int x);按照上面命令描述实现；
• void insert_after(int x, int y);按照上面命令描述实现；
• void delete_node(int x);按照上面命令描述实现；
• void print(int n); 按照上面命令描述实现；请用循环实现；
• void reverse_print(Node *node, int n);：请用递归实现。

如果你有能力将链表实现成一个类，请实现以下类和函数：

• class LinkedList;：链表类；
• class LLNode;：链表的节点类，存储数字和指向下一个节点的指针；
• void LinkedList::insert_at_beginning(int x);：按照上面命令描述实现；
• void LinkedList::insert_at_ending(int x);：按照上面命令描述实现；
• void LinkedList::insert_after(int x, int y);：按照上面命令描述实现；
• void LinkedList::delete_node(int x);按照上面命令描述实现；
• void LinkedList::print(int n);：按照上面命令描述实现，请用循环实现；
• void LinkedList::reverse_print(int n);：按照上面命令描述实现，请用递归实现。你可能需要另外实现一个成员函数来实际完成递归。

3 样例输入输出

输入：

insert_at_beginning 1
insert_at_beginning 2
insert_at_ending 5
insert_at_ending 6
print -1
delete 6
insert_after 5 55
delete 1
print 3
reverse_print -1

输出：

2 1 5 6
2 5 55
55 5 2

题目 2 - 链表分叉变成树

1 前导知识：树

本节旨在给没有了解过数据结构的同学建立一个对树结构的初步了解。如果你对树和树的遍历已经比较了解，可以跳过这一节的内容。

试想，如果链表的每一个节点后面都有可能分岔出多条路，会变成什么样子？

链表分岔之后的形态，我们称之为“树”。具体而言，树是由n个节点，n-1条边连接起来的数据结构。特别地，链表所形成的一条链的结构也是树的一种特殊形态。

在上图中，树之间的边是有指向关系的，这种树被称为“有序树”。最左边的节点有指向其他节点的边，但是没有从其他节点指过来的边，这个节点被称为树的根或根节点。相应的，树最右边只有被指向的边，而没有指向其他节点边的节点被称作叶子或叶子节点。被一条边连起来的两个节点，边起点的节点被称作父节点，边指向的节点被称作子节点。以任意一个节点开始，沿着边的指向能达到的所有节点称作以该节点为根的子树。定义根节点的深度为1，则根节点的子节点深度为2，其他节点的深度可以依此类推。

链表可以轻易地使用循环或递归访问到每一个节点。按照某种顺序依次访问树的每个节点，称为为树的遍历。实际上，对递归访问链表的函数稍作改动，即可对树进行遍历。遍历链表时，每个节点对其唯一的后继节点调用递归函数；遍历树时，需要对多个子节点依次调用。例如：

// 递归输出链表的每一个节点:
void traverse(Node *node) {
    cout << node->value << endl;
    if (node->next != NULL)  
        traverse(node->next);  // 只调用一次
}

// 递归输出树的每一个节点:
void traverse(Node *node) {
    cout << node->value << endl;
    for (each pointer p to node’s children)
        traverse(p);  // 有几个子节点，调用几次
}

对图中的树调用traverse(root)函数，则会按照1->2->5->7->8->3->4->6的顺序遍历整棵树。

以上信息已经足够你完成本周的题目，如果你想了解更多关于树的更多信息，可以查阅这里。

2 题目要求

本次练习要求实现一个分叉链表树，实现插入、删除和输出功能。树上每个节点存储一个数字（int）。

为了简化问题，你可以假定树上的节点的数字不会重复。

题目要求程序读入一系列命令，按照命令构造树或输出树内容。命令的格式如下：

• insert_at_root <x>：在树根插入数字x，如果原来树是空的，新插入的节点即为树的唯一节点，否则，原来的根变成新根的子节点；
• insert_after <x> <y>：寻找树中第一次出现数字x的位置，如果x存在，在后面添加一个新的分支插入y，此时刚刚插入的y应该是叶子节点。
• delete <x>：寻找树中出现数字x的位置，如果存在并且该节点是叶子节点，将其删除；
• print <n>：递归输出树上深度不超过n的数字。以“先序遍历”的顺序，即图中绘制的顺序输出：从根开始输出，同一个节点的子节点，先插入的应该排在前面。特别地，如果给定n == -1，输出整棵树。

3 实现要求

这道题目要求实现以下结构体和函数：

• struct TNode;：树节点类，存储数字和指向下一个节点的（多个）指针；
• void insert_at_root(int x);：按照上面命令描述实现；

• void print(TNode *node, int n);：：按照上面命令描述，用递归实现。

如果你有能力将树实现成一个类，请实现以下结构体和函数：

• class Tree;：树类；
• class TNode;：树节点类，存储数字和指向下一个节点的指针；
• void Tree::insert_at_root(int x);：按照上面命令描述实现；
• void Tree::insert_after(int x, int y);：按照上面命令描述实现，请用递归实现；
• void Tree::delete_node(int x);按照上面命令描述实现，请用递归实现；
• void Tree::print(int n);：按照上面命令描述实现，请用递归实现。

注意，由于每个节点的子节点数目不定，你可以把上一题实现的链表稍作修改，以维护可变数量的子节点指针。如果在每个节点内嵌入一个链表对你实现起来有困难，你也可以假设每个节点的子节点的数目不会超过10，用数组维护；或使用STL中的vector类维护。

4 样例输入输出

输入：

insert_at_root 1
insert_at_root 2
insert_after 2 3
insert_after 2 4 
insert_after 1 6
print -1
delete 6
delete 1
print -1

输出：

2 1 6 3 4
2 3 4

题目 3 - 搜索引擎补全：字典树 （附加题，不算分）

1 题目要求

相信大家都使用过搜索引擎。以下图中某不存在的搜索引擎为例，当用户输入若干个字之后，搜索框下面会快速提示若干备选搜索词。实现这一功能，我们可以在上周练习题第一题的基础上稍作改动，把用户已经键入的字符串与词典中的字符串的前缀进行匹配。然而由于词典过大，这种逐一匹配的方法效率令人发指。

字典树（Trie）是一种可以用来加速这一检索过程的数据结构。以由26个字母组成的英文单词为例，字典树上的每一个节点都存储一个字母，并最多有26个子节点。从根节点沿着边向下走，途径的字母就组成了单词或者单词的前缀。为了标识从根节点走到某个节点途径的字母是不是组成了单词，每个节点额外存储一个单词标记，如下图所示。

字典树的基本操作包括插入、删除、检索指定前缀的所有单词等等。这里，我们举例说明这三种操作的实现思路。

插入：以插入单词tar为例。以根节点为起点，首先判断根节点下是否有节点t？由于节点t存在，接下来我们移动到t节点继续插入后缀ar。由于t节点下没有a，需要动态创建a节点作为t的子节点。创建完成后，继续移动到a节点插入r节点。当移动至r节点后，待插入后缀为空，此时标记r节点的is_word属性为true即可。

删除：以删除单词tea为例，只需从根节点沿着t-e-a的边找到对应tea的节点，将其is_word标记改为false即可。

检索以给定前缀开头的所有单词：完成这一操作的方法是先沿着前缀的单词走（如果走到某个位置，没有以下一个字母标记的字节点，则说明词典中没有以该前缀开头的单词）；走完前缀之后，递归遍历当前节点的子树，遇到有单词标记的节点时，输出根节点到当前节点的路径上的字母，即为一个单词。

这道题目要求大家实现一个支持插入单词、删除单词、给定前缀查找单词的字典树。

2 实现要求

请实现以下类和函数：

• class Trie;：字典树类；
• class TrieNode;：字典树的节点类；
• void Trie::insert(char *word);：插入单词；
• void Trie::delete(char *word);：删除单词；
• void Trie::retrieve(char *prefix);：检索并输出给定前缀的单词。如果你觉得由成员函数直接输出不够优美，也可以自行修改函数的定义和功能。

这道题是附加题，你可以自行设计测试用例测试自己的程序。