c - 逻辑错误-插入排序

Closed. This question is off-topic. It is not currently accepting answers. Learn more。
想改进这个问题吗？Update the question所以堆栈溢出的值小于aa>。
两年前关闭。
代码目录结构，

$ pwd
/home/Personal/../Computing
$ ls -LR
.:
list testList.c testList.exe type.h

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

/********* type.h ********/
#ifndef TYPE_H
#define TYPE_H /* Header guard */
 #include<stdbool.h>
 #include<stddef.h>
 #include<stdlib.h>
 #include<stdio.h>
 #include<string.h>
#endif /* TYPE_H */

/************ list.h ************/

#ifndef LIST_H /* Header guard */
#define LIST_H
#include"type.h"

/***************** Usage-start ************/

#if defined(ARRAY) || (LINKED_LIST)

  /* To ensure Encapsulation(i.e., maintain invariants of array & linked list)
     So, Just provide the `List` declartion, to avoid mis-use of `List`
  */
  typedef struct List List;

#else
  #error "Wrong list implementation macro name !!!"
#endif



 void listInsertItem(List *, void *newItem);
 void *listDeleteItem(List *, int listIndex);
 void *listDeleteLastItem(List *);
 void *listDeleteFirstItem(List *);
 const void *listGetItem(List *, const int index); /* 'index' is array index */
 int listGetSize(List *);


 /*********** Searching & Sorting algorithm - start*************/

 typedef int (*compareTo)(const void *key, const void *item);
 typedef bool (*isLess)(const void *key, const void *item);
 typedef bool (*isEqual)(const void *key, const void *item);

 void *linearSearch(const void *key, List *, size_t listSize, isEqual);
 /*
   bsearch() function returns a pointer to a matching member
   of the array, or NULL if no match is found
 */
 void *binarySearch(const void *key, List *, size_t listSize, compareTo);


 /*'listSize' elements. First argument points to list.*/
 void insertionSort(List *, size_t listSize, isLess);
 void selectionSort(List *, size_t listSize, compareTo);
     void shellSort(List *, size_t listSize, compareTo);
     void mergeSort(List *, size_t listSize, compareTo);
     void quickSort(List *, size_t listSize, compareTo);
/**************** Sorting algorithm - end*************/

 List* createList();
 void freeList(List *);
#endif /* LIST_H */

/***************** Usage-end ***************/

下面是数组实现，

/***************** arrayImpl.c **************/

#include"list/list.h"

#if defined(ARRAY)
typedef enum {DOUBLE_THE_LIST, HALF_THE_LIST}ListResizeOperation;

static List *resizeList(List *, ListResizeOperation);
static void *bSearchRecur(const void *, void**, int, int, compareTo);
static void *bSearchIter(const void *, void **, int, int, compareTo);

static void swap(void **, int i, int j);
static void insSort(void **, size_t, isLess);

/************ Representation - start ************/
typedef struct List{
  void **array;

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

#define INITIAL_LIST_SIZE 50
#define FIRST_ITEM_INDEX 0
/********************* Representation - end ************/




/************* Usage - start ***************/
List *createList(){

    List *list = malloc(sizeof(List));
    if(list != NULL){

      list->array = malloc(INITIAL_LIST_SIZE*sizeof(void*));
      if(list->array != NULL){

        /* Is it safe to initialise zero to  array of  pointers? */
        list->array = memset(list->array, 0, INITIAL_LIST_SIZE*sizeof(void *));
        list->lastItemPosition = -1;
        list->size = INITIAL_LIST_SIZE;
      }else{
        free(list);
        list = NULL;
      }
    }

    return list;
}

void freeList(List *list){

  if(list != NULL){
    if(list->array != NULL){
      int index = 0;
      while( index < list->size){
        free(list->array[index++]);
      }
      free(list->array);
    }else{
      fprintf(stderr, "Invalid list sent to freeList()\n");
    }
    free(list);
  }
}


int listGetSize(List *list){
  if(list != NULL){
    return list->lastItemPosition + 1;
  }else{
    fprintf(stderr, "List is NULL\n ");
    return -1;
  }
}

const void *listGetItem(List *list, const int index){
  if((index >=0) && (index < list->size)){
    return (const void *)list->array[index];
  }else{
    return NULL;
  }
}

void listInsertItem(List *arrayList, void *newItem){

  if(arrayList == NULL){
    fprintf(stderr, "listInsertItem() -Invalid list \n");
    return;
  }
  /* House keeping - Enhance the array */
  if(arrayList->lastItemPosition + 1 == arrayList->size){
    arrayList = resizeList(arrayList, DOUBLE_THE_LIST);
    if(arrayList == NULL){
      fprintf(stderr, "insertItem() - Unable to allocate memory \n");
      exit(1);
    }
  }


  /* Insert new element - O(1) operation */
  arrayList->array[++(arrayList->lastItemPosition)] = newItem;


}

void *listDeleteItem(List *arrayList, int listIndex){

  if(arrayList == NULL){
    fprintf(stderr, "Invalid list \n");
    return NULL;
  }

  void *returnElement  = arrayList->array[listIndex];

  /* Delete operation - O(n) operation */
  for(int accumulator = listIndex; accumulator <= arrayList->lastItemPosition; accumulator++){
    arrayList->array[accumulator] = arrayList->array[accumulator + 1];
  }

  arrayList->lastItemPosition--;


  /* House keeping - Half the list */
  if(arrayList->size > INITIAL_LIST_SIZE){ /* Minimum size maintained */
    if((arrayList->lastItemPosition + 1) == ((arrayList->size)/2)){
      arrayList = resizeList(arrayList, HALF_THE_LIST);
      if(arrayList == NULL){
        fprintf(stderr, "deleteItem() - Unable to allocate memory \n");
        exit(1);
      }
    }
  }
  return returnElement; /* User must free this element*/
}


void * listDeleteLastItem(List *arrayList){
  return listDeleteItem(arrayList, arrayList->lastItemPosition);
}

void *listDeleteFirstItem(List *arrayList){
  return listDeleteItem(arrayList, FIRST_ITEM_INDEX);
}



/**************Searching & Sorting -start **************/
void *linearSearch(const void *key, List *list, size_t listSize, isEqual equal){

  if(list != NULL && (listSize > 0)){
    void ** array = list->array;
    for(int index =0; index < listSize; index++){
      if(equal(key, (array[index])) ){
        return array[index];
      }
    }
  }
  return NULL;
}

void *binarySearch(const void *key, List *list, size_t listSize, compareTo compare){
  if(list != NULL && (listSize > 0)){
    return bSearchIter(key, list->array, 0, listSize-1, compare);
    //return bSearchRecur(key, list->array, 0, listSize-1, compare);
  }
  return NULL;
}

void insertionSort(List *list, size_t listSize, isLess less){
  if(list!=NULL && (listSize > 0)){
    insSort(list->array, listSize, less);
  }
}
/**************Searching & Sorting -end **************/




/******************** Usage - end *******************/

/************* helper function - start     ********/


static void swap(void **array, int i, int j){
  void *tempPointer = array[i];
  array[i] = array[j];
  array[j] = tempPointer;
}


static void insSort(void **array, size_t listSize, isLess less){
  for(int sortedBoundaryIndex = -1; sortedBoundaryIndex < listSize; sortedBoundaryIndex++){
    /*
      -1 mean sorted pool is yet to form.
       0 mean first element is in sorted pool
    */

    for(int unSortedElementIndex = sortedBoundaryIndex + 1; unSortedElementIndex > 0; unSortedElementIndex--){
      /* Within this loop, sorted pool does not exist, as unsorted new element is being compared*/
      if(less(array[unSortedElementIndex], array[unSortedElementIndex-1])){
        swap(array, unSortedElementIndex, unSortedElementIndex-1);
      }else{
        break; //If the unsorted element is > or ==, no swap, Stable sort
      }
    }
  }

}


static void *bSearchIter(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

  int mid =0;
  while(lowerBound <= upperBound){

    mid = (lowerBound + upperBound)/2;

    if(compare(key, array[mid]) == 0){

      return array[mid];
    }else if(compare(key, array[mid]) < 0){
      upperBound = mid-1;
    }else if(compare(key, array[mid]) > 0){
      lowerBound = mid + 1;
    }
  }/* end while */

  return NULL;
}

static void *bSearchRecur(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

  if(lowerBound > upperBound) return NULL;

  int mid = (lowerBound + upperBound)/2;

  if(compare(key, array[mid]) == 0){

    return array[mid];
  }else if(compare(key, array[mid]) < 0){

    return bSearchRecur(key, array, lowerBound, mid-1, compare);
  }else { // compare() > 0

    return bSearchRecur(key, array, mid+1, upperBound, compare);
  }
}



/* resizeList() is not visible to Linker (ld) */

static List *resizeList(List *list, ListResizeOperation opType){

  if(opType == DOUBLE_THE_LIST){

    list->array = realloc(list->array, 2*(list->size)*sizeof(void *));
    if(list->array == NULL){ return NULL; }
    list->lastItemPosition = list->lastItemPosition;;
    list->size = 2*(list->size);
  }else if(opType == HALF_THE_LIST){

    list->array = realloc(list->array, ((list->size)/2)*sizeof(void *));
    if(list->array == NULL){ return NULL; }
    list->lastItemPosition = list->lastItemPosition;
    list->size = (list->size)/2;
  }

  return list;
}

/************* helper function - end     *************/

#endif

执行插入排序，但在用户代码下面，

/************************* testList.c *****************/
#include"list/list.h"
#include<time.h>
#include<stdlib.h>


bool equal (const void * key, const void *item){
  if( *((int *)key) == *((int *)item) ){
    return true;
  }else{
    return false;
  }
}

bool less (const void * key, const void *item){
  if( *((int *)key) < *((int *)item) ){
    return true;
  }else{
    return false;
  }
}


int compare(const void *key, const void *item){
  if( *((int *)key) == *((int *)item) ){
    return 0;
  }else if((int *)key < (int *)item){
    return -1;
  }else{
    return 1;
  }
}

int main(void){
  // Comments in the below, how do I formally convey to user ?
  List *arrayList = createList();
  int *item = NULL;
  srand(time(NULL));
  for(int input = 10; input > 0; input--){
    item = malloc(sizeof(int));
    *item = rand();
    listInsertItem(arrayList, item);
  }

  item = (int  *)listGetItem(arrayList, 0); // Returns (const void *)
  printf("First item: %d\n", *item);

  printf("\nSize of list: %d\n", listGetSize(arrayList));

  int *item1 = listDeleteItem(arrayList, 3);
  free(item1); // User's responsibility to avoid leak, after calling deleteItem()
  printf("One item deleted \n");

  printf("\nSize of list: %d\n", listGetSize(arrayList));

  printf("Item found after linear search: %d\n",*(int *)(linearSearch(item, arrayList, listGetSize(arrayList), equal)));
  printf("Item found after Binary search: %d\n",*(int *)(binarySearch(item, arrayList, listGetSize(arrayList), compare)));
  insertionSort(arrayList, listGetSize(arrayList), less);

  printf("Sorted array \n");
  for(int index =0; index < listGetSize(arrayList); index++){
    printf("Element: %d \n", *((const int *)listGetItem(arrayList, index)));
  }


  freeList(arrayList);  // User is responsible to free list, before stop using list
}

不打印排序数组。
编译成功，使用以下指令，

> pwd
/home/Personal/../Computing
> `gcc -Wall -g -I. -DARRAY ./list/*.c testList.c -o testList`
./list/arrayImpl.c:240:14: warning: ‘bSearchRecur’ defined but not used [-Wunused-function]
 static void *bSearchRecur(const void *key, void **array, int lowerBound, int upperBound, compareTo compare){

但结果是，

$ ./testList.exe
First item: 2043943058

Size of list: 10
One item deleted

Size of list: 9
Item found after linear search: 2043943058
Item found after Binary search: 2043943058

Before sorting
Element: 1611124216
Element: 1315139801
Element: 642548661
Element: 1598077511
Element: 792705528
Element: 913581568
Element: 1766294466
Element: 1469344807
Element: 895523447

After sorting
Element: 1611124216
Element: 1315139801
Element: 642548661
Element: 1598077511
Element: 792705528
Element: 913581568
Element: 1766294466
Element: 1469344807
Element: 895523447

排序后的预期输出为：

After sorting
Element: 1611124216
Element: 1315139801
Element: 642548661
Element: 1598077511
Element: 792705528
Element: 913581568
Element: 1766294466
Element: 1469344807
Element: 895523447

问题：
调用insertionSort(arrayList, listGetSize(arrayList), less);后元素未被排序，
如何解决这个问题？这与指针有关吗？
注意：Cygwin对gdb没有帮助。

最佳答案

在insSort函数中，有sortedBoundaryIndex类型的int（signed）从-1开始，然后在for条件下与listSize类型的size_t进行比较（unsigned）。当比较两个数字（一个有符号，另一个无符号）时，有符号的数字被解释为一个无符号的数字（更糟糕的是，有符号的数字越低，其解释就越大）。所以-1（因为它是最低负数）将被解释为unsigned int的最大可能值，即4294967295。因此，循环从未进入。无论如何，sortedBoundaryIndex从-1开始是没有意义的，因为内环的条件会失败，所以sortedBoundaryIndex应该从0开始。
注意：外循环的条件应该是sortedBoundaryIndex < listSize - 1而不是sortedBoundaryIndex < listSize，因为在内循环中，您将1添加到sortedBoundaryIndex以获取unSortedElementIndex并将其用作array的下标，因此当sortedBoundaryIndex到达listSize - 1时，unSortedElementIndex将等于listSize这是越界的，并将导致执行错误。
这是我的insSort函数版本（我使用while而不是for作为内环，当然我使用了短名称）：

static void insSort(void **array, size_t listSize, isLess less){
    for(int sbi = 0; sbi < listSize - 1; sbi++){
        int usei = sbi + 1;
        while(usei > 0 && less(array[usei], array[usei - 1])){
            swap(array, usei, usei - 1);
            usei--;
        }
    }
}

关于c - 逻辑错误-插入排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41389354/