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


How It Works

Let’s look at MAIN.CPP. The first source line includes <stdlib.h>, which contains the prototype of bsearch. The second source line includes <stdio.h>, which contains the prototype of printf(). The third line includes the prototype of compare, 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 has four elements, and it is initialized in a sorted order.

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

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

char *pkey  = “Stroustrup”; //exists in array
char *pkey2 = “Stepanov”;  //does not exist in array

A void pointer, p, stores the result of bsearch.

void *p = NULL;

bsearch is invoked twice. Here is the first invocation:

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

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

The arguments passed to bsearch are the same as the arguments of qsort, except for the first one. Let’s examine the role of each argument. The first one is the address of a key that bsearch has to look up. That is, the address of a value to be located in the array. In this case, the array in question holds elements of type char *; therefore, a pointer to char * is passed as the first argument.

The rest should look familiar. The second argument is the address of the array. The third argument is the total number of elements in the array. The fourth argument is the size of an element in the array. Finally, pass the address of the callback function. It is the same function compare used in the previous How-To.

The result returned from bsearch is stored in p.bsearch returns the address of the element that holds the value of the key, or null when the key does not exist in the array. You test the returned value and print 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);

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

  p = bsearch( &pkey2,  /*address of key */
	       sarr,     /* address of array’s beginning */
	       4,        /* 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”);
}

And null is what you get.

8.3 Locate an element in a nonsorted array?

Problem

I have to look up a value in an array. I cannot use bsearch for this purpose because the array is not sorted. How can I locate an element in the array without having to sort it first?

Technique

Standard C does not offer a solution to this problem. However, many vendors ship with their compiler libraries two additional lookup functions—_lsearch and _lfind. Both can locate an element in any array, sorted and nonsorted alike.

Steps

1.  Change to your base source directory and create a new subdirectory named FIND_AND_SEARCH.
2.  Start your source code editor and type the following code into a file named COMPARE.H. (Note: The following source file is identical to the source file COMPARE.H from the “Comments” section in How-To 8.1.)
#ifndef COMPARE_H
#define COMPARE_H

int __cdecl compare (const void* pfirst, const void  * psecond);

#endif
3.  Save COMPARE.H. Type the following code into a new file named COMPARE.CPP (Note: The following source code is identical to the source code file COMPARE.CPP from the “Comments” section in How-To 8.1.)
#include <string.h>

int __cdecl compare (const void * pfirst, const void  * psecond)
{
  return strcmp(*(const char**) pfirst, *(const char **) psecond);
}
4.  Save COMPARE.CPP. Type the following code into a new file named MAIN.CPP:
#include <stdlib.h>
#include <stdio.h>
#include <search.h>
#include “compare.h”

void main()
{
  /* define an array of pointers to char and initialize it */
  char * sarr[] = {“Kernighan”, “Ritchie”, “Koenig”,”Stroustrup”};
  char *pkey  = “Stroustrup”;
  char *pkey2 = “Stepanov”;
  void *p = NULL;
  unsigned int num = 4; /* number of array elements */

  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 */
  if (p)
    printf(“%s was found!\n”, *(const char **) p);
  else
    printf(“requested item was NOT found\n”);

  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”);
}
5.  Save MAIN.CPP. Compile MAIN.CPP and COMPARE.CPP, and link MAIN.CPP.
If you are not working in a Windows environment, your compiler might complain about the __cdecl specifier in the prototype and the definition of the function compare. In that case, comment out or remove the specifier __cdecl from COMPARE.H and COMPARE.CPP.


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.