C动态数组内存分配、填充和排序

Question

我正在创建四个函数：

为数组分配内存
生成随机字符并填充数组
将数组升序排列
打印排序后的数组

正如您将在代码中看到的那样，我使用 printf 查看生成的字符。
问题是，排序功能无法正常工作，我不明白问题出在哪里（我得到一个输出，其中字符没有按应有的方式排序）。

有人可以告诉我我做错了什么吗？关于如何改进所有代码的任何其他提示也将受到欢迎。

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

int size = 20;
char* pArrChar1;
void allocate(char**);
void fill(char*);
void sort(char*);
void printArr(char*);

void main() {

    allocate(&pArrChar1);
    fill(pArrChar1);
    sort(pArrChar1);
    printArr(pArrChar1);

   system("pause");
}

void allocate(char** p_char) {
    *p_char = (char*)malloc(size*sizeof(char));
}

void fill(char* p_char) {
    int max = 90 ;
    int min = 65;
    for (int i = 0; i < size; i++) {
        p_char[i]= (char)(rand() % (min + 1 - max) + min);
        printf("%c ", p_char[i]);
    }
    printf("\n\n");
}

void sort(char* p_char) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 1; j++) {
            if (*(p_char + j) > *(p_char + j + 1)) {
                char tmp = *(p_char + j);
                *(p_char + j) = *(p_char + j + 1);
                *(p_char + j + 1) = tmp;
            }
        }
    }
}

void printArr(char* p_char) {
    for (int i = 0; i < size; i++)
        printf("%c ", p_char[i]);
   printf("\n\n");
}

Answer 1

您在第 38 行有一个实施错误。下面这个详细的输出显示了它在哪一行出错。 "ASan" 工具声称您有 heap buffer overflow.

当 i 为 19 时，您取消引用 p_char[20]，这超出了分配的末尾。

$ clang -fsanitize=address -g -Wall sorter.c 
sorter.c:11:1: warning: return type of 'main' is not 'int' [-Wmain-return-type]
void main() {
^
sorter.c:11:1: note: change return type to 'int'
void main() {
^~~~
int
1 warning generated.
$ ./a.out 
H W J T R H K M J N C T C T L W M S E Q 

=================================================================
==7176==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60300000eff4 at pc 0x0000004cd8af bp 0x7fff8db88420 sp 0x7fff8db88418
READ of size 1 at 0x60300000eff4 thread T0
    #0 0x4cd8ae in sort /home/brian/src/so/sorter.c:38:33
    #1 0x4cd5e4 in main /home/brian/src/so/sorter.c:15:5
    #2 0x7fbeb021da3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)
    #3 0x417508 in _start (/home/brian/src/so/a.out+0x417508)

0x60300000eff4 is located 0 bytes to the right of 20-byte region [0x60300000efe0,0x60300000eff4)
allocated by thread T0 here:
    #0 0x4a626b in __interceptor_malloc /home/development/llvm/3.7.0/final/llvm.src/projects/compiler-rt/lib/asan/asan_malloc_linux.cc:40:3
    #1 0x4cd65c in allocate /home/brian/src/so/sorter.c:22:22
    #2 0x4cd576 in main /home/brian/src/so/sorter.c:13:5
    #3 0x7fbeb021da3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x20a3f)

SUMMARY: AddressSanitizer: heap-buffer-overflow /home/brian/src/so/sorter.c:38:33 in sort
Shadow bytes around the buggy address:
  0x0c067fff9da0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9db0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9dc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9dd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9de0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c067fff9df0: fa fa fa fa fa fa fa fa fa fa fa fa 00 00[04]fa
  0x0c067fff9e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff9e40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==7176==ABORTING

Answer 2

在您的代码中，您有：

for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1; j++) {
        if (*(p_char + i) > *(p_char + i + 1)) {

当 i 等于 size - 1 时，您正在越界访问。

更改循环限制：

for (int i = 0; i < size - 1; i++) {
    for (int j = 0; j < size; j++) {
        if (*(p_char + i) > *(p_char + i + 1)) {

这样至少避免了数组越界访问。令人惊讶的是，您没有使用 i 和 j 作为下标；你似乎重复写了很多相同的比较。

Answer 3

这里我用下面的更新了排序函数；

/* new sort */
void sort2(char* p_char) {
    counter = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (*(p_char + i) > *(p_char + j)) {
                char tmp = *(p_char + i);
                *(p_char + i) = *(p_char + j);
                *(p_char + j) = tmp;

                counter++;
            }
        }
    }
    printf("Sort2 process # : %d\n", counter);
}

并且使用这个更新的排序，改进了寻找解决方案的进程数，50,000 个随机字符的输出如下；

D:\SOF>gcc main.c -Wall -Wextra -pedantic -std=c11 -o main

D:\SOF>main
Sort  process # : 598810451
Sort2 process # : 574789

请查看下面的测试代码；

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

#define MAX_SIZE 50000

int counter = 0;
int size = MAX_SIZE;
char* pArrChar1;
void allocate(char**);
void fill(char*);
void sort(char*);
void sort2(char* p_char); /* updated sort */
void printArr(char*);

int main() {

    allocate(&pArrChar1);
    fill(pArrChar1);
    sort(pArrChar1);
    //printArr(pArrChar1);

    allocate(&pArrChar1);
    fill(pArrChar1);
    sort2(pArrChar1);

    system("pause");

    return 0;
}

void allocate(char** p_char) {
    *p_char = (char*)malloc(size*sizeof(char));
}

void fill(char* p_char) {
    int max = 90 ;
    int min = 65;
    for (int i = 0; i < size; i++) {
        p_char[i]= (char)(rand() % (min + 1 - max) + min);
        //printf("%c ", p_char[i]);
    }
    //printf("\n\n");
}

void sort(char* p_char) {
    counter = 0;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 1; j++) {
            if (*(p_char + j) > *(p_char + j + 1)) {
                char tmp = *(p_char + j);
                *(p_char + j) = *(p_char + j + 1);
                *(p_char + j + 1) = tmp;

                counter++;
            }
        }
    }
    printf("Sort  process # : %d\n", counter);
}

/* new sort */
void sort2(char* p_char) {
    counter = 0;
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (*(p_char + i) > *(p_char + j)) {
                char tmp = *(p_char + i);
                *(p_char + i) = *(p_char + j);
                *(p_char + j) = tmp;

                counter++;
            }
        }
    }
    printf("Sort2 process # : %d\n", counter);
}

void printArr(char* p_char) {
    for (int i = 0; i < size; i++)
        printf("%c ", p_char[i]);
    printf("\n\n");
}

希望对您有所帮助！

Answer 4

排序函数有错误，这是正确的

void sort(char* p_char) {
for (int i = 0; i < size; i++) {
    for (int j = 0; j < size - 1; j++) {
        if (*(p_char+j) > *(p_char + j + 1)) {
            char tmp = *(p_char + j);
            *(p_char + j) = *(p_char + j + 1);
            *(p_char + j + 1) = tmp;
        }
      }
   }
}

C动态数组内存分配、填充和排序

C dynamic array memory allocation, filling and sorting

c

memory

arrays

sorting

allocation