下圖是基于TCP協(xié)議的客戶端/服務(wù)器程序的一般流程:
服務(wù)器調(diào)用socket()、bind()、listen()完成初始化后,調(diào)用accept()阻塞等待,處于監(jiān)聽(tīng)端口的狀態(tài),客戶端調(diào)用socket()初始化后,調(diào)用connect()發(fā)出SYN段并阻塞等待服務(wù)器應(yīng)答,服務(wù)器應(yīng)答一個(gè)SYN-ACK段,客戶端收到后從connect()返回,同時(shí)應(yīng)答一個(gè)ACK段,服務(wù)器收到后從accept()返回。
數(shù)據(jù)傳輸?shù)倪^(guò)程:
建立連接后,TCP協(xié)議提供全雙工的通信服務(wù),但是一般的客戶端/服務(wù)器程序的流程是由客戶端主動(dòng)發(fā)起請(qǐng)求,服務(wù)器被動(dòng)處理請(qǐng)求,一問(wèn)一答的方式。因此,服務(wù)器從accept()返回后立刻調(diào)用read(),讀socket就像讀管道一樣,如果沒(méi)有數(shù)據(jù)到達(dá)就阻塞等待,這時(shí)客戶端調(diào)用write()發(fā)送請(qǐng)求給服務(wù)器,服務(wù)器收到后從read()返回,對(duì)客戶端的請(qǐng)求進(jìn)行處理,在此期間客戶端調(diào)用read()阻塞等待服務(wù)器的應(yīng)答,服務(wù)器調(diào)用write()將處理結(jié)果發(fā)回給客戶端,再次調(diào)用read()阻塞等待下一條請(qǐng)求,客戶端收到后從read()返回,發(fā)送下一條請(qǐng)求,如此循環(huán)下去。
如果客戶端沒(méi)有更多的請(qǐng)求了,就調(diào)用close()關(guān)閉連接,就像寫(xiě)端關(guān)閉的管道一樣,服務(wù)器的read()返回0,這樣服務(wù)器就知道客戶端關(guān)閉了連接,也調(diào)用close()關(guān)閉連接。注意,任何一方調(diào)用close()后,連接的兩個(gè)傳輸方向都關(guān)閉,不能再發(fā)送數(shù)據(jù)了。如果一方調(diào)用shutdown()則連接處于半關(guān)閉狀態(tài),仍可接收對(duì)方發(fā)來(lái)的數(shù)據(jù)。
在學(xué)習(xí)socket API時(shí)要注意應(yīng)用程序和TCP協(xié)議層是如何交互的: *應(yīng)用程序調(diào)用某個(gè)socket函數(shù)時(shí)TCP協(xié)議層完成什么動(dòng)作,比如調(diào)用connect()會(huì)發(fā)出SYN段 *應(yīng)用程序如何知道TCP協(xié)議層的狀態(tài)變化,比如從某個(gè)阻塞的socket函數(shù)返回就表明TCP協(xié)議收到了某些段,再比如read()返回0就表明收到了FIN段
最簡(jiǎn)單的TCP網(wǎng)絡(luò)程序
下面通過(guò)最簡(jiǎn)單的客戶端/服務(wù)器程序的實(shí)例來(lái)學(xué)習(xí)socket API。
server.c的作用是從客戶端讀字符,然后將每個(gè)字符轉(zhuǎn)換為大寫(xiě)并回送給客戶端。
/* server.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <netinet/in.h>
#define MAXLINE 80
#define SERV_PORT 8000
int main(void)
{
struct sockaddr_in servaddr, cliaddr;
socklen_t cliaddr_len;
int listenfd, connfd;
char buf[MAXLINE];
char str[INET_ADDRSTRLEN];
int i, n;
listenfd = socket(AF_INET, SOCK_STREAM, 0);
bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
servaddr.sin_port = htons(SERV_PORT);
bind(listenfd, (struct sockaddr *)&servaddr, sizeof(servaddr));
listen(listenfd, 20);
printf("Accepting connections ...\n");
while (1) {
cliaddr_len = sizeof(cliaddr);
connfd = accept(listenfd,
(struct sockaddr *)&cliaddr, &cliaddr_len);
n = read(connfd, buf, MAXLINE);
printf("received from %s at PORT %d\n",
inet_ntop(AF_INET, &cliaddr.sin_addr, str, sizeof(str)),
ntohs(cliaddr.sin_port));
for (i = 0; i < n; i++)
buf[i] = toupper(buf[i]);
write(connfd, buf, n);
close(connfd);
}
}
下面介紹程序中用到的socket API,這些函數(shù)都在sys/socket.h
中。
int socket(int family, int type, int protocol);
socket()打開(kāi)一個(gè)網(wǎng)絡(luò)通訊端口,如果成功的話,就像open()一樣返回一個(gè)文件描述符,應(yīng)用程序可以像讀寫(xiě)文件一樣用read/write在網(wǎng)絡(luò)上收發(fā)數(shù)據(jù),如果socket()調(diào)用出錯(cuò)則返回-1。對(duì)于IPv4,family參數(shù)指定為AF_INET。對(duì)于TCP協(xié)議,type參數(shù)指定為SOCK_STREAM,表示面向流的傳輸協(xié)議。如果是UDP協(xié)議,則type參數(shù)指定為SOCK_DGRAM,表示面向數(shù)據(jù)報(bào)的傳輸協(xié)議。protocol參數(shù)的介紹從略,指定為0即可。
int bind(int sockfd, const struct sockaddr *myaddr, socklen_t addrlen);
服務(wù)器程序所監(jiān)聽(tīng)的網(wǎng)絡(luò)地址和端口號(hào)通常是固定不變的,客戶端程序得知服務(wù)器程序的地址和端口號(hào)后就可以向服務(wù)器發(fā)起連接,因此服務(wù)器需要調(diào)用bind綁定一個(gè)固定的網(wǎng)絡(luò)地址和端口號(hào)。bind()成功返回0,失敗返回-1。
bind()的作用是將參數(shù)sockfd和myaddr綁定在一起,使sockfd這個(gè)用于網(wǎng)絡(luò)通訊的文件描述符監(jiān)聽(tīng)myaddr所描述的地址和端口號(hào)。前面講過(guò),struct sockaddr *是一個(gè)通用指針類型,myaddr參數(shù)實(shí)際上可以接受多種協(xié)議的sockaddr結(jié)構(gòu)體,而它們的長(zhǎng)度各不相同,所以需要第三個(gè)參數(shù)addrlen指定結(jié)構(gòu)體的長(zhǎng)度。我們的程序中對(duì)myaddr參數(shù)是這樣初始化的:
bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
servaddr.sin_port = htons(SERV_PORT);
首先將整個(gè)結(jié)構(gòu)體清零,然后設(shè)置地址類型為AF_INET,網(wǎng)絡(luò)地址為INADDR_ANY,這個(gè)宏表示本地的任意IP地址,因?yàn)榉?wù)器可能有多個(gè)網(wǎng)卡,每個(gè)網(wǎng)卡也可能綁定多個(gè)IP地址,這樣設(shè)置可以在所有的IP地址上監(jiān)聽(tīng),直到與某個(gè)客戶端建立了連接時(shí)才確定下來(lái)到底用哪個(gè)IP地址,端口號(hào)為SERV_PORT,我們定義為8000。
int listen(int sockfd, int backlog);
典型的服務(wù)器程序可以同時(shí)服務(wù)于多個(gè)客戶端,當(dāng)有客戶端發(fā)起連接時(shí),服務(wù)器調(diào)用的accept()返回并接受這個(gè)連接,如果有大量的客戶端發(fā)起連接而服務(wù)器來(lái)不及處理,尚未accept的客戶端就處于連接等待狀態(tài),listen()聲明sockfd處于監(jiān)聽(tīng)狀態(tài),并且最多允許有backlog個(gè)客戶端處于連接待狀態(tài),如果接收到更多的連接請(qǐng)求就忽略。listen()成功返回0,失敗返回-1。
int accept(int sockfd, struct sockaddr *cliaddr, socklen_t *addrlen);
三方握手完成后,服務(wù)器調(diào)用accept()接受連接,如果服務(wù)器調(diào)用accept()時(shí)還沒(méi)有客戶端的連接請(qǐng)求,就阻塞等待直到有客戶端連接上來(lái)。cliaddr是一個(gè)傳出參數(shù),accept()返回時(shí)傳出客戶端的地址和端口號(hào)。addrlen參數(shù)是一個(gè)傳入傳出參數(shù)(value-result argument),傳入的是調(diào)用者提供的緩沖區(qū)cliaddr的長(zhǎng)度以避免緩沖區(qū)溢出問(wèn)題,傳出的是客戶端地址結(jié)構(gòu)體的實(shí)際長(zhǎng)度(有可能沒(méi)有占滿調(diào)用者提供的緩沖區(qū))。如果給cliaddr參數(shù)傳NULL,表示不關(guān)心客戶端的地址。
我們的服務(wù)器程序結(jié)構(gòu)是這樣的:
while (1) {
cliaddr_len = sizeof(cliaddr);
connfd = accept(listenfd,
(struct sockaddr *)&cliaddr, &cliaddr_len);
n = read(connfd, buf, MAXLINE);
...
close(connfd);
}
整個(gè)是一個(gè)while死循環(huán),每次循環(huán)處理一個(gè)客戶端連接。由于cliaddr_len是傳入傳出參數(shù),每次調(diào)用accept()之前應(yīng)該重新賦初值。accept()的參數(shù)listenfd是先前的監(jiān)聽(tīng)文件描述符,而accept()的返回值是另外一個(gè)文件描述符connfd,之后與客戶端之間就通過(guò)這個(gè)connfd通訊,最后關(guān)閉connfd斷開(kāi)連接,而不關(guān)閉listenfd,再次回到循環(huán)開(kāi)頭listenfd仍然用作accept的參數(shù)。accept()成功返回一個(gè)文件描述符,出錯(cuò)返回-1。
client.c的作用是從命令行參數(shù)中獲得一個(gè)字符串發(fā)給服務(wù)器,然后接收服務(wù)器返回的字符串并打印。
/* client.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/socket.h>
#include <netinet/in.h>
#define MAXLINE 80
#define SERV_PORT 8000
int main(int argc, char *argv[])
{
struct sockaddr_in servaddr;
char buf[MAXLINE];
int sockfd, n;
char *str;
if (argc != 2) {
fputs("usage: ./client message\n", stderr);
exit(1);
}
str = argv[1];
sockfd = socket(AF_INET, SOCK_STREAM, 0);
bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
inet_pton(AF_INET, "127.0.0.1", &servaddr.sin_addr);
servaddr.sin_port = htons(SERV_PORT);
connect(sockfd, (struct sockaddr *)&servaddr, sizeof(servaddr));
write(sockfd, str, strlen(str));
n = read(sockfd, buf, MAXLINE);
printf("Response from server:\n");
write(STDOUT_FILENO, buf, n);
close(sockfd);
return 0;
}
由于客戶端不需要固定的端口號(hào),因此不必調(diào)用bind(),客戶端的端口號(hào)由內(nèi)核自動(dòng)分配。注意,客戶端不是不允許調(diào)用bind(),只是沒(méi)有必要調(diào)用bind()固定一個(gè)端口號(hào),服務(wù)器也不是必須調(diào)用bind(),但如果服務(wù)器不調(diào)用bind(),內(nèi)核會(huì)自動(dòng)給服務(wù)器分配監(jiān)聽(tīng)端口,每次啟動(dòng)服務(wù)器時(shí)端口號(hào)都不一樣,客戶端要連接服務(wù)器就會(huì)遇到麻煩。
int connect(int sockfd, const struct sockaddr *servaddr, socklen_t addrlen);
客戶端需要調(diào)用connect()連接服務(wù)器,connect和bind的參數(shù)形式一致,區(qū)別在于bind的參數(shù)是自己的地址,而connect的參數(shù)是對(duì)方的地址。connect()成功返回0,出錯(cuò)返回-1。
先編譯運(yùn)行服務(wù)器:
$ ./server
Accepting connections ...
然后在另一個(gè)終端里用netstat命令查看:
$ netstat -apn|grep 8000
tcp 0 0 0.0.0.0:8000 0.0.0.0:* LISTEN 8148/server
可以看到server程序監(jiān)聽(tīng)8000端口,IP地址還沒(méi)確定下來(lái)?,F(xiàn)在編譯運(yùn)行客戶端:
$ ./client abcd
Response from server:
ABCD
回到server所在的終端,看看server的輸出:
$ ./server
Accepting connections ...
received from 127.0.0.1 at PORT 59757
可見(jiàn)客戶端的端口號(hào)是自動(dòng)分配的。現(xiàn)在把客戶端所連接的服務(wù)器IP改為其它主機(jī)的IP,試試兩臺(tái)主機(jī)的通訊。
再做一個(gè)小實(shí)驗(yàn),在客戶端的connect()代碼之后插一個(gè)while(1);死循環(huán),使客戶端和服務(wù)器都處于連接中的狀態(tài),用netstat命令查看:
$ ./server &
[1] 8343
$ Accepting connections ...
./client abcd &
[2] 8344
$ netstat -apn|grep 8000
tcp 0 0 0.0.0.0:8000 0.0.0.0:* LISTEN 8343/server
tcp 0 0 127.0.0.1:44406 127.0.0.1:8000 ESTABLISHED8344/client
tcp 0 0 127.0.0.1:8000 127.0.0.1:44406 ESTABLISHED8343/server
應(yīng)用程序中的一個(gè)socket文件描述符對(duì)應(yīng)一個(gè)socket pair,也就是源地址:源端口號(hào)和目的地址:目的端口號(hào),也對(duì)應(yīng)一個(gè)TCP連接。
表 37.1. client和server的socket狀態(tài)
socket文件描述符 |
源地址:源端口號(hào) |
目的地址:目的端口號(hào) |
狀態(tài) |
server.c中的listenfd |
0.0.0.0:8000 |
0.0.0.0:* |
LISTEN |
server.c中的connfd |
127.0.0.1:8000 |
127.0.0.1:44406 |
ESTABLISHED |
client.c中的sockfd |
127.0.0.1:44406 |
127.0.0.1:8000 |
ESTABLISHED |
上面的例子不僅功能簡(jiǎn)單,而且簡(jiǎn)單到幾乎沒(méi)有什么錯(cuò)誤處理,我們知道,系統(tǒng)調(diào)用不能保證每次都成功,必須進(jìn)行出錯(cuò)處理,這樣一方面可以保證程序邏輯正常,另一方面可以迅速得到故障信息。
為使錯(cuò)誤處理的代碼不影響主程序的可讀性,我們把與socket相關(guān)的一些系統(tǒng)函數(shù)加上錯(cuò)誤處理代碼包裝成新的函數(shù),做成一個(gè)模塊wrap.c:
#include <stdlib.h>
#include <errno.h>
#include <sys/socket.h>
void perr_exit(const char *s)
{
perror(s);
exit(1);
}
int Accept(int fd, struct sockaddr *sa, socklen_t *salenptr)
{
int n;
again:
if ( (n = accept(fd, sa, salenptr)) < 0) {
if ((errno == ECONNABORTED) || (errno == EINTR))
goto again;
else
perr_exit("accept error");
}
return n;
}
void Bind(int fd, const struct sockaddr *sa, socklen_t salen)
{
if (bind(fd, sa, salen) < 0)
perr_exit("bind error");
}
void Connect(int fd, const struct sockaddr *sa, socklen_t salen)
{
if (connect(fd, sa, salen) < 0)
perr_exit("connect error");
}
void Listen(int fd, int backlog)
{
if (listen(fd, backlog) < 0)
perr_exit("listen error");
}
int Socket(int family, int type, int protocol)
{
int n;
if ( (n = socket(family, type, protocol)) < 0)
perr_exit("socket error");
return n;
}
ssize_t Read(int fd, void *ptr, size_t nbytes)
{
ssize_t n;
again:
if ( (n = read(fd, ptr, nbytes)) == -1) {
if (errno == EINTR)
goto again;
else
return -1;
}
return n;
}
ssize_t Write(int fd, const void *ptr, size_t nbytes)
{
ssize_t n;
again:
if ( (n = write(fd, ptr, nbytes)) == -1) {
if (errno == EINTR)
goto again;
else
return -1;
}
return n;
}
void Close(int fd)
{
if (close(fd) == -1)
perr_exit("close error");
}
慢系統(tǒng)調(diào)用accept、read和write被信號(hào)中斷時(shí)應(yīng)該重試。connect雖然也會(huì)阻塞,但是被信號(hào)中斷時(shí)不能立刻重試。對(duì)于accept,如果errno是ECONNABORTED,也應(yīng)該重試。詳細(xì)解釋見(jiàn)參考資料。
TCP協(xié)議是面向流的,read和write調(diào)用的返回值往往小于參數(shù)指定的字節(jié)數(shù)。對(duì)于read調(diào)用,如果接收緩沖區(qū)中有20字節(jié),請(qǐng)求讀100個(gè)字節(jié),就會(huì)返回20。對(duì)于write調(diào)用,如果請(qǐng)求寫(xiě)100個(gè)字節(jié),而發(fā)送緩沖區(qū)中只有20個(gè)字節(jié)的空閑位置,那么write會(huì)阻塞,直到把100個(gè)字節(jié)全部交給發(fā)送緩沖區(qū)才返回,但如果socket文件描述符有O_NONBLOCK標(biāo)志,則write不阻塞,直接返回20。為避免這些情況干擾主程序的邏輯,確保讀寫(xiě)我們所請(qǐng)求的字節(jié)數(shù),我們實(shí)現(xiàn)了兩個(gè)包裝函數(shù)readn和writen,也放在wrap.c中:
ssize_t Readn(int fd, void *vptr, size_t n)
{
size_t nleft;
ssize_t nread;
char *ptr;
ptr = vptr;
nleft = n;
while (nleft > 0) {
if ( (nread = read(fd, ptr, nleft)) < 0) {
if (errno == EINTR)
nread = 0;
else
return -1;
} else if (nread == 0)
break;
nleft -= nread;
ptr += nread;
}
return n - nleft;
}
ssize_t Writen(int fd, const void *vptr, size_t n)
{
size_t nleft;
ssize_t nwritten;
const char *ptr;
ptr = vptr;
nleft = n;
while (nleft > 0) {
if ( (nwritten = write(fd, ptr, nleft)) <= 0) {
if (nwritten < 0 && errno == EINTR)
nwritten = 0;
else
return -1;
}
nleft -= nwritten;
ptr += nwritten;
}
return n;
}
如果應(yīng)用層協(xié)議的各字段長(zhǎng)度固定,用readn來(lái)讀是非常方便的。例如設(shè)計(jì)一種客戶端上傳文件的協(xié)議,規(guī)定前12字節(jié)表示文件名,超過(guò)12字節(jié)的文件名截?cái)?,不?2字節(jié)的文件名用'\0'補(bǔ)齊,從第13字節(jié)開(kāi)始是文件內(nèi)容,上傳完所有文件內(nèi)容后關(guān)閉連接,服務(wù)器可以先調(diào)用readn讀12個(gè)字節(jié),根據(jù)文件名創(chuàng)建文件,然后在一個(gè)循環(huán)中調(diào)用read讀文件內(nèi)容并存盤(pán),循環(huán)結(jié)束的條件是read返回0。
字段長(zhǎng)度固定的協(xié)議往往不夠靈活,難以適應(yīng)新的變化。比如,以前DOS的文件名是8字節(jié)主文件名加“.”加3字節(jié)擴(kuò)展名,不超過(guò)12字節(jié),但是現(xiàn)代操作系統(tǒng)的文件名可以長(zhǎng)得多,12字節(jié)就不夠用了。那么制定一個(gè)新版本的協(xié)議規(guī)定文件名字段為256字節(jié)怎么樣?這樣又造成很大的浪費(fèi),因?yàn)榇蠖鄶?shù)文件名都很短,需要用大量的'\0'補(bǔ)齊256字節(jié),而且新版本的協(xié)議和老版本的程序無(wú)法兼容,如果已經(jīng)有很多人在用老版本的程序了,會(huì)造成遵循新協(xié)議的程序與老版本程序的互操作性(Interoperability)問(wèn)題。如果新版本的協(xié)議要添加新的字段,比如規(guī)定前12字節(jié)是文件名,從13到16字節(jié)是文件類型說(shuō)明,從第17字節(jié)開(kāi)始才是文件內(nèi)容,同樣會(huì)造成和老版本的程序無(wú)法兼容的問(wèn)題。
現(xiàn)在重新看看上一節(jié)的TFTP協(xié)議是如何避免上述問(wèn)題的:TFTP協(xié)議的各字段是可變長(zhǎng)的,以'\0'為分隔符,文件名可以任意長(zhǎng),再看blksize等幾個(gè)選項(xiàng)字段,TFTP協(xié)議并沒(méi)有規(guī)定從第m字節(jié)到第n字節(jié)是blksize的值,而是把選項(xiàng)的描述信息“blksize”與它的值“512”一起做成一個(gè)可變長(zhǎng)的字段,這樣,以后添加新的選項(xiàng)仍然可以和老版本的程序兼容(老版本的程序只要忽略不認(rèn)識(shí)的選項(xiàng)就行了)。
因此,常見(jiàn)的應(yīng)用層協(xié)議都是帶有可變長(zhǎng)字段的,字段之間的分隔符用換行的比用'\0'的更常見(jiàn),例如本節(jié)后面要介紹的HTTP協(xié)議??勺冮L(zhǎng)字段的協(xié)議用readn來(lái)讀就很不方便了,為此我們實(shí)現(xiàn)一個(gè)類似于fgets的readline函數(shù),也放在wrap.c中:
static ssize_t my_read(int fd, char *ptr)
{
static int read_cnt;
static char *read_ptr;
static char read_buf[100];
if (read_cnt <= 0) {
again:
if ( (read_cnt = read(fd, read_buf, sizeof(read_buf))) < 0) {
if (errno == EINTR)
goto again;
return -1;
} else if (read_cnt == 0)
return 0;
read_ptr = read_buf;
}
read_cnt--;
*ptr = *read_ptr++;
return 1;
}
ssize_t Readline(int fd, void *vptr, size_t maxlen)
{
ssize_t n, rc;
char c, *ptr;
ptr = vptr;
for (n = 1; n < maxlen; n++) {
if ( (rc = my_read(fd, &c)) == 1) {
*ptr++ = c;
if (c == '\n')
break;
} else if (rc == 0) {
*ptr = 0;
return n - 1;
} else
return -1;
}
*ptr = 0;
return n;
}
1、請(qǐng)讀者自己寫(xiě)出wrap.c的頭文件wrap.h,后面的網(wǎng)絡(luò)程序代碼都要用到這個(gè)頭文件。
2、修改server.c和client.c,添加錯(cuò)誤處理。
目前實(shí)現(xiàn)的client每次運(yùn)行只能從命令行讀取一個(gè)字符串發(fā)給服務(wù)器,再?gòu)姆?wù)器收回來(lái),現(xiàn)在我們把它改成交互式的,不斷從終端接受用戶輸入并和server交互。
/* client.c */
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <netinet/in.h>
#include "wrap.h"
#define MAXLINE 80
#define SERV_PORT 8000
int main(int argc, char *argv[])
{
struct sockaddr_in servaddr;
char buf[MAXLINE];
int sockfd, n;
sockfd = Socket(AF_INET, SOCK_STREAM, 0);
bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
inet_pton(AF_INET, "127.0.0.1", &servaddr.sin_addr);
servaddr.sin_port = htons(SERV_PORT);
Connect(sockfd, (struct sockaddr *)&servaddr, sizeof(servaddr));
while (fgets(buf, MAXLINE, stdin) != NULL) {
Write(sockfd, buf, strlen(buf));
n = Read(sockfd, buf, MAXLINE);
if (n == 0)
printf("the other side has been closed.\n");
else
Write(STDOUT_FILENO, buf, n);
}
Close(sockfd);
return 0;
}
編譯并運(yùn)行server和client,看看是否達(dá)到了你預(yù)想的結(jié)果。
$ ./client
haha1
HAHA1
haha2
the other side has been closed.
haha3
$
這時(shí)server仍在運(yùn)行,但是client的運(yùn)行結(jié)果并不正確。原因是什么呢?仔細(xì)查看server.c可以發(fā)現(xiàn),server對(duì)每個(gè)請(qǐng)求只處理一次,應(yīng)答后就關(guān)閉連接,client不能繼續(xù)使用這個(gè)連接發(fā)送數(shù)據(jù)。但是client下次循環(huán)時(shí)又調(diào)用write發(fā)數(shù)據(jù)給server,write調(diào)用只負(fù)責(zé)把數(shù)據(jù)交給TCP發(fā)送緩沖區(qū)就可以成功返回了,所以不會(huì)出錯(cuò),而server收到數(shù)據(jù)后應(yīng)答一個(gè)RST段,client收到RST段后無(wú)法立刻通知應(yīng)用層,只把這個(gè)狀態(tài)保存在TCP協(xié)議層。client下次循環(huán)又調(diào)用write發(fā)數(shù)據(jù)給server,由于TCP協(xié)議層已經(jīng)處于RST狀態(tài)了,因此不會(huì)將數(shù)據(jù)發(fā)出,而是發(fā)一個(gè)SIGPIPE信號(hào)給應(yīng)用層,SIGPIPE信號(hào)的缺省處理動(dòng)作是終止程序,所以看到上面的現(xiàn)象。
為了避免client異常退出,上面的代碼應(yīng)該在判斷對(duì)方關(guān)閉了連接后break出循環(huán),而不是繼續(xù)write。另外,有時(shí)候代碼中需要連續(xù)多次調(diào)用write,可能還來(lái)不及調(diào)用read得知對(duì)方已關(guān)閉了連接就被SIGPIPE信號(hào)終止掉了,這就需要在初始化時(shí)調(diào)用sigaction處理SIGPIPE信號(hào),如果SIGPIPE信號(hào)沒(méi)有導(dǎo)致進(jìn)程異常退出,write返回-1并且errno為EPIPE。
另外,我們需要修改server,使它可以多次處理同一客戶端的請(qǐng)求。
/* server.c */
#include <stdio.h>
#include <string.h>
#include <netinet/in.h>
#include "wrap.h"
#define MAXLINE 80
#define SERV_PORT 8000
int main(void)
{
struct sockaddr_in servaddr, cliaddr;
socklen_t cliaddr_len;
int listenfd, connfd;
char buf[MAXLINE];
char str[INET_ADDRSTRLEN];
int i, n;
listenfd = Socket(AF_INET, SOCK_STREAM, 0);
bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
servaddr.sin_port = htons(SERV_PORT);
Bind(listenfd, (struct sockaddr *)&servaddr, sizeof(servaddr));
Listen(listenfd, 20);
printf("Accepting connections ...\n");
while (1) {
cliaddr_len = sizeof(cliaddr);
connfd = Accept(listenfd,
(struct sockaddr *)&cliaddr, &cliaddr_len);
while (1) {
n = Read(connfd, buf, MAXLINE);
if (n == 0) {
printf("the other side has been closed.\n");
break;
}
printf("received from %s at PORT %d\n",
inet_ntop(AF_INET, &cliaddr.sin_addr, str, sizeof(str)),
ntohs(cliaddr.sin_port));
for (i = 0; i < n; i++)
buf[i] = toupper(buf[i]);
Write(connfd, buf, n);
}
Close(connfd);
}
}
經(jīng)過(guò)上面的修改后,客戶端和服務(wù)器可以進(jìn)行多次交互了。我們知道,服務(wù)器通常是要同時(shí)服務(wù)多個(gè)客戶端的,運(yùn)行上面的server和client之后,再開(kāi)一個(gè)終端運(yùn)行client試試,新的client能得到服務(wù)嗎?想想為什么。
怎么解決這個(gè)問(wèn)題?網(wǎng)絡(luò)服務(wù)器通常用fork來(lái)同時(shí)服務(wù)多個(gè)客戶端,父進(jìn)程專門(mén)負(fù)責(zé)監(jiān)聽(tīng)端口,每次accept一個(gè)新的客戶端連接就fork出一個(gè)子進(jìn)程專門(mén)服務(wù)這個(gè)客戶端。但是子進(jìn)程退出時(shí)會(huì)產(chǎn)生僵尸進(jìn)程,父進(jìn)程要注意處理SIGCHLD信號(hào)和調(diào)用wait清理僵尸進(jìn)程。
以下給出代碼框架,完整的代碼請(qǐng)讀者自己完成。
listenfd = socket(...);
bind(listenfd, ...);
listen(listenfd, ...);
while (1) {
connfd = accept(listenfd, ...);
n = fork();
if (n == -1) {
perror("call to fork");
exit(1);
} else if (n == 0) {
close(listenfd);
while (1) {
read(connfd, ...);
...
write(connfd, ...);
}
close(connfd);
exit(0);
} else
close(connfd);
}
現(xiàn)在做一個(gè)測(cè)試,首先啟動(dòng)server,然后啟動(dòng)client,然后用Ctrl-C使server終止,這時(shí)馬上再運(yùn)行server,結(jié)果是:
$ ./server
bind error: Address already in use
這是因?yàn)?,雖然server的應(yīng)用程序終止了,但TCP協(xié)議層的連接并沒(méi)有完全斷開(kāi),因此不能再次監(jiān)聽(tīng)同樣的server端口。我們用netstat命令查看一下:
$ netstat -apn |grep 8000
tcp 1 0 127.0.0.1:33498 127.0.0.1:8000 CLOSE_WAIT 10830/client
tcp 0 0 127.0.0.1:8000 127.0.0.1:33498 FIN_WAIT2 -
server終止時(shí),socket描述符會(huì)自動(dòng)關(guān)閉并發(fā)FIN段給client,client收到FIN后處于CLOSE_WAIT狀態(tài),但是client并沒(méi)有終止,也沒(méi)有關(guān)閉socket描述符,因此不會(huì)發(fā)FIN給server,因此server的TCP連接處于FIN_WAIT2狀態(tài)。
現(xiàn)在用Ctrl-C把client也終止掉,再觀察現(xiàn)象:
$ netstat -apn |grep 8000
tcp 0 0 127.0.0.1:8000 127.0.0.1:44685 TIME_WAIT -
$ ./server
bind error: Address already in use
client終止時(shí)自動(dòng)關(guān)閉socket描述符,server的TCP連接收到client發(fā)的FIN段后處于TIME_WAIT狀態(tài)。TCP協(xié)議規(guī)定,主動(dòng)關(guān)閉連接的一方要處于TIME_WAIT狀態(tài),等待兩個(gè)MSL(maximum segment lifetime)的時(shí)間后才能回到CLOSED狀態(tài),因?yàn)槲覀兿菴trl-C終止了server,所以server是主動(dòng)關(guān)閉連接的一方,在TIME_WAIT期間仍然不能再次監(jiān)聽(tīng)同樣的server端口。MSL在RFC1122中規(guī)定為兩分鐘,但是各操作系統(tǒng)的實(shí)現(xiàn)不同,在Linux上一般經(jīng)過(guò)半分鐘后就可以再次啟動(dòng)server了。至于為什么要規(guī)定TIME_WAIT的時(shí)間請(qǐng)讀者參考UNP 2.7節(jié)。
在server的TCP連接沒(méi)有完全斷開(kāi)之前不允許重新監(jiān)聽(tīng)是不合理的,因?yàn)椋琓CP連接沒(méi)有完全斷開(kāi)指的是connfd(127.0.0.1:8000)沒(méi)有完全斷開(kāi),而我們重新監(jiān)聽(tīng)的是listenfd(0.0.0.0:8000),雖然是占用同一個(gè)端口,但I(xiàn)P地址不同,connfd對(duì)應(yīng)的是與某個(gè)客戶端通訊的一個(gè)具體的IP地址,而listenfd對(duì)應(yīng)的是wildcard address。解決這個(gè)問(wèn)題的方法是使用setsockopt()設(shè)置socket描述符的選項(xiàng)SO_REUSEADDR為1,表示允許創(chuàng)建端口號(hào)相同但I(xiàn)P地址不同的多個(gè)socket描述符。在server代碼的socket()和bind()調(diào)用之間插入如下代碼:
int opt = 1;
setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));
有關(guān)setsockopt可以設(shè)置的其它選項(xiàng)請(qǐng)參考UNP第7章。
select是網(wǎng)絡(luò)程序中很常用的一個(gè)系統(tǒng)調(diào)用,它可以同時(shí)監(jiān)聽(tīng)多個(gè)阻塞的文件描述符(例如多個(gè)網(wǎng)絡(luò)連接),哪個(gè)有數(shù)據(jù)到達(dá)就處理哪個(gè),這樣,不需要fork和多進(jìn)程就可以實(shí)現(xiàn)并發(fā)服務(wù)的server。
/* server.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <netinet/in.h>
#include "wrap.h"
#define MAXLINE 80
#define SERV_PORT 8000
int main(int argc, char **argv)
{
int i, maxi, maxfd, listenfd, connfd, sockfd;
int nready, client[FD_SETSIZE];
ssize_t n;
fd_set rset, allset;
char buf[MAXLINE];
char str[INET_ADDRSTRLEN];
socklen_t cliaddr_len;
struct sockaddr_in cliaddr, servaddr;
listenfd = Socket(AF_INET, SOCK_STREAM, 0);
bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
servaddr.sin_port = htons(SERV_PORT);
Bind(listenfd, (struct sockaddr *)&servaddr, sizeof(servaddr));
Listen(listenfd, 20);
maxfd = listenfd; /* initialize */
maxi = -1; /* index into client[] array */
for (i = 0; i < FD_SETSIZE; i++)
client[i] = -1; /* -1 indicates available entry */
FD_ZERO(&allset);
FD_SET(listenfd, &allset);
for ( ; ; ) {
rset = allset; /* structure assignment */
nready = select(maxfd+1, &rset, NULL, NULL, NULL);
if (nready < 0)
perr_exit("select error");
if (FD_ISSET(listenfd, &rset)) { /* new client connection */
cliaddr_len = sizeof(cliaddr);
connfd = Accept(listenfd, (struct sockaddr *)&cliaddr, &cliaddr_len);
printf("received from %s at PORT %d\n",
inet_ntop(AF_INET, &cliaddr.sin_addr, str, sizeof(str)),
ntohs(cliaddr.sin_port));
for (i = 0; i < FD_SETSIZE; i++)
if (client[i] < 0) {
client[i] = connfd; /* save descriptor */
break;
}
if (i == FD_SETSIZE) {
fputs("too many clients\n", stderr);
exit(1);
}
FD_SET(connfd, &allset); /* add new descriptor to set */
if (connfd > maxfd)
maxfd = connfd; /* for select */
if (i > maxi)
maxi = i; /* max index in client[] array */
if (--nready == 0)
continue; /* no more readable descriptors */
}
for (i = 0; i <= maxi; i++) { /* check all clients for data */
if ( (sockfd = client[i]) < 0)
continue;
if (FD_ISSET(sockfd, &rset)) {
if ( (n = Read(sockfd, buf, MAXLINE)) == 0) {
/* connection closed by client */
Close(sockfd);
FD_CLR(sockfd, &allset);
client[i] = -1;
} else {
int j;
for (j = 0; j < n; j++)
buf[j] = toupper(buf[j]);
Write(sockfd, buf, n);
}
if (--nready == 0)
break; /* no more readable descriptors */
}
}
}
}
下圖是典型的UDP客戶端/服務(wù)器通訊過(guò)程。
以下是簡(jiǎn)單的UDP服務(wù)器和客戶端程序。

/**//* server.c */
#include <stdio.h>
#include <string.h>
#include <netinet/in.h>
#include "wrap.h"

#define MAXLINE 80
#define SERV_PORT 8000

int main(void)


{
struct sockaddr_in servaddr, cliaddr;
socklen_t cliaddr_len;
int sockfd;
char buf[MAXLINE];
char str[INET_ADDRSTRLEN];
int i, n;

sockfd = Socket(AF_INET, SOCK_DGRAM, 0);

bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
servaddr.sin_port = htons(SERV_PORT);
Bind(sockfd, (struct sockaddr *)&servaddr, sizeof(servaddr));

printf("Accepting connections
\n");

while (1)
{
cliaddr_len = sizeof(cliaddr);
n = recvfrom(sockfd, buf, MAXLINE, 0, (struct sockaddr *)&cliaddr, &cliaddr_len);
if (n == -1)
perr_exit("recvfrom error");
printf("received from %s at PORT %d\n",
inet_ntop(AF_INET, &cliaddr.sin_addr, str, sizeof(str)),
ntohs(cliaddr.sin_port));
for (i = 0; i < n; i++)
buf[i] = toupper(buf[i]);
n = sendto(sockfd, buf, n, 0, (struct sockaddr *)&cliaddr, sizeof(cliaddr));
if (n == -1)
perr_exit("sendto error");
}
}


/**//* client.c */
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <netinet/in.h>
#include "wrap.h"

#define MAXLINE 80
#define SERV_PORT 8000

int main(int argc, char *argv[])


{
struct sockaddr_in servaddr;
int sockfd, n;
char buf[MAXLINE];
char str[INET_ADDRSTRLEN];
socklen_t servaddr_len;
sockfd = Socket(AF_INET, SOCK_DGRAM, 0);

bzero(&servaddr, sizeof(servaddr));
servaddr.sin_family = AF_INET;
inet_pton(AF_INET, "127.0.0.1", &servaddr.sin_addr);
servaddr.sin_port = htons(SERV_PORT);

while (fgets(buf, MAXLINE, stdin) != NULL)
{
n = sendto(sockfd, buf, strlen(buf), 0, (struct sockaddr *)&servaddr, sizeof(servaddr));
if (n == -1)
perr_exit("sendto error");

n = recvfrom(sockfd, buf, MAXLINE, 0, NULL, 0);
if (n == -1)
perr_exit("recvfrom error");
Write(STDOUT_FILENO, buf, n);
}

Close(sockfd);
return 0;
}
由于UDP不需要維護(hù)連接,程序邏輯簡(jiǎn)單了很多,但是UDP協(xié)議是不可靠的,實(shí)際上有很多保證通訊可靠性的機(jī)制需要在應(yīng)用層實(shí)現(xiàn)。
編譯運(yùn)行server,在兩個(gè)終端里各開(kāi)一個(gè)client與server交互,看看server是否具有并發(fā)服務(wù)的能力。用Ctrl+C關(guān)閉server,然后再運(yùn)行server,看此時(shí)client還能否和server聯(lián)系上。和前面TCP程序的運(yùn)行結(jié)果相比較,體會(huì)無(wú)連接的含義。
問(wèn)題:數(shù)組查找它和數(shù)組排序一樣是重要的計(jì)算應(yīng)用之一,電話公司根據(jù)姓氏查找,能容易的找到用戶的電話號(hào)碼和繳費(fèi)情況,在學(xué)校成績(jī)管理系統(tǒng)可以根據(jù)學(xué)生的學(xué)號(hào),很容易就能查找到學(xué)生的成績(jī)及相關(guān)資料,查找在生活中的應(yīng)用是十分廣泛,數(shù)據(jù)排序是一個(gè)令人感興趣的問(wèn)題,這里深入理解兩種最基本的算法:線型查找和二分法查找。
線型查找:把數(shù)組的每一個(gè)元素和檢索關(guān)鍵字比較,安順序從第一個(gè)元素一直檢索到要查找的元素,平均來(lái)說(shuō),程序要把查找關(guān)鍵字與一半數(shù)組元素進(jìn)行比較。二分法查找:線型查找法對(duì)小型數(shù)組和未排序的數(shù)組效果較好,但是,對(duì)于大型數(shù)據(jù)來(lái)說(shuō),線型查找法效率較低。如果已經(jīng)對(duì)數(shù)組排序,那么可以使用速度很快的二分法查找.
程序1:線型查找法實(shí)現(xiàn)對(duì)某個(gè)數(shù)的查找!
#include<stdio.h>
#include<stdlib.h>
#define Size 100
int main()
{
int linearSearch(int a[],int key,int size);
int a[Size],i,searchKey,element;
for(i=0;i<Size-1;i++)
a[i]=2*i;
printf("Enter integer search key:\n");
scanf("%d",&searchKey);
element=linearSearch(a,searchKey,Size);
if(element!=-1)
printf("Found value in element %d !\n",element);
else
printf("Value is not found!\n");
system("pause");
}
int linearSearch(int array[],int key,int size)
{
int j;
for(j=0;j<Size-1;j++)
if(array[j]==key)
return j;
return -1;
}
程序2:二分法查找法實(shí)現(xiàn)對(duì)某個(gè)數(shù)的查找!
#include<stdio.h>
#include<stdlib.h>
#define Size 15
int main()
{
int binarySearch(int [],int,int,int);
void printHeader(void);
void printRow(int [],int,int,int);
int a[Size],i,key,element;
for(i=0;i<=Size-1;i++)
a[i]=2*i;
printf("Enter a number between 0 and 28:");
scanf("%d",&key);
printHeader();
element=binarySearch(a,key,0,Size-1);
if(element!=-1)
printf("\n%d found in array element %d !\n",key,element);
else
printf("\n%d is not found!\n",key);
system("pause");
}
void printHeader()
{
int i;
printf("\nSubscripts:\n");
for(i=0;i<=Size-1;i++)
printf("%3d",i);
printf("\n");
for(i=1;i<=4*Size;i++)
printf("-");
printf("\n");
}
int binarySearch(int array[],int searchKey,int low,int high)
{
void printRow(int array[],int low,int middle,int high);
int middle;
while(low<=high)
{
middle=(low+high)/2;
printRow(array,low,middle,high);
if(searchKey==array[middle])
return middle;
else if(searchKey<array[middle])
high=middle-1;
else
low=middle+1;
}
return -1;
}
void printRow(int array[],int low,int middle,int high)
{
int i;
for(i=0;i<=Size-1;i++)
if(i<low||i>high)
printf(" ");
else if(i==middle)
printf("%3d*",array[i]);
else
printf("%3d",array[i]);
printf("\n");
}
效率分析:線型查找擺脫了數(shù)組排序的約束,不足之處是不適合大型數(shù)據(jù)查找,并且查找方法比較老套,如果要找的數(shù)在數(shù)組中最后一個(gè)數(shù)n,那么搜索從0開(kāi)始,一直檢索到n,要經(jīng)過(guò)n次遍歷,時(shí)間復(fù)雜度:O(n),而二分查找法中如果查找關(guān)鍵字小于數(shù)組中間的元素,就查找數(shù)組的頭半部分,否則查找數(shù)組的后半部分,時(shí)間復(fù)雜度:O(log2n),如果在指定子數(shù)組中還沒(méi)有查找到關(guān)鍵字,就再把子數(shù)組折半,反復(fù)進(jìn)行這種查找,直到要查找的關(guān)鍵字等于子數(shù)組中間的元素,或沒(méi)有找到關(guān)鍵字為止。在最壞的情況下,用二分法查找有1024個(gè)元素的數(shù)組也只需要比較10次,即用2除1024,連續(xù)除10次得到1為止,如果有1048576(2的20次方)個(gè)元素,用二分法只要比較20次就可以找到要查找的元素,而用簡(jiǎn)單的線型查找則需要進(jìn)行2的20次方查找,可見(jiàn)二分法比線型查找法的效率要高得多,對(duì)10億哥元素的數(shù)組來(lái)說(shuō),平均比較5億次和30次簡(jiǎn)直是天壤之別!所以掌握二分法對(duì)在龐大的數(shù)組庫(kù)處理是很有效的!
問(wèn)題:數(shù)組排序(即按某種特定的順序排列數(shù)據(jù),如升序或降序)是最重要的計(jì)算應(yīng)用之一,銀行用帳號(hào)對(duì)所有的支票進(jìn)行能夠排序,并根據(jù)排序結(jié)果準(zhǔn)備月底的財(cái)務(wù)報(bào)告,學(xué)校學(xué)生成績(jī)管理系統(tǒng)用數(shù)組排序的方法將考試成績(jī)從高到低進(jìn)行排名,數(shù)組排序方法很多,有直接插入排序、冒泡排序、快速排序、直接選擇排序,下面來(lái)詳細(xì)介紹這四種基本的排序方法及其實(shí)現(xiàn)。
1,直接插入排序:當(dāng)數(shù)據(jù)表A中每個(gè)元素距其最終位置不遠(yuǎn),數(shù)據(jù)表A按關(guān)鍵字值基本有序,可用此方法排序較快。
2,冒泡排序法:將較小的值“上浮”到數(shù)組頂部,而較大值“下沉”到數(shù)組底部,這種排序技術(shù)要比較好幾趟,每一趟要比較連續(xù)的數(shù)組元素對(duì),如果某對(duì)數(shù)值是按升序排序的(或者這兩個(gè)值相等),那就保持原樣,如果某對(duì)數(shù)組是按降序排列的,就要交換它們的值。
3,快速排序法:快速排序是對(duì)冒泡排序的一種改進(jìn)。它的基本思想是:通過(guò)一躺排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按次方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過(guò)程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。
4,直接選擇排序法:直接選擇排序的作法是:第一趟掃描所有數(shù)據(jù),選擇其中最小的一個(gè)與第一個(gè)數(shù)據(jù)互換;第二趟從第二個(gè)數(shù)據(jù)開(kāi)始向后掃描,選擇最小的與第二個(gè)數(shù)據(jù)互換;依次進(jìn)行下去,進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過(guò)程。它比起冒泡排序有一個(gè)優(yōu)點(diǎn)就是不用不斷的交換。
程序1:直接插入法實(shí)現(xiàn)對(duì)數(shù)組的排序!
#include<stdio.h>
#include<conio.h>
int main()
{
void InsertSort(int [],int);
int a[7]={8,10,2,3,1,7,13};
int i;
InsertSort(a,7);
for(i=0;i<7;i++)
printf("%4d",a[i]);
getch();
}
void InsertSort(int a[],int count)
{
int i,j,temp;
for(i=1;i<count;i++)
{
temp=a[i];
j=i-1;
while(a[j]>temp && j>=0)
{
a[j+1]=a[j];
j--;
}
if(j!=(i-1))
a[j+1]=temp;
}
}
程序2:冒泡法實(shí)現(xiàn)對(duì)數(shù)組的排序!
#include<stdio.h>
#include<conio.h>
int main()
{
void BubbleSort(int []);
int a[10];
int i,j,temp;
printf("Input tem integer numbers for a[10]:");
for(i=0;i<10;i++)
scanf("%d,",&a[i]);
printf("\n");
BubbleSort(a);
printf("The sorted array is:\n");
for(j=0;j<10;j++)
printf("%d,",a[j]);
printf("\n\n");
getch();
}
void BubbleSort(int array[])
{
int i,j,temp;
for(j=0;j<9;j++)
for(i=0;i<9-j;i++)
if(array[i]>array[i+1])
{
temp=array[i];
array[i]=array[i+1];
array[i+1]=temp;
}
}
程序3:快速排序法實(shí)現(xiàn)對(duì)數(shù)組的排序!
#include<stdio.h>
#include<conio.h>
#define Max 8
int main()
{
void QuickSort(int a[],int p,int r);
int a[]={2,8,7,1,3,5,6,4};
QuickSort(a,1,Max);
printf(" The sorted array is :");
for(int i=0;i<Max;i++)
printf("%d,",a[i]);
printf("\n");
getch();
}
void QuickSort(int a[],int p,int r)
{
int Partition(int a[],int p,int r);
if(p<r)
{
int q=Partition(a,p,r);
QuickSort(a,p,q-1);
QuickSort(a,q+1,r);
}
}
int Partition(int a[],int p,int r)
{
int i=p-1;
int x=a[r-1];
for(int j=p;j<r;j++)
{
if(a[j-1]<=x)
{
i=i+1;
int temp;
temp=a[j-1];
a[j-1]=a[i-1];
a[i-1]=temp;
}
}
int temp;
temp=a[i];
a[i]=a[r-1];
a[r-1]=temp;
return i+1;
}
程序4:直接選擇法實(shí)現(xiàn)對(duì)數(shù)組的排序!
#include<stdio.h>
#include<conio.h>
int main()
{
void ChooseSort(int []);
int i,j,a[10];
printf("Input ten integer numbers for a[10]: ");
for(i=0;i<10;i++)
scanf("%d,",&a[i]);
printf("\n");
ChooseSort(a);
printf("The sorted array is:\n");
for(j=0;j<10;j++)
printf("%d,",a[j]);
printf("\n\n");
getch();
}
void ChooseSort(int array[])
{
int j,temp,*p1,*p2;
for(p1=array;p1<array+9;p1++)
{
j++;
for(p2=array+j;p2<=array+9;p2++)
if(*p2<*p1)
{
temp=*p2;
*p2=*p1;
*p1=temp;
}
}
}
各種排序方法的綜合比較:
一、時(shí)間性能
按平均的時(shí)間性能來(lái)分,四種類排序方法時(shí)間復(fù)雜度分別為:
直接插入排序法:O(n^2),冒泡排序法:O(n^2)快速排序法:O(nlogn),直接選擇排序法:O(n^2)
時(shí)間復(fù)雜度為O(n^2)的有:直接插入排序、起泡排序和簡(jiǎn)單選擇排序,其中以直接插入為最好,特別是對(duì)那些對(duì)關(guān)鍵字近似有序的記錄序列尤為如此;當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí),直接插入排序和起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度;而對(duì)于快速排序而言,這是最不好的情況,此時(shí)的時(shí)間性能蛻化為O(n2),因此是應(yīng)該盡量避免的情況。
二、排序方法的穩(wěn)定性能
1. 穩(wěn)定的排序方法指的是,對(duì)于兩個(gè)關(guān)鍵字相等的記錄,它們?cè)谛蛄兄械南鄬?duì)位置,在排序之前和經(jīng)過(guò)排序之后,沒(méi)有改變。
2. 當(dāng)對(duì)多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí),必須采用穩(wěn)定的排序方法。
3. 對(duì)于不穩(wěn)定的排序方法,只要能舉出一個(gè)實(shí)例說(shuō)明即可。
4. 快速排序是不穩(wěn)定的排序方法。
今天在準(zhǔn)備發(fā)布用VS2005寫(xiě)的那個(gè)程序時(shí),拷貝到我同事機(jī)器上,雙擊突然出現(xiàn)了“由于應(yīng)用程序的配置不正確,應(yīng)用程序未能啟動(dòng),重新安裝應(yīng)用程序可能會(huì)糾正這個(gè)問(wèn)題“,這個(gè)問(wèn)題很讓我意外,以前只出現(xiàn)過(guò)缺少DLL的情況,而這次出現(xiàn)這個(gè)問(wèn)題,讓我一時(shí)沒(méi)辦法。想想,無(wú)非是兩個(gè)原因引起的,要么是他沒(méi)有安裝VS2005的原因,要么是我的程序里依賴了其它的一些庫(kù)。于是百度一下,發(fā)現(xiàn)好多相關(guān)主題。我是按照這個(gè)帖子解決的:
在VS2005下用C++寫(xiě)的程序,在一臺(tái)未安裝VS2005的系統(tǒng)上,
用命令行方式運(yùn)行,提示:
“系統(tǒng)無(wú)法執(zhí)行指定的程序”
直接雙擊運(yùn)行,提示:
“由于應(yīng)用程序的配置不正確,應(yīng)用程序未能啟動(dòng),重新安裝應(yīng)用程序可能會(huì)糾正這個(gè)問(wèn)題”
以前用VC6和VS2003的話, 如果缺少庫(kù)文件,是會(huì)提示缺少“**.dll”,但是用VS2005卻沒(méi)有這樣的提示。
自己實(shí)驗(yàn)了一下,感覺(jué)以下幾種解決辦法是可行的:
方法一:
在類似C:\Program Files\Microsoft Visual Studio 8\VC\redi
st\Debug_NonRedist\x86\Microsoft.VC80.DebugCRT 下找到了下列文件:
msvcm80d.dll
msvcp80d.dll
msvcr80d.dll
Microsoft.VC80.DebugCRT.manifest
把這幾個(gè)文件拷貝到目標(biāo)機(jī)器上,與運(yùn)行程序同一文件夾或放到system32下,就可以正確運(yùn)行了。
其他release版、MFC程序什么的都是拷redist下相應(yīng)文件夾下的文件就可以了,文件夾后都有標(biāo)識(shí)!
方法二:
修改編譯選項(xiàng),將/MD或/MDd 改為 /MT或/MTd,這樣就實(shí)現(xiàn)了對(duì)VC運(yùn)行時(shí)庫(kù)的靜態(tài)鏈接,在運(yùn)行時(shí)就不再需要VC的dll了。
方法三:
工程-》屬性-》配置屬性-》常規(guī)-》MFC的使用,選擇“在靜態(tài)庫(kù)中使用mfc”
這樣生成的exe文件應(yīng)該就可以在其他機(jī)器上跑了。
方法四:
你的vc8安裝盤(pán)上找到再分發(fā)包vcredist_xxx.exe和你的程序捆綁安裝
C#調(diào)用c++制作的DLL時(shí),一些參數(shù)的賦值問(wèn)題如char *,結(jié)構(gòu)體
c++ dll中的原型
int test(char* xm,char* fa,UINT &VerNum,double Mile,char *SurvMile);
c#調(diào)用時(shí)
[DllImport(@"Test2.DLL")]
public static extern int test(string xm,string fa,ref UInt32 VerNum,double Mile, StringBuilder SurvMile);
注意:
1.調(diào)用的時(shí)候,有部分char* ,如果想獲得返回值,不能用string 作參數(shù)來(lái)進(jìn)行調(diào)用,這樣得不到返回到結(jié)果,可以用StringBuilder來(lái)聲明變
StringBuilder strMyTemp = new StringBuilder(256);//256是長(zhǎng)度
2.結(jié)構(gòu)體的引用傳遞
首先在c#中定義和c++相同的結(jié)構(gòu)體,如果是引用傳遞,在結(jié)構(gòu)體前面加上[In, Out]
[DllImport(@"test.dll")]
public static extern int test([In, Out] SLineData[] lndt,ref UInt32 length);
3.其他的類型如整形等等用ref加上數(shù)據(jù)變量則可獲得返回值
使用C++調(diào)用C#的DLL
SwfDotNet是C#編寫(xiě)的,作者的C#水平,真是令我佩服。這是個(gè)特別好的讀寫(xiě)Swf文件的庫(kù)。但是,我要用在C++項(xiàng)目中,怎么讓C++調(diào)用C#的DLL呢。今天一上午都在琢磨這個(gè)問(wèn)題,耽誤了很多時(shí)間,原因是編譯是出現(xiàn):
warning C4819: 該文件包含不能在當(dāng)前代碼頁(yè)(936)中表示的字符。請(qǐng)將該文件保存為 Unicode 格式以防止數(shù)據(jù)丟失。
接著就是一大堆的0x01等等。自己做了個(gè)Sample,仔細(xì)分析發(fā)現(xiàn)還是自己沒(méi)有搞清楚。正確的操作如下:
1 創(chuàng)建C# DLL,需要指定應(yīng)用類型為“類庫(kù)”,代碼:
namespace CSLib
{
public class Class1
{
private string name;
public string Name
{
get
{
return name;
}
set
{
name = "Your Name: " + value;
}
}
}
}
2 C++客戶程序,是個(gè)控制臺(tái)應(yīng)用,代碼:
#using "..\debug\CSLib.dll"
using namespace CSLib;
int _tmain(int argc, _TCHAR* argv[])
{
Class1 ^c = gcnew Class1();
c->Name = "zzj";
printf("%s\n", c->Name);
return 0;
}
3 幾點(diǎn)要記?。?br> 1 使用#using引用C# DLL,而不是#include。我就是想當(dāng)然的使用了后者,所以浪費(fèi)了一上午的時(shí)間;
2 別忘了using namespace CSLib;
3 使用C++/clr語(yǔ)法,采用正確的訪問(wèn)托管對(duì)象,即:使用帽子'^',而不是星星'*'(選擇菜單[項(xiàng)目]->[屬性],在其[屬性頁(yè)]中的[公共語(yǔ)言運(yùn)行庫(kù)支持]項(xiàng))
1、去掉Oracle生成的SQL創(chuàng)建語(yǔ)句中的雙引號(hào)
用powerdesigner導(dǎo)出orale數(shù)據(jù)庫(kù)的建表sql時(shí),默認(rèn)會(huì)給表名和字段名加上雙引號(hào),如下圖:

這樣給操作數(shù)據(jù)庫(kù)帶來(lái)很大的不便,解決的辦法是設(shè)置Database菜單,

然后點(diǎn)擊Edit Current DBMS菜單,再依次點(diǎn)開(kāi)Script->Format,然后找到CaseSensitivityUsingQuote
將其設(shè)為NO,即可。如下圖:

如果帶有包的話,導(dǎo)出時(shí)要選擇包中的表。
2、PowerDesign高級(jí)應(yīng)用
編寫(xiě)相關(guān)的VBS腳本在PowerDesign里自定義一些命令與操作等,具體的可以參考C:\Program Files\Sybase\PowerDesigner 9\VB Scripts目錄下的腳本示例。怎么運(yùn)用這些腳本呢?
在Tools->Execute Commands里可以進(jìn)行操作。具體說(shuō)明在幫助里寫(xiě)的很清楚。幫助的位置在 PowerDesigner General Features Guide-> PART 2. Modeling Guide->CHAPTER 8. Managing Objects->Accessing objects using VBScript->VBScript uses in PowerDesigner
PowerDesign的使用主要是DBMS的配置
3、修改建表腳本生成規(guī)則。
如果每個(gè)表格都有相同的字段,可以如下修改:
Database -> Edit Current DBMS 展開(kāi) Script -> Object -> Table -> Create 見(jiàn)右下的Value值,可以直接修改如下:
/* tablename: %TNAME% */
create table [%QUALIFIER%]%TABLE% (
%TABLDEFN%
ts char(19) null default convert(char(19),getdate(),20),
dr smallint null default 0
)
[%OPTIONS%]
其中的 ts、dr 兩列會(huì)在生成SQL腳本的時(shí)候自動(dòng)的插入每個(gè)表格中,其中的%TNAME% 變量是給每個(gè)表格的SQL添加一個(gè)該表的Name值注釋。
4、修改字段生成規(guī)則。
要給每個(gè)字段都添加一個(gè)注釋的話,同一窗口中展開(kāi) Script -> Object -> Column -> Add 的 Value修改為:
%20:COLUMN% [%COMPUTE%?AS (%COMPUTE%):%20:DATATYPE% [%IDENTITY%?%IDENTITY%:[%NULL%][%NOTNULL%]][ default %DEFAULT%]
[[constraint %CONSTNAME%] check (%CONSTRAINT%)]]/*%COLNNAME%*/
其中的%COLNNAME%就是列的Name值(可以是中文)
5、修改外鍵命名規(guī)則。
選擇Database—>Edit Current DBMS
選擇Scripts-》Objects-》Reference-》ConstName
可以發(fā)現(xiàn)右側(cè)的Value為:
FK_%.U8:CHILD%_%.U9:REFR%_%.U8:PARENT%
可見(jiàn),該命名方法是:'FK_'+8位子表名+9位Reference名+8位父表名,你可以根據(jù)這中模式自定義為:
FK_%.U7:CHILD%_RELATIONS_%.U7:PARENT%,
可以使FK名稱變?yōu)镕K_TABLE_2_RELATIONS_TABLE_1
掌握這種方法后就可以按照自己的想法修改了
生成建庫(kù)腳本SQL文件中的表頭注釋很討厭,可以在 Databse -> Generate Database (Ctrl+G)窗口中,選擇Options卡片,去掉Usage的Title鉤選項(xiàng)即可。
6、添加外鍵
Model -> References新建一條外鍵后,雙擊進(jìn)入外鍵屬性,在“Joins”卡片中可以選擇子表的外鍵字段。如下圖:

接著出現(xiàn)如下畫(huà)面:

按照步驟操作即可。
7、取消name和code聯(lián)動(dòng)
在修改name的時(shí)候,code的值將跟著變動(dòng),很不方便。修改方法:PowerDesign中的選項(xiàng)菜單里修改,在[Tool]-->[General Options]->[Dialog]->[Operating modes]->[Name to Code mirroring],這里默認(rèn)是讓名稱和代碼同步,將前面的復(fù)選框去掉就行了。如圖:

編寫(xiě)相關(guān)的VBS腳本在PowerDesign里自定義一些命令與操作等,具體的可以參考C:\Program Files\Sybase\PowerDesigner 9\VB Scripts目錄下的腳本示例。怎么運(yùn)用這些腳本呢?
在Tools-》Execute Commands里可以進(jìn)行操作。具體說(shuō)明在幫助里寫(xiě)的很清楚。幫助的位置在 PowerDesigner General Features Guide-> PART 2. Modeling Guide->CHAPTER 8. Managing Objects->Accessing objects using VBScript->VBScript uses in PowerDesigner
PowerDesign的使用主要是DBMS的配置
1、修改建表腳本生成規(guī)則。如果每個(gè)表格都有相同的字段,可以如下修改:
Database -> Edit Current DBMS 展開(kāi) Script -> Object -> Table -> Create 見(jiàn)右下的Value值,可以直接修改如下:
/* tablename: %TNAME% */
create table [%QUALIFIER%]%TABLE% (
%TABLDEFN%
ts char(19) null default convert(char(19),getdate(),20),
dr smallint null default 0
)
[%OPTIONS%]
其中的 ts、dr 兩列會(huì)在生成SQL腳本的時(shí)候自動(dòng)的插入每個(gè)表格中,其中的%TNAME% 變量是給每個(gè)表格的SQL添加一個(gè)該表的Name值注釋。
2、修改字段生成規(guī)則。要給每個(gè)字段都添加一個(gè)注釋的話,同一窗口中展開(kāi) Script -> Object -> Column -> Add 的 Value修改為:
%20:COLUMN% [%COMPUTE%?AS (%COMPUTE%):%20:DATATYPE% [%IDENTITY%?%IDENTITY%:[%NULL%][%NOTNULL%]][ default %DEFAULT%]
[[constraint %CONSTNAME%] check (%CONSTRAINT%)]]/*%COLNNAME%*/
其中的%COLNNAME%就是列的Name值(可以是中文)
3、修改外鍵命名規(guī)則。選擇Database—>Edit Current DBMS
選擇Scripts-》Objects-》Reference-》ConstName
可以發(fā)現(xiàn)右側(cè)的Value為:
FK_%.U8:CHILD%_%.U9:REFR%_%.U8:PARENT%
可見(jiàn),該命名方法是:'FK_'+8位子表名+9位Reference名+8位父表名,你可以根據(jù)這中模式自定義為:
FK_%.U7:CHILD%_RELATIONS_%.U7:PARENT%,
可以使FK名稱變?yōu)镕K_TABLE_2_RELATIONS_TABLE_1
掌握這種方法后就可以按照自己的想法修改了
生成建庫(kù)腳本SQL文件中的表頭注釋很討厭,可以在 Databse -> Generate Database (Ctrl+G)窗口中,選擇Options卡片,去掉Usage的Title鉤選項(xiàng)即可。
4、添加外鍵
Model -> References新建一條外鍵后,雙擊進(jìn)入外鍵屬性,在“Joins”卡片中可以選擇子表的外鍵字段
5、去掉生成的SQL腳本雙引號(hào)的問(wèn)題:ORACLE 8I2::Script\Sql\Format\CaseSensitivityUsingQuote改成No,默認(rèn)是Yes所以會(huì)有雙引號(hào)。
在修改name的時(shí)候,code的值將跟著變動(dòng),很不方便。修改方法:PowerDesign中的選項(xiàng)菜單里修改,在[Tool]-->[General Options]->[Dialog]->[Operating modes]->[Name to Code mirroring],這里默認(rèn)是讓名稱和代碼同步,將前面的復(fù)選框去掉就行了。