14、实现strstr功能，即在父串中寻找子串首次出现的位置。（笔试中常让面试者实现标准库中的一些函数）

char * strstring(char *ParentString, char *SubString) {
 char *pSubString, *pPareString;
 for(char *pTmp=ParentString; *pTmp; pTmp++) {
  pSubString = SubString;
  pPareString = pTmp;
  while(*pSubString == *pPareString && *pSubString != '\0') {
   pSubString++;
   pPareString++;
  }
  if(*pSubString == '\0')  return pTmp;
 }
 return NULL;
}
int main(int argc, char* argv[]) {
 char *ParentString = "happy birthday to you!";
 char *SubString = "birthday";
 printf("%s",strstring(ParentString, SubString));
}

15、现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过桥要1分，小明的弟弟要3分，小明的爸爸要6分，小明的妈妈要8分，小明的爷爷要12分。每次此桥最多可过两人，而过桥的速度依过桥最慢者而定，而且灯在点燃后30分就会熄灭。问小明一家如何过桥时间最短？（原本是个小小智力题，据说是外企的面试题，在这里用程序来求解）

#include "stdafx.h"
#define N    5
#define SIZE 64
// 将人员编号：小明-0，弟弟-1，爸爸-2，妈妈-3，爷爷-4
// 每个人的当前位置：0--在桥左边， 1--在桥右边
int Position[N];   
// 过桥临时方案的数组下标； 临时方案； 最小时间方案；
int Index, TmpScheme[SIZE], Scheme[SIZE];  
// 最小过桥时间总和，初始值100；每个人过桥所需要的时间
int MinTime=100, Time[N]={1, 3, 6, 8, 12}; 
// 寻找最佳过桥方案。Remnant:未过桥人数; CurTime:当前已用时间;
// Direction:过桥方向,1--向右,0--向左
void Find(int Remnant, int CurTime, int Direction) {
    if(Remnant == 0) {                               // 所有人已经过桥，更新最少时间及方案
        MinTime=CurTime;
        for(int i=0; i=0; i++)
            Scheme = TmpScheme;
    } else if(Direction == 1) {                        // 过桥方向向右，从桥左侧选出两人过桥
        for(int i=0; i
            if(Position == 0 && CurTime + Time < MinTime) {
                TmpScheme[Index++] = i;
                Position = 1;
                for(int j=0; j
                    int TmpMax = (Time > Time[j]  Time : Time[j]);
                    if(Position[j] == 0 && CurTime + TmpMax < MinTime) {
                        TmpScheme[Index++] = j;   
                        Position[j] = 1;       
                        Find(Remnant - 2, CurTime + TmpMax, !Direction);
                        Position[j] = 0;       
                        TmpScheme[--Index] = -1;
                    }
                }
                Position = 0;
                TmpScheme[--Index] = -1;
            }
    } else {        // 过桥方向向左，从桥右侧选出一个人回来送灯
        for(int j=0; j
            if(Position[j] == 1 && CurTime+Time[j] < MinTime) {
                TmpScheme[Index++] = j;
                Position[j] = 0;
                Find(Remnant+1, CurTime+Time[j], !Direction);
                Position[j] = 1;
                TmpScheme[--Index] = -1;
            }
        }
    }
}
int main(int argc, char* argv[]) {
    for(int i=0; i
        Scheme = TmpScheme = -1;
Find(N, 0, 1);        // 查找最佳方案
    printf("MinTime=%d:", MinTime); // 输出最佳方案
    for(int i=0; i=0; i+=3)
        printf("  %d-%d  %d", Scheme, Scheme[i+1], Scheme[i+2]);
    printf("\b\b  ");
}

16、2005年11月金山笔试题。编码完成下面的处理函数。函数将字符串中的字符’‘移到串的前部分，前面的非’‘字符后移，但不能改变非’‘字符的先后顺序，函数返回串中字符’‘的数量。如原始串为：ab**cd**e*12，处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）

int change(char *str) {    
 int count = 0;    
 for(int i=0, j=0; str; i++) { 
  if(str=='*') {   
   for(j=i-1; str[j]!='*'&&j>=0; j--)
    str[j+1]=str[j];    
   str[j+1] = '*';
   count++;
  }
 }
 return count;
}
int main(int argc, char* argv[]) {
 char str[] = "ab**cd**e*12";
 printf("str1=%s\n", str);
 printf("str2=%s, count=%d", str, change(str));
}
// 终于得到一个比较高效的算法，一个网友提供，估计应该和金山面试官的想法一致。算法如下：
int change(char *str) {
 int i,j=strlen(str)-1;
 for(i=j; j>=0; j--) {
  if(str!='*') {
   i--;
  } else if(str[j]!='*') {
   str = str[j];
   str[j] = '*';
   i--;
  }
 }
 return i+1;
}

17、2005年11月15日华为软件研发笔试题。实现一单链表的逆转。

#include "stdafx.h"
typedef char eleType;  // 定义链表中的数据类型
typedef struct listnode  { // 定义单链表结构
 eleType data;
 struct listnode *next;
}node;
node *create(int n) {  // 创建单链表，n为节点个数
 node *p = (node *)malloc(sizeof(node));
 node *head = p;  head->data = 'A';
 for(int i='B'; i<'A'+n; i++) {   
  p = (p->next = (node *)malloc(sizeof(node)));
  p->data = i;
  p->next = NULL; 
 }
 return head;
}
void print(node *head) { // 按链表顺序输出链表中元素
 for(; head; head = head->next)
  printf("%c ", head->data);
 printf("\n");
}
node *reverse(node *head, node *pre) { // 逆转单链表函数。这是笔试时需要写的最主要函数
 node *p=head->next;
 head->next = pre;
 if(p) return reverse(p, head);
 else  return head;
}
int main(int argc, char* argv[]) {
 node *head = create(6);
 print(head);
 head = reverse(head, NULL);
 print(head);
}