C Programming Help

[Gamingphreek]

First off: THIS IS SCHOOLWORK. PLEASE DO NOT GIVE ME THE ANSWER- MERELY POINT ME IN THE RIGHT DIRECTION

Now that is out of the way - this is a painfully simply program in C:

#include <stdlib.h>

unsigned int reverseArray(int A[], unsigned int Lo, unsigned int Hi)
{
/*
This allocates enough space to fit the size of the array passed
into the function.
*/
int *temp = malloc (sizeof (int) *Hi);
int *index = temp;
// This is the number of swaps done in the function.
int numSwap=0;

// This loop switches the indices between Hi and Lo.
auto int i;
for(i=Hi; i>=Lo; i--)
{
// This is a pointer to the index of the temp array.
*index = A BRACKET I BRACKET;
// This increases the index and number of swaps.
index++;
numSwap++;
}

// Resets the index to the initial value.
index = index - numSwap;

// Fills the original array with the values that are now flipped.
for(i=Lo; i<=Hi; i++)
{
A BRACKET I BRACKET = *index;
index++;
}

// This returns the number of swaps done by the function.
return numSwap;
}

We submit this to an online grader which then spits out the result and docks point. The grader has a main function which it uses as a "test harness" where it tests a variety of conditions. I am not able to see the tests that it is going through.

Apparently my program is failing and the online grade is creating a stack dump. I cannot, for the life of me, find a test which causes my program to crash.

The Lo and Hi have to be within bounds of the array. The Lo and Hi have to be a Low Point and a High Point. Nothing I have been able to do in my testing has been able to produce incorrect results.

All my Professor said was that I had boundary issues. It all seems to work fine for me. Can anyone point me in the right direction here - because I can't figure out why such a stupidly simple program is causing me more than 5 minutes of work.

(I suspect it is a problem with my Dynamic Memory Management malloc() function if it is indeed boundary issues)

-Kevin

 

[nickbits]

Is Hi inclusive or exclusive? Your code seems to go both ways.

 

[Gamingphreek]

Both are inclusive.

An array of {1,2,3,4,5}
Lo = 0
Hi = 2
Should swap and return {3,2,1,4,5}

-Kevin

 

[Markbnj]

Yep, looks to me like Hi is inclusive (it's a count of elements in A[]).

An array of {1,2,3,4,5}
Lo = 0
Hi = 2
Should swap and return {3,2,1,4,5}

Ok, but that means that the highest value for Hi is 4 in that case, correct? How many elements are you allocating for the temporary array? How are you addressing those elements in your loop?

 

[Gamingphreek]

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

unsigned int reverseArray(int A[], unsigned int Lo, unsigned int Hi)
{
/*
This allocates enough space to fit the size of the array passed
into the function.
*/
int *theArray = malloc (sizeof(A));
printf("%d\n", sizeof(*A));
int i;
// This is the number of swaps done in the function.
int numSwap=0;

// This loop switches the indices between Hi and Lo.
for(i=(int)Hi; i>=(int)Lo; i--)
{
// This is a pointer to the index of the temp array.
theArray[numSwap] = A BRACKET i BRACKET;
// This increases the index and number of swaps.
numSwap++;

}

// Fills the original array with the values that are now flipped.
numSwap = 0;

for(i=Lo; i<=Hi; i++)
{
A BRACKET I BRACKET = theArray[numSwap];
numSwap++;
}

for(i=0; i<10; i++)
printf("%d\n", A BRACKET i BRACKET);

free(theArray);

// This returns the number of swaps done by the function.
return numSwap;
}

This is my updated code.

My problem was that the unsigned int would not go below 0. So in the for statement it would just sit at 0 and run over and over. So I merely casted it as an int.

My problem now is the malloc. I won't know the size of the array in advance that my professor is passing in. sizeof() obviously returns 8 (Since I am running a 64bit machine) because it is a pointer to the array.

Is there any way that I can research to grab the correct value for the size of the array that is being passed into my function?

Thanks,
-Kevin

 

[degibson]

Try it without calling malloc()

 

[Ken g6]

Is it possible your professor wants you to write the code so that it reverses a section without using any extra memory? It is possible to do that. The simple way uses one extra variable; it is also possible to do without any extra memory at all, but probably not worth it.

 

[Gamingphreek]

Originally posted by: Ken g6
Is it possible your professor wants you to write the code so that it reverses a section without using any extra memory? It is possible to do that. The simple way uses one extra variable; it is also possible to do without any extra memory at all, but probably not worth it.

It is possible I suppose. He didn't specify. The problem is if he sends it a 16 or 32 index array it most definitely will not fit in the stack.

How would I do this without using extra memory? I thought malloc and then using free afterwards is essentially no memory.

-Kevin

 

[Fallen Kell]

Using malloc allocates memory, which means you use memory. Simply free'ing it at the end means that you are not creating a memory leak, but it doesn't mean that you are not using memory.

What the other posters are saying is not to use malloc at all so that you do not need to worry about the size of the array. To swap the values of the array, all you should ever need is a single variable that is the size of a member of the array. It is easier if you have 2 variables, but 2 are not needed. In fact it is even possible to do it without any extra variables, but that is needlessly complex especially for something like this.

In other words, want to do something like


i = 0
while ( i < sizeof(array)/2) {
tmp = array[sizeof(array)-i]
array[sizeof(array)-i] = array[ i]
array[ i] = tmp
}

Please note the above is just off the top of my head... you may need to take in consideration what happens if the array's size is an even number or odd number... I also write mostly perl and java anymore, but you should get the idea....

 

[Cerebus451]

Originally posted by: Gamingphreek

Originally posted by: Ken g6
Is it possible your professor wants you to write the code so that it reverses a section without using any extra memory? It is possible to do that. The simple way uses one extra variable; it is also possible to do without any extra memory at all, but probably not worth it.

It is possible I suppose. He didn't specify. The problem is if he sends it a 16 or 32 index array it most definitely will not fit in the stack.

How would I do this without using extra memory? I thought malloc and then using free afterwards is essentially no memory.

-Kevin

Two things I would point out:

First, in your original code, the source of the seg fault is that you are using Hi as a basis for your memory allocation, but Hi is a 0-based index.

Second, to do this without allocating memory, you can perform the swap in place. First, think of how you would swap the value at index Lo with the value at index Hi. Once you have that, you can swap the value at index Lo + 1 with the value at index Hi - 1, and so on and so forth.

 

[Markbnj]

First, in your original code, the source of the seg fault is that you are using Hi as a basis for your memory allocation, but Hi is a 0-based index.

Haha, thing is, he asked us not to tell him.

 

[Gamingphreek]

Originally posted by: Markbnj

First, in your original code, the source of the seg fault is that you are using Hi as a basis for your memory allocation, but Hi is a 0-based index.

Haha, thing is, he asked us not to tell him.

No worries - I think he saw my post about the fact that I was using an unsigned int and getting stuck. I had already figure it out so no worries.

As for the size, after sleeping I had one of those "DUH" moments. I don't need to fit the entire array in the temp array. Just the amount to be swapped! So:
malloc(Hi * sizeof(int) + 1)
That allocates sufficient space for any temp array that I might need.

I had thought of using 1 array and swapping from within, but as someone earlier said it was needlessly complex.

Here is my final code (When is the code feature going to start working - its aggravating editing my code so it doesn't parse it as HTML):

#include <stdlib.h>

unsigned int reverseArray(int A[], unsigned int Lo, unsigned int Hi)
{
/*
This allocates enough space to fit the bounded size of the array passed
into the function.
*/
int *theArray = malloc(Hi * sizeof(int) + 1);
int i;
// This is the number of swaps done in the function.
int numSwap=0;


// This loop switches the indices between Hi and Lo and stores in a temp array.
for(i=(int)Hi; i>=(int)Lo; i--)
{
// This is a pointer to the index of the temp array.
theArray[numSwap] = A BRACKET i BRACKET;
// This increases the index and number of swaps.
numSwap++;
}

// Resets numSwap
numSwap = 0;

// Places the swapped elements back into the original array.
for(i=Lo; i<=Hi; i++)
{
A BRACKET i BRACKET = theArray[numSwap];
numSwap++;
}

// Calculates the number of swaps done.
numSwap/=2;

// This frees the space allocated for the array.
free(theArray);

// This returns the number of swaps done by the function.
return numSwap;
}

-Kevin

(Oh and that was my Final submission - I am out of submissions now lol)

 

[Ken g6]

Would you like to be given the answer now? Now that you're done, I can also point you to how to swap with no extra memory at all. Just to blow your mind.

 

[Gamingphreek]

Originally posted by: Ken g6
Would you like to be given the answer now? Now that you're done, I can also point you to how to swap with no extra memory at all. Just to blow your mind.

Oh that is something I hadn't thought about and probably never would have come up with. Pretty cool implementation! I'll now have it for future reference

Thanks!

-Kevin

 

[blahblah99]

Originally posted by: Gamingphreek

Originally posted by: Ken g6
Is it possible your professor wants you to write the code so that it reverses a section without using any extra memory? It is possible to do that. The simple way uses one extra variable; it is also possible to do without any extra memory at all, but probably not worth it.

It is possible I suppose. He didn't specify. The problem is if he sends it a 16 or 32 index array it most definitely will not fit in the stack.

How would I do this without using extra memory? I thought malloc and then using free afterwards is essentially no memory.

-Kevin

Pointers are your friend.

 

[degibson]

unsigned int temp;
while( Lo < Hi ) {
temp = A[Lo];
A[Lo] = A[Hi];
A[Hi] = temp;
Lo++;
Hi--;
}

As pointed out before, you could also use XOR instead of the temp variable. There is not a good reason to do so, however.

 

[Cerebus451]

Originally posted by: Gamingphreek

(Oh and that was my Final submission - I am out of submissions now lol)

Bummer ... your malloc is still off a little (the +1 is in the wrong place).

 

[degibson]

Originally posted by: Cerebus451

Originally posted by: Gamingphreek

(Oh and that was my Final submission - I am out of submissions now lol)

Bummer ... your malloc is still off a little (the +1 is in the wrong place).

The malloc is functionally correct, but a little wasteful. Allocating Hi*sizeof(int)+1 bytes is more than you're going to need -- you will only need (Hi-Lo)*sizeof(int) bytes, assuming you are going to use malloc() at all.

 

[Fallen Kell]

The malloc is simply adding needless complexity and possible areas for the program to cause problems... For instance what happens if you kill the application from running during execution? With a malloc, unless you are trapping the kill signal in the program and handle the kill yourself (by cleaning up), you are possibly creating a memory leak which will remain until the computer system is rebooted... This is yet another reason why you are to avoid doing these things unless you have to.

There are a ton of rules that you should follow when dealing with allocating memory for writing clean well behaving code. A few are linked below:

http://www.codeproject.com/KB/...memory_allocation.aspx

 

[degibson]

Originally posted by: Fallen Kell
The malloc is simply adding needless complexity and possible areas for the program to cause problems... For instance what happens if you kill the application from running during execution? With a malloc, unless you are trapping the kill signal in the program and handle the kill yourself (by cleaning up), you are possibly creating a memory leak which will remain until the computer system is rebooted... This is yet another reason why you are to avoid doing these things unless you have to.

There are a ton of rules that you should follow when dealing with allocating memory for writing clean well behaving code. A few are linked below:

http://www.codeproject.com/KB/...memory_allocation.aspx

All process memory, with the exception of System V segments, is automatically cleaned up when a process's life ends. Adding complexity yes, system-wide memory leak, no.