设计一个信息管理系统，你需要知道这些

假设需要设计一个信息管理系统，用于管理大约一万个学生的相关信息，可以通过学号查找到对应学生的信息，每条学生记录包含学号、姓名、性别、身高、体重等信息。即：

typedef struct _student{

              unsigned char id[6];                         // 学号（6字节）

            char               name[10];                  // 姓名

            char               sex;                       // 性别

            float                height, weight;                 // 身高、体重

作为信息管理系统，首先要能够存储学生记录，这上万条记录如何存储呢？简单地，可以使用一段连续的内存存储学生记录，比如，使用一个大数组存储，每个数组元素都可以存储一条学生记录：

student_t  student_db[10000];

当使用数组存储学生信息时，如何通过学号查找相应的信息呢？如果学号编排是一种非常理想的情况，10000个学生的学号按照 0 ~ 9999顺序排列，则可以直接将学号作为数组的索引值查找相应的数组元素，其存储和查找的效率都非常高。但实际上学号往往不是如此简单编排的，一种常见的编排方法是"年级+专业代码+班级+班级内序号"，比如，6字节学号为0x20, 0x16, 0x44, 0x70, 0x02, 0x39，即：201644700239，表示2016年入学，专业代码为4470（即计算机专业），2班的39号同学。

此时，通过学号查找学生信息的方法也很简单，直接从第一个学生记录开始，顺序遍历各个学生记录，将记录中的学号与期望查找的学生学号相比较，学号相同即查找到了相应学生的信息，详见程序清单3.61。

程序清单3.61  顺序查找范例程序

1    student_t * student_search(unsigned char id[6])

2    {

3        for (int i = 0; i < 10000; i++) {

4            if (memcmp(student_db[i].id, id, 6) == 0) {      // 比较

5                 return &student_db[i];                  // 找到该学生的信息

6            }

7        }

8        return NULL;                                // 未找到该学生的信息

显然，如果采用顺序查找法，学生记录越多，则查找时需要比较的次数越多，效率也就越低。当学生记录的条数上万时，则可能需要比较上万次才能找到相应的学生信息。

如何以更高的效率实现查找呢？在理想情况下，若将学号作为数组索引存储数据，则查找的效率非常高。既然如此，如果扩大数组容量至学号