哈希表创建
题目链接
哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。哈希表相关定义如下：
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
| typedef enum{
HASH_OK,
HASH_ERROR,
HASH_ADDED,
HASH_REPLACED_VALUE,
HASH_ALREADY_ADDED,
HASH_DELETED,
HASH_NOT_FOUND,
} HASH_RESULT;
typedef struct __HashEntry HashEntry;
struct __HashEntry{
union{
char *str_value;
double dbl_value;
int int_value;
} key;
union{
char *str_value;
double dbl_value;
int int_value;
long long_value;
void *ptr_value;
} value;
HashEntry *next;
};
struct __HashTable{
HashEntry **bucket;
int size;
HASH_RESULT last_error;
};
typedef struct __HashTable HashTable;
HashTable *create_hash(int hash_size);
|
哈希表相关说明：
- HASH_RESULT 类型为相关函数的返回类型
- HashEntry 为哈希表所保存元素（即键值对 ）类型
- HashTable 为哈希表，其中 bucket 指向大小为size的、元素类型为 HashEntry*的指针数组
- 希表采用链地址法处理冲突
请实现 create_hash 函数，创建指定大小的哈希表。
程序流程图(flow代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| step1=>start: 开始
step2=>operation: 分配哈希表（容器）空间
step3=>operation: 分配bucket（桶）空间
cond1=>condition: 是否成果分配bucket空间
step4=>operation: 释放哈希表空间
step5=>operation: return NULL
step6=>operation: 初始化哈希表
step7=>operation: return H
step8=>end: 结束
step1->step2->step3->cond1
cond1(yes)->step6
cond1(no)->step4->step5
step6->step7->step8
|
答案代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include "hash.h"
#include
#include
#include
HashTable* create_hash(int size)
{
HashTable* H = (HashTable*)malloc(sizeof(HashTable));
H->bucket = (HashEntry**)malloc(sizeof(HashEntry**) * size);
if (!H->bucket) {
free(H);
return NULL;
}
memset(H, 0, sizeof(HashTable));
H->size = size;
return H;
}
|
哈希表创建
题目链接
哈希表（Hash Table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做哈希函数，存放记录的数组称做哈希表。哈希表相关定义如下：
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
| typedef enum{
HASH_OK,
HASH_ERROR,
HASH_ADDED,
HASH_REPLACED_VALUE,
HASH_ALREADY_ADDED,
HASH_DELETED,
HASH_NOT_FOUND,
} HASH_RESULT;
typedef struct __HashEntry HashEntry;
struct __HashEntry{
union{
char *str_value;
double dbl_value;
int int_value;
} key;
union{
char *str_value;
double dbl_value;
int int_value;
long long_value;
void *ptr_value;
} value;
HashEntry *next;
};
struct __HashTable{
HashEntry **bucket;
int size;
HASH_RESULT last_error;
};
typedef struct __HashTable HashTable;
HashTable *create_hash(int hash_size);
|
哈希表相关说明：
- HASH_RESULT 类型为相关函数的返回类型
- HashEntry 为哈希表所保存元素（即键值对 ）类型
- HashTable 为哈希表，其中 bucket 指向大小为size的、元素类型为 HashEntry*的指针数组
- 希表采用链地址法处理冲突
请实现 create_hash 函数，创建指定大小的哈希表。
程序流程图(flow代码）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| step1=>start: 开始
step2=>operation: 分配哈希表（容器）空间
step3=>operation: 分配bucket（桶）空间
cond1=>condition: 是否成果分配bucket空间
step4=>operation: 释放哈希表空间
step5=>operation: return NULL
step6=>operation: 初始化哈希表
step7=>operation: return H
step8=>end: 结束
step1->step2->step3->cond1
cond1(yes)->step6
cond1(no)->step4->step5
step6->step7->step8
|
答案代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include "hash.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
HashTable* create_hash(int size)
{
HashTable* H = (HashTable*)malloc(sizeof(HashTable));
H->bucket = (HashEntry**)malloc(sizeof(HashEntry**) * size);
if (!H->bucket) {
free(H);
return NULL;
}
memset(H, 0, sizeof(HashTable));
H->size = size;
return H;
}
|