Returning an array of structs without pointers in C

Question

I have been working my way through Kochan's "Programming in C" 3rd Edition on my own to get ready for grad school next year, and I am stuck for the first time. I am a chapter away from pointers, yet the exercise at the end of this most recent chapter on character strings has a problem that my own research seems to indicate can only be solved by using pointers.

The question has to do with a data structure entry:

struct entry {
    char word[15];
    char definition[50];
};

We create an array of entries:

struct entry dictionary[10] = 
{{"aardvark", "a burrowing African mammal"},
 {"abyss", "a bottomless pit"},
 {"addle", "to become confused"},
 {"aerie", "a high nest"},
 {"ajar", "partially opened"},
 {"acumen", "mentally sharp; keen"},
 {"affix", "to append; attach"},
 {"agar", "a jelly made from seaweed"},
 {"ahoy", "a nautical call of greeting"},
 {"aigrette", "an ornamental cluster of feathers"}};

The prompt reads: "Write a function called dictionary_sort that sorts a dictionary, as defined [above], into alphabetical order."

I know there are subtleties to structures and arrays in relation to functions and how functions can take them as arguments or give them back as returned values. The only way that seemed to make sense to me was returning a struct, or specifically an array of structs, but I do not think I applying it correctly here:

struct entry dictionary_sort(struct entry dictionary)

In total, my current version of the program is as follows:

#include <stdio.h>
#include <stdbool.h>

struct entry {
    char word[15];
    char definition[50];
};

// Function to compare two character strings

int compare_strings(const char s1[], const char s2[])
{
    int i = 0, answer; 

    while (s1[i] == s2[i] && s1[i] != '\0' && s2[i] != '\0')
        i++;

    if (s1[i] < s2[i])
        answer = -1; // s1 < s2
    else if (s1[i] == s2[i])
        answer = 0; // s1 == s2
    else
        answer = 1; // s1 > s2

    return answer;
}

// Function to sort a dictionary structure

struct entry dictionary_sort(struct entry dictionary[])
{
    int dictionary_length = sizeof(dictionary) / sizeof(dictionary[0]);
    int i, j, minimum;
    struct entry temp;

    for (i = 0; i < dictionary_length; i++) {
        minimum = i;
        for (j = i + 1; j < dictionary_length; j++) {
            if (compare_strings(dictionary[j].word, 
                                dictionary[minimum].definition) == -1)
                minimum = j;
        }
        temp = dictionary[minimum];
        dictionary[minimum] = dictionary[i];
        dictionary[i] = dictionary[minimum];
    }

    return dictionary;
}

int main(void)
{
    struct entry dictionary[10] =
    {{"aardvark", "a burrowing African mammal"},
     {"abyss", "a bottomless pit"},
     {"addle", "to become confused"},
     {"aerie", "a high nest"},
     {"ajar", "partially opened"},
     {"acumen", "mentally sharp; keen"},
     {"affix", "to append; attach"},
     {"agar", "a jelly made from seaweed"},
     {"ahoy", "a nautical call of greeting"},
     {"aigrette", "an ornamental cluster of feathers"}};
    int i, dictionary_length = sizeof(dictionary) / sizeof(dictionary[0]);

    dictionary = dictionary_sort(dictionary);

    for (i = 0; i < dictionary_length; i++)
        printf("%s - %s.\n", dictionary[i].word, dictionary[i].definition);

    return 0;
}

The string comparison function behaves as expected since it is only returning an integer. I am really at a loss as to how to have the desired functionality without knowledge of pointers. There are enough examples with pointers to look up, but I am curious what fundamental principle I am missing here because I feel as though everything else in the book has come very naturally to me.

Thank you in advance!

Structures take up a fixed amount of memory. If they are next to each other contiguously in memory, they form an array. You can get to the nth structure in this array (the first n being 0, located at the first byte of the array) by n * k, where k is the size of the struct. That's all a[i] means anyway. — Robert Harvey
– Robert Harvey, Commented Apr 22, 2013 at 21:03
@RobertHarvey, thank you for your reply. Is the only way to make a function then that returns one element of the arranged struct array at a time? It just seems inefficient to have to rearrange it for each call. I know this is a contrived example, but it seems like he is asking for a function that acts on the whole array at once. — user1032719
– user1032719, Commented Apr 22, 2013 at 21:05
Well, when you say a[i], you are referring to that particular structure in the array. What you do with it at that point is entirely up to you. You can read it, write it, replace it with a different struct, etc. You can modify it in place. — Robert Harvey
– Robert Harvey, Commented Apr 22, 2013 at 21:07

score 4 · Accepted Answer · 2013-04-22 21:13:39Z

4

You do not have to return anything at all, you don't even need explicit pointers, none of that. Sort in-place, and don't reinvent the wheel: use strcmp() and qsort() (live demo here):

struct entry dictionary[] = {
    { "def", "second entry" },
    { "abc", "first entry" },
    { "ghi", "third entry" },
    { "mno", "fifth entry" },
    { "jkl", "fourth entry" }
};

int compare_entry(const void *l, const void *r)
{
    const struct entry *ll = l;
    const struct entry *rr = r;
    return strcmp(ll->word, rr->word);
}

#define COUNT(x) (sizeof(x) / sizeof(x[0]))

qsort(dictionary, COUNT(dictionary), sizeof(dictionary[0]), compare_entry);

edited Apr 22, 2013 at 21:13

answered Apr 22, 2013 at 21:06

user529758

Sign up to request clarification or add additional context in comments.

11 Comments

user1032719 Over a year ago

That will certainly work. Thank you. I think the spirit of the exercise/book, though, is to avoid using library functions as much as possible.

user529758 Over a year ago

@thomasjames That's a no-brainer. They're there because they're well-implemented, tested and performant. Do have an idea about how they work, but don't roll your own ones. Being able to use the standard library fluently is a core competence in C. See, they've reduced your code size by about 70% and improved readability by IDK-how-many-thousands-%.

Rüppell's Vulture Over a year ago

@thomasjames While we are at it printf() is no more innocent a library function than strcmp() or qsort().All are standard C library functions.It's just that some are used much more frequently than others.

user1032719 Over a year ago

@H2CO3, if I ever get to the point where I do larger projects, then yes. In this one the author specifically asked that we use a custom string comparison function from another exercise, though. That said, in general, I absolutely would agree. I think my inner OCD is coming out here.

user1032719 Over a year ago

@SheerFish, it is just that the book is sequential, and qsort hasn't been covered yet. I know I am being a bit ridiculous, and I apologize.

|

user1032719 · Accepted Answer · 2013-04-24 19:11:09Z

While not perfect and still requiring the explicit definition of pointers, this answer is within the scope of the problem and the book by not just calling libraries.

#include <stdio.h>
#include <stdbool.h>

struct entry {
    char word[15];
    char definition[50];
};

// Function to compare two character strings

int compare_strings(const char s1[], const char s2[])
{
    int i = 0, answer; 

    while (s1[i] == s2[i] && s1[i] != '\0' && s2[i] != '\0')
        i++;

    if (s1[i] < s2[i])
        answer = -1; // s1 < s2
    else if (s1[i] == s2[i])
        answer = 0; // s1 == s2
    else
        answer = 1; // s1 > s2

    return answer;
}

// Function to sort a dictionary structure

void dictionary_sort(struct entry *dictionary, int dictionary_length)
{
    int i, j, minimum;
    struct entry temp;

    for (i = 0; i < dictionary_length - 1; i++) {
        minimum = i;
        for (j = i + 1; j < dictionary_length; j++) {
            if (compare_strings(dictionary[j].word, 
                                dictionary[minimum].word) == -1)
                minimum = j;
        }
        temp = dictionary[minimum];
        dictionary[minimum] = dictionary[i];
        dictionary[i] = temp;
    }
}

// Prints the dictionary in its current state

void print_dictionary(struct entry *dictionary, int dictionary_length)
{
    int i;

    for (i = 0; i < dictionary_length; i++) {
        printf("%s - %s.\n", dictionary[i].word, dictionary[i].definition);
    }
}

// Demostrates the dictionary_sort function

int main(void)
{
    struct entry dictionary[10] =
    {{"aardvark", "a burrowing African mammal"},
     {"abyss", "a bottomless pit"},
     {"addle", "to become confused"},
     {"aerie", "a high nest"},
     {"ajar", "partially opened"},
     {"acumen", "mentally sharp; keen"},
     {"affix", "to append; attach"},
     {"agar", "a jelly made from seaweed"},
     {"ahoy", "a nautical call of greeting"},
     {"aigrette", "an ornamental cluster of feathers"}};

    int i, dictionary_length = sizeof(dictionary) / sizeof(dictionary[0]);

    print_dictionary(&dictionary, dictionary_length);
    printf("\nSorting...\n\n");
    dictionary_sort(&dictionary, dictionary_length);
    print_dictionary(&dictionary, dictionary_length);
    printf("\n");

    return 0;
}

Olaf Dietsche · Accepted Answer · 2013-04-22 21:10:00Z

0

When you declare a function parameter with [], you already use pointers. The function definition

int compare_strings(const char s1[], const char s2[])

is functionally the same as

int compare_strings(const char *s1, const char *s2)

Same with struct entry dictionary_sort(struct entry dictionary[]).

Since you get a pointer to struct entry as parameter dictionary, return dictionary returns a pointer to struct entry as well.

And all changes you make to dictionary are already visible outside, because you modify the array itself and not some local array.

edited Apr 22, 2013 at 21:10

answered Apr 22, 2013 at 21:04

Olaf Dietsche

74.4k9 gold badges113 silver badges214 bronze badges

2 Comments

user1032719 Over a year ago

so if I made it a function void dictionary_sort(struct entry dictionary[]) it would effect dictionary globally back in main without having to return anything?

Olaf Dietsche Over a year ago

@thomasjames It already does so. The return type doesn't change anything. In your case though, it doesn't compile, because the return types conflict struct entry vs struct entry*.

Rüppell's Vulture · Accepted Answer · 2013-04-22 21:11:19Z

0

A statement like "Returning an array of structs without pointers in C" is a paradox in C because the only way to pass or return an array in C is through pointers.Even though it may seem that in something like char *foo(char arr_demo[]){} an array is being passed, essentially it's a pointer being passed as it reduces to char *foo(char *arr_demo){}.

answered Apr 22, 2013 at 21:11

Rüppell's Vulture

3,6638 gold badges37 silver badges49 bronze badges

1 Comment

hyde Over a year ago

Well, it's certainly possible to return a fixed size (known at compile time) array by wrapping it in a struct, so returning a pointer is not the only way. I'd call this passing/returning an array, because that's what happens, even if that array is inside a struct. It's just a very bad approach usually, so it does not get used much.

Collectives™ on Stack Overflow

Returning an array of structs without pointers in C

4 Answers 4

11 Comments

Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

11 Comments

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related