문자열 C에서 문자 정렬 병합

Question

나는이 작업 병합 정렬 알고리즘을 C로 가지고 있습니다. 그러나 정수에서만 작동합니다. int를 char로 변경하려고하면 segfault가 발생합니다. 나는이 코드를 변경해야합니다 당신이 좀 도와 주시겠습니까

, 그래서 나는 다음과 같이 머지 소트를 사용할 수 있습니다 내가

char*str = "test_string"; 
MergeSort(str, 0, strlen(str)-1); 

---

void Merge(int *array, int left, int mid, int right){ 

    int tempArray[right-left+1]; 
    int pos=0,lpos = left,rpos = mid + 1; 

    while(lpos <= mid && rpos <= right){ 
      if(array[lpos] <= array[rpos]){ 
        tempArray[pos++] = array[lpos++]; 
      } 
      else{ 
        tempArray[pos++] = array[rpos++]; 
      } 
    } 

    while(lpos <= mid) tempArray[pos++] = array[lpos++]; 
    while(rpos <= right)tempArray[pos++] = array[rpos++]; 

    int iter; 
    for(iter = 0;iter < pos; iter++){ 
      array[iter+left] = tempArray[iter]; 
    } 

    return; 
} 

void MergeSort(int *array, int left, int right){ 
    int mid = (left+right)/2; 

    if(left<right){ 
      MergeSort(array,left,mid); 
      MergeSort(array,mid+1,right); 
      Merge(array,left,mid,right); 
    } 
    return; 
} 

을 잃었어요합니다. 감사!

Answer 1

array의 선언을 두 기능 모두에서 int *에서 char *으로 변경하십시오. int[] 대신 tempArray을 char[]으로 지정하십시오. 배열 끝에서 4x (또는 8x) 범위 밖의 메모리를 읽으려고하므로 seg-fault가 발생합니다. 다른 말로하면 char은 1 바이트 (일반적으로) 인 반면 int은 4 또는 8이므로 서로 다른 크기의 항목이 나란히 놓여 있습니다. 또한 문자열에 const *을 전달하지 마세요. char*str = "test_string";으로 문자열을 선언하면 일부 시스템에서 읽기 전용 메모리가 사용됩니다. 대신 char str[] = "test_string";을 사용하십시오. http://www.codeproject.com/Articles/257589/An-Idiots-Guide-to-Cplusplus-Templates-Part-1

Answer 2

#include <stdio.h> 

#include<ctype.h> 

#include<string.h> 

int Run_count=-1; 

int main (int argc , char *argv[]) 
{ 

    /* if you dont want to use argv, put the elements in A yourself, 
    size being the number of string*/ 

    /*L --> left side, R --> right side*/ 

    int i = 0; 

    int size = argc-1; 

    char *A[argc-1]; 

    for(i=1;i<=argc;i++){*(A+i-1) = argv[i];} 

    Caller(A,size); 

    for(i=0;i<size;i++){ 

     printf("%s\n", A[i]); 

    } 

    printf("%d",Run_count); 
} 

int Caller(char* A[] , int n){ 

    Run_count++; 

    int sizeL, sizeR ,i; 

    char *L[n/2+1] , *R[n-n/2+1]; 

    if (n < 2){return 1;} 

    sizeL = n/2; 
    sizeR = n - sizeL; 

    for(i=0;i<sizeL;i++) {L[i] = *(A+i);} 
    for(i=0;i<n - n/2;i++) {R[i] = *(A+i+n/2);} 

    Caller(L, sizeL); 
    Caller(R, sizeR); 
    merger(L,sizeL, R,sizeR, A); 
} 

void merger(char* L[], int lengthL , char* R[] , int lengthR , char *A[]){ 

    int i, j, k ,t =0 ; 

    for(k = 0 , j = 0; k < lengthL && j < lengthR ;t++){ 

     if(compare(*(L+k),*(R+j))){ 
      *(A+t) = *(L+k); 
      k++;} 

     else{*(A+t) = *(R+j);j++;} 
    } 

    while(k < lengthL){ 
     *(A+t) = *(L+k); 
     k++;t++; 
     } 

    while(j < lengthR){ 
     *(A+t) = *(R+j); 
     j++;t++;} 
} 

int compare(char *line1 , char *line2) 
{ 
    int i; 

    for(i = 0;*(line1 + i) != '\0' && *(line2 + i) != '\0' ;){ 
     if(isdigit(*(line1+i)) && isalpha(*(line2+i))){return 0;} 

     else if(isdigit(*(line2+i)) && isalpha(*(line1+i))){return 1;} 

     else if(*(line1 + i) > *(line2 + i)){return 0;} 

     else if(*(line1 + i) == *(line2 + i)){i++;} 

     else{return 1;} 
    } 
}