IP地址匹配

问题描述：
在路由器中，一般来说转发模块采用最大前缀匹配原则进行目的端口查找，具体如下：

IP地址和子网地址匹配：

IP地址和子网地址所带掩码做AND运算后，得到的值与子网地址相同，则该IP地址与该子网匹配。

比如：

IP地址：192.168.1.100

子网：192.168.1.0/255.255.255.0，其中192.168.1.0是子网地址，255.255.255.0是子网掩码。

192.168.1.100&255.255.255.0 = 192.168.1.0，则该IP和子网192.168.1.0匹配

IP地址：192.168.1.100

子网：192.168.1.128/255.255.255.192

192.168.1.100&255.255.255.192 = 192.168.1.64，则该IP和子网192.168.1.128不匹配

最大前缀匹配：

任何一个IPv4地址都可以看作一个32bit的二进制数，比如192.168.1.100可以表示为：11000000.10101000.00000001.01100100，

192.168.1.0可以表示为11000000.10101000.00000001.00000000

最大前缀匹配要求IP地址同子网地址匹配的基础上，二进制位从左到右完全匹配的位数尽量多（从左到右子网地址最长）。比如：

IP地址192.168.1.100，同时匹配子网192.168.1.0/255.255.255.0和子网192.168.1.64/255.255.255.192，

但对于子网192.168.1.64/255.255.255.192，匹配位数达到26位，多于子网192.168.1.0/255.255.255.0的24位，

因此192.168.1.100最大前缀匹配子网是192.168.1.64/255.255.255.192。

请编程实现上述最大前缀匹配算法。

要求实现函数：
void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n)

【输入】ip_addr：IP地址字符串，严格保证是合法IPv4地址形式的字符串

net_addr_array：子网地址列表，每一个字符串代表一个子网，包括子网地址和掩码，

表现形式如上述，子网地址和子网掩码用’/’分开，严格保证是

合法形式的字符串；如果读到空字符串，表示子网地址列表结束

【输出】n：最大前缀匹配子网在*net_addr_array[]数组中对应的下标值。如果没有匹配返回-1

示例
输入：

ip_addr = "192.168.1.100"

net_addr_array[] =

{

"192.168.1.128/255.255.255.192",

"192.168.1.0/255.255.255.0",

"192.168.1.64/255.255.255.192",

"0.0.0.0/0.0.0.0",

}

输出：n = 2

这题真麻烦，搞了好久~分高就是难

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<string.h>
  4 void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n)
  5 {
  6     int i,j,ip[4],mask[4],l,len,net[4],sum;
  7     const char *p;
  8     i = 0;
  9     l = 0;
 10     sum = 0;
 11     len = 0;
 12     *n = -1;
 13     p = ip_addr;
 14     while (*p != '')
 15         {
 16             j = 0;
 17             while (*p >= '0' && *p <= '9')
 18             {
 19                 int k = *p - '0';
 20                 j = j * 10 + k;
 21                 p++;
 22             }
 23             if (*p == ''){
 24                 ip[l++] = j;
 25                 break;
 26             }
 27             ip[l++] = j;
 28             p++;
 29         }
 30     l = 0;
 31     printf("ip:
");
 32     for (l=0; l < 4; l++)
 33         printf("%d ",ip[l]);
 34     printf("
");
 35     l = 0;
 36     while (*net_addr_array[i] != '' )
 37     {
 38         p = net_addr_array[i];
 39         while (*p != '/')
 40         {
 41             j = 0;
 42             while (*p >= '0' && *p <= '9')
 43             {
 44                 int k = *p - '0';
 45                 j = j * 10 + k;
 46                 p++;
 47             }
 48             net[l++] = j;
 49             if (*p == '/')
 50                 break;
 51             p++;
 52         }
 53         p++;
 54         l = 0;
 55         while (*p != '')
 56         {
 57             j = 0;
 58             while (*p >= '0' && *p <= '9')
 59             {
 60                 int k = *p - '0';
 61                 j = j * 10 + k;
 62                 p++;
 63             }
 64             if (*p == ''){
 65                 mask[l++] = j;
 66                 break;
 67             }
 68             mask[l++] = j;
 69             p++;
 70         }
 71         printf("
");
 72         for (l=0; l < 4; l++)
 73             printf("%d ",net[l]);
 74         printf("/ ");
 75         for (l=0; l < 4; l++)
 76             printf("%d ",mask[l]);
 77         printf("
cal ip & mask:
");
 78         for (l=0; l < 4; l++)
 79         {
 80             printf(" %d ",ip[l]&mask[l]);
 81             if ((ip[l]&mask[l]) != net[l])
 82                 break;
 83             int temp = mask[l];
 84             while(temp)
 85             {
 86 
 87                 if (temp & 0x00000001){
 88                     sum++;
 89                 }
 90                 temp = temp >> 1;
 91             }
 92         }
 93         if (l >= 4)
 94         {
 95             printf("
前缀长度：%d",sum);
 96             if (len <= sum)
 97                 {
 98                     *n = i;
 99                     len = sum;
100                 }
101         }
102         sum = 0;
103         i++;
104         l = 0;
105         printf("
");
106     }
107     printf("
");
108 }
109 int main()
110 {
111     char ip_addr[20] = "192.168.1.100";
112 
113     //ip_addr[13] = '';
114 
115     const char *net_addr_array[100] =
116 
117     {
118     "192.168.1.128/255.255.255.192",
119     "192.168.1.0/255.255.255.0",
120     "192.168.1.64/255.255.255.192",
121     "0.0.0.0/0.0.0.0",
122     ""
123     };
124     int *n;
125     n = (int*)malloc(sizeof(int));
126     max_prefix_match(ip_addr, net_addr_array, n);
127     printf("n = %d
",*n);
128 
129 }