library_8.html

Linux程序员的工作手册

<!-- This HTML file has been created by texi2html 1.27
     from library.texinfo on 3 March 1994 -->

<TITLE>The GNU C Library - Searching and Sorting</TITLE>
<P>Go to the <A HREF="library_7.html" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_7.html">previous</A>, <A HREF="library_9.html" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_9.html">next</A> section.<P>
<H1><A NAME="SEC86" HREF="library_toc.html#SEC86" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_toc.html#SEC86">Searching and Sorting</A></H1>
<P>
This chapter describes functions for searching and sorting arrays of
arbitrary objects.  You pass the appropriate comparison function to be
applied as an argument, along with the size of the objects in the array
and the total number of elements.
<P>
<A NAME="IDX380"></A>
<H2><A NAME="SEC87" HREF="library_toc.html#SEC87" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_toc.html#SEC87">Defining the Comparison Function</A></H2>
<P>
In order to use the sorted array library functions, you have to describe
how to compare the elements of the array.
<P>
To do this, you supply a comparison function to compare two elements of
the array.  The library will call this function, passing as arguments
pointers to two array elements to be compared.  Your comparison function
should return a value the way <CODE>strcmp</CODE> (see section <A HREF="library_5.html#SEC62" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_5.html#SEC62">String/Array Comparison</A>) does: negative if the first argument is "less" than the
second, zero if they are "equal", and positive if the first argument
is "greater".
<P>
Here is an example of a comparison function which works with an array of
numbers of type <CODE>double</CODE>:
<P>
<PRE>
int
compare_doubles (const double *a, const double *b)
{
  double temp = *a - *b;
  if (temp &#62; 0)
    return 1;
  else if (temp &#60; 0)
    return -1;
  else
    return 0;
}
</PRE>
<P>
The header file <TT>`stdlib.h'</TT> defines a name for the data type of
comparison functions.  This is a GNU extension and thus defined only if
you request the GNU extensions.
<A NAME="IDX381"></A>
<P>
<PRE>
int comparison_fn_t (const void *, const void *);
</PRE>
<P>
<A NAME="IDX382"></A>
<A NAME="IDX383"></A>
<A NAME="IDX384"></A>
<H2><A NAME="SEC88" HREF="library_toc.html#SEC88" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_toc.html#SEC88">Array Search Function</A></H2>
<P>
To search a sorted array for an element matching the key, use the
<CODE>bsearch</CODE> function.  The prototype for this function is in
the header file <TT>`stdlib.h'</TT>.
<A NAME="IDX385"></A>
<P>
<A NAME="IDX386"></A>
<U>Function:</U> void * <B>bsearch</B> <I>(const void *<VAR>key</VAR>, const void *<VAR>array</VAR>, size_t <VAR>count</VAR>, size_t <VAR>size</VAR>, comparison_fn_t <VAR>compare</VAR>)</I><P>
The <CODE>bsearch</CODE> function searches the sorted array <VAR>array</VAR> for an object
that is equivalent to <VAR>key</VAR>.  The array contains <VAR>count</VAR> elements,
each of which is of size <VAR>size</VAR>.
<P>
The <VAR>compare</VAR> function is used to perform the comparison.  This
function is called with two pointer arguments and should return an
integer less than, equal to, or greater than zero corresponding to
whether its first argument is considered less than, equal to, or greater
than its second argument.  The elements of the <VAR>array</VAR> must already
be sorted in ascending order according to this comparison function.
<P>
The return value is a pointer to the matching array element, or a null
pointer if no match is found.  If the array contains more than one element
that matches, the one that is returned is unspecified.
<P>
This function derives its name from the fact that it is implemented
using the binary search.
<P>
<A NAME="IDX387"></A>
<A NAME="IDX388"></A>
<A NAME="IDX389"></A>
<H2><A NAME="SEC89" HREF="library_toc.html#SEC89" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_toc.html#SEC89">Array Sort Function</A></H2>
<P>
To sort an array using an arbitrary comparison function, use the
<CODE>qsort</CODE> function.  The prototype for this function is in
<TT>`stdlib.h'</TT>.
<A NAME="IDX390"></A>
<P>
<A NAME="IDX391"></A>
<U>Function:</U> void <B>qsort</B> <I>(void *<VAR>array</VAR>, size_t <VAR>count</VAR>, size_t <VAR>size</VAR>, comparison_fn_t <VAR>compare</VAR>)</I><P>
The <VAR>qsort</VAR> function sorts the array <VAR>array</VAR>.  The array contains
<VAR>count</VAR> elements, each of which is of size <VAR>size</VAR>.
<P>
The <VAR>compare</VAR> function is used to perform the comparison on the
array elements.  This function is called with two pointer arguments and
should return an integer less than, equal to, or greater than zero
corresponding to whether its first argument is considered less than,
equal to, or greater than its second argument.
<A NAME="IDX392"></A>
<P>
<STRONG>Warning:</STRONG> If two objects compare as equal, their order after
sorting is unpredictable.  That is to say, the sorting is not stable.
This can make a difference when the comparison considers only part of
the elements.  Two elements with the same sort key may differ in other
respects.
<P>
If you want the effect of a stable sort, you can get this result by
writing the comparison function so that, lacking other reason
distinguish between two elements, it compares them by their addresses.
<P>
Here is a simple example of sorting an array of doubles in numerical
order, using the comparison function defined above (see section <A HREF="library_8.html#SEC87" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_8.html#SEC87">Defining the Comparison Function</A>):
<P>
<PRE>
{
  double *array;
  int size;
  ...
  qsort (array, size, sizeof (double), compare_doubles);
}
</PRE>
<P>
The <CODE>qsort</CODE> function derives its name from the fact that it was
originally implemented using the algorithm "quick sort".
<P>
<H2><A NAME="SEC90" HREF="library_toc.html#SEC90" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_toc.html#SEC90">Searching and Sorting Example</A></H2>
<P>
Here is an example showing the use of <CODE>qsort</CODE> and <CODE>bsearch</CODE>
with an array of structures.  The objects in the array are sorted
by comparing their <CODE>name</CODE> fields with the <CODE>strcmp</CODE> function.
Then, we can look up individual objects based on their names.
<P>
<PRE>
#include &#60;stdlib.h&#62;
#include &#60;stdio.h&#62;
#include &#60;string.h&#62;

/* Define an array of critters to sort.  */

struct critter
{
  char *name;
  char *species;
};

struct critter muppets[]=
{
  {"Kermit", "frog"},
  {"Piggy", "pig"},
  {"Gonzo", "whatever"},
  {"Fozzie", "bear"},
  {"Sam", "eagle"},
  {"Robin", "frog"},
  {"Animal", "animal"},
  {"Camilla", "chicken"},
  {"Sweetums", "monster"},
  {"Dr. Strangepork", "pig"},
  {"Link Hogthrob", "pig"},
  {"Zoot", "human"},
  {"Dr. Bunsen Honeydew", "human"},
  {"Beaker", "human"},
  {"Swedish Chef", "human"}};

int count = sizeof (muppets) / sizeof (struct critter);



/* This is the comparison function used for sorting and searching.  */

int 
critter_cmp (const struct critter *c1, const struct critter *c2)
{
  return strcmp (c1-&#62;name, c2-&#62;name);
}


/* Print information about a critter.  */

void 
print_critter (const struct critter *c)
{
  printf ("%s, the %s\n", c-&#62;name, c-&#62;species);
}


/* Do the lookup into the sorted array.  */

void 
find_critter (char *name)
{
  struct critter target, *result;
  target.name = name;
  result = bsearch (&#38;target, muppets, count, sizeof (struct critter),
		    critter_cmp);
  if (result)
    print_critter (result);
  else
    printf ("Couldn't find %s.\n", name);
}

/* Main program.  */

int
main (void)
{
  int i;

  for (i = 0; i &#60; count; i++)
    print_critter (&#38;muppets[i]);
  printf ("\n");

  qsort (muppets, count, sizeof (struct critter), critter_cmp);

  for (i = 0; i &#60; count; i++)
    print_critter (&#38;muppets[i]);
  printf ("\n");

  find_critter ("Kermit");
  find_critter ("Gonzo");
  find_critter ("Janice");

  return 0;
}
</PRE>
<A NAME="IDX393"></A>
<P>
The output from this program looks like:
<P>
<PRE>
Animal, the animal
Beaker, the human
Camilla, the chicken
Dr. Bunsen Honeydew, the human
Dr. Strangepork, the pig
Fozzie, the bear
Gonzo, the whatever
Kermit, the frog
Link Hogthrob, the pig
Piggy, the pig
Robin, the frog
Sam, the eagle
Swedish Chef, the human
Sweetums, the monster
Zoot, the human


Kermit, the frog
Gonzo, the whatever
Couldn't find Janice.
</PRE>
<P>
<P>Go to the <A HREF="library_7.html" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_7.html">previous</A>, <A HREF="library_9.html" tppabs="http://www.cs.utah.edu/dept/old/texinfo/glibc-manual-0.02/library_9.html">next</A> section.<P>