Socket网络编程--网络爬虫(2) - 无脑仔的小明

本邮件内容由第三方提供，如果您不想继续收到该邮件，可 点此退订 。

Socket网络编程--网络爬虫(2) - 无脑仔的小明  阅读原文»

　　上一小节，我们实现了下载一个网页。接下来的一步就是使用提取有用的信息。如何提取呢？一个比较好用和常见的方法就是使用正则表达式来提取的。想一想我们要做个什么样的网络爬虫好呢？我记得以前好像博客园里面有人写过一个提取博客园用户名的博客。我这次就实现这个好了。

　　第一步我们要分析博客园一个URL的组成，我们每一个用户对应都有这样的一个主目录http://www.cnblogs.com/XXXXXXX 这样的一个主页(现在有了http://XXXXXXX.cnblogs.com这样的主页了，但是不常用)。所以我们判断一个字符串是不是博客园的有效用户，我们的做法就是提取一个像上面一样的URL，然后截取后面的用户名即可。

　　带正则表达式的网页下载程序

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <sys/types.h>
5 #include <sys/socket.h>
6 #include <unistd.h>
7 #include <netdb.h>
8 #include <netinet/in.h>
9 #include <arpa/inet.h>
10 #include <regex.h>//正则表达式
11
12 #define BUF_SIZE 512
13
14 int reptile_regex(char * buf,char *pattern);
15
16 char ch[100000];//100k
17
18 int main(int argc,char *argv[])
19 {
20 struct sockaddr_in servAddr;
21 struct hostent * host;
22 int sockfd;
23 char sendBuf,recvBuf;
24 int sendSize,recvSize;
25
26 host=gethostbyname(argv[1]);
27 if(host==NULL)
28 {
29 perror("dns 解析失败");
30 }
31 servAddr.sin_family=AF_INET;
32 servAddr.sin_addr=*((struct in_addr *)host->h_addr);
33 servAddr.sin_port=htons(atoi(argv[2]));
34 bzero(&(servAddr.sin_zero),8);
35
36 sockfd=socket(AF_INET,SOCK_STREAM,0);
37 if(sockfd==-1)
38 {
39 perror("socket 创建失败");
40 }
41
42 if(connect(sockfd,(struct sockaddr *)&servAddr,sizeof(struct sockaddr_in))==-1)
43 {
44 perror("connect 失败");
45 }
46
47 //构建一个http请求
48 sprintf(sendBuf,"GET / HTTP/1.1 \r\nHost: %s \r\nConnection: Close \r\n\r\n",argv[1]);
49 if((sendSize=send(sockfd,sendBuf,BUF_SIZE,0))==-1)
50 {
51 perror("send 失败");
52 }
53 //获取http应答信息
54 memset(recvBuf,0,sizeof(recvBuf));
55 memset(ch,0,sizeof(ch));
56 char pattern[128]={0};
57 strcpy(pattern,"http://www.cnblogs.com/[[:alnum:]]*/");
58 while(recvSize=recv(sockfd,recvBuf,BUF_SIZE,0)>0)
59 {
60 //printf("%s",recvBuf);
61 strcat(ch,recvBuf);
62 memset(recvBuf,0,sizeof(recvBuf));
63 }
64 reptile_regex(ch,pattern);
65
66 return 0;
67 }
68
69
70 //第一个参数是要匹配的字符串，

滚动数组~\(���)/~ - PJQOOO  阅读原文»

今天第一次用了滚动数组，缘由要从一道题说起：POJ 1159 Palindrome

题意：给你一个字符串，求对字符串最少添加几个字符可变为回文串。

分析: 简单做法是直接对它和它的逆序串求最长公共子序列长度len。n-len即为所求。至于为什么，小盆友们可以自己模拟一下下。O(∩_∩)O~因为这不是我们今天讲的重点~噶呜

很明显这是一道LCS题，如果你还不知道什么是LCS，可以点击 LCS ，我们都知道要开辟一个dp[5001][5001]的数组来存LCS值，问题来了，当我开心的交上代码的时候竟然

内存超限了~！！看了下讨论组，说改成short int 能过，果然过了，但是memory==49156.。。太大了。上网一搜，发现了滚动数组这个东西，memory立即编程188K。啥都不说了，进入正题！

滚动数组的作用在于优化空间，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以

舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

一个DP，如果需要1000×1000的空间，其实根据DP的无后效性，可以开成2×1000，然后通过滚动，获得和1000×1000一样的效果。

滚动数组常用于DP之中，在DP过程中，我们在由一个状态转向另一个状态时，很可能之前存储的某些状态信息就已经无用了，例如在01背包问题中，从理解角度讲我们应开

DP[j]的二维数组，第一维我们存处理到第几个物品，也就是阶段了，第二维存储容量，但是我们获得DP,只需使用DP的信息，DP,k>1都成了无用空间，因此我们

可以将数组开成一维就行，迭代更新数组中内容，滚动数组也是这个原理，目的也一样，不过这时候的问题常常是不可能缩成一维的了，比如一个DP[j]需要由DP[k],

DP[k]决定，i<n，0<k<=10;n <=100000000;显然缩不成一维,正常我们应该开一个DP[100000005][11]的数组，结果很明显，超内存，其实我们只要开DP[3][11]

就够了DP[j]由DP[(i - 1)%3][k]和DP[(i - 2)%3][k]决定，空间复杂度差别巨大。

学以致用：http://poj.org/problem?id=1159 小盆友们快去做一做吧~噶呜~

本文链接：滚动数组~\(���)/~，转载请注明。

阅读更多内容