网络上搜集的面试题
原文：http://blog.csdn.net/he_haiqiang/article/details/7914983
假设需要将N个任务分配给N个工人同时去完成,每个人都能承担这N个任务,但费用不
同.下面的程序用回溯法计算总费用最小的一种工作分配方案,在该方案中,为每个人分配
1个不同的任务.
程序中,N个任务从0开始依次编号,N个工人也从0开始依次编号,主要的变量说明如下:
c[i][j]:将任务i分配给工人j的费用;
task[i]:值为0表示任务i未分配,值为j表示任务i分配给工人j;
worker[k]:值为0表示工人k未分配任务,值为1表示工人k已分配任务;
mincost:最小总费用.
*/
#include <stdio.h>
#include <stdlib.h>
#define N 8 //N表示任务数和工人数
int c[N][N];
unsigned int mincost = 65535; //设置的初始值,大于可能的费用
int task[N],temp[N],worker[N];
void Plan(int k,unsigned int cost){
int i;
if(k>=N && cost<mincost){
mincost = cost;
for(i=0;i<N;i++){
temp[i] = task[i];
}
}else{
for(i=0;i<N;i++){ //分配任务k
if(worker[i]==0 && cost+c[k][i]){
worker[i] = 1; task[k] = i;
Plan(k+1,cost+c[k][i]);
worker[i] = 0; task[k] = 0;
}
}
}
}来求出用1，2，5这三个数不同个数组合的和为1000的组合个数(华为面试题目)
即x+2y+5z=100，并且条件为x<=100,y<=50,z<=20
程序就如下：
int number=0;
for (x=0; x<=100; x++) for (y=0; y<=50; y++) for (z=0; z<=20; z++) if ((x+2*y+5*z)==100) number++; 3 void main()
4 {
5 int i,j,n=0;
6 for(i=0;i<=20;i++)
7 {
8 for(j=0;j<=(100-i*5)/2;j++)
9 {
10 n++;
11 }
12 }
用异或运算实现交换两个变量的值
void swap(int a , int b)
{
a = a^b;
b = a^b;
a = a^b;
}
Winsock建立套接字的步骤
服务器端:socket()建立套接字,绑定bind()并监听listen(),用accept()等待客户端连接.
客户端:socket()建立套接字,连接connect()服务器,连接上后使用send()和recv(),在套接字上读写数据,直至数据交换完毕,closesocket()关闭套按字.
服务器端:accept()发现有客户端连接,建立一个新的套接字,自身重新开始等待连接.该新产生的套接字使用send()和recv()读写数据,直至数据交换完毕,closesocket()关闭套接字.
MFC消息映射机制
消息映射就是建立一个消息和函数的对应表，当收到消息时查找表，如果表中有相应的消息，就将消息交给相应的函数处理。通俗点讲，消息映射表就是一个记录了消息号和相应处理函数的数组。当然表中还有其他信息，这里先说矛盾的主要方面了。其中消息映射表中的每个元素都是一个结构体变量，他的成员很多，最主要的就是消息号和相对应的消息处理函数。关于消息映射表的查找，是通过虚函数实现的，通过父类的虚函数查找父类及其层层子类定义的消息映射表。如果找不到，就交给默认的窗口处理函数处理。 如果一个类的消息映射表中定义了一个消息处理，那么就不再继续查找子类或者子类的子类，从而实现了覆盖。
进程间、线程间通信方式概括
博客分类： C++网络应用Socket 【转】进程间的通信方式：
1.管道（pipe）及有名管道（named pipe）：
管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信。
2.信号（signal）：
信号是在软件层次上对中断机制的一种模拟，它是比较复杂的通信方式，用于通知进程有某事件发生，一个进程收到一个信号与处理器收到一个中断请求效果上可以说是一致的。
3.消息队列（message queue）：
消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息。
4.共享内存（shared memory）：
可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等。
5.信号量（semaphore）：
主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段。
6.套接字（socket）；
这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
线程之间的同步通信：
1.信号量 二进制信号量 互斥信号量 整数型信号量 记录型信号量
2.消息 消息队列 消息邮箱
3.事件event
- 请用标准C语言实现下列标准库函数，设计中不得使用其他库函数。
char *strstr(char *str1,char *str2);
在字符串str1中，寻找字串str2，若找到返回找到的位置，否则返回NULL
const char* StrStr(const char *str1, const char *str2) - {
- assert(NULL != str1 && NULL != str2);
- while(*str1 != " ")
- {
- const char *p = str1;
- const char *q = str2;
- const char *res = NULL;
- if(*p == *q)
- {
- res = p;
- while(*p && *q && *p++ == *q++)
- ;
- if(*q == " ")
- return res;
- }
- str1++;
- }
- return NULL;
- }
已知strcat函数的原型是
char *strcat (char *strDest, const char *strSrc);
其中strDest 是目的字符串，strSrc 是源字符串。
char* Strcat(char *str1,char *str2)
{
char* tempt = str1;
while(*str1!=" ")
{
str1++;
}
while(*str2!=" ")
{
*str1 = *str2;
str1++;
str2++;
}
*str1 = " ";
return tempt;
} 求质数的程序 bool NotRrime(int num) { bool bRim=false; i f (num<3) { returnfalse; } while (num>=3) { for (int index=2;index<num;index++ ) { if (num%index==0) { bRim =true;break; } } } return bRim; } 大端模式和小端模式
大端格式：
在这种格式中，字数据的高字节存储在低地址中，而字数据的低字节则存放在高地址中，如图2.1所示：
小端格式：
与大端存储格式相反，在小端存储格式中，低地址中存放的是字数据的低字节，高地址存放的是字数据的高字节。如图2.2所示：
请写一个C函数，若处理器是Big_endian的，则返回0；若是Little_endian的，则返回1
解答：
int checkCPU( )
{
{
union w
{
int a;
char b;
} c;
c.a = 1;
return(c.b ==1);
}
}
库函数atoi c语言实现
2012-04-13 21:46 39人阅读 评论(0)收藏举报
库函数原型：
#inclue <stdlib.h>
int atoi(const char *nptr);
用法：将字符串里的数字字符转化为整形数，返回整形值。
注意：转化时跳过前面的空格字符，直到遇上数字或正负符号才开始做转换，而再遇到非数字或字符串结束符号时("/0")才结束转换，并将结果返回。
例：
#include <stdio.h>
#include <stdlib.h>
int main()
{
char *ptr1 = "-12345.12";
char *ptr2 = "+1234w34";
char *ptr3 = " 456er12";
char *ptr4 = "789 123";
int a,b,c,d;
a = atoi(ptr1);
b = atoi(ptr2);
c = atoi(ptr3);
d = atoi(ptr4);
printf("a = %d, b = %d, c = %d, d = %d/n", a,b,c,d);
return 0;
}
输出结果：a = 12345， b = 1234， c = 456， d = 789
***************************************************
不调用库函数用C语言实现atoi函数的功能：
#include <stdio.h>
#include <stdlib.h>
int my_atoi(const char *str);
int main(int argc, char *argv[])
{
char *ptr = " 1234 3455";
int n;
n = my_atoi(ptr);
printf("myAtoi:%d/n", n);
n = atoi(ptr);
printf("atoi:%d/n", n);
return 0;
}
int my_atoi(const char *str)
{
int value = 0;
int flag = 1; //判断符号
while (*str == " ") //跳过字符串前面的空格
{
str++;
}
if (*str == "-") //第一个字符若是‘-’，说明可能是负数
{
flag = 0;
str++;
}
else if (*str == "+") //第一个字符若是‘+’，说明可能是正数
{
flag = 1;
str++;
}//第一个字符若不是‘+’‘-’也不是数字字符，直接返回0
else if (*str >= "9" || *str <= "0")
{
return 0;
}
//当遇到非数字字符或遇到‘/0’时，结束转化
while (*str != "/0" && *str <= "9" && *str >= "0")
{
value = value * 10 + *str - "0"; //将数字字符转为对应的整形数
str++;
}
if (flag == 0) //负数的情况
{
value = -value;
}
return value;
}
五大算法：贪心法，动态规划法，分治法
http://blog.sina.com.cn/s/blog_3f135d4601010lsk.html
字符串逆序
中文需要单独处理的，一个中文占两个字节，反转时顺序不变。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void reverse(char* s)
{
int len = strlen(s);
char* pNewStr = (char*)malloc(len + 1) ;
char* pNewMove = pNewStr;
char* pStr = s + len - 1;
while(pStr >= s)
{
unsigned char ch = *pStr;
if(ch > 127) //中文判断 不太确定，这个条件是否严谨，在本机测试没问题
{
*pNewMove = *(pStr - 1);
pNewMove ++;
*pNewMove= *pStr;
pNewMove ++;
pStr -= 2;
}else
{
*pNewMove =*pStr;
pNewMove ++;
pStr--;
}
}
pNewStr[len] = " ";
strcpy(s,pNewStr);
free(pNewStr);
}
int main()
{
char str[201];
printf("输入要反转的字符串 ");
scanf("%s",str);
reverse(str);
printf("反转后字符变为: %s ",str);
system("pause");
return 0;
}
top命令是Linux下常用的性能分析工具，能够实时显示系统中各个进程的资源占用状况，类似于Windows的任务管理器。
2011-10-08 00:00中国IT实验室佚名 关键字：Linux(1)at命令
假如我们只是想 要让特定任务运行一次,那么，这时候就要用到at监控程序了。
设置at命令很简单，指示定运行的时间，那么就会在哪个时候运行。at类似打印 进程，会把任务放到/var/spool/at目录中，到指定时间运行它 。at命令相当于另一个shell，运行at time命令时，它发送一个个命令，可以输入任意命令或者程序。at now + time命令可以在指示任务。
假设处理一个大型数据库，要在别人不用系统时去处理数据，比如凌晨3点10分。那么我们就应该先建立/home/kyle/do_job脚本管理数据库，计划处理/home/kyle/do_job文件中的结果。正常方式是这样启动下列命令:
# at 2:05 tomorrow
at>/home/kyle/do_job
at> Ctrl+D
AT Time中的时间表示方法
-----------------------------------------------------------------------
时 间 例子 说明
-----------------------------------------------------------------------
Minute at now + 5 minutes 任务在5分钟后运行
Hour at now + 1 hour 任务在1小时后运行
Days at now + 3 days 任务在3天后运行
Weeks at now + 2 weeks 任务在两周后运行
Fixed at midnight 任务在午夜运行
Fixed at 10:30pm 任务在晚上10点30分
注意：一定要检查一下atq的服务是否启 动，有些操作系统未必是默认启动的， linux默认为不启动，而ubuntu默认为启动的。检查是否启动，用service atd检查语法，用service atd status检查atd的状态，用service atd start启动atd服务。
查看at执行的具体内容：一般位于/var/spool/at目录下面， 用vi打开，在最后一部分就是你的执行程序
(2)crontab
cron是一个linux下 的定时执行工具，可以在无需人工干预的情况下运行作业。由于Cron 是Linux的内置服务，但它不自动起来，可以用以下的方法启动、关闭这个服务：
/sbin/service crond start //启动服务
/sbin/service crond stop //关闭服务
/sbin/service crond restart //重启服务
/sbin/service crond reload //重新载入配置
/sbin/service crond status //查看服务状态
你也可以将这个服务在系统启 动的时候自动启动：
在/etc/rc.d/rc.local这个脚本的末尾加上：
/sbin/service crond start
现在Cron这个服务已经在进程里面了，我们就可以用这个服务了，Cron服务提供以下几种接口供大家使用：
1、直接用crontab命 令编辑
cron服务提供 crontab命令来设定cron服务的，以下是这个命令的一些参数与说明：
crontab -u //设定某个用户的cron服务，一般root用户在执行这个命令的时候需要此参数
crontab -l //列出某个用户cron服务的详细内容
crontab -r //删除某个用户的cron服务
crontab -e //编辑某个用户的cron服务
比如说root查看自己的cron设置：crontab -u root -l
再例 如，root想删除fred的cron设置：crontab -u fred -r
基本格式 :
* * * * * command
分 时 日 月 周 命令
第1列表示分钟1～59 每分钟用*或者 */1表示
第2列表示小时1～23(0表示0点)
第3列表示日期1～31
第4列表示月份1～12
第5列标识号星期0～6(0表示星期天)
第6列要运行的命令
crontab文件的一些例子：
#每晚的21:30重启apache。
30 21 * * * /usr/local/etc/rc.d/lighttpd restart
#每月1、10、22日
45 4 1,10,22 * * /usr/local/etc/rc.d/lighttpd restart
#每天早上6点10分
10 6 * * * date
#每两个小时
0 */2 * * * date
#晚上11点到早上8点之间每两个小时，早上8点
0 23-7/2，8 * * * date
#每个月的4号和每个礼拜的礼拜一到礼拜三的早上11点
0 11 4 * mon-wed date
#1月份日早上4点
0 4 1 jan * date
进程是程序的一次执行，线程可以理解为进程中的执行的一段程序片段。在一个多任务环境中下面的概念可以帮助我们理解两者间的差别：
进程间是独立的，这表现在内存空间，上下文环境；线程运行在进程空间内。
一般来讲（不使用特殊技术）进程是无法突破进程边界存取其他进程内的存储空间；而线程由于处于进程空间内，所以同一进程所产生的线程共享同一内存空间。
同一进程中的两段代码不能够同时执行，除非引入线程。
线程是属于进程的，当进程退出时该进程所产生的线程都会被强制退出并清除。
线程占用的资源要少于进程所占用的资源。
进程和线程都可以有优先级。
在线程系统中进程也是一个线程。可以将进程理解为一个程序的第一个线程。
以下程序的输出结果是：0120；
#include <stdio.h>
void eit(int n);
int main(void)
{
int a = 3;
eit(a);
return 0;
}
void eit(int n)
{
if (n > 0)
{
eit(--n);
printf("%d", n);
eit(--n);
}
}
一道思考题：
写一个“标准”宏MIN，这个宏输入两个参数并返回较小的一个。另外，当你运行”least = MIN(*p++, b); “代码时会发生什么事？
解答： #define MIN(A,B) ( (A) <= (B) ? (A) : (B) ) MIN(*p++, b)会产生宏的副作用。
剖析： 这道题考察对宏定义的使用，宏定义可以实现类似于函数的功能，但是它终归不是函数，而宏定义中括弧中的“参数”也不是真的参数，在宏展开的时候对“参数”进行的是一对一的替换。 程序员对宏定义的使用要非常小心，特别要注意两个问题：
（1）谨慎地将宏定义中的“参数”和整个宏用用括弧括起来。所以，严格地讲，下
述解答： #define MIN(A,B) (A) <= (B) ? (A) : (B) #define MIN(A,B) (A <= B ? A : B ) 都是错误的。
（2）防止宏的副作用。宏定义#define MIN(A,B) ((A) <= (B) ? (A) : (B))对MIN(*p++, b)的作用结果是： ((*p++) <= (b) ? (*p++) : (b)) 这个表达式会产生副作用，指针p会作二次++自增操作。
除此之外，另一个典型的错误解答是： #define MIN(A,B) ((A) <= (B) ? (A) : (B)); 这个解答在宏定义的后面加“;”，显示编写者对宏的概念模糊不清。
搜索引擎是指根据一定的策略、运用特定的计算机程序从互联网上搜集信息，在对信息进行组织和处理后，为用户提供检索服务，将用户检索相关的信息展示给用户的系统。搜索引擎包括全文索引、目录索引、元搜索引擎、垂直搜索引擎、集合式搜索引擎、门户搜索引擎与免费链接列表等。百度和谷歌等是搜索引擎的代表。
就是对地图中的特征点如何获取
1、给定一个数组a[N],我们希望构造数组b[N]，其中b[i]=a[0]*a[1]*...*a[N-1]/a[i]。在构造过程：
不允许使用除法；
要求O(1)空间复杂度和O(n)时间复杂度；
除遍历计数器与a[N] b[N]外，不可使用新的变量(包括栈临时变量、对空间和全局静态变量等)；
请用程序实现并简单描述。
解答：数组分割
10 void output(long long* a, int len)
20 /*
21 题目要求的算法
22 */
23 /************************************************************************/
24 void problem(int* a, long long* b, int N)
25 {
26 b[0] = 1;
27 for(int i = 1; i < N; ++i)
28 {
29 b[i] = b[i-1] * a[i-1]; // 分水岭的前半段乘积
30 }
31
32 b[0] = a[N - 1];
33 for(int i = N - 2; i >= 1; --i)
34 {
35 b[i] *= b[0];
36 b[0] *= a[i]; // 分水岭的后半段乘积，是从数组尾部向前循环的
37 }
38 }
1.一个正确的二分法。
二分查找用于在多条记录中快速找到待查找的记录。它的思想是：每次将查找的范围缩小一半，直到最后找到记录或者找不到记录返回。
二分查找的时间复杂度为O(logn)
二分法的递归和非递归算法如下
i.非递归算法。
[cpp] view plaincopyprint?
1. int binary_search(int arr[],int n ,int key){
2. int mid;
3. int low = 0,high = n-1;
4. while(low <= high){ //防止死循环
5. mid = low + (high - low)/2; //中间元素，防止溢出
6. if(key == arr[mid]) return mid;//找到时返回
7.
8. else if(key > arr[mid]){
9. low = mid + 1;//在更高的区间搜索
10. }else{
11. high = mid - 1;//在更低的区间搜索
12. }
13. }
14. return -1;//没有找到元素，返回-1
15.
16. }
ii.递归算法：
[cpp] view plaincopyprint?
1. int binary_search(int arr[],int low,int high,int key){
2. if(low > high) return -1;
3. int mid = low + (high - low)/2 //中间元素，防止溢出
4. if(key == arr[mid])return mid;//找到时返回
5.
6. else if(key > arr[mid]){
7. return binary_search(arr,mid + 1,high,key);/在更高的区间搜索
8. }else{
9. return binary_search(arr,low,mid - 1,key);/在更低的区间搜索
10. }
11. }
12.
经典书籍推荐，主要是linux C方面的，我把我看过或者了解的简单说一下。
C语言：
C程序设计语言 --
没有太细的看，而且修为不够，所以没啥感觉
C和指针 -- 感觉这本书倒很适合做大一的教材，比较经典。
C陷阱与缺陷 --
两天就能看完吧，比较简单，只要了解一些变态语法就行。
C专家编程 --
我没看。但九度貌似有word版总结这几本书的，那个word看完了。确实总结的很不错。
个人重点推荐C和指针 +
C陷阱缺陷
C++
C++ Primer -- 看了两遍吧；实习生面试前一遍；暑假一遍；
高质量程序设计指南C/C++ --
6月初看的一遍，这本书很不错，很多黑体重要结论，引经据典，回答C++的问题能够拎上的话加分不少。
深度搜索C++对象模型 --
6月份看的，有点小难，而且意义不是很大，了解一个逻辑模型就可以了，而且里面本身就有很多错误。
STL源码剖析 --
暑假看的更是扫描的看的。重原理，轻细节，纠结详尽的模板语法对菜鸟来说估计会死。
Effective C++ --
每天整理两三个条款，我觉得这种条款类的书很适合闲暇时间看。
More Effective C++ --
就挑了几个常考的条款看了看，挺好的。
Effective STL --
仅看了几个条款。
软件基础知识，个人认为最好都通晓点：
数据结构 & 算法设计分析 --
算法导论对我这菜鸟实在啃不动。就整了考研时李春葆的课本 + 清华那本计算机算法设计与分析。
操作系统原理 -- 汤子瀛的课本 整了整进程调度 +
内存那块。
计算机网络 -- 谢希仁的课本 整了整网络层 + 传输层。
数据库系统实现 --
结合pg源码看的。同样，也是看到编译执行，并发事务没看。
搜索引擎-信息检索实践 --
9月中旬才买的书，忽悠搜索引擎用的，但整天在面试，基本没看。但看看挺好的。忽悠百度、搜狗、有道啥的有用。
大话设计模式 --
就看了几个模式。本来就一个暑假，不可能样样都知道，实验室老板还逼着看Totem源代码（实验室基于PostgreSQL自己开发的扩展版数据库，代码更改了近三分之一啊感觉，也就不奇怪当年开发实验室自己数据库那帮人很多去搞Oracle
DB2了，武大最后三年制变两年制的最后一届）
个人推荐：数据结构和算法最重要啊还是，另外，建议大家买的专业课考研资料不要卖啊。看重点很有用。
Linux/Unix程序设计部分
Linux程序设计，过年开学正月十五去光谷玩时在华科买的，5月份差不多主要部分就看完了。了解了这么些系统调用。啥的。
UNIX环境高级编程
6月18号 - 7月30号 看了两遍，并做了笔记。挺好的。
POSIX多线程程序设计
第二遍看APUE时附带看的，这本书很早就绝版了，电子版貌似也不多。
TCP/IP Sockets编程(C语言实现)
简单的入门书。200页很薄。
TCP/IP高效编程
真本书是条款的，44个条款。大概也就看了前十多个条款。挺好的，有时间的话这两本加起来基本可以了，UNIX网络编程那两卷加起来都可以镇宅用了，能看？
重点推荐UNIX环境高级编程
+
TCP/IP高效编程啊。后边那本书44个条款对网络编程绝对是一个很好的总结。另外shell/python啥的，反正找工作时候自学了一点，基本不会。也没重点去看，所以没啥推荐的。
应试啊，应试啊：
编程之美--至少今年很多题还出自这里面，必不可少。。。
程序员面试宝典
-- 三天就能看完，真要沦落到看这本书，那。。。除非技术正的大牛。。。
程序员求职成功路：技术、求职技巧与软实力培养 --
就算看应试的书，个人推荐还是看这本吧，讲的很多都比较有深度。尤其前几章C内存的部分。
程序员面试攻略 --
题目比较老，但是看看有助于思维发散。
《编程之美:
求二叉树中节点的最大距离》的另一个解法
昨天花了一个晚上为《编程之美》，在豆瓣写了一篇书评《迟来的书评和感想──给喜爱编程的朋友》。书评就不转载到这里了，取而代之，在这里介绍书里其中一条问题的另一个解法。这个解法比较简短易读及降低了空间复杂度，或者可以说觉得比较「美」吧。
问题定义
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。
我也想不到更好的分析方法。
书上的解法
书中对这个问题的分析是很清楚的，我尝试用自己的方式简短覆述。
计算一个二叉树的最大距离有两个情况:
情况A: 路径经过左子树的最深节点，通过根节点，再到右子树的最深节点。
情况B: 路径不穿过根节点，而是左子树或右子树的最大距离路径，取其大者。
只需要计算这两个情况的路径距离，并取其大者，就是该二叉树的最大距离。
我也想不到更好的分析方法。
但接着，原文的实现就不如上面的清楚 (源码可从这里下载):
?
// 数据结构定义
struct NODE
{
NODE* pLeft; // 左子树
NODE* pRight; // 右子树
int nMaxLeft; // 左子树中的最长距离
int nMaxRight; // 右子树中的最长距离
char chValue; // 该节点的值
};
int nMaxLen = 0;
// 寻找树中最长的两段距离
void FindMaxLen(NODE* pRoot)
{
// 遍历到叶子节点，返回
if(pRoot == NULL)
{
return;
}
// 如果左子树为空，那么该节点的左边最长距离为0
if(pRoot -> pLeft == NULL)
{
pRoot -> nMaxLeft = 0;
}
// 如果右子树为空，那么该节点的右边最长距离为0
if(pRoot -> pRight == NULL)
{
pRoot -> nMaxRight = 0;
}
// 如果左子树不为空，递归寻找左子树最长距离
if(pRoot -> pLeft != NULL)
{
FindMaxLen(pRoot -> pLeft);
}
// 如果右子树不为空，递归寻找右子树最长距离
if(pRoot -> pRight != NULL)
{
FindMaxLen(pRoot -> pRight);
}
// 计算左子树最长节点距离
if(pRoot -> pLeft != NULL)
{
int nTempMax = 0;
if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight)
{
nTempMax = pRoot -> pLeft -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pLeft -> nMaxRight;
}
pRoot -> nMaxLeft = nTempMax + 1;
}
// 计算右子树最长节点距离
if(pRoot -> pRight != NULL)
{
int nTempMax = 0;
if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight)
{
nTempMax = pRoot -> pRight -> nMaxLeft;
}
else
{
nTempMax = pRoot -> pRight -> nMaxRight;
}
pRoot -> nMaxRight = nTempMax + 1;
}
// 更新最长距离
if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen)
{
nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight;
}
}
有一个数组，该数组的特点是：前一部分递增有序，后一部分递减有序，求数组的峰值位置
我们发现，给出的数组可能有如下三种形态：
其中后两种情况是属于特殊的，是有序数组，峰值的位置就是数组的开始或结束索引。我们单单考虑第一种情况。
思考1：线性扫描,思路最简单，也最容易实现，只需扫描 一遍数组，比较当前元素与前一个元素的大小关系，一旦碰到当前元素比前一元素小，前一元素就是峰值。或者比较当前元素与后一元素，一旦后一元素比当前元素小，当前元素就是峰值。此方法的缺点是需要线性时间O(n)
思考2：考虑二分搜索，如果不考虑情况2和情况3.对于情况一而言，mid中间元素的位置不外乎三个情况：
是不是跟二分搜索很类似？
我们可以根据中间元素与两边元素的大小关系，判断搜索左边还是右边。据此，不难写出如下代码（未经严格测试）：
[cpp] view plaincopyprint?
1. #include <stdio.h>
2.
3. //数组是先增后减数组。
4. int findMax(int *a ,int n){
5. int low = 0,high = n-1,mid;
6. while(low <= high){
7. mid = low + ((high-low)>>1);
8. if((mid + 1)<=high && (mid-1)>=low){
9. if(a[mid] >= a[mid-1] && a[mid] >= a[mid + 1]){
10. return mid;
11. }else if(a[mid] >= a[mid-1] && a[mid] <=a[mid + 1]){
12. low = mid + 1;
13. }else{
14. high = mid - 1;
15. }
16. }else if((mid+1) <= high){
17. if(a[mid] <= a[mid+1]){
18. return mid+1;
19. }else{
20. return mid;
21. }
22. }else{
23. if(a[mid] <= a[mid-1]){
24. return mid-1;
25. }else{
26. return mid;
27. }
28. }
29.
30. }
31. }
32.
33. int main(){
34. int a[] = {1,2,7,6,5,4,3,1};
35. printf("%d
",findMax(a,8));
36. }
OSI七层划分
各层功能
应用层（Application Layer）
与其它计算机进行通讯的一个应用，它是对应应用程序的通信服务的。例如，一个没有通信功能的字处理程序就不能执行通信的代码，从事字处理工作的程序员也不关心OSI的第7层。但是，如果添加了一个传输文件的选项，那么字处理器的程序员就需要实现OSI的第7层。示例：telnet，HTTP,FTP,NFS,SMTP等。
表示层（Presentation Layer）
这一层的主要功能是定义数据格式及加密。例如，FTP允许你选择以二进制或ASCII格式传输。如果选择二进制，那么发送方和接收方不改变文件的内容。如果选择ASCII格式，发送方将把文本从发送方的字符集转换成标准的ASCII后发送数据。在接收方将标准的ASCII转换成接收方计算机的字符集。示例：加密，ASCII等。
会话层（Session Layer）
它定义了如何开始、控制和结束一个会话，包括对多个双向消息的控制和管理，以便在只完成连续消息的一部分时可以通知应用，从而使表示层看到的数据是连续的，在某些情况下，如果表示层收到了所有的数据，则用数据代表表示层。示例：RPC，SQL等。
传输层（Transport Layer）
这层的功能包括是否选择差错恢复协议还是无差错恢复协议，及在同一主机上对不同应用的数据流的输入进行复用，还包括对收到的顺序不对的数据包的重新排序功能。示例：TCP，UDP，SPX。
网络层（Network Layer）
这层对端到端的包传输进行定义，它定义了能够标识所有结点的逻辑地址，还定义了路由实现的方式和学习的方式。为了适应最大传输单元长度小于包长度的传输介质，网络层还定义了如何将一个包分解成更小的包的分段方法。示例：IP,IPX等。
数据链路层（Data Link Layer）
它定义了在单个链路上如何传输数据。这些协议与被讨论的各种介质有关。示例：ATM，FDDI等。
物理层（Physical Layer）
OSI的物理层规范是有关传输介质的特性标准，这些规范通常也参考了其他组织制定的标准。连接头、帧、帧的使用、电流、编码及光调制等都属于各种物理层规范中的内容。物理层常用多个规范完成对所有细节的定义。示例：Rj45，802.3等。
在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
在TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接。
第一次握手：建立连接时，客户端发送syn包(syn=j)到服务器，并进入SYN_SEND状态，等待服务器确认；
第二次握手：服务器收到syn包，必须确认客户的SYN（ack=j+1），同时自己也发送一个SYN包（syn=k），即SYN+ACK包，此时服务器进入SYN_RECV状态； 第三次握手：客户端收到服务器的SYN＋ACK包，向服务器发送确认包ACK(ack=k+1)，此包发送完毕，客户端和服务器进入ESTABLISHED状态，完成三次握手。 完成三次握手，客户端与服务器开始传送数据.
多线程同步方法
现在流行的进程线程同步互斥的控制机制，其实是由最原始最基本的4种方法实现的：
1临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。
2互斥量:为协调共同对一个共享资源的单独访问而设计的。
3信号量:为控制一个具有有限数量用户资源而设计。
4事件:用来通知线程有一些事件已发生，从而启动后继任务的开始。
临界区（Critical Section）
保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。
临界区包含两个操作原语： EnterCriticalSection（）进入临界区 LeaveCriticalSection（）离开临界区
互斥量（Mutex）
互斥量跟临界区很相似，只有拥有互斥对象的线程才具有访问资源的权限，由于互斥对象只有一个，因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出，以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。
互斥量包含的几个操作原语：
CreateMutex（）创建一个互斥量
OpenMutex（）打开一个互斥量
ReleaseMutex（）释放互斥量
WaitForMultipleObjects（）等待互斥量对象
信号量（Semaphores）
信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源，这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore（）创建信号量时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数，每增加一个线程对共享资源的访问，当前可用资源计数就会减1，只要当前可用资源计数是大于0的，就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目，不能在允许其他线程的进入，此时的信号量信号将无法发出。线程在处理完共享资源后，应在离开的同时通过ReleaseSemaphore（）函数将当前可用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。
PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用共享资源的进程数。
P操作申请资源：
（1）S减1；
（2）若S减1后仍大于等于零，则进程继续执行；
（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转入进程调度。
V操作 释放资源：
（1）S加1；
（2）若相加结果大于零，则进程继续执行；
（3）若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转入进程调度。
信号量包含的几个操作原语：
CreateSemaphore（）创建一个信号量
OpenSemaphore（）打开一个信号量
ReleaseSemaphore（）释放信号量
WaitForSingleObject（）等待信号量
事件（Event）
事件对象也可以通过通知操作的方式来保持线程的同步。并且可以实现不同进程中的线程同步操作。
总结：
1． 互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。
2． 互斥量（Mutex），信号灯（Semaphore），事件（Event）都可以被跨越进程使用来进行同步数据操作，而其他的对象与数据同步操作无关，但对于进程和线程来讲，如果进程和线程在运行状态则为无信号状态，在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和线程退出。
3． 通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号灯对象可以说是一种资源计数器。
这里有一个初学者经常混淆的概念。覆盖（override）和重载（overload）。上面说了，覆盖是指子类重新定义父类的虚函数的做法。而重载，是指允许存在多个同名函数，而这些函数的参数表不同（或许参数个数不同，或许参数类型不同，或许两者都不同）。其实，重载的概念并不属于“面向对象编程”，重载的实现是：编译器根据函数不同的参数表，对同名函数的名称做修饰，然后这些同名函数就成了不同的函数（至少对于编译器来说是这样的）。如，有两个同名函数：function func(p:integer):integer;和function
func(p:string):integer;。那么编译器做过修饰后的函数名称可能是这样的：int_func、str_func。对于这两个函数的调用，在编译器间就已经确定了，是静态的（记住：是静态）。也就是说，它们的地址在编译期就绑定了（早绑定），因此，重载和多态无关！真正和多态相关的是“覆盖”。当子类重新定义了父类的虚函数后，父类指针根据赋给它的不同的子类指针，动态（记住：是动态！）的调用属于子类的该函数，这样的函数调用在编译期间是无法确定的（调用的子类的虚函数的地址无法给出）。因此，这样的函数地址是在运行期绑定的（晚邦定）。结论就是：重载只是一种语言特性，与多态无关，与面向对象也无关！
字节对齐
其实字节对齐的细节和具体编译器实现相关，但一般而言，满足三个准则：1) 结构体变量的首地址能够被其最宽基本类型成员的大小所整除；2) 结构体每个成员相对于结构体首地址的偏移量都是成员大小的整数倍，如有需要编译器会在成员之间加上填充字节；例如上面第二个结构体变量的地址空间。3) 结构体的总大小为结构体最宽基本类型成员大小的整数倍，如有需要编译器会在最末一个成员之后加上填充字节。
五 小结与领悟
进行字节对齐的原因是因为处理器在存取内存的时候并不是一个字节一个字节操作的， 通常他会一次存取多个字节， 比如四个。所以将数据以四字节对齐方式存储能够提高数据存取效率(其实具体的存储和对齐方式没那么简单，不说了)。但是， 有时候这种默认的优化并不是我们想要的。比如在设计网络程序的时候，一般情况下我们会定义一个结构体来表示应用程协议的协议头，如果通信双方的程序是在不同体系结构的计算机编译出来的(这很有可能)，那么默认的对齐方式是有可能是不同的，这样解析出来的协议头必然就是错的。 另外即使很幸运的对齐方式一样，在协议头里面插入了几个无关的字节那也是很不优雅的何况还占用带宽。
C++笔试题 String类的实现 三大复制控制函数
分类： 著名IT笔试题 C++实现 2011-08-08 10:37 501人阅读 评论(1) 收藏 举报
#include<iostream>
using namespace std;
class String
{
friend ostream& operator<<(ostream& out,const String& str) //输出操作符重载
{
return str.Print(out);
}
public:
String(const char *str = 0);// 普通构造函数
String(const String &other); // 拷贝构造函数
~String(void) { delete [] data_; }// 析构函数
String& operator=(const String &other);// 赋值函数
char* data(void) const { return data_; }
private:
ostream& Print(ostream& out) const;
char *data_; // 用于保存字符串
};
//赋值操作符首先要注意是不是自己赋给自己，如果是这样的话什么也不做，把自己返回即可。
//其次就是别人赋值给自己，这时首先要自己把原来的值扔到，根据别人的大小开辟一块空间
//准备盛放别人的内容，最后不要忘了返回对自己的引用。
String& String::operator =(const String& other)
{
if(this!=&other)
{
delete [] data_;
size_t length=strlen(other.data());
data_=new char[length+1];
strcpy_s(data_,length+1,other.data());
}
return *this;
}
//复制构造
- 上一篇： php中字符串处理函数中最常用的6个
- 下一篇： IIS应用程序池回收图文详解
