50018. Map
難度：4/5
實作不難，難在猜複雜度跟猜題目意義。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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86/*
typedef struct Pair{
int key;
char value[128];
} Pair;
typedef struct Map{
int map_size;
Pair data[1024];
}
*/
#include "map.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int cmp_pair(const void* a, const void* b){
return (((Pair*)a)->key) - (((Pair*)b)->key);
}
int cmp_key(const void* a, const void* b){
return *(int*)a - *(int*)b;
}
void init(Map *map){
map->map_size = 0;
}
int map(Map *map, const int key, const char *value){
for(int i = 0; i < map->map_size; i++){
if(map->data[i].key == key){
strcpy(map->data[i].value, value);
return 0;
}
}
map->data[map->map_size].key = key;
strcpy(map->data[map->map_size].value, value);
map->map_size++;
return 1;
}
int numPairs(Map *map){
return map->map_size;
}
void print(Map *map){
qsort(map->data, map->map_size, sizeof(Pair), cmp_pair);
printf("----- map begin -----\n");
for(int i = 0; i < map->map_size; i++){
printf("%d %s\n", map->data[i].key, map->data[i].value);
}
printf("----- end -----\n");
}
const char *getValue(Map *map, const int key){
for(int i = 0; i < map->map_size; i++){
if(map->data[i].key == key){
return map->data[i].value;
}
}
return NULL;
}
int unmap(Map *map, int key){
int key_pos = 0;
for(key_pos = 0; key_pos < map->map_size; key_pos++){
if(map->data[key_pos].key == key) break;
}
if(key_pos == map->map_size) return 0;
else{
for(int i = key_pos; i < map->map_size - 1; i++){
map->data[i] = map->data[i + 1];
}
map->map_size -= 1;
return 1;
}
}
int reverseMap(Map *map, const char *value, int keys[]){
int key_size = 0;
for(int i = 0; i < map->map_size; i++){
if(!strcmp(map->data[i].value, value)){
keys[key_size] = map->data[i].key;
key_size++;
}
}
qsort(keys, key_size, sizeof(int), cmp_key);
return key_size;
}