Kenny Kerr - Code Corner

Code Corner - Algorithms

I've always wanted to study computer science at a university. Unfortunately I've never been able to afford it. Its a real pity as I really enjoy the academic nature of computer science. As a result I don't have much experience writing algorithms. Even though one doesn't write all that many algorithms in typical business software, it is very good practice as it makes you think. So to improve my algorithm writing skills (and to help me to think) I'm going to start writing an algorithm-related routine every so often. These algorithms are presented here largely for their academic value. In production code prefer supported libraries to writing your own. For example, instead of writing a linked list or a string class, use the Standard C++ library.

Note: these code snippets were compiled and tested using Visual C++ 6. If you are using a different compiler or version you may have to tweak them a little to get them to work.

Reverse the words in a string (23 January 2002)

Reverse a string in place (2 Nov 2001)

Reverse the words in a string (23 January 2002)

A more interesting problem than Reversing a string in place, is to reverse the words in a string, and doing so without allocating any additional memory. Well I had to think about this one for a while. How do you move groups of characters (words) in place, especially since they can be of different lengths? Well the thing to remember is that you must just keep the characters together. If we use my ReverseString function from last time, we get the groups of characters together and grouped in the right order (in other words back to front). But the characters of the words are now backwards. To solve this we can just reapply the reversing algorithm to each word! To do this I must first make my ReverseString function a bit more generic:

#include <string.h>

char* ReverseString(char* begin, char* end)
{
    char* first = begin;
    char* last = end - 1;

    for(; first < last; ++first, --last)
    {
        *first = *first + *last;
        *last  = *first - *last;
        *first = *first - *last;
    }

    return begin;
}

char* ReverseString(char* pstr)
{
    return ReverseString(pstr, pstr + strlen(pstr));
}

What I've done is to change ReverseString to work on any sequence of characters. This allows me to pass it a substring (for example a word). So to reverse the words I first call ReverseString on the entire string to group the characters together so that the groups are in the right order. Then I iterate over the string and reverse the characters in each group individually.

#include <algorithm>

char* ReverseWordsInString(char* begin, char* end)
{
    ReverseString(begin, end);

    char* word = begin;
    char* space = std::find(word, end, ' ');

    ReverseString(word, space);

    while (space < end)
    {
        word = space + 1;
        space = std::find(word, end, ' ');

        ReverseString(word, space);
    }

    return begin;
}

char* ReverseWordsInString(char* pstr)
{
    return ReverseWordsInString(pstr, pstr + strlen(pstr));
}

Its important to call ReverseString at least once after the entire sting has been reversed in the beginning. This is for the case where the string contains only a single word.

Examples:

Original string	Result
Joshua is seven months old today	today old months seven is Joshua
Joshua	Joshua

Reverse a string in place (2 Nov 2001)

This seems to be quite a common one. So I thought I'd give it a try. Before you can think about reversing a string in place you must figure out how to swap the value of an intrinsic object such as an integer or a character variable without allocating any additional memory. The qualification is that you must be able to perform mathematical or algebraic operation on this type. For example:

#include <iostream>

int main()
{
    int x = 123;
    int y = 456;

    std::cout << x << " - " << y << std::endl;

    x = x + y;
    y = x - y;
    x = x - y;

    std::cout << x << " - " << y << std::endl;

    return 0;
}

As you can see its quite easy once you know how. It works equally well using boolean algebra using the bitwise operators, but I don't generally recommend using these as they tend to make the code hard to read and invariably less portable. The next step is to apply this swapping technique to the characters in the string. To be honest with you I first wrote the code to iterate over the characters in the string using the swap routine from the Standard C++ Library. Then once I was happy with my routine framework I replaced the swap routine with my own code.

#include <string.h>

char* ReverseString(char* pstr)
{
    char* first = pstr;
    char* last = first + strlen(first) - 1;

    for(; first < last; ++first, --last)
    {
        *first = *first + *last;
        *last  = *first - *last;
        *first = *first - *last;
    }

    return pstr;
}

I will be looking at the space and time tradeoffs when I get a chance. But I would guess that reversing a string in place probably takes a few more CPU cycles depending on the length of the string. Of course you need to also factor in the memory constraints.

kennykerr@hotmail.com