To reverse a word you might copy it backwards into a second array. You do not need one: swap the two ends and move inwards. Watch “signal” turn round in place.
Reversing a word in place
Two pointers swap the ends of signal and move inwards
void reverse(char *s){ size_t n = 0; while (s[n] != '\0') n++; if (n == 0) return; char *lo = s; char *hi = s + n - 1; while (lo < hi) { char t = *lo; *lo = *hi; *hi = t; lo++; hi--; }}int main(void){ char word[] = "signal"; reverse(word); printf("%s\n", word); char name[] = "dsp";main has started.
- n
- –
- swaps
- 0
Output
Describe this picture
One strip, char word[] = "signal": seven one-byte cells holding s, i, g, n, a, l and the zero byte, drawn as \0, with the code of reverse and the start of main beside it, the line about to run marked. The clip takes about 13 seconds. First a marker n walks from cell 0, each cell tinted as it is read, and stops on the zero: the readout “n” reads 6. Then lo appears above cell 0 and hi below cell 5. Each pass tints the two cells, swaps them, the letters crossing, and moves lo one cell right and hi one cell left: s and l make lignas, i and a make lagnis, g and n make langis. When lo has passed hi the loop stops; the readout “swaps” reads 3, and the output reads langis. The transport plays and pauses, steps one line back or forward, and scrubs; a paused step is kept in the page address as reverse-word.step.
Letters as codes
Strings in C showed that a char is a number. That makes many string tasks arithmetic: the lower-case letters run from 97 to 122 in order, the upper-case ones from 65 to 90, and the digits from 48 to 57.
The other half of most string tasks is a walk: one pointer from the front, or two from both ends towards the middle.
The code and its cost
Case
void to_upper(char *s)
{
for (size_t i = 0; s[i] != '\0'; i++)
if (s[i] >= 'a' && s[i] <= 'z')
s[i] = (char)(s[i] - 32);
}'a' - 'A' is 32, so changing case is one subtraction: “dsp” becomes “DSP”. The functions isalpha and toupper in <ctype.h> do the same for any character set the system uses; pass them the char as an unsigned char value.
Two pointers
void reverse(char *s)
{
size_t n = 0;
while (s[n] != '\0')
n++;
if (n == 0)
return;
char *lo = s;
char *hi = s + n - 1;
while (lo < hi) {
char t = *lo;
*lo = *hi;
*hi = t;
lo++;
hi--;
}
}After finding n, lo starts on the first char and hi on the last. Each pass swaps them through t and moves both inwards. For “signal” the passes are cells 0 and 5, 1 and 4, 2 and 3; then lo is past hi. A string of length n takes ⌊n/2⌋ swaps, and no second array: the middle char of an odd length stays where it is.
Comparing
int compare(const char *a, const char *b)
{
while (*a != '\0' && *a == *b) {
a++;
b++;
}
return (unsigned char)*a - (unsigned char)*b;
}Walk both strings while they agree and the first has not ended, then return the difference of the chars where they stopped: negative if a sorts first, zero if they are equal, positive if b sorts first. compare("cat", "car") stops at 't' against 'r' and returns 2.
== does not compare strings. On two arrays or two pointers it compares addresses.
Palindromes
is_palindrome uses the same two ends: compare s[lo] with s[hi], step inwards, and stop at the first difference. “level” matches l with l and e with e, then lo meets hi at the v: true after 2 comparisons. “signal” fails at once, s against l. The program prints 1 0.
Literals and arrays
char word[] = "signal"; makes an array of 7 chars, a copy of the literal that the program may change. char *w = "signal"; makes a pointer to the literal itself, which the program must not write to: writing to a string literal is undefined behaviour.
Worked example
Digits to numbers. '7' - '0' is 7.
A shorter string. compare("car", "cart") runs out of “car” first: the zero, 0, against 't', 116, gives −116.
“radar” by hand. r against r, a against a, then lo and hi meet at cell 2: 2 comparisons, a palindrome.
Writing to a literal. char *w = "signal"; reverse(w); writes to a literal, which is undefined behaviour. On this build it stopped with a segmentation fault at the first swap: literal.c’s sanitiser build reports SEGV in reverse, on the line *lo = *hi;.
Two arrays holding “dsp”. Pointers to two separate arrays that both hold “dsp” are not equal, p == q is 0, while compare(p, q) is 0: same chars, two addresses. (gcc refuses to compile a == b on the two arrays themselves with warnings as errors: it is almost always a mistake.)
Two checks. How many swaps reverse a 9-letter word? (4.) What sign does compare("dog", "cat") have? (Positive: d comes after c.)
Where it’s used
Command lines. Programs read their options as strings and compare them with the names they know.
Matching and search. Case-insensitive matching and normalising text before a search change case first, then compare.
Checking input. A date, a postcode or a number typed by a user is checked char by char before it is used.
Reference card
| Code or idea | Meaning |
|---|---|
'a' - 'A' | 32: change case by subtracting or adding it |
c - '0' | a digit’s value |
| two pointers | lo from the front, hi from the back, until lo ≥ hi |
| reverse | ⌊n/2⌋ swaps, in place |
| compare | walk while equal; return the difference of the first unequal chars |
a == b | compares addresses, not chars |
char w[] = "…"; | a changeable copy |
char *w = "…"; | points at the literal: do not write to it |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.