实验7 统计话费

实验时间

选做。

实验目的

综合运用所学知识，为实际问题设计高效算法。

问题描述

给定一份通话记录文件，包含约10万用户一天共计约100万条通话记录。文件是纯文本格式，每行为一条记录，格式如下：
手机号码（11位）、呼叫类型（2位，00表示主叫，01表示被叫）、通话时长（4位，以秒为单位）、呼叫发生小区（4位）、换行符（2位，即’\r\n’）
例如，文件的第一行：13955191490010225JQHK
表示手机号码为13955191490的用户在JQHK小区被叫，时长为225秒。
计费规则如下：

  1. 通话时长以分钟为单位计费，不足一分钟按一分钟计算。
  2. 主叫每分钟0.40元（40分）、被叫每分钟0.20元（20分）。

请生成话费账单，输出一份文件，要求输出文件是纯文本格式，每行为一条记录，格式如下：
手机号码（11位）、总费用（8位，以分为单位）、换行符（2位，即’\r\n’）
如输出文件的第一行：1395519149000001240
表示手机号码为13955191490的用户费用是12.40元。

实验内容

请设计计算复杂度尽可能低的算法。**提交程序运行时间最短的5名同学可获得实验加分。**
（注：提交的源代码将由助教编译运行，源代码必须能够正确编译链接，运行结果必须正确。运行时间将由助教在同一台计算机上多次运行程序取平均值得到。）
实验报告应详细说明所设计的算法是如何工作的，并附完整源代码。

实验想法

第一次看到这题的人都会想用树写吧？？所以我花了几个小时看了看AVL和红黑树，也查阅了AVL和红黑树各自的优缺点，但最后我还是不知道对于这个问题来说哪种树更合适。当我打算以后慢慢的去把这两种方案都实现一遍时，我去对老师给的数据进行了研究。竟然所有的电话号码都是139开头的？？？发现这一点，就越来越想用散列表来实现。少了139这个无效数据后，每个人只有一个唯一对应的8位的电话号码。我们只需要构造长为100,000,000存放int型的数组即可啦！

我尝试去编写这个程序，可是发现计算机不能分配这么大的内存（其实也不大），而在编程序的过程中，我继续对数据的特征进行挖掘，紧接着我发现139的后两位要么是 05,要么是55,要么是56;此时，我觉得哈希算法实现就在眼前，也许老师给的数据就是指引我们运用哈希算法？？

再去掉两位，我们只剩下6位值，和三个不同特征值，这时候，前方又有两个选择，是保留这个哈希冲突（每个链表最长也就3个结点），还是想想别的方法呢？我选择了哈希冲突，不过在一堆报错后放弃了（好像是内存溢出不是我写错了），只好继续想别的方法啦！

继续对数据特征进行挖掘，又发现了一个东西！139XX再后两位总是那么几个值：07-19,51-60，共23个值，一个两位数你就只有23个取值可能，这不是浪费吗？而23×3又刚好小于100,此时我们可以用一个六位数对应到每一个人的电话！六位数的后四位就是电话的后四位，六位数的前两位（1-23表示的是05XX;24-46表示的是55XX;47-69表示的是56XX）这样就成功实现没有哈希冲突的散列函数啦！

我们研究一下时间复杂度，n个数据均需要插入或者查找，不论是AVL还是红黑树复杂度都是O（nlogn),而哈希查找的时间复杂度为O（n），在时间复杂度上哈希查找有绝对优势。而空间复杂度，我们只需建立一个长度为700，000的unsigned short int型数组。而不同的用户有100,000个，用树写也需要100，000个结点，而每个结点要存好多乱七八糟的数据（电话（要对其进行大小比较），话费，指针，红黑树的颜色或者AVL的BF值等等），相比之下对于内存的占用不相上下！总而言之，恭喜你发现哈希算法是对这个问题最好的实现！

下面给出源代码，100行左右的代码，一种简洁的实现！

有的系统用fgetc()读取换行符\r\n需要两步,有的系统用fgetc()读取换行符\r\n只需要一步，对于如果这类报错，可以直接对代码76行进行注释或者删掉注释。

不同的电脑，不同的系统，不同的IDE，以及大家存放的文件名及路径会有些不同，对于打开不了文件，可以直接在代码的第15行和第80行修改成正确的文件名。

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
#include<cstdio>
#include<cstdlib>
#define maxnumber 700000
int main(void){
    int tongji=0,calltime,huafei,telnumber,telnumber0,featurenumber1,featurenumber2,key;
    unsigned short int hashtable[maxnumber]={0};
    bool huchu;
    char feature1[3];
    char feature2[3];
	char tel[5];
	char tmptime[5];
    FILE *f;
    
    printf("begin!");
    f=fopen("records.txt","rt");
    if(!f)
        printf("打开失败！\n");
	fseek(f,0,SEEK_SET);
	
    while(tongji<1000000){
        fgetc(f);
        fgetc(f);
        fgetc(f);
        for(int i=0;i<2;i++)
            feature1[i]=fgetc(f);
        feature1[2]='\0'; 
        featurenumber1=atoi(feature1);
        if(featurenumber1==5)
            key=0;
        else if(featurenumber1==55)
            key=1;
        else if(featurenumber1==56)
            key=2;
        else {
            printf("数据集错误！！%d",featurenumber1);
            exit(1);
        }
        for(int i=0;i<2;i++)
            feature2[i]=fgetc(f);
        feature2[2]='\0';
        featurenumber2=atoi(feature2);
        if(featurenumber2>=7&&featurenumber2<=19)
            featurenumber2 -=6;
        else if(featurenumber2>=51&&featurenumber2<=60)
            featurenumber2 -=37;
        else{
            printf("数据集错误！！！%d",featurenumber2);
            exit(1);
        }
        for(int i=0;i<4;i++)
            tel[i]=fgetc(f);
        tel[4]='\0';
        telnumber0=atoi(tel);
        telnumber=(key*23+featurenumber2)*10000+telnumber0;
        char b;
        fgetc(f);
        b=fgetc(f);
        if(b=='0')
            huchu=true;
        else if(b=='1')
            huchu = false;
        for(int i=0;i<4;i++)
            tmptime[i]=fgetc(f);
        tmptime[4]='\0';
        calltime=((atoi(tmptime)-1)/60+1);
        if(huchu==true)
            huafei=calltime*40;
        else
            huafei=calltime*20;
        hashtable[telnumber]+=huafei;
        fgetc(f);
        fgetc(f);
        fgetc(f);
        fgetc(f);
        fgetc(f);
//        fgetc(f);
        tongji++;
    }
    printf("end!");
    FILE *fout=fopen("out.txt","wt");
    for(int j=0;j<maxnumber;j++){
        if(hashtable[j]!=0) {
            int n=j/10000;
            int a1,a2;
            int a3=j-10000*n;
            if(n>=1&&n<=23){
                a1=5;
                if(n<=13)
                    a2=n+6;
                else
                    a2=n+37;
            }
            else if(n>=24&&n<=46){
                a1=55;
                if(n<=36)
                    a2=n-17;
                else
                    a2=n+14;
            }
            else if(n>=47&&n<=69){
                a1=56;
                if(n<=59)
                    a2=n-40;
                else
                    a2=n-9;
            }
            fprintf(fout, "139%02d%02d%04d%08d\n",a1,a2,a3, hashtable[j]);
        }
    }
    fclose(f);
    fclose(fout);
    printf("OK!\n");
}

不止要有手，还要有明亮的双眼