C++ 배열, 함수에서 반복 계산하기

Question

저는 최근에 C++을 배웠고 배열에서 반복되는 값의 수를 계산하려고합니다. 어떤 이유로 배열이 제 카운터 기능에 제대로 전달되지 않습니다.

#include <iostream> 
#include <time.h> 

using namespace std; 


//quicksort for int arrays, left should be left index (0), right is right index(last one) 
void quSort(int input[], int left, int right); 

//binary search will return the index of the target or -1 if not found 
int biSearch(int input[], int target, int iLeft, int iRight); 

//count reapeats in the array with biSearch 
int countRepeats(int input[], int target); 

int main() 
{ 
    srand((unsigned int) time(0)); 
    int test[1000]; 

    //generate 100 random numbers under 1000 
    for(int i = 0; i < 1000; i++) 
     test[i] = rand()%1000; 

    //output test original 
    cout << "orig: "; 
    for(int i = 0; i < sizeof(test)/sizeof(*test); i++) 
    { 
     cout << test[i] << " "; 
    } 
    cout << endl << endl; 

    //sorting 
    quSort(test,0,((sizeof(test)/sizeof(*test))-1)); 

    cout << "sorted: "; 
    for(int i = 0; i < sizeof(test)/sizeof(*test); i++) 
    { 
     cout << test[i] << " "; 
    } 

    //binary search test 
    int target; 
    int iTarget; 

    cout << "\nenter target: "; 
    cin >> target; 

    iTarget = biSearch(test,target,0,sizeof(test)/sizeof(*test)); 

    cout << "\n the target is at index: " << iTarget << " :: test[" << iTarget << "] = " << test[iTarget]; 

    //count repeats 

    cout << "\nWith " << countRepeats(test,target) << " repeats"; 

    system("pause"); 
    return 0; 
} 


//quicksort function; effiecent array sorter; important for furture array analysis!!! 
void quSort(int input[], int left, int right) 
{ 
    int pivot = input[(left+right)/2]; 
    int l = left;//to control loop 
    int r = right; 

    while(l <= r)//will get smaller over iterations 
    { 
     int placeHold;// for use in swap, temp number 

     //finds value higher than the pivot from left 
     while(input[l] < pivot) 
      l++; 
     //find value lower than pivot on right 
     while(input[r] > pivot) 
      r--; 
     //swapper 
     if(l <= r) 
     { 
     //if the value greater than pivot is to the left of the value 
     //lessser than pivot 
      placeHold = input[l]; 
      input[l] = input[r]; 
      input[r] = placeHold; 

      l++; 
      r--; 

     } 
     //recursion to sort whole array until l=r 
     if(left<r) 
      quSort(input, left, r); 
     if(l < right) 
      quSort(input, l , right); 
    } 
} 

//binary search function; array MUST be sorted 
int biSearch(int input[], int target, int iLeft, int iRight) 
{ 
    if(iLeft > iRight) 
     return -1; 
    else 
    { 
     int iMid = ((iLeft+iRight)/2); 

     if(input[iMid] > target) 
      return biSearch(input, target, iLeft, iMid-1); 
     else if(input[iMid] < target) 
      return biSearch(input, target, iMid+1, iRight); 
     else 
      return iMid;//target found 
    } 
} 


//Must be sorted 
int countRepeats(int *input, int target) 
{ 
    int holder[sizeof(input)/sizeof(*input)]; 
    int biSResult; 
    int counter = 0; 

    biSResult = biSearch(input,target,0,sizeof(input)/sizeof(*input)); 

    //bug test 
    cout<<"c++" << biSResult << "c++"; 
    // 

    while(biSResult != -1) 
    { 
     holder[biSResult] = target; 

     counter++; 

     input[biSResult] = 0; 
     quSort(input,0,((sizeof(input)/sizeof(*input))-1)); 
     biSResult = biSearch(input,target,0,sizeof(input)/sizeof(*input)); 
    } 

    biSResult = biSearch(holder,target,0,sizeof(holder)/sizeof(*holder)); 

    while(biSResult != -1) 
    { 

     input[biSResult] = target; 

     holder[biSResult] = 0; 
     quSort(holder,0,((sizeof(holder)/sizeof(*holder))-1)); 
     biSResult = biSearch(input,target,0,sizeof(holder)/sizeof(*holder)); 
    } 
    return counter; 
} 

는 사람이 그것이 큰 도움이

Answer 1

는 countRepeats()에 몇 가지 문제가 있습니다

가

(1) 이미 다른 답변에서 했나요로, 매개 변수가 전달되는 방식에 오류가 있습니다.함수에서 배열의 크기를 계산하려면 int* 또는 int[]을 사용하든 관계 없습니다. 따라서 배열 주소뿐만 아니라 시작 및 종료 카운터를 제공하여 quSort()에서와 같이이 함수에 가장 적합한 인수를 전달하십시오.

(2) 사용자가 while(biSResult != -1)의 목표를 묻는다면 프로그램이 중단됩니다.

(3)이 함수는 배열을 계속해서 다시 정렬합니다. 이 성능에 꽤 나쁜 것 같습니다. 배열이 이미 정렬되어 있다는 사실을 이용하지 않는 이유는 무엇입니까? 발견 된 색인에서부터 계산을 시작할 수 있습니다. 단지 iTarget이 맨 처음 발생했는지 확신 할 수 없기 때문에이 직책의 전후에 계산해야한다고 생각합니다. 이것은 다음과 같이 보일 수 있습니다 :

int countRepeats(int input[], int pos, int start, int end) 
{ 
    if (pos<start || pos>=end) // you never know ! 
     return 0; 

    int counter = 1; 

    for (int i=pos-1; i>=start && input[i]==input[pos]; i--) 
     counter++; 
    for (int i=pos+1; i<end && input[i]==input[pos]; i++) 
     counter++; 

    return counter; 
} 

그런데 그것을 테스트 한 결과 작동했습니다. 프로토 타입을 적용하고 주 기능에서 호출해야합니다.

cout << "\nWith " << countRepeats(test, iTarget, 0, 
        sizeof(test)/sizeof(*test)) << " repeats"; 

Answer 2

이 int *

그래서를 입력 가지고있다

int countRepeats(int *input, int target) 

로 선언 된 함수 countRepeats의 첫 번째 매개 변수가 될 것 일어나고있는 이유를 알고있는 경우

sizeof(input)/sizeof(*input) 

예를 sizeof (INT의 *)에 대해 4는 sizeof (INT) 같으면 516,

또한 식의 값 즉, 다음 식 (1)와 동일 할 것 (4)와 동일하다

sizeof(int *)/sizeof(int) 

동등 인수로 함수에 전달 된 배열의 요소 수에 달려 있지 않습니다.

배열의 크기를 명시 적으로 함수의 인수로 전달해야합니다. 그래서 함수는

int countRepeats(int *input, int n, int target); 

으로 선언되어야합니다. 또는 함수의 첫 번째 매개 변수를 array에 대한 참조로 선언 할 수 있습니다.

Answer 3

배열에 대한 포인터를받은 함수 내에서 배열의 크기를 계산할 수 없습니다. 이는 카운팅 함수 내부의 sizeof(input) 값이 int에 대한 포인터 크기를 반환하기 때문입니다. 따라서 sizeof(input)/sizeof(*input)은 항상 1이됩니다.

대신에 배열의 크기를 계산하여 int으로 저장 한 다음 계산 기능에 전달하면됩니다. 그래서 귀하의 계산 함수 호출을 변경 :

cout << "\nWith " << countRepeats(test,target,sizeof(test)/sizeof(*test)) << " repeats";

그리고 당신의 countRepeats 선언 : 어디서나 당신의 countRepeats 정의 내에 다음

int countRepeats(int input[], int target, int size);

, 당신은했다 (sizeof(input)/sizeof(*input)) 당신은 size을 말할 수있다 :

를

int countRepeats(int *input, int target, int size) 
{ 
    int holder[size]; 
    int biSResult; 
    int counter = 0; 

    biSResult = biSearch(input,target,0,size); 

    //bug test 
    cout<<"c++" << biSResult << "c++"; 
    // 

    while(biSResult != -1) 
    { 
     holder[biSResult] = target; 

     counter++; 

     input[biSResult] = 0; 
     quSort(input,0,(size-1)); 
     biSResult = biSearch(input,target,0,size); 
    } 

    biSResult = biSearch(holder,target,0,size); 

    while(biSResult != -1) 
    { 

     input[biSResult] = target; 

     holder[biSResult] = 0; 
     quSort(holder,0,(size-1)); 
     biSResult = biSearch(input,target,0,size); 
    } 
    return counter; 
} 

하지만 실제로는 std::vector을 대신 사용해야합니다. std::vector<int> test (1000);을 가질 수 있었고 countRepeats이 quSort에 대한 호출을 통해 배열을 변경 했으므로 벡터를 참조로 전달할 수 있습니다 (포인터를 전달하는 것만 큼 효과가 원본에 적용됨) 및 그 크기는 항상 test.size()