x
Solved

# 2-d array

Posted on 1998-08-20
Medium Priority
244 Views

Is there any way in which I can delete an element from an array without implementing linked-list? In my program, I need to find the minimum value from the array and delete the element with minimum value. Then I repeat the step of searching for minimum value from the remaining elements and delete the element with minimum value.

If there is no way of avoiding the implementation of linked-list, please send any sample codes, information and URLs related to linked-list implementation.

I tried to use dynamic allocation to declare a 2-dimensional array but there was an error during compilation. Message was "Cannot convert void* to double*".

typedef  double **matrix;
typedef  double *row;
typedef  double elem;

matrix get_space(int M, int N)
{  int i;
elem  *p;
matrix a;
p = malloc(M*N*sizeof(elem));     //get space for all elements
a = malloc(M*sizeof(row));
--a;                                                      //offset pointer
for (i=1;i<=M;i++)
a[i]=p+((i-1)*N)-1;
return a;
}

0
Question by:misumi
• 5
• 2
• 2
• +2

LVL 1

Accepted Solution

meessen earned 100 total points
ID: 1252184
If you want to remove the element from the array as if you are removing an element from a list, then the most efficient solution is a linked list. This is if you want to maintain the order of the elements.

In your problem where you need to remove the smallest value, you could replace the value by the last element of the list and reduce the list length by one. This would change the order of values but would be much simpler to implement. You must then add a variable holding the number of values left in the array to examine. This is as fast as a linked list remove operation.

Thus in your case both solutions are equivalent.

Though if you need to implement this in a 2D array, playing with linked list becomes really tricky. The second solution is then much simpler to implement.

ABout your void* error message you simply need to put a cast in front of the malloc operation. malloc returns a void* and you want to store the value into a double *. This is just a type checking problem.

0

Author Comment

ID: 1252185
meessen,

I did cast the malloc before posting my question but the same error message appeared for both cases.
0

LVL 1

Expert Comment

ID: 1252186
Your code above compiled fine for me as long as I included malloc.h, and created a main().
You can dynamically create an array, and then use memmove() to delete an element.
0

LVL 1

Expert Comment

ID: 1252187
Then I don't see. Your code looks correct to me.

You may change the following code
--a;                                                      //offset pointer
for (i=1;i<=M;i++)
a[i]=p+((i-1)*N)-1;
into

for( i = 0; i < M; ;i++ )
a[i] = p+i*N;

As I said, you don't need to preserve order in your arrays. The memmove is useless.
In both case if you better keep the number of values left to examine in order to avoid searching in places previously removed.

To make your code cleaner, remove the last value from the array before starting to search.
Use this value as first guess. Now search in the array, if you find a smaller value, swap with your current guess. When you reached the end of the list, the value you hold is the smallest value.

Suppose L is the list length and A is the array, S is the smallest value.

S = A[L--];  /* init S and shorten the array */
for( i = 0; i < L; i++ ){
if( A[i] < S ) {
double t = A[i];
A[i] = S;
S = t;
}
}

return S;

0

LVL 1

Expert Comment

ID: 1252188
Then I don't see. Your code looks correct to me.

You may change the following code
--a;                                                      //offset pointer
for (i=1;i<=M;i++)
a[i]=p+((i-1)*N)-1;
into

for( i = 0; i < M; ;i++ )
a[i] = p+i*N;

As I said, you don't need to preserve order in your arrays. The memmove is useless.
In both case if you better keep the number of values left to examine in order to avoid searching in places previously removed.

To make your code cleaner, remove the last value from the array before starting to search.
Use this value as first guess. Now search in the array, if you find a smaller value, swap with your current guess. When you reached the end of the list, the value you hold is the smallest value.

Suppose L is the list length and A is the array, S is the smallest value.

S = A[L--];  /* init S and shorten the array */
for( i = 0; i < L; i++ ){
if( A[i] < S ) {
double t = A[i];
A[i] = S;
S = t;
}
}

return S;

0

LVL 2

Expert Comment

ID: 1252189
Depending on your job, you could either

1) trash the minimum entry after finding it and noting its value/position by overwriting its entry with MAXINT, or,

2) maintain a BYTE array of the same length as your main array.  Initially zero this BYTE array, and set the corresponding element to 1 each time you find a minimum.  Remove any elements with a 1 in the BYTE array from consideration as being the minimum.

Regards,

-Andy
0

LVL 1

Expert Comment

ID: 1252190
Both are inefficient because you will test these MAXINT values or byte flags when you know they are not interesting.
Shrinking the array is the best you can do if one can afford modifying it's content.

0

LVL 3

Expert Comment

ID: 1252191
Hey meessen, warmcat's suggestion is perfectly valid and may be the most efficient in some situations. Horses for courses.
0

LVL 1

Expert Comment

ID: 1252192
I didn't say it was not valid. I said it was ineffcient.

Solution 1 is destroying the array content by replacing each value by a MAXINT value.
This is worse than my solution because it is less efficient. It will work though. I would say it is valide but not good.

Solution 2 is leaves the array content unchanged but is still not very efficient.
To make it more effcient, instead of building an array of flags, build an array of indices.
In the first pass through the value array you build this secondary indices array and extract the smallest value. In the subsequent pass you use the indice array to scan your list and remove the indices of the smalles value found.

The number of indices will shrink and thus the search space too.
I would use this strategy if the valules would be big blocs. We then only manipulate references of big blocs instead of the blocs themselves.

Finaly a latest solution not expressed yet is to build a heap with the smalles value on top.
The first entry of the list would always be the smallest. At each step finding the next smallest value cost only log N operations which is even faster then N operation for a sequantial scan.

This is if performance is really a critical question.
Apparently the author of the question doesn't find it worth to co;;ent or validate the answer.

0

LVL 2

Expert Comment

ID: 1252193
Thanks for leaping to my defense, mon Brave; I was offering some quick retrofits to misumi.  But to be honest I was educated by meessen's response, and after I had given some thought to it I had to agree with it.  You can cheaply shrink the array by swapping the last entry with the just-discovered minimum entry slot and reducing the number of entries to scan by 1.  And the benefit of shrinking the array accumulates throughout all the subsequent scans: it's a neat technique.

But Brave's point is true too: all these optimizations are sensitive to one or more aspect of the exact job being done, so it is a case of choose the best method that fits the job best (and is likely to cause you least implementation bugs :) )
0

LVL 3

Expert Comment

ID: 1252194
Obviously meessen's approach is the ideal one but sometimes a quick and simple but inefficient retrofit is more cost effective than reengineering a solution.
0

## Featured Post

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.