首页 > 代码库 > IP地址匹配
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 != ‘\0‘) 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 == ‘\0‘){ 24 ip[l++] = j; 25 break; 26 } 27 ip[l++] = j; 28 p++; 29 } 30 l = 0; 31 printf("ip:\n"); 32 for (l=0; l < 4; l++) 33 printf("%d ",ip[l]); 34 printf("\n"); 35 l = 0; 36 while (*net_addr_array[i] != ‘\0‘ ) 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 != ‘\0‘) 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 == ‘\0‘){ 65 mask[l++] = j; 66 break; 67 } 68 mask[l++] = j; 69 p++; 70 } 71 printf("\n"); 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("\ncal ip & mask:\n"); 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("\n前缀长度：%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("\n");106 }107 printf("\n");108 }109 int main()110 {111 char ip_addr[20] = "192.168.1.100";112 113 //ip_addr[13] = ‘\0‘;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",*n);128 129 }
IP地址匹配