2013.9.2 校招准备 tips + 各种数据结构
下面以最小堆为例说明堆的输出：
图1为一个最小堆，当最小节点根节点13输出后，将最后一个节点97作为根节点，移到顶端，如图2. 然后要对堆进行调整。比较此完全树的根节点与其两个子节点大小，因为27 < 38 < 97，所以27是三个节点里最小的，将节点27与根节点97交换。此时以97替代27而产生的右子树为一个新的堆，再以97为根节点，对此最小堆进行调整，同理，知道要将97与49交换，得到图3的完全树。此时以97代替49为根节点的右子树为一个新堆，再对此堆做同样的操作，因为此完全树已经是最小堆，所以可以停止操作，堆的调整完毕。此时再将根节点，对的最小值输出，并进行同样的调整，可以得到如图4的新堆。这个过程被称为“筛选”。
同样以最小堆说明堆的初始化：
从一个无序序列初始化为一个堆的过程就是一个反复“筛选”的过程。由完全二叉树的性质可以知，一个有n个节点的完全二叉树的最后一个非叶节点是节点[n/2]，堆的初始化过程就从这个[n/2]节点开始。上图为如下无序数组的初始化：
{49,38,65,97,76,13,27,50}
首先，未处理的数组对应的堆为图1模样。从第四个节点开始（[8/2]=4），因为50 < 97，故要交换两节点，交换后还要继续对其新的左子树进行类似输出后那样的筛选。易见其左子树只有节点97，已经为最佳情况，故可以继续堆的初始化，如图2。再考虑第三个节点，因为13 < 27 < 65，即节点13为当前的最小节点，故与节点65交换，并对新的左子树进行筛选，其也为最佳情况，故可继续堆的初始化，结果如图3。然后考虑第二个节点，因为38 < 50 < 76，故已经为最优情况，不用调整。最后再考虑第一个节点，根节点。因为 13 < 38 < 49，故需要将根节点49与其右孩子节点13交换，交换后还要继续对其新的右子树进行类似输出后那样的筛选，可见右子树还需要调整，因为 27 < 49 < 65,故将节点49与节点27交换。此时已经处理完了根节点，初始化结束。最终结果如图5.
本文参考了严蔚敏的《数据结构》
题目：如何判断单项链表有死循环？
答案：定义两个指针p、q，然后让p、q同时从链表头向后查找，注意他们移动的步幅是不同的分别为a
、b，例如p指针每次执行一次【p = p->next;】q每次执行两次【q = q->next;】，如果q先到链尾【if(q->next == NULL)】则没有死循环（这里假设q比p的移动速度要快），如果p、q在此之前相遇了则有死环。
问题1. 一个单向链表，请设计算法判断该链表中有没有环？
思路1：声明一个指向链首的指针和一个足够大的int数组(或hash表，用于保存地址)，逐个节点地遍历链表；遍历过程中，先判断该节点的地址是否已经在数组中存在了，如果不存在，则将该地址加入数组并让指针指向下一个节点；如果存在，则证明链表中有环。这种方法需要用数组来保存地址，并反复遍历该数组，效率很低，伪代码如下：
1
Node* ptr = head;//链首
2int i[100000];
3int len=0;
4while(ptr!= null)
5
{
6
int address= ptr;
7 if(address alreadyin i)
8
{
9 print'链表中存在环';
10 exit();
11
}
12 i[len]= ptr;
13 ptr= ptr->next;
14
}
15print'链表中没有环'
16exit();
思路2：如果链表中有环的话，则整个链表呈6、9、或0字形；可以声明两个指向链首的指针，其中一个指针每次移动一个节点，另一个指针每次移动两个节点，如果两个指针指向同一个节点，则表示链表中存在环(类似与小学数学中的追击问题=_=)，否则不存在环。伪代码如下：
1Node* ptr1 = head;
2Node* ptr2 = head;
3if(ptr1!= null)
4 ptr1= ptr1->next;
5if(ptr1== ptr2)//考虑链表中只有一个元素，且构成一个环的情况
6{
7 print'链表中存在环';
8 exit();
9}
10ptr2= ptr2->next->next;//或者ptr1->next;
11while(true)
12{
13 if(ptr1==null|| ptr2==null)
14 {
15 print'链表中没有环';
16 break;
17 }
18 if(ptr1==ptr2)
19 {
20 print'链表中存在环';
21 break;
22 }
23 ptr1= ptr1->next;
24 if(ptr2->next!= null)
25 ptr2= ptr2->next->next;
26}
27exit();
支持思路二 更加优化~
