C RSS C RSS

Trie's in C

Please support our C advertiser: Programming Forums - DaniWeb Sister Site
Thread Solved
1 2

•
•
Join Date: Oct 2008
Posts: 15
Reputation: thanatosys is an unknown quantity at this point 
Solved Threads: 1
thanatosys thanatosys is offline Offline
Newbie Poster

Trie's in C

 
0
  #1
Oct 26th, 2008
I have a homework assignment for a c class I am in currently, the assignment is to write a simple spell checker. I am having a bit of trouble understanding how to write a trie in c. A trie would be composed of nodes, which contain the following I believe:

1. char value (value of the node)
2. boolean isroot (is this the root node)
3. boolean endsword (is this the end of a word)
optionally
4. Node *nextnode ( a pointer to the next node if one exists).

What I am confused on, is how this should be written as an ADT in c. I have found a few samples online based in Java, but they tend to have too many features.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 15
Reputation: thanatosys is an unknown quantity at this point 
Solved Threads: 1
thanatosys thanatosys is offline Offline
Newbie Poster

Re: Trie's in C

 
0
  #2
Oct 26th, 2008
I would also like to add they need a 2nd pointer to the next sibling.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 15
Reputation: thanatosys is an unknown quantity at this point 
Solved Threads: 1
thanatosys thanatosys is offline Offline
Newbie Poster

Re: Trie's in C

 
0
  #3
Oct 26th, 2008
So I have been working a bit further but seem to have something wrong in my code. The header file for each node is this "node.h"
c Syntax (Toggle Plain Text) 
  1. #include <stdbool.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <ctype.h>
  6. #include <stdbool.h>
  7.  
  8. typedef struct node { 
  9. 	char value;
  10. 	bool isroot;
  11. 	bool isend;
  12. 	struct node* sibling;
  13. 	struct node* child; 
  14. }

The code for my test of the node structure is this "node.c"
c Syntax (Toggle Plain Text) 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5. #include <stdbool.h>
  6. #include "node.h"
  7.  
  8. int main(void){
  9. 	return 0;
  10. }

The makefile reads as such:
C Syntax (Toggle Plain Text) 
  1. CC=gcc
  2. CFLAGS=-Wall -g
  3.  
  4. eread:	node.o
  5. 	$(CC) $(CFLAGS) -o $@ node.o
  6.  
  7. node.c: node.h

And finally the error message is this
C Syntax (Toggle Plain Text) 
  1. $ make
  2. gcc -Wall -g   -c -o node.o node.c
  3. node.c:6: error: syntax error at end of input
  4. make: *** [node.o] Error 1

Any ideas what is going on here?
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2005
Posts: 5,850
Reputation: Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute Salem has a reputation beyond repute 
Solved Threads: 749
Team Colleague
Salem's Avatar
Salem Salem is offline Offline
Void main'ers are DOOMed

Re: Trie's in C

 
0
  #4
Oct 26th, 2008
Missing ; at end of typedef.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 15
Reputation: thanatosys is an unknown quantity at this point 
Solved Threads: 1
thanatosys thanatosys is offline Offline
Newbie Poster

Re: Trie's in C

 
0
  #5
Oct 26th, 2008
so new header file is this:
c Syntax (Toggle Plain Text) 
  1. #include <stdbool.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5. #include <ctype.h>
  6. #include <stdbool.h>
  7.  
  8. typedef; struct node { 
  9. 	char value;
  10. 	bool isroot;
  11. 	bool isend;
  12. 	struct node* sibling;
  13. 	struct node* child; 
  14. }

And the error message then becomes:
C Syntax (Toggle Plain Text) 
  1. $ make
  2. gcc -Wall -g   -c -o node.o node.c
  3. In file included from node.c:6:
  4. node.h:8: warning: useless storage class specifier in empty declaration
  5. node.h:8: warning: empty declaration
  6. node.c:8: error: two or more data types in declaration specifiers
  7. node.c:8: warning: return type of ‘main’ is not ‘int’
  8. node.c: In function ‘main’:
  9. node.c:9: error: incompatible types in return
  10. node.c:10: warning: control reaches end of non-void function
  11. make: *** [node.o] Error 1

The warnings are not as troubling to me as the errors, though I am pretty sure that whatever is causing them is related.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 273
Reputation: Sci@phy will become famous soon enough Sci@phy will become famous soon enough 
Solved Threads: 42
Sci@phy's Avatar
Sci@phy Sci@phy is offline Offline
Posting Whiz in Training

Re: Trie's in C

 
0
  #6
Oct 26th, 2008
Funny:
c Syntax (Toggle Plain Text) 
  1. typedef struct node { 
  2. 	char value;
  3. 	bool isroot;
  4. 	bool isend;
  5. 	struct node* sibling;
  6. 	struct node* child; 
  7. }; //<== if semicolon goes here, it's much more reasonable
Last edited by Sci@phy; Oct 26th, 2008 at 7:34 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2006
Posts: 2,035
Reputation: Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of 
Solved Threads: 177
Aia's Avatar
Aia Aia is offline Offline
Postaholic

Re: Trie's in C

 
0
  #7
Oct 26th, 2008 
typedef struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
};
He meant there.
Reply With Quote Quick reply to this message  
•
•
Join Date: Oct 2008
Posts: 15
Reputation: thanatosys is an unknown quantity at this point 
Solved Threads: 1
thanatosys thanatosys is offline Offline
Newbie Poster

Re: Trie's in C

 
0
  #8
Oct 26th, 2008
Wow... now I feel... dumb . Anyway brings me to a final warning
C Syntax (Toggle Plain Text) 
  1. $ make
  2. gcc -Wall -g   -c -o node.o node.c
  3. In file included from node.c:6:
  4. node.h:14: warning: useless storage class specifier in empty declaration
  5. gcc -Wall -g -o eread node.o

What exactly does this mean?
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2008
Posts: 273
Reputation: Sci@phy will become famous soon enough Sci@phy will become famous soon enough 
Solved Threads: 42
Sci@phy's Avatar
Sci@phy Sci@phy is offline Offline
Posting Whiz in Training

Re: Trie's in C

 
0
  #9
Oct 26th, 2008
Do you know why do you use typedef?
It's syntax should be:
c Syntax (Toggle Plain Text) 
  1. typedef some huge type A_DEF;

And the code you wrote has no use from typedef since you haven't specified name that will replace that struct.
Reply With Quote Quick reply to this message  
•
•
Join Date: Dec 2006
Posts: 2,035
Reputation: Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of Aia has much to be proud of 
Solved Threads: 177
Aia's Avatar
Aia Aia is offline Offline
Postaholic

Re: Trie's in C

 
0
  #10
Oct 26th, 2008
>What exactly does this mean?
typedef struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
} aliasname;
Where aliasname is any identifier you want to substitute struct node for.
Reply With Quote Quick reply to this message  
Reply
1 2

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C Forum
Thread Tools Search this Thread



#include * ansi append array arrays asterisks binarysearch calculate changingto char character cm convert copyimagefile cprogramme creafecopyofanytypeoffileinc database dynamic execv feet fflush fgets file fork forloop framework function getlasterror givemetehcodez grade gtkwinlinux hacking hardware histogram inches include incrementoperators input intmain() iso kernel keyboard km license linked linkedlist linux list lists locate logical_drives looping loopinsideloop. lowest matrix microsoft motherboard mqqueue number oddnumber odf opendocumentformat opensource overwrite owf pattern pdf performance pointer posix probleminc process program programming radix recursion recv recvblocked research reversing scanf scripting segmentationfault sequential socket socketprograming standard string systemcall testing threads turboc unix user variable voidmain() wab whythiscodecausesegmentationfault windowsapi
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC