realloc，堆内存泄漏
realloc, heap memory leaks
这是我从 leetcode 解决方案中算出的问题。但是内存泄漏 https://leetcode.com/problems/count-and-say/
我的生成文件
build:
gcc main.c -Wall -g -o main; \
$(PWD)/main; \
我的构建命令
make
或使用 valgrind：
make
valgrind --leak-check=yes ./main
输出：（正确，经过测试）
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
来自 Valgrind
==1796== Memcheck, a memory error detector
==1796== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et
al.
==1796== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright
info
==1796== Command: ./main
==1796==
==1796== Invalid read of size 1
==1796== at 0x100000930: countAndSay (main.c:62)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x10000096B: countAndSay (main.c:73)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x1000009D7: countAndSay (main.c:89)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 16
==1796== at 0x100655A65: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796== Address 0x10545d410 is 1 bytes after a block of size 4,463
alloc'd
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Conditional jump or move depends on uninitialised value(s)
==1796== at 0x100655A7D: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796==
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
==1796==
==1796== HEAP SUMMARY:
==1796== in use at exit: 29,301,895 bytes in 40,712 blocks
==1796== total heap usage: 80,412 allocs, 39,700 frees, 58,326,719
bytes allocated
==1796==
==1796== 72 bytes in 3 blocks are possibly lost in loss record 25 of 51
==1796== at 0x1000ABD72: calloc (vg_replace_malloc.c:755)
==1796== by 0x10075A7C2: map_images_nolock (in
/usr/lib/libobjc.A.dylib)
==1796== by 0x10076D4E0: map_images (in /usr/lib/libobjc.A.dylib)
==1796== by 0x100007C64: dyld::notifyBatchPartial(dyld_image_states,
bool, char const* (*)(dyld_image_states, unsigned int, dyld_image_info
const*), bool, bool) (in /usr/lib/dyld)
==1796== by 0x100007E39: dyld::registerObjCNotifiers(void (*)
(unsigned int, char const* const*, mach_header const* const*), void (*)
(char const*, mach_header const*), void (*)(char const*, mach_header
const*)) (in /usr/lib/dyld)
==1796== by 0x10022571D: _dyld_objc_notify_register (in /
/usr/lib/system/libdyld.dylib)
==1796== by 0x10075A073: _objc_init (in /usr/lib/libobjc.A.dylib)
==1796== by 0x1001AFB34: _os_object_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1001AFB1B: libdispatch_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1000BE9C2: libSystem_initializer (in
/usr/lib/libSystem.B.dylib)
==1796== by 0x100019AC5:
ImageLoaderMachO::doModInitFunctions(ImageLoader::LinkContext const&)
(in /usr/lib/dyld)
==1796== by 0x100019CF5:
ImageLoaderMachO::doInitialization(ImageLoader::LinkContext const&) (in
/usr/lib/dyld)
==1796==
==1796== 168 bytes in 56 blocks are definitely lost in loss record 28
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 570 bytes in 1 blocks are possibly lost in loss record 37 of
51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 1,512 bytes in 378 blocks are definitely lost in loss record
38 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 4,462 bytes in 1 blocks are definitely lost in loss record 45
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000867: countAndSay (main.c:29)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 17,848 bytes in 1 blocks are definitely lost in loss record 46
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000857: countAndSay (main.c:28)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 19,257 (240 direct, 19,017 indirect) bytes in 1 blocks are d
definitely lost in loss record 48 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000839: countAndSay (main.c:19)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 61,644 bytes in 406 blocks are definitely lost in loss record
49 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 80,493 bytes in 379 blocks are definitely lost in loss record
50 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 29,093,648 bytes in 39,299 blocks are definitely lost in loss
record 51 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== LEAK SUMMARY:
==1796== definitely lost: 29,260,015 bytes in 40,521 blocks
==1796== indirectly lost: 19,017 bytes in 29 blocks
==1796== possibly lost: 642 bytes in 4 blocks
==1796== still reachable: 200 bytes in 6 blocks
==1796== suppressed: 22,021 bytes in 152 blocks
==1796== Reachable blocks (those to which a pointer was found) are not
shown.
==1796== To see them, rerun with: --leak-check=full --show-leak-
kinds=all
==1796==
==1796== For counts of detected and suppressed errors, rerun with: -v
==1796== Use --track-origins=yes to see where uninitialised values come
from
==1796== ERROR SUMMARY: 124 errors from 15 contexts (suppressed: 11
from 11)
main.c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SEQUENCE_COUNT 30
#define BUFFER_MAX 4462
char* countAndSay(int n) {
int msc;
if (n > 0 && n <= 30) {
msc = MAX_SEQUENCE_COUNT;
} else {
fprintf(stderr, "Error: The range for this count and say method is 1...30\n");
exit(1);
}
//Holds the array of sequences
char **out_buffer = malloc(msc * sizeof(char*));
//Holds current sequence
char *out;
int size = n;
//Holds previous sequence
char *prev_chunk = NULL;
//memory for the counts and says
int *counts = malloc(BUFFER_MAX*sizeof(int));
char *says = malloc(BUFFER_MAX*sizeof(char));
//index into the buffer memory of sequences
int index = 0;
//solve iteratively
while (size > 0) {
//base condition
//size counts down to 0, filling chunks, populating the next chunk to be processed
//filled chunks are placed in the out buffer at the index which is counting
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '[=15=]';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
//from 0 to index - 1 get the chunk to be processed, use it to put together
//the count and say chunk for adding to the index slot
for (int s = 0; s < index; s++) {
if (s == 0) {
prev_chunk = out_buffer[0];
} else {
prev_chunk = out_buffer[index];
}
//count the length of the current chunk
int length = 0;
for (int e = 0; e <= BUFFER_MAX; e++) {
if (prev_chunk[e]) {
length += 1;
} else {
break;
}
}
//The count of says at each iteration
int count = 0;
//say is a char byte from the previous chunk memory
char say = prev_chunk[0];
//skip is used in the iteration process
int skip = 0;
//The idx into memory for the counts and says
int idx = 0;
//iteratively generate the count and say chunk for this index
for (int i = 0; i < length; i++) {
if (skip > 0) {
if (i < length - 1) {
say = prev_chunk[i + 1];
}
skip -= 1;
continue;
}
if (prev_chunk[i] == say) {
count += 1;
counts[idx] = count;
says[idx] = say;
//if at the end of the iteration add one
//as a terminator for the counts, says, pairs
if (i == length - 1) {
idx += 1;
break;
}
} else {
count = 0;
if (i == length - 1) {
//finish off
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
say = says[idx];
idx += 1;
} else {
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
char next_say = prev_chunk[i + 1];
say = prev_chunk[i];
//Takes care of itself with idx
if (next_say != prev_chunk[i]) {
count = 0;
continue;
}
int y = i;
while (next_say == say && y < length -1) {
count += 1;
//dont need to up the index because we are counting howmany there are
says[idx] = say;
counts[idx] = count;
//skip because this is the next loop
skip += 1;
//subtract 1 because we want this to be in the final index slot
//count because we added an index
y += 1;
next_say = prev_chunk[y + 1];
}
idx += 1;
count = 0;
}
}
}
//Could have just generated the sequence from above but felt like doing this manually at the time
//If I get around to it ill change
int chunk_offset = 0;
char *temp = NULL;
for (int u = 0; u < idx; u++) {
int c = counts[u];
//TODO: factor out or use sprintf, or maybe not, maybe this is just faster
char cc;
if (c >= 10) {
cc = 'A' + c - 10;
} else {
cc = '0' + c;
}
char say = says[u];
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '[=15=]';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '[=15=]';
}
out = realloc(out, chunk_offset + 3);
out = temp;
temp = NULL;
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
out = temp;
temp = NULL;
free(temp);
}
}
out_buffer[index] = out;
out = NULL;
free(out);
}
index += 1;
size -= 1;
}
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
}
int main(int argc, char **argv) {
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
}
我知道这不是最好的算法，但它确实有效。据我了解，可以使用 realloc 来避免
将 malloc 的内存堆积到循环内部的堆中，就像这样可行。我怀疑这样做会将内存移动到不容易找到和释放的地方。我的思路是否正确？简单的重新分配
char *e = NULL;
for (int i = 0; i < 10; i++) {
e = realloc(e, i + 1);
if (i == 9) {
e[i] = '[=16=]';
} else {
e[i] = 'e';
}
}
printf("%s\n", e);
free(e);
valgrind 的产量：
==4421== LEAK SUMMARY:
==4421== definitely lost: 0 bytes in 0 blocks
==4421== indirectly lost: 0 bytes in 0 blocks
==4421== possibly lost: 72 bytes in 3 blocks
==4421== still reachable: 200 bytes in 6 blocks
==4421== suppressed: 22,021 bytes in 152 blocks
我已经 运行 与 valgrind 一起尝试确定泄漏问题。我也看到过这样的解决方案，但没有成功："Pointer being freed was not allocated." error after malloc, realloc.
我认为我在这里遇到的主要问题是我第一次 malloc "out"。之后我每次在循环中重新分配它。 Valgrind 在 main.c:184 "out = realloc(out, chunk_offset + 2);" 行给出了最大的泄漏。似乎 realloc 只是决定将该内存放在堆中的某个位置，而我无法访问它。我知道地址可以从 realloc 更改，但我仍然无法获取它。我怎么才能在我的countandsay中绝对迷失到0。
你的问题是你正在释放你在循环结束时分配的指针，即使你为后代或其他东西保存了指针。
根据这段代码，我认为您想做几件事：
- 不要仅仅因为你已经完成了持有它的指针的变量就释放你没有完成的内存。
- 将其更改为 malloc 而不是 realloc，因为您显然希望每次通过循环都有一个单独的 space。
- 获取可帮助您进行缩进的编辑器，或学习配置用于帮助您进行缩进的编辑器。这听起来像是一种意见，但如果您的缩进有意义的话，我发现这种问题看起来更容易诊断。它也可能会帮助您获得帮助，因为很少有专家程序员愿意像那样处理不一致的缩进。我的印象是，我是少数几个看到类似内容并决定将其放入 vim，然后键入
=gg 以重新格式化一切以使其合理的人之一。 （注意：如果您不使用 vi、nvi 或 vim，请不要仅仅因为我会而使用它 - 所有这三个编辑器都有很大的学习曲线，而且大多数编程编辑器都可以做同样的事情的事情。）
并且只是为了强调最后一点：一旦我将其重新格式化为具有一致的缩进，问题就突然出现了。汤姆几乎明白了，但我认为他认为那是你的函数的结束，而不是循环的结束。
让我们从这个块开始：
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '[=10=]';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '[=10=]';
}
out = realloc(out, chunk_offset + 3);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
}
在 if 的两个部分中，您扩展了 out 的大小，但随后您立即用 temp 的值覆盖了 out，泄漏了内存out 指向。
由于 temp 包含您想要的值，因此您不再需要 out 中的内容，因此去掉 out 上的 realloc，取而代之的是 free 以前有什么。此外，不需要 free(temp)，因为它指向 NULL，并且您可以将 realloc 调用替换为 malloc，因为 temp 将始终为 NULL：
if (u == idx - 1) {
temp = malloc(chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '[=11=]';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '[=11=]';
}
} else {
temp = malloc(chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
}
free(out);
out = temp;
然后你在 for 循环的底部有这个：
for (int s = 0; s < index; s++) {
...
out_buffer[index] = out;
out = NULL;
free(out);
}
您在每次迭代时覆盖 out_buffer[index] 的内容，这会导致内存泄漏。您需要先 free 旧内容，最后还要删除不需要的 free(out) ，因为它在那一点上包含 NULL 。这也意味着您需要在进入循环之前将 out_buffer[index] 初始化为 NULL。
out_buffer[index] = NULL;
for (int s = 0; s < index; s++) {
...
free(out_buffer[index]);
out_buffer[index] = out;
out = NULL;
}
那么你这里有问题：
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '[=14=]';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
未能在下一次循环迭代之前将 out 设置为 NULL，这将导致 out_buffer[0] 被释放并随后从释放的内存中读取。所以在这里添加：
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '[=15=]';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
out = NULL;
continue;
}
然后最后：
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
你不想 free(prev_chunk); 因为它指向一个已经被释放的 out 的旧副本。您也没有释放 out_buffer 或它指向的任何字符串。当然，你不想释放你 return 的字符串，所以跳过那个：
char *rval = out_buffer[n - 1];
for (int i = 0; i < n - 1; i++) {
free(out_buffer[i]);
}
free(out_buffer);
free(counts);
free(says);
return rval;
最后，确保 free 一旦 main 完成此函数的结果：
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
free(cs);
现在您通过 valgrind 获得了干净的 运行，没有内存泄漏或无效 read/write/free 错误。
附带说明一下，此代码中存在很多低效之处。在外部 while 循环的每次迭代中，您都会生成从 1 到 n 当前值的整个列表。因此，在第一次迭代中计算 n=1，然后在下一次计算 n=1,2，然后在下一次计算 n=1,2,3，等等
这里只需要一个循环。这也意味着您不必重用 out_buffer 的当前值，而是可以只引用前一个值。我会将这些更改留作 reader.
的练习
如果我们看看 Look-and-Say 算法的工作原理，我们会发现每个字符（或相同字符的序列）都会在输出中生成一个字符对。因此，如果输入的长度为N个字符，则输出的长度最多为2N个字符。
让我们看一下在 Look-and-Say 序列中生成 next 字符串的函数：
#include <stdlib.h>
#include <string.h>
char *look_and_say(const char *src)
{
const size_t srclen = (src) ? strlen(src) : 0;
char *dst;
if (srclen < 1) {
/* Nothing to look or say. */
return NULL;
}
/* The result can be up to twice as long as the source,
plus the string-terminating nul char. */
dst = malloc(2*srclen + 1);
if (!dst) {
/* Not enough memory for the result. */
return NULL;
}
{
const char *const end = src + srclen;
char *pos = dst;
while (src < end) {
const char *const was = src;
/* Skip repeated source characters. */
do {
src++;
} while (src < end && *src == *was);
/* The longest allowed sequence is 9. */
if ((size_t)(src - was) > 9) {
free(dst);
return NULL;
}
*(pos++) = '0' + (size_t)(src - was);
*(pos++) = *was;
}
*pos = '[=10=]';
return dst;
}
}
上面不关心输入的字符串是什么；你可以提供任何东西。如果输入字符串为 NULL 或空，它将 return NULL。如果它不能分配内存（两倍于输入字符串的长度，加上一个字符作为字符串终止 nul '[=13=]' 字符），它 return 为 NULL。如果一个字符连续重复超过 9 次，函数 returns NULL.
Look-and-Say 序列是 OEIS A005150 在线整数序列百科全书，指出 R. G. Wilson v 在 2004 年表明只有数字 1, 2, 和 3 存在于序列中。因此，对于整数序列，可以打开代码测试一个数字是否重复（两次或三次）。
该序列中每一项的长度形成另一个整数序列，OEIS A005341。事实证明，i 项的长度类似于 1.56 × 1.304i（即 (size_t)(1.0 + 1.56*exp(0.26544*i)).序列中的第 30 项长度为 4462 个字符。
如果我们想要生成序列中的每个值，我们可以使用单个动态管理的缓冲区（保存正在生成的值），并保存每个结果的副本 :
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
char *sdup(const char *src, const size_t len)
{
char *s;
s = malloc(len + 1);
if (!s) {
fprintf(stderr, "sdup(): Not enough memory for a duplicate of %zu-character string.\n", len);
return NULL;
}
memcpy(s, src, len);
s[len] = '[=11=]';
return s;
}
/* Initial buffer size, at least 1. */
#ifndef INITIAL_BUFFER_SIZE
#define INITIAL_BUFFER_SIZE 1
#endif
char **look_and_say(const size_t count)
{
char **table;
char *src, *end;
char *dst, *pos;
size_t len, max = INITIAL_BUFFER_SIZE;
size_t i, k;
if (count < 1) {
fprintf(stderr, "look_and_say(): Count is less than 1.\n");
return NULL;
}
/* Allocate memory for the array of pointers. */
table = calloc(count + 2, sizeof *table);
if (!table) {
fprintf(stderr, "look_and_say(): Not enough memory for an array of %zu strings.\n", count);
return NULL;
}
/* First and last entries are NULLs; sentinels, if you will. */
table[0] = NULL;
table[count + 1] = NULL;
/* Allocate memory for the dynamic buffer. */
dst = malloc(max);
if (!dst) {
fprintf(stderr, "look_and_say(): Not enough memory for a %zu-character work buffer.\n", max);
free(table);
return NULL;
}
/* The sequence starts with "1". */
dst[0] = '1';
len = 1;
/* Save that. */
table[1] = sdup(dst, len);
/* Loop over the rest of the entries to be generated. */
for (i = 2; i <= count; i++) {
/* The source is the last item in the sequence. */
src = table[i - 1];
end = table[i - 1] + len;
/* Ensure we have enough room for the next value in the sequence. */
if (2*len > max) {
/* TODO: Better growth policy! */
max = 2*len;
pos = realloc(dst, max);
if (!pos) {
fprintf(stderr, "look_and_say(): Not enough memory to grow work buffer to %zu chars.\n", max);
free(dst);
for (k = 1; k < i; k++)
free(table[k]);
free(table);
return NULL;
}
dst = pos;
} else
pos = dst;
/* Source is [src, end[. pos is the next position in work buffer. */
while (src < end) {
const int nc = *(src++);
int nn = '1';
/* Skip if source is repeated twice or three times. */
if (*src == nc) {
src++;
nn++; /* 2 */
if (*src == nc) {
src++;
nn++; /* 3 */
}
}
*(pos++) = nn;
*(pos++) = nc;
}
/* Length of the generated value. */
len = (size_t)(pos - dst);
/* Save to table. */
table[i] = sdup(dst, len);
if (!table[i]) {
free(dst);
for (k = 1; k < i; k++)
free(table[i]);
free(table);
return NULL;
}
}
/* Dynamic buffer is no longer needed. */
free(dst);
return table;
}
#ifndef LIMIT
#define LIMIT 30
#endif
int main(void)
{
char **sequence;
size_t i;
sequence = look_and_say(LIMIT);
if (!sequence)
exit(EXIT_FAILURE);
for (i = 1; i <= LIMIT; i++)
printf("%zu. %s\n", i, sequence[i]);
for (i = 1; i <= LIMIT; i++)
free(sequence[i]);
free(sequence);
return EXIT_SUCCESS;
}
在这一点上，我们必须注意，我们已经有了一个 O(N) 算法来生成序列中的下一个值, were N 是前一个值的长度。获得比线性更好的性能需要更好的算法，但据我所知，没有比线性更好的简单解决方案。
我们当然可以在代码层面优化上面的代码；但是它的时间复杂度已经很不错了
如果我们想要"cheat"，我们可以观察到序列中前三十项的长度是1,2,2,4,6,6,8,10,14,20, 26、34、46、62、78、102、134、176、226、302、408、528、678、904、1182、1540、2012、2606、3410、4462。这意味着如果我们为指针和 19019 个字符（长度之和 + 字符串结尾字符的 30），我们只需要一次分配。如果我们为 NULL 保留第零指针，那么该分配将是 malloc(19019 + 31 * sizeof (char *)).
然而，沿着这条路继续前进，我们最终得到以下代码，或者非常相似的东西：
static const char term_1[] = "1";
static const char term_2[] = "11";
static const char term_3[] = "21";
static const char term_4[] = "1211";
static const char term_5[] = "111221";
/* term_6[] through term_30[] omitted */
static const char *sequence[31] = {
NULL,
term_1, term_2, term_3, term_4, term_5,
term_6, term_7, term_8, term_9, term_10,
term_11, term_12, term_13, term_14, term_15,
term_16, term_17, term_18, term_19, term_20,
term_21, term_22, term_23, term_24, term_25,
term_26, term_27, term_28, term_29, term_30
};
这会在生成的二进制文件中生成大约 19 KiB 的只读（不可变）数据。即使在许多微控制器上，这也不是问题，如果该序列对操作至关重要。
如果内存使用是个问题，可以简单地将每个单独的数字打包成两位，从而保持合理的访问时间，在这种情况下，数据仅使用大约 5 KiB 的内存。
这是我从 leetcode 解决方案中算出的问题。但是内存泄漏 https://leetcode.com/problems/count-and-say/
我的生成文件
build:
gcc main.c -Wall -g -o main; \
$(PWD)/main; \
我的构建命令
make
或使用 valgrind：
make
valgrind --leak-check=yes ./main
输出：（正确，经过测试）
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
来自 Valgrind
==1796== Memcheck, a memory error detector
==1796== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et
al.
==1796== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright
info
==1796== Command: ./main
==1796==
==1796== Invalid read of size 1
==1796== at 0x100000930: countAndSay (main.c:62)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x10000096B: countAndSay (main.c:73)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 1
==1796== at 0x1000009D7: countAndSay (main.c:89)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Address 0x100df6f80 is 0 bytes inside a block of size 2
free'd
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796== Block was alloc'd at
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000892: countAndSay (main.c:40)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Invalid read of size 16
==1796== at 0x100655A65: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796== Address 0x10545d410 is 1 bytes after a block of size 4,463
alloc'd
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== Conditional jump or move depends on uninitialised value(s)
==1796== at 0x100655A7D: _platform_memchr$VARIANT$Base (in
/usr/lib/system/libsystem_platform.dylib)
==1796== by 0x1002E99E9: __sfvwrite (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002F35FE: __vfprintf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100318058: __v2printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002EF741: vfprintf_l (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x1002ED7CA: printf (in
/usr/lib/system/libsystem_c.dylib)
==1796== by 0x100000EE0: main (main.c:210)
==1796==
count and say 30 = 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211
==1796==
==1796== HEAP SUMMARY:
==1796== in use at exit: 29,301,895 bytes in 40,712 blocks
==1796== total heap usage: 80,412 allocs, 39,700 frees, 58,326,719
bytes allocated
==1796==
==1796== 72 bytes in 3 blocks are possibly lost in loss record 25 of 51
==1796== at 0x1000ABD72: calloc (vg_replace_malloc.c:755)
==1796== by 0x10075A7C2: map_images_nolock (in
/usr/lib/libobjc.A.dylib)
==1796== by 0x10076D4E0: map_images (in /usr/lib/libobjc.A.dylib)
==1796== by 0x100007C64: dyld::notifyBatchPartial(dyld_image_states,
bool, char const* (*)(dyld_image_states, unsigned int, dyld_image_info
const*), bool, bool) (in /usr/lib/dyld)
==1796== by 0x100007E39: dyld::registerObjCNotifiers(void (*)
(unsigned int, char const* const*, mach_header const* const*), void (*)
(char const*, mach_header const*), void (*)(char const*, mach_header
const*)) (in /usr/lib/dyld)
==1796== by 0x10022571D: _dyld_objc_notify_register (in /
/usr/lib/system/libdyld.dylib)
==1796== by 0x10075A073: _objc_init (in /usr/lib/libobjc.A.dylib)
==1796== by 0x1001AFB34: _os_object_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1001AFB1B: libdispatch_init (in
/usr/lib/system/libdispatch.dylib)
==1796== by 0x1000BE9C2: libSystem_initializer (in
/usr/lib/libSystem.B.dylib)
==1796== by 0x100019AC5:
ImageLoaderMachO::doModInitFunctions(ImageLoader::LinkContext const&)
(in /usr/lib/dyld)
==1796== by 0x100019CF5:
ImageLoaderMachO::doInitialization(ImageLoader::LinkContext const&) (in
/usr/lib/dyld)
==1796==
==1796== 168 bytes in 56 blocks are definitely lost in loss record 28
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 570 bytes in 1 blocks are possibly lost in loss record 37 of
51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 1,512 bytes in 378 blocks are definitely lost in loss record
38 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 4,462 bytes in 1 blocks are definitely lost in loss record 45
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000867: countAndSay (main.c:29)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 17,848 bytes in 1 blocks are definitely lost in loss record 46
of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000857: countAndSay (main.c:28)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 19,257 (240 direct, 19,017 indirect) bytes in 1 blocks are d
definitely lost in loss record 48 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x100000839: countAndSay (main.c:19)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 61,644 bytes in 406 blocks are definitely lost in loss record
49 of 51
==1796== at 0x1000AB2C5: malloc (vg_replace_malloc.c:302)
==1796== by 0x1000AC30C: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000C67: countAndSay (main.c:157)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 80,493 bytes in 379 blocks are definitely lost in loss record
50 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000D10: countAndSay (main.c:172)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== 29,093,648 bytes in 39,299 blocks are definitely lost in loss
record 51 of 51
==1796== at 0x1000AC2DA: realloc (vg_replace_malloc.c:829)
==1796== by 0x100000DCD: countAndSay (main.c:184)
==1796== by 0x100000ECA: main (main.c:209)
==1796==
==1796== LEAK SUMMARY:
==1796== definitely lost: 29,260,015 bytes in 40,521 blocks
==1796== indirectly lost: 19,017 bytes in 29 blocks
==1796== possibly lost: 642 bytes in 4 blocks
==1796== still reachable: 200 bytes in 6 blocks
==1796== suppressed: 22,021 bytes in 152 blocks
==1796== Reachable blocks (those to which a pointer was found) are not
shown.
==1796== To see them, rerun with: --leak-check=full --show-leak-
kinds=all
==1796==
==1796== For counts of detected and suppressed errors, rerun with: -v
==1796== Use --track-origins=yes to see where uninitialised values come
from
==1796== ERROR SUMMARY: 124 errors from 15 contexts (suppressed: 11
from 11)
main.c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SEQUENCE_COUNT 30
#define BUFFER_MAX 4462
char* countAndSay(int n) {
int msc;
if (n > 0 && n <= 30) {
msc = MAX_SEQUENCE_COUNT;
} else {
fprintf(stderr, "Error: The range for this count and say method is 1...30\n");
exit(1);
}
//Holds the array of sequences
char **out_buffer = malloc(msc * sizeof(char*));
//Holds current sequence
char *out;
int size = n;
//Holds previous sequence
char *prev_chunk = NULL;
//memory for the counts and says
int *counts = malloc(BUFFER_MAX*sizeof(int));
char *says = malloc(BUFFER_MAX*sizeof(char));
//index into the buffer memory of sequences
int index = 0;
//solve iteratively
while (size > 0) {
//base condition
//size counts down to 0, filling chunks, populating the next chunk to be processed
//filled chunks are placed in the out buffer at the index which is counting
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '[=15=]';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
//from 0 to index - 1 get the chunk to be processed, use it to put together
//the count and say chunk for adding to the index slot
for (int s = 0; s < index; s++) {
if (s == 0) {
prev_chunk = out_buffer[0];
} else {
prev_chunk = out_buffer[index];
}
//count the length of the current chunk
int length = 0;
for (int e = 0; e <= BUFFER_MAX; e++) {
if (prev_chunk[e]) {
length += 1;
} else {
break;
}
}
//The count of says at each iteration
int count = 0;
//say is a char byte from the previous chunk memory
char say = prev_chunk[0];
//skip is used in the iteration process
int skip = 0;
//The idx into memory for the counts and says
int idx = 0;
//iteratively generate the count and say chunk for this index
for (int i = 0; i < length; i++) {
if (skip > 0) {
if (i < length - 1) {
say = prev_chunk[i + 1];
}
skip -= 1;
continue;
}
if (prev_chunk[i] == say) {
count += 1;
counts[idx] = count;
says[idx] = say;
//if at the end of the iteration add one
//as a terminator for the counts, says, pairs
if (i == length - 1) {
idx += 1;
break;
}
} else {
count = 0;
if (i == length - 1) {
//finish off
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
say = says[idx];
idx += 1;
} else {
idx += 1;
count += 1;
counts[idx] = count;
says[idx] = prev_chunk[i];
char next_say = prev_chunk[i + 1];
say = prev_chunk[i];
//Takes care of itself with idx
if (next_say != prev_chunk[i]) {
count = 0;
continue;
}
int y = i;
while (next_say == say && y < length -1) {
count += 1;
//dont need to up the index because we are counting howmany there are
says[idx] = say;
counts[idx] = count;
//skip because this is the next loop
skip += 1;
//subtract 1 because we want this to be in the final index slot
//count because we added an index
y += 1;
next_say = prev_chunk[y + 1];
}
idx += 1;
count = 0;
}
}
}
//Could have just generated the sequence from above but felt like doing this manually at the time
//If I get around to it ill change
int chunk_offset = 0;
char *temp = NULL;
for (int u = 0; u < idx; u++) {
int c = counts[u];
//TODO: factor out or use sprintf, or maybe not, maybe this is just faster
char cc;
if (c >= 10) {
cc = 'A' + c - 10;
} else {
cc = '0' + c;
}
char say = says[u];
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '[=15=]';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '[=15=]';
}
out = realloc(out, chunk_offset + 3);
out = temp;
temp = NULL;
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
out = temp;
temp = NULL;
free(temp);
}
}
out_buffer[index] = out;
out = NULL;
free(out);
}
index += 1;
size -= 1;
}
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
}
int main(int argc, char **argv) {
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
}
我知道这不是最好的算法，但它确实有效。据我了解，可以使用 realloc 来避免 将 malloc 的内存堆积到循环内部的堆中，就像这样可行。我怀疑这样做会将内存移动到不容易找到和释放的地方。我的思路是否正确？简单的重新分配
char *e = NULL;
for (int i = 0; i < 10; i++) {
e = realloc(e, i + 1);
if (i == 9) {
e[i] = '[=16=]';
} else {
e[i] = 'e';
}
}
printf("%s\n", e);
free(e);
valgrind 的产量：
==4421== LEAK SUMMARY:
==4421== definitely lost: 0 bytes in 0 blocks
==4421== indirectly lost: 0 bytes in 0 blocks
==4421== possibly lost: 72 bytes in 3 blocks
==4421== still reachable: 200 bytes in 6 blocks
==4421== suppressed: 22,021 bytes in 152 blocks
我已经 运行 与 valgrind 一起尝试确定泄漏问题。我也看到过这样的解决方案，但没有成功："Pointer being freed was not allocated." error after malloc, realloc.
我认为我在这里遇到的主要问题是我第一次 malloc "out"。之后我每次在循环中重新分配它。 Valgrind 在 main.c:184 "out = realloc(out, chunk_offset + 2);" 行给出了最大的泄漏。似乎 realloc 只是决定将该内存放在堆中的某个位置，而我无法访问它。我知道地址可以从 realloc 更改，但我仍然无法获取它。我怎么才能在我的countandsay中绝对迷失到0。
你的问题是你正在释放你在循环结束时分配的指针，即使你为后代或其他东西保存了指针。
根据这段代码，我认为您想做几件事：
- 不要仅仅因为你已经完成了持有它的指针的变量就释放你没有完成的内存。
- 将其更改为 malloc 而不是 realloc，因为您显然希望每次通过循环都有一个单独的 space。
- 获取可帮助您进行缩进的编辑器，或学习配置用于帮助您进行缩进的编辑器。这听起来像是一种意见，但如果您的缩进有意义的话，我发现这种问题看起来更容易诊断。它也可能会帮助您获得帮助，因为很少有专家程序员愿意像那样处理不一致的缩进。我的印象是，我是少数几个看到类似内容并决定将其放入 vim，然后键入
=gg以重新格式化一切以使其合理的人之一。 （注意：如果您不使用 vi、nvi 或 vim，请不要仅仅因为我会而使用它 - 所有这三个编辑器都有很大的学习曲线，而且大多数编程编辑器都可以做同样的事情的事情。）
并且只是为了强调最后一点：一旦我将其重新格式化为具有一致的缩进，问题就突然出现了。汤姆几乎明白了，但我认为他认为那是你的函数的结束，而不是循环的结束。
让我们从这个块开始：
if (u == idx - 1) {
temp = realloc(temp, chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '[=10=]';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '[=10=]';
}
out = realloc(out, chunk_offset + 3);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
} else {
temp = realloc(temp, chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
out = realloc(out, chunk_offset + 2);
// *** MEMORY LEAK ***
out = temp;
temp = NULL;
// NOT NEEDED
free(temp);
}
在 if 的两个部分中，您扩展了 out 的大小，但随后您立即用 temp 的值覆盖了 out，泄漏了内存out 指向。
由于 temp 包含您想要的值，因此您不再需要 out 中的内容，因此去掉 out 上的 realloc，取而代之的是 free 以前有什么。此外，不需要 free(temp)，因为它指向 NULL，并且您可以将 realloc 调用替换为 malloc，因为 temp 将始终为 NULL：
if (u == idx - 1) {
temp = malloc(chunk_offset + 3);
if (chunk_offset > 0) {
for (int y = 0; y < chunk_offset; y++) {
temp[y] = out[y];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
temp[chunk_offset + 2] = '[=11=]';
} else {
temp[0] = cc;
temp[1] = say;
temp[2] = '[=11=]';
}
} else {
temp = malloc(chunk_offset + 2);
for (int ii = 0; ii < chunk_offset; ii++) {
temp[ii] = out[ii];
}
temp[chunk_offset] = cc;
temp[chunk_offset + 1] = say;
chunk_offset += 2;
}
free(out);
out = temp;
然后你在 for 循环的底部有这个：
for (int s = 0; s < index; s++) {
...
out_buffer[index] = out;
out = NULL;
free(out);
}
您在每次迭代时覆盖 out_buffer[index] 的内容，这会导致内存泄漏。您需要先 free 旧内容，最后还要删除不需要的 free(out) ，因为它在那一点上包含 NULL 。这也意味着您需要在进入循环之前将 out_buffer[index] 初始化为 NULL。
out_buffer[index] = NULL;
for (int s = 0; s < index; s++) {
...
free(out_buffer[index]);
out_buffer[index] = out;
out = NULL;
}
那么你这里有问题：
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '[=14=]';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
continue;
}
未能在下一次循环迭代之前将 out 设置为 NULL，这将导致 out_buffer[0] 被释放并随后从释放的内存中读取。所以在这里添加：
if (index == 0) {
out = malloc(2 * sizeof(char));
out[0] = '1';
out[1] = '[=15=]';
prev_chunk = out;
size -= 1;
index += 1;
out_buffer[0] = out;
out = NULL;
continue;
}
然后最后：
free(prev_chunk);
prev_chunk = NULL;
free(counts);
counts = NULL;
free(says);
says = NULL;
return out_buffer[n - 1];
你不想 free(prev_chunk); 因为它指向一个已经被释放的 out 的旧副本。您也没有释放 out_buffer 或它指向的任何字符串。当然，你不想释放你 return 的字符串，所以跳过那个：
char *rval = out_buffer[n - 1];
for (int i = 0; i < n - 1; i++) {
free(out_buffer[i]);
}
free(out_buffer);
free(counts);
free(says);
return rval;
最后，确保 free 一旦 main 完成此函数的结果：
char *cs = countAndSay(30);
printf("count and say 30 = %s\n", cs);
free(cs);
现在您通过 valgrind 获得了干净的 运行，没有内存泄漏或无效 read/write/free 错误。
附带说明一下，此代码中存在很多低效之处。在外部 while 循环的每次迭代中，您都会生成从 1 到 n 当前值的整个列表。因此，在第一次迭代中计算 n=1，然后在下一次计算 n=1,2，然后在下一次计算 n=1,2,3，等等
这里只需要一个循环。这也意味着您不必重用 out_buffer 的当前值，而是可以只引用前一个值。我会将这些更改留作 reader.
如果我们看看 Look-and-Say 算法的工作原理，我们会发现每个字符（或相同字符的序列）都会在输出中生成一个字符对。因此，如果输入的长度为N个字符，则输出的长度最多为2N个字符。
让我们看一下在 Look-and-Say 序列中生成 next 字符串的函数：
#include <stdlib.h>
#include <string.h>
char *look_and_say(const char *src)
{
const size_t srclen = (src) ? strlen(src) : 0;
char *dst;
if (srclen < 1) {
/* Nothing to look or say. */
return NULL;
}
/* The result can be up to twice as long as the source,
plus the string-terminating nul char. */
dst = malloc(2*srclen + 1);
if (!dst) {
/* Not enough memory for the result. */
return NULL;
}
{
const char *const end = src + srclen;
char *pos = dst;
while (src < end) {
const char *const was = src;
/* Skip repeated source characters. */
do {
src++;
} while (src < end && *src == *was);
/* The longest allowed sequence is 9. */
if ((size_t)(src - was) > 9) {
free(dst);
return NULL;
}
*(pos++) = '0' + (size_t)(src - was);
*(pos++) = *was;
}
*pos = '[=10=]';
return dst;
}
}
上面不关心输入的字符串是什么；你可以提供任何东西。如果输入字符串为 NULL 或空，它将 return NULL。如果它不能分配内存（两倍于输入字符串的长度，加上一个字符作为字符串终止 nul '[=13=]' 字符），它 return 为 NULL。如果一个字符连续重复超过 9 次，函数 returns NULL.
Look-and-Say 序列是 OEIS A005150 在线整数序列百科全书，指出 R. G. Wilson v 在 2004 年表明只有数字 1, 2, 和 3 存在于序列中。因此，对于整数序列，可以打开代码测试一个数字是否重复（两次或三次）。
该序列中每一项的长度形成另一个整数序列，OEIS A005341。事实证明，i 项的长度类似于 1.56 × 1.304i（即 (size_t)(1.0 + 1.56*exp(0.26544*i)).序列中的第 30 项长度为 4462 个字符。
如果我们想要生成序列中的每个值，我们可以使用单个动态管理的缓冲区（保存正在生成的值），并保存每个结果的副本 :
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
char *sdup(const char *src, const size_t len)
{
char *s;
s = malloc(len + 1);
if (!s) {
fprintf(stderr, "sdup(): Not enough memory for a duplicate of %zu-character string.\n", len);
return NULL;
}
memcpy(s, src, len);
s[len] = '[=11=]';
return s;
}
/* Initial buffer size, at least 1. */
#ifndef INITIAL_BUFFER_SIZE
#define INITIAL_BUFFER_SIZE 1
#endif
char **look_and_say(const size_t count)
{
char **table;
char *src, *end;
char *dst, *pos;
size_t len, max = INITIAL_BUFFER_SIZE;
size_t i, k;
if (count < 1) {
fprintf(stderr, "look_and_say(): Count is less than 1.\n");
return NULL;
}
/* Allocate memory for the array of pointers. */
table = calloc(count + 2, sizeof *table);
if (!table) {
fprintf(stderr, "look_and_say(): Not enough memory for an array of %zu strings.\n", count);
return NULL;
}
/* First and last entries are NULLs; sentinels, if you will. */
table[0] = NULL;
table[count + 1] = NULL;
/* Allocate memory for the dynamic buffer. */
dst = malloc(max);
if (!dst) {
fprintf(stderr, "look_and_say(): Not enough memory for a %zu-character work buffer.\n", max);
free(table);
return NULL;
}
/* The sequence starts with "1". */
dst[0] = '1';
len = 1;
/* Save that. */
table[1] = sdup(dst, len);
/* Loop over the rest of the entries to be generated. */
for (i = 2; i <= count; i++) {
/* The source is the last item in the sequence. */
src = table[i - 1];
end = table[i - 1] + len;
/* Ensure we have enough room for the next value in the sequence. */
if (2*len > max) {
/* TODO: Better growth policy! */
max = 2*len;
pos = realloc(dst, max);
if (!pos) {
fprintf(stderr, "look_and_say(): Not enough memory to grow work buffer to %zu chars.\n", max);
free(dst);
for (k = 1; k < i; k++)
free(table[k]);
free(table);
return NULL;
}
dst = pos;
} else
pos = dst;
/* Source is [src, end[. pos is the next position in work buffer. */
while (src < end) {
const int nc = *(src++);
int nn = '1';
/* Skip if source is repeated twice or three times. */
if (*src == nc) {
src++;
nn++; /* 2 */
if (*src == nc) {
src++;
nn++; /* 3 */
}
}
*(pos++) = nn;
*(pos++) = nc;
}
/* Length of the generated value. */
len = (size_t)(pos - dst);
/* Save to table. */
table[i] = sdup(dst, len);
if (!table[i]) {
free(dst);
for (k = 1; k < i; k++)
free(table[i]);
free(table);
return NULL;
}
}
/* Dynamic buffer is no longer needed. */
free(dst);
return table;
}
#ifndef LIMIT
#define LIMIT 30
#endif
int main(void)
{
char **sequence;
size_t i;
sequence = look_and_say(LIMIT);
if (!sequence)
exit(EXIT_FAILURE);
for (i = 1; i <= LIMIT; i++)
printf("%zu. %s\n", i, sequence[i]);
for (i = 1; i <= LIMIT; i++)
free(sequence[i]);
free(sequence);
return EXIT_SUCCESS;
}
在这一点上，我们必须注意，我们已经有了一个 O(N) 算法来生成序列中的下一个值, were N 是前一个值的长度。获得比线性更好的性能需要更好的算法，但据我所知，没有比线性更好的简单解决方案。
我们当然可以在代码层面优化上面的代码；但是它的时间复杂度已经很不错了
如果我们想要"cheat"，我们可以观察到序列中前三十项的长度是1,2,2,4,6,6,8,10,14,20, 26、34、46、62、78、102、134、176、226、302、408、528、678、904、1182、1540、2012、2606、3410、4462。这意味着如果我们为指针和 19019 个字符（长度之和 + 字符串结尾字符的 30），我们只需要一次分配。如果我们为 NULL 保留第零指针，那么该分配将是 malloc(19019 + 31 * sizeof (char *)).
然而，沿着这条路继续前进，我们最终得到以下代码，或者非常相似的东西：
static const char term_1[] = "1";
static const char term_2[] = "11";
static const char term_3[] = "21";
static const char term_4[] = "1211";
static const char term_5[] = "111221";
/* term_6[] through term_30[] omitted */
static const char *sequence[31] = {
NULL,
term_1, term_2, term_3, term_4, term_5,
term_6, term_7, term_8, term_9, term_10,
term_11, term_12, term_13, term_14, term_15,
term_16, term_17, term_18, term_19, term_20,
term_21, term_22, term_23, term_24, term_25,
term_26, term_27, term_28, term_29, term_30
};
这会在生成的二进制文件中生成大约 19 KiB 的只读（不可变）数据。即使在许多微控制器上，这也不是问题，如果该序列对操作至关重要。
如果内存使用是个问题，可以简单地将每个单独的数字打包成两位，从而保持合理的访问时间，在这种情况下，数据仅使用大约 5 KiB 的内存。