今天复习了下一些常见的排序算法,并用c语言实现了下。代码如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX 65536 /*用于归并排序中的哨兵*/
/*简单插入排序,时间复杂度为o(n2),稳定排序，适合已经排好序的*/
void insertSort(int arr[],int len)
{
int i,j;
int key;
for(i=1;i<len;i++)
{
key=arr[i];
for(j=i-1;j>=0;j--)
{
if(arr[j]>key)
arr[j+1]=arr[j];
else
break;
}
arr[j+1]=key;
}
}
/*选择排序，时间复杂度为o(n2),不稳定排序，适合规模比较小的*/
void selectSort(int arr[],int len)
{
int i,j,temp;
for(i=0;i<len;i++)
{
for(j=i+1;j<len;j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
/*冒泡排序，时间复杂度为o(n2),稳定排序，适合规模比较小的*/
void bubbleSort(int arr[],int len)
{
int i,j,temp;
for(i=0;i<len;i++)
{
for(j=0;j<len-i-1;j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
/*合并（归并）排序,时间复杂度为o(nlogn),稳定排序，适合规模比较大的排序*/
void merge(int arr[],int p,int q,int r)
{
int *A,*B;
int n1,n2,i,j,k;
n1=q-p+1;
n2=r-q;
if((A=(int*)malloc((n1+1)*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
if((B=(int*)malloc((n2+1)*sizeof(int)))==NULL)
{
perror("malloc error");
exit(1);
}
for(i=0;i<n1;i++)
{
A[i]=arr[p+i];
}
A[i]=MAX;
for(i=0;i<n2;i++)
{
B[i]=arr[q+i+1];
}
B[i]=MAX;
i=0;j=0;
for(k=p;k<=r;k++)
{
if(A[i]>B[j])
{
arr[k]=B[j];
j++;
}else{
arr[k]=A[i];
i++;
}
}
}
void mergeSort(int arr[],int begin,int end)
{
int mid;
if(begin<end)
{
mid=(begin+end)/2;
mergeSort(arr,begin,mid);
mergeSort(arr,mid+1,end);
merge(arr,begin,mid,end);
}
}
int main()
{
int a[8]={5,2,4,7,1,3,2,6};
int b[8]={5,2,4,7,1,3,2,6};
int c[8]={5,2,4,7,1,3,2,6};
int d[8]={5,2,4,7,1,3,2,6};
int i;
/*测试插入排序*/
insertSort(a,8);
printf("after 插入排序\n");
for(i=0;i<8;i++)
{
printf("%d ",a[i]);
}
printf("\n");
/*测试选择排序*/
selectSort(b,8);
printf("after 选择排序\n");
for(i=0;i<8;i++)
{
printf("%d ",b[i]);
}
printf("\n");
/*测试冒泡排序*/
bubbleSort(c,8);
printf("after 冒泡排序\n");
for(i=0;i<8;i++)
{
printf("%d ",c[i]);
}
printf("\n");
/*测试归并排序*/
mergeSort(d,0,7);
printf("after 归并排序\n");
for(i=0;i<8;i++)
{
printf("%d ",d[i]);
}
printf("\n");
}
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*naive string-matching algorithm,T为原始字符串，P为需要匹配的字符串*/
void naiveMatch(char *T,char *P)
{
int lenT,lenP,i,j;
lenT=strlen(T);
lenP=strlen(P);
if(lenT<lenP)/*需要匹配的字符串比原始字符串还要长出错*/
{
perror("input error");
return ;
}
for(i=0;i<(lenT-lenP+1);i++)
{
for(j=0;j<lenP;j++)
{
if(T[i+j]!=P[j])
break;
}
if(j==lenP)
printf("string match at place %d\n",i);
}
}
/*kmp预处理需要的匹配串*/
void getNext(char *p,int next[])
{
int len,i,j;
len=strlen(p);
next[0]=0;
for(i=1;i<len;i++)
{
j=next[i-1];
while((p[i-1]!=p[j-1])&&(j!=0))
{
j=next[j-1];
// printf("j= %d\n",j);
}
next[i]=j+1;
printf("next[i]=%d\n",next[i]);
}
}
/*kmp字符串匹配算法*/
void kmp(char *t,char *p,int next[])
{
int lent,lenp,i,j;
lent=strlen(t);
lenp=strlen(p);
i=0;
j=0;
while(i<(lent))
{
if((j==-1)||(t[i]==p[j]))
{
i++;
j++;
// printf("i=%d,j=%d\n",i,j);
}
else
{
// printf("in else i=%d,j=%d\n",i,j);
j=next[j]-1;
}
if(j==(lenp))
{
printf("match at place %d\n",i-lenp);
}
}
}
int main()
{
char p[10]="0001";
char t[20]="000010001010001";
naiveMatch(t,p);/*测试普通字符串匹配算法*/
char p1[10]="abaabcac";
char t1[20]="acabaabaabcacaabc";
int len=strlen(p1);
int *next;
next=(int*)malloc(sizeof(int)*len);
getNext(p1,next);
kmp(t1,p1,next);/*测试kmp算法*/
getNext(p,next);
kmp(t,p,next);/*测试kmp算法*/
}
在linux的网络编程中，很长的时间都在使用select来做事件触发。在linux新的内核中，有了一种替换它的机制，就是epoll。
相比于select，epoll最大的好处在于它不会随着监听fd数目的增长而降低效率。因为在内核中的select实现中，它是采用轮询来处理的，轮询的fd数目越多，自然耗时越多。并且，在linux/posix_types.h头文件有这样的声明：
#define __FD_SETSIZE 1024
表示select最多同时监听1024个fd，当然，可以通过修改头文件再重编译内核来扩大这个数目，但这似乎并不治本。
epoll的接口非常简单，一共就三个函数：
1. int epoll_create(int size);
创
建一个epoll的句柄，size用来告诉内核这个监听的数目一共有多大。这个参数不同于select()中的第一个参数，给出最大监听的fd+1的值。
需要注意的是，当创建好epoll句柄后，它就是会占用一个fd值，在linux下如果查看/proc/进程id/fd/，是能够看到这个fd的，所以在
使用完epoll后，必须调用close()关闭，否则可能导致fd被耗尽。
2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
epoll的事件注册函数，它不同与select()是在监听事件时告诉内核要监听什么类型的事件，而是在这里先注册要监听的事件类型。第一个参数是epoll_create()的返回值，第二个参数表示动作，用三个宏来表示：
EPOLL_CTL_ADD：注册新的fd到epfd中；
EPOLL_CTL_MOD：修改已经注册的fd的监听事件；
EPOLL_CTL_DEL：从epfd中删除一个fd；
第三个参数是需要监听的fd，第四个参数是告诉内核需要监听什么事，struct epoll_event结构如下：
struct epoll_event {
__uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};
events可以是以下几个宏的集合：
EPOLLIN ：表示对应的文件描述符可以读（包括对端SOCKET正常关闭）；
EPOLLOUT：表示对应的文件描述符可以写；
EPOLLPRI：表示对应的文件描述符有紧急的数据可读（这里应该表示有带外数据到来）；
EPOLLERR：表示对应的文件描述符发生错误；
EPOLLHUP：表示对应的文件描述符被挂断；
EPOLLET： 将EPOLL设为边缘触发(Edge Triggered)模式，这是相对于水平触发(Level Triggered)来说的。
EPOLLONESHOT：只监听一次事件，当监听完这次事件之后，如果还需要继续监听这个socket的话，需要再次把这个socket加入到EPOLL队列里
3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
等
待事件的产生，类似于select()调用。参数events用来从内核得到事件的集合，maxevents告之内核这个events有多大，这个
maxevents的值不能大于创建epoll_create()时的size，参数timeout是超时时间（毫秒，0会立即返回，-1将不确定，也有
说法说是永久阻塞）。该函数返回需要处理的事件数目，如返回0表示已超时。
--------------------------------------------------------------------------------------------
从man手册中，得到ET和LT的具体描述如下
EPOLL事件有两种模型：
Edge Triggered (ET)
Level Triggered (LT)
假如有这样一个例子：
1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符
2. 这个时候从管道的另一端被写入了2KB的数据
3. 调用epoll_wait(2)，并且它会返回RFD，说明它已经准备好读取操作
4. 然后我们读取了1KB的数据
5. 调用epoll_wait(2)......
Edge Triggered 工作模式：
如
果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志，那么在第5步调用epoll_wait(2)之后将有可能会挂起，因为剩
余的数据还存在于文件的输入缓冲区内，而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET
工作模式才会汇报事件。因此在第5步的时候，调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。在上面的例子中，会有一个事件产生在RFD句柄
上，因为在第2步执行了一个写操作，然后，事件将会在第3步被销毁。因为第4步的读取操作没有读空文件输入缓冲区内的数据，因此我们在第5步调用
epoll_wait(2)完成后，是否挂起是不确定的。epoll工作在ET模式的时候，必须使用非阻塞套接口，以避免由于一个文件句柄的阻塞读/阻塞
写操作把处理多个文件描述符的任务饿死。最好以下面的方式调用ET模式的epoll接口，在后面会介绍避免可能的缺陷。
i 基于非阻塞文件句柄
ii 只有当read(2)或者write(2)返回EAGAIN时才需要挂起，等待。但这并不是说每次read()时都需要循环读，直到读到产生一个EAGAIN才认为此次事件处理完成，当read()返回的读到的数据长度小于请求的数据长度时，就可以确定此时缓冲中已没有数据了，也就可以认为此事读事件已处理完成。
Level Triggered 工作模式
相
反的，以LT方式调用epoll接口的时候，它就相当于一个速度比较快的poll(2)，并且无论后面的数据是否被使用，因此他们具有同样的职能。因为即
使使用ET模式的epoll，在收到多个chunk的数据的时候仍然会产生多个事件。调用者可以设定EPOLLONESHOT标志，在
epoll_wait(2)收到事件后epoll会与事件关联的文件句柄从epoll描述符中禁止掉。因此当EPOLLONESHOT设定后，使用带有
EPOLL_CTL_MOD标志的epoll_ctl(2)处理文件句柄就成为调用者必须作的事情。
然后详细解释ET, LT:
LT(level
triggered)是缺省的工作方式，并且同时支持block和no-block
socket.在这种做法中，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作，内核还是会继续通知你
的，所以，这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表．
ET(edge-triggered)
是高速工作方式，只支持no-block
socket。在这种模式下，当描述符从未就绪变为就绪时，内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪，并且不会再为那个文件描述
符发送更多的就绪通知，直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如，你在发送，接收或者接收请求，或者发送接收的数据少于一定量时导致
了一个EWOULDBLOCK 错误）。但是请注意，如果一直不对这个fd作IO操作(从而导致它再次变成未就绪)，内核不会发送更多的通知(only
once),不过在TCP协议中，ET模式的加速效用仍需要更多的benchmark确认（这句话不理解）。
在
许多测试中我们会看到如果没有大量的idle
-connection或者dead-connection，epoll的效率并不会比select/poll高很多，但是当我们遇到大量的idle-
connection(例如WAN环境中存在大量的慢速连接)，就会发现epoll的效率大大高于select/poll。（未测试）
另外，当使用epoll的ET模型来工作时，当产生了一个EPOLLIN事件后，
读数据的时候需要考虑的是当recv()返回的大小如果等于请求的大小，那么很有可能是缓冲区还有数据未读完，也意味着该次事件还没有处理完，所以还需要再次读取
：
while(rs)
{
buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);
if(buflen < 0)
{
// 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读
// 在这里就当作是该次事件已处理处.
if(errno == EAGAIN)
break;
else
return;
}
else if(buflen == 0)
{
// 这里表示对端的socket已正常关闭.
}
if(buflen == sizeof(buf)
rs = 1; // 需要再次读取
else
rs = 0;
}
还
有，假如发送端流量大于接收端的流量(意思是epoll所在的程序读比转发的socket要快),由于是非阻塞的socket,那么send()函数虽然
返回,但实际缓冲区的数据并未真正发给接收端,这样不断的读和发，当缓冲区满后会产生EAGAIN错误(参考man
send),同时,不理会这次请求发送的数据.所以,需要封装socket_send()的函数用来处理这种情况,该函数会尽量将数据写完再返回，返回
-1表示出错。在socket_send()内部,当写缓冲已满(send()返回-1,且errno为EAGAIN),那么会等待后再重试.这种方式并
不很完美,在理论上可能会长时间的阻塞在socket_send()内部,但暂没有更好的办法.
ssize_t socket_send(int sockfd, const char* buffer, size_t buflen)
{
ssize_t tmp;
size_t total = buflen;
const char *p = buffer;
while(1)
{
tmp = send(sockfd, p, total, 0);
if(tmp < 0)
{
// 当send收到信号时,可以继续写,但这里返回-1.
if(errno == EINTR)
return -1;
// 当socket是非阻塞时,如返回此错误,表示写缓冲队列已满,
// 在这里做延时后再重试.
if(errno == EAGAIN)
{
usleep(1000);
continue;
}
return -1;
}
if((size_t)tmp == total)
return buflen;
total -= tmp;
p += tmp;
}
return tmp;
}
epoll有两种模式,Edge Triggered(简称ET) 和 Level
Triggered(简称LT).在采用这两种模式时要注意的是,如果采用ET模式,那么仅当状态发生变化时才会通知,而采用LT模式类似于原来的
select/poll操作,只要还有没有处理的事件就会一直通知.
以代码来说明问题:
首先给出server的代码,需要说明的是每次accept的连接,加入可读集的时候采用的都是ET模式,而且接收缓冲区是5字节的,也就是每次只接收5字节的数据:
#include
<
iostream
>
#include
<
sys
/
socket.h
>
#include
<
sys
/
epoll.h
>
#include
<
netinet
/
in.h
>
#include
<
arpa
/
inet.h
>
#include
<
fcntl.h
>
#include
<
unistd.h
>
#include
<
stdio.h
>
#include
<
errno.h
>
using namespace std;
#define MAXLINE
5
#define OPEN_MAX
100
#define LISTENQ
20
#define SERV_PORT
5000
#define INFTIM
1000
void setnonblocking(
int
sock)
{
int
opts;
opts
=
fcntl(sock,F_GETFL);
if
(opts
<
0
)
{
perror(
"
fcntl(sock,GETFL)
"
);
exit
(
1
);
}
opts
=
opts|O_NONBLOCK;
if
(fcntl(sock,F_SETFL,opts)
<
0
)
{
perror(
"
fcntl(sock,SETFL,opts)
"
);
exit
(
1
);
}
}
int
main()
{
int
i, maxi, listenfd, connfd, sockfd,epfd,nfds;
ssize_t n;
char line[MAXLINE];
socklen_t clilen;
//
声明epoll_event结构体的变量,ev用于注册事件,数组用于回传要处理的事件
struct epoll_event ev,events[
20
];
//
生成用于处理accept的epoll专用的文件描述符
epfd
=
epoll_create(
256
);
struct sockaddr_in clientaddr;
struct sockaddr_in serveraddr;
listenfd
=
socket(AF_INET, SOCK_STREAM,
0
);
//
把socket设置为非阻塞方式
//
setnonblocking(listenfd);
//
设置与要处理的事件相关的文件描述符
ev.data.fd
=
listenfd;
//
设置要处理的事件类型
ev.events
=
EPOLLIN|EPOLLET;
//
ev.events
=
EPOLLIN;
//
注册epoll事件
epoll_ctl(epfd,EPOLL_CTL_ADD,listenfd,
&
ev);
bzero(
&
serveraddr, sizeof(serveraddr));
serveraddr.sin_family
=
AF_INET;
char
*
local_addr
=
"
127.0.0.1
"
;
inet_aton(local_addr,
&
(serveraddr.sin_addr));
//
htons(SERV_PORT);
serveraddr.sin_port
=
htons(SERV_PORT);
bind(listenfd,(sockaddr
*
)
&
serveraddr, sizeof(serveraddr));
listen(listenfd, LISTENQ);
maxi
=
0
;
for
( ; ; ) {
//
等待epoll事件的发生
nfds
=
epoll_wait(epfd,events,
20
,
500
);
//
处理所发生的所有事件
for
(i
=
0
;i
<
nfds;
++
i)
{
if
(events[i].data.fd
==
listenfd)
{
clilen=sizeof(struct sockaddr);
connfd
=
accept(listenfd,(struct sockaddr
*
)
&
clientaddr,
&
clilen);
if
(connfd
<
0
){
perror(
"
connfd<0
"
);
exit
(
1
);
}
//
setnonblocking(connfd);
char
*
str
=
inet_ntoa(clientaddr.sin_addr);
cout
<<
"
accapt a connection from
"
<<
str
<<
endl;
//
设置用于读操作的文件描述符
ev.data.fd
=
connfd;
//
设置用于注测的读操作事件
ev.events
=
EPOLLIN|EPOLLET;
//
ev.events
=
EPOLLIN;
//
注册ev
epoll_ctl(epfd,EPOLL_CTL_ADD,connfd,
&
ev);
}
else
if
(events[i].events
&
EPOLLIN)
{
cout
<<
"
EPOLLIN
"
<<
endl;
if
( (sockfd
=
events[i].data.fd)
<
0
)
continue;
if
( (n
=
read(sockfd, line, MAXLINE))
<
0
) {
if
(errno
==
ECONNRESET) {
close(sockfd);
events[i].data.fd
=
-
1
;
}
else
std::cout
<<
"
readline error
"
<<
std::endl;
}
else
if
(n
==
0
) {
close(sockfd);
events[i].data.fd
=
-
1
;
}
line[n]
=
'
\0';
cout
<<
"
read
"
<<
line
<<
endl;
//
设置用于写操作的文件描述符
ev.data.fd
=
sockfd;
//
设置用于注测的写操作事件
ev.events
=
EPOLLOUT|EPOLLET;
//
修改sockfd上要处理的事件为EPOLLOUT
//
epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd,
&
ev);
}
else
if
(events[i].events
&
EPOLLOUT)
{
sockfd
=
events[i].data.fd;
write(sockfd, line, n);
//
设置用于读操作的文件描述符
ev.data.fd
=
sockfd;
//
设置用于注测的读操作事件
ev.events
=
EPOLLIN|EPOLLET;
//
修改sockfd上要处理的事件为EPOLIN
epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd,
&
ev);
}
}
}
return
0
;
}
下面给出测试所用的Perl写的client端,在client中发送10字节的数据,同时让client在发送完数据之后进入死循环, 也就是在发送完之后连接的状态不发生改变--既不再发送数据, 也不关闭连接,这样才能观察出server的状态:
#!
/
usr
/
bin
/
perl
use IO::Socket;
my $host
=
"
127.0.0.1
"
;
my $port
=
5000
;
my $socket
=
IO::Socket::INET
->
new
(
"
$host:$port
"
)
or
die
"
create socket error $@
"
;
my $msg_out
=
"
1234567890
"
;
print $socket $msg_out;
print
"
now send over, go to sleep
\n
"
;
while
(
1
)
{
sleep(
1
);
}
运行server和client发现,server仅仅读取了5字节的数据,而client其实发送了10字节的数据,也就是说,server仅当第一次
监听到了EPOLLIN事件,由于没有读取完数据,而且采用的是ET模式,状态在此之后不发生变化,因此server再也接收不到EPOLLIN事件了.
(友情提示:上面的这个测试客户端,当你关闭它的时候会再次出发IO可读事件给server,此时server就会去读取剩下的5字节数据了,但是这一事件与前面描述的ET性质并不矛盾.)
如果我们把client改为这样:
#!
/
usr
/
bin
/
perl
use IO::Socket;
my $host
=
"
127.0.0.1
"
;
my $port
=
5000
;
my $socket
=
IO::Socket::INET
->
new
(
"
$host:$port
"
)
or
die
"
create socket error $@
"
;
my $msg_out
=
"
1234567890
"
;
print $socket $msg_out;
print
"
now send over, go to sleep
\n
"
;
sleep(
5
);
print
"
5 second gone
send another line\n
"
;
print $socket $msg_out;
while
(
1
)
{
sleep(
1
);
}
可以发现,在server接收完5字节的数据之后一直监听不到client的事件,而当client休眠5秒之后重新发送数据,server再次监听到了变化,只不过因为只是读取了5个字节,仍然有10个字节的数据(client第二次发送的数据)没有接收完.
如果上面的实验中,对accept的socket都采用的是LT模式,那么只要还有数据留在buffer中,server就会继续得到通知,读者可以自行改动代码进行实验.
基
于这两个实验,可以得出这样的结论:ET模式仅当状态发生变化的时候才获得通知,这里所谓的状态的变化并不包括缓冲区中还有未处理的数据,也就是说,如果
要采用ET模式,需要一直read/write直到出错为止,很多人反映为什么采用ET模式只接收了一部分数据就再也得不到通知了,大多因为这样;而LT
模式是只要有数据没有处理就会一直通知下去的.
补充说明一下这里一直强调的"状态变化"是什么:
1)对于监听可读事件时,如果是socket是监听socket,那么当有新的主动连接到来为状态发生变化;对一般的socket而言,协议栈中相应的缓
冲区有新的数据为状态发生变化.但是,如果在一个时间同时接收了N个连接(N>1),但是监听socket只accept了一个连接,那么其它未
accept的连接将不会在ET模式下给监听socket发出通知,此时状态不发生变化;对于一般的socket,就如例子中而言,如果对应的缓冲区本身
已经有了N字节的数据,而只取出了小于N字节的数据,那么残存的数据不会造成状态发生变化.
2)对于监听可写事件时,同理可推,不再详述.
而不论是监听可读还是可写,对方关闭socket连接都将造成状态发生变化,比如在例子中,如果强行中断client脚本,也就是主动中断了socket连接,那么都将造成server端发生状态的变化,从而server得到通知,将已经在本方缓冲区中的数据读出.
把前面的描述可以总结如下:仅当对方的动作(发出数据,关闭连接等)造成的事件才能导致状态发生变化,而本方协议栈中已经处理的事件(包括接收了对方的数
据,接收了对方的主动连接请求)并不是造成状态发生变化的必要条件,状态变化一定是对方造成的.所以在ET模式下的,必须一直处理到出错或者完全处理完
毕,才能进行下一个动作,否则可能会发生错误.
另外,从这个例子中,也可以阐述一些基本的网络编程概念.首先,连接的两端中,一端发送成功并不代表着对方上层应用程序接收成功,
就拿上面的client测试程序来说,10字节的数据已经发送成功,但是上层的server并没有调用read读取数据,因此发送成功仅仅说明了数据被对
方的协议栈接收存放在了相应的buffer中,而上层的应用程序是否接收了这部分数据不得而知;同样的,读取数据时也只代表着本方协议栈的对应
buffer中有数据可读,而此时时候在对端是否在发送数据也不得而知.
给定九个数，例如：1，3，3，5，6，7，8，8，9计算出这九个数的排列的种数。需要考虑重复情况，如果给定9个1，则只有一种结果。
限制：不能使用stl库
要求：完成函数 unsigned int foo(unsigned int *arr);
输入算法代码，并给出算法复杂度分析。
分析：
#include <cstdlib>
#include <iostream>
using namespace std;
unsigned int foo(unsigned int *arr)
{
unsigned int p[] ={1,2,6,24,120,720,5040,40320,362880};
unsigned int i,j,c,s=p[8];//first the number is p99
for(i = 0; i < 7; i++)
for(j = i+1; j < 8; j++)
{
if(arr[i]>arr[j]) //swap two number
{
arr[i]^=arr[j];
arr[j]^=arr[i];
arr[i]^=arr[j];
}
}
i = 0;
c = 0;
while(i<8)
{
j = i+1;
while(arr[i]==arr[j])//compute the number of the repetition
{
c++;
j++;
}
s/=p[c];
c=0;
i=j;
}
return s;
}
int main()
{
unsigned int a[]={1,3,3,5,6,7,8,8,9};
cout<<"The number of permutation is: "<<foo(a)<<endl;
system("pause");
return 0;
}
还可以改进排序那部分。
转一个经典的题目：
给一个天平,问如何用3次把这个小球找出来
并且求出这个小球是比其他的轻还是重
将12个球分别编号为a1,a2,a3.......a10,a11,a12.
第一步：将12球分开3拨，每拨4个，a1~a4第一拨，记为b1， a5~a8第2拨，记为b2，其余第3拨，记为b3；
第二步：将b1和b2放到天平两盘上，记左盘为c1，右为c2；这时候分两中情况：
1.c1和c2平衡，此时可以确定从a1到a8都是常球；然后把c2拿空，并从c1上拿下a4，从a9到a12四球里随便取三球，假设为a9到a11，放到c2上。此时c1上是a1到a3，c2上是a9到a11。从这里又分三种情况：
A：天平平衡，很简单，说明没有放上去的a12就是异球，而到此步一共称了两次，所以将a12随便跟11个常球再称一次，也就是第三次，马上就可以确定a12是重还是轻；
B：
若c1上升，则这次称说明异球为a9到a11三球中的一个，而且是比常球重。取下c1所有的球，并将a8放到c1上，将a9取下，比较a8和a11（第三
次称），如果平衡则说明从c2上取下的a9是偏重异球，如果不平衡，则偏向哪盘则哪盘里放的就是偏重异球；
C：若c1下降，说明a9到a11里有一个是偏轻异球。次种情况和B类似，所以接下来的步骤照搬B就是；
2.c1和c2不平衡，这时候又分两种情况，c1上升和c1下降，但是不管哪种情况都能说明a9到a12是常球。这步是解题的关键。也是这个题最妙的地方。
A：c1上升，此时不能判断异球在哪盘也不能判断是轻还是重。取下c1中的a2到a4三球放一边，将c2中的a5和a6放到c1上，然后将常球a9放到c2上。至此，c1上是a1，a5和a6，c2上是a7，a8和a9。此时又分三中情况：
1）
如果平衡，说明天平上所有的球都是常球，异球在从c1上取下a2到a4中。而且可以断定异球轻重。因为a5到a8都是常球，而第2次称的时候c1是上升
的，所以a2到a4里必然有一个轻球。那么第三次称就用来从a2到a4中找到轻球。这很简单，随便拿两球放到c1和c2，平衡则剩余的为要找球，不平衡则
哪边低则哪个为要找球；
2）c1仍然保持上升，则说明要么a1是要找的轻球，要么a7和a8两球中有一个是重球（这步懂吧？
好好想想，很简单的。因为a9是常球，而取下的a2到a4肯定也是常球，还可以推出换盘放置的a5和a6也是常球。所以要么a1轻，要么a7或a8重）。
至此，还剩一次称的机会。只需把a7和a8放上两盘，平衡则说明a1是要找的偏轻异球，如果不平衡，则哪边高说明哪个是偏重异球；
3）如果换球称第2次后天平平衡打破，并且c1降低了，这说明异球肯定在换过来的a5和a6两求中，并且异球偏重，否则天平要么平衡要么保持c1上升。确定要找球是偏重之后，将a5和a6放到两盘上称第3次根据哪边高可以判定a5和a6哪个是重球；
B：
第1次称后c1是下降的，此时可以将c1看成c2，其实以后的步骤都同A，所以就不必要再重复叙述了。至此，不管情况如何，用且只用三次就能称出12个外
观手感一模一样的小球中有质量不同于其他11球的偏常的球。而且在称的过程中可以判定其是偏轻还是偏重。
3.U2 合唱团在17
分钟内得赶到演唱会场，途中必需跨过一座桥，四个人从桥的同一端出发，你得帮助他们到达另一端，天色很暗，而他们只有一只手电筒。一次同时最多可以有两人
一起过桥，而过桥的时候必须持有手电筒，所以就得有人把手电筒带来带去，来回桥两端。手电筒是不能用丢的方式来传递的。四个人的步行速度各不同，若两人同
行则以较慢者的速度为准。Bono 需花1 分钟过桥，Edge 需花2 分钟过桥，Adam需花 5 分钟过桥，Larry 需花10
分钟过桥。他们要如何在17
分钟内过桥呢？（有个同济的学生写文章说他当时在微软面试时就是碰到了这道题，最短只能做出在19分钟内过桥，微软的人对他讲这样的结果已经是不错的
了！）
A点到 B 点
1 和2 过去 2 分钟 2
2 过来 4 分钟 2+2=4
10和 5过去 14 分钟 4+10=14
1 过来 15 分钟 14+1=15
1 和2 过去 17 分钟 15+2=17
第一组
1.烧一根不均匀的绳，从头烧到尾总共需要1个小时。现在有若干条材质相同的绳子，问如何用烧绳的方法来计时一个小时十五分钟呢?
ans:三根绳，开始的时候，第一根点燃两端，第二根点燃一端，第三根不点。第一根绳烧完(30分钟)后，点燃第二根绳的另一端，第二根只要15分钟就可以烧完了，第二根绳烧完(45分钟)后，点燃第三根绳子两端，第三根绳烧完(1小时15分)后，计时完成
2.你有一桶果冻，其中有黄色、绿色、红色三种，闭上眼睛抓取同种颜色的两个。抓取多少个就可以确定你肯定有两个同一颜色的果冻?
3.如果你有无穷多的水，一个3公升的提捅，一个5公升的提捅，两只提捅形状上下都不均匀，问你如何才能准确称出4公升的水?
4.一个岔路口分别通向诚实国和说谎国。来了两个人，已知一个是诚实国的，另一个是说谎国的。诚实国永远说实话，说谎国永远说谎话。现在你要去说谎国，但不知道应该走哪条路，需要问这两个人。请问应该怎么问?
5.12个球一个天平，现知道只有一个和其它的重量不同，问怎样称才能用三次就找到那个球。13个呢?(注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑)
6.在9个点上画10条直线，要求每条直线上至少有三个点?
7.在一天的24小时之中，时钟的时针、分针和秒针完全重合在一起的时候有几次?都分别是什么时间?你怎样算出来的?
8.怎么样种植4棵树木，使其中任意两棵树的距离相等?
第二组
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个蓝色弹球，随机选出一个罐子， 随机选出一个弹球放入罐子，怎么给出红色弹球最大的选中机会?在你的计划里，得到红球的几率是多少?
7.给你两颗6面色子，可以在它们各个面上刻上0-9任意一个数字，要求能够用它们拼出任意一年中的日期数值
第四组
第一题 . 五个海盗抢到了100颗宝石，每一颗都一样大小和价值连城。他们决定这么分：
抽签决定自己的号码(1、2、3、4、5)
首先，由1号提出分配方案，然后大家表决，当且仅当超过半数的人同意时，按照他的方案
进行分配，否则将被扔进大海喂鲨鱼
如果1号死后，再由2号提出分配方案，然后剩下的4人进行表决，当且仅当超过半数的人同
意时，按照他的方案进行分配，否则将被扔入大海喂鲨鱼
依此类推
条件：每个海盗都是很聪明的人，都能很理智地做出判断，从而做出选择。
问题：第一个海盗提出怎样的分配方案才能使自己的收益最大化?
第二题 . 一道关于飞机加油的问题，已知：
每个飞机只有一个油箱，
飞机之间可以相互加油(注意是相互，没有加油机)
一箱油可供一架飞机绕地球飞半圈，
问题：
为使至少一架飞机绕地球一圈回到起飞时的飞机场，至少需要出动几架飞机?(所有飞机从同一机场起飞，而且必须安全返回机场，不允许中途降落，中间没有飞机场)第三题. 汽车加油问题
一辆载油500升的汽车从A开往1000公里外的B，已知汽车每公里耗油量为1升，A处有无穷多的油，其他任何地点都没有油，但该车可以在任何地点存放油以备中转，问从A到B最少需要多少油
第四题. 掷杯问题
一种杯子，若在第N层被摔破，则在任何比N高的楼层均会破，若在第M层不破，则在任何比M低的楼层均会破，给你两个这样的杯子，让你在100层高的楼层中测试，要求用最少的测试次数找出恰巧会使杯子破碎的楼层。
第五题. 推理游戏
教授选出两个从2到9的数，把它们的和告诉学生甲，把它们的积告诉学生乙，让他们轮流猜这两个数
甲说：“我猜不出”
乙说：“我猜不出”
甲说：“我猜到了”
乙说：“我也猜到了”
问这两个数是多少
第六题. 病狗问题
一个住宅区内有100户人家，每户人家养一条狗，每天傍晚大家都在同一个地方遛狗。已知这些狗中有一部分病狗，由于某种原因，狗的主人无法判断自己的狗
是否是病狗，却能够分辨其他的狗是否有病，现在，上级传来通知，要求住户处决这些病狗，并且不允许指认他人的狗是病狗(就是只能判断自己的)，过了7天之
后，所有的病狗都被处决了，问，一共有几只病狗?为什么?
第八题. 监狱里有100个房间，每个房间内有一囚犯。一天，监狱长说，你
们狱房外有一电灯，你们在放风时可以控制这个电灯(熄或亮)。每天只能有一个人出来放风，并且防风是随机的。如果在有限时间内，你们中的某人能对我说：
“我敢保证，现在每个人都已经至少放过一次风了。”我就放了你们!问囚犯们要采取什么策略才能被监狱长放掉?如果采用了这种策略，大致多久他们可以被释
放?
第五组
1.某手机厂家由于设计失误，有可能造成电池寿命比原来设计的寿命短一半(不是冲放电时间)，解决方案就是免费更换电池或给50元购买该厂家新手机的折换券。请给所有已购买的用户写信告诉解决方案。
2.一高层领导在参观某博物馆时，向博物馆馆员小王要了一块明代的城砖作为纪念，按国家规定，任何人不得将博物馆收藏品变为私有。博物馆馆长需要如何写信给这位领导，将城砖取回。
3.营业员小姐由于工作失误，将2万元的笔记本电脑以1.2万元错卖给李先生，王小姐的经理怎么写信给李先生试图将钱要回来?
4.给你一款新研制的手机，如果你是测试组的组长，你会如何测试?
5.如何为函数int atoi(const char * pstr)编写测试向量?
第六组
1.链表和数组的区别在哪里?
2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法?
3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法?
4.请编写能直接实现char * strcpy(char * pstrDest,const char * pstrSource)函数功能的代码。
5.编写反转字符串的程序，要求优化速度、优化空间。
6.在链表里如何发现循环链接?
7.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
8.写一个函数，检查字符是否是整数，如果是，返回其整数值。(或者：怎样只用4行代码
9.给出一个函数来输出一个字符串的所有排列。
10.请编写实现void * malloc(int)内存分配函数功能一样的代码。
11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
12.怎样编写一个程序，把一个有序整数数组放到二叉树中?
13.怎样从顶部开始逐层打印二叉树结点数据?请编程。
14.怎样把一个链表掉个顺序(也就是反序，注意链表的边界条件并考虑空链表)? --
15.请编写能直接实现int atoi(const char * pstr)函数功能的代码
-----------------------------------------------------------------------------------
第一组题答案：
2)根据抽屉原理，4个
3)3升装满;3升-〉5升(全注入);3升装满;3升-〉5升(剩1升);5升倒掉;3升-〉5升(注入1升);3升装满;3升-〉5升;完成(另：可用回溯法编程求解)
4)问其中一人：另外一个人会说哪一条路是通往诚实国的?回答者所指的那条路必然是通往说谎国的。
5)12个球：
第一次：4，4 如果平了：
那么剩下的球中取3放左边,取3个好球放右边，称：
如果左边重，那么取两个球称一下，哪个重哪个是次品，平的话第三个重，是次品，轻的话同理
如果平了，那么剩下一个次品，还可根据需要称出次品比正品轻或者重
如果不平：
那么不妨设左边重右边轻，为了便于说明，将左边4颗称为重球，右边4颗称为轻球，剩下4颗称为好球
取重球2颗，轻球2颗放在左侧，右侧放3颗好球和一颗轻球
如果左边重
称那两颗重球，重的一个次品，平的话右边轻球次品
如果右边重
称左边两颗轻球，轻的一个次品
如果平
称剩下两颗重球，重的一个次品，平的话剩下那颗轻球次品
13个球：
第一次：4，4，如果平了
剩5颗球用上面的方法仍旧能找出次品，只是不能知道次品是重是轻
如果不平，同上
6)
o o o
o o o
o o o
7)
23次，因为分针要转24圈，时针才能转1圈，而分针和时针重合两次之间的间隔显然>1小时，它们有23次重合机会，每次重合中秒针有一次重合机会，所以是23次
重合时间可以对照手表求出，也可列方程求出
8)
在地球表面种树，做一个地球内接的正四面体，内接点即为所求
第二组 无标准答案
第三组
1. 分成1,2,4三段，第一天给1，第二天给2取回1，第3天给1，第4天给4取回1、2，第5天给1，第6天给2取回1，第七天给1
2. 求出火车相遇时间，鸟速乘以时间就是鸟飞行的距离
3. 四个罐子中分别取1,2,3,4颗药丸，称出比正常重多少，即可判断出那个罐子的药被污染
4. 三个开关分别：关，开，开10分钟，然后进屋，暗且凉的为开关1控制的灯，亮的为开关2控制的灯，暗且热的为开关3控制的灯
5. 因为可以用1，2，5，10组合成任何需要的货币值，日常习惯为10进制
6. 题意不理解...*_*
7. 012345 0126(9)78
第四组 都是很难的题目
第一题：97 0 1 2 0 或者 97 0 1 0 2 (提示：可用逆推法求出)
第二题：3架飞机5架次，飞法：
ABC 3架同时起飞，1/8处，C给AB加满油，C返航，1/4处，B给A加满油，B返航，A到达1/2处，C从机场往另一方向起飞，3/4处，C同
已经空油箱的A平分剩余油量，同时B从机场起飞，AC到7/8处同B平分剩余油量，刚好3架飞机同时返航。所以是3架飞机5架次。第三题：需要建立数学模
型
(提示，严格证明该模型最优比较麻烦，但确实可证，大胆猜想是解题关键)
题目可归结为求数列 an=500/(2n+1) n=0,1,2,3......的和Sn什么时候大于等于1000,解得n>6
当n=6时，S6=977.57
所以第一个中转点离起始位置距离为1000-977.57=22.43公里
所以第一次中转之前共耗油 22.43*(2*7+1)=336.50升
此后每次中转耗油500升
所以总耗油量为7*500+336.50=3836.50升
第四题：需要建立数学模型
题目可归结为求自然数列的和S什么时候大于等于100，解得n>13
第一个杯子可能的投掷楼层分别为：14，27，39，50，60，69，77，84，90，95，99，100
第五题：3和4(可严格证明)
设两个数为n1，n2，n1>=n2，甲听到的数为n=n1+n2，乙听到的数为m=n1*n2
证明n1=3，n2=4是唯一解
证明：要证以上命题为真，不妨先证n=7
1)必要性：
i) n>5 是显然的，因为n<4不可能，n=4或者n=5甲都不可能回答不知道
ii) n>6 因为如果n=6的话，那么甲虽然不知道(不确定2+4还是3+3)但是无论是2，4还是3，3乙都不可能说不知道(m=8或者m=9的话乙说不知道是没有道理的)
iii) n<8 因为如果n>=8的话，就可以将n分解成 n=4+x 和 n=6+(x-2)，那么m可以是4x也可以是6(x-2)
而4x=6(x-2)的必要条件是x=6即n=10，那样n又可以分解成8+2，所以总之当n>=8时，n至少可以分解成两种不同的合数之和，这样
乙说不知道的时候，甲就没有理由马上说知道。
以上证明了必要性
2)充分性
当n=7时，n可以分解成2+5或3+4
显然2+5不符合题意，舍去，容易判断出3+4符合题意，m=12，证毕
于是得到n=7 m=12 n1=3 n2=4是唯一解。第六题：7只(数学归纳法证明)
1)若只有1只病狗，因为病狗主人看不到有其他病狗，必然会知道自己的狗是病狗(前提是一定存在病狗)，所以他会在第一天把病狗处决。
2)设有k只病狗的话，会在第k天被处决，那么，如果有k+1只，病狗的主人只会看到k只病狗，而第k天没有人处决病狗，病狗主人就会在第k+1天知道自己的狗是病狗，于是病狗在第k+1天被处决
3)由1)2)得，若有n只病狗，必然在第n天被处决
第八题：
约定好一个人作为报告人(可以是第一个放风的人)
规则如下：
1、报告人放风的时候开灯并数开灯次数
2、其他人第一次遇到开着灯放风时，将灯关闭
3、当报告人第100次开灯的时候，去向监狱长报告，要求监狱长放人......
按照概率大约30年后(10000天)他们可以被释放
第五组无标准答案
第六组部分题参考答案：
4.
char * strcpy(char * pstrDest,const char * pstrSource)
{
assert((pstrDest!=NULL)&&(pstrSource!=NULL));
char * pstr=pstrDest;
while((*(pstrDest++)=*(pstrSource++))!='\0');
return pstr;
}
5.
char * strrev(char * pstr)
{
assert(pstr!=NULL);
char * p=pstr;
char * pret=pstr;
while(*(p++)!='\0');
p--;
char tmp;
while(p>pstr)
{
tmp=*p;
*(p--)=*(pstr);
*(pstr++)=tmp;
}
return pret;
百度笔试题：
IP段格式:ip1 ip2。之间以空格分开，ip形式为X.X.X.X，数据保存在文件中，文件不超过2k行，无序。现在要求编写算法去掉可重IP，可重有三种形式：包含、交叠、紧靠。
例如，文件内容为：
10.0.0.0 10.0.0.12
10.0.0.5 10.0.0.10 ( <= 包含)
10.0.0.8 10.0.0.15 ( <= 交叠)
10.0.0.15 10.0.0.24 ( <= 紧靠)
最后输出为:
10.0.0.0 10.0.0.24
code：
/*
**这个函数的作用是将文件中的一行对应的两个数据转换成整形的数据
**比如把10.0.0.0 10.0.0.12 转换后，left=10*224,就是10.0.0.0对应的整数，每个数字对应8位，right=left+12
*/
void ParseLine( char line[], size_t length, unsigned int &left, unsigned int &right)
{
size_t i;
for( i=0; i<length; i++ )
{
if ( line[i]=='.' || line[i]==' ' )//将点变成0
{
line[i]=0;
}
}
char *p = (char*)&left;
char *num = line;
for( i=3; i<4; --i ) //size是size_t，而size_t是unsigned int，所以i=0再自减后变成了最大的整数，循环就会终止
{
// cout<<i<<",";
*(p+i) = strtol( num, &num ,10 );
cout<<static_cast<int>(*(p+i))<<",";
++num;
// cout<<num<<":";
}
cout<<endl;
p = (char*)&right;
for( i=3; i<4; --i )
{
*(p+i) = strtol( num, &num, 10 );
++num;
}
}
void UniqueSequence( vector<unsigned int> & uSeq, unsigned int left, unsigned int right )
{
size_t i, lPos=-1, rPos=-1;
for( i=0; i<uSeq.size(); i++ )
{
if( left <= uSeq.at(i) )
{
lPos = i;
break;
}
}
for( ;i<uSeq.size(); i++ )
{
if( right<=uSeq.at(i) )
{
rPos=i;
break;
}
}
if( lPos == -1 )
{
uSeq.push_back( left );
uSeq.push_back( right );
return;
}
if( lPos%2 == 0 )
{
if( uSeq.at(lPos)==left )
{
}
else
{
uSeq.insert( uSeq.begin()+lPos, left );
}
}
else
{
--lPos;
}
if( rPos == -1 )
{
uSeq.erase( uSeq.begin()+(lPos+1), uSeq.end() );
uSeq.push_back(right);
}
else if( rPos%2 == 0 )
{
if( uSeq.at(rPos)== right )
{
uSeq.erase( uSeq.begin()+(lPos+1), uSeq.begin()+(rPos+1) );
}
else
{
uSeq.erase( uSeq.begin()+(lPos+1), uSeq.begin()+rPos );
uSeq.insert( uSeq.begin()+rPos, right );
}
}
else
{
uSeq.erase( uSeq.begin()+(lPos+1), uSeq.begin()+rPos );
}
}
void PrintIP( unsigned int num )
{
char *p = (char*)#
for( size_t i=3;i>0; --i)
{
cout<< (int)p[i]<<".";
}
cout<<(int)p[0];
}
#define MAX_BUFFER_LENGTH 100
int main()
{
unsigned int left, right;
char buffer[MAX_BUFFER_LENGTH];
ifstream infile( "test.txt" );
if( infile.fail() )
{
return 0;
}
vector<unsigned int> uSeq;
while( infile.getline(buffer, MAX_BUFFER_LENGTH) )
{
ParseLine(buffer, strlen(buffer), left, right);
// cout<<left<<","<<right<<endl;
UniqueSequence( uSeq, left, right );
for( size_t i=0; i<uSeq.size(); i+=2 )
{
PrintIP(uSeq.at(i) );
cout<<" ";
PrintIP(uSeq.at(i+1));
cout<<endl;
}
cout<<endl;
}
for( size_t i=0; i<uSeq.size(); i+=2 )
{
PrintIP(uSeq.at(i) );
cout<<" ";
PrintIP(uSeq.at(i+1));
cout<<endl;
}
return 0;
}
/*long strtol( const char *nptr, char **endptr, int base ),其中nptr是以NULL结尾字符串，endptr是字符串停止扫描的地方（Pointer to character that stops scan），strtol returns the value represented in the string nptr，The strtol function converts nptr to a long. strtol
stops reading the string nptr at the first character it cannot
recognize as part of a number. This may be the terminating null
character, or it may be the first numeric character greater than or
equal to base.
string = "-10110134932This stopped it";
l = strtol( string, &stopstring, 10 );
printf( "string = %s", string );
printf(" strtol = %ld", l );
printf(" Stopped scan at: %s", stopstring );
string = "10110134932";
printf( "string = %s\n", string );
/* Convert string using base 2, 4, and 8: */
for( base = 2; base <= 8; base *= 2 )
{
/* Convert the string: */
ul = strtoul( string, &stopstring, base );
printf( " strtol = %ld (base %d)\n", ul, base );
printf( " Stopped scan at: %s\n", stopstring );
}
打印的结果是：
string = -10110134932This stopped it strtol = -2147483647 Stopped scan at: This stopped itstring = 10110134932
strtol = 45 (base 2)
Stopped scan at: 34932
strtol = 4423 (base 4)
Stopped scan at: 4932
strtol = 2134108 (base 8)
Stopped scan at: 932
*/
5.如果存在两个变量：a和b，不使用“if”、“?:”、 “switch”和其它的判断语句，找出两个数中的最大值。
答案：( ( a + b ) + abs( a - b ) ) / 2
6. 写一个函数找出一个整数数组中，第二大的数 （microsoft）
const int MINNUMBER = -32767 ;
int find_sec_max( int data[] , int count)
{
int maxnumber = data[0] ;
int sec_max = MINNUMBER ;
for ( int i = 1 ; i < count ; i++)
{
if ( data[i] > maxnumber )
{
sec_max = maxnumber ;
maxnumber = data[i] ;
}
else
{
if ( data[i] > sec_max )
sec_max = data[i] ;
}
}
return sec_max ;
}
一、如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）
struct node { char val; node* next;}
bool check(const node* head) {} //return false : 无环；true: 有环
一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：
bool check(const node* head)
{
if(head==NULL)
return false;
node *low=head, *fast=head->next;
while(fast!=NULL && fast->next!=NULL)
{
low=low->next;
fast=fast->next->next;
if(low==fast)
return true;
}
return false;
}
二、删除一个单项链表的最中间的元素，要求时间尽可能短（不能使用两次循环）
struct link
{
int data;
struct link *next;
};
void delMiddle(link *head)
{
if(head == NULL)
return;
else if(head->next == NULL)
{
delete head;
return;
}
else
{
link *low = head;
link *fast = head->next;
while(fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
if(fast == NULL)
break;
low = low->next;
}
link *temp = low->next;
low->next = low->next->next;
delete temp;
}
}
int main()
{
struct link *head,*l;
struct link *s;
head = (link*)malloc(sizeof(link));
head->data=0;
head->next = NULL;
l = head;
for(int i=1; i<9; i++)
{
s = (link*)malloc(sizeof(link));
s->data = i;
s->next = NULL;
l->next= s;
l = l->next;
}
print(head);
delMiddle(head);
print(head);
return 0;
}
三、输入n，求一个n*n矩阵，规定矩阵沿45度线递增(威盛)
/**
* 得到如下样式的二维数组
* zigzag（jpeg编码里取象素数据的排列顺序）
*
* 0, 1, 5, 6,14,15,27,28,
* 2, 4, 7,13,16,26,29,42,
* 3, 8,12,17,25,30,41,43,
* 9,11,18,24,31,40,44,53,
* 10,19,23,32,39,45,52,54,
* 20,22,33,38,46,51,55,60,
* 21,34,37,47,50,56,59,61,
* 35,36,48,49,57,58,62,63
*/
void zigzag(int n)
{
int **a =(int**) malloc(n*sizeof(int *)); //分配空间
if(NULL == a)
return ;
int i;
for(i = 0; i < n; i++) {
if((a[i] =(int*) malloc(n * sizeof(int))) == NULL) {
while(--i>=0)
free(a[i]);
free(a);
return;
}
}
bool flag = false; //这个标志位用来判断是从45度角生成还是225度角生成
int count = 0;
for(i=0; i<n; i++) //生成的上半部分的数据
{
if(flag)
{
for(int r = 0; r<=i; r++)
{
a[r][i-r] = count;
count++;
}
flag = false;
}
else
{
for(int r = i; r>=0; r--)
{
a[r][i-r] = count;
count++;
}
flag = true;
}
}
for(i=n-1; i>=0; i--) //生成的是下半部分的数据
{
// cout<<i<<endl;
if(flag)
{
for(int r = 0; r<=i-1; r++)
{
int r1 = n-i+r; //代表当前行
int c1 = 2*n-i-1-r1; //代表当前列
a[r1][c1] = count;
count++;
}
flag = false;
}
else
{
for(int r = i-1; r>=0; r--)
{
cout<<"ddd"<<endl;
int r1 = n-i+r;
int c1 = 2*n-i-1-r1;
// cout<<r1<<","<<c1<<endl;
a[r1][c1] = count;
count++;
}
flag = true;
}
}
for(int r = 0; r<n; r++)
{
for(int c=0; c<n; c++)
cout<<a[r][c]<<",";
cout<<endl;
}
}
int main()
{
int n;
cin>>n;
zigzag(n);
return 0;
}
网上还有一个人写了一个比较巧的算法：
/**
* 得到如下样式的二维数组
* zigzag（jpeg编码里取象素数据的排列顺序）
*
* 0, 1, 5, 6,14,15,27,28,
* 2, 4, 7,13,16,26,29,42,
* 3, 8,12,17,25,30,41,43,
* 9,11,18,24,31,40,44,53,
* 10,19,23,32,39,45,52,54,
* 20,22,33,38,46,51,55,60,
* 21,34,37,47,50,56,59,61,
* 35,36,48,49,57,58,62,63
*/
#include <stdio.h>
int main()
{
int N;
int s, i, j;
int squa;
scanf("%d", &N);
/* 分配空间 */
int **a = malloc(N * sizeof(int *));
if(a == NULL)
return 0;
for(i = 0; i < N; i++) {
if((a[i] = malloc(N * sizeof(int))) == NULL) {
while(--i>=0)
free(a[i]);
free(a);
return 0;
}
}
/* 数组赋值 */
squa = N*N;
for(i = 0; i < N; i++)
for(j = 0; j < N; j++) {
s = i + j;
if(s < N)
a[i][j] = s*(s+1)/2 + (((i+j)%2 == 0)? i : j);
else {
s = (N-1-i) + (N-1-j);
a[i][j] = squa - s*(s+1)/2 - (N - (((i+j)%2 == 0)? i : j));
}
}
/* 打印输出 */
for(i = 0; i < N; i++) {
for(j = 0; j < N; j++)
printf("%-6d", a[i][j]);
printf("\n");
}
return 0;
}
四、打印1到1000的整数，不能使用流程控制语句(for,while,goto等)也不能使用递归
1.
typedef struct _test{
static int a;
_test(){
printf("%d\n",_test::a);
a++;
}
}Test;
int Test::a = 1;
int main()
{
Test tt[1000];
return 0;
}
2.
#include <stdio.h>
#define B P,P,P,P,P,P,P,P,P,P
#define P L,L,L,L,L,L,L,L,L,L
#define L I,I,I,I,I,I,I,I,I,I,N
#define I printf( "%3d ",i++)
#define N printf( "\n ")
int main()
{
int i = 1;
B;
}
或
#define A(x) x;x;x;x;x;x;x;x;x;x;
int main ()
{
int n = 1;
A(A(A(printf ("%d ", n++))));
return 0;
}
五、struct S {
int i;
int * p;
};
void main()
{
S s;
int * p = &s.i;
p[0] = 4;
p[1] = 3;
s.p = p;
s.p[1] = 1;
s.p[0] = 2;
}
问程序会在哪一行死掉。 （microsoft）
解： S s;
int * p = &s.i; //s.i的地址存储在p里
p[0] = 4; //修改了s.i
p[1] = 3; //修改了s.p
s.p = p; //s.p指向s.i
s.p[1] = 1; //修改s.p本身
s.p[0] = 2; //s.p指向的是0x00000001,尝试向这里写,出错
s.p[0] = 2; 时出错
因为s.p存的是s.i的地址,s.p[1]为s.p,当s.p[1]=1时,s.p此时存放的是1了,而不是地址s.i,故在s.p[0] = 2时出错.
此时相当于s.p=ox00000001;地址ox0000001 = 2;当然就出错了
如果语句s.p[0] =2 先于s.p[1]=1则程序就不会出错.此时语句相当于s.i=2;s.p=1;
六、题目描述：
1. int swap(int *x,int *y)
{
if(x==NULL ¦ ¦ y==NULL)
return -1;
*x += *y;
*y = *x- *y;
*x -= *y;
return 1;
}
请改错，溢出已经考虑，不是错误
2.
void foo(int *x, int *y)
{
*x += *y;
*x += *y;
}
void fun(int *x, int *y)
{
*x += 2 * (*y);
}
问两个函数是否等价，能否互换
解答：第一题的函数是交换。但假如考虑x, y都是指向同一个变量,结果是这个变量的值为0.
第二题的两个函数是有区别的,也考虑x,y是指向同一个变量.这样第一个函数的结果是这个变量的4倍.但第二个函数的结果是变量的3倍.
1.下列程序的输出结果为：(B)
#include<iostream.h>
void main()
{
char* a[ ] = { "hello", "the", "world"};
char** pa = a;
pa++;
cout<<”*pa<<endl;
}
A) theworld B) the C) ello D) ellotheworld
2. 已知二叉树后序遍历序列是bfegcda，中序遍历序列是badefcg，它的前序遍历序列是：(B)
A) abcdefg B) abdcefg C) adbcfeg D) abecdfg
3. 栈和队列的共同特点是：(C)
A) 都是先进先出 B) 都是先进后出
C) 只允许在短点处插入和删除元素 D) 没有共同点
4. 下面程序的运行结果为：(A)
#include <iostream.h>
void main()
{
int a, x;
for(a = 0, x = 0; a<=1 && !x++; a++)
{
a++;
}
cout<< a << x <<endl;
}
A) 21 B) 22 C) 32 D) 41
5. 下列选项，不正确的是：(B) while后没有分号
A) for(int a=1; a<=10; a++);
B) int a=1;
do
{
a++;
}while(a<=10)
C) int a=1;
while(a<=10)
{
a++;
}
D) for(int a= 1; a<=10; a++)a++;
6. 下面关于数组的初始化正确的是：(B)
A) char str[2] = {“a”,”b”};
B) char str[2][3]={“a”,”b”};
C) char str[2][3]={{‘a’,’b’},{‘e’,’d’},{‘e’,’f’}};
D) char str[] = {“a”, “b”};
7. 下列说法正确的是：(B)
A) 内联函数在运行时是将该函数的目标代码插入每个调用该函数的地方
B) 内联函数在编译时是将该函数的目标代码插入每个调用该函数的地方
C) 类的内联函数必须在类体内定义
D) 类的内联函数必须在类体外通过关键字inline定义
8．下面对静态成员的描述中，正确的是：(D)
A) 静态数据成员可以在类体内初始化
B) 静态数据成员不可以被类的对象调用
C) 静态数据成员不能受private控制符的作用
D) 静态数据成员可以直接用类名调用
9. 下列运算符中，在C++语言中不能重载的是：(C)
A) * B) >= C) :: D) delete
10 下面关于多态性的描述，错误的是：(C)
A) C++语言的多态性分为编译时的多态性和运行时的多态性
B) 编译时的多态性可通过函数重载实现
C) 运行时的多态性可通过模板和虚函数实现 //模板的是编译时多态性，而虚函数是运行时
D) 实现运行时多态性的机制称为动态绑定
11. 如果进栈序列为e1,e2,e3,e4,e5,则可能的出栈序列是：(D)
A) e3,e2,e5,e4,e1
B) e2,e3,e5,e4,e1
C) e3,e2,e4,e5,e1
D) 以上都有可能
12 下面关于类和对象的描述中，错误的是：(A)
A) 类就是C语言中的结构体类型，对象就是C语言中的结构体变量
B) 类和对象之间的关系是抽象和具体的关系
C) 对象是类的实例，一个对象必须属于一个已知的类
D) 类是具有共同行为的若干对象的统一描述体
13.下面关于数组的描述错误的是：（D）
A) 在C++语言中数组的名字就是指向该数组第一个元素的指针
B) 长度为n的数组，下标的范围是0－n-1
C) 数组的大小必须在编译是确定
D) 数组只能通过值参数和引用参数两种方式传递给函数
注释：
在把数组作为参数传递给函数时，有值传递(by value)和地址传递(by reference)两种方式。
在值传递方式中，要在数组参数的尾部加上一对方括号([])，调用函数时只需将数组的地址(即数组名)传递给函数。
例如：如果数组x被声明为：int x[10];
那麽函数被说明为：void byval_func(int[]);
参数int[]告诉编译程序byval_func()函数只有一个参数,即一个由int型值组成的数组。
函数调用时只需将数组名传递给函数:byval_func(x);
#include <stdio.h>
void byval_func(int[]);
void main(void);
void main(void)
{
int x[10];
int y;
for(y=0;y<10;y++)
x[y]=y;
byval_func(x);
}
void byal_func(int i[])
{
int y;
for(y=0;y<10;y++)
printf("%d\n",i[y]);
}
在
值传递方式中,数组x将被复制一份,复制所得的数组将被存放在栈中,然后由byval_func()函数接收并打印出来。由於传递给
byval_func()函数的是初始数组的一份拷贝，因此在byval_func()函数内部修改传递过来的数组对初始数组没有任何影响。
值传递方法的开销是很大的，因为首先它要完整地复制初始数组并将这份拷贝存放到栈中，这将耗费相当可观的运行时间，
因而值传递方法效率较低；其次，初始化数组的拷贝需要占用额外的内存空间（栈中的内存）；最后，编译程序需要专门产生一部分用来复制初始数组的代码，这将
使程序变大。
地址传递方法克服了值传递方法的缺点。在地址传递方法中，传递给函数的是指向初始数组的指针，不用复制数组，因此程序变得简练，也节省了栈中的内存空间。在地址传递过程中,只需在函数原形中将函数的参数说明为指向数组元素数据类型的一个指针。
例如同样定义一个数组x：int x[10];
那麽函数被说明为：int const_funt(const int*);
参数const int*告诉编译程序const_funt()函数只有一个参数,即指向一个int类型常量的指针。
函数调用时只需将数组的地址传递给函数:const_func(x);
#include <stdio.h>
void const_func(const int*);
void main(void);
void main(void)
{
int x[10];
int y;
for(y=0;y<10;y++)
x[y]=y;
constl_func(x);
}
void const_func(const int*i)
{
int y;
for(y=0;y<10;y++)
printf("%d\n",*(i+y));
}
在
值传递方式中,没有复制初始数组并将其拷贝存放在栈中,const_func()函数只接收到指向一个int类型常量的指针,因此在编写程序时要保证传递
给const_func()函数的是指向一个由int类型常量组成的数组的指针。const修饰符的作用是防止意外修改初始数组中的某一个元素。
14． 引用标准库时，下面的说法你认为哪个是正确的：（B）
A) 语句#include “stdlib.h”是正确的，但会影响程序的执行速度
B) 语句#include <stdlib.h>是正确的，而去程序执行速度比#include “stdlib.h”要快
C) 语句#include <stdlib.h>和#include “stdlib.h”都是正确的，程序执行速度没有区别
D) 语句#include “stdlib.h”是错误的
注释：include ""是先从本地目录开始寻找，然后去寻找系统路径，而Include <> 相反先从系统目录，后从本地目录，
15.设a、b、c、d、m、n均为int型变量，且a=5、b=6、c=7、d=8、m=2、n=2,则逻辑表达式（m=a>b）&&(n=c>d)运算后，n的值为：（C）
A) 0 B) 1 C) 2 D) 7
16．不能作为重载函数的调用的依据是：（C）
A) 参数个数 B) 参数类型
C) 函数类型 D) 函数名称
17．下列程序的输出结果为: (D)
#include< iostream. h>
int func(int n)
{
if〔n<1)return 1;
else return n+func(n-1);
return 0;
}
void main()
{
cout<<func(5)<<endl;
}
A) 0 B)10 C)15 D)16
18. 建立派生类对象时,3种构造函数分别是a(基类的构造函数)、b(成员对象的构造函数)、c(派生类的构造函数)这3种构造函数的调用顺序为: (A)
A)abc B)acb
C)cab D)cba
19. 如果友元函数重载一个运算符时，其参数表中没有任何参数则说明该运算符是：（D）
A）一元运算符 B）二元运算符
C）选项A）和选项B）都可能 D）重载错误
解析：C++中用友元函数重载运算符至少有一个参数，重载一目运算符要有一个参数，重载二目运算符要有两个参数。
20. 有以下程序段：（D）？
#define F(X,Y) (X)--; (Y)++ (X)*(Y);
…
int i, a = 3, b = 4;
for( i = 0; i<5; i++) F(a,b)
printf(“%d, %d”, a, b);
输出结果是：（）
A) 3, 4 B) 3, 5
C) -2, 5 D) -2, 9
21. 下列for循环的循环体执行次数为：（A）
for(int i(10), j(1); i=j=0; i++, j--)
A) 0; B) 1; C) 无限; D)以上都不对
22. 下面程序的输出结果是（D）
char *p1= “123”, *p2 = “ABC”, str［50］= "xyz";
strcpy（str+2,strcat（p1,p2））;
cout << str;
A）xyz123ABC B）z123ABC
C）xy123ABC D）出错
23．下面函数的执行结果是输出（B）
char str[ ] = “xunlei”;
char *p = str;
int n = 10;
printf(“%d, %d, %d\n”, sizeof(str), sizeof(p), sizeof(n));
A) 4, 4, 4 B) 7, 4, 4
C) 6, 4, 4 D) 6, 6, 4
33. 有下列程序段：
char *p, *q;
p = (char*) malloc(sizeof(char) * 20);
q = p;
scanf(“%s %s”, p, q);
printf(“%s %s\n”, p, q);
若从键盘输入：abc def， 则输出结果是（A）
A) def def B) abc def
C) abc d D) d d
解析：q=p;因此p,q指向的是同一段内存.scanf先是把abc写到p指向的空间,再把def写到q指向的空间,也就是同一段空间,因此abc被def覆盖了.
34．现在有以下语句：
struct _THUNDER{
int iVersion;
char cTag;
char cAdv;
int iUser;
char cEnd;
}Thunder;
int sz = sizeof(Thunder);
则执行后，变量sz的值将得到（D）
A) 11 B) 12 C) 13 D) 16
35. 有如下程序段：
void GetMemeory(char* p)
｛
p = (char*) malloc (100);
｝
void test()
{
char *str=NULL;
GetMemory(str);
strcpy(str,”Thunder”);
strcat(str+2, “Downloader”);
printf(str);
}
请问运行Test函数结果是：（D）
A) Thunder Downloader B) under Downloader
C) Thunderownloader D) 程序崩溃
解析：在函数中给指针分配空间，实际上是给指针的临时变量分配空间，函数结束后，这个临时变量也消亡，而str仍然为NULL，没有为其分配空间，此时strcpy()是肯定会出错的。
36. 函数调用exec((v1,v2), (v3,v4,v5),v6,v7);中，实参的个数是（A）
A) 4 B) 5 C) 6 D) 7
37. p是指向类X的成员m的指针，s是类X的一个对象。现要给m赋值，（C）是正确的。
A) s.p = 5 B) s->p = 5
C) s.*p = 5 D) *s.p = 5
38. 函数fun（char* p） { return p;}的返回值是（B）
A)无确切值 B) 行参p中存放的地址值
C) 一个临时存储单元的地址 D) 行参p自身的地址值
39．a,b均为不等于0的整形变量，以下关系式恒成立的是：（C）
A) a*b/a*b == 1 B) a/b*b/a == 1
C) a/b*b + a%b == a D) a/b*b == a
40. 设有如下说明：
typedef struct ST{ long a; int b; char c[2]; } NEW;
则下面叙述中正确的是：(C)
A）以上的说明形式非法 B）ST是一个结构体类型
C）NEW是一个结构体类型 D）NEW是一个结构体变量
41. 下列表达式正确的是：（C）
A) 9++ B) （x+y）++ C) c+++c+++c++ D) ++（a-b--）
42．在int b[ ][3] = {{1},{3,2},{4,5,6},{0}};中，sizeof(b) = （D）。
A) 4 B) 12 C) 28 D) 48
43．以下程序的输出结果是：(D)
#define M(x,y,z) x*y+z
main()
{
int a=1, b=2, c=3;
printf(“%d\n”,M(a+b,b+c,c+a));
}
A）19 B) 17 C) 15 D) 12
44．若有以下定义和语句：
int u=010, v= 0x10, w=10;
printf(“%d，%d,%d\n”,u,v,w);
则输出结果是：(A)
A)8,16,10 B)10,10,10 C)8,8,10 D)8,10,10
45. 下面程序段的输出结果是：（B）
int a=5, b=4, c=3, d=2;
if(a>b>c)
printf(“%d\n”,d);
else if((c-1>=d)==1)
printf(“%d\n”, d+1);
else
printf(“%d\n”, d+1);
A) 2 B) 3 C) 4 D) 编译错误
46．有如下程序段，请问k的值是：（D）
enum {a, b=5, c, d=4, e} k; k =c;
A) 3 B）4 C) 5 D) 6
47．有如下程序段：
int i, n = 0;
double x = 1, y1 = 2.1/1.9, y2 = 1.9/2.1;
for( i = 1; i<22; i++)
x = x*y1;
while( x!=1.0)
{
x =x*y2;
n++;
}
printf(“%d\n”, n);
请问执行结果是：（A）
A) 21 B) 22 C)无限循环 D) 程序崩溃
48. 用树形结构表示实体之间联系的模型是（C）
A) 关系模型 B) 网状模型 C) 层次模型 D)以上三个都是
49．有如下程序段：
char fun(char *);
main()
{
char *s = “one”, a[5] = {0}, (*f1)(char *) = fun, ch;
}
则对函数fun的调用语句正确的是（C）
A) *f1(&a); B) f1（*s）; C) f1(&ch) D) ch = *f1(s);要改成（*f1）(s)才正确
50．有如下程序段：
int c = 23;
printf(“%d\n”, c&c);
请问执行结果是：（C）
A) 0 B) 46 C) 23 D) 以上都不对