第一章

1. 如果不缺内存，如何使用一个具有库的语言来实现一种排序算法以表示和排序集合。
   compare方法：

int compare(void const *a, void const *b){
    return *(int *)a- *(int *)b;
}

实现：

int n;
    scanf("%d",&n);
    int c[n];
    for (int i = 0; i < n; i ++) {
        scanf("%d",&c[i]);
        qsort(c, n, sizeof(int), compare);
    }
    for (int i = 0; i < n; i ++) {
        printf("%d",c[i]);
    }

2. 如何使用为逻辑运算（如与、或、移位）来实现位向量。
   宏定义

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
#define K 1000000

全局变量声明：

int a[1 + N/BITSPERWORD];

赋值函数：

//i>>SHIFT i右移5位，作为a的下标
//i & MASK int32位，确定在哪一位 
void set(int i){
    a[i>>SHIFT] |= (1<<(i & MASK));
}

清空函数：

//~(1<<(i & MASK)) 实际对i取反 &= 操作之后结果为00000
void clr(int i){
    a[i >> SHIFT] &= ~(1<<(i & MASK));
}

校验函数：

int test(int i){
    return a[i >> SHIFT] & (1 << (i & MASK));
}

3. 运行效率是设计目标的重要组成部分，所得到的程序需要足够高效。在你自己的系统上实现位图排序并度量其时间。该时间与系统排序的运行时间以及习题1排序运行的时间相比如何？假设n为10000000，并输入文件包含1000000个整数。
   使用习题2的答案来实现排序算法。

for (int i = 0; i < N; i ++) {
        clr(i);
        while (scanf("%d",&i) != EOF) {
            set(i);
        }
    }
    for (int i = 0; i < N; i ++) {
        if (test(i)) {
            printf("%d\n",i);
        }
    }

4. 如果认真考虑了习题3，你将会面对一个生成小于n且没有重复的k个整数的问题。最简单的方法就是使用前k个正整数。这个极端的数据集合将不会明显地改变位图方法的运行时间，但可能会扭曲系统排序的运行时间。如何生成位于0到n-1之间的k个不同的随机栓恤的随机整数？尽量使你的程序简单且高效。
   生成随机数的函数

int randint(int l,int u){
    int temp;
    srand((unsigned)time(NULL));
    temp = floor(l + (1.0*rand()/RAND_MAX)*(u - l + 1 ));
    return temp;
}

交换函数：

void swap(int *a,int *b){
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

声明全局变量narray

int narray[N];

实现：

//对narray赋值
for (int i = 0 ; i < N; i ++) {
        narray[i] = i;
    }
    //声明karray
    int karray[K];
    //dui对karray赋值
    for (int i = 0; i < K; i ++) {
    //随机打乱narray顺序并对karray赋值
    swap(&narray[i], &narray[randint(i, N - 1)]);
        karray[i] = narray[i];
    }
    //清除
    for (int i = 0; i < N; i ++) {
        clr(i);
    }
    //赋值
    for (int i = 0; i < K; i ++) {
        set(karray[i]);
    }
    //校验和输出
    for (int i = 0; i < N; i ++) {
        if (test(i)) {
            printf("%d\n",i);
        }
    }

5. 那个程序员说他有1MB 可用存储空间，但是我们概要描述的代码需要1.25MB的空间。他可以不费力气的索取到额外的空间。如果1MB的空间是严格的边界，你会推荐如何处理？你的算法的运行时间又是多少？
   使用位图表示1000万个数需要1000万个位，或者说125万字节考虑到没有数字1和0开头的电话号码，我们可以将内存需求降低为100万字节。另外一种做法是采用两趟算法，首先用5000000/8=625000个字节的存储空间来排序0-4999999之间的整数，然后在第二趟排序5000000-9999999的整数。k趟算法可以在kn的时间开销和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。
6. 如果那个程序员说的不是每个文件最多出现1次，而是每个整数最多出现10次，你又如何建议他？你的解决方案如何随着可用存储空间的总量的变化而变化？
   如果每个整数最多出现10次，那我们可以使用4位的半字节来统计它出现的次数。利用习题5的答案，我们可以10000000/2个字节在1趟内完成对整个文件的排序，或者使用10000000/2k个字节在k趟内完成对整个文件的排序。

宏定义：

#define BITSPERWORD 16
#define SHIFT 3
#define MASK 0x07
#define N 10000000
#define K 1000000

函数：

void set(int i){
    a[i>>SHIFT] += (1<<(4 *(i & MASK)));
}

void clr(int i){
    a[i >> SHIFT] &= ~(0x0F<<(4*(i & MASK)));
}

int test(int i){
    return (a[i>>SHIFT] & (0x0F<<(4 *(i&MASK))))>>4*(i&MASK);
}

代码测试：

int number[5] = {13,9,13,11,13};
    for (int i = 0; i < 5; i ++) {
        clr(number[i]);
    }
    
    for (int i = 0; i < 5; i ++) {
        set(number[i]);
    }

    printf("number==%d\n",test(13));

7. 本书1.4节中描述的程序存在一些缺陷。首先是假定在输入中没有出现两次的整数。如果某个数出现超过一次的话，会发生什么？在这种情况下，如何修改程序来调用错误处理函数？当输入整数小于0或大于等于n时，又会发生什么？如果某个输入不是数值又如何？在这种情况下，程序应该如何处理？程序还应该包含哪些明智的检查？描述一些用以测试程序的小型数据集合，并说明如何正确处理上述以及其他的不良情况。
   可能我想的这些都是一些很浅显的想法，但无论怎样先记录下来吧。
   如果整数超出一次的话，在保存的时候进行记录。超出一次的后果第一次存储的数据会被第二次的替换，排序总数少一个。
   当输入的整数小于零或大于n时，排序相当于对n-1个整数排序。如果输入的不是数值有可能会发生崩溃的情况比如输入的是char类型字符，也有可能发生和输入大于n小于0一样的情况。这样的情况下需要对输入的信息进行判断，当信息不准确的时候提示重新输入或者结束当前程序。
   就先写下了这么多。
8. 当那个程序员解决gai该问题的时候，美国所有免费电话的区号都是800。现在免费的区号包括800、877、和888，而且还在增多。如果在1MB空间内完成对所有这些免费电话的排序？如何将免费电话号码存储在一个集合中，要求可以实现非常快速的查找以判定一个给定的免费电话号码是否可用或者已经存在？
   随机数的生成出现了一些问题，有时间再回来解决。
9. 使用更多的空间来换取更少的运行时间存在一个问题：初始化空间本身需要消耗大量的时间。艘名如何设计一种技术，在第一次访问向量时将其初始化为0。你的方案应该使用常量时间进行初始化和向量访问，使用的额外空间正比于向量的大小。因为该方法通过进一步增加空间来减少初始化的时间，所以仅在空间很廉价、时间很宝贵且响亮很稀疏的情况下才考虑使用。
   借助于两个额外的向量from、to和一个整数top，我们就可以使用表示来初始化向量data[0..n-1]。如果元素data[i]已经初始化，那么from[i]<top并且to[from[i]] = i。因此，from是一个简单的标识，to和top一起确保了from中不会被写入内存里的随机内容。
   代码展示：（不确定正确）

int nameArray[100000];
    int from[100];
    int to[100];
    int top = 2;
    from[80] = top;
    to[from[80]] = 80;
    nameArray[80] = 33;
    top ++;

10. 在成本低廉的隔日送达时代之前，商店允许顾客通过电话订购商品，并在几天后上门自取。尚待你的数据库使用客户的电话号码作为其检索的主关键字（客户知道他们自己的电话号码，而且这些关键字几乎都是唯一的）。你如何组织商店的数据库，以允许高效的插入和检索操作？
    商店将纸质的表格放在10*10的箱数组中，使用客户电话号码的最后两位作为散列索引。当客户打电话下订单时，将订单放到适当的箱中当客户来取商品时，销售人员顺序搜索对应箱中的订单-这就是经典的“用顺序搜索来解决冲突中的开放散列”。电话号码的最后两位非常接近随机，因此是非常理想的散列函数，而最前面的两位数字很不理想。
11. 略
12. 载人航天的先驱们很快就意识到了需要在外太空的极端环境下实现顺利的书写。民间盛传美国航天宇航局话费100万美元研发出来了一种特殊的钢笔来解决这个问题。那么，前苏联又会如何解决相同的问题呢？
    民间盛传的美国宇航局话费100万美元研发出来了这种钢笔的信息是错误的。这种钢笔确实是由美国的一个商人自费研发出来的，后卖给了美国宇航局使用。苏联据说也在使用这种钢笔。这个故事可以告诉我们三个道理（1）：不要被事物的表象迷惑。针对每一件事情而言，你都需要彻彻底底的融入进去知道每一步的每一个细节，知道每一步的每一个原因。没有特别小的事情，很多时候一件事情涉及到了很多知识和智慧。再回头可能不是我们当初想象的那么简单。（2）对一件事情换一个思路可能会有不同的结果。更多的时候面对一件事情最重要的不是立即去做，而是要好好思考一下怎么去做。（3）无论做什么都要有自己的看法，不要被别人带走了。对对的事情坚持和赞扬，对错的事情避