题目详细要求、参考资料及更新发布于： http://lamda.nju.edu.cn/xiez/bop19/week_2/ 第二周 链表与指针 题目详细要求、参考资料及更新发布于： http://lamda.nju.edu.cn/xiez/bop19/week_2/

Presentation on theme: "题目详细要求、参考资料及更新发布于： http://lamda.nju.edu.cn/xiez/bop19/week_2/ 第二周 链表与指针 题目详细要求、参考资料及更新发布于： http://lamda.nju.edu.cn/xiez/bop19/week_2/"— Presentation transcript:

1 题目详细要求、参考资料及更新发布于： http://lamda.nju.edu.cn/xiez/bop19/week_2/
第二周 链表与指针 题目详细要求、参考资料及更新发布于：

2 如何方便地测试程序 反复运行程序的时候一遍一遍粘贴样例输入很麻烦，怎么办？ 将输入文件存成in.txt 避免粘贴的方法：
命令行里执行可执行程序（例如可执行程序命名为main）时， 用 main < in.txt ，这样 in.txt 里的内容会当作标准输入，输入给main 如果你用visual studio，可以在开头加一句freopen(“in.txt”, “r”, stdin); 记得在提交到系统的时候删掉这一行。 如果程序执行正确，应该退出掉。作业最终提交到系统的版本不要用 while(true)或getchar()等方式将程序卡在最后，否则助教评测起来会很 麻烦。前四周请只提交cpp文件到系统。

3 如何初始化字符数组 定义字符数组时最好将其全部初始化成0。 方法1: char a[100] = “”; 方法2: char b[100]={‘\0‘}; //这里是单引号 方法3: 在需要初始化时（程序一开始）调用： memset(a, 0, sizeof a); memset函数包含在string.h中。

4 我们如何评测程序？ 每道题我们有5组数据； 我们会使用脚本编译你的程序，使用输入文件作为输入， 记录你的输出与正确的输出进行比较。
因此：请注意输出的大小写正确，不要输出多余的提示， 严格按照样例输入输出的格式输出。结尾请输出一个换行。 g++ -o main $1 ./main < in1.txt > tmp1.txt diff out1.txt tmp1.txt >/dev/null && printf "correct" || printf "wrong"

5 练习一

6 链表回顾 本次练习要求实现一个单链表，实现插入、删除和正逆序输出功能。链表每个节点存储 一个数字（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，输出整个链表。 背景？敏感词过滤？

7 样例输入输出 Input: 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 Output: 2 5 55 55 5 2

8 链表回顾 本次题目要求实现以下函数（每个函数功能请严格按照要求完成，不要修 改）： 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);：请用递归实现。 背景？敏感词过滤？

9 链表回顾 如果你有能力将链表实现成一个类（class），请实现以下结构体和函数（每个函数功能请严格按 照要求完成，不要修改）：
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);：请用递归实现。因为这个函数的参数不适合进行递归，你 可能需要另外实现一个成员函数来实际完成递归，然后用reverse_print()调用那个函数。

10 练习二

11 链表 value 1 next value 2 next value 3 next value 4 next NULL 背景？敏感词过滤？

12 树 value 1 next value 2 next value 3 next value 4 next NULL value 5
6 next NULL value 7 next NULL 背景？敏感词过滤？ value 8 next value 9 next NULL value 10 next NULL

13 树 深度1 深度2 深度3 深度4 根 value 1 next value 2 next value 3 next value 4
NULL value 5 next value 6 next NULL value 7 next NULL 根 背景？敏感词过滤？ value 8 next value 9 next NULL value 10 next NULL

14 如何遍历一棵树 递归输出链表的每一个节点: 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); // 有几个子节点，调用几次 }

15 树 调用traverse(root), 前面的函数会输出树的先序遍历：
1 -> 2 -> 3 -> 4 -> 7 -> 5 -> 6 -> 8 -> 9 -> 10 value 1 next value 2 next value 3 next value 4 next NULL value 5 next value 6 next NULL value 7 next NULL 背景？敏感词过滤？ value 8 next value 9 next NULL value 10 next NULL

16 链表分叉变成树 本次练习要求实现一个树，实现插入、删除和输出功能。树上每个节点存储一个数字（int）。 为了简化问题，树上的节点的数字不会重复。 题目要求程序读入一系列命令，按照命令构造树或输出树内容。命令的格式如下： insert_at_root <x>：在树根插入数字x，如果原来树是空的，新插入的节点即为树的 唯一节点，否则，原来的根变成新根的子节点； insert_after <x> <y>：寻找树中出现数字x的位置，如果x存在，在后面添加一个新 的分支插入y，此时刚刚插入的y应该是叶子节点。 delete <x>：寻找树中出现数字x的位置，如果存在并且该节点是叶子节点，将其删除； print <n>：递归输出树上深度不超过n的数字。以“先序遍历”的顺序输出：从根开始 输出，同一个节点的子节点，先插入的应该排在前面。特别地，如果给定n == -1，输 出整棵树。 背景？敏感词过滤？

17 样例输入输出 Input: 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 Output: 2 3 4

18 链表回顾 这道题目要求实现以下结构体和函数： struct TNode;：树节点类，存储数字和指向下一个节点的 （多个）指针； void insert_at_root(int x); void insert_after(TNode *node, int x, int y);请用递归实现。 void delete_node(TNode *node, int x);请用递归实现。 void print(TNode *node, int n);：请用递归实现。 背景？敏感词过滤？

19 链表回顾 如果你会用类，请实现以下类和函数： 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);：请用递归实现。因为这个函数的参数不适合进行 递归，你可能需要另外实现一个成员函数来实际完成递归，然后用print() 调用那个函数。 背景？敏感词过滤？