Using qsort() and bsearch() with strings - example program in C
By: Manoj Kumar in C Tutorials on 2007-10-03
This program makes use of an array of pointers to strings.You can "sort" the strings by sorting the array of pointers. However, this method requires a modification in the comparison function. This function is passed pointers to the two items in the array that are compared. However, you want the array of pointers sorted based not on the values of the pointers themselves but on the values of the strings they point to.
Because of this, you must use a comparison function that is passed pointers to pointers. Each argument to comp() is a pointer to an array element, and because each element is itself a pointer (to a string), the argument is therefore a pointer to a pointer. Within the function itself, you dereference the pointers so that the return value of comp() depends on the values of the strings pointed to.
The fact that the arguments passed to comp() are pointers to pointers creates another problem. You store the search key in buf[], and you also know that the name of an array (buf in this case) is a pointer to the array. However, you need to pass not buf itself, but a pointer to buf. The problem is that buf is a pointer constant, not a pointer variable. buf itself has no address in memory; it's a symbol that evaluates to the address of the array. Because of this, you can't create a pointer that points to buf by using the address-of operator in front of buf, as in &buf.
What to do? First, create a pointer variable and assign the value of buf to it. In the program, this pointer variable has the name key. Because key is a pointer variable, it has an address, and you can create a pointer that contains that address--in this case, key1. When you finally call bsearch(), the first argument is key1, a pointer to a pointer to the key string. The function bsearch() passes that argument on to comp(), and everything works properly.
1: /* Using qsort() and bsearch() with strings. */ 2: 3: #include <stdio.h> 4: #include <stdlib.h> 5: #include <string.h> 6: 7: #define MAX 20 8: 9: int comp(const void *s1, const void *s2); 10: 11: main() 12: { 13: char *data[MAX], buf[80], *ptr, *key, **key1; 14: int count; 15: 16: /* Input a list of words. */ 17: 18: printf("Enter %d words, pressing Enter after each.\n",MAX); 19: 20: for (count = 0; count < MAX; count++) 21: { 22: printf("Word %d: ", count+1); 23: gets(buf); 24: data[count] = malloc(strlen(buf)+1); 25: strcpy(data[count], buf); 26: } 27: 28: /* Sort the words (actually, sort the pointers). */ 29: 30: qsort(data, MAX, sizeof(data[0]), comp); 31: 32: /* Display the sorted words. */ 33: 34: for (count = 0; count < MAX; count++) 35: printf("\n%d: %s", count+1, data[count]); 36: 37: /* Get a search key. */ 38: 39: printf("\n\nEnter a search key: "); 40: gets(buf); 41: 42: /* Perform the search. First, make key1 a pointer */ 43: /* to the pointer to the search key.*/ 44: 45: key = buf; 46: key1 = &key; 47: ptr = bsearch(key1, data, MAX, sizeof(data[0]), comp); 48: 49: if (ptr != NULL) 50: printf("%s found.\n", buf); 51: else 52: printf("%s not found.\n", buf); 53: return(0); 54: } 55: 56: int comp(const void *s1, const void *s2) 57: { 58: return (strcmp(*(char **)s1, *(char **)s2)); 59: } Enter 20 words, pressing Enter after each. Word 1: apple Word 2: orange Word 3: grapefruit Word 4: peach Word 5: plum Word 6: pear Word 7: cherries Word 8: banana Word 9: lime Word 10: lemon Word 11: tangerine Word 12: star Word 13: watermelon Word 14: cantaloupe Word 15: musk melon Word 16: strawberry Word 17: blackberry Word 18: blueberry Word 19: grape Word 20: cranberry 1: apple 2: banana 3: blackberry 4: blueberry 5: cantaloupe 6: cherries 7: cranberry 8: grape 9: grapefruit 10: lemon 11: lime 12: musk melon 13: orange 14: peach 15: pear 16: plum 17: star 18: strawberry 19: tangerine 20: watermelon Enter a search key: orange orange found.
DON'T forget to put your search array into ascending order before using bsearch().
Add Comment
This policy contains information about your privacy. By posting, you are declaring that you understand this policy:
- Your name, rating, website address, town, country, state and comment will be publicly displayed if entered.
- Aside from the data entered into these form fields, other stored data about your comment will include:
- Your IP address (not displayed)
- The time/date of your submission (displayed)
- Your email address will not be shared. It is collected for only two reasons:
- Administrative purposes, should a need to contact you arise.
- To inform you of new comments, should you subscribe to receive notifications.
- A cookie may be set on your computer. This is used to remember your inputs. It will expire by itself.
This policy is subject to change at any time and without notice.
These terms and conditions contain rules about posting comments. By submitting a comment, you are declaring that you agree with these rules:
- Although the administrator will attempt to moderate comments, it is impossible for every comment to have been moderated at any given time.
- You acknowledge that all comments express the views and opinions of the original author and not those of the administrator.
- You agree not to post any material which is knowingly false, obscene, hateful, threatening, harassing or invasive of a person's privacy.
- The administrator has the right to edit, move or remove any comment for any reason and without notice.
Failure to comply with these rules may result in being banned from submitting further comments.
These terms and conditions are subject to change at any time and without notice.
Most Viewed Articles (in C ) |
Latest Articles (in C) |
- Data Science
- Android
- React Native
- AJAX
- ASP.net
- C
- C++
- C#
- Cocoa
- Cloud Computing
- HTML5
- Java
- Javascript
- JSF
- JSP
- J2ME
- Java Beans
- EJB
- JDBC
- Linux
- Mac OS X
- iPhone
- MySQL
- Office 365
- Perl
- PHP
- Python
- Ruby
- VB.net
- Hibernate
- Struts
- SAP
- Trends
- Tech Reviews
- WebServices
- XML
- Certification
- Interview
categories
Related Tutorials
Sum of the elements of an array in C
Printing a simple histogram in C
Find square and square root for a given number in C
Simple arithmetic calculations in C
Passing double value to a function in C
Passing pointer to a function in C
Infix to Prefix And Postfix in C
while, do while and for loops in C
Comments