제1 1 장 산 목록 (2) 산 목록
가장 간단 한 해결 방법 은 링크 법 과 다음 절 에 소개 되 는 개방 주소 법 이다.
링크 법, 즉 같은 슬롯 에 흩 어 져 있 는 모든 요 소 를 하나의 링크 에 넣 는 것 이다.
링크 는 무질서 합 니 다. 원 소 를 찾 을 때 링크 를 옮 겨 다 녀 야 합 니 다.
삭제 함수 에 대해 서 는 인자 가 삭제 할 노드 라면 링크 가 양 방향 이면 삭제 작업 은 O (1) 내 에 완 료 될 수 있 습 니 다.
아래 삭제 함수 에서 매개 변 수 는 키워드 로 더욱 편리 합 니 다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 20
//
typedef struct _ListNode {
struct _ListNode *prev, *next;
char *key;
char *val;
} ListNode;
//
ListNode *hashmap[SIZE];
// Java String HashMap
// ( 0 )
// h
unsigned hashcode(char *key)
{
// Ensure >> is logical shift
unsigned h = 0;
// String.hashcode()
do h = 31 * h + *key++;
while (*key != '\0');
// HashMap.hash()
h ^= (h >> 20) ^ (h >> 12);
return h ^ (h >> 7) ^ (h >> 4);
}
ListNode * hashmap_search(char *key)
{
unsigned h = hashcode(key) % SIZE;
ListNode *node = hashmap[h];
while (node != NULL) {
// ,strcmp 0
if (strcmp(node->key, key) == 0) {
return node;
}
node = node->next;
}
return NULL;
}
char * hashmap_insert(char *key, char *val)
{
unsigned h = hashcode(key) % SIZE;
printf("Insert %s - %s to bucket %d
", key, val, h);
// Find duplicate key, replace it then return old value
ListNode *node = hashmap_search(key);
if (node != NULL) {
char *oldVal = node->val;
node->val = val;
return oldVal;
}
// Not found, create new node to save key&val pair
ListNode *newNode = malloc(sizeof(ListNode));
newNode->prev = NULL;
newNode->key = key;
newNode->val = val;
if (hashmap[h] == NULL) {
hashmap[h] = newNode;
} else {
hashmap[h]->prev = newNode;
newNode->next = hashmap[h];
hashmap[h] = newNode;
}
return val;
}
char * hashmap_delete(char *key)
{
ListNode *node = hashmap_search(key);
if (node != NULL) {
// Set prev node's next to node's next
if (node->prev == NULL) {
unsigned h = hashcode(key) % SIZE;
hashmap[h] = node->next;
} else {
node->prev->next = node->next;
}
// Set next node's prev to node's prev
if (node->next != NULL)
node->next->prev = node->prev;
return node->val;
}
return NULL;
}
void hashmap_print()
{
int i;
for (i = 0; i < SIZE; i++) {
ListNode *node = hashmap[i];
while (node != NULL) {
printf("%s - %s, ", node->key, node->val);
node = node->next;
}
if (hashmap[i] != NULL)
printf("%d bucket
", i);
}
printf("
");
}
int main(void)
{
// Compare to String.hashcode() in JDK
printf("%d
", hashcode("helloworld"));
hashmap_insert("aabb", "value1");
hashmap_insert("ccdd", "value2");
hashmap_insert("i'mcdai", "value3");
int i;
for (i = 0; i < 2 * SIZE + 5; i++) {
char *key = calloc(sizeof(char), 10);
char *val = calloc(sizeof(char), 10);
sprintf(key, "%s%d", "aabbcc", i);
sprintf(val, "%s%d", "val ", i);
hashmap_insert(key, val);
}
// Insert duplicate key
printf("%s
", hashmap_insert("i'mcdai", "dupdup"));
hashmap_print();
printf("%s
", hashmap_search("i'mcdai")->val);
printf("%s
", hashmap_search("aabbcc18")->val);
//printf("%s
", hashmap_search("NOTFOUND")->val);
// All in bucket 18: aabbcc10 => aabbcc0 => i'mcdai
printf("%s
", hashmap_delete("aabbcc10"));
printf("%s
", hashmap_delete("i'mcdai"));
hashmap_print();
return 1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.