遍历二叉树的非递归算法

typedef int TElemType;
typedef struct BiTNode
{
　　TElemType data;
　　struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

// 中序遍历的非递归算法
bool InOrderTraverse(BiTree T, bool (*Visit)(TElemType e))
{
　　if (NULL == T) return false;

　　Stack S; //辅助的栈
　　BiTree p = T;

　　InitStack(S);
　　while (p || !StackEmpty(S))
　　{
　　　　if (p)
　　　　{
　　　　　　Push(S, p);
　　　　　　p = p->lchild;
　　　　}
　　　　else
　　　　{
　　　　　　Pop(S, p);
　　　　　　if (!Visit(p->data))
　　　　　　{
　　　　　　　　DestroyStack(S);
　　　　　　　　return false;
　　　　　　}
　　　　　　p = p->rchild;
　　　　}
　　}
　　DestroyStack(S);
　　return true;
}

// 层次遍历的非递归算法
bool HierarchyTraverse(BiTree T, bool (*Visit)(TElemType e))
{
　　if (NULL == T) return false;

　　LinkQueue *Q; //辅助的队列
　　BiTree p = T;

　　InitQueue(Q);
　　Visit(p->data);
　　if (p->lchild) EnQueue(Q, p->lchild);
　　if (p->rchild) EnQueue(Q, p->rchild);
　　while (!QueueEmpty(Q))
　　{
　　　　DeQueue(Q, p);
　　　　Visit(p->data);
　　　　if (p->lchild) EnQueue(Q, p->lchild);
　　　　if (p->rchild) EnQueue(Q, p->rchild);
　　}
　　DestroyQueue(Q);
　　return true;
}

更多见：二叉树非递归遍历算法

微软算法题第5题

5.编写反转字符串的程序，要求优化速度、优化空间。

最简单的解法就是遍历字符串，第一个字符和最后一个交换，第二和倒数第二交换，依此类推次，即Reverse1函数。其中元素交换可以不用辅助变量，直接用异或实现，这种优化措施在嵌入式开发中经常使用，因此可修改为Reverse2函数。

void Reverse1(char *str)
{
　　int len = 0;
　　while ('\0' != str[len])
　　　　len++;

　　char temp;
　　for (int j = 0; j < len/2; j++)
　　{
　　　　temp = str[j];
　　　　str[j] = str[len-j-1];
　　　　str[len-j-1] = temp;
　　}
}

void Reverse2(char *str)
{
　　int len = 0;
　　while ('\0' != str[len])
　　　　len++;
　　for (int j = 0; j < len/2; j++)
　　{
　　　　str[j] ^= str[len-j-1];
　　　　str[len-j-1] ^= str[j];
　　　　str[j] ^= str[len-j-1];
　　}
}

void Reverse3(char *str)
{
　　char *s = str;
　　char *e = str;

　　while (*e++)
　　　　;
　　e -= 2;
　　while (s < e)
　　{
　　　　*s ^= *e;
　　　　*e ^= *s;
　　　　*s++ ^= *e--;
　　}
}

不过有人说微软的意思是 I love you 反转后是 you love I。那这就是下面的算法了。
首先将整个字符串反转，然后每个单词反转。这样简单，不过效率不高，还有优化的算法没？

void Reverse(char* pStart, char* pEnd)
{
　　while (pStart < pEnd)
　　{
　　　　*pStart ^= *pEnd;
　　　　*pEnd ^= *pStart;
　　　　*pStart++ ^= *pEnd--;
　　}
}

void ReverseString(char* str)
{
　　int length = 0;
　　while (str[length])
　　　　length++;
　　Reverse(str, str + length - 1);

　　char *p = str;
　　for (int i = 0; '\0' != *p; p++)
　　{
　　　　if ( ' ' != *p )
　　　　　　i++;
　　　　else if (i > 0)
　　　　{
　　　　　　Reverse(p - i, p - 1);
　　　　　　i = 0;
　　　　}
　　}
}

完整程序见 ：程序员讨论组

智力题目

1
10 层楼的电梯门口，每层放一个宝石，10个宝石大小不同，每层门都会打开，只能检一次，怎样得到最大的宝石
2
法国某港口的船，美国某港口的船，同一时刻对开，每天中午同一时刻发一趟，某船从法国到美国要7天7夜对面碰到多少开来的船

3公升的提捅+5公升的提捅->4公升的水

　3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水？（40秒-3分钟）

答: 将五公升水桶里的水倒入三公升的桶,然后倒空三公升的桶,将五公升水桶里有两公升水倒入三公升的水桶,这样三公升的水桶就空出一公升的空间,装满五公升的水桶,然后用其加满三公升的桶,这样五公升的桶里就剩下四公升水了!!! 哈哈,师姐被蒙了!!

Re:烧绳问题&果冻问题

first：一个绳子从一端烧要1个小时，那么从两端烧就需要半个小时；
准备：3根绳子，编号1，2，3；
1从一端烧同时2从两端烧，2烧完后用了半个小时，2烧完的同时将1另一端点燃，烧完之后用了1/4小时，这时消耗总时间45分钟；1烧完的同时从两端点燃绳子3，烧完后花费时间30分钟；这时消耗总时间1个小时15分钟。
second：4个果冻，哈哈 ！！！ 小杜被蒙了！

微软算法题第4题

　　4.请编写能直接实现strstr()函数功能的代码。

参考答案：
　　// 使用最简单的字符串匹配。可以改进为KMP匹配算法
　　int StrStr(char a[], int alen, char pat[], int patlen)
　　{
　　　　int i = 0;
　　　　int j = 0;
　　　　while (i < alen && j < patlen)
　　　　{
　　　　　　if (a[i] == pat[j])
　　　　　　{
　　　　　　　　++i;
　　　　　　　　++j;
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　　i = i - j + 1;
　　　　　　　　j = 0;
　　　　　　}
　　　　}
　　　　if ( j >= patlen)
　　　　　　return (i - patlen + 1); //位置
　　　　else
　　　　　　return 0; //没有匹配
　　}

其它类似函数：（注意：都没有加错误判断！！！）
　　void StrCpy(char *dst, const char *src)
　　{
　　　　while (*dst++ = *src++)
　　　　　　;
　　}

　　int StrCmp(const char *s, const char *t)
　　{
　　　　for (; *s == *t; s++, t++)
　　　　　　if ( '\0' == *s)
　　　　　　　　return 0;
　　　　return (*s - *t);
　　}
完整代码见 程序员讨论组

微软算法题和参考答案

　　六.算法题（说明：这些题就不是什么花样了，考的是你的基础知识怎么样。再聪明而没有实学的人都将会被这些题所淘汰。）
　　1.链表和数组的区别在哪里？
　　2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
　　3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
　　4.请编写能直接实现strstr()函数功能的代码。
　　5.编写反转字符串的程序，要求优化速度、优化空间。
　　6.在链表里如何发现循环链接？
　　7.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
　　8.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）
　　9.给出一个函数来输出一个字符串的所有排列。
　　10.请编写实现malloc()内存分配函数功能一样的代码。
　　11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
　　12.怎样编写一个程序，把一个有序整数数组放到二叉树中？
　　13.怎样从顶部开始逐层打印二叉树结点数据？请编程。
　　14.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？

参考答案：仅供参考！（待增加）
　　1 顺序表（即数组）的主要优点体现在没有使用指针，节省存储空间，而且线性表元素的读访问非常简洁便利。
　　链表的主要优点则体现在无需事先确定线性表的长度，可以根据需要动态申请，且允许线性表的长度有很大变化，能够适应在线性表中经常插入、删除内部元素的情况。
　　需要根据具体的应用来选择采用何种存储方式的线性表。当线性表经常要进行插入、删除元素的操作时，不宜使用顺序表，另外，当无法事先确定线性表的长度时也不应选择顺序存储方式。而当需要经常对线性表进行按位置访问，且读操作比插入删除操作频率大时，则不应该选择链表。

　　2 对链表而言：直接插入排序，简单；归并排序，效率高，STL就使用的归并排序。
直接插入排序：
归并排序:（说明和源码）Mergesort For Linked Lists

　　3 对数组而言：快速排序，效率最高。
　　（附：快速排序和归并排序的比较：From PKU
　　快速排序首先从待排序序列Array中任意选择一个记录k作为轴值，然后将剩余的记录分割成两个子序列L和R。L中包含所有小于或等于轴值k的记录，都放在记录k的左边；R中包含所有大于轴值k的记录，都放在记录k的右边。原问题分解为子序列L和R这两个规模更小的同结构子问题，对L和R子序列递归进行快速排序，直到子序列中只含有0或1个元素时退出递归。
　　实际上快速排序名副其实，它几乎是最快的排序算法，被评选为20世纪十大算法之一。快速排序之所以快，主要因为它在分组时不是随便划分而是尽量将原数组划分为两半。
　　归并排序将序列划分为两个子序列，分别对两个子序列递归进行归并排序，将这两个已排好序的子序列合并为一个有序序列。快速排序侧重于分割过程，归并排序侧重于归并过程。归并排序比快速排序多了一个归并过程，但快速排序的不足之处在于轴值的选择对算法效率的影响太大。归并排序避免了这种最差情况，不依赖于原始数组中记录的有序程度。另外，归并排序是稳定的）
快速排序：Wikipedia（可能要代理）

（未完待续）

微软程序员测试题

转载自PConline

　　一．最基本题型（说明：此类题型比较简单）
　　1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢？（这道题我当初想了一个小时）
　　2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻？（5秒-1分钟）
　　3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水？（40秒-3分钟）
　　4.一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问？（20秒-2分钟）
　　5.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13个呢？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）（5分钟-1小时）
　　6.在9个点上画10条直线，要求每条直线上至少有三个点？（3分钟-20分钟）
　　7.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次？都分别是什么时间？你怎样算出来的？（5分钟-15分钟）

　　二．没有答案型（说明：这些题显然不是考你智力。而考的是你的反应能力。这种题大多数没有答案，但是要看你的反应喽！）
　　1.为什么下水道的盖子是圆的？
　　2.中国有多少辆汽车？
　　3.将汽车钥匙插入车门，向哪个方向旋转就可以打开车锁？
　　4.如果你要去掉中国的34个省（含自治区、直辖市和港澳特区及台湾省）中的任何一个，你会去掉哪一个，为什么？
　　5.多少个加油站才能满足中国的所有汽车？
　　6.想象你站在镜子前，请问，为什么镜子中的影象可以颠倒左右，却不能颠倒上下？
　　7.为什么在任何旅馆里，你打开热水，热水都会瞬间倾泻而出？
　　8.你怎样将Excel的用法解释给你的奶奶听？
　　9.你怎样重新改进和设计一个ATM银行自动取款机？
　　10.如果你不得不重新学习一种新的计算机语言，你打算怎样着手来开始？
　　11.如果你的生涯规划中打算在5年内受到奖励，那获取该项奖励的动机是什么？观众是谁？
　　12.如果微软告诉你，我们打算投资五百万美元来启动你的投资计划，你将开始什么样商业计划？为什么？
　　13.如果你能够将全世界的电脑厂商集合在一个办公室里，然后告诉他们将被强迫做一件事，那件事将是什么？

　　三．难题（说明：这类题有一定难度，如果得不到答案，也不能说明什么。如果你想到了解题思路，那么答案马上就能出来。如果想不到思路，那么……就别想解出来了。）
　　1.你让工人为你工作7天，回报是一根金条，这个金条平分成相连的7段，你必须在每天结束的时候给他们一段金条。如果只允许你两次把金条弄断，你如何给你的工人付费？
　　2.有一辆火车以每小时15公里的速度离开北京直奔广州，同时另一辆火车每小时20公里的速度从广州开往北京。如果有一只鸟，以30公里每小时的速度和两辆火车同时启动，从北京出发，碰到另一辆车后就向相反的方向返回去飞，就这样依次在两辆火车之间来回地飞，直到两辆火车相遇。请问，这只鸟共飞行了多长的距离？
　　3.你有四个装药丸的罐子，每个药丸都有一定的重量，被污染的药丸是没被污染的药丸的重量+1。只称量一次，如何判断哪个罐子的药被污染了？
　　4.门外三个开关分别对应室内三盏灯，线路良好，在门外控制开关时候不能看到室内灯的情况，现在只允许进门一次，确定开关和灯的对应关系？
　　5.人民币为什么只有1、2、5、10的面值？
　　6.你有两个罐子以及50个红色弹球和50个蓝色弹球，随机选出一个罐子， 随机选出一个弹球放入罐子，怎么给出红色弹球最大的选中机会？在你的计划里，得到红球的几率是多少？

　　四．超难题（说明：如果你是第一次看到这种题，并且以前从来没有见过类似的题型，并且能够在半个小时之内做出答案。只能说明你的智力超常……）
　　第一题 . 五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分：
抽签决定自己的号码（1、2、3、4、5）
　　首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔进大海喂鲨鱼
　　如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决，当且仅当超过半数的人同意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼
　　依此类推
　　条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
　　问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化？

　　第二题 . 一道关于飞机加油的问题，已知：
　　每个飞机只有一个油箱，
　　飞机之间可以相互加油（注意是相互，没有加油机）
　　一箱油可供一架飞机绕地球飞半圈，
　　问题：
　　为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）

　　五．主观题（说明：在以后的工作过程中，我们可定会犯这样那样的错误。既然错误已经酿成，损失在所难免，我们只能想办法把损失减少到最小。如果能巧妙地回答出这些问题，再发生错误的情况下。能让客户有最少的抱怨，公司有最少的损失。）
　　1.某手机厂家由于设计失误，有可能造成电池寿命比原来设计的寿命短一半（不是冲放电时间），解决方案就是免费更换电池或给50元购买该厂家新手机的折换券。请给所有已购买的用户写信告诉解决方案。
　　2.一高层领导在参观某博物馆时，向博物馆馆员小王要了一块明代的城砖作为纪念，按国家规定，任何人不得将博物馆收藏品变为私有。博物馆馆长需要如何写信给这位领导，将城砖取回。
　　3.营业员小姐由于工作失误，将2万元的笔记本电脑以1.2万元错卖给李先生，王小姐的经理怎么写信给李先生试图将钱要回来？

　　六.算法题（说明：这些题就不是什么花样了，考的是你的基础知识怎么样。再聪明而没有实学的人都将会被这些题所淘汰。）
　　1.链表和数组的区别在哪里？
　　2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
　　3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
　　4.请编写能直接实现strstr()函数功能的代码。
　　5.编写反转字符串的程序，要求优化速度、优化空间。
　　6.在链表里如何发现循环链接？
　　7.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
　　8.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）
　　9.给出一个函数来输出一个字符串的所有排列。
　　10.请编写实现malloc()内存分配函数功能一样的代码。
　　11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
　　12.怎样编写一个程序，把一个有序整数数组放到二叉树中？
　　13.怎样从顶部开始逐层打印二叉树结点数据？请编程。
　　14.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？

C语言难点 From《C专家编程》

选自《C专家编程》 作者：Perter Van Der LinDen

---------------------------------------
找代码中的错误：

1 int foo(const char **p) { }
2
3 main(int argc, char **argv)
4 {
5 foo(argv);
6 }

If you try compiling it, you'll notice that the compiler issues a warning message, saying:
line 5: warning: argument is incompatible with prototype
（提示：指针类型赋值问题）

---------------------------------------
找代码中的错误：

/* Convert the source file timestamp into a localized date string */
char * localized_time(char * filename)
{
struct tm *tm_ptr;
struct stat stat_block;
char buffer[120];
/* get the sourcefile's timestamp in time_t format */
stat(filename, &stat_block);
/* convert UNIX time_t into a struct tm holding local time
*/
tm_ptr = localtime(&stat_block.st_mtime);
/* convert the tm struct into a string in local format */
strftime(buffer, sizeof(buffer), "%a %b %e %T %Y", tm_ptr);
return buffer;
}

（提示：返回了局部变量）

---------------------------------------
If you want to cast something to the type of pointer-to-array, you have to express the cast as:

char (*j)[20]; /* j is a pointer to an array of 20 char */
j = (char (*)[20]) malloc( 20 );

If you leave out the apparently redundant parentheses around the asterisk, it becomes invalid.

---------------------------------------
A declaration involving a pointer and a const has several possible orderings:

const int * grape;
int const * grape;
int * const grape_jelly;

The last of these cases makes the pointer read-only, whereas the other two make the object that it points at read-only; and of course, both the object and what it points at might be constant. Either of the following equivalent declarations will accomplish this:

const int * const grape_jam;
int const * const grape_jam;

---------------------------------------
Does the following declaration (adapted from the telnet program) declare?

char* const *(*next)();

"next is a pointer to a function returning a pointer to a const pointer-to-char"

---------------------------------------
The ANSI Standard shows that signal is declared as:

void (*signal(int sig, void (*func)(int)) ) (int);

"signal is a function (with some funky arguments) returning a pointer to a function (taking an int argument and returning void)".
One of the funky arguments is itself:

void (*func)(int);

a pointer to a function taking an int argument and returning void. Here's how it can be simplified by a typedef that "factors out" the common part.

typedef void (*ptr_to_func) (int);
/* this says that ptr_to_func is a pointer to a function
* that takes an int argument, and returns void
*/
ptr_to_func signal(int, ptr_to_func);
/* this says that signal is a function that takes
* two arguments, an int and a ptr_to_func, and
* returns a ptr_to_func
*/

(未完待续)

海盗分金币

首先给个简单的，传说是微软的面试题：
有5个海盗A,B,C,D,E，得到100个金币，决定瓜分掉，分法怪异：
首先A提出分法，B,C,D,E表决，如果不过半数同意，就砍掉A的头（2：2也砍掉）；
然后由B来分，C,D,E表决，如果不过半数同意，就砍掉B的头；
依次类推，如果假设海盗都足够聪明，在不被砍掉头的同时获得最多的金币。
问：最后结果如何？（精确结果！）

上面实际上是海盗问题的一个变种。
经典的海盗问题：
十个海盗，分一百个金币。由首领先决定分法，有半数以上同意（包括半数），则这样分，不到半数，则首领被扔下海，由二首领来分，规则相同。
问：怎样分，首领才能得到最多的金币而不被扔下海？

继续推广为500个海盗呢？

详细解答见：
英文原文: A Puzzle for Pirates
中文翻译：海盗分金币
相关程序：海盗分金币

飞机加油问题

已知： 每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机），一箱油可供一架飞机绕地球飞半圈。
问题： 为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机？（所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场）

babli给出的答案： 5架。
首先出动三架，由一架向另两架持续加油，以保持这两架的油始终保持是满的。这种状况可以保持到1/8圈，然后这架飞机就可以安全返航了。（1/2 = 4*1/8）
接着一架飞机向另一架飞机加油，也让这架保持油始终是满的。这样可以到1/4圈处，然后加油的飞机也返航，这样就有一架是满油，而且飞到了1/4圈处的飞机。
接下来在反方向也这样搞。就是出动两架飞机，方向与开始三架飞机相反，去接那架满油飞到1/4处的飞机。 基本上这样就ok了。

称球问题

有12球，其中一球质量不同与其于其他11球，外形一样，现用一天平称3次，如何称？
推广一下：对于给定的自然数N，怎么来解有N个球的称球问题？

详细解答见：
称球问题——经典智力题推而广之三

简单答案：
12球问题：称三次。
1.编号 1到12
2.把球分三组， 四个一组
3.先称 1 2 3 4 和 5 6 7 8
4.再称 1 2 3 5 和 4 9 10 11
以上的条件是假设每次称天平都不平， 如果有平的就很简单了。

另：8球问题(需附加条件，其中一球重)：称两次。
对球编号，A组：㈠㈡㈢；B组：㈣㈤㈥；C组：㈦㈧
A、B两组称
|——A重——㈠、㈡两球称
|.....................|——㈠球重
|.....................|——㈡球重
|.....................|——一样重——㈢球重
|
|——B重——方法同上
|
|——AB等重——㈦、㈧两球称
|.....................|——㈦球重
|.....................|——㈧球重