Click Here!
home account info subscribe login search FAQ/help site map contact us


 
Brief Full
 Advanced
      Search
 Search Tips
[an error occurred while processing this directive]
Previous Table of Contents Next


6.  Run the program; the output should be as follows:
looking for Stroustrup...
Stroustrup was found!

looking for Stepanov...
Requested item was NOT found

How It Works

Let’s look at MAIN.CPP. The first source line includes <stdlib.h>, which contains the declaration of bsearch. The second source line includes <stdio.h>, which contains the declaration of the function printf(). The third line includes the prototype of compare, which is the callback function used by bsearch:

#include <stdlib.h>
#include <stdio.h>
#include “compare.h”

An array of C strings is defined and initialized inside main(). The array is deliberately not sorted.

void main()
{
  /* define an array of pointers to char and initialize it */
  char * sarr[] = {“Kernighan”, “Ritchie”, “Koenig”,”Stroustrup”};

The following keys hold values that _lfind will look up in the array. The first key exists in the array; the second one does not.

char *pkey  = “Stroustrup”;
char *pkey2 = “Stepanov”;

A void pointer, p, stores the result of _lfind. Also, a variable num of type unsigned int is declared as an argument of _lfind.

void *p = NULL;
unsigned int num = 4; /* number of array elements */

_lfind is invoked twice. Here is the first invocation:

  printf (“\nlooking for %s...\n”, pkey);

  p = _lfind( &pkey,     /* address of key */
	       sarr,      /* address of array’s beginning */
	      &num,       /* number of elements in array */
	       sizeof (char *), /* sizeof each element */
	       compare);  /* pointer to user-defined comparison function */

The parameters passed to _lfind are the same as the parameters of bsearch, except for the third one. The first element is the address of a key _lfind has to look up (the address of a value to be located in the array). In this case, the sought array holds elements of type char *. A pointer to a char * is passed as the first argument. The second argument is the address of the array. The third argument is slightly different from bsearch: Instead of the number of total elements in the array, pass a pointer to an unsigned int that holds the number of total elements in the array. The fourth argument is the size of an element in the array. Finally, pass the address of the callback function. Again, it is the address of compare that you’ve used before.

The result returned from _lfind is stored in p._lfind returns the address of the element that holds the value of the key, or null when the key does not exist in the array. Test the returned value and display a message accordingly:

if (p)
  printf(“%s was found!\n”, *(const char **) p);
else
  printf(“requested item was NOT found\n”);

printf (“\nlooking for %s...\n”, pkey2);

_lfind looked for an element with the value “Stroustrup”. This value exists in the array. In the second invocation of _lfind, use a key with the value “Stepanov”. No element in the array holds this value, so you can expect to get null.

  printf (“\nlooking for %s...\n”, pkey2);

  p = _lfind( &pkey2,  /* address of key */
	       sarr,    /* address of array’s beginning */
	       &num,    /* number of elements in array */
	       sizeof (char *), /* sizeof each element */
	       compare);/* pointer to user-defined comparison function */
  if (p)
    printf(“%s was found!\n”, *(const char **) p);
  else
    printf(“requested item was NOT found\n”);
}

As expected, you get a null result this time.

8.4 Choose between_lfind and_lsearch?

Problem

I know how to use bsearch to find an element in a sorted array, and I also know I have to use _lfind to look up an element in an array that has not been sorted. However, I would like to know when I should use _lfind and when I should use _lsearch. Apparently, both these functions can be used to find an element in an array that has not been sorted.

Technique

_lsearch, like _lfind, performs a linear search on an array that doesn’t have to be sorted in advance. The signature of _lsearch is identical to _lfind. Thus, these functions are pretty similar. However, there are three differences in their behavior when a key cannot be found in the array:

1.  Unlike _lfind, which returns null when it cannot find a key, _lsearch appends that key to the end of the array.
2.  _lsearch increments the number of array elements (the third argument) to reflect the fact that a new element has been added to the array.
3.  After appending the new element and incrementing the number of elements, _lsearch returns a pointer to the newly added key.

The following program demonstrates how to use _lsearch.


Previous Table of Contents Next


Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.