[박혜웅] 집합 (set)

• 집합의 정의

  • 집합: 같은 성질을 갖는 원소들이 순서를 갖지 않고 모인 것

  • 프로그래밍 언어측면에서의 집합: 연관된 원소의 집합이며, 다음 조건이 맞아야 함

    • 각 원소 데이터는 키를 갖고 있음
    • 한 집합내의 두 원소는 같은 키를 동시에 갖지 않음

 

• 집합연산 인터페이스 연산 프로그래밍을 위한  규칙

  • 데이터형과 집합의 원소들에 대한 형 선언

    1. typedef .... set;
    2. typedef ... elementType;

  • char* 사용 지양

    • 적절한 데이터형 사용(예: short)

  • 포인터의 사용

    • 매개변수 수정시
    • 효율성

  • 불리언 데이터형 정의

    1. #define TRUE 1
    2. #define FALSE 0
    3. typedef int boolean; // boolean형에 0,1외의 다른 값도 대입이 가능하다. (예: boolean b = -1;)
  • 불리언 데이터형 정의 (바게식)
  1. enum{FALSE=0, TRUE=1} boolean; // boolean형에는 0,1외의 다른 값은 대입이 불가능하다.

  • 포인터 사용시 유의사항

    • 응용(함수외부)에서는 집합에서 사용된 값을 수정하지 않는다.
    • 함수안에서 자료를 복사하여 사용한다.
    1. v="abc";
    2. Insert(s,v); // char* v 로 함수에 전달
    3. v[1]='x'; // 함수 Insert 내부의 v값도 함께 변한다.

  • 집합원소에 대해 반복 연산 방법

    1. void Iterate(set *s, boolean (*)());   // 함수포인터를 이용하여 여러가지 반복 연산 함수를 이용할 수 있다.
    2. boolean PrintElement(elementType i);   // 원소 i를 출력하는 함수
    3. Iterate(S, PrintElement);

  • 패키징

    • header, source 파일을 분리

 

• 집합 구현시 고려사항

  • 집합의 크기가 다양하다

    • 메모리 또는 보조기억장치를 이용할 수 있음
    • 여러가지 기법이 요구됨

  • 정보의 양은 지속적으로 증가한다.

    • 성능을 위하여 계산의 일부분은 알고리즘 밖으로 빼야 한다.

  • 구현방법

    • B-tree

    • bit-vector for set

    • hashing for set
  • 구현방법에 따른 성능비교
  •  
    
  •