设计一个信息管理系统,你需要知道这些
的最大值加1(以包含学号0),则可以直接以学号作为数组的索引值。由于学号是由6字节组成的,因此数组必须能够容纳248条记录,需要占用多少存储空间呢?就算一条记录只占用一个字节,也需要262144 G存储空间,何况电脑硬盘没这么大!如果只使用其中的10000条记录,则剩下的(248-10000)空间就会造成极大的浪费,显然这种方式是不可取的。
在查找算法中,非常经典高效的算法是"二分法查找",按10000条记录算,最多也只需要比较14次(log210000)。但使用"二分法查找"的前提是信息必须有序排列,即要求学生记录必须按照学号的顺序存储,这就导致在添加或删除学生信息时,数据库存储的信息需要进行大量的移动操作。比如,数组中已经按照学号从小到大的顺序存储了9999条记录,现在写入第10000条记录,若该记录的学号最小,需要写入到所有记录的前面,这就需要将之前存储的9999条记录全部向后移动一次,以预留出首元素的空间,然后将新的学生记录写入首元素对应的空间中。由此可见,虽然使用这种方法可以提高查找效率,却牺牲了添加信息时的效率。
为了在添加信息时不进行大量的数据移动,能否换一种存储方式呢?比如,使用存储空间不连续的"单向链表"结构,将各个学生记录"链"起来,其示意图详见图3.23。
图3.23 使用单向链表管理学生记录
当使用链表管理学生记录时,实现有序排列只需每次插入新结点时,找到正确的插入位置,无需进行大量数据的移动。由于存储空间不连续,因此无法使用"二分法"查找学生信息,则实现有序排列也没有解决查找效率低下的问题,无论是否有序,查找时都需要从头开始顺序查找。
由此可见,使用"二分法查找"必须牺牲记录写入的效率以实现所有记录有序排列,使得写入记录的效率非常低。虽然基础的"顺序查找"对写入记录的效率完全不影响,但查找效率极为低下。因此,这两种情况都太极端了,要么选择极低的写入效率,要么选择极低的查找效率。何不将二者结合一下,以折中写入的效率和查找的效率呢?比如,将记录"二分"为两部分,使用两个数组来存储:
student_t student_db0[5000];
student_t student_db1[5000];
假设规定,学号小于某值(即201044700239)时,记录存储在student_db0中,反之,记录存储在student_db1中。如此一来,在写入记录时,只需要多一条判断语句,对性能并没太大影响。而在查找时,只要根据学号判断记录在哪一个数组中,即可按照顺序查找的方式查找。此时,查找需要比较的次数就从最大的10000次降低到了5000次。由此可见,通过一个简单的方法,将信息分别存储在两个数组中,就可以明显地提高查找效率。为了继续提高查找的效率,还可以继续分组,比如,分成250组,每组的大小为40:
student_t student_db0[40];
student_t student_db1[40];
……
student_t student_db248[40];
student_t student_db249[40];
显然,采用这种定义方式太繁琐了,由于每个数组的大小是相同的,因此可以直接将存储40个学生记录的数组定义为一个类型:
typedef student_t student_group_t[40];
student_group_t student_db[250];
此时,每个分组的大小为40,从而使得查找记录时,最多只需要比较40次。接下来,需要定义分组规则,以通过学号找到该记录属于哪个组。在定义规则时,应尽可能地使所有记录平均地分布在各个组中,不应该出现一些组存储的记录非常多,而一些组存储的记录非常少的情况。但这并不是一件容易的事情,需要对学号的数据分布进行精确的分析。
如果分成250组,假定学号是均匀分布的,则可以将6字节学号数求和除以250(分组数目)所得的余数(取余法)作为分组的索引,由于写入和查找时,都需要通过学号找到该记录应该属于哪个组,因此可以根据学号分组的依据,编写一个通过学号找到对应分组索引的函数,详见程序清单3.62。
程序清单3.62 通过学号分组范例程序
1 int db_id_to_idx(unsigned char id[6])
2 {
3 int i, sum = 0;
4
5 for (i = 0; i < 6; i++) {
6 sum += id[0];
7 }
8 return sum % 250; 9 }
- 电源软启动的实用设计技巧(07-16)
- 周立功:动态分布内存——malloc()函数与calloc()函数(07-22)
- 周立功“程序设计与数据结构”:深度解剖动态分布内存的free()函数与realloc()函数(07-25)
- 周立功教你学程序设计技术:做好软件模块的分层设计,回调函数要这样写(07-30)
- 周立功教你学C语言编程:教你数组是如何保存指针的(07-31)
- 算法的泛化问题,这些坑你可能都经历过!|周立功教你学软件设计(08-01)