 | In this program we show a recursive version of the function strcmp. Notice that this function is slightly different from strncmp. A similar iterative program is also available. Both are made by Kurt Nørmark. |
/* Programmed by Kurt Nørmark, April 2003 */
#include <stdio.h>
#include <string.h>
/* Assume as a precondition that both s1 and s2 are non-NULL values, and '0' terminated strings. */
int mystrcmp(const char* s1, const char* s2){
int result;
if (*s1 == '\0' && *s2 == '\0')
result = 0;
else if (*s1 == '\0' && *s2 != '\0')
result = -1;
else if (*s1 != '\0' && *s2 == '\0')
result = 1;
else if (*s1 < *s2)
result = -1;
else if (*s1 > *s2)
result = 1;
else /* (*s1 == *s2) */
result = mystrcmp(s1+1, s2+1);
return result;
}
void compare(char *s1, char *s2){
printf("strcmp(\"%s\",\"%s\") = %i, %i\n", s1, s2, mystrcmp(s1,s2), strcmp(s1,s2));
}
int main(void) {
compare("abe", "kat");
compare("abe", "abe");
compare("", "kat");
compare("", "");
compare("", "a");
compare("a", "");
compare("abe", "aben");
compare("aben", "aben");
return 0;
}
| In this program we show a recursive version of the function strcmp. Notice that this function is slightly different from strncmp. A similar iterative program is also available. Both are made by Kurt Nørmark. |
| /* Assume as a precondition that both s1 and s2 are non-NULL values, and '0' terminated strings. */
int mystrcmp(const char* s1, const char* s2){ |
In the head of the function we first state a precondition: We do not cope with NULL values of the pointers s1 and s2. We assume (without testing for it) that both s1 and s2 are non-NULL pointers. We name the function mystrcmp in order not to conflict with the string.h library function strcmp. |
| if (*s1 == '\0' && *s2 == '\0') result = 0; else if (*s1 == '\0' && *s2 != '\0') result = -1; else if (*s1 != '\0' && *s2 == '\0') result = 1; else if (*s1 < *s2) result = -1; else if (*s1 > *s2) result = 1; else /* (*s1 == *s2) */ result = mystrcmp(s1+1, s2+1); |
The body of mystrcomp is one long if else chain. This makes up a simple overall structure. We first care about the most specialized cases. Most important, we chose first to deal with all possible combination of empty strings in one or the other of the parameters. We discuss these cases in the next section. |
| if (*s1 == '\0' && *s2 == '\0') result = 0; else if (*s1 == '\0' && *s2 != '\0') result = -1; else if (*s1 != '\0' && *s2 == '\0') result = 1; |
If both s1 and s2 refers to empty strings the first case applies. We return 0 because the strings are equal in that case. If s1 is empty and s2 is not, s1 is lexicographically smaller than s2, and we return -1. If, on the other hand, s1 is not empty and s2 is empty, s1 is lexicograpically larger than s2, and we return 1 (a positive number). In the remaining cases we know that we have two initial, regular characters to compare. |
| else if (*s1 < *s2) result = -1; else if (*s1 > *s2) result = 1; else /* (*s1 == *s2) */ result = mystrcmp(s1+1, s2+1); |
In case *s1 (the first character i s1) is smaller than *s2 (the first character in s2, notice the dereferencings) we return -1. If *s1 is larger than *s2, return 1. In all other cases we know that *s1 and *s2 are equal, in which case the result is the recusive comparison of s1+1 and s2+1 (the strings starting with the second character, pointer arithmetic). Recursion comes into play because we are left with a subproblem of the same overall nature as the orginal (larger) problem. This ends our discussion of mystrcmp. Notice, the single exit point (the single return) which in general is better than multiple exit points in a function. |
| void compare(char *s1, char *s2){
printf("strcmp(\"%s\",\"%s\") = %i, %i\n", s1, s2, mystrcmp(s1,s2), strcmp(s1,s2));
} |
The function compare is a handy function with compares to strings, s1 and s2, with mystrcmp and the library version of strcmp. We assume similar results, of course. But as it appears below, we do not get the same results. |
| int main(void) {
compare("abe", "kat");
compare("abe", "abe");
compare("", "kat");
compare("", "");
compare("", "a");
compare("a", "");
compare("abe", "aben");
compare("aben", "aben");
return 0;
} |
We show the output of the main program: strcmp("abe","kat") = -1, -10
strcmp("abe","abe") = 0, 0
strcmp("","kat") = -1, -107
strcmp("","") = 0, 0
strcmp("","a") = -1, -97
strcmp("a","") = 1, 97
strcmp("abe","aben") = -1, -110
strcmp("aben","aben") = 0, 0 |