Hi /prog/. I'm learning C, and wrote a program that takes a bunch of numbers and sorts them using a binary tree. I know it's not an efficient way to sort, I'm just learning binary trees. Could you look over it real quick and just give me some comments, like if there was something you would have done differently or something that's just stupid. Thanks a lot.
#include <stdio.h>
#include <stdlib.h>
struct node_ {
int value;
struct node_ *left, *right;
};
int main(int argc, char *argv[])
{
puts("enter values, 0 to stop");
int next;
scanf("%d", &next);
node *root = 0;
while (next) {
root = insert(root, next);
scanf("%d", &next);
}
print(root);
puts("");
return 0;
}
Name:
Anonymous2010-05-24 23:49
Your binary tree is dropping values. It's turning your collection into a set, which is probably incorrect.
Also, you should be using four spaces per indentation level, not eight.
Name:
Anonymous2010-05-25 0:13
Your binary tree is dropping values. It's turning your collection into a set, which is probably incorrect.
That was on purpose, not really sure why I did that. Also, you should be using four spaces per indentation level, not eight.
I used tabs in vim, apparently copying and pasting from an xterm converts to spaces. I haven't set my tab size to 4, which I guess I should do though.
Thanks for the comments, so the way I did this wasn't completely stupid or anything like that, right?
every time, of course. >>4's point is a stylistic choice, because either way will almost certainly generate the same assembly, but K&R indentation must be taken seriously.
>>5 I would have folded the struct definition and typedef into one thing
It took me 10 years to learn why that's a bad thing to do. OP doesn't have it much better though.
>>20
>>his hypothesis
>>Could you look over it real quick and just give me some comments
Name:
Anonymous2010-05-25 19:58
computer science is as much about mathematics, as astronomy is about telescopes
Name:
Anonymous2010-05-25 20:12
>>23
when parent is NULL, your insert returns a pointer to a node with left and right containing unspecified values (they can be anything). you probably want them to be set to NULL instead, like >>11 does.
Name:
Anonymous2010-05-25 20:35
>>23
Logic errors aside: no reason to typedef the struct, use sizeof expr instead of sizeof (type) when possible, check malloc (at least print something + exit), scanf is usually bad for untrusted input
Name:
Anonymous2010-05-25 20:51
>>28
the typedef makes the code shorter, and is good if the tree is intended to be an opaque type only used through an api, which is the right way to do something like this. sizeof(expr) just gets turned into sizeof(typeof(expr)) anyway. scanf is used safely here (bad input can't cause anything worse than bad output). good point about checking malloc, tho.
Name:
Anonymous2010-05-25 21:34
>>29
An opaque API can be done with struct node; in the header. I find typedefs like this to be less clear than just using the normal type name. I also find using expressions for sizeof (when possible) nicer than embedding the type name. When you use an expression, allocations usually look like p = malloc(n * sizeof *p);. No type name needed. There's no right answer for either of these issues though, both are a matter of style. Just thought I'd give some food for thought.
scanf is OK for example code, but it actually causes undefined behaviour if the input item for the %d specifier is out of int range (eg sscanf("9999999999999999", "%d", &n);). A combination of fgets and the strto* functions works well.
>>30 When you use an expression, allocations usually look like p = malloc(n * sizeof *p);.
Are you trolling?
Okay, okay, assuming you're not: I really hate that. When do you ever not know the type you're allocating? OTOH, if anyone else was reading your code they might not know (perhaps you're the type to write functions as long as your arm), and the call to malloc wouldn't help clear that up. There's no point in removing information like that.
I take the opposite approach: p = malloc(sizeof(Tp[n]));. I greatly prefer this because the syntax used parallels the stack allocation syntax, and the semantics are obvious when adding constants, factors, etc. void.h needs #define new(x) malloc(sizeof(x)).
gtfo my prague. Shitchan converts tabs inside of [code] and (I think) [m] tags into 8 spaces. You should know this.
Name:
Anonymous2010-05-25 22:54
>>34
In principle it isn't. In practice you'll probably be fine in this particular case, but >>27 is right and it's a really to set things explicitly to NULL.
>>35
Still doesn't change the fact he shouldn't be using literal tabs at all, but four spaces.
Name:
Anonymous2010-05-25 23:01
Here's version 2, did I fix everything mentioned? I did change the behavior to keep duplicate values. Also, I added some basic malloc checking, but I'm not worried about scanf for this.
int main(int argc, char *argv[])
{
puts("enter values, 0 to stop");
int next;
scanf("%d", &next);
node *root = 0;
while (next) {
root = insert(root, next);
scanf("%d", &next);
}
print(root);
puts("");
return 0;
}
Name:
Anonymous2010-05-25 23:04
Alright, I wasn't sure about that. So when you allocate memory it's not guaranteed to be zeroed, right?
right. if you do (node){ .value = newval }, the rest of the struct members are guaranteed to be zeroed.
but i'm pretty sure this should work without a memcpy: node *n = malloc(sizeof(n));
*n = (node){ .value = newval };
Name:
Anonymous2010-05-25 23:14
>>37
one return is a lot better than two: node *insert(node *parent, int newval)
{
if(!parent)
{
parent = malloc(sizeof(node));
if(!parent)
{
fputs("malloc failed", stderr); /* errors go to stderr */
exit(1); /* no point continuing if we're out of memory */
}
*parent = (node){ .value = newval; };
}
else if(newval <= parent->value)
parent->left = insert(parent->left, newval);
else
parent->right = insert(parent->right, newval);
return parent;
}
and there's print, which it almost looks like you're doing wrong on purpose: void print(node *top)
{
if(top)
{
print(top->left);
printf("%d ", top->value);
print(top->right);
}
}
Name:
Anonymous2010-05-25 23:52
>>33
Not trolling. I always know the type, but I don't see a point in adding information like that.
>>40
I already made my counter argument to that. There's also the niggling issue with void and converted pointers. Niggling because it's rarely practical, but the fact is your form does fail to cover valid possibilities, not all of which are bad form.
Besides, the information is there, only indirectly. The problem is that by using the typed variable instead of the type itself hides that information from the person reading the code. It should be obvious this is bad: the cost of being explicit here is virtually nothing. Will no one else ever read your code? And to take the extreme: it's not like allocating to the stack using a typed variable in place of the type itself is a good idea, but you can totally do it.
Name:
Anonymous2010-05-26 3:08
>>22
I just copied the functionality he had but wrote it with cleaner if/else statements and with the returns.