<转>求二叉树中节点的最大距离

问题：

如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。

实际上就是求树的直径。若采用“动态规划方法”思想，会将该问题分解成“具有最大距离两点间的路径是否经过根节点”两个子问题，然后再对这两个子问题求解判断。实际上，不必这么麻烦。距离最远的两点必然在以某个节点A为根的子树上，它们间的路径必然经过该子树的根节点A。因而，以任意一个节点B为根的子树，计算出经过该子树根节点B的最大距离，则所有最大距离的最大值就是所要求的二叉树的最大距离，即“树的直径”。而经过树的根节点的最大距离为：左子树的高度+右子树的高度+2（假设空节点的高度为-1），因而，原问题等同于“计算每个节点的左子树和右子树的高度和，取最大值”。

<转>getchar()详解

　　函数名: getchar
　　功 能: 从stdin流中读字符
　　用 法: int getchar(void);

　　注解：
　　getchar有一个int型的返回值.当程序调用getchar时.程序就等着用户按键.用户输入的字符被存放在键盘缓冲区中.直到用户按回车为止(回车字符也放在缓冲区中).当用户键入回车之后,getchar才开始从stdin流中每次读入一个字符.getchar函数的返回值是用户输入的第一个字符的ASCII码,如出错返回-1,且将用户输入的字符回显到屏幕.如用户在按回车之前输入了不止一个字符,其他字符会保留在键盘缓存区中,等待后续getchar调用读取.也就是说,后续的getchar调用不会等待用户按键,而直接读取缓冲区中的字符,直到缓冲区中的字符读完为后,才等待用户按键.

　　getch与getchar基本功能相同,差别是getch直接从键盘获取键值,不等待用户按回车,只要用户按一个键,getch就立刻返回, getch返回值是用户输入的ASCII码,出错返回-1.输入的字符不会回显在屏幕上.getch函数常用于程序调试中,在调试时,在关键位置显示有关的结果以待查看,然后用getch函数暂停程序运行,当按任意键后程序继续运行.

　　程序例:
　　#include <stdio.h>
　　int main(void)
　　{
　　　　int c;
　　　　/* Note that getchar reads from stdin and
　　　　is line buffered; this means it will
　　　　not return until you press ENTER. */
　　　　while ((c = getchar()) != '\n')
　　　　printf("%c", c);
　　　　return 0;
　　}

　　注：可以利用getchar()函数让程序调试运行结束后等待编程者按下键盘才返回编辑界面，用法：在主函数结尾，return 0；之前加上getchar()；即可

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/oopDesigner/archive/2008/11/20/3341799.aspx

<转>找到单链表环路入口

既然能够判断出是否是有环路，那改如何找到这个环路的入口呢？ 思路类似找单链表的交点。

解法如下： 当p2按照每次2步，p1每次一步的方式走，发现p2和p1重合，确定了单向链表有环路了

接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当p1和p2再次相遇的时候，就是环路的入口了。

这点可以证明的：

在p2和p1第一次相遇的时候，假定p1走了n步骤，环路的入口是在p步的时候经过的，那么有

p1走的路径： p+c ＝ n；         c为p1和p2相交点，距离环路入口的距离

p2走的路径： p+c+k*L = 2*n；   L为环路的周长，k是整数

显然，如果从p+c点开始，p1再走n步骤的话，还可以回到p+c这个点

同时p2从头开始走的话，经过n步，也会达到p+c这点

显然在这个步骤当中p1和p2只有前p步骤走的路径不同，所以当p1和p2再次重合的时候，必然是在链表的环路入口点上。

解决此问题可用于判断两个带环链表是否相交。方法是判断其中一个链表的环路入口是否出现在另一个链表中。

<转>最大子序列的线性时间算法

Int MaxSubsequenceSum(const int A[], int N)
{
       int ThisSum, MaxSum, j;
       ThisSum = MaxSum = 0;
       For(j=0; j < N; j++)
       {
              ThisSum += A[j];
              If (ThisSum > MaxSum)
                     MaxSum = ThisSum;
              Else if(ThisSum < 0)
                     ThisSum = 0;
       }
       return MaxSum;
}

对于这个算法的分析(逻辑):

从左相右相加，若结果不断的增加，那么ThisSum将同MaxSum一起增加，如果遇到负数，那么也加到ThisSum上去，但是此时ThisSum < MaxSum，那么就不加。看ThisSum是不是会回升，若一直不回升，不断或是波浪型的下降，那么当它降到0时，说明前一段与后一段是可以抛弃的。正如有 7 ， -8 一样，我们可以不要这两个数，但是我们知道MaxSum依然保存着前一段的最大值，（这就是这个算法中的厉害，我认为）。然后，ThisSum将从后面开始将这个子段进行分析，若有比当前MaxSum大的子段，然后替换（此时可以彻底抛弃前一段）。这样一趟扫描结果也就出来了。

在序列中所有数都是负数的情况下不能用该算法，结果会返回0。考虑到这种情况，在应用此算法前只需增加一次遍历判断值是否都为负，是则返回序列中最大值，否则应用上面的算法，复杂度仍然是o(n)。

<转>５分钟搞定内存字节对齐

写出一个struct,然后sizeof,你会不会经常对结果感到奇怪?sizeof的结果往往都比你声明的变量总长度要大,这是怎么回事呢?讲讲字节对齐吧.
/******************************分割线
如果体系结构是不对齐的，A中的成员将会一个挨一个存储，从而sizeof(a)为11。显然对齐更浪费了空间。那么为什么要使用对齐呢？
体系结构的对齐和不对齐，是在时间和空间上的一个权衡。对齐节省了时间。假设一个体系结构的字长为w，那么它同时就假设了在这种体系结构上对宽度为w的数据的处理最频繁也是最重要的。它的设计也是从优先提高对w位数据操作的效率来考虑的。比如说读写时.............此处省略５０万字
***********************************************************/
上面是你随便　google一下,人家就可以跟你解释的,一大堆的道理,我们没怎么多时间,讨论为何要对齐.直入主题,怎么判断内存对齐规则,sizeof的结果怎么来的,请牢记以下3条原则:(在没有#pragma pack宏的情况下，务必看完最后一行)
１:数据成员对齐规则：结构(struct)(或联合(union))的数据成员，第一个数据成员放在offset为0的地方，以后每个数据成员存储的起始位置要从该成员大小或者成员的子成员大小（只要该成员有子成员，比如说是数组，结构体等）的整数倍开始(比如int在３２位机为４字节,则要从４的整数倍地址开始存储。
２:结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部最大元素大小的整数倍地址开始存储.(struct a里存有struct b,b里有char,int ,double等元素,那b应该从8的整数倍开始存储.)
３:收尾工作:结构体的总大小,也就是sizeof的结果,.必须是其内部最大成员的整数倍.不足的要补齐.
等你看完此３条原则,２分钟已经过去,抓紧时间,实战３分钟:
typedef struct bb
{
 int id;             //[0]....[3]
 double weight;      //[8].....[15]　　　　　　原则１
 float height;      //[16]..[19],总长要为８的整数倍,补齐[20]...[23]　　　　　原则３
}BB;
typedef struct aa
{
 char name[2];     //[0],[1]
 int  id;         //[4]...[7]　　　　　　　　　　原则１
 double score;     //[8]....[15]　　　　
 short grade;    //[16],[17]　　　　　　　　
 BB b;             //[24]......[47]　　　　　　　　　　原则２
}AA;
int main()
{
  AA a;
  cout<<sizeof(a)<<" "<<sizeof(BB)<<endl;
  return 0;
}
结果是
48 24
ok,上面的全看明白了,内存对齐基本过关.
再讲讲#pragma pack().
在代码前加一句#pragma pack(1),你会很高兴的发现,上面的代码输出为
32 16
bb是4+8+4=16,aa是2+4+8+2+16=32;
这不是理想中的没有内存对齐的世界吗.没错,#pragma pack(1),告诉编译器,所有的对齐都按照1的整数倍对齐,换句话说就是没有对齐规则.
明白了不?
那#pragma pack(2)的结果又是多少呢?对不起,５分钟到了,自己去测试吧.
ps:Vc,Vs等编译器默认是#pragma pack(8)，所以测试我们的规则会正常；注意gcc默认是#pragma pack(4)，并且gcc只支持1,2,4对齐。套用三原则里计算的对齐值是不能大于#pragma pack指定的n值。

逗号运算符

　　C语言提供一种特殊的运算符——逗号运算符。用它将两个表达式连接起来。如：

　　3+5，6+8

称为逗号表达式，又称为“顺序求值运算符”。逗号表达式的一般形式为

　　　　　　　　 表达式1，表达式2

逗号表达式的求解过程是：先求解表达式1，再求解表达式2。整个逗号表达式的值是表达式2的值。例如，上面的逗号表达式“3+5，6+8”的值为14。又如，逗号表达式
　　a=3*5，a*4
对此表达式的求解，读者可能会有两种不同的理解：一种认为“3*5，a*4” 是一个逗号表达式，先求出此逗号表达式的值， 如果a的原值为3，则逗号表达式的值为12，将12赋给a， 因此最后a的值为12。另一种认为：“a=3*5”是一个赋值表达式”，“a*4”是另一个表达式，二者用逗号相连，构成一个逗号表达式。这两者哪一个对呢?赋值运算符的优先级别高于逗号运算符， 因此应先求解a=3*5(也就是把“a=3*5”作为一个表达式)。经计算和赋值后得到a的值为15，然后求解a*4，得60。整个逗号表达式的值为60。
　　一个逗号表达式又可以与另一个表达式组成一个新的逗号表达式，如(a=3*5，a*4)，a+5 先计算出a的值等于15，再进行a*4的运算得60(但a值未变，仍为15)，再进行a+5得20，即整个表达式的值为20。
　　逗号表达式的一般形式可以扩展为

　　　　表达式1，表达式2，表达式3……表达式n

它的值为表达式n的值。

　　逗号运算符是所有运算符中级别最低的。因此，下面两个表达式的作用是不同的:

　　① x=(a=3，6*3)
　　② x=a=3，6*a

　　第①个是一个赋值表达式，将一个逗号表达式的值赋给x，x的值等于18。第②个是逗号表达式，它包括一个赋值表达式和一个算术表达式，x的值为3。

　　其实，逗号表达式无非是把若干个表达式“串联”起来。在许多情况下，使用逗号表达式的目的只是想分别得到各个表达式的值，而并非一定需要得到和使用整个逗号表达式的值，逗号表达式最常用于循环语句(for语句)中．

　　请注意并不是任何地方出现的逗号都是作为逗号运算符。例如函数参数也是用逗号来间隔的。如

　　printf("%d，%d，%d"，a，b，c)；

　　上一行中的“a，b，c”并不是一个逗号表达式，它是printf函数的3个参数，参数间用逗号间隔。
如果改写为

　　printf("%d，%d，%d"，(a，b，c)，b，c)；

则“(a，b，c)”是一个逗号表达式，它的值等于c的值。括弧内的逗号不是参数间的分隔符而是逗号运算符。括弧中的内容是一个整体，作为printf函数的一个参数。
C语言表达能力强，其中一个重要方面就在于它的表达式类型丰富，运算符功能强，因而c使用灵活，适应性强

<转>不用临时变量交换两个数的值

当要交换两个数的值时，通常的做法是定义一个临时变量，然后再进行交换。那么能不能不用临时变量而交换两个数的值呢？可以的！C语言提供的异或运算就可以实现这样的操作。

异或运算符^也称XOR运算符，它的规则是若参加运算的两个二进位同号，则结果为0（假）；异号为1（真）。即0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0。

例：
#include

int main(int argc, char *argv[])
{
int a = 2, b = 6;

a = a ^ b;
b = b ^ a;
a = a ^ b;

printf("a = %d b = %d\n", a, b);

return 0;
}


结果如下：

a = 6 b = 2


分析：

前两个赋值语句：“a = a ^ b；”和“b = b ^ a；”相当于b = b ^ (a ^ b)，而b ^ a ^ b等于a ^ b ^ b。b ^ b的结果为0，因为同一个数与相向相^，结果必为0。因此b的值等于a ^ 0，即a，其值为2。

再执行第三个赋值语句：“a = a ^ b”。由于a的值等于(a ^ b)，b的值等于(b ^ a ^ b)，因此，相当于a = a ^ b ^ b ^ a ^ b，即a的值等于a ^ a ^ b ^ b ^ b，等于b。

2007.06.02

今天又发现另外两种方法，特补上。

方法一
void swap(int *p, int *q)
{
*p = *p + *q;
*q = *p - *q;
*p = *p - *q;
}


方法二

void swap(int *p, int *q)
{
*p = *p + *q - (*q = *p);
}


原理为算术运算符的结合顺序为自左至右。

strcmp实现

strcmp是比较两个字符串的大小,两个字符串相同时返回0,第一个字符串大于第二个字符串时返回一个正值,否则返回负值.
比较两个字符串的算法是:逐个比较两个串中对应的字符，字符大小按照ASCII码值确定，从左向右比较，如果遇到不同字符，所遇第一对不同字符的大小关系就确定了两个字符串的大小关系，如果未遇到不同字符而某个字符串首先结束，那么这个字符串是较小的，否则两个字符串相等。

int strcmp( const char *string1, const char *string2 )
{
　　int i;
　　do
　　{
　　　　i = (int)*string1 -(int)*string2;
　　}
　　while(*string1++ && *string2++ && (!i) );
　　return i;
}

递归求二叉树深度

int depth(b_tree p)
{
　　int dep1=0,dep2=0;
　　if(p==NULL)
　　{
　　　　return 0;
　　}
　　dep1=depth(p->lchild);
　　dep2=depth(p->rchild);

　　if(dep1>dep2)
　　　　return dep1+1;
　　else
　　　　return dep2+1;
}

递归创建二叉树

Tree *Create()
{
　　char ch;
　　cin>> ch;
　　Tree *root;

　　if( ch == NIL )
　　{
　　　　return NULL;
　　}
　　else
　　{
　　　　root = new Tree(ch);
　　　　root->left = Create();
　　　　root->right = Create();
　　　　return root;
　　}
}