C 숙제 도움말 : 배열을 통한 검색

Question

정렬 된 정수 배열이있는 문제에 대해 작업 중이며 사용자로부터 입력을 받아 입력을 검색하고 첫 번째 인스턴스를 반환해야합니다. (존재하는 경우) 및 나타나는 횟수가 표시됩니다.

다음 접근 방식으로 프로그램을 작성했습니다. 사용자로부터 입력을받습니다. 그런 다음 이진 검색을 사용하여 값을 찾습니다. 존재한다면 인덱스를 m으로 저장합니다. 그 후 두 개의 while 루프를 작성합니다. 첫 번째 루프는 왼쪽에있는 값의 발생 횟수를 확인하고 두 번째 루프는 값을 같지만 오른쪽으로 계산합니다. 예를 들어, 2 진 검색은 5를 찾고있을 것입니다. 그러나, 그것은 제 3의 것에 상륙한다, 즉. {.....5,5,**5**,5....}. 첫 번째 while 루프는 두 개를 계산하고 두 번째 루프는 한 개를 계산합니다. 그런 다음 모두 합계하여 총 인스턴스 수를 반환합니다. 입력 값이 없으면 앞에서 언급 한 코드를 건너 뛰고 간단히 -1을 반환합니다.

main 함수의 본문에서 반환 값을 확인합니다. 값이 -1 인 경우 값을 찾지 못했음을 사용자에게 알립니다. 반환 값이> = 0이면 필요한 정보를 인쇄합니다.

어쨌든 프로그램의 C 코드를 작성했지만 정상적으로 작동하지 않습니다. 나는 seg.를 얻는다. 오류 오류, 내가 뭘 잘못하고 있는지 모르겠다. 어쨌든, 어떤 도움을 주시면 감사하겠습니다. 나는이 문제에 대한 내 머리를 잠시 두드리고있다. 흥미롭고 힘들었습니다. 저는 올바른 논리를 가지고 있다고 생각합니다. 하지만 제대로 작동하지 않습니다. 뭔가 의미

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stddef.h> 

/* function prototype */ 

int get_num_of_ints(const int* arr, size_t r, int N, size_t* f, size_t* count); 

int main() 
{ 
    int i; 
    int N;          /* input variable */ 
    int arr[]={1,1,2,3,4,4,4,4,5,5,6,7,7,7,7,8,9,9};     /* array of sorted integers */ 
    size_t r = sizeof(arr[i])/sizeof(int);      /* right bound */ 
    size_t f;          /* first match index */ 
    size_t *fPtr; 
    fPtr = &f; 
    size_t count;          /* total number of matches */ 
    size_t *countPtr;         
    countPtr = &count; 

    printf("\nPlease input the integer you would like to find.\n"); 
    scanf("%d", &N); 

    int a = get_num_of_ints(arr, r, N, fPtr, countPtr); 

    if(a == -1)  
    printf("%d has not been found.\n", N); 

    else if(a >= 0){ 
    printf("The first index is %d.\n", f); 
    printf("The total number of values is %d.\n", count); 
    } 

    return 0; 
} 

/* function definition */ 

int get_num_of_ints(const int* arr, size_t r, int N, size_t* f, size_t* count) 
{ 
    int l = 0; 
    int m; 
    int w=r; 
    size_t *fPtr; 
    size_t *countPtr; 


    while(l <= r){ 
     m = l +(r - l)/2; 
     if(arr[m] < N) 
      l = m+1; 
     else if(arr[m] > N) 
      r = m-1; 
     else if(arr[m]==N) 
      m=m; 
      break; 
    } 
    if(l > r) 
     m = -1; 

    if(m >= 0){ 

     int j = m-1; 
     int L = 0; 

     while(arr[j] == arr[m] && j >= 0){ 
      L++; 
      j--; 
     } 


     if(j>= 0 && L > 0) 
      *fPtr=j; 
     else 
      *fPtr=m; 

     int h = m + 1; 
     int R = 0; 

     while(arr[h]==arr[m] && h <= w){ 
      R++; 
      h++; 
     } 

     *countPtr = (R + L + 1); 
     return *fPtr; 
    } 

    else if(m==-1) 
     return -1; 
} 

Answer 1

1. 사용 변수 이름 : 어쨌든, 여기에 코드입니다. 문제를 즉시 발견 할 수 있습니다.

2. 디버거에서 프로그램을 실행하고 코드를 단계별 실행하십시오. 당신은 일들이 꽤 빨리 잘못되는 곳을보아야합니다. 힌트, get_num_of_ints에 사용 된 fPtr은 무엇입니까? 다른 사람들도 지적했듯이 다른 버그가 있습니다.

Answer 2

발생 횟수가 필요하므로 각 요소를 검색해야합니다. 맞습니까?

사물을 단순화하고 선형 스캔 만하는 것이 어떨까요? 다음은 몇 가지 의사 코드는 다음과 같습니다

function get_num_of_ints(arr, n){ 
    first_index = -1 
    count = 0 

    for(i = 0; i < length(arr); i++) 
     if(x == n){ 
      count++ 
      if(first_index == -1) 
       first_index = i 
     } 

    return count, first_index 
} 

Answer 3

while(arr[j] == arr[m] && j >= 0) 

당신은 여기에 두 가지 조건의 순서를 전환해야하거나 arr[-1]을 읽으려고합니다. 두 번째 while 루프도 똑같습니다.

arr[array_size]이 끝나기 때문에 r은 배열 크기보다 1 작게 시작해야한다는 또 다른 문제가 있습니다.

편집 :

심각한 문제가 당신이 *count 및 *f에 기록해야 할 때 초기화되지 않은 포인터 countPtr 및 fPtr에 작성하는 것입니다. 이것은 아마 segfault를 일으키는 원인 일 것입니다. 이것은 디버거에서 발견하기 쉬웠을 것입니다.

Answer 4

내가 지금 앉아있어 컴퓨터의 C 컴파일러가없는, 그래서 그것을 테스트 할 수 없습니다,하지만 난 당신의 함수의 첫 번째 동안 루프에서 당신이 말하고있는 것을 볼 수 :

else if(arr[m]==N) 
      m=m; 
      break; 

break 문은이 경우 if 문 외부에 있으므로 while 루프는 매번 한 번만 실행됩니다.

이것이 오류의 원인인지는 모르겠습니다.

Answer 5

get_num_of_ints() 함수에서 메모리를 할당하지 않고 fptr 포인터를 사용하고 있습니다.

Answer 6

분할 오류가 라인 74, 77 get_num_of_ints()에서 유래하고, 87

if(j>= 0 && L > 0) 
    *fPtr=j; 
else 
    *fPtr=m; 
... 
*countPtr = (R + L + 1); 

당신은 포인터에 메모리 주소를 할당하지 않은, 따라서 이러한에서 임의의 메모리 위치를 사용하는 윤곽.

어쨌든 이러한 변수에 대한 포인터를 사용하는 실제 이유가없는 것 같습니다. size_t에 대한 포인터에서 size_t 유형의 변수로 변경해보십시오.

size_t fPtr; 
size_t countPtr; 

Answer 7

모두의 의견에 감사 드리며, 내 프로그램에서 모든 버그를 찾을 수 있었으며 gdb 디버거도 사용할 수있었습니다. 어쨌든, 나는 더 이상 나의 seg가 없다. 프로그램을 실행할 때 오류 오류; 그러나 나는 사용자에게 입력을 요구할 때 어떤 종류의 논리 문제가 발생하고 사용자 유형 4라고 말하면 발생 횟수 및 발생 빈도가 가비지 값입니다.

내가 얻을 :

이 내 기능의 마지막 두 개의 매개 변수로 이전 한 문제를 중심으로 돌아

Please input the integer you would like to find. 
4 
The first index is -1075300456. 
The total number of values is 12169204. 

. 아래쪽의 함수 정의에서 count는 목록에서 발견 된 총 발생 횟수입니다. 모두 countPtr 및 fPtr 요구 지적

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stddef.h> 

/* function prototype */ 

int get_num_of_ints(const int* arr, size_t r, int N, size_t f, size_t count); 

int main() 
{ 
    int i; 
    int N;          /* input variable */ 
    int arr[]={1,1,2,3,4,4,4,4,5,5,6,7,7,7,7,8,9,9};     /* array of sorted integers */ 
    size_t r = sizeof(arr)/sizeof(arr[0]) - 1;     /* right bound */ 
    size_t f;          /* first match index */ 


    size_t count;          /* total number of matches */ 


    printf("\nPlease input the integer you would like to find.\n"); 
    scanf("%d", &N); 

    int a = get_num_of_ints(arr, r, N, f, count); 

    if(a == -1)  
    printf("%d has not been found.\n", N); 

    else if(a >= 0){ 
    printf("The first index is %d.\n", f); 
    printf("The total number of values is %d.\n", count); 
    } 

    return 0; 
} 

/* function definition */ 

int get_num_of_ints(const int* arr, size_t r, int N, size_t f, size_t count) 
{ 
    int l = 0; 
    int m; 
    int w=r; 


    while(l <= r){ 
     m = l +(r - l)/2; 
     if(arr[m] < N) 
      l = m+1; 
     else if(arr[m] > N) 
      r = m-1; 
     else if(arr[m]==N){ 
      m=m; 
      break; 
     } 
    } 
    if(l > r) 
     m = -1; 

    if(m >= 0){ 

     int j = m-1; 
     int L = 0; 

     while(j >= 0 && arr[j] == arr[m]){ 
      L++; 
      j--; 
     } 


     if(j>= 0 && L > 0) 
      f=j; 
     else 
      f=m; 

     int h = m + 1; 
     int R = 0; 

     while(arr[h]==arr[m] && h <= w){ 
      R++; 
      h++; 
     } 

     count = (R + L + 1); 
     return f; 
    } 

    else if(m==-1) 
     return -1; 
} 

Answer 8

1. 같이 메모리 할당 될

   를 size_t * = fPtr의 malloc (sizeof 연산자 (이 size_t));

2. , 당신이 그것을

3. 이 # gcc -g -Wall <your c file name> -o 시작

   arraysort 디버거 (당신이 리눅스에있는 경우) 프로그램을 컴파일 사용하기 전에 "I"일부 값을 초기화하기 확인 찾기 위해 코드를 단계별로 out valeues, r, arr [m]에 대한 몇 가지 재미있는 값을 찾았습니다.

   #gdb./

   B 실행 을 arraysort

HTH