C에서 Set ADT를 만들 때 중복 값을 제거 할 수 없습니다.

Question

학습용으로 동적 배열을 사용하여 C로 간단한 Set 추상 데이터 형식을 만들려고합니다. buildSet()이라는 함수를 구현했습니다.이 함수는 매개 변수로 구조 Set, n 요소 매개 변수 다음에 가져올 요소의 수인 n을 가져옵니다. 내 문제는 수학에서 알 수 있듯이 중복 값을 허용하지 말아야한다는 것입니다. 하지만 내 코드는이 요구 사항을 통과 할 수 없습니다. Set 구조체를 오류없이 구현했지만 세트를 인쇄하려고 할 때 중복이 있음을 알았습니다.

메인 파일의 다음 예

고려해

Set S; 
buildSet(&S, 6, 5, 20, 2, 3, -8, -8); 
for (int i = 0; i < S.size; ++i) { 
    printf("%d ", S.elems[i]); 
} 

예상 출력된다

5 20 2 3 -8 

실제 출력

5 20 2 3 -8 -8 

벨로하다 께 구조는 I 사용

typedef struct { 
    int *elems; /* Array contains our set elements. */ 
    size_t size; /* Number of elements exist in set. */ 
    long maxSize; /* Maximum allowed number of elements in set. */ 
    long sum; /* Sum of all elements in set. */ 
    int *min; /* The minimum element in set. */ 
    int *max; /* The maximum element in set. */ 
} Set; 

내 함수 프로토 타입을 내가 사용

void buildSet(Set *S, size_t n, ...) { 
    /** 
    * Pass each argument, representing a set element, 
    * from our variadic function to variadic list. 
    */ 
    va_list setElems; 

    /** 
    * Get the number of elements we want to pass 
    * to our set. 
    */ 
    va_start(setElems, n); 

    /** 
    * The number of elements in set structure. 
    */ 
    S->size = 0; 

    /** 
    * Using this function we don't restrict ourselves 
    * of using any number of elements for our set, so 
    * we "unset" maxSize member. 
    */ 
    S->maxSize = -1; 

    /** 
    * We initialize the sum counter. This will 
    * allow us to get the sum using sumOfSet() 
    * in O(1) time. 
    */ 
    S->sum = 0; 

    /** 
    * Allocates memory for our set. 
    */ 
    S->elems = malloc(sizeof(int)*(S->size)); 

    /** 
    * Pass each set element, to our set 
    * and update the sum counter. 
    */ 
    int elem; 
    for (size_t i = 0; i < n; ++i) { 
     elem = va_arg(setElems, int); 
     if (!isElementOfSet(S, elem)) { 
      ++(S->size); 
      S->elems = realloc(S->elems, sizeof(int)*(S->size)); 
      S->elems[(S->size)-1] = elem; 

      S->sum += elem; 
     } 
    } 

    /** 
    * Frees the variadic list. 
    */ 
    va_end(setElems); 
} 

int isElementOfSet(Set *S, int x) { 
    /** 
    * We use binary search in our array-set 
    * to find if x belongs to S. 
    */ 
    int middle, left = 0, right = (S->size)-1; 
    while (left < right) { 
     middle = (left + right)/2; 
     if (S->elems[middle] == x) { 
      return 1; 
     } else { 
      if (S->elems[middle] > x) { 
       right = middle - 1; 
      } else { 
       left = middle + 1; 
      } 
     } 
    } 

    return 0; 
} 

Answer 1

당신은 당신의 방법 isElementOfSet에서 이진 검색을 사용하고 있습니다 :

/** 
* Creates a set structure S 
* with n elements x1,x2, x3,…. 
*/ 
void buildSet(Set *S, size_t n, ...); 

/** 
* Checks whether the value x is in the set S. 
*/ 
int isElementOfSet(Set *S, int x); 

우는 소리는 함수 본문입니다. Binary Search은 배열의 요소가 정렬 된 경우에만 배열에 적용 할 수 있습니다. 어떤 종류의 정렬을 적용한 곳은 어디에도 없습니다. 따라서 귀하의 방법을 선형 검색으로 변경하시는 것이 좋습니다 isElementOfSet.

int isElementOfSet(Set *S, int x) { 

    int i; 
    for(i = 0;i < S->size;++i) 
    { 
    if(S->elems[i] == x) 
     return 1; 
    } 
    return 0; 
}