CCF201812-3 CIDR合并【详解】

试题编号: 201812-3
试题名称: CIDR合并
时间限制: 1.0s
内存限制: 512.0MB
问题描述:

样例输入

2
1
2

样例输出

1.0.0.0/8
2.0.0.0/8

样例输入

2
10/9
10.128/9

样例输出

10.0.0.0/8

样例输入

2
0/1
128/1

样例输出

0.0.0.0/0

分析

自定义数据类型

由于IP地址需要排序、匹配等,因此使用字符串类存储32位IP地址,整型len表示前缀长度。在struct IP中对<运算符进行了重载,以IP地址为第一关键字,前缀长度为第二关键字,从小到大排序。

struct IP{
IP(string s,int len):s(s),len(len){}
string s;
int len;
//以IP地址为第一关键字,前缀长度为第二关键字,从小到大排序
bool operator <(const IP &a)const
{
return s==a.s?(len<a.len):(s<a.s);
}
};
 

数据结构的选择

由于要频繁进行删除、插入操作,选择链表是一个合适的选择,因此可使用STL提供的list数据结构。

listv;
 

第一步:将各种形式的IP前缀用自定义数据类型表示

输入的IP前缀包括标准型、省略后缀型以及省略长度型,我们需要将它们用struct IP统一表示,并逐条插入到listv数据结构中。IP前缀是由字符串存储的点分十进制,我们需要将省略的部分都补齐,最后进行统一处理。

//字符串转换成base进制的整数
int stoi(string s,int base)
{
int res=0;
for(int i=0;i<s.length();i++)
res=res*base+s[i]-‘0’;
return res;
}

//将读入的IP前缀用struct类型的数据表示,并插入到数据结构listv中
void f(char str[])//str为字符串存储的点分十进制
{
vectorvec;
char sp=strtok(str,”.”);//先用”.”对str进行分割,将分割的各个部分放在vec中 while(sp) { vec.push_back(sp); sp=strtok(NULL,”.”); } int num=vec.size();//形成了num个部分 //确定是否有前缀,如果有一定是在最后一部分分,且含有”/”符号 string s=vec.back(),l=””;//l存储表示长度的字符串 vec.pop_back(); int pos=s.find(“/”); //含有”/”说明有长度 if(pos!=string::npos) { string ss=s; //将长度分割出来 s=ss.substr(0,pos); l=ss.substr(pos+1); } int len; if(l==””)//如果l为空,说明没有长度,是省略长度型,那么它的长度为num8
len=num*8;
else//l不为空,即l表示长度,把它转换成十进制整数
len=stoi(l,10);
vec.push_back(s);//将最后一部分重新压入vec中
while(num<4)//如果不足4部分,就加0 { vec.push_back(“0″); num++; } //将4个部分换成字符串存储的32位二进制 string res=””; for(int i=0;i中
v.push_back(IP(res,len));
}
第一步之后大部分工作就OK了。

第二步:排序

//1.排序 
v.sort();

第三步:从小到大合并

问题的关键是如何判断b的匹配集是否为a的匹配集的子集,其实很简单,设a的前缀长度为len,那么如果b的前len个字符和a相同,则b的匹配集是a的匹配集的子集,否则不是。

//判断q的匹配集是否为p的匹配集的子集,len为p的前缀长度
bool check(string p,string q,int len)
{
if(len>p.length()||len>q.length()) return false;
for(int i=0;i<len;i++)
if(p[i]!=q[i])
return false;
return true;
}
 

第四步:同级合并

//3.同级合并
for(list::iterator cur=v.begin();cur!=v.end();)//遍历列表
{
list::iterator next=cur;
next++;
if(next==v.end())
break;

    IP p1=*cur; //当前元素 
    IP p2=*next;//下一个元素 
    //p1.len==p2.len且p1前缀长度减一后依然合法(只要p1.s[p1.len-1]=0就是合法的) 
    if(p1.len==p2.len&amp;&amp;p1.len>0&amp;&amp;p1.s[p1.len-1]=='0')
    {
        IP tmp=p1;
        tmp.len--;
        //能合并 
        if(check(tmp.s,p2.s,tmp.len))
        {
          v.erase(next);//删除下一个元素 
          *(cur)=tmp;//删除当前元素,并插入tmp,等价于将当前元素的值变为tmp 
          if(cur!=v.begin())//如果cur所指的不是第一个元素,那么就要从cur的前一个元素考虑,就cur-- 
            cur--;
        }
        //不能合并,直接考虑下一个元素 
        else
          cur++;
    }
    //减一后不合法,直接考虑下一个元素 
    else
      cur++; 
}

第五步:输出

由于输出形式为点分十进制,因此需要一个打印函数

//打印输出
void print(string s,int len)
{
string s1=s.substr(0,8);
string s2=s.substr(8,8);
string s3=s.substr(16,8);
string s4=s.substr(24,8);
cout<::iterator cur=v.begin();cur!=v.end();cur++)
print((cur).s,(cur).len);
至此,问题解决!!!

C++程序

第一版(时间:2019.1.27)


#include<iostream>

#include<algorithm>

#include<string>

#include<cstring>

#include<vector>

#include<list>

using namespace std;

struct IP{
IP(string s,int len):s(s),len(len){}
string s;
int len;
//以IP地址为第一关键字,前缀长度为第二关键字,从小到大排序
bool operator <(const IP &a)const
{
return s==a.s?(len<a.len):(s<a.s);
}
};

listv;

//字符串转换成base进制的整数
int stoi(string s,int base)
{
int res=0;
for(int i=0;i<s.length();i++)
res=res*base+s[i]-‘0’;
return res;
}

//将读入的IP前缀用struct类型的数据表示,并插入到数据结构listv中
void f(char str[])//str为字符串存储的点分十进制
{
vectorvec;
char sp=strtok(str,”.”);//先用”.”对str进行分割,将分割的各个部分放在vec中 while(sp) { vec.push_back(sp); sp=strtok(NULL,”.”); } int num=vec.size();//形成了num个部分 //确定是否有前缀,如果有一定是在最后一部分分,且含有”/”符号 string s=vec.back(),l=””;//l存储表示长度的字符串 vec.pop_back(); int pos=s.find(“/”); //含有”/”说明有长度 if(pos!=string::npos) { string ss=s; //将长度分割出来 s=ss.substr(0,pos); l=ss.substr(pos+1); } int len; if(l==””)//如果l为空,说明没有长度,是省略长度型,那么它的长度为num8
len=num*8;
else//l不为空,即l表示长度,把它转换成十进制整数
len=stoi(l,10);
vec.push_back(s);//将最后一部分重新压入vec中
while(num<4)//如果不足4部分,就加0 { vec.push_back(“0″); num++; } //将4个部分换成字符串存储的32位二进制 string res=””; for(int i=0;i中
v.push_back(IP(res,len));
}

//判断q的匹配集是否为p的匹配集的子集,len为p的前缀长度
bool check(string p,string q,int len)
{
if(len>p.length()||len>q.length()) return false;
for(int i=0;i<len;i++)
if(p[i]!=q[i])
return false;
return true;
}

//打印输出
void print(string s,int len)
{
string s1=s.substr(0,8);
string s2=s.substr(8,8);
string s3=s.substr(16,8);
string s4=s.substr(24,8);
cout<<stoi(s1,2)<<“.”<<stoi(s2,2)<<“.”<<stoi(s3,2)<<“.”<<stoi(s4,2)<<“/”<<len<<endl;
}

int main()
{
char s[200];
int n;
scanf(“%d”,&n);
while(n–)
{
scanf(” %s”,s);
f(s);
}
//1.排序
v.sort();
//2.从小到大合并
for(list::iterator cur=v.begin();cur!=v.end();)//遍历列表
{
list::iterator next=cur;
next++;
if(next==v.end())
break;

    IP p1=*cur;//当前元素 
    IP p2=*next;//下一个元素 
    if(check(p1.s,p2.s,p1.len))
    {//如果p2的匹配集是p1的匹配集的子集,就删除p2,即 next所指元素 
        v.erase(next);
    }
    else//否则直接考虑下一个元素 
      cur++;
}   
//3.同级合并 
for(list<IP>::iterator cur=v.begin();cur!=v.end();)//遍历列表 
{
    list<IP>::iterator next=cur;
    next++;
    if(next==v.end())
      break; 

    IP p1=*cur; //当前元素 
    IP p2=*next;//下一个元素 
    //p1.len==p2.len且p1前缀长度减一后依然合法(只要p1.s[p1.len-1]=0就是合法的) 
    if(p1.len==p2.len&amp;&amp;p1.len>0&amp;&amp;p1.s[p1.len-1]=='0')
    {
        IP tmp=p1;
        tmp.len--;
        //能合并 
        if(check(tmp.s,p2.s,tmp.len))
        {
          v.erase(next);//删除下一个元素 
          *(cur)=tmp;//删除当前元素,并插入tmp,等价于将当前元素的值变为tmp 
          if(cur!=v.begin())//如果cur所指的不是第一个元素,那么就要从cur的前一个元素考虑,就cur-- 
            cur--;
        }
        //不能合并,直接考虑下一个元素 
        else
          cur++;
    }
    //减一后不合法,直接考虑下一个元素 
    else
      cur++; 
}
//输出 
for(list<IP>::iterator cur=v.begin();cur!=v.end();cur++)
  print((*cur).s,(*cur).len);
return 0; 

}
 

第二版(时间:2019.3.4)

#include<iostream>

#include<list>

#include<string>

using namespace std;

struct IP{
string ip;//ip地址
int len;//前缀长度
IP(){}
//以IP地址为第一关键字,前缀长度为第二关键字,从小到大排序
IP(string ip,int len):ip(ip),len(len){}
bool operator <(const IP &a)const
{
return ip==a.ip?(len<a.len):(ip<a.ip);
}
};

listl;

//将整数n(0<=n<256)化成二进制数
string itos(int n)
{
string res=”00000000″;
int k=7;
while(n)
{
res[k–]=n%2+’0′;
n/=2;
}
return res;
}

//读取ip前缀
void read()
{
string ip=””;
char ch;
int len=0,k=0,val=0;//k记录小数点的数量
bool flag=false;
while((ch=getchar())!=’\n’)//读入’\n’退出
{
if(ch==’.’)//读入小数点
{
k++;
ip+=itos(val);
val=0;
}
else if(ch==’/’)
{
ip+=itos(val);
val=0;
flag=true;
}
else
val=val10+ch-‘0’; } len=(flag?val:(k+1)8);//如果flag=true len就等于val,否则就是省略长度型
if(!flag) ip+=itos(val);//flag=false,表示是省略后缀型,那么val就是ip前缀的一部分
while(k<3)//补齐
{
ip+=itos(0);
k++;
}
l.insert(l.end(),IP(ip,len));//将元素插入list中
}

int main()
{
int n,i;
scanf(“%d”,&n);
getchar();//读取空白符
for(int i=1;i<=n;i++)//读入n个ip前缀 read(); l.sort();//第一步:排序 for(list::iterator cur=l.begin(),next;cur!=l.end();)//第二步:从小到大合并
{
next=cur;
next++;
if(next==l.end()) break;//如果cur已经是最后一个元素了就退出
for(i=0;ilen;i++)
if(cur->ip[i]!=next->ip[i])
break;
if(i==cur->len)//如果next是cur的子集,就删除next
l.erase(next);
else
cur++;//查看下一个元素
}
for(list::iterator cur=l.begin(),next;cur!=l.end();)//第三步:统计合并
{
next=cur;
next++;
if(next==l.end()) break;
if(cur->len==next->len&&cur->len>0&&cur->ip[cur->len-1]==’0′)
{
for(i=0;ilen-1;i++)
if(cur->ip[i]!=next->ip[i])
break;
if(i==cur->len-1)
{
l.erase(next);
cur->len-=1;
if(cur!=l.begin())//如果cur的前面还有元素,则让cur–
{
cur–;
continue;
}
}
}
cur++;//考虑下一个元素
}
//输出
for(list::iterator cur=l.begin();cur!=l.end();cur++)
{
for(i=7;i<32;i+=8) { int temp=0; for(int j=i-7;j<=i;j++) temp=temp*2+cur->ip[j]-‘0’;//注意权值为2
printf(“%d”,temp);
if(i!=31) printf(“.”);
}
printf(“/%d\n”,cur->len);
}
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注