burleigh@cica.cica.indiana.edu (Frank Burleigh) (10/21/89)
Suppose you have:
typedef struct struct_name {...} struct_name;
struct_name list[MAXSIZE], *s_start, *s_one, *s_two;
main()
{
/*load the array of struct here*/
s_start = list;
/*other business*/
qsort( s_start, s_members, sizeof( struct_name ), ncmp );
}
int ncmp( struct_name * s_one, struct_name * s_two )
{
return strcmp( s_one->elem, s_two->elem );
}
This arrangement works well (less than 1000 members), but it may
be a poor design. If we display the structure members, have to
move forward and backward among them interactively, *and may re-
move members*, then there are two nagging problems.
1) qsort won't know that you'd like to discard members tagged
as deleted (ncmp could always make such members greater than
the comparison member).
2) Going forward (backward) by, say, 20 members isn't as easy
some pointer arithmetic, as you could land on (a) deleted
member(s). You'd have to walk forward (backward) until 20
valid members had been counted. That seems like a lot of over-
head in an interactive environment.
Adding a field to the structure pointing to the next valid member
doesn't seem to obviate the need to deal with these two problems.
Another approach is to instead maintain an array of pointers to
struct_name. Assuming the members are sorted, then with each
deletion you could move forward all the following elements of the
array of pointers, filling in the gap created by the deletion;
you'd also decrement a variable counting the number of valid
members. To move forward (backware) by 20 members only requires
bumping the index into the array of pointers by that much.
First, the concrete question:
Can the standard qsort accept not the array of structures, but
the array of pointers to structure members? If yes, how then
can the declaration of ncmp (the compare function) be changed
to accept two elements ([i], [j]) from the array of pointers,
since the call (and i, j) is buried in the library? If no,
then I'll have to make my own qsort -- less desirable, since it
makes more sense to take advantage of the library authors'
presumed expertise at writing fast sort routines.
Second, a more global question:
If there are fewer than 1000 members in the struct, am I mis-
taken to believe there would be less overhead in closing the
gap in the array of pointers with each deletion, then there
would be in counting off valid members with *each movement* in
the array of struct, especially considering the need to
occasionally resort? Alternatively, are there approaches to
managing a list on screen than I've not thought of and that
have greater merit than either of the ones above?
Unless this seems of general interest, please e-mail. Thank you
much.
--
Frank Burleigh burleigh@cica.cica.indiana.edu
USENET: ...rutgers!iuvax!cica!burleigh BITNET: BURLEIGH@IUBACS.BITNET
Department of Sociology, Indiana University, Bloomington, Indiana 47405gwyn@smoke.BRL.MIL (Doug Gwyn) (10/21/89)
In article <169@cica.cica.indiana.edu> burleigh@cica.cica.indiana.edu (Frank Burleigh) writes: > Can the standard qsort accept not the array of structures, but > the array of pointers to structure members? qsort() doesn't know what the array it is sorting consists of; it leaves that up to the comparison function. Thus, a standard trick is to have qsort() sort an array of pointers to records rather than an array of records. The rest is merely a matter of getting the type declarations right; this amounts to adding an extra * to the parameters in the comparison function. Note that the comparison function is fed "generic" pointers (void* or char*), and you ought to cast them into record_type**s before using them in the comparison function.
cpcahil@virtech.UUCP (Conor P. Cahill) (10/21/89)
In article <169@cica.cica.indiana.edu>, burleigh@cica.cica.indiana.edu (Frank Burleigh) writes: > Can the standard qsort accept not the array of structures, but > the array of pointers to structure members? If yes, how then > can the declaration of ncmp (the compare function) be changed > to accept two elements ([i], [j]) from the array of pointers, Your example would be changed to something like: typedef struct struct_name {...} struct_name; struct_name *list[MAXSIZE], **s_start, *s_one, *s_two; ^ ^ main() { /*allocate and load the array of struct here*/ ^^^^^^^^^^^^ s_start = list; /*other business*/ qsort( s_start, s_members, sizeof( struct_name *), ncmp ); ^ } int ncmp( struct_name ** s_one, struct_name ** s_two ) ^ ^ { return strcmp( (*s_one)->elem, (*s_two)->elem ); ^^^^^^^^ ^^^^^^^^ } NOTE: I have not compiled the above, but you should get the idea. -- +-----------------------------------------------------------------------+ | Conor P. Cahill uunet!virtech!cpcahil 703-430-9247 ! | Virtual Technologies Inc., P. O. Box 876, Sterling, VA 22170 | +-----------------------------------------------------------------------+