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


3.  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.
4.  Run the program; the output should be as follows:
element 0 of sarr is: Stroustrup
element 1 of sarr is: Koenig
element 2 of sarr is: Ritchie
element 3 of sarr is: Kernighan
sorted

element 0 of sarr is: Kernighan
element 1 of sarr is: Koenig
element 2 of sarr is: Ritchie
element 3 of sarr is: Stroustrup

How It Works

Let’s look at MAIN.CPP. This program sorts an array of char *. The array contains four elements—the names of C and C++ creators. No changes are added to the flow of the program. The only changes are those deriving from the different type of the array elements and the size of the array.

Let’s look at COMPARE.CPP to see the changes. The first source lines includes the header file <string.h>, which contains the declaration of strcmp.

#include <string.h>

The prototype of compare, as expected, is the same. However, the function body has changed. strcmp is used to compare the arguments, which you know are C strings. Luckily, strcmp does not return a Boolean value indicating whether the strings are identical; it would be useless for our purpose. Rather, it performs a lexicographical comparison. A lexicographical comparison compares two strings in a method similar to the way two words are compared to decide which comes first in a dictionary. A lexicographic comparison treats every character of the compared strings as an integer. The value of the character of the second string is subtracted from the corresponding value of the first string. The result can be 0, which means that the two strings are identical. A positive value indicates the first string ranks lexicographically higher than the second one. A negative value indicates the first string ranks lexicographically lower than the second one. This is exactly what qsort expects to get from its callback function, so compare has only to invoke strcmp and return the result. In order to call strcmp, you have to cast the void pointers to their real types.

int __cdecl compare (const void * pfirst, const void  * psecond)
{
  return strcmp(*(const char**) pfirst, *(const char **) psecond);
}

Comments

qsort, as you have seen, is a powerful algorithm. It is efficient, generic, and standardized. However, you have to bear in mind that it does not support C++ objects. Unlike STL containers, qsort will not reconstruct a relocated object, nor will it invoke the destructor of that object in its previous location. In other words, qsort and STL’s sort are not interchangeable, but are complementary. You should use qsort with arrays (and arrays only) of plain data types such as char, int, pointers of all kind, and structs.

8.2 Find an element in an array?

Problem

I know how to sort an array but I need to find an element in it. How do I do it in C?

Technique

Standard C has a generic function for searching an element in an array—bsearch.bsearch performs a binary search on a sorted array of elements. If your array is not sorted, you should sort it before using bsearch. Later you will see how it is possible to locate an element in a nonsorted array.

bsearch tries to locate an element in an array. If the element exists, bsearch returns a pointer to it. Otherwise, it returns null.bsearch and qsort are similar both in the way they are used and in the principles of their implementation. Therefore, it is advisable for you to read this How-To after reading How-To 8.1. Remember also that this How-To uses two source files from the “Comments” section of How-To 8.1—COMPARE.H and COMPARE.CPP. The text states whether a source file is identical to any of the source files used in previous examples.

Steps

1.  Change to your base source directory and create a new subdirectory named C_BSEARCH.
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 “compare.h”

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

  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 */
  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 = 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”);
}
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.
6.  Run the program; the output should be as follows:
looking for Stroustrup...
Stroustrup was found!

looking for Stepanov...
Requested item was NOT found


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.