最近在网上看到一个有关算法的题目，于是就拿来做做。算法的思想是一方面，后面再详细说明。而在实现中也发现若干问题，说明对C语言的一些基本问题掌握得还不够牢固，特别是对实参传递形参的问题上还有一些问题。通过这个算法题一并复习一下。先来看看问题的具体描述：
将形如下面的一棵二元查找树：
10
/ \
6 14
/ \ / \
4 8 12 16
转换为双向链表：
4=6=8=10=13=14=16
一. 二元查找树
首先要明确的是什么是二元查找树？
二元查找树具有下列性质：若左子树不为空，则左子树上所有节点的值均小于它的根节点；
若右子树不空，则右子树上所有节点的值均大于它的根节点的值。
二. 具体实现与分析
知道了二元查找树的概念，我们就可以着眼于具体实现。
二院树单个节点的结构原题已经给出，也很好理解：
struct BSTreeNode
{
int value;
struct BSTreeNode *left;//left child
struct BSTreeNode *right;//right child
}; |
其具体实现应该分为两个步骤：
1）构建二元查找树
2）中序查找二院查找树的同时完成节点的调整
下面将分别予以介绍。
二元查找树的构建
因为是一组数据添加到树结构中，所以需要一个个添加进去。即该函数能够传一个树的根节点加一个待写到树结构中的数据。
void addBSTree(struct BSTreeNode **root, int val)
{
if(*root == NULL)
{
struct BSTreeNode *node;
node = malloc(sizeof(struct BSTreeNode));
node->left = NULL;
node->right = NULL;
node->value = val;
*root = node;
}
else
{
printf("val=%d", val);
if( val < (*root)->value)
{
addBSTree( &(*root)->left, val);
printf("左子树添加\n");
}
else if( val > (*root)->value)
{
addBSTree( &(*root)->right, val);
printf("右子树添加\n");
}
else
{
printf("repeat number occured !\n");
}
}
} |
这里第一个参数传递的是二元查找树的根节点的地址，第二个参数就是要插入到树结构中的节点的值。若根节点为空，就创建一个本地的指针，将它赋给根节点；若根节点不为空，则将带插入节点的值与根节点的值比较，若前者大，则将根节点的右子树作为根节点递归调用这个函数，若后者大，则将根节点的左子树作为根节点递归调用该函数，若出现相同的值，则证明这列数不能构成二元查找树。
二元查找树的查找
可以套用二叉树的遍历。二叉树的遍历有三种前序、中序和后序遍历。选择中序遍历可以保证二元查找树遍历的节点的值是按从小到大的顺序排列，而剩下的工作只需要调节指针的指向问题，这里给出中序遍历的写法。
void inOrderBSTree(struct BSTreeNode *root)
{
if ( root == NULL)
{
return ;
}
if (root->left != NULL)
{
inOrderBSTree(root->left);
}
convertoDlist(root);
if(root->right != NULL)
{
inOrderBSTree(root->right);
}
} |
复习一下，所谓中序遍历，即先访问左孩子节点、再访问当前节点、最后访问右孩子节点。
前序遍历即先访问当前节点，再访问左孩子结点，再访问右孩子节点。后序遍历 则是先访问左孩子结点、再访问右孩子结点、再访问当前节点。仔细的你应该注意到了convertoDlist函数，这个函数定义 了如何调整节点间的位置的具体策略。
调整节点位置
void convertoDlist( struct BSTreeNode *node)
{
node->left = index;//当前节点的左指针指向index
if (index == NULL)
{
head = node;
}
else
{
index->right = node;
}
// node->right = NULL;
index = node;
printf("当前节点：%d\n", node->value);
}
|
这里面的index 和 head 是两个全局变量，其数据类型是指向struct BSTreeNode结构的指针。head用来指向循环队列的头结点，index指向当前节点的前一个节点。你需要理解的几点：
1）由于这个函数是在遍历整个树，因而你的指针变更的操作不能破坏原来的树的结构，否则不能遍历成功。可以看见其逻辑是在当前节点和前一个节点间改变孩子指针的指向，而最后一个节点的右孩子指针是没有指定的， 笔者曾担心这会出现问题，所以加上蓝色部分的代码，结果程序无法遍历整个树。就是因为这句话破坏了原来树的结构。而且笔者的担心也是没必要的，因为最后一个节点的右孩子肯定是空的，这在树的建立的时候已经初始化好了。
2）通过这两个全局指针可以完成这个转换过程，也是必不可少的。
3）笔者曾经想过一种取巧的办法来完成这种转换，即你会发现这种转换实际上就是在原来树结构的基础上添加一些指针，但发现这其实还不如遍历来的方便。
main函数：
int main()
{
struct BSTreeNode *pRoot = NULL;
struct BSTreeNode *temp;
addBSTree(&pRoot, 10);
// printf("10 %d\n", pRoot->value);
addBSTree(&pRoot, 6);
// printf("6 %d\n", pRoot->value);
addBSTree(&pRoot, 14);
addBSTree(&pRoot, 4);
addBSTree(&pRoot, 8);
addBSTree(&pRoot, 12);
addBSTree(&pRoot, 16);
inOrderBSTree(pRoot);
temp = head;
while (temp !=NULL)
{
printf("temp=%d\n", temp->value);
// printf("tempright->%d\n", temp->right->value);
// printf("index%d\n",index->value);
//printf(("inde%d\n", index->right->value));
temp = temp->right;
}
return 0;
} |
最后的结果截图三. 遇到的问题
1.结构体指针初始化的方法：
struct me {
int val;
char c;
};
方法1：让结构体指针指向一个已经存在的结构体
struct me *p;
struct me q = {20,'c'};
p = &q;
方法2：动态分配空间
struct me *p;
p = malloc(sizeof(struct me) );
|
实验1：结构体指针初始化分配空间问题
代码段：
struct me
{
int val;
char c;
struct me *left;
struct me *right;
};
int main()
{
struct me *p = NULL;
//p= malloc((sizeof(struct me)));
printf("%d,%d,%d,%d,%d,%d\n", &p, p, &p->c, &p->left, &p->right, &p->val);
|
运行结果截图：
你会发现除了指针p的地址以外， 其他的地址的值都是很小的，而这是不正常的地址。因为操作系统会保留较小的这段地址，不会给用户使用。而且如果在此时，你去访问p中的元素，则程序会崩溃。其原因是： 如果一个结构体指针在初始化的时候被置为空，那么这个指针是没有被分配实际空间的。这个时候，可以通过上面提到的2种方法对结构体指针进行初始化。 如果把注释掉的代码释放出来，即给结构体指针分配堆空间，结果截图： 可以看见，这里就已经可以初步判断成功分配了空间。
2.实参与形参的传递
实验1：
代码段：
void Fun(char ca[])
{
printf("%d,%d,%d\n", &ca, &(ca[0]), &(ca[1]));
}
int main()
{
char a[] = {'a', 'b', 'c', 'd'};
printf("%d,%d,%d\n", &a, &(a[0]), &(a[1]));
Fun(a);
}
|
结果截图：
可以看到形参的地址发生变化，说明这里的传递是复制传递，即形参仅仅是把实参的值复制了过来，故形参在函数中如果发生了改变，不会影响实参的值。
其实，这里想要通过这个Fun函数来改变实参的值。这里有2种方式：
1）引用传递。即把实参的地址传给形参。在这里，笔者曾有一个错误的观点：基本类型的实参传它的地址就是引用传递，那么定义一个基本类型的指针，让这个指针指向某个基本类型对象的地址就可达到效果。在这个理论基础上，那么对于一个结构体来说，也应该是一样的。所以笔者在最开始编写程序的时候，仅仅把结构体指针作为函数形参的类型就可以了。
其实，这里笔者犯了一个逻辑上的问题。前面的理论基础是没有问题的，但是后面的就有问题了。即这里不应该把结构体中的各个组成元素（基本类型或其他数据结构）看做分开的独立，而应该把整个结构体当做一个基本类型处理。 如果要把一个结构体指针传递给形参实现通过函数修改，则应该让它指向一个同类型结构体的对象的地址。在使用结构体指针变量的时候，往往容易犯一个“低级”错误。即定义一个结构体指针变量后就直接对结构体指针变量所指向的结构体成员进行操作，从而产生一些莫名其妙的错误。我们必须要给结构体指针变量赋予一个有效的结构体变量地址，才能正常操作结构体指针变量。例如：
struct me
{
int val;
char c;
struct me *left;
struct me *right;
};
int main()
{
struct me *p;
p->val = 14;
p->c = 'a';
}
|
这个程序输出的值将是不可预知的，因为“在程序中只是定义了一个结构体指针变量，并没有给该结构体指针变量赋一个有效值，因此该结构体变量所指向的地址将不确定，从而不能得到预期结果”。
2）在函数中做完想想做的工作后，以返回值的形式返回一个指针赋给main函数中你定义的指针，这种方式不会有太多问题，就不展开来谈了。
四. 总结
通过本次的学习，发现这道算法题不算很难，其思想也比较常见，但是笔者仍搞了很长时间，就是在于实参和形参这块的传递问题上没有搞清楚，导致一些无法解释的现象，影响心情。
|
