(一)直接寻址表
关键字集合U = { 0, 1, ..., m - 1 },实际的关键字集合K。
用一个数组T[0..m - 1],其中每个位置对应U中的一个关键字。
直接寻址表的问题:
(1)如果U很大,要保存|U|大小的一张表T有点不实际。
(2)实际存储的关键字集合K相对U来说可能很小,因而分配给T的大部分空间都要浪费掉。
(二)位向量
位向量 (bit vector)是一种仅包含0和1的数组,所占空间比包含指针的数组少得多。
一个32位的整型,每一位用0和1表示key是否存在,这样一个整数就可以表示32个key。
key / 32表示key应保持在数组哪个下标的整数中,而key % 32则表示key应该用
该整数中的第几位置1来表示存在。
#include <stdio.h>
#include <stdlib.h>
#define INT_BIT 32
typedef struct {
unsigned int *table;
int size;
} BitMap;
BitMap * bitmap_create(int max)
{
BitMap *bitmap = malloc(sizeof(BitMap));
bitmap->size = max / INT_BIT + 1;
bitmap->table = calloc(sizeof(int), bitmap->size);
return bitmap;
}
void bitmap_insert(BitMap *bitmap, int key)
{
bitmap->table[key / INT_BIT] |= (1 << (key % INT_BIT));
}
void bitmap_delete(BitMap *bitmap, int key)
{
bitmap->table[key / INT_BIT] &= ~(1 << (key % INT_BIT));
}
int bitmap_search(BitMap *bitmap, int key)
{
return bitmap->table[key / INT_BIT] & (1 << (key % INT_BIT));
}
void bitmap_print(BitMap *bitmap)
{
printf("-----\n");
int i;
for (i = 0; i < bitmap->size; i++)
if (bitmap->table[i] != 0)
printf("%d: %d\n ", i, bitmap->table[i]);
printf("-----\n");
}
int main(void)
{
BitMap *bitmap = bitmap_create(1024);
bitmap_insert(bitmap, 15);
bitmap_insert(bitmap, 520);
bitmap_insert(bitmap, 900);
bitmap_print(bitmap);
printf("%d\n", bitmap_search(bitmap, 68));
printf("%d\n", bitmap_search(bitmap, 520));
return 1;
}
更快速、简洁的表示方法是用位运算来表示除法和求余。
key >> 5表示key / 32
key & 0x1F表示key % 32
#define SHIFT 5
#define MASK 0x1F
#define INT_BIT 32
void bitmap_insert(BitMap *bitmap, int key)
{
bitmap->table[key >> SHIFT] |= (1 << (key & MASK));
}
void bitmap_delete(BitMap *bitmap, int key)
{
bitmap->table[key >> SHIFT] &= ~(1 << (key & MASK));
}
int bitmap_search(BitMap *bitmap, int key)
{
return bitmap->table[key >> SHIFT] & (1 << (key & MASK));
}
一道笔试题:
腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?
分享到:
相关推荐
算法导论第四章答案算法导论第四章答案算法导论第四章答案算法导论第四章答案
最近在研习算法导论,发现课后习题的精彩程度甚至不亚于正文,对于算法导论的爱好者而言,这是一份不错的参考资料
算法导论 第二十五章 答案 算法导论 第二十五章 答案 算法导论 第二十五章 答案
算法导论第15章-动态规划的课后习题参考答案,对于算法爱好者而言,是不错的参考资料。
算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案
算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业:股票买卖最佳时期系列问题 南开大学 算法导论源码算法导论大作业...
本章问题较多的设计到数论与概率工具,由于对数学工具掌握的不够熟悉,有些习题尚未完成
基本上完整的算法导论第三版课后答案,中文版!
算法导论第二版课后习题,有1-26章的答案
第11章 散列表 第12章 二叉查找树 第13章 红黑树 第14章 数据结构的扩张 第四部分 高级设计和分析技术 导论 第15章 动态规划 第16章 贪心算法 第17章 平摊分析 第五部分 高级数据结构 概述 第18章 B树 第19章 二项堆...
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来
算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 算法导论讲义\算法导论讲义 MIT教师的课堂讲义 很有价值
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来
计算机算法导论计算机算法导论计算机算法导论计算机算法导论计算机算法导论
第十一章 散列表(Hash Tables) 第十二章 二叉查找树(Binary Search Trees) 第十三章 红-黑树(Red-Black Trees) 第十四章 扩充的数据结构(Augmenting Data Structures) 第四部分(Part IV) ...
31~35章
算法导论
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来
第11章 散列表 11.1 直接寻址表 11.2 散列表 11.3 散列函数 11.3.1 除法散列法 11.3.2 乘法散列法 11.3.3 全域散列法 11.4 开放寻址法 11.5 完全散列 思考题 本章注记 第12章 二叉...
能用代码表示的都用代码表示,不能表示的写出思路,思路都没写的就是我也做不出来