404频道

学习笔记

Posted on Edited on

第一遍阅读unpv3后，对书中讲述的内容有了大体的认识，但对书中的具体细节地方却是早已忘记。重新阅读unpv3，这次不希望仍然是阅后即忘，于是通过编写代码的方式对书中的例子和注意事项加深理解。

为了能够将书中的很多细节问题理解清楚并且便于记忆，本文采用了编写书中代码并运行的方式，并将书中容易出错和意想不到的问题记在代码中。

本文的代码实例并未完全按照书中的代码实例，本着单个文件即能编译通过并运行的原则，本文对于很多系统调用并未做防御式编程处理。针对每个版本的程序中缺点和注意事项在代码中已经进行了标注。

鉴于高性能的epoll机制出现比较晚，晚于unp的编写时间，书中并未做介绍。

TCP客户端程序

客户端函数执行效率情况：select非阻塞式I/O版本>线程化版本>fork版本>select阻塞式I/O版本>停等版本，停等版本的执行效率非常低，在实际生产环境中不建议使用。

其中poll和select机制基本类似，书中并未给出poll版本。

停-等版本

最常规的实现思路，但效率非常低，且当程序阻塞在读取要发送内容时，程序是无法收到服务端的状态变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
 * 停-等版本
 * 该版本缺陷为当服务端发生某些事件时，客户端可能仍然阻塞于fgets调用中
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */

void str_cli(FILE *fp, int sockfd)
{
	char sendline[MAXLINE], recvline[MAXLINE];
	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		/* 当阻塞在fgets函数时将服务器进程关闭时虽然给客户端发送了FIN信号，客户端并不会知道，
		 * 服务端关闭时第一次调用write服务器会返回RST，
		 * 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
		 * 该问题需要使用I/O复用技术来解决，或者使用fork处理的方式来解决
		 * */
		write(sockfd, sendline, strlen(sendline));
		int n = read(sockfd, recvline, MAXLINE);
		if (n == 0)
		{
			printf("str_cli: server terminated prematurely\n");
			exit(1);
		}

		// 向标准输出写内容，既可以使用write也可以使用fputs
		write(STDOUT_FILENO, recvline, n);

		// 使用fputs时需要注意将recvline数组有效内容的后面一位设置为'\0'
//		recvline[n] = '\0';
//		fputs(recvline, stdout);
	}
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	// 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
	// 最好的方式是忽略此信号的处理方式，并在程序下面处理该异常情况
	signal(SIGPIPE, SIG_IGN);

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr));

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

fork版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/**
 * 阻塞式I/O的fork版本
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */

/**
 * 即使服务端已经退出，子进程的read方法仍然能够感知到并且退出while循环，并给父进程发送SIGTERM,父进程对该信号的默认处理方式为退出
 * 优点：代码量比较少，每个进程只处理2个I/O流，从一个复制到另一个
 */
void str_cli(FILE *fp, int sockfd)
{
	char sendline[MAXLINE], recvline[MAXLINE];
	pid_t pid;
	if ((pid = fork()) == 0)
	{
		// child process : server -> stdout
		int n;
		while ((n = read(sockfd, recvline, MAXLINE)) > 0)
		{
			recvline[n] = '\0';
			fputs(recvline, stdout);
		}
		kill(getppid(), SIGTERM);
		exit(0);
	}

	// parent process : stdin -> server
	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		write(sockfd, sendline, strlen(sendline));
	}
	shutdown(sockfd, SHUT_WR);
	pause();
	return ;
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	// 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
	// 最好的方式是忽略此信号的处理方式，并在程序下面处理该异常情况
	signal(SIGPIPE, SIG_IGN);

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	if (connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) != 0)
	{
		printf("connect error...\n");
		exit(1);
	}

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

阻塞式I/O的select版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/**
 * 阻塞式I/O的select版本
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */

/**
 * 缺点：使用了阻塞式I/O，如果在向套接字调用write发送给服务器时，套接字缓冲区已满，write调用会阻塞，从而影响了后续的套接字缓冲区的读取
 */
void str_cli(FILE *fp, int sockfd)
{
	int maxfdp1;
	fd_set rset;
	char sendline[MAXLINE], recvline[MAXLINE];
	int stdineof = 0;
	FD_ZERO(&rset);
	for (; ;)
	{
		// select
		FD_SET(fileno(fp), &rset);
		FD_SET(sockfd, &rset);
		maxfdp1 = (fileno(fp) > sockfd ? fileno(fp) : sockfd) + 1;
		select(maxfdp1, &rset, NULL, NULL, NULL);

		// socket
		if (FD_ISSET(sockfd, &rset))
		{
			int n = read(sockfd, recvline, MAXLINE);
			if (n == 0)
			{
				if (stdineof == 1)
				{
					return ;
				}
				else
				{
					printf("str_cli: server terminated prematurely\n");
					exit(1);
				}
			}
			else if (n == -1)
			{
				exit(1);
			}
			recvline[n] = '\0';
			fputs(recvline, stdout);
//			write(STDOUT_FILENO, recvline, n);
		}

		// input
		if (FD_ISSET(fileno(fp), &rset))
		{
			// 此处不能使用fgets函数，该函数带有缓冲区功能，select跟带有缓冲区的c函数混合使用有问题
//			if (fgets(sendline, MAXLINE, fp) == NULL)
//			{
//				return ;
//			}
			int n = read(fileno(fp), sendline, MAXLINE);
			if (n == 0)
			{
				stdineof = 1;
				shutdown(sockfd, SHUT_WR);	// 关闭写
				FD_CLR(fileno(fp), &rset);
				continue;
			}
			else if (n == -1)
			{
				exit(1);
			}
			write(sockfd, sendline, n);
		}
	}
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	if (connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr)) != 0)
	{
		printf("connect error...\n");
		exit(1);
	}

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

非阻塞式I/O的select版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
/**
 * 非阻塞式I/O的select版本
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <fcntl.h>

#define SERV_PORT 9877
#define MAXLINE 4096	/* max text line length */
#define max(a,b) ( ((a)>(b)) ? (a):(b) )

/**
 * 优点：速度是最快的，可以防止进程在做任何工作时发生阻塞
 * 缺点：同时管理4个不同的I/O流，每个流都是非阻塞的，需要考虑到4个流的部分读和部分写问题。编码量是最多的，需要引入缓冲区管理机制。
 */
void str_cli(FILE *fp, int sockfd)
{
	// 将socket、标准输入和标准输出描述符设置为非阻塞方式
	int val = fcntl(sockfd, F_GETFL, 0);
	fcntl(sockfd, F_SETFL, val | O_NONBLOCK);

	val = fcntl(STDIN_FILENO, F_GETFL, 0);
	fcntl(STDIN_FILENO, F_SETFL, val | O_NONBLOCK);

	val = fcntl(STDOUT_FILENO, F_GETFL, 0);
	fcntl(STDOUT_FILENO, F_SETFL, val | O_NONBLOCK);

	char to[MAXLINE], fr[MAXLINE];
	char *toiptr, *tooptr, *friptr, *froptr;
	toiptr = tooptr = to;
	friptr = froptr = fr;
	int stdineof = 0;

	int maxfdp1 = max(max(STDIN_FILENO, STDOUT_FILENO), sockfd) + 1;
	fd_set rset, wset;
	for (; ;)
	{
		FD_ZERO(&rset);
		FD_ZERO(&wset);
		if (stdineof == 0 && toiptr < &to[MAXLINE])
		{
			FD_SET(STDIN_FILENO, &rset);
		}
		if (friptr < &fr[MAXLINE])
		{
			FD_SET(sockfd, &rset);
		}
		if (tooptr != toiptr)
		{
			FD_SET(sockfd, &wset);
		}
		if (froptr != friptr)
		{
			FD_SET(STDOUT_FILENO, &wset);
		}
		select(maxfdp1, &rset, &wset, NULL, NULL);	// select函数仍然是阻塞的
		// 标准输入
		if (FD_ISSET(STDIN_FILENO, &rset))
		{
			int n;
			if ((n = read(STDIN_FILENO, toiptr, &to[MAXLINE] - toiptr)) < 0)
			{
				// 对于非阻塞式IO，如果操作不能满足，相应系统调用会返回EWOULDBLOCK错误
				if (errno != EWOULDBLOCK)
				{
					printf("read error on stdin\n");
					exit(1);
				}
			}
			else if (n == 0)
			{
				fprintf(stderr, "EOF on stdin\n");
				stdineof = 1;
				if (tooptr == toiptr)
				{
					shutdown(sockfd, SHUT_WR);	// 缓冲区中没有数据要发送，关闭socket
				}
			}
			else
			{
				fprintf(stderr, "read %d bytes from stdin\n", n);
				toiptr += n;
				FD_SET(sockfd, &wset);
			}
		}

		// 从套接字读
		if (FD_ISSET(sockfd, &rset))
		{
			int n;
			if ((n = read(sockfd, friptr, &fr[MAXLINE] - friptr)) < 0)
			{
				if (errno != EWOULDBLOCK)
				{
					printf("read error on socket\n");
					exit(1);
				}
			}
			else if (n == 0)
			{
				fprintf(stderr, "EOF on socket\n");
				if (stdineof)
				{
					return ;
				}
				else
				{
					printf("server terminated prematurely\n");
					exit(1);
				}
			}
			else
			{
				fprintf(stderr, "read %d bytes from socket\n", n);
				friptr += n;
				FD_SET(STDOUT_FILENO, &wset);
			}
		}

		// 标准输出
		int n;
		if (FD_ISSET(STDOUT_FILENO, &wset) && ((n = friptr - froptr) > 0))
		{
			int nwritten;
			if ((nwritten = write(STDOUT_FILENO, froptr, n)) < 0)
			{
				if (errno != EWOULDBLOCK)
				{
					printf("write error to stdout\n");
					exit(1);
				}
			}
			else
			{
				fprintf(stderr, "wrote %d bytes to stdout\n", nwritten);
				froptr += nwritten;
				if (froptr == friptr)
				{
					froptr = friptr = fr;
				}
			}
		}

		// 向socket写
		if (FD_ISSET(sockfd, &wset) && ((n = toiptr - tooptr)) > 0)
		{
			int nwritten;
			if ((nwritten = write(sockfd, tooptr, n)) < 0)
			{
				if (errno != EWOULDBLOCK)
				{
					printf("write error to socket\n");
					exit(1);
				}
			}
			else
			{
				fprintf(stderr, "wrote %d bytes to socket\n", nwritten);
				tooptr += nwritten;
				if (tooptr == toiptr)
				{
					toiptr = tooptr = to;
					if (stdineof)
					{
						shutdown(sockfd, SHUT_WR);
					}
				}
			}
		}
	}

	return ;
}

/**
 * connect的非阻塞版本
 * 连接建立成功时，描述符变为可写；连接建立错误时，描述符变为即可读又可写
 * 优点：
 * 1、阻塞式的connect调用会消耗CPU时间，非阻塞式connect可以充分利用CPU时间，在等待的过程中可以处理其他工作
 * 2、可以同时建立多个连接，浏览器中会用到此技术
 * 3、阻塞式connect的函数超时过长，可以通过该函数设置超时时间
 * 4、阻塞式的套接字调用connect时，在TCP的三次握手完成之前被某些信号中断时并且connect未设置内核自动重启的标志时，connect将返回EINTR错误
 * 当再次调用connect等待未完成的连接时将会返回EADDRINUSE错误
 */
int connect_nonb(int sockfd, const struct sockaddr *saptr, socklen_t salen, int nsec)
{
	// 将套接字设置为非阻塞状态
	int flags = fcntl(sockfd, F_GETFL, 0);
	fcntl(sockfd, F_SETFL, flags | O_NONBLOCK);

	int error = 0;

	int n;
	if ((n = connect(sockfd, saptr, salen)) < 0)
	{
		// 连接未成功建立，正常情况下返回EINPROGRESS错误，表示操作正在处理
		if (errno != EINPROGRESS)
		{
			// EINPROGRESS表示连接建立已经启动，但是尚未完成
			return -1;
		}
	}
	else if (n == 0)
	{
		// 当服务器和客户端在一台主机上时会立即建立连接
		goto done;
	}

	// 当代码执行到如下过程中时，connect正在建立连接，可以在此位置执行业务相关代码
	// 当然真正使用时，在此位置加入其他代码并不合适，需要根据具体情况重新调整代码
	// 可以参照书中的web客户程序例子

	fd_set rset, wset;
	FD_ZERO(&rset);
	FD_SET(sockfd, &rset);
	wset = rset;

	struct timeval tval;
	tval.tv_sec = nsec;
	tval.tv_usec = 0;
	if ((n = select(sockfd + 1, &rset, &wset, NULL, nsec ? &tval : NULL)) == 0)
	{
		// 发生超时
		close(sockfd);
		errno = ETIMEDOUT;
		return -1;
	}

	// 当连接建立成功时sockfd变为可写，当连接建立失败时sockfd变为即可读又可写
	if (FD_ISSET(sockfd, &rset) || FD_ISSET(sockfd, &wset))
	{
		int len = sizeof(error);
		// 非可移植性函数，连接建立成功返回0，连接建立失败将错误值返回给error
		// 连接建立失败时，有返回-1和返回0的情况
		if (getsockopt(sockfd, SOL_SOCKET, SO_ERROR, &error, &len) < 0)
		{
			// solaris连接建立失败返回-1
			return -1;
		}
	}
	else
	{
		printf("select error:sockfd not set");
		exit(1);
	}
done:
	// 恢复套接字的文件状态标志
	fcntl(sockfd, F_SETFL, flags);
	if (error)
	{
		close(sockfd);
		errno = error;
		return -1;
	}
	return 0;
}

int main(int argc, char **argv)
{
	int sockfd;
	struct sockaddr_in	servaddr;

	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	// 当一个进程向某个收到RST的套接字执行写操作时，内核会向该进程发送一个SIGPIPE信号
	// 最好的方式是忽略此信号的处理方式，并在程序下面处理该异常情况
	signal(SIGPIPE, SIG_IGN);

	sockfd = socket(AF_INET, SOCK_STREAM, 0);

	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	//connect(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr));
	if (connect_nonb(sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr), 50) < 0)
	{
		printf("socket connect error\n");
		exit(1);
	}

	str_cli(stdin, sockfd);		/* do it all */

	exit(0);
}

TCP服务端程序

服务器程序要处理大量并发，在设计时更要注重效率。

fork版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/**
 * fork版本
 * PPC(Process per Connection)模型
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

void sig_chld(int signo)
{
	if (signo != SIGIO)
	{
		return;
	}
	int stat;

	/* 此处不可以使用wait函数，当多个SIGCHLD信号同时发出时会因为信号覆盖而出现僵尸进程的情况
	pid_t pid = wait(&stat);
	printf("child %d terminated\n", pid);	// 非异步信号安全函数，此处不应该调用
	*/

	/* 使用非阻塞的参数WNOHANG来循环处理信号，避免信号丢失问题 */
	pid_t pid;
	while ((pid = waitpid(-1, &stat, WNOHANG)) > 0)
	{
		printf("child %d terminated\n", pid);
	}
}

void str_echo(int sockfd)
{
	ssize_t	n;
	char buf[MAXLINE];

again:
	while ( (n = read(sockfd, buf, MAXLINE)) > 0)
	{
		write(sockfd, buf, n);
	}

	if (n < 0 && errno == EINTR)
		goto again;
	else if (n < 0)
		printf("str_echo: read error\n");
}

/**
 * fork版本
 * 缺点：
 * 		1.fork需要将父进程的内存映像复制到子进程，并在子进程中复制所有的描述符，尽管现在的操作系统已经都实现了写时复制技术，但是耗时仍然比较多
 * 		2.父进程和子进程之间需要IPC机制进行通信，从子进程返回信息到父进程比较麻烦
 */
int main(int argc, char *argv[])
{
	signal(SIGCHLD, sig_chld);
    int listenfd, connfd;
    pid_t childpid;
    struct sockaddr_in cliaddr, servaddr;

    // socket
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
		printf("socket error\n");
		exit(1);
	}

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }

    for ( ; ; )
    {
    	socklen_t clilen = sizeof(cliaddr);
    	// 处理accept被信号中断时返回EINTR错误
		if ((connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen)) < 0)
		{
			if (errno == EINTR)
			{
				continue;
			}
			else
			{
				printf("accept error");
				exit(1);
			}
		}

		if ((childpid = fork()) == 0)
		{
			/* child process */
			close(listenfd); /* close listening socket */
			str_echo(connfd); /* process the request */
			exit(0);
		}
		close(connfd); /* parent closes connected socket */
	}
}

select版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/**
 * select版本
 * 缺点：
 * 		1. 有最大并发数限制，一个进程最多打开FD_SETSIZE个文件描述符，FD_SETSIZE往往是1024或2048字节
 * 		2. select每次调用都会线性扫描全部的FD集合，这样效率就会呈现线性下降，把FD_SETSIZE改大的后果就是所有FD处理都慢慢来
 * 		3. 内核/用户空间内存拷贝问题，内核把FD消息通知给用户空间采取了内存拷贝方法
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <sys/select.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

/**
 * 使用select的需要维护client数组和allset的描述符集
 */
int main(int argc, char *argv[])
{
    struct sockaddr_in cliaddr, servaddr;

    // socket
    int listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
    	printf("socket error\n");
    	exit(1);
    }
    printf("finish socket...\n");

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }
    printf("finish bind...\n");

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }
    printf("finish listening...\n");

    int maxfd = listenfd;
    int maxi = -1;
    int client[FD_SETSIZE];
    for (int i=0; i<FD_SETSIZE; i++)
    {
    	client[i] = -1;
    }
    fd_set allset;
    FD_ZERO(&allset);
    FD_SET(listenfd, &allset);

    for ( ; ; )
    {
    	fd_set rset = allset;
    	int nready = select(maxfd + 1, &rset, NULL, NULL, NULL);
    	if (FD_ISSET(listenfd, &rset))
    	{
    		// 设置client数组
    		socklen_t clilen = sizeof(cliaddr);
    		// 调用select时有个问题，见书中16.6节
    		// 如果调用accept时客户端已经关闭连接，此时accept会阻塞并直到新的客户端连接到来
    		// 为了解决该问题可以将套接字设置为非阻塞再调用accept
			int connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen);
			printf("accept one client:%d...\n", connfd);
			int i = 0;
			for (; i<FD_SETSIZE; i++)
			{
				if (client[i] < 0)
				{
					client[i] = connfd;
					break;
				}
			}

			FD_SET(connfd, &allset);

			if (i == FD_SETSIZE)
			{
				printf("too many clients");
				exit(-1);
			}
			if (connfd > maxfd)
			{
				maxfd = connfd;
			}
			if (i > maxi)
			{
				maxi = i;
			}
			if (--nready <= 0)
			{
				continue;
			}
    	}

    	// 检测所有客户端的数据
    	for (int i=0; i<=maxi; i++)
    	{
    		if (client[i] < 0)
    		{
    			continue;
    		}
    		if (FD_ISSET(client[i], &rset))
    		{
    			int n;
    			char buf[MAXLINE];
    			printf("start reading form one client...\n");
    			if ((n = read(client[i], buf, MAXLINE)) == 0)
				{
    				close(client[i]);
    				FD_CLR(client[i], &allset);
    				client[i] = -1;
				}
    			else
    			{
    				write(client[i], buf, n);
    			}
    			if (--nready <= 0)
    			{
    				break;
    			}
    		}
    	}
	}
}

poll版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/**
 * poll版本
 * poll版本的解决了select文件描述符限制问题，但是仍然具备select的缺点中的2和3
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>
#include <poll.h>
#include <stropts.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */
#define OPEN_MAX 1024  // 该宏已经从limit.h中移除，用来表示一个进程可以打开的最大描述符数目

/**
 * 使用select的缺点为需要维护client数组
 */
int main(int argc, char *argv[])
{
    struct sockaddr_in cliaddr, servaddr;

    // socket
    int listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
    	printf("socket error\n");
    	exit(1);
    }
    printf("finish socket...\n");

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }
    printf("finish bind...\n");

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }
    printf("finish listening...\n");

    struct pollfd client[OPEN_MAX];
    client[0].fd = listenfd;
    client[0].events = POLLIN;
    for (int i=1; i<OPEN_MAX; i++)
    {
    	client[i].fd = -1;
    }

    int maxi = 0;	// 当前client正在使用的最大下标

    for ( ; ; )
    {
    	int nready = poll(client, maxi + 1, -1);
    	if (client[0].revents & POLLIN)
    	{
    		// 设置client数组
    		socklen_t clilen = sizeof(cliaddr);
			int connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen);
			printf("accept one client:%d...\n", connfd);
			int i = 1;
			for (; i<OPEN_MAX; i++)
			{
				if (client[i].fd < 0)
				{
					client[i].fd = connfd;
					break;
				}
			}

			if (i == OPEN_MAX)
			{
				printf("too many clients");
				exit(-1);
			}
			client[i].events = POLLIN;
			if (i > maxi)
			{
				maxi = i;
			}
			if (--nready <= 0)
			{
				continue;
			}
    	}

    	// 检测所有客户端的数据
    	for (int i=0; i<=maxi; i++)
    	{
    		if (client[i].fd < 0)
    		{
    			continue;
    		}
    		if (client[i].revents & (POLLIN | POLLERR))
    		{
    			int n;
    			char buf[MAXLINE];
    			printf("start reading form one client...\n");
    			if ((n = read(client[i].fd, buf, MAXLINE)) < 0)
				{
    				if (errno == ECONNRESET)
    				{
    					close(client[i].fd);
    					client[i].fd = -1;
    				}
    				else
    				{
    					printf("read client error\n");
    					exit(-1);
    				}
				}
    			else if (n == 0)
    			{
    				printf("client %d close\n", client[i].fd);
    				close(client[i].fd);
    				client[i].fd = -1;
    			}
    			else
    			{
    				write(client[i].fd, buf, n);
    			}
    			if (--nready <= 0)
    			{
    				break;
    			}
    		}
    	}
	}
}

多线程版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/**
 * 多线程版本
 * TPC(Thread Per Connection)模型
 * 线程的开销虽然比进程小，但是仍然有比较大开销，因此并发数不是很高
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>
#include <pthread.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

void str_echo(int sockfd)
{
	ssize_t	n;
	char buf[MAXLINE];

again:
	while ( (n = read(sockfd, buf, MAXLINE)) > 0)
	{
		write(sockfd, buf, n);
	}

	if (n < 0 && errno == EINTR)
		goto again;
	else if (n < 0)
		printf("str_echo: read error\n");
}

static void *doit(void *arg)
{
	pthread_detach(pthread_self());
	str_echo((int)arg);
	close((int)arg);
	printf("close socket...\n");
	return NULL;
}

int main(int argc, char *argv[])
{
    int listenfd, connfd;
    struct sockaddr_in cliaddr, servaddr;

    // socket
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if (listenfd == -1)
    {
		printf("socket error\n");
		exit(1);
	}

    // bind
    bzero(&servaddr, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(SERV_PORT);
    if (bind(listenfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) == -1)
    {
    	printf("bind error\n");
    	exit(1);
    }

    // listen
    // 套接字排队的最大连接数为20
    if (listen(listenfd, 20) == -1)
    {
    	printf("listen error\n");
    	exit(1);
    }

    for ( ; ; )
    {
    	socklen_t clilen = sizeof(cliaddr);
    	// 处理accept被信号中断时返回EINTR错误
		if ((connfd = accept(listenfd, (struct sockaddr*)&cliaddr, &clilen)) < 0)
		{
			if (errno == EINTR)
			{
				continue;
			}
			else
			{
				printf("accept error");
				exit(1);
			}
		}
		printf("receive new client...\n");
		pthread_t tid;
		pthread_create(&tid, NULL, &doit, (void *)connfd);
	}
}

UDP

由于udp比较简单，书中并未将udp协议当做重点来讲解。

UDP客户端程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

// sendto、recvfrom方式
void dg_cli(FILE *fp, int sockfd, const struct sockaddr *pservaddr, socklen_t servlen)
{
	char sendline[MAXLINE], recvline[MAXLINE + 1];
	struct sockaddr *preply_addr = (struct sockaddr *)malloc(servlen);

	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		sendto(sockfd, sendline, strlen(sendline), 0, pservaddr, servlen);
		int len = servlen;
		int n = recvfrom(sockfd, recvline, MAXLINE, 0, preply_addr, &len);
		// 为了防止接收到其他进程的数据，通过条件判断去除
		if (len != servlen || memcmp(pservaddr, preply_addr, len) != 0)
		{
			printf("reply from others (!ignore)\n");
			continue;
		}
		recvline[n] = 0;
		fputs(recvline, stdout);
	}
}

// connect、write、read方式
void dg_cli2(FILE *fp, int sockfd, const struct sockaddr *pservaddr, socklen_t servlen)
{
	char sendline[MAXLINE], recvline[MAXLINE + 1];

	connect(sockfd, (struct sockaddr *)pservaddr, servlen);

	while (fgets(sendline, MAXLINE, fp) != NULL)
	{
		write(sockfd, sendline, strlen(sendline));
		int n = read(sockfd, recvline, MAXLINE);
		recvline[n] = 0;
		fputs(recvline, stdout);
	}
}

int main(int argc, char *argv[])
{
	if (argc != 2)
	{
		printf("usage: tcpcli <IPaddress>\n");
		exit(1);
	}

	struct sockaddr_in servaddr;
	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_port = htons(SERV_PORT);
	inet_pton(AF_INET, argv[1], &servaddr.sin_addr);

	int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	dg_cli2(stdin, sockfd, (struct sockaddr*)&servaddr, sizeof(servaddr));
	exit(0);
}

UDP服务端程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

void dg_echo(int sockfd, struct sockaddr *pcliaddr, socklen_t clilen)
{
	char mesg[MAXLINE];
	for (;;)
	{
		socklen_t len = clilen;
		int n;
		bzero(mesg, MAXLINE);
		if ((n = recvfrom(sockfd, mesg, MAXLINE, 0,  pcliaddr, &len)) < 0)
		{
			close(sockfd);
			printf("recvfrom error, error=%m\n");
			exit(1);
		}
		printf("recv %s\n", mesg);
		sendto(sockfd, mesg, n, 0, pcliaddr, len);
	}
}

int main(int argc, char *argv[])
{
	int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	struct sockaddr_in servaddr, cliaddr;
	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(SERV_PORT);
	if (bind(sockfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0)
	{
		printf("bind error\n");
		exit(1);
	}

	dg_echo(sockfd, (struct sockaddr*)&cliaddr, sizeof(cliaddr));
}

UDP服务端信号驱动式I/O版本

信号驱动式I/O：进程执行I/O系统调用告知内核启动某个I/O操作，内核启动I/O操作后立即返回到进程。进程在I/O操作发生期间继续执行。当操作完成或遇到错误时，内核以进程在I/O系统调用中指定的方式通知进程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
/**
 * 信号驱动式I/O在TCP套接字用途不大，该信号产生的过于频繁，它的出现并未指示发生的事情
 */
#include <unistd.h>
#include <errno.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <stdio.h>
#include <signal.h>
#include <strings.h>
#include <fcntl.h>

#define SERV_PORT 9877
#define MAXLINE		4096	/* max text line length */

static int sockfd;

#define MAXDG 4096


typedef struct
{
	void *dg_data;				// 实际数据
	size_t dg_len;				// 实际数据长度
	struct sockaddr *dg_sa;		// 包含客户端地址
	socklen_t dg_salen;			// 客户端地址长度
} DG;

#define QSIZE 8
static DG dg[QSIZE];			// 存放数据的环形缓冲区

static long cntread[QSIZE + 1];
// 需要处理的下一个数据元素的下标
static int iget;
// 存放数据元素的下一个位置
static int iput;
static int nqueue;				// 队列中的数据个数
static socklen_t clilen;

static void sig_hup(int signo)
{
	int i=0;
	for (; i <= QSIZE; i++)
	{
		printf("cntread[%d = %ld\n", i, cntread[i]);
	}
}

static void sig_io(int signo)
{
	int nread;
	// 为了解决非实时信号不排队问题，采用循环读取方式
	for (nread = 0; ; )
	{
		// 检查队列是否已满
		if (nread >= QSIZE)
		{
			printf("receive overflow\n");
			exit(1);
		}
		DG *ptr = &dg[iput];
		ptr->dg_salen = clilen;
		ssize_t len = recvfrom(sockfd, ptr->dg_data, MAXDG, 0, ptr->dg_sa, &ptr->dg_salen);
		if (len < 0)
		{
			if (errno == EWOULDBLOCK)
			{
				break;
			}
			else
			{
				printf("recvfrom error\n");
				exit(1);
			}
		}
		ptr->dg_len = len;
		nread++;
		nqueue++;
		if (++iput >= QSIZE)
		{
			iput = 0;
		}
	}
	cntread[nread]++;
}

void dg_echo(int sockfd_arg, struct sockaddr *pcliaddr, socklen_t clilen_arg)
{
	sockfd = sockfd_arg;
	clilen = clilen_arg;
	int i = 0;
	for (; i<QSIZE; i++)
	{
		dg[i].dg_data = malloc(MAXDG);
		dg[i].dg_sa = (struct sockaddr *)malloc(clilen);
		dg[i].dg_salen = clilen;
	}
	iget = iput = nqueue = 0;
	signal(SIGHUP, sig_hup);

	// 在启动信号I/O前设置信号处理函数
	signal(SIGIO, sig_io);

	// 设置接收信号通知的进程，让本进程接收SIGIO信号
	fcntl(sockfd, F_SETOWN, getpid());

	// 为了能够在得到I/O事件后重复执行I/O操作，需要将文件描述符设置为非阻塞方式
	// O_ASYNC表示在文件描述符上使用信号驱动I/O
	int flags = fcntl(sockfd, F_GETFL);
	fcntl(sockfd, F_SETFL, flags | O_ASYNC | O_NONBLOCK);

	sigset_t zeromask, newmask, oldmask;
	sigemptyset(&zeromask);
	sigemptyset(&newmask);
	sigemptyset(&oldmask);

	// 设置新的信号掩码，阻塞SIGIO信号
	sigaddset(&newmask, SIGIO);
	sigprocmask(SIG_BLOCK, &newmask, &oldmask);
	for (; ;)
	{
		while (nqueue == 0)
		{
			// 挂起进程直到收到任何信号，该函数返回后SIGIO继续被阻塞
			sigsuspend(&zeromask);
		}
		// 解除SIGIO的阻塞
		sigprocmask(SIG_SETMASK, &oldmask, NULL);
		sendto(sockfd, dg[iget].dg_data, dg[iget].dg_len, 0, dg[iget].dg_sa, dg[iget].dg_salen);
		if (++iget >= QSIZE)
		{
			iget = 0;
		}
		// 为了能够修改nqueue的值，阻塞SIGIO信号
		sigprocmask(SIG_BLOCK, &newmask, &oldmask);
		nqueue--;
	}
}

int main(int argc, char *argv[])
{
	int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
	struct sockaddr_in servaddr, cliaddr;
	bzero(&servaddr, sizeof(servaddr));
	servaddr.sin_family = AF_INET;
	servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
	servaddr.sin_port = htons(SERV_PORT);
	if (bind(sockfd,  (struct sockaddr*)&servaddr, sizeof(servaddr)) < 0)
	{
		printf("bind error\n");
		exit(1);
	}

	dg_echo(sockfd, (struct sockaddr*)&cliaddr, sizeof(cliaddr));
	return 1;
}

相关下载

本文中的实例，代码采用eclipse CDT编写，可以直接导入eclipse中运行。

下载实例

Posted on Edited on

最近这段时间回顾了下python，距离上次使用python已经超过两年的时间了。

相对于c++语言，python要灵活许多，对于工作中的一些小问题的解决可以通过python来实现比较高效和方便，比如网页的抓取和解析。甚至对于非IT的工作，也可以通过脚本的方式来解决，只要是工作中遇到反复处理的体力活劳动就可以考虑利用编程方式来解决。

本文以我的博客的文档列表页面为例，利用python对页面中的文章名进行提取。

文章列表页中的文章列表部分的url如下：

1
2
3
4
5
6
7
<ul class="listing">
    <li class="listing-item"><span class="date">2014-12-03</span><a href="/post/linux_funtion_advance_feature"  title="Linux函数高级特性" >Linux函数高级特性</a>
    </li>
    <li class="listing-item"><span class="date">2014-12-02</span><a href="/post/cgdb"  title="cgdb的使用" >cgdb的使用</a>
    </li>
...
</ul>

requests模块的安装

requests模块用于加载要请求的web页面。

在python的命令行中输入import requests，报错说明requests模块没有安装。

我这里打算采用easy_install的在线安装方式安装，发现系统中并不存在easy_install命令，输入sudo apt-get install python-setuptools来安装easy_install工具。

执行sudo easy_install requests安装requests模块。

Beautiful Soup安装

为了能够对页面中的内容进行解析，本文使用Beautiful Soup。当然，本文的例子需求较简单，完全可以使用分析字符串的方式。

执行sudo easy_install beautifulsoup4即可安装。

编码问题

python的编码问题确实是一个很头大的问题，尤其是对于不熟悉python的菜鸟。

python自身的编码问题就已经够头大的了，碰巧requests模块也有一个编码问题的bug，具体的bug见参考文章。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#!/usr/bin/env python                                                                                                                                                           
# -*- coding: utf-8 -*-

' a http parse test programe '

__author__ = 'kuring lv'


import requests
import bs4

archives_url = "http://kuring.me/archive"

def start_parse(url) :
    print "开始获取(%s)内容" % url
    response = requests.get(url)
    print "获取网页内容完毕"
    
    soup = bs4.BeautifulSoup(response.content.decode("utf-8"))
    #soup = bs4.BeautifulSoup(response.text);
    
    # 为了防止漏掉调用close方法，这里使用了with语句
    # 写入到文件中的编码为utf-8
    with open('archives.txt', 'w') as f :
        for archive in soup.select("li.listing-item a") :
            f.write(archive.get_text().encode('utf-8') + "\n")
            print archive.get_text().encode('utf-8')

# 当命令行运行该模块时，__name__等于'__main__'
# 其他模块导入该模块时，__name__等于'parse_html'
if __name__ == '__main__' :
    start_parse(archives_url)

参考文章

Posted on Edited on

最近学习了《GNU Make项目管理》，改进了我之前一直在用的Makefile文件，解决我之前的Makefile中一直存在的修改依赖头文件后不能自动编译cpp文件的问题。本文列举了我常用的两个Makefile文件，其中第一个为我常用的Makefile，第二个为从网上找到的其他Makefile文件。

第一个Makefile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
all:
INCLUDE = -I./

FLAGS = -g -Wall $(INCLUDE)
FLAGS += -fPIC

LIBDIR = -lz -lm -lcrypto

LINK = $(LIBDIR) -lpthread

GCC = g++

# for C++ language
CODE.cpp = main.cpp \
			trim.cpp

CPP.o = $(CODE.cpp:.cpp=.o)
OBJS.d = $(CODE.cpp:.cpp=.d)

OBJS.o = $(CPP.o)

# 解决头文件依赖
-include $(subst .cpp,.d,$(CODE.cpp))

%.d: %.cpp
	$(GCC) -M $(FLAGS) $< > $@.$$$$;		\
	sed 's,\($*\)\.o[ :]*,\1.o $@ : ,g' < $@.$$$$ > $@;	\
	rm -f $@.$$$$

# rule for C++ language
%.o : %.cpp	
	$(GCC) $(FLAGS) -o $@ -c $<	
	@echo $*.o build successfully!......

TARGET = main
	
$(TARGET) : $(OBJS.o) 
	$(GCC) $(OBJS.o) -o $(TARGET) $(LINK)
	@echo $(TARGET) BUILD OK!.........

all : $(TARGET)

.PHONY:
clean:
	rm -rf $(TARGET)
	rm -rf $(OBJS.o)
	rm -rf $(OBJS.d)
	rm -rf *.d

该文件特点为需要手工将需要编译的源文件手动添加到Makefile中，可能比较麻烦，但是编译时比较灵活。可以随意修改需要编译源文件的顺序和是否需要编译源文件。

第二个Makefile

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
###########################################################
#
# KEFILE FOR C/C++ PROJECT
# Author: swm8023 <swm8023@gmail.com>
# Date:   2014/01/30
#
###########################################################

.PHONY: all clean
all: 

# annotation when release version
DEBUG       := y
TARGET_PROG := main

# project directory	
DEBUG_DIR   := ./Debug
RELEASE_DIR := ./Release
BIN_DIR     := $(if $(DEBUG), $(DEBUG_DIR), $(RELEASE_DIR))

# shell command
CC    := gcc
CXX   := g++
RM    := rm -rf
MKDIR := mkdir -p
SED   := sed
MV    := mv

# init sources & objects & depends
sources_all := $(shell find . -name "*.c" -o -name "*.cpp" -o -name "*.h")
sources_c   := $(filter %.c, $(sources_all))
sources_cpp := $(filter %.cpp, $(sources_all))
sources_h   := $(filter %.h, $(sources_all))
objs        := $(addprefix $(BIN_DIR)/,$(strip $(sources_cpp:.cpp=.o) $(sources_c:.c=.o)))
deps        := $(addprefix $(BIN_DIR)/,$(strip $(sources_cpp:.cpp=.d) $(sources_c:.c=.d)))

# create directory
$(foreach dirname,$(sort $(dir $(sources_c) $(sources_cpp))),\
  $(shell $(MKDIR) $(BIN_DIR)/$(dirname)))

# complie & link variable
CFLAGS     := $(if $(DEBUG),-g -O, -O2)
CFLAGS     += $(addprefix -I ,$(sort $(dir $(sources_h))))
CXXFLAGS    = $(CFLAGS)
LDFLAGS    := 
LOADLIBES  += #-L/usr/include/mysql
LDLIBS     += #-lpthread -lmysqlclient

# add vpath
vpath %.h $(sort $(dir $(sources_h)))
vpath %.c $(sort $(dir $(sources_c)))
vpath %.cpp $(sort $(dir $(sources_cpp)))

# generate depend files
# actually generate after object generated, beacasue it only used when next make)
ifneq "$(MAKECMDGOALS)" "clean"
sinclude $(deps)
endif

# make-depend(depend-file,source-file,object-file,cc)
define make-depend
  $(RM) $1;                                     \
  $4 $(CFLAGS) -MM $2 |                         \
  $(SED) 's,\($(notdir $3)\): ,$3: ,' > $1.tmp; \
  $(SED) -e 's/#.*//'                           \
         -e 's/^[^:]*: *//'                     \
         -e 's/ *\\$$//'                        \
         -e '/^$$/ d'                           \
         -e 's/$$/ :/' < $1.tmp >> $1.tmp;      \
  $(MV) $1.tmp $1;
endef

# rules to generate objects file
$(BIN_DIR)/%.o: %.c
	@$(call make-depend,$(patsubst %.o,%.d,$@),$<,$@,$(CC))
	$(CC) $(CFLAGS) -o $@ -c $<

$(BIN_DIR)/%.o: %.cpp
	@$(call make-depend,$(patsubst %.o,%.d,$@),$<,$@,$(CXX))
	$(CXX) $(CXXFLAGS) -o $@ -c $<

# add-target(target,objs,cc)
define add-target
  REAL_TARGET += $(BIN_DIR)/$1
  $(BIN_DIR)/$1: $2
	$3 $(LDFLAGS) $$^ $(LOADLIBES) $(LDLIBS) -o $$@
endef

# call add-target
$(foreach targ,$(TARGET_PROG),$(eval $(call add-target,$(targ),$(objs),$(CXX))))

all: $(REAL_TARGET) $(TARGET_LIBS)

clean: 
	$(RM) $(BIN_DIR)

该Makefile为从一个通用的C/C++ Makefile中直接获得的，为了避免原博客以后不能访问的情况，这里备份一下。

该Makefile可以动检测Makefile所在目录及其子目录中的.c和.cpp文件，并进行编译，不需要手动修改Makefile来填写需要编译的源文件，比较自动化。

相关参考

第二个Makefile文件的作者博客中的两篇文章：GNU Make学习总结（一）和GNU Make学习总结（二）

相关下载

一个包含上述两个Makefile的例子

Posted on Edited on

问题描述

一个最多包含n个正整数的文件，每个数小于n，其中n为10000000。要求升序排列整数列表，最多使用1MB的内存，运行时间尽可能短。

代码实现

#include <stdio.h>                                                                                                                                                              
#include <stdlib.h>

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000

int a[1 + N/BITSPERWORD] = {0};

/**
 * i>>SHIFT相当于i/32，用于确定i在第几个int数组中
 * 其中i&MASK含义为i%32，用于确定在int中的第几位
 */
void set(int i)
{
    a[i >> SHIFT] |= (1 << (i & MASK));
}

void clr(int i)
{
    a[i >> SHIFT] &= (0 << (i & MASK));
}

int test(int i)
{
    return a[i >> SHIFT] & (1 << (i & MASK));
}

int main(void)
{
    int i;
    while (scanf("%d", &i) != EOF)
    {
        set(i);
    }
    for (i=0; i<N; i++)
    {
        if (test(i))
        {
            printf("%d\n", i);
        }
    }
    return 0;
}

习题5

通过shell命令echo "scale=2; 10000000 / 1024 / 8 / 1024.0" | bc计算该程序运行时至少需要的存储空间为1.19MB，如果仅提供了1MB的存储空间，则需要更改上述程序的处理方式。

可采用多趟算法，多趟读入输入数据，每次完成一步。针对该题，可采用2步来完成，int数组的大小变更为5000000/8，比之前小了一半。第一步处理0-4999999之间的数据，第二步处理5000000-999999之间的数据。

习题6

如果是每个整数至少出现10次，而不是原先的一次。可以使用4bit来统计出现的次数，申请的数组大小变为了10000000/2。只要是每个整数有出现的最多次数上限该种处理方式就合适，当然整数出现的上限不能太大，否则该算法就没有了任何优势。

习题9

对一个大的数组的初始化操作需要耗费一些时间，为了消除数组的初始化，可以通过两个额外的数组来解决，这是典型的用空间换时间的方法。

      +---+---+---+---+---+---+---+----+
data  |   |   | 3 |   | 2 |   | 8 |    |
      +---+---+---+---+---+---+---+----+
                                        
      +---+---+---+---+---+---+---+----+
from  |   |   | 0 |   | 2 |   | 1 |    |
      +---+---+---+---+---+---+---+----+
                                        
      +---+---+---+---+---+---+---+----+
to    | 1 | 5 | 3 |   |   |   |   |    |
      +---+---+---+---+---+---+---+----+
                                        
                    ^                   
                    +                   
                   top

上图中data为要初始化的数组，from和to为辅助数组。如果data[i]已经初始化，则from[i]<top，to[from[i]]=i。from是一个简单的标识，to和top确保了from中不会写入内存中的随机内容。

习题11

该题的答案太他妈逗了，为了能够解决两地之间的数据传输瓶颈，作者给出的答案居然是用信鸽传输图片的底片后再将底片放大的方式来代替原先的用汽车运输的方式，这就是中国古代的飞鸽传书啊。

习题12

该题在《三傻大闹宝莱坞》中见过，这跟编程毛线关系也没有啊。

Posted on Edited on

本文以从服务器下载一个文件为例，讲解HTTP的断点续传功能。

客户端IP地址为：192.168.1.2
服务器IP地址为：192.168.1.3

客户端向服务器发送请求

客户端向服务器发送的请求为：

1
2
3
4
5
6
7
GET /deepc.a HTTP/1.1
Host: 192.168.100.189
Connection: keep-alive
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/30.0.1599.14 Safari/537.36
Accept-Encoding: gzip,deflate,sdch
Accept-Language: zh-CN,zh;q=0.8,en;q=0.6

从中可以看出请求的文件名为deepc.a文件。

客户端向服务器发送具体请求

1
2
3
4
5
6
7
8
9
GET /deepc.a HTTP/1.1
Host: 192.168.100.189
Connection: keep-alive
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/30.0.1599.14 Safari/537.36
Accept: */*
Referer: http://192.168.100.189/deepc.a
Accept-Encoding: gzip,deflate,sdch
Accept-Language: zh-CN,zh;q=0.8,en;q=0.6
Range: bytes=0-32767

Range字段表示请求文件的范围为0-32767。

服务器响应

第一次服务器的HTTP响应报文如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
GET /deepc.a HTTP/1.1
Host: 192.168.1.3
Connection: keep-alive
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/30.0.1599.14 Safari/537.36
Accept: */*
Referer: http://192.168.1.3/deepc.a
Accept-Encoding: gzip,deflate,sdch
Accept-Language: zh-CN,zh;q=0.8,en;q=0.6
Range: bytes=0-32767

HTTP/1.1 206 Partial Content
Date: Sun, 04 May 2014 05:14:54 GMT
Server: Apache/2.4.4 (Win32) PHP/5.4.16
Last-Modified: Sat, 03 May 2014 00:43:22 GMT
ETag: "7efce6-4f8742f6ed9b2"
Accept-Ranges: bytes
Content-Length: 32768
Content-Range: bytes 0-32767/8322278
Keep-Alive: timeout=5, max=100
Connection: Keep-Alive

HTTP的状态为206，表示服务器已经处理了部分HTTP相应。其中Content-Range字段表示服务器已经响应了0-32767个字节的文件内容。8322278表示文件的总长度为8322278字节。

客户端继续向服务器发送请求

客户端根据上次HTTP报文中服务器已经返回给的客户端的数据情况继续向服务器发送请求报文，向服务器发送的请求报文内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
GET /deepc.a HTTP/1.1
Host: 192.168.100.189
Connection: keep-alive
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/30.0.1599.14 Safari/537.36
Accept: */*
Referer: http://192.168.100.189/deepc.a
Accept-Encoding: gzip,deflate,sdch
Accept-Language: zh-CN,zh;q=0.8,en;q=0.6
Range: bytes=32768-8322277
If-Range: "7efce6-4f8742f6ed9b2"

HTTP/1.1 206 Partial Content
Date: Sun, 04 May 2014 05:14:54 GMT
Server: Apache/2.4.4 (Win32) PHP/5.4.16
Last-Modified: Sat, 03 May 2014 00:43:22 GMT
ETag: "7efce6-4f8742f6ed9b2"
Accept-Ranges: bytes
Content-Length: 8289510
Content-Range: bytes 32768-8322277/8322278
Keep-Alive: timeout=5, max=98
Connection: Keep-Alive

Content-Range的内容表示客户端向服务器请求文件中32768-8322277之间的字节数据。

第二次服务器的HTTP响应报文如下：

1
2
3
4
5
6
7
8
9
10
HTTP/1.1 206 Partial Content
Date: Sun, 04 May 2014 05:14:54 GMT
Server: Apache/2.4.4 (Win32) PHP/5.4.16
Last-Modified: Sat, 03 May 2014 00:43:22 GMT
ETag: "7efce6-4f8742f6ed9b2"
Accept-Ranges: bytes
Content-Length: 8289510
Content-Range: bytes 32768-8322277/8322278
Keep-Alive: timeout=5, max=98
Connection: Keep-Alive

表示服务器已经相应完成了32768-8322277之间的数据。

Posted on Edited on

为了避免linux下的控制台程序A死掉，可以通过一个另外一个程序B来监听A程序，当A程序异常退出时将B程序带起来。当然程序设计的最好方式为程序不崩溃，但是程序中存在bug很难避免，该方法还是有一定的实践意义。对于B程序可以通过shell脚本或者单独一个应用程序来解决。本文将通过shell脚本来解决此问题。

shell脚本的内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/bin/bash

check_process()
{
	# check parameter
	if [ $1 = "" ];
	then
		return -1
	fi

	# get the running process
	process_names=$(ps -ef | grep $1 | grep -v grep | awk '{print $8}')
	for process_name in $process_names
	do
		if [ $process_name = $1 ] ;
		then
			return 1
		fi
	done

	# not run and run the process
	echo "$(date) : process $1 not run, just run it"
	$1
	return 0
}

while [ 1 ];do
	check_process "/usr/bin/app/process"	# programe path
	sleep 5
done

将shell脚本在脱离控制台下可以运行

一旦断开了控制台，shell脚本就会由于接收到SIGHUP信号而退出。这里有两种思路来解决该问题，一种是通过系统的crontab来定期调用脚本程序，另外一种是通过神奇的screen程序来解决该问题，我这里通过screen程序来解决该问题，具体screen程序的应用见我的另外一篇文章《》。

应用程序为daemon方式运行

为了能够保证该脚本监控多个应用程序，需要将应用程序设置为daemon方式运行，可以调用函数daemon实现。也可以调用单独实现的daemon函数，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void init_daemon(void) 
{ 
    int pid; 
    int i;  

    if(pid=fork()) 
        exit(0);//是父进程，结束父进程 
    else if(pid< 0)  
        exit(1);//fork失败，退出 
    //是第一子进程，后台继续执行 

    setsid();//第一子进程成为新的会话组长和进程组长 
    //并与控制终端分离 
    if(pid=fork()) 
        exit(0);//是第一子进程，结束第一子进程 
    else if(pid< 0)  
        exit(1);//fork失败，退出 
    //是第二子进程，继续 
    //第二子进程不再是会话组长 

    for(i=0;i< NOFILE;++i)//关闭打开的文件描述符 
        close(i); 
    chdir("/tmp");//改变工作目录到/tmp 
    umask(0);//重设文件创建掩模 
    return; 
}

Posted on Edited on

在github上可以fork别人的项目成为自己的项目，但是当fork的项目更新后自己fork的项目应该怎么怎么更新呢？我从网上看到了两种方式，一种是采用github的web界面中的操作来实现，具体是通过“Pull Request”功能来实现；另外一种是通过在本地合并代码分支的方式来解决。本文将采用第二种方式，以我最近fork的项目为例来说明。

将fork后自己的项目clone到本地

执行git clone https://github.com/kuring/leetcode.git即可将自己fork的代码更新到本地。

fork完成后的远程分支和所有分支情况如下：

1
2
3
4
5
6
7
kuring@T420:/data/git/leetcode$ git remote -v
origin	https://github.com/kuring/leetcode.git (fetch)
origin	https://github.com/kuring/leetcode.git (push)
kuring@T420:/data/git/leetcode$ git branch -a
* master
  remotes/origin/HEAD -> origin/master
  remotes/origin/master

将fork之前的项目clone到本地

将fork之前的项目添加到本地的远程分支haoel中，执行git remote add haoel https://github.com/haoel/leetcode。

再查看一下远程分支和所有分支情况：

1
2
3
4
5
6
7
8
9
kuring@T420:/data/git/leetcode$ git remote -v
haoel	https://github.com/haoel/leetcode (fetch)
haoel	https://github.com/haoel/leetcode (push)
origin	https://github.com/kuring/leetcode.git (fetch)
origin	https://github.com/kuring/leetcode.git (push)
kuring@T420:/data/git/leetcode$ git branch -a
* master
  remotes/origin/HEAD -> origin/master
  remotes/origin/master

将远程代码halel分支fetch到本地

执行git fetch haoel，此时的所有分支情况如下，可以看出多了一个remotes/haoel/master分支。

1
2
3
4
5
kuring@T420:/data/git/leetcode$ git branch -a
* master
  remotes/haoel/master
  remotes/origin/HEAD -> origin/master
  remotes/origin/master

将halel分支merge到本地的分支

执行git merge remotes/haoel/master，此时发现有冲突，提示内容如下：

1
2
3
4
uring@T420:/data/git/leetcode$ git merge haoel/master
自动合并 src/reverseInteger/reverseInteger.cpp
冲突（内容）：合并冲突于 src/reverseInteger/reverseInteger.cpp
自动合并失败，修正冲突然后提交修正的结果。

之所以出现上述错误，这是由于我在fork之后在本地修正了源代码中的一处bug，而在fork之后到现在的时间间隔内原作者haoel也正好修正了该bug。打开文件后发现存在如下的内容，其实就是代码风格的问题，我这里将错误进行修正。

1
2
3
4
5
36 <<<<<<< HEAD                                                                                                                                                                
37     while( x != 0 ){
38 =======
39     while( x != 0){
40 >>>>>>> haoel/master

如果没有冲突的情况下通过merge命令即会将haoel/master分支合并master分支并执行commit操作。可以通过git status命令看到当前冲突的文件和已经修改的文件。执行git status命令可以看到如下内容，说明未冲突的文件已经在暂存区，冲突的文件需要修改后执行add操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
kuring@T420:/data/git/leetcode$ git status
位于分支 master
您的分支与上游分支 'origin/master' 一致。

您有尚未合并的路径。
  （解决冲突并运行 "git commit"）

要提交的变更：

	修改:         src/3Sum/3Sum.cpp
	修改:         src/4Sum/4Sum.cpp
	修改:         src/LRUCache/LRUCache.cpp
	......	// 此处省略了很多重复的
	......

未合并的路径：
  （使用 "git add <file>..." 标记解决方案）

	双方修改：     src/reverseInteger/reverseInteger.cpp

解决完冲突后执行add操作后再通过git status命令查看的内容如下。通过git status命令却看不到已经解决的冲突文件，对于这一点我还是很理解，参考文章中的Git 分支 - 分支的新建与合并是可以看到已经解决的冲突文件的，因为执行git add后将解决完成冲突的文件放到了暂存区中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
kuring@T420:/data/git/leetcode$ git status
位于分支 master
您的分支与上游分支 'origin/master' 一致。

所有冲突已解决但您仍处于合并中。
  （使用 "git commit" 结束合并）

要提交的变更：

	修改:         src/3Sum/3Sum.cpp
	修改:         src/4Sum/4Sum.cpp
	修改:         src/LRUCache/LRUCache.cpp
	......	// 此处省略了很多重复的
	......

这里冲突后merge操作并没有执行commit操作，需要解决冲突后再手工执行commit操作，此时整个的同步操作就已经完成了。

结尾

如果隔一段时间后又需要同步项目了仅需要执行git fetch haoel命令以下的操作即可。

参考

由于git命令较多，为了便于查阅增加一处git data transprot commands

Git图解

Posted on Edited on

问题

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

分析

要想能够生成多个树并存储到vector中，最容易想到的就是递归算法。要想能够递归，题目中提供的函数仅有一个参数，结合题目不能够完成递归的条件，考虑到unique binary search trees中的解法，需要递归具有两个参数的函数。

考虑到了递归的问题，还需要利用循环不断将树添加到vector中，这编写起来也是比较有难度，需要掌握循环的次数和什么时候将树添加到vector中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
vector<TreeNode *> generateTrees(int n) {
	vector<TreeNode *> sub_tree = generateTrees(1, n);
	return sub_tree;
}

vector<TreeNode *> generateTrees(int low, int high) {
	vector<TreeNode *> result;
	if (low > high)
	{
		result.push_back(NULL);
		return result;
	}
	else if (low == high)
	{
		TreeNode *node = new TreeNode(low);
		result.push_back(node);
		return result;
	}
	
	for (int i=low; i<=high; i++)
	{
		vector<TreeNode *> left = generateTrees(low, i - 1);
		vector<TreeNode *> right = generateTrees(i + 1, high);
		for (int j=0; j<left.size(); j++)
		{
			for (int k=0; k<right.size(); k++)
			{
				TreeNode *root = new TreeNode(i);
				root->left = left[j];
				root->right = right[k];
				result.push_back(root);
			}
		}
	}
	return result;
}

Posted on Edited on

图的存储

在leetcode中图的存储形式如下，这种形式的图只能适合用来存储是连通图的情况，且根据leetcode提供的_{0,1,2#1,2#2,2}_格式的字符串通过程序来自动构造图比较麻烦，预知字符串的含义请移步到leetcode的解释。

1
2
3
4
5
6
7
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };

本文为了能够用字符串表示所有图，并且便于程序的构造，使用了邻接表的形式来对图进行存储，即可以用来存储有向图，有可以存储无向图。图一个节点的结构如下：

1
2
3
4
5
6
7
8
9
/**
 * 图节点的邻接表表示形式
 */
struct GraphNode {
    std::string label;
    std::vector<GraphNode *> neighbors;
    bool visited;			// 深度优先搜索和广度优先搜索的遍历都需要visited数组，为了简化程序，直接在节点的存储结构中设置visited变量
    GraphNode(std::string x) : label(x), visited(false) {};
};

图的创建方面为了简化算法实现，对程序的效率没做太多关注，算法复杂度稍高。本算法的难点在于对字符串的拆解，并根据字符串找到对应的节点指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/**
 * 图节点的邻接表表示形式
 */
struct GraphNode {
    std::string label;
    std::vector<GraphNode *> neighbors;
    bool visited;
    GraphNode(std::string x) : label(x), visited(false) {};
};

/**
 * 通过字符串的值，找到该字符串对应的图节点
 */ 
GraphNode *get_one_node(const std::vector<GraphNode *> &node_vector, std::string str)
{
    for (std::vector<GraphNode *>::const_iterator iter = node_vector.begin(); iter != node_vector.end(); iter++)
    {
        if ((*iter)->label == str)
        {
            return *iter;
        }
    }
    return NULL;
}

/**
 * 时间复杂度高,对图的构建一般效率要求较低
 * 对于查找某个节点的邻接点的指针操作可以使用map来提高查询效率
 * 或者可以通过不需要初始化所有节点的方式来构造图，而是采用需要哪个节点构造哪个节点的方式
 */
std::vector<GraphNode *> create_graph(std::string str)
{
    std::vector<GraphNode *> node_vector;
   
    // init all nodes
    for (size_t pos = 0; pos < str.length() - 1;)
    {
        size_t end = str.find(',', pos);
        if (end != std::string::npos)
        {
            GraphNode *node = new GraphNode(str.substr(pos, end - pos));
            node_vector.push_back(node);
        }
        else
        {
            break;
        }

        pos = str.find('#', pos);
        if (pos == std::string::npos)
        {
            break;
        }
        else
        {
            pos++;
        }
    }

    // add neighbors in every node
    for (size_t pos = 0; pos < str.length() - 1; )
    {
        GraphNode *current_node = NULL;
        size_t current_end = str.find(',', pos);
        if (current_end != std::string::npos)
        {
            current_node = get_one_node(node_vector, str.substr(pos, current_end - pos));
            pos = current_end + 1;
        }
        else
        {
            break;
        }

        size_t node_end = str.find('#', pos);   // 当前节点的字符串的结束位置
        if (node_end == std::string::npos)
        {
            node_end = str.length();
        }
        else
        {
            node_end--;
        }

        for ( ; ; )
        {
            current_end = str.find(',', pos);
            if (current_end > node_end || current_end == std::string::npos)
            {
                // 一个节点的最后一个邻接点
                current_end = node_end;
            }
            else 
            {
                current_end--;
            }

            GraphNode *node = get_one_node(node_vector, str.substr(pos, current_end - pos + 1)); 
            if (node != NULL)
            {
                current_node->neighbors.push_back(node);
                std::cout << current_node->label << " add " << node->label << std::endl;
            }
            if (current_end == node_end)
            {
                // 一个节点的最后一个邻接点
                break;
            }
            else
            {
                pos = current_end + 2;  // 该节点之后还有其他邻接点
            }
        }
        pos = node_end + 2;
    }
    return node_vector;
}

深度优先搜索

深度优先搜索遵循贪心算法的原理，如果孩子节点不为空，则一直遍历下去。

递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void DFS_traverse_recursion(GraphNode *node)
{
    if (!node->visited)
    {
        std::cout << node->label << '\t';
        node->visited = true;
    }
    for (std::vector<GraphNode *>::iterator iter = node->neighbors.begin(); iter != node->neighbors.end(); iter++)
    {
        if (!(*iter)->visited)
        {
            DFS_traverse_recursion(*iter);
        }
    }
}

/**
 * 图的深度优先搜索的递归形式
 */
void DFS_traverse_recursion(std::vector<GraphNode *> &graph)
{
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        (*iter)->visited = false;
    }
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        if (!(*iter)->visited)
            DFS_traverse_recursion(*iter);
    }
}

非递归算法

使用栈来实现非递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 图的深度优先搜索的非递归形式
 */
void DFS_traverse_not_recursion(std::vector<GraphNode *> &graph)
{
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        (*iter)->visited = false;
    }

    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        std::stack<GraphNode *> node_stack;
        if ((*iter)->visited)
        {
            continue;
        }
        node_stack.push(*iter);
        while (!node_stack.empty())
        {
            GraphNode *node = node_stack.top();
            node_stack.pop();
            if (node->visited)
                continue;
            std::cout << node->label << '\t';
            node->visited = true;
            /* 使用反向迭代器遍历后将节点加入到栈中 */
            for (std::vector<GraphNode *>::reverse_iterator iter2 = node->neighbors.rbegin(); iter2 != node->neighbors.rend(); iter2++)
            {
                if (!(*iter2)->visited)
                {
                    node_stack.push(*iter2);
                }
            }
        }
    }
}

广度优先搜索

该算法不存在递归算法，仅有非递归版本。需要利用队列来保存需要遍历的节点，占用的存储空间稍多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 图的广度优先搜索的非递归形式
 */
void BFS_traverse_not_recursion(std::vector<GraphNode *> &graph)
{
    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        (*iter)->visited = false;
    }

    for (std::vector<GraphNode *>::iterator iter = graph.begin(); iter != graph.end(); iter++)
    {
        std::queue<GraphNode *> node_queue;
        if ((*iter)->visited)
        {
            continue;
        }
        node_queue.push(*iter);
        while (!node_queue.empty())
        {
            GraphNode *node = node_queue.front();
            node_queue.pop();
            if (node->visited)
                continue;
            std::cout << node->label << '\t';
            node->visited = true;
            for (std::vector<GraphNode *>::iterator iter2 = node->neighbors.begin(); iter2 != node->neighbors.end(); iter2++)
            {
                if (!(*iter2)->visited)
                {
                    node_queue.push(*iter2);
                }
            }
        }
    }
}

相关下载

本文相关源码

Posted on Edited on

[TOC]

近期准备复习数据结构和算法的知识，参照了网络上各路大神的学习攻略，大部分算法学习的思路为参照一些经典书籍（如算法导论）并结合一些代码的实践来完成，并未找到一条适合我的算法学习之路。经过思考后决定采用代码编写曾经的教科书中代码实例的方式来学习，曾经接触的算法教科书包括《数据结构（C语言版）》和《计算机算法基础》。一来这些算法已经基本熟悉，只是时间久远有些已经忘记；二来，通过思考后编写代码增强自己的记忆。

同时我编写的这些实例可以作为leetcode上的很多题目的基础，为下一个阶段刷leetcode上的题目打好基础。

树的存储形式包括了顺序存储（采用数组形式）和链式存储，其中链式存储更为灵活，可以表示任意形式的树，本文中的代码将采用树的链式存储方式。

树的构建

树的构建有多种方式，本文使用字符串采用了自顶向下、自左到右的顺序构建树，跟leetcode的形式一致。其中’#’表示该节点为空，如果该节点为空节点，其左右子孩子节点也要用’#’表示，而不能不用任何字符表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 二叉树的链式存储结构
 */
struct TreeNode
{
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(char data) : data(data), left(NULL), right(NULL) {}
};

/**
 * 构造二叉树，要构造的字符串采用了自顶向下、自左到右的顺序，跟leetcode的形式一致
 */
TreeNode *create_binary_tree(const char *str)
{
    if (!str || strlen(str) == 0)
    {
        return NULL;
    }

    // 对每个节点分配存储空间
    int node_size = strlen(str);
    TreeNode **tree = new TreeNode*[node_size];
    for (int i=0; i<node_size; i++)
    {
        if (str[i] == '#')
        {
            tree[i] = NULL;
        }
        else
        {
            tree[i] = new TreeNode(str[i]);
        }
    }

    for (int i=0, j=0; i<node_size && j<node_size; i++)
    {
        if (tree[i] != NULL)
        {
            if ((j + 1) < node_size)
            {
                tree[i]->left = tree[++j];
                tree[i]->right = tree[++j];
            }
        }
        else
        {
            j += 2;
        }
    }
    return *tree;
}

二叉树的先序遍历

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 先序遍历二叉树的递归形式
 */
void preorder_traverse_recursion(TreeNode *root)
{
    if (!root)
    {
        return;
    }
    
    printf("%c\t", root->data);
    
    preorder_traverse_recursion(root->left);

    preorder_traverse_recursion(root->right);
}

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 先序遍历的非递归形式
 */
void preorder_traverse_not_recursion(TreeNode *root)
{
    if (!root)
    {
        return ;
    }
    std::stack<TreeNode *> tree_stack;
    tree_stack.push(root);
    while (tree_stack.size() > 0)
    {
        TreeNode *node = tree_stack.top();
        tree_stack.pop();
        printf("%c\t", node->data);
        if (node->right != NULL)
        {
            tree_stack.push(node->right);   
        }
        if (node->left != NULL)
        {
            tree_stack.push(node->left);
        }
    }
}

二叉树的中序遍历

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 中序遍历二叉树的递归形式
 */
void inorder_traverse_recursion(TreeNode *root)
{
    if (!root)
    {
        return;
    }
    
    inorder_traverse_recursion(root->left);
    
    printf("%c\t", root->data);

    inorder_traverse_recursion(root->right);
}

非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 中序遍历二叉树的非递归形式
 */
void inorder_traverse_not_recursion(TreeNode *root)
{
    if (!root)
    {
        return ;
    }
    std::stack<TreeNode *> tree_stack;
    while (root != NULL || tree_stack.size() > 0)
    {
        // 遍历到左子树的叶子节点
        while (root)
        {
            tree_stack.push(root);
            root = root->left;
        }

        // 遍历栈顶节点
        root = tree_stack.top();
        tree_stack.pop();
        printf("%c\t", root->data);

        root = root->right;
    }
}

二叉树的后序遍历

递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 后序遍历二叉树的递归形式
 */
void postorder_traverse_recursion(TreeNode *root)
{
    if (!root)
    {
        return;
    }
    
    postorder_traverse_recursion(root->left);
    
    postorder_traverse_recursion(root->right);

    printf("%c\t", root->data);
}

非递归实现

仅用一个栈不能够实现后序遍历非递归算法，需要保存一个上次访问过节点的变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 后序遍历二叉树的非递归形式
 */
void postorder_traverse_not_recursion(TreeNode *root)
{
    if (!root)
    {
        return ;
    }
    std::stack<TreeNode *> tree_stack;
    TreeNode *visited = NULL;
    while (root != NULL || tree_stack.size() > 0)
    {
        // 遍历到左子树的叶子节点
        while (root)
        {
            tree_stack.push(root);
            root = root->left;
        }

        root = tree_stack.top();

        if (root->right == NULL || root->right == visited)
        {
            // 如果没有右孩子，或者右孩子刚刚访问过，则访问当前节点
            printf("%c\t", root->data);
            tree_stack.pop();
            visited = root;
            root = NULL;
        }
        else
        {
            root = root->right;
        }
    }
}

总结

二叉树遍历的递归形式程序结构类似，编写相对简单。但是递归方法在C语言中存在执行效率差（需要维护函数栈），容易出现栈溢出的异常的问题。任何递归问题问题都可以转化为非递归问题，转化的思路包括了直接转化法和间接转化法。直接转化法可以通过循环来解决，间接转化法需要借助栈加循环来解决。

二叉树遍历的非递归形式相对复杂，二叉树的先序遍历的非递归形式容易理解，二叉树的中序遍历稍微困难，后序遍历的非递归形式最复杂。

相关下载

程序源代码

0%