I want to sort an array of struct using qsort by their name, But the output is not what I expected.
typedef struct node{
char name[64];
char ingredient[10][64];
}node;
int compare(const void *a, const void *b){
node *nodeA = (node *)a;
node *nodeB = (node *)b;
return strcmp(nodeA->name, nodeB->name);
}
int main(){
int num; scanf("%d", &num);
int sum[num];
node recipe[num];
//input
for(int i = 0; i < num; i++){
scanf("%s", recipe[i].name);
scanf("%d", &sum[i]);
for(int j = 0; j < sum[i]; j++){
scanf("%s", recipe[i].ingredient[j]);
}
}
//sort
qsort(recipe, num, sizeof(node), compare);
//print out to check
printf("\n");
for(int i = 0; i < num; i++){
printf("%s ", recipe[i].name);
for(int j = 0; j < sum[i]; j++){
printf("%s ", recipe[i].ingredient[j]);
}
printf("\n");
}
input as follows
5
cake 4 egg flour sugar butter
omelet 4 egg bacon ham butter
bread 1 flour
breed 0
breag 0
output as follows
bread flour
breag H??
breed ?i?
cake
omelet
expected output as follows
bread flour
breag
breed
cake egg flour sugar butter
omelet egg bacon ham butter
Moreover, what if I also want to sort the ingredient within each node as follows, how to achieve this?
//maybe I can do something like this
for(int i = 0; i < num; i++){
qsort(recipe[i].ingredient, num, sizeof(recipe[i].ingredient[0]), mycompare//to compare each ingredient);
}
expected output as follows
bread flour
breag
breed
cake butter egg flour sugar
omelet bacon butter egg ham
It is possible and it is common to write code this way.
But:
I will show down here a common way to write this --- and to reason about this --- using your code as input. I will write here as I code and at the end there will be a complete program, with output and comments along the way.
I will use no memory allocation and will not change sorting algorithm. It is just a toy just to show a way to write this kind of code. A way that usually works at the first run, as it worked here.
This can be a long post. No TL;DR
This is the basic data? No. And there is no need to name the
struct: let it anonymous. And the name is already showing something: anode? A node is part of something and your program has no representation for this something.As far as your model is from the real thing, more trouble you will have to operate on your data.
Want proof? Look at the array
sumand the valuenumin your code. If you need to write this to a file, a simple thing, the data is spread inside the code. Imagine an array of recipes and how in the world would you control that?Encapsulation is the way to go, as we see in all OOP languages. Encapsulation and OOP is much more a phylosophy than a technology, specially in
C.The data as a
thingThis is the start of the posted code:
And we have more and more problems:
Cas reading a number and declaring an array with the size of this number. There is a thing calledVLAtreated as extension by some compilers, and even if now, after decades usingC, it goes into the standard it is still problematic. Do the simple:nodewith the 10 ingredients with 64 bytes nameCwas written for this tasks.sumis the number of ingredients. It is not event a sum: it is a simple counter. Every recipe has up to 10 ingredients.node.ingredientis a vector of strings. Since the 70's we know thatmainprototype can beAnd for
mainthe command line arguments are... a vector ofgetcstrings. Just likechar ingredient [10][64]should be a vector withsumingredients. It should raise some flags since allCprogram works very well with this arguments formainscanfis a scanner, as the name suggests. And it was written to consume tabular data, like large tables with thousands of lines of similar data. It was not written to get user input. For this we havefgetcandfgetsfor example. If we choosescanfto read free-form input like from the keyboard we can expect much more work.scanfso it returns anintwith the total fields parsed from input. It is very naive not to test. If the user types awinstead of a2there goes your program to space.#defineand avoid magic numbers (like10or64in your code).mallocandfreeinstead of static things.So a possible way to go
Now we have encapsulation: we can operate on
Recipes. And it is the data after all. We wrote no line of code yet, but we can see it is easier. Or not?limitis here so make it easy to avoid overflow on the array.sizeis the obvious total of ingredients in each recipe.unsignedis here so we do not need to worry if someone enter -20 as thenumRecipesis a container for thenode. And it is way better than a modestnode[]because we can have metadata, things like limit and size, kept inside thestructFor a book of up to 40 collections of up to 40 recipes each. And we wrote no code yet.
And we can change the code of each one of this things without changing the others.
Recipecould beThis way each recipe is constructed at run time instead of having a fixed size. And the same principle could be applied to
RecipesandBookfor that matter. It is the usual way inC.never write interactive code
This is important: if you rely on typing recipe's fields each time you test your code things can be really hard. For 10 recipes of around 5 ingredients each, and with the program crashing in seconds at each run, life can be sad, i will cost you hours to do simple testing.
CC. It is a function that returns some uniqueRecipeat each call so you can test with 1 or 1,000 recipes at will.Then when the code is ok you can insert logic to get user input. Only then. And only if it is part of the request: parsing user input is hard and boring.
write the obvious stuff first
display one recipe
It is clear that we need to show a recipe on screen. So let us write this.
From the original code, 5 recipe's prints:
Not good. Better plan ahead:
It looks better. And it is better not to code a bunch of
printfeach time we need to print a recipe.Less than a dozen lines, and it will print as planned. Not good? Change in a single point. Another OOP thing, a.k.a. SRP, Single Responsibility Principle ;)
Why the second parameter? Well, we are testing and this means we can add a message to each call, embedded in the call itself. Handy. See the example below
test ahead
We need a
Recipe. Any one. From the original code, the first one:In
Cterms:So this code must run ok:
And it shows
Good for moral support. And less typing.
but we need more
Recipeand no user inputTime for a factory function:
rcp_factory()Not hard: at each call it returns a recipe with controlled random data. The argument limits the total ingredients of each
Recipe, limited to the obvious 10.At each call a full struct is copied. In general we would prefer to return a pointer to a new
Recipebut this is for demonstration only: only static data.Would it work? How to test? Just change the program above:
And it shows
Good for moral support.
but to sort we need a group of
RecipeAnd we already designed one: it is the
Recipesstruct. How to build one? Keeping the same principlercp_g_factory()and return a group of then.rcp_sort()to sort themrcp_g_show()since it is obvious that we want to display a collection before and after sort.creating the group
It is a matter of copy and paste from
rcp_factory(). Once again we will use onlystaticdata. Not smart. All data is being copied around at each call.Sure, we want to display it.
Adding a way to display the collection
Copying and pasting from
rcp_show()is a good first move since we do not want to waste timeSince we already know how to print one, this is just a matter of calling
rcp_show(). Thank you SRPWill this work? How to test such a thing?
Not bad huh? Works?
Good. But no surprise. It is just a loop over things already tested.
time to sort
RecipesSure, we want a function like
rcp_g_ sort()to encapsulate things. We know that we need to sort by some criteria, this criteria is a user-supplied function, so this is the time to pass it down:Not much to think: it is the same signature as
qsort.a problem: recipes are already sorted
Since we are using a factory function that returns names as "Recipe #n" they come already sorted. We can just invert the sort order by changing the compare function, but I will change the factory function anyway. SRP again.
Just one change: the
sprintfcall fromto
And now the recipes have a 3-letter random prefix to the number.
Will it work?
How to test such a complex thing?
And it shows
And it works. At first run. Good for moral support
what if we want to sort the ingredients by name?
It is the same stuff. The compare function is the same, the data is already a string --- the beauty of student code: little or no testing at all. So it is just a matter of calling
qsort. Sure it is naive to callqsortto sort such a small thing, but it is just a toy.It is just a matter of calling
qsort()how to test
rcp_sort()The same thing: let us use
That shows
It is time for me to stop.
Here is the final code. A few changes: I changed all factory functions to use the 3-letters prefix in the names, to better show the sorting process.
The complete code at this point
source
output
I did almost no testing.