Given a sequence of words, print all anagrams together

Question

Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”.

My idea is to sort individual words firstly. And then sort the array of words. In this way, the anagrams will be together. The following is my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct word_with_ind
{
    char* word;
    int ind;
}*word_with_ind_ptr;

int comp_char(const void* x, const void* y)
{
    char* c1 = (char*)x;
    char* c2 = (char*)y;

    return *c1 - *c2;
}

int comp_str(const void* x, const void* y)
{
    const word_with_ind_ptr w1 = (word_with_ind_ptr)x;
    const word_with_ind_ptr w2 = (word_with_ind_ptr)y;

    return strcmp(w1->word, w2->word);
}

void destroy(word_with_ind_ptr x, int size)
{
    for(int i = 0; i < size; ++i)
    {
        free(x[i].word);
    }
    free(x);
}

void print_anagrams_together(char* word[], int size)
{
    //make a copy of the original word array. And sort
    //the individual words
    word_with_ind_ptr x = (word_with_ind_ptr)malloc(sizeof(struct word_with_ind)*size);
    for(int i = 0; i < size; ++i)
    {
        x[i].ind = i;
        x[i].word = (char*)malloc(sizeof(char)*(strlen(word[i])+1));
        strcpy(x[i].word, word[i]);
        qsort(x[i].word, strlen(x[i].word), sizeof(char), comp_char);
    }

    //sort the array of words
    qsort(x, size, sizeof(struct word_with_ind), comp_str);

    //print result
    for(int i = 0; i < size; ++i)
    {
        printf("%s\n", word[x[i].ind]);
    }

    //free memory
    destroy(x, size);

}



int main()
{
    char* word[] = {"cat", "dog", "tac", "god", "act"};
    int size = sizeof(word)/sizeof(word[0]);
    print_anagrams_together(word, size);


    getchar();
    return 0;
}

Answer 1

FiHopZz, your concept seems fine. A few comments:

• in general, don't typedef pointers. It is confusing.

• your functions are not const-correct. In other words they cast const values to non-const values. The compiler will warn you of this if you enable warnings.

• I prefer pointers to be declared like this: char *p, not char* p. Consider char* a, b if in doubt (b is not a pointer but looks as if it should be).

• all local functions should be declared static

• print_anagrams_together should take a const word array and a size_t size (destroy should also take size_t not int)

• don't cast the return from malloc and note that malloc can fail.

• sizeof(char) is 1 by definition.

• use strdup to copy a word, not malloc. strdup can also fail.

• you took the length of the string twice, once in the malloc call and once in the qsort call.

• you also used strcpy on a string of which you already knew the length. memcpy is better (but remember to copy length+1).

• print_anagrams_together is arguably better broken into several sub-functions: copy_words, sort_words, print_words. Well done for making destroy as function. This would be renamed destroy_words for symmetry.

• arguably, copy_words and sort_words above could be combined. This is how your loop is written, with a word copied and then sorted in the same loop. This is clearly slightly more efficient, but in some way it does not appeal to me. For a start what do you call it? - copy_and_sort_words is rather ugly. But also a copy_words that just duplicates the array is easily tested; one that duplicates it and modifies it is not. These are perhaps not considerations that belong to a simple program such as this, but they are worth beaaring in mind for more complicated tasks.

• comments should be useful. Yours are mainly noise. If nothing needs saying, say nothing.

• the word array in main should be const

• the size in main should be const size_t, not int

• main should have a parameter list

Don't take my comments on breaking your print_anagrams_together into separate functions too seriously. It is not a big function and it is easily understood. Breaking it apart would probably make the program worse. However, for bigger or more complicated applications, having several loops in the same function in my opinion often indicates a lack of proper subdivision. Just my opinion though and others may differ.

Note also that although I say that malloc/strdup can fail, they are of course unlikely to fail in a small program like this. You might say that it is pointless testing for NULL pointers when you know they will probably be okay. The only thing you can sensibly do is to print an error and exit anyway (perror("malloc"); exit(EXIT_FAILURE);). But it is a good discipline always to check the return values of functions that can fail. Just do it.