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

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;
　　}
}