华为校招上机及笔试

2. IP地址匹配（60分） 问题描述： 在路由器中，一般来说转发模块采用最大前缀匹配原则进行目的端口查找，具体如下： 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 #include<iostream> using namespace std; //void max_prefix_match(const char *ip_addr); //void max_prefix_match(const char *ip_addr, const char *net_addr_array[], int *n) void max_prefix_match(const char *ip_addr, const char *net_addr_array[],int lenth,int *n) { int count=0; int count1=0; int count2=0; int count3=0; int sum=0; int sum1=0; //int m=sizeof(net_addr_array)/sizeof(net_addr_array[0]);在这里m值不是字符串个数 //cout<<"m="<<m<<endl; int i,j,temp; int len=strlen(ip_addr); //int len1=strlen(net_addr_array[0]+10); int *a=new int[len]; int *b=new int[2*len+1]; int *c=new int[2*len+1]; int *d=new int[2*len+1]; c[0]=-1; //此处取出ip_addr的值，以整数形式表示 for(i=0;i<len;i++) { if(ip_addr[i]=='.') { a[count++]=sum; sum=0; continue; } else { sum=sum*10+(ip_addr[i]-'0'); } } a[count++]=sum;//之所以加这一句，是因为ip_addr不是以.结尾，上边的最后一个sum取不到 //将net_addr_array中的IP地址和子网掩码转化为整数 for(i=0;i<lenth;i++) { sum1=0; count1=0; for(j=0;j<strlen(net_addr_array[i]);j++) { if(net_addr_array[i][j]=='.') { b[count1++]=sum1; sum1=0; continue; } else if(net_addr_array[i][j]=='/') { b[count1++]=sum1; sum1=0; continue; } else { sum1=sum1*10+(net_addr_array[i][j]-'0'); } if(j==strlen(net_addr_array[i])-1) { b[count1++]=sum1; } } //这里输出取完以后的值 for(j=0;j<count1;j++) { cout<<b[j]<<" "; } cout<<endl; //ip地址以1.0.0.1开始，第一个肯定不能为0 if(b[0]==0) { continue; } //判断子网是否匹配 for(j=0;j<count;j++) { if((a[j]&b[j+4])==b[j]) { count2++; } if(count2==4) { c[count3]=i; d[count3]=b[j]; count3++; } } count2=0; } //对没有匹配子网进行处理 if(c[0]==-1) { cout<<"没有找到匹配的子网"<<endl; exit(1); } /*for(i=0;i<count3;i++) { cout<<"c[i]="<<c[i]<<" "; cout<<"d[i]="<<d[i]<<" "; } cout<<endl;*/ /*for(i=0;i<count;i++) cout<<a[i]<<" "; cout<<endl;*/ //按最大匹配原则，应将符合匹配条件中的b[3]最大值对应的字符串下标输出 for(i=0;i<count3-1;i++) for(j=0;j<count3-i-1;j++) { if(d[j]<d[j+1]) { temp=c[j]; c[j]=c[j+1]; c[j+1]=temp; temp=d[j]; d[j]=d[j+1]; d[j+1]=temp; } } for(i=0;i<count3;i++) { cout<<"c[i]="<<c[i]<<" "; cout<<"d[i]="<<d[i]<<" "; } cout<<endl; n=&c[0]; cout<<"最大前缀匹配子网在*net_addr_array[]数组中对应的下标值为:"<<endl; cout<<"n="<<*n<<endl; delete [] a; delete [] b; delete [] c; delete [] d; } int main() { const char *ip_addr="192.168.1.129"; const char *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",""}; int m=sizeof(net_addr_array)/sizeof(net_addr_array[0]); //cout<<"m="<<m<<endl; //cout<<*net_addr_array<<endl; int *n=NULL; max_prefix_match(ip_addr,net_addr_array,m,n); return 0; }