识别有效的IP地址和掩码并进行分类统计
Published in：2024-12-19 |

识别有效的IP地址和掩码并进行分类统计

在本题中，我们需要处理地址信息，其由 IP 地址和子网掩码组成，这两者均形如 "*.*.*.*" ，由四段数字组成，每段数字之间以点分隔。

我们定义五类 IP 地址：

  • A类：”1.0.0.0”-“126.255.255.255”；
  • B类：”128.0.0.0”-“191.255.255.255”；
  • C类：”192.0.0.0”-“223.255.255.255”；
  • D类：”224.0.0.0”-“239.255.255.255”；
  • E类：”240.0.0.0”-“255.255.255.255”。

我们定义私有 IPIP 地址：

  • “10.0.0.0”-“10.255.255.255”；
  • “172.16.0.0”-“172.31.255.255”；
  • “192.168.0.0”-“192.168.255.255”。

我们定义合法的子网掩码：

  • 将 IP 地址转换为二进制后，必须由若干个连续的 1 后跟若干个连续的 0 组成；
  • 例如，”1.1.1.5” 是一个非法的子网掩码，因为它转换为二进制后为 1.1.1.101 ，中间出现了 0 后又出现了 1 ；
  • 注意，全为 1 或全为 0 的子网掩码也是非法的。

现在，你需要分类统计ABCDE类地址的数量、错误 IP 或错误子网掩码的数量、私有 IP 的数量。

特别地，我们还有以下提示：

  • 类似于 "0.*.*.*" 和 "127.*.*.*" 的 IP 地址不属于上述输入的任意一类，也不属于不合法 IP 地址；
  • 一个 IP 地址既可以是私有 IP 地址，也可以是五类 IP 地址之一，计数时请分别计入。

输入描述：

本题将会给出 1≦T≦1000 条地址信息，确切数字未知，您需要一直读入直到文件结尾；每条地址信息描述如下：

在一行上先输入一个字符串，代表 IP 地址；随后，在同一行输入一个字符串，代表子网掩码；使用 “~” 分隔。

输出描述：

在一行上输出七个整数，分别代表ABCDE类地址的数量、错误 IP 或错误子网掩码的数量、私有 IP 的数量。

示例1

输入：

1
2
3
4
10.70.44.68~1.1.1.5
1.0.0.1~255.0.0.0
192.168.0.2~255.255.255.0
19..0.~255.255.255.0

输出：

1
1 0 1 0 0 2 1

说明：

1
2
3
4
对于第一条地址信息，"10.70.44.68""10.70.44.68" 是其 IPIP 地址，"255.254.255.0""255.254.255.0" 是其子网掩码；该条地址的子网掩码非法。
对于第二条地址信息，IPIP 地址和子网掩码均无误，且属于A类地址。
对于第三条地址信息，IPIP 地址和子网掩码均无误，且属于C类地址，同时属于私有 IPIP 地址。
对于第四条地址信息，IPIP 地址非法。

示例2

输入：

1
2
0.201.56.50~255.255.255.0
127.201.56.50~255.255.111.255

输出：

1
0 0 0 0 0 0 0

说明：

1
2
对于第一、二条地址信息，均属于上方提示中提到的特殊 IPIP 地址，不需要处理，直接跳过。
特别地，第二条地址的子网掩码是非法的。但是因为该条为特殊 IPIP 地址，此优先级更高，所以不进入统计。

问题分析

  • IPv4 地址点分十进制表示形如 129.244.251.53 ，共有4个字段，中间由点隔开。每个字段的值是 0 ~ 255 共 256 个值，每个值可以保存在一个字节中（unsigned char）。sizeof(int) 等于 4个 字节，所以可以将一个 IP 地址转换成一个 unsigned int 数值。
  • A 类地址段 "1.0.0.0"-"126.255.255.255" ，值的范围为 .
    • A类地址范围包含了一段私有地址段 "10.0.0.0"-"10.255.255.255" ，其值对应的范围为： .
  • B类地址段 "128.0.0.0"-"191.255.255.255" ，值的范围为 .
    • B类地址中包含了一段私有地址段 "172.16.0.0"-"172.31.255.255" ，值的范围 .
  • C类地址段 "192.0.0.0"-"223.255.255.255"， .
    • C类地址段中包含了一段私有地址 "192.168.0.0"-"192.168.255.255" ，.
  • D类 "224.0.0.0"-"239.255.255.255" ， .
  • E类，题目中的描述的地址段是 "240.0.0.0"-"255.255.255.255" ，根据计算机网络的知识，255.255.255.255 是一个特殊的 广播地址，专门用于局域网中的广播通信，不算是 E 类IP地址。所以数值范围是左闭右开的 .
  • 根据题意，只有子网掩码合法的情况下，才对IP地址进行判断是否合法和分类。
  • 根据题意，0.*.*.* 和 127.*.*.* 地址段，无论子网掩码是否合法都不列统计范围。

算法设计思路

写一个函数 unsigned int strToIP(char* ipstr); ，可以将字符串的 IP 地址或子网掩码转换成一个 unsigned int 型的数值。如果 IP 地址格式错误返回 -1 。 (-1 的补码为 1111 1111 1111 1111 1111 1111 1111 1111 对应了 255.255.255.255 的地址）。

写一个函数 int isCorrectSubnetMask(unsigned int subnet_mask);，用于判断子网掩码是否合法，合法返回 1，否则返回 0 。

strToIP 函数的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
unsigned int strToIP(char* ipstr) {   // 形如"192.168.233.12."的IP地址字符串转换成数值
    unsigned int ip = 0;
    char num[3];    //IP地址一个十进制字段最多只能有三个字符（255）
    unsigned char count = 0;   //num的下标
    unsigned char ipDigit = 3;     //十进制的位数
    for (int i = 0; ipstr[i] != 0; i++) {   //遍历IP 地址字符串
        if ( '.' != ipstr[i] ) {    // 如果不等于点
            if ( ipstr[i] < '0' || ipstr[i] > '9' )    //如果不是数字字符，则IP地址错误返回 -1
                return -1;
            else
                num[count++] = ipstr[i] - 48;   //是数字字符，减去48 转换成对应的数值
        } else {    //如果遍历到一个点
            if ('.' == ipstr[i + 1])   //如果下一个字符还是点，则ip地址格式错误，返回-1
                return -1;
            int digit = count - 1;    //定义一个临时的位
            int temp = 0;    //临时int
            for (int j = count - 1; j > -1; j--)   //倒着遍历 num 数组。因为下标从0开始，所以 count - 1
                temp += num[j] * pow(10, (digit - j));   //计算出十进制数
            count = 0;     //count下标置为零，为下一次循环，记录下一个十进制字段做准备
            if (temp < 0 || temp >255)    //计算后的十进制数如果不在 0~255之间，则IP地址错误，返回 -1
            	return -1;
            ip += temp * pow(256, (ipDigit));    //计算ip的数值
            ipDigit--;    // ipDigit 位自减1
        }
    }
    return ip;     //返回转换后的 ip 地址对应的数值
}

isCorrectSubnetMask 函数的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int isCorrectSubnetMask(unsigned int subnet_mask) {    //判断子网掩码是否合法，合法返回1，不合法返回0
    long long int subnetMask = pow(2, 32);    //8字节的long long int，33比特处置为1，方便后面处理
    subnetMask += subnet_mask;     //加上传入的32位子网掩码的数值
	int flag = 0;    //定义一个标志
    while (subnetMask != 0) {
        int temp = subnetMask % 2;    //临时变量保存每一个二进制的位
        // subnetMask 数值除以2取余数，依次得到从右往左的每一个二进制位
        if (temp == 0 && flag == 0) {    //temp=0, flag=0 表明最右边的二进制位为 0
            flag++;  // flag 自增，flag 等于 1，表明进入了二进制位连续为0的范围内
        } else if (temp == 1 && flag == 1) {      //当得到了一个二进制位为1时，flag自增为2，表明进入到了连续为1的范围
            flag++;
        } else if (temp == 0 && flag == 2) {     //表明从右往左一次进入了连续0和连续1后，又得到了一个二进制位为0
            return 0;    // 子网掩码不合法返回0
        } else if (temp == 1 && flag == 0) {     //最右边第一个二进制位为1，子网掩码非法
        	return 0;
		}
        subnetMask /= 2;    //subnetMask 数值在同一个循环中自除以2取整，更新数值，以便下一次循环得到左边的一位二进制数值
	}
    if (flag == 0 || flag == 1) {    
        //循环遍历结束后，flag 仍然等于0，表明从右往左没有遇到任何0的二进制位（全为1），不合法
        //循环结束后， flag 仍然等于1，表明二进制数全为 0，不合法
        return 0;
    } else {
    	return 1;
	}
}

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <string.h>
#include <math.h>

unsigned int strToIP(char* ipstr); //传入形如"192.168.233.12."的IP地址字符串，将IP地址转换成 unsigned int 数值
void IPClass(unsigned int ip, int* a, int* b, int* c, int* d, int* e, int* pIP); //传入IP 地址和其他几个用于计数的变量的指针，判断 ip 的数值的范围从而确定它是哪类地址
int isCorrectSubnetMask(unsigned int subnet_mask);   //传入子网掩码转换成 unsigned int 后的数值，判断它是否合法。

unsigned int strToIP(char* ipstr) {
    unsigned int ip = 0;
    char num[3];
    unsigned char count = 0;
    unsigned char ipDigit = 3;
    for (int i = 0; ipstr[i] != 0; i++) {
        if ( '.' != ipstr[i] ) {
            if ( ipstr[i] < '0' || ipstr[i] > '9' )
                return -1;
            else
                num[count++] = ipstr[i] - 48;
        } else {
            if ('.' == ipstr[i + 1])
                return -1;
            int digit = count - 1;
            int temp = 0;
            for (int j = count - 1; j > -1; j--)
                temp += num[j] * pow(10, (digit - j));
            count = 0;
            if (temp < 0 || temp >255)
            	return -1;
            ip += temp * pow(256, (ipDigit));
            ipDigit--;
        }
    }
    return ip;
}

void IPClass(unsigned int ip, int* a, int* b, int* c, int* d, int* e, int* pIP) {
    if (ip > 16777215 && ip <= 2130706431) {
        (*a)++;
        if ( ip >= 167772160 && ip <= 184549375)
            (*pIP)++;
    } else if (ip >= 2147483648 && ip <= 3221225471) {
        (*b)++;
        if ( ip >= 2886729728 && ip <= 2887778303 )
            (*pIP)++;
    } else if ( ip >= 3221225472 && ip <= 3758096383 ) {
        (*c)++;
        if ( ip >= 3232235520 && ip <= 3232301055 )
            (*pIP)++;
    } else if ( ip >= 3758096384 && ip <= 4026531839 )
        (*d)++;
    else if (ip >= 4026531840 && ip < 4294967295)
        (*e)++;
}

int isCorrectSubnetMask(unsigned int subnet_mask) {
    long long int subnetMask = pow(2, 32);
    subnetMask += subnet_mask;
    int flag = 0;
    while (subnetMask != 0) {
        int temp = subnetMask % 2;
        if (temp == 0 && flag == 0) {
            flag++;
        } else if (temp == 1 && flag == 1) {
            flag++;
        } else if (temp == 0 && flag == 2) {
            return 0;
        } else if (temp == 1 && flag == 0) {
            return 0;
        }
        subnetMask /= 2;
    }
    if (flag == 0 || flag == 1) {
        return 0;
    } else {
        return 1;
    }
}

int main() {
    int a = 0, b = 0, c = 0, d = 0, e = 0, errip = 0, private_ip = 0;
    unsigned int ip, subnetMask;  //用保存转换后的 ip 和子网掩码 的数值
    char ips[1002][32];     //1~1000个数据，每个数据最长 32 个字节
    strcpy(ips[0], "init");    //初始化第零个数据
    int index = 1;     //用于保存数据的下标
    char str[32];       //用于接收输入的每一行
    while (1) {
        gets(str);    //接收行
        strcpy(ips[index++], str);    //复制到 ips 数组中， index自增1
        if (!strcmp(ips[index - 2], str))    //输入结束的标志，退出循环
            break;
    }
    for (int i = 1; i < index - 1; i++) {     //遍历输入的每一行
        ip = 0;   //初始化 ip 数值
        subnetMask = 0;    // 初始化子网掩码数值
        char ipstr[17] = { 0 };     //保存一个 IP 地址或子网掩码的字符串
        int count = 0;     //ipstr 的下标
        for (int j = 0; * (*(ips + i) + j) != 0; j++) {     //每一行的末尾值是0，j从0开始遍历这一行的数据，直到这一行的末尾
            if ('~' != ips[i][j]) {  // ip 和子网掩码中间的分隔符 ~ ，如果不是分隔符，则是前面的IP字符串中的字符
                ipstr[count++] = ips[i][j];     //记录每个IP的字符到ipstr字符串中
            } else {     //如果遇到了 ~ 字符
                ipstr[count++] = '.';    //在末尾添加一个点，方便 strToIP() 处理
                ipstr[count] = 0;     //添加字符串结束的标志
                //printf("ip address:%s\n", ipstr);
                ip = strToIP(ipstr);      // 调用 strToIP() 将字符串形式的 IP 地址转换成一个数值
                //printf("ip:%d %u\n",ip, ip);
                count = 0;    //count 从0 开始进入下一次循环，保存 ~ 后面的所有子网掩码的字符到 ipstr 中
            }
        }    //for 循环结束后，ipstr 中保存的是子网掩码的字符串
        ipstr[count++] = '.';     //同样添加一个点，方便处理
        ipstr[count] = 0;
        //printf("subnet mask:%s\n", ipstr);
        subnetMask = strToIP(ipstr);     //将子网掩码转换成数值的形式
        if (-1 == subnetMask)   //subnetMask错误或等于255.255.255.255（-1的补码）
            errip++;
        else { //subnetMask 没有错误或不等于 255.255.255.255
            if (!isCorrectSubnetMask(subnetMask)) {  // subnetMask 不合法
                if ( !((ip >= 0 && ip <=16777215) || (ip > 2130706431 && ip < 2147483648)) )  
                // 属于 0.*.*.* 或 127.*.*.* 这两个段的地址无论子网掩码是否合法都不计数，取非! 排除这两个地址段
            	    errip++;
                //printf("error subnet mask: %s\n", ipstr);
            }
            else {   // subnetMask 合法的情况
                if (-1 == ip) { // IP不合法
                    errip++;
                    //printf("error ip address: %s\n", ipstring);
                } else {
                    IPClass(ip, &a, &b, &c, &d, &e, &private_ip);    //调用分类函数进行分类，传入变量的内存地址
                }
            }
        }
    }
    printf("%d %d %d %d %d %d %d\n", a, b, c, d, e, errip, private_ip);
    return 0;
}

提交代码：过辣！！！

在这里插入图片描述

改进一下输入部分，使用 fgets() ，在输入一行的时候就进行统计操作，不用保存所有数据，更节省内存，同时少了 for 循环遍历。如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int main() {
    int a = 0, b = 0, c = 0, d = 0, e = 0, errip = 0, private_ip = 0;
    char str[33];
    unsigned int ip, subnetMask;
    while (fgets(str, 33, stdin) != NULL) {
        ip = 0;
        subnetMask = 0;
        char ipstr[17] = { 0 };
        int count = 0;
        for (int i = 0; * (str + i) != '\n'; i++) {
            if ('~' != str[i]) {
                ipstr[count++] = str[i];
            } else {
                ipstr[count++] = '.';
                ipstr[count] = 0;
                ip = strToIP(ipstr);
                count = 0;
            }
        }
        ipstr[count++] = '.';
        ipstr[count] = 0;
        subnetMask = strToIP(ipstr);
        if (-1 == subnetMask)
            errip++;
        else {
            if (!isCorrectSubnetMask(subnetMask)) {
                if ( !((ip >= 0 && ip <= 16777215) || (ip > 2130706431 && ip < 2147483648)) )
                    errip++;
            } else {
                if (-1 == ip) {
                    errip++;
                } else {
                    IPClass(ip, &a, &b, &c, &d, &e, &private_ip);
                }
            }
        }
    }
    printf("%d %d %d %d %d %d %d\n", a, b, c, d, e, errip, private_ip);
    return 0;
}
Data_Structure/Algorithms_数据结构与算法
Prev:
C语言 单向链表反转问题
Next:
最长无重复字符子字符串问题（Longest Substring Without Repeating Characters）

    • Copyright © 2024 Jackey Song