本文介绍了Mergesort-细分错误的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

代码目录结构,

./Computing$ ls -LR
.:
list file.txt  mergeSort.c  program.exe type.h

./list:
arrayImpl.c  linkedListImpl.c  list.h


编译过程:


Compilation procedure:

$./Computing
gcc -Wall -Werror -DARRAY -I. mergeSort.c ./list/*.c -o program


此处是包含文件mergeSort.clist/*type.h

使用List的给定表示形式,


Here is the complete code having files, mergeSort.c, list/*, type.h

With the given representation of List,

typedef struct List{
  void **array;

  /* Housekeeping - Array enhancement/shrink */
  int lastItemPosition;
  int size;
}List;


mergesort在下面的list->array上执行,其中aux维护array的浅表副本


mergesort is performed below on list->array, where aux maintains the shallow copy of array

void mergeSort(List *list, size_t listSize, isLess less){

  if(list != NULL){

    void **aux = malloc(list->size * sizeof(void*)); //Auxillary shadow copy
    if(aux != NULL){
      printf("Size of list: %d\n", listSize);
      mSort(list->array, aux, 0, listSize-1, less);
    }else{

      fprintf(stderr, "mergeSort() - Malloc failure");
      exit(EXIT_FAILURE);
    }
  }else{

    fprintf(stderr, "mergeSort() - List is NULL");
  }
}

static void mSort(void **array, void **aux, int low, int high, isLess less){

  if(high <= low) return;
  int mid = (low + high)/2;

  mSort(array, aux, low, mid, less);
  mSort(array, aux, mid+1, high, less);
  merge(array, aux, low, mid, high, less);
}

static void merge(void **array, void **aux, int low, int mid, int high, isLess less){

  for(int index = 0; index <= high; index++){
    aux[index] = array[index]; //Shallow copy
  }
  printf("Low-%d, Mid-%d, High-%d\n", low, mid, high);
  int leftIndex = low; int rightIndex = mid+1;
  printf("leftIndex-%d, rightIndex-%d\n", leftIndex, rightIndex);

  for(int index = 0; index <= high; index++){

    if(leftIndex > mid)    /* right array exhausted */  array[index] = aux[rightIndex++];
    else if(rightIndex > high) /*left array exhausted*/ array[index] = aux[leftIndex++];
    else if( less(aux[rightIndex], aux[leftIndex]) )    array[index] = aux[rightIndex++];
    else                                                array[index] = aux[leftIndex++];
  }

}


使用代码所在的地方


where the use code is,

bool less(const void *key, const void *item){
  printf("\nIn less function\n");
  printf("left-%d, Right-%d\n\n", ((Record *)key)->age, ((Record *)item)->age);
  if( ((Record *)key)->age < ((Record *)item)->age ){
    printf("Return true\n");
    return true;
  }else{
    printf("Return false\n");
    return false;
  }
}

int main(){
  FILE *pFile = fopen("file.txt", "r");
  checkHandleFailure(pFile, FILE_HANDLE_FAILURE);
  char buf[MAX_RECORD_SIZE];
  DBCache *cache = initCache(pFile);


  readHeader(pFile, cache, buf);

  readData(pFile, cache, buf);

  printRecords(cache);

  printf("Before calling mergesort() \n");
  mergeSort(cache->records, listGetSize(cache->records), less);
}



实际输出为:



Actual output is:

$ ./program.exe
Age,LastName,FirstName
------------------------------
50,B,A

30,A,B

20,X,D

10,F,A

90,V,E

60,N,M

Records#: 6
Before calling mergesort()
Size of list: 6
Low-0, Mid-0, High-1
leftIndex-0, rightIndex-1

In less function
left-30, Right-50

Return true
Low-0, Mid-1, High-2
leftIndex-0, rightIndex-2

In less function
left-20, Right-30

Return true
Low-3, Mid-3, High-4
leftIndex-3, rightIndex-4

In less function
left-90, Right-10

Return false
Low-3, Mid-4, High-5
leftIndex-3, rightIndex-5
Segmentation fault (core dumped)
In less function



如何解决此问题?



How to resolve this problem?

Cygwin不支持使用gdb的coredump跟踪格式,提供了跟踪(上方)

推荐答案

合并中的两个for循环应该从低位开始,而不是从零开始.从0开始的第二个for循环可能导致分段错误.从0开始的第一个for循环不应引起分段错误,但会浪费额外的时间.

The two for loops in merge should start at low, not at zero. The second for loop starting at 0 is probably causing the segmentation fault. The first for loop starting at 0 shouldn't cause a segmentation fault, but it consumes extra time.

static void merge(....)

    /* ... */

    for(int index = low; index <= high; index++){   // low not 0
        aux[index] = array[index];
    }

    /* ... */

    for(int index = low; index <= high; index++){   // low not 0
        if(leftIndex > mid) /* ... */
        /* ... */

这篇关于Mergesort-细分错误的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-06 05:21