一、概述
本篇文章主要通过单项链表的有序排序、链式搜索二叉树来探索C的能力即“C能够取得现存对象的地址”,与指针的指针通过间接操作符“*”改变指针所指向的指针的能力如出一辙。因此在读本篇文章之前需要基础的指针、链表、二叉树知识，当然接下来也会简单介绍指针的指针。
指针作为C这门高级语言的重要组成部分，因其操作内存的高风险与高效率引得众人心向往之，为此该篇文章着重突出“改变地址指向的内容”以解决复杂的数据结构问题。
二、指针的指针
首先我们声明一个整型变量：
int a=10;
对于以下表达式我们是否能清晰的明白含义：
*&a=20;
而a最终的结果是10还是20？
以上的表达式首先看左值*&a的含义，根据优先级先对a取地址，在通过间接操作符指向地址的内容，即左值是变量a本身，最后将右值赋值给左值a，结果与以下表达式一样：
a=20;
因此a最终结果为20。
倘若我们再声明一个指针变量指向整型变量a:
int a=10;
int* b;
b=&a;
或者再次声明一个变量：
int**p;
p=&b;
那么*b=20或者**p=20都可以达到a=20的目的。
由于举例颇为简单，只是介绍指针的指针的用法，并不能感受“C能够取得现存对象的地址”这个强大能力的魅力，为此接下来从复杂问题里探索这个能力的奥秘。
三、单项链表
内存中存在着多个相同的结构类型且相关联的数据，构成一个集合。把每个独立的结构数据称之为节点，每个节点又包含一个指向下一个节点的指针，以及其他必要的数据。如图1所示，我们声明一个结构类型如下：
typedef struct TABLENODE {
int value;
struct TABLENODE* next;
}TableNode;
其中，整形变量value是节点的内容，next指向下一个节点。
如图1所示，当查找value值为11的节点，需要通过根节点找到第一个节点，再根据第一个节点的next指针寻找到第二个节点，依次并寻找到11这个节点。要说明的是根节点是指向第一个节点，并不不包含其他数据。另外我们图上有序的逻辑排列方便于直观探讨，而在实际物理内存中，不同节点占有的内存并不是连续的。
简单介绍完单项链表的含义，于是，可以引出如下思考：
如何将图1中的value值为9的节点删除，且不影响链表的完整性？
分析：
根据单项链表的不可逆性，从根节点依次查找节点的顺序是唯一的，通过比较当前节点的值与9的大小，如果不相等，则继续查找下一个节点，这也是循环判断的条件。
重要的是当查找到值为9这个当前节点时，接下来要进行的操作是提取当前节点指向的下一个节点11，并且要满足当前节点的前一个节点7的next指针指向11这个节点，最后删除9这个节点。
因此需要保存当前指针的前一个节点的指针。
步骤如下：
第一步：如图3.2，查找第一个节点时，当前指针current指向第一个value值为3的节点，即current->value=3，与我们要删除的9是不等的，因此在current指针继续指向下一个节点之前，将current保存到previous。
第二步：如图3.3，查找第二个节点时，当前指针current指向第2个value值为7的节点，即current->value=7，与我们要删除的9是不等的，因此在current指针继续指向下一个节点之前，将current保存到previous。
第三步：如图3.4，查找第3个节点时，当前指针current指向第3个value值为9的节点，即current->value=9，发现与我们要删除的9是相等的，此时只需要将previous节点的next指针指向current节点指向的下一个节点。得到图3.5所示。
第一次尝试Delete函数如下：
void Delete(TableNode* node,int value)
{
TableNode*current;
TableNode*previous;
previous=NULL;
current= node;
while((current!=NULL)&&(current->value!=value))
{
previous=current;
current=current->Next;
}
previous->Next=current->Next;
free(current);//销毁内存
}
第一次尝试删除函数存在如下问题：
1.传递的形参为根节点，如果需要删除第一个节点，就需要改变根节点的指向，由于形参传递不能改变形参本身的值，所以以上代码未考虑到这种情况。针对这种情况，我们只需要根据“函数的形参为指针时，可以改变指针指向的内容”这一特点，传递参数由根指针转换为根指针的地址。
2.传递的根节点有可能是空的，会导致其他问题。
对以上代码做如下改进：
void Delete(TableNode** node,int value)
{
assert(node!=NULL);
TableNode*current;
TableNode*previous;
previous=NULL;
current= *node;
while((current!=NULL)&&(current->value!=value))
{
previous=current;
current=current->Next;
}
assert(current!=NULL);
if(previous==NULL)
{
*node=current->Next;
}
else
{
previous->Next=current->Next;
}
free(current);
}
第二次尝试是可以达到正常解决问题的目的，但这并不是这篇文章的主旨，也未突出“指针的指针通过间接操作符*改变指针指向的指针”这一思想。
我们将根指针的地址即二维指针作为形参传递到函数，用一个一维指针current指向当前节点。当第一个节点不是删除对象时，我们只需使用二维指针保留current->next的地址，这个时候二维指针的意义变为指向当前节点的next指针。作为循环条件，在下次循环之前，重新将二维指针指向current，这样当前节点current指针自动前往下一个节，作为循环的条件进行判断。
因此我们只需要“指向当前节点的指针”以及“指向当前节点的next指针的指针”。
步骤如下：
第一步：如图3.6，p为根节点的地址，此时*p指向第一个value为3的节点，与current等价。
第二步：如图3.7，可以注意到p指向的是第一个节点的next指针位置，而不是第一个节点，这个至关重要。此时在下次循环之前p指向的内容保留到current指针，自动使得current指向value为7的节点。
第三步：如图3.8，p指向的是第二个节点的next指针位置。此时在下次循环之前p指向的内容保留到current指针，自动使得current指向value为9的节点。
第四步：如图3.9,判断当前的节点是需要删除的节点。将p指向当前节点current的next指针。
代码如下：
void Delete(TableNode** node,int value)
{
assert(node!=NULL);
TableNode*current;
TableNode**p=node;
current= *p;
while((current!=NULL)&&(current->value!=value))
{
p=¤t->Next;
current=*p;
}
assert(current!=NULL);
*p=current->next;
}
第三次尝试可以看到，并没有采取第二次尝试中的保留前一个节点的方式，而是抓住“指针的指针通过间接操作符*改变指针指向的指针”这一思想解决问题。而这类思想在链式搜索二叉树中也有所使用。
事情并没有结束，我们很快知道插入一个节点也可以这么操作，可以参照删除的思想，只贴上代码：
void insert(TableNode** node,int value)
{
assert(node!=NULL);
TableNode*current;
TableNode**p=node;
TableNode*insertnode;
current= *p;
while((current!=NULL)&&(current->value<value))
{
p=¤t->Next;
current=*p;
}
//新增：
insertnode=(TableNode*)malloc(sizeof(TableNode));
assert(insertnode!=NULL);
insertnode->value=value;
insertnode->next=current;
*p=insertnode;
}
四、链式搜索二叉树
二叉树的特点：当前节点的值要大于它左子树所有的节点值，并小于它右子树所有的节点值。
如上图4.1是一个二叉树，基于以上特点，我们可以采用链表的搜索方式查找二叉树，并将“指针的指针通过间接操作符*改变指针指向的指针”这一思想运用到其中。
例：在上图二叉树插入11.
结果如图4.2所示：
节点结构为：
typedef struct TREENODE {
int value;
struct TABLENODE*left;
struct TABLENODE*right;
}TreeNode;
代码如下：
void insert(TreeNode** node,int value)
{
assert(node!=NULL);//
TreeNode*current;//当前节点
TreeNode*insertnode;//要插入的节点
current= *node;
while((current!=NULL))
{
if(current->value>value)
{
node=¤t->left;
current=*node;
}
else
{
if(current->value<value)
{
node=¤tt->right;
current=*node;
}
}
}
//新增：
insertnode=(TreeNode*)malloc(sizeof(TreeNode));
insertnode->left=NULL;
insertnode->right=NULL;
insertnode->value=value;
*node=insertnode;
}
参考书籍：《C和指针》《C专家编程》《STL源码剖析》
