C: Array not allocating more memory correctly

Question

I'm fairly new to C and I'm working on a project. Given an integer array, I want to move all the zeros in it to the left of the array with the rest of the elements in any order to the right of all the zeros. The basic idea of my algorithm is to count the number of zeros in the array, create a new array with the number of zeros in it from the old array, and then "append" the rest of the non-zero integers onto this array. And then of course I print finished product.

int main(int argc, const char * argv[]) {
    int a[10] = {3, 0, 1, 4, 0, 0, 7, 20, 1, 5};
    int n = 10, count = 0;

    // counts the number of 0's in the original array
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == 0)
        {
            ++count;
        }
    }

    // creates a new array and makes each element 0
    int *array = NULL;
    for (int j = 0; j < count; ++j)
    {
        array = realloc(array, (j + 1) * sizeof(int));
        array[j] = 0;
    }

    // adds the nonzero elements of the array to the new array
    for (int l = count; l < n; ++l)
    {
        array = realloc(array, l * sizeof(int)); // getting an error here
        if (a[l] != 0)
        {
            array[l+count] = a[l];
        }
    }

    // prints the array out in a nice format
    printf("%s", "{");
    for (int k = 0; k < n-1; ++k)
    {
        printf("%d%s", array[k], ",");
    }

    printf("%d", array[n-1]);
    printf("%s", "}\n");


    free(array);
    return 0;
}

I'm getting a "Thread 1: EXC_BAD_ACCESS (code=1, address=0x40)" error when I run this code. I think it's got to do something with invalid pointers to the new array, but I'm not sure how to fix it.

How exactly do you think it makes sense to call realloc on the very same variable, over and over from a loop? — Lundin
– Lundin, Commented Feb 10, 2016 at 14:13
You code like that and you don't know that int *array is a pointer and not an Array ? — Michi
– Michi, Commented Feb 10, 2016 at 14:14
" create a new array with the number of zeros in it from the old array, and then "append" the rest of the non-zero integers onto this array." You realize this is pretty much the very same thing as sorting the original array? Also do you realize that the new array will always have the same size as the original array? So dynamic allocation is not need in the first place. — Lundin
– Lundin, Commented Feb 10, 2016 at 14:44

Erich Kitzmueller · Accepted Answer · 2016-02-10 14:20:07Z

7

array[l+count] = a[l];

This accesses the memory block that array points at beyond its allocated size. You have to do it differently, using a second index:

// adds the nonzero elements of the array to the new array
int l = count;

for (int j=0; j < n; ++j)
{
    if (a[j] != 0)
    {
        array = realloc(array, (l+1) * sizeof(int));
        array[l] = a[j];
        ++l;
    }
}

edited Feb 10, 2016 at 14:20

answered Feb 10, 2016 at 14:14

Erich Kitzmueller

37.1k5 gold badges85 silver badges104 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Michi Over a year ago

This accesses array beyond its size int *array is a pointer not an Array .

Erich Kitzmueller Over a year ago

@Michi Technically you are correct. It accesses the memory region pointed to by array beyond the size it has been given by realloc

dbush Over a year ago

There's still not enough memory being allocated. You need space for one more: realloc(array, (l + 1) * sizeof(int));

Lundin Over a year ago

How does this code make any sense though? This still has the same problem as the original code, namely muddled purpose and work flow. The OP needs to do Understand problem -> Come up with a solution -> Write the code rather than Write the code-> Understand the solution -> Come up with a problem. Assisting him in writing the code for the latter work flow is not to help him.

Erich Kitzmueller Over a year ago

@Lundin: I aggree that the problem could be handled differently and the realloc in a loop is not necessary at all in this use case. Anyway, since there are legit cases where one has to use realloc, I didn't want to give an answer that simply rewrites the solution so it comes without realloc, thus possibly leaving the impression that realloc doesn't work correctly (as the title suggests)

Eric · Accepted Answer · 2016-02-10 14:36:11Z

1

About your algorithm:

I think u don't need to create a new array, just use a int tmp as swap area, and a int foundZeroCount as index, u swap 2 numbers at a time.

About memory allocation:

If u want to allocate memory for a fixed size array, just use malloc() to allocate array once, later when u need to extend the array, just call realloc() once.

About memory reset:

Just use memset(), and don't need a loop.

Suggestion - about c programming

Try improve your c basic, especially about array / pointer / memory, and try to know more functions from glibc.

Books like <The c programming language 2nd>, GNU c library document, and <The linux programming interface> would be useful, I guess.

edited Feb 10, 2016 at 14:36

answered Feb 10, 2016 at 14:16

Eric

25.8k26 gold badges168 silver badges232 bronze badges

6 Comments

Michi Over a year ago

You don't allocate memory for a fixed size array ..you create a block of memory and use a pointer to point there. How does/can an Array point there?

Eric Over a year ago

@Michi Isn't that what I said?

Michi Over a year ago

I'm sorry i can't help you here if you don't understand my Comment.

Eric Over a year ago

@Michi I think that's ok, all c programmers see what I mean.

unwind Over a year ago

About spelling: it's "you", not "u". :)

|

MarengoHue · Accepted Answer · 2016-02-10 14:40:35Z

The problem is with array[l+count] = a[l]; right when you are done allocating your 'zero-array' it's size is 3 and then you try to access (l + count)'th position which is 6.

And even if you have fixed those issues with memory it still wouldn't work because a[l] and further may still be zeros. (Your initial array is doesn't have zeroes in the beggining, remember?)

And there is a couple of suggestions: use calloc() to build your initial array of zeros because as man states:

The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. The memory is set to zero

First allocate then set because operations with memory are quite taxing for performance. It would be better for you to first allocate some memory and work with it instead of reallocating it each step. It would be much easier to keep track of as well.

John Bollinger · Accepted Answer · 2016-02-10 14:44:13Z

Other answers address your immediate issue, that

            array[l+count] = a[l];

attempts to access outside the bounds of the allocated space to which array points. I'll focus instead on your approach to the problem, which is flawed.

Dynamic memory allocation is comparatively expensive. You do not want to do any more than necessary, and it is particularly poor form to reallocate many times to increase by small increments each time, as you do.

Since you know at compile time how many elements you will need, dynamic allocation is altogether unnecessary here. You could instead do this:

int a[10] = {3, 0, 1, 4, 0, 0, 7, 20, 1, 5};
int array[10] = { 0 };

(Note also here that when an array initializer is provided, any array elements it does not explicitly initialize are initialized to 0.)

Even if you did not know at compile time how many elements you would need, it would be far better to perform the whole allocation in one chunk. Moreover, if you did that via calloc() then you would get automatic initialization of the allocated space to all-zeroes.

Umamahesh P · Accepted Answer · 2016-02-10 14:13:41Z

0

The count is known before defining the array. You can allocate memory using malloc as shown below.

array = malloc( count * sizeof(int)).

The error indicates you are trying to access address 0x40. This indicates one of the pointer has become NULL and you are trying to dereference ptr+0x40.

answered Feb 10, 2016 at 14:13

Umamahesh P

1,24410 silver badges14 bronze badges

4 Comments

Jabberwocky Over a year ago

True, but that's not related to the problem.

Michi Over a year ago

The count is known before defining the array which Array.... this =>>> int *array ?

Umamahesh P Over a year ago

I agree. To answer your Q, in this specific example the array a is predefined and there is loop to count. so the 2nd array is allocated using that count. When you see an address at a very lower range like 40, 30, 20... then that indicates a ptr has become NULL.

Umamahesh P Over a year ago

Why address 0x40 is printed in the error? That indicates array is NULL and count is 10. ptr+10 moves the pointer to 40 bytes for integer. so the address is 0x40.

Lundin · Accepted Answer · 2016-02-10 15:17:04Z

Before you start to hack away, take your time to consider the actual problem, which you have described as:

count the number of zeros in the array, create a new array with the number of zeros in it from the old array, and then "append" the rest of the non-zero integers onto this array.

Your comments say what the code should do, yet the code does something entirely different. Your algorithm to solve the problem is wrong - this, and nothing else, is the cause of the bugs.

To begin with, if the new array should contain all zeroes of the old array plus all non-zeroes, then common sense says that the new array will always have the same size as the old array. You don't even need to use dynamic memory allocation.

The code you have creates a new array and discards the old one, in the same memory location, over and over. This doesn't make any sense. On top of that, it is very ineffective to call realloc repeatedly in a loop.

You should do something like this instead:

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

int main(int argc, const char * argv[]) {
    int a[10] = {3, 0, 1, 4, 0, 0, 7, 20, 1, 5};
    const int n = 10; 

    // counts the number of 0's in the original array
    int zeroes = 0;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == 0)
        {
            ++zeroes;
        }
    }

    // creates a new array and makes each element 0
    // there's actually no need to allocate this dynamically at all...
    int *array = calloc(1, sizeof(int[n]) ); 
    assert(array != NULL);

    // skip zeroes, ie "move the zeroes from the original array"
    int* not_zeroes = array + zeroes; // point at first item to contain "not zeroes"

    // adds the non-zero elements of the original array to the new array
    for (int i = 0; i < n; ++i)
    {
      if(a[i] != 0)
      {
        *not_zeroes = a[i]; 
        not_zeroes++;
      }
    }

    // prints the array out in a nice format
    printf("%s", "{");
    for (int i = 0; i < n; ++i)
    {
        printf("%d,", array[i]);
    }
    printf("}\n");


    free(array);
    return 0;
}

Collectives™ on Stack Overflow

C: Array not allocating more memory correctly

6 Answers 6

5 Comments

About your algorithm:

About memory allocation:

About memory reset:

Suggestion - about c programming

6 Comments

Comments

Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

5 Comments

About your algorithm:

About memory allocation:

About memory reset:

Suggestion - about c programming

6 Comments

Comments

Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related