Ad:

C Discussion Thread
Marked Solved
Views: 5533

Page 1
2
Next

You are currently viewing page 1 of this multi-page discussion thread

Oct 26th, 2008

Trie's in C

Expand Post »

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.

Similar Threads

VB: Connect to Access database via ODBC datasource name in Visual Basic 4 / 5 / 6
trie in C++
Trie/Tree addWord() method in Computer Science
creating a Trie in Java
Missing Thumbnails in Web Browsers

thanatosys

Reputation Points: 10

Solved Threads: 1

Newbie Poster

Offline

15 posts
since Oct 2008

Permalink

Oct 26th, 2008

Re: Trie's in C

I would also like to add they need a 2nd pointer to the next sibling.

thanatosys

Reputation Points: 10

Solved Threads: 1

Newbie Poster

Offline

15 posts
since Oct 2008

Permalink

Oct 26th, 2008

Re: Trie's in C

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)
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
 
typedef struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
}
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

typedef struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
}

The code for my test of the node structure is this "node.c"

c Syntax (Toggle Plain Text)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include "node.h"
 
int main(void){
	return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
#include "node.h"

int main(void){
	return 0;
}

The makefile reads as such:

C Syntax (Toggle Plain Text)
CC=gcc
CFLAGS=-Wall -g
 
eread:	node.o
	$(CC) $(CFLAGS) -o $@ node.o
 
node.c: node.h
CC=gcc
CFLAGS=-Wall -g

eread:	node.o
	$(CC) $(CFLAGS) -o $@ node.o

node.c: node.h

And finally the error message is this

C Syntax (Toggle Plain Text)
$ make
gcc -Wall -g   -c -o node.o node.c
node.c:6: error: syntax error at end of input
make: *** [node.o] Error 1
$ make
gcc -Wall -g   -c -o node.o node.c
node.c:6: error: syntax error at end of input
make: *** [node.o] Error 1

Any ideas what is going on here?

thanatosys

Reputation Points: 10

Solved Threads: 1

Newbie Poster

Offline

15 posts
since Oct 2008

Permalink

Oct 26th, 2008

Re: Trie's in C

Missing ; at end of typedef.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Oct 26th, 2008

Re: Trie's in C

so new header file is this:

c Syntax (Toggle Plain Text)
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>
 
typedef; struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
}
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

typedef; struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
}

And the error message then becomes:

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

thanatosys

Reputation Points: 10

Solved Threads: 1

Newbie Poster

Offline

15 posts
since Oct 2008

Permalink

Oct 26th, 2008

Re: Trie's in C

Funny:

c Syntax (Toggle Plain Text)
typedef struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
}; //<== if semicolon goes here, it's much more reasonable
typedef struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
}; //<== if semicolon goes here, it's much more reasonable

Last edited by Sci@phy; Oct 26th, 2008 at 7:34 pm.

Sci@phy

Reputation Points: 110

Solved Threads: 43

Posting Whiz in Training

Offline

279 posts
since Sep 2008

Permalink

Oct 26th, 2008

Re: Trie's in C

(Toggle Plain Text)

typedef struct node { 
	char value;
	bool isroot;
	bool isend;
	struct node* sibling;
	struct node* child; 
};

He meant there.

Aia

Reputation Points: 2224

Solved Threads: 218

Nearly a Posting Maven

Offline

2,304 posts
since Dec 2006

Permalink

Oct 26th, 2008

Re: Trie's in C

Wow... now I feel... dumb

. Anyway brings me to a final warning

C Syntax (Toggle Plain Text)
$ make
gcc -Wall -g   -c -o node.o node.c
In file included from node.c:6:
node.h:14: warning: useless storage class specifier in empty declaration
gcc -Wall -g -o eread node.o
$ make
gcc -Wall -g   -c -o node.o node.c
In file included from node.c:6:
node.h:14: warning: useless storage class specifier in empty declaration
gcc -Wall -g -o eread node.o

What exactly does this mean?

thanatosys

Reputation Points: 10

Solved Threads: 1

Newbie Poster

Offline

15 posts
since Oct 2008

Permalink

Oct 26th, 2008

Re: Trie's in C

Do you know why do you use typedef?
It's syntax should be:

c Syntax (Toggle Plain Text)

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.

Sci@phy

Reputation Points: 110

Solved Threads: 43

Posting Whiz in Training

Offline

279 posts
since Sep 2008

Permalink

Oct 26th, 2008

Re: Trie's in C

>What exactly does this mean?

(Toggle Plain Text)

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.

Aia

Reputation Points: 2224

Solved Threads: 218

Nearly a Posting Maven

Offline

2,304 posts
since Dec 2006

Page 1
2
Next

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C Forum Timeline: Duplicates project :

Next Thread in C Forum Timeline: need some help

DaniWeb Message

Cancel Changes

User Name
Password