Pointers in-depth by the example of sorting C-strings
Objectives: learn pointers in-depth, work with C-stringsIn this article, we show how to use pointers in C. The best way to understand pointers is to work over concrete task.
Task
- Ask user, how many strings he would like to enter;
- Read strings from user.
- Sort them in alphabetical order.
Solution of the task involves much work with the pointers.
Reading string
C-string is stored as an array of characters and terminated with null character. First, program should allocate a memory for the array. Since application doesn't know string length prior to reading it, application reads string into the buffer first. Then it allocates exact amount of memory to store string and copies characters from buffer.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main() {
char buf[256];
char *str;
int len;
printf("Input string: ");
fgets(buf, sizeof(buf), stdin);
len = strlen(buf);
/* remove new line character */
if (buf[len - 1] == '\n')
buf[len - 1] = 0;
str = (char *)calloc(len, sizeof(char));
strcpy(str, buf);
printf("Your string: %s\n", str);
free(str);
system("PAUSE");
return 0;
}
Note. Using fgets function is a good solution to read a string. First, it allows limiting number of characters to input, which prevents potential buffer overflow. It also reads whole line until newline character. Notice, that fgets doesn't throw away newline character, but put it in buf and program should remove it manually.
Extract string input into a function
Now let us extract string reading code into a function. This function returns string length. String itself is returned via a pointer argument.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int readLine(char **pStr) {
char buf[256];
int len;
printf("Input string: ");
fgets(buf, sizeof(buf), stdin);
len = strlen(buf);
// remove new line character
if (buf[len - 1] == '\n')
buf[len - 1] = 0;
*pStr = (char *)calloc(len, sizeof(char));
strcpy(*pStr, buf);
return len;
}
int main() {
char *str;
readLine(&str);
printf("Your string: %s\n", str);
free(str);
system("PAUSE");
return 0;
}
This code involves using pointer to pointer. Indeed, str is a pointer to char. To change its value inside readLine function, main should pass pointer to str, which is a pointer to pointer to char.
Reading many lines
The initial task was to ask user for number of lines he would like to input and then to read them. Let's do it.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int readLine(char **pStr) {
char buf[256];
int len;
printf("Input string: ");
fgets(buf, sizeof(buf), stdin);
len = strlen(buf);
// remove new line character
if (buf[len - 1] == '\n')
buf[len - 1] = 0;
*pStr = (char *)calloc(len, sizeof(char));
strcpy(*pStr, buf);
return len;
}
int main() {
char **strings;
int n, i;
printf("How many strings to input: ");
scanf("%d", &n);
// skip newline
getc(stdin);
strings = (char **)calloc(n, sizeof(char *));
for (i = 0; i < n; i++)
readLine(&strings[i]);
printf("Your strings: \n");
for (i = 0; i < n; i++)
printf("%s\n", strings[i]);
// free memory
for (i = 0; i < n; i++)
free(strings[i]);
free(strings);
system("PAUSE");
return 0;
}
Here we use widely applied programming trick. When storing big objects, such as strings, it's more convenient to store not the array of objects, but array of pointers to objects. First advantage of this approach is that elements may have different size (as for strings). Also, swapping two items becomes very fast and simple. Program swaps two pointers, instead of copying large objects. This trick improves performance of activities, involving many swaps, i.e. sorting.
Extract lines input into a function
Now let us extract code reading lines into a function. The function returns number of input lines. Strings are returned via a pointer argument.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int readLine(char **pStr) {
char buf[256];
int len;
printf("Input string: ");
fgets(buf, sizeof(buf), stdin);
len = strlen(buf);
// remove new line character
if (buf[len - 1] == '\n')
buf[len - 1] = 0;
*pStr = (char *)calloc(len, sizeof(char));
strcpy(*pStr, buf);
return len;
}
int readLines(char ***pStrings) {
int n, i;
printf("How many strings to input: ");
scanf("%d", &n);
// skip newline
getc(stdin);
*pStrings = (char **)calloc(n, sizeof(char *));
for (i = 0; i < n; i++)
readLine(&(*pStrings)[i]);
return n;
}
int main() {
char **strings;
int n, i;
n = readLines(&strings);
printf("Your strings: \n");
for (i = 0; i < n; i++)
printf("%s\n", strings[i]);
// free memory
for (i = 0; i < n; i++)
free(strings[i]);
free(strings);
system("PAUSE");
return 0;
}
Here we deal with a pointer to pointer to pointer to char. Let's make a stop at three stars.
Sort strings
To sort strings let's use build-in qsort function. We can't sort strings themselves, but we can sort pointers to them. To compare two pointers we design special function, which compares them, taking into account that they point to strings. So, actually, this function compares two strings. Qsort will give us two void pointers pointing to a pair of elements of the source array. Since we are sorting array of pointers to chars, comparison function get two pointers to pointers to chars. See the code.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int readLine(char **pStr) {
char buf[256];
int len;
printf("Input string: ");
fgets(buf, sizeof(buf), stdin);
len = strlen(buf);
// remove new line character
if (buf[len - 1] == '\n')
buf[len - 1] = 0;
*pStr = (char *)calloc(len, sizeof(char));
strcpy(*pStr, buf);
return len;
}
int readLines(char ***pStrings) {
int n, i;
printf("How many strings to input: ");
scanf("%d", &n);
// skip newline
getc(stdin);
*pStrings = (char **)calloc(n, sizeof(char *));
for (i = 0; i < n; i++)
readLine(&(*pStrings)[i]);
return n;
}
int compareStrings(const void *pStr1, const void *pStr2) {
return strcmp(*(char **)pStr1, *(char **)pStr2);
}
int main() {
char **strings;
int n, i;
n = readLines(&strings);
qsort(strings, n, sizeof(char *), compareStrings);
printf("Sorted strings: \n");
for (i = 0; i < n; i++)
printf("%s\n", strings[i]);
// free memory
for (i = 0; i < n; i++)
free(strings[i]);
free(strings);
system("PAUSE");
return 0;
}
Final source code
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int readLine(char **pStr) {
char buf[256];
int len;
printf("Input string: ");
fgets(buf, sizeof(buf), stdin);
len = strlen(buf);
// remove new line character
if (buf[len - 1] == '\n')
buf[len - 1] = 0;
*pStr = (char *)calloc(len, sizeof(char));
strcpy(*pStr, buf);
return len;
}
int readLines(char ***pStrings) {
int n, i;
printf("How many strings to input: ");
scanf("%d", &n);
// skip newline
getc(stdin);
*pStrings = (char **)calloc(n, sizeof(char *));
for (i = 0; i < n; i++)
readLine(&(*pStrings)[i]);
return n;
}
int compareStrings(const void *pStr1, const void *pStr2) {
return strcmp(*(char **)pStr1, *(char **)pStr2);
}
int main() {
char **strings;
int n, i;
n = readLines(&strings);
qsort(strings, n, sizeof(char *), compareStrings);
printf("Sorted strings: \n");
for (i = 0; i < n; i++)
printf("%s\n", strings[i]);
// free memory
for (i = 0; i < n; i++)
free(strings[i]);
free(strings);
system("PAUSE");
return 0;
}
To digest all this pointers information, we highly recommend to solve this task again on your own.
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!