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

if(IsMember(&s, n)) /* 집합 s에 n 값이 들어 있는지 확인할 때 작성하는 if문 */

원소를 추가하는 Add 함수

Add 함수는 집합 s에 n을 추가하는 함수입니다. 집합 s에 n을 추가하는 방법은 그림 7-15처
럼 집합 s 비트 벡터와 SetOf(n)으로 얻은 비트 벡터를 논리합(OR) 연산하면 됩니다. a 처럼
집합에 n이 이미 들어 있는 경우에는 논리합 연산을 하더라도 집합 s는 업데이트되지 않습니
다. b 처럼 집합에 n이 없다면 논리합 연산에 의해 n에 대응하는 비트가 0에서 1로 변경됩니

다(원소가 추가됩니다).

a 집합 {1, 3, 5, 6}에 6을 추가합니다. b 집합 {1, 3, 5, 6}에 4를 추가합니다.

３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０ ３１ ３０ ９ ８ ７ ６ ５ ４ ３ ２ １ ０
s 0 0 0 0 0 1 1 0 1 0 1 0 s 0 0 0 0 0 1 1 0 1 0 1 0

SetOf(n) 0 0 0 0 0 1 0 0 0 0 0 0 SetOf(n) 0 0 0 0 0 0 0 1 0 0 0 0
| |
0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0

논리합 연산을 해도 원래 집합의 상 논리합 연산을 통해 4에 해당하는
태를 유지합니다. 비트가 1로 바뀝니다.
원래의 n이 유지됩니다. n 값이 추가되었습니다.

[그림 7-15] Add 함수로 n을 추가하는 과정

실습 7-6[B] •완성 파일 chap07/BitSet.c
01 /*--- 집합 s에서 n을 삭제 ---*/
02 void Remove (BitSet *s, int n)
03 {
04 *s &= ~SetOf(n);
05 }
06
07 /*--- 집합 s의 원소 개수를 반환 ---*/
08 int Size (BitSet s)
09 {
10 int n = 0;
11 for(; s != BitSetNull; n++)
12 s &= s - 1;
13 return n;
14 }
15

07•집합 295