1. 程序的模块化思想

将一些经常使用的功能模块化，从而达到一次编写，多次调用的效果，也方便调试和修改。
此时，全局变量是有害的，因为在一定程度上干扰了模块化的实现。

2. ADT

概念

ADT（抽象数据类型），指的是一种数据结构和在他之上的操作。
比如：

• 表，及其对表的操作。
• 集合，及对集合的操作。

如果数据结构相同，但是操作不同（种类或数量不同），则称作是不同的ADT。

进一步的抽象

不仅仅使用了程序的模块化思想，更是进一步的抽象，因为其规定了输入输出，而对其内部的实现没做要求，故而实现了分层，进一步加强了程序的可维护性。

3. 表

表是一种抽象的概念，其描述了数据和数据之间的关系，并定义了在其上的一些操作，之后用具体的数据结构实现。
操作可以定义：

• PrintList：打印这个表
• Insert：在表中插入某个数

• Delete：在表中删除某个数

  如果用数组实现

  插入和删除需要线性时间，FindKth需要常数时间。

  如果用链表实现

  插入和删除需要常数时间，FindKth需要线性时间。

  4. 关于链表

  细节的东西有点多，书上也有，我解释一下几个问题，写一下自己的感悟吧。

  为什么要采用 dummy node（哑结点）？

  从P33中，我们可以发现，删除和插入都需要有前驱节点并改变前驱节点中的指针，所以 dummy node 的使用可以使得链表中的所有节点都有前驱节点，进而维持了一致性，排除了一些特殊情况（特殊判断首节点等），便于编程。
  也就是说：
  对于插入和删除来说，如果使用哑元节点，则维持了所有节点的“前驱节点”一致性，便于编程。

  判断特殊情况？

• 对于链表及其操作，对于一些特殊的情况，循环无法批量解决的问题，需要提前判断（比如没有使用哑结点的插入到首节点之前）。

• 更经常的，是对参数合法性的判断，因为每个函数都有其处理数据的域，我们将不满足这个域的情况排除。

二者本质是一样的，需要大家理解。

结论 ：

其实，循环就是从问题中抽取重复的单元（或者向上文所述，通过一些微小的改变来使特殊情况变成“重复的单元”）从而批量的解决问题，递归是从问题中抽取子问题，进而递归的求解。这就是循环和递归的更本质的理解。
链表.cpp，这是我写的可以执行的代码，操作不全，也没有注释，有些地方跟书上不太一样，但是可以参考。

5. free和malloc 和指针一些语法问题

free(node *p) 指的是释放p所指向的内存空间，其具体操作是：

• p所存放的地址不变。
• 该地址处的数据已经无定义了（等待被回收），所以对于该处数据的访问是不合法、危险的。

在使用指针时，如果调用了 p->XX ,一定要先判断指针是否为NULL。

6. 链表的拓展

双向链表，循环链表，双向循环链表等。

• 双向链表:简化了删除操作（因为不需要 findPrevious）

7. 多重表

可以用于关系数据库的存储过程。

8. P62 3.3 a

逻辑不是很复杂，这里要注意的是，我们需要什么指针，指针的更改时序。

9. P62 3.4

这里需要注意的是：每个链表中的数字都是不重复的，因为交操作本身就是就集合而言。