华为机试题（4）
1、识别字符串中的整数并转换为数字形式void take_num(const char *strIn, int *n, unsigned int *outArray)
【输入】 strIn： 输入的字符串
【输出】 n： 统计识别出来的整数个数
outArray：识别出来的整数值，其中outArray是输入字符串中从左到右第一个整数，
outArray是第二个整数，以此类推。数组地址已经分配，可以直接使用
【返回】 无
注：
I、 不考虑字符串中出现的正负号(+, -)，即所有转换结果为非负整数（包括0和正整数）
II、 不考虑转换后整数超出范围情况，即测试用例中可能出现的最大整数不会超过unsigned int可处理的范围
III、 需要考虑 '0' 开始的数字字符串情况，比如 "00035" ，应转换为整数35；
"000" 应转换为整数0；"00.0035" 应转换为整数0和35（忽略小数点：mmm.nnn当成两个数mmm和nnn来识别）
IV、 输入字符串不会超过100 Bytes，请不用考虑超长字符串的情况。
示例
输入：strIn = "ab00cd+123fght456-25 3.005fgh"
输出：n = 6
outArray = {0, 123, 456, 25, 3, 5}
view plaincopyprint?
[*]#include<stdio.h>
[*]
#include<string.h>
[*]
[*]
voidtake_num(constchar*strIn,int*n,unsignedint*outArray)
[*]{
[*]unsignedintres;
[*]/*unsignedint*/
[*]intm=0;
[*]while(*strIn!='\0')
[*]{
[*]while(!(*strIn>='0'&&*strIn<='9')&&*strIn!='\0')
[*]strIn++;
[*]if(*strIn!='\0')
[*]{
[*]res=*strIn-'0';
[*]strIn++;
[*]while(*strIn>='0'&&*strIn<='9')
[*]{
[*]res=10*res+(*strIn-'0');
[*]strIn++;
[*]}
[*]outArray=res;
[*]m++;
[*]}
[*]}
[*]*n=m;
[*]}
[*]
[*]
intmain(/*intargc,char**argv*/)
[*]{
[*]intnum;
[*]inti;
[*]constcharstrIn="ab00cd+123fght456-253.005fgh";
[*]unsignedintoutArray;
[*]take_num(strIn,&num,outArray);
[*]for(i=0;i<num;i++)
[*]printf("%d",outArray);
[*]
[*]system("pause");
[*]return0;
[*]}
#include <stdio.h>
#include <string.h>
void take_num(const char *strIn, int *n, unsigned int *outArray)
{
unsigned int res;
/*unsigned int */
int m=0;
while(*strIn != '\0')
{
while(!(*strIn>='0' && *strIn <= '9') && *strIn != '\0')
strIn++;
if(*strIn != '\0')
{
res= *strIn-'0';
strIn++;
while(*strIn>='0' && *strIn <= '9')
{
res = 10*res+(*strIn-'0');
strIn++;
}
outArray =res;
m++;
}
}
*n = m;
}
int main(/*int argc, char **argv*/)
{
int num;
int i;
const char strIn="ab00cd+123fght456-253.005fgh";
unsigned int outArray;
take_num(strIn,&num,outArray);
for(i=0;i<num;i++)
printf("%d ",outArray);
system("pause");
return 0;
}
1、 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",
""
}
view plaincopyprint?
[*]#include<stdio.h>
[*]
#include<string.h>
[*]
[*]
voidmax_prefix_match(constchar*ip_addr,constchar*net_addr_array[],int*n)
[*]{
[*]intip,subnet_ip,subnet_mask;
[*]intip_pa,subnet_ip_pa,subnet_mask_pa;
[*]intindex;
[*]inti,result,cnt=0;
[*]intmaxi=0;
[*]sscanf(ip_addr,"%d.%d.%d.%d",&ip_pa,&ip_pa,&ip_pa,&ip_pa);
[*]ip=(ip_pa<<24)+(ip_pa<<16)+(ip_pa<<8)+(ip_pa);
[*]*n=-1;
[*]for(index=0;net_addr_array!='\0';index++)
[*]{
[*]sscanf(net_addr_array,"%d.%d.%d.%d/%d.%d.%d.%d",&subnet_ip_pa,&subnet_ip_pa,&subnet_ip_pa,&subnet_ip_pa,&subnet_mask_pa,&subnet_mask_pa,&subnet_mask_pa,&subnet_mask_pa);
[*]subnet_ip=(subnet_ip_pa<<24)+(subnet_ip_pa<<16)+(subnet_ip_pa<<8)+(subnet_ip_pa);
[*]subnet_mask=(subnet_mask_pa<<24)+(subnet_mask_pa<<16)+(subnet_mask_pa<<8)+(subnet_mask_pa);
[*]if((ip&subnet_mask)==subnet_ip)
[*]{
[*]//统计子网掩码中1的个数
[*]for(i=0;i<sizeof(subnet_mask)*8;i++)
[*]{
[*]result=subnet_mask&1;
[*]subnet_mask=subnet_mask>>1;
[*]cnt+=result;
[*]}
[*]if(cnt>maxi)
[*]{
[*]maxi=cnt;
[*]*n=index;
[*]}
[*]}
[*]
[*]}
[*]
[*]}
[*]
[*]
intmain(/*intargc,char**argv*/)
[*]{
[*]intn;
[*]constcharip_addr="192.168.1.100";
[*]constchar*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",
[*]""
[*]
[*]
[*]};
[*]max_prefix_match(ip_addr,net_addr_array,&n);
[*]
[*]printf("n=%d\n",n);
[*]
[*]system("pause");
[*]return0;
[*]}
页:
[1]