编写算法与数据结构中存在的小技巧和一些陷阱

1 链表中前驱的重要性。

      在链表中，删除一个结点而不导致链表断裂，一个必要条件就是这个结点的前驱和后继能够相连。

      然而不是每种数据结构上都保存有前驱指针。

      在这种情况下我们可以使用的一个小技巧就是在起点之前再增加一个结点（比如有些链表中的head）。然后把head与head->next一起推进，当head->next正好到达指定结点时，我们想要找的前驱也就找到了。

 

2 链表中临时指针的重要性。

 

      (1) 在很多时候，数据结构中都有一个关键的起点指针，比如链表中的first（不含有头结点）、head（含有头结点）、二叉树中的root。我们的遍历操作都要从这些起点指针开始动手，这就要求我们必须要慎重对待。很多时候我们可以使用一些临时指针来作为开头，避免修改关键性数据。

      (2) 当我们的遍历达到一定程度的时候，我们必须要保存一个结点的前驱，或者后继的时候，也就有必要了。

3 链表中for循环、while循环中止隐藏的陷阱。

/*注意for循环中止的时候，p指向第k个结点已经成立了。*/
   for (int i=1; i<k; i++) p=p->link;
 for (int i=1; i<k-1; i++) q=q->link; /*循环结束时，q指向谁？指向要删除的结点的前驱。有趣的是，如果要删除头结点，则这个语句不会执行*/

 

4 注意删除指针时的错误。

 

delete [] elements;//释放整个elements数组 
delete  elements; //只是释放element数组的头一个元素