Page 441 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２
a
14 29 69 5 6 20

17 33

０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０ １１ １２
b
13 14 29 69 5 6 46 리스트의 맨 앞에 46을 삽입

13을 삽입
17 20

33

[그림 11-7] 체인법에 의한 해시의 검색과 추가

요소를 삭제하는 Remove 함수
Remove 함수는 키 값이 x->no인 요소를 삭제하는 함수입니다.

69를 삭제하는 경우(그림 11-8 a )
69의 해시 값은 4이고 table[4]의 버킷에 저장된 포인터의 리스트를 연결 검색하면 69를 찾
을 수 있습니다. 그런데 69를 저장한 노드의 다음 노드는 17을 저장한 노드입니다. 그래서
b 처럼 17을 저장한 노드에 대한 포인터를 table[4]의 버킷에 대입하고 69를 저장하는 노드

의 메모리를 해제합니다. 이렇게 하면 삭제 처리가 완료됩니다.

요소를 삭제하는 과정을 정리하면 아래와 같습니다.

1. 해시 함수가 키 값을 해시 값으로 변환합니다.
2. 해시 값을 인덱스로 하는 버킷을 선택합니다.
3. 선택한 버킷의 포인터가 가리키는 연결 리스트를 처음부터 순서대로 검색합니다. 키 값과 같은 값을 찾으면
그 노드를 리스트에서 삭제합니다. 그렇지 않으면 삭제에 실패합니다.

11•해시 441