[ Bottom of Page | Previous Page | Next Page | Contents | Index | Library Home | Legal | Search ]

General Programming Concepts:
Writing and Debugging Programs

Searching and Sorting Example Program

/**This program demonstrates the use of the following: 

-qsort subroutine (a quick sort library routine)

-bsearch subroutine (a binary search library routine) 

-fgets, fopen, fprintf, malloc, sscanf, and strcmp subroutines.

The program reads two input files with records in
string format, and prints or displays:

-records from file2, which are excluded in file1

-records from file1, which are excluded in file2

The program reads the input records from both files
into two arrays, which are  subsequently sorted in
common order using the qsort subroutine. Each element of
one array is searched for its counterpart entry in the
other array using the bsearch subroutine. If the item is
not found in both arrays, a message indicates the record
was not found. The process is repeated interchanging
the two arrays, to obtain the second list of exclusions.


#include <stdio.h>      /*the library file to be included for
                         /*standard input and output*/

#include <search.h>     /*the file to be included for qsort*/
#include <sys/errno.h>  /*the include file for interpreting   

                        /*predefined error conditions*/

#define MAXRECS  10000           /*array size limit*/

#define MAXSTR   256             /*maximum input string length*/
#define input1 "file1"           /*one input file*/
#define input2 "file2"           /*second input file*/
#define out1   "o_file1"         /*output file1*/
#define out2   "o_file2"         /*output file2*/


char *arr1[MAXRECS] , *arr2[MAXRECS] ;/*the arrays to store

input records*/

unsigned int num1 , num2;        /*to keep track of the number of

                                 /*input records. Unsigned int 

                                 /*declaration ensures

                                 /*with qsort library routine.*/

int i ;
int compar();            /*the function used by qsort and  


extern int errno ; /*to capture system call failures*/
FILE *ifp1 , *ifp2, *ofp1, *ofp2; /*the file pointers for 

input and output */

void *bsearch() ;       /*the library routine for binary search*/
void qsort();           /*the library routine for quick sort*/
char*malloc() ;         /*memory allocation subroutine*/
void exit() ;

num1 = num2 = 0;

/**Open the input and output files for reading or writing

if ( (ifp1 = fopen( input1 , "r" ) ) == NULL )

(void) fprintf(stderr,"%s could not be opened\n",input1);


if (( ifp2 = fopen( input2 , "r" )) == NULL )

(void) fprintf(stderr,"%s could not be opened\n",input2);


if (( ofp1 = fopen(out1,"w" )) == NULL )

(void) fprintf(stderr,"%s could not be opened\n",out1);


if (( ofp2 = fopen(out2,"w")) == NULL )

(void) fprintf(stderr,"%s could not be opened\n", out2);


/**Fill the arrays  with data from input files. Readline
function returns the number of input records.**/   

if ( (i = readline( arr1 , ifp1 ))  < 0 )

(void) fprintf(stderr,"o data in %s. Exiting\n",input1);

num1 = (unsigned) i;
if ( (i = readline ( arr2 , ifp2)) < 0 )

(void) fprintf(stderr,"No data in %s.  Exiting\n",input2);

num2 = (unsigned) i;

The arrays can now be sorted using qsort subroutine

qsort( (char *)arr1 , num1 ,  sizeof (char *)  , compar);
qsort( (char *)arr2 , num2 ,  sizeof (char *)  , compar);

/**When the two arrays are sorted in a common order, the
program builds a list of elements found in one but not
in the other, using bsearch.   

Check that each element in array1 is in array2

for ( i= 0 ; i < num1 ; i++ )

if ( bsearch((void *)&arr1[i] , (char *)arr2,num2, 

sizeof(char *) , compar) == NULL )

(void)  fprintf(ofp1,"%s",arr1[i]);


} /**One list of exclusions is complete**/

/**Check that each element in array2 is in array1**/

for ( i = 0 ; i < num2 ; i++ )
 if ( bsearch((void *)&arr2[i], (char *)arr1, num1 

, sizeof(char *) , compar) == NULL )

(void) fprintf(ofp2,"%s",arr2[i]);


/**Task completed, so return**/



/**The function reads in records from an input 
 file and fills in the details into the two arrays.**/

readline ( char **aptr, FILE *fp )


char str[MAXSTR] , *p ;
int i=0 ;

/**Read the input file line by line**/

while ( fgets(str , sizeof(str) , fp ))

/**Allocate sufficient memory. If the malloc subroutine
fails, exit.**/

if ( (p = (char *)malloc ( sizeof(str))) == NULL )

(void) fprintf(stderr,"Insufficient Memory\n");


if ( 0 > strcpy(p, str))

(void) fprintf(stderr,"Strcpy failed \n");
i++ ; /*increment number of records count*/  


} /**End of input file reached**/
return(i);/*return the number of records read*/


/**We want to sort the arrays based only on the contents of the first field of
the input records. So we get the first  field using SSCANF**/

compar( char **s1 , char **s2 ) 

char st1[100] , st2[100] ;
(void) sscanf(*s1,"%s" , st1) ;
(void) sscanf(*s2,"%s" , st2) ;

/**Return the results of string comparison to the calling procedure**/

return(strcmp(st1 , st2));


[ Top of Page | Previous Page | Next Page | Contents | Index | Library Home | Legal | Search ]