c - 计数排序，正常运行但不时报segmentfault，求助

问题描述

问 题

计数排序，不知怎么的是不是报错segmentfault，但是有时又能正常运行，实在找不出原因，gdb调试技巧不高，附上完整源代码，求助高手！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <unistd.h>
#include <time.h>

typedef enum _Ret {
    RET_OK,
    RET_OOM,
    RET_STOP,
    RET_INVALID_PARAMS,
    RET_FAIL
}Ret;

typedef int  (*DataCompareFunc)(void* ctx, void* data);
typedef Ret  (*SortFunc)(void** array, size_t size, DataCompareFunc cmp, void* ctx);

#define return_if_fail(p) if(!(p)) \
    {printf("%s:%d Warning: "#p" failed.\n", \
        __func__, __LINE__); return;}
#define return_val_if_fail(p, ret) if(!(p)) \
    {printf("%s:%d Warning: "#p" failed.\n",\
    __func__, __LINE__); return (ret);}

#define SAFE_FREE(p) if(p != NULL) {free(p); p = NULL;}


Ret counts_sort(void** array, size_t size, DataCompareFunc cmp, void* ctx) {
    int i = 0;
    void* counts_nr = ctx;

    return_val_if_fail(array != NULL, RET_INVALID_PARAMS);

    if(size < 2) {
        return RET_OK;
    }

    // temp memory
    int* counts = malloc(sizeof(int) * (int)counts_nr);
    memset(counts, 0, sizeof(int) * (int)counts_nr);
    void** storage = malloc(sizeof(void*) * size);

    // counts
    for(i = 0; i < size; i++) {
        ++counts[ (int)array[i] ];
    }
    // accumulating counts
    for(i = 0; i < (int)counts_nr; i++) {
        counts[i + 1] += counts[i];
    }

    // sort
    for(i = size - 1; i >= 0; i--) {
        storage[--counts[ (int)array[i] ]] = array[i];
    }

    // copy back
    memcpy(array, storage, size * sizeof(void**));

    // free temp memory
    SAFE_FREE(counts);
    SAFE_FREE(storage);

    return RET_OK;
}

int int_cmp_asc(void* a, void* b) {
    return ( (int)a - (int)b );
}

static void array_print(void** array, size_t size) {
    size_t i = 0;
    while(i < size) {
        printf("%d ", (int)array[i]);
        i++;
    }
    printf("\n");
    return;
}

static void** create_int_array(int size) {
    int i = 0;
    void** array = malloc(sizeof(void*) * size);
    for(i = 0; i < size; i++) {
        array[i] = (void*)(rand() % 100);
    }
    return array;
}

static void sort_test_one_asc(SortFunc sort, int size) {
    int i = 0;
    void* max_nr = NULL;
    void* ctx = NULL;
    void** array = create_int_array(size);

    for(i = 0; i < size; i++) {
        if(int_cmp_asc(array[i], max_nr) > 0) {
            max_nr = array[i];
        }
    }
    ctx = (void*)((int)max_nr + 1);

    sort(array, size, int_cmp_asc, ctx);
    array_print(array, size);

    SAFE_FREE(array);

    return;
}

void sort_test(SortFunc sort) {
    int i = 0;
    for(i = 0; i < 10; i++) {
        sort_test_one_asc(sort, i);
    }
    return;
}

int main(int argc, char* agrv[]) {
    srand((unsigned)time(NULL));

    sort_test(counts_sort);

    return 0;
}

解决方案

int counts = malloc(sizeof(int) (int)counts_nr);
改成：
int counts = malloc(sizeof(int) (int)counts_nr + 1);
因为你内存越界了，在：

// accumulating counts
for(i = 0; i < (int)counts_nr; i++) {
    counts[i + 1] += counts[i];<-------------越界了
}

这篇关于c - 计数排序，正常运行但不时报segmentfault，求助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！