Solved

2-d array

Posted on 1998-08-20
11
234 Views
Last Modified: 2010-04-15

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;
}

Please advise. Thanks in advance.







0
Comment
Question by:misumi
  • 5
  • 2
  • 2
  • +2
11 Comments
 
LVL 1

Accepted Solution

by:
meessen earned 50 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 programming problem, you look really in trouble.


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

by:misumi
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

by:marvinm
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

by:meessen
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;

which is more readable.

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

by:meessen
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;

which is more readable.

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
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 2

Expert Comment

by:warmcat
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

by:meessen
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

by:braveheart
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

by:meessen
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

by:warmcat
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

by:braveheart
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

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.

746 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now