面试题合并区间(续)

前面讲到对一系列的区间合并，里边定义了结构

1 struct myDataType
2 {
3     unsigned int a;
4     unsigned int b;
5     bool flag;
6 };

具体参考：http://www.cnblogs.com/ivorfeng/archive/2013/04/30/3052022.html

那如果是对IP区间的合并呢？首先先回顾一下关于IP的知识。

一个IP地址由32bit组成，形式上为x.x.x.x，每一个x的范围是0~255，即1Byte = 8 bit。也就是说，对于每一个IP地址，我们都可以将其看成是32bit的数，对应于计算机里的unsigned int，这样我们就可以定义IP地址的数据结构为如下：

1 struct IP
2 {    //按低位向高位排
3     unsigned int p4:8;
4     unsigned int p3:8;
5     unsigned int p2:8;
6     unsigned int p1:8;
7 };

思路：现在，我们成功地将一个IP地址对应到一个unsigned int类型的值，接下来就好办了，即将问题转化为对整数区间的合并，待输出结果时，还需要将结果转化为IP地址的形式。

实际写代码的时候，我们只需要使用合并区间里面的myDataType这个数据结构，输入是把IP地址的值转化到myDataType里边的值即可，下面讲解如何转化。

输出的时候，将该数地址转为IP类型的地址，按IP的内容输出即可；现在的关键是如何把输入的IP，转化为unsigned int值。我们知道bit field是不支持取地址操作的，因此将myDataType类型的地址转化为IP类型的地址后，取其地址输入的办法是行不通的。但我们知道unsigned char 的字节刚好就1Byte，因此可以借助unsigned char类型的临时数组，先把IP地址的各位数输入到该数组，然后再将数据赋值到IP结构里边的值。看文字可能不太清楚，下面看看代码：

 1 int main()
 2 {    
 3     int T;
 4     printf("输入测试次数:\n");
 5     scanf("%d",&T);
 6     while(T--)
 7     {
 8         int N;
 9         printf("输入IP区间数:\n");
10         scanf("%d",&N);
11         myDataType *p = (myDataType*)malloc(N * sizeof(myDataType));
12 
13         for(int i = 0; i < N; ++i)
14         {
15             //myDataType类型的地址转化为IP类型的地址
16             IP *tmp1 = (IP *)&((p+i)->a);
17             IP *tmp2 = (IP *)&((p+i)->b);
18             //借助unsigned char类型的临时数组，先把IP地址的各位数输入到该数组
19             unsigned char ip1[4];
20             unsigned char ip2[4];
21             scanf("%d %d %d %d", ip1, ip1 + 1, ip1 + 2, ip1 + 3);
22             scanf("%d %d %d %d", ip2, ip2 + 1, ip2 + 2, ip2 + 3);
23             //将数据赋值到IP结构里边的值
24             tmp1->p1 = ip1[0];
25             tmp1->p2 = ip1[1];
26             tmp1->p3 = ip1[2];
27             tmp1->p4 = ip1[3];
28             tmp2->p1 = ip2[0];
29             tmp2->p2 = ip2[1];
30             tmp2->p3 = ip2[2];
31             tmp2->p4 = ip2[3];
32             /*scanf("%d %d",&((p+i)->a),&((p+i)->b));*/
33             (p+i)->flag = true;
34         }
35         newInterval(p, N);
36         free(p);
37         p = NULL;
38 
39     }

下面是关键函数：

 1 //判断p1  p2是否有交集
 2 bool isOverlap(myDataType *p1, myDataType *p2)
 3 {
 4     bool result = false;
 5     if(p1 == NULL || p2 == NULL)
 6         return result;
 7 
 8     if((*p1).b >= (*p2).a)
 9         result = true;
10 
11     return result;
12 }
13 //更新p1
14 void update(myDataType *p1, myDataType *p2)
15 {
16     if((*p1).b < (*p2).b)
17         (*p1).b = (*p2).b;
18 
19     if((*p1).a > (*p2).a)
20         (*p1).a = (*p2).a;
21 }
22 //比较函数 
23 int compare(const void *p1, const void *p2)
24 {
25     return ((myDataType*)p1)->a - ((myDataType*)p2)->a;
26 }
27 
28 void newInterval(myDataType *p, int nLen)
29 {
30 
31     if(p == NULL || nLen <= 0)
32         return;
33     //区间排序 
34     qsort(p, nLen, sizeof(myDataType), compare);
35     int i;
36     for(i = 1; i < nLen; ++i)
37     {     //判断区间是否重叠 
38         if(isOverlap(p + i - 1, p + i))
39         {    //更新后一个区间 
40             update(p + i , p + i - 1);
41             (p + i - 1)->flag = false;
42         }
43     }
44     printf("\n最终区间:\n");
45     for(i = 0; i < nLen; ++i)
46     {
47         if((p+i)->flag == true)
48         {
49             //将区间转化为IP结构输出
50             IP *tmp1 = (IP *)&((p+i)->a);
51             IP *tmp2 = (IP *)&((p+i)->b);
52             printf("%d.%d.%d.%d-", (tmp1->p1), (tmp1->p2), (tmp1->p3), (tmp1->p4));
53             printf("%d.%d.%d.%d\n", (tmp2->p1), (tmp2->p2), (tmp2->p3), (tmp2->p4));
54         }
55             
56     }
57     printf("\n");
58 
59 }

下面给一个简单的例子：