• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 288
  • Last Modified:

tree index managing linked lists

I want to programm in C the following:
make a tree. Root is a node with "sub-nodes" "a","b",.."z".
Every letter has a pointer to a node of second level. i.e. a->(aa,ab,ac,..,az), b->(ba,bb,bc..) etc
Third level: aa->(aaa,aab,..,aaz) etc and fourth level has pointers to last names of a linked list of struct.
joh(of fourth level)-->johnson.
Thank u!!
0
xiromdim
Asked:
xiromdim
  • 5
  • 4
  • 4
  • +4
2 Solutions
 
AxterCommented:
Hi xiromdim,

Exactly what is your question?

David Maisonave (Axter)
Cheers!
0
 
xiromdimAuthor Commented:
I want to implement in C a linked list as struct node{int id; char lastname[30];}*head; and find a person in this specific list using the tree i discribed in the question, in order to find faster if a name exists...
0
 
AxterCommented:
Why did you accept my comment as an answer?

You should wait until you have a satisfactory answer, before awarding points.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
AxterCommented:
I"ve unaccepted the answer, so as to allow other experts to give you a satisfactory answer.
0
 
AxterCommented:
>>I want to implement in C a linked list as struct node{int id; char lastname[30];}*head; and find a person in this specific list using the tree i discribed in the question, in order to find faster if a name exists...

Notice that your comment doesn't have a question, and neither does your original post.

What parts of implementing this do you need help with?
Can you post your existing code?
0
 
xiromdimAuthor Commented:
the point is to find a person in a linked list as above struct node..., but to search more efficiently i want to use atree index as I mentioned above...(root, first level all the combinations of 2 leters, second level all the combination of 3 letters and the nodes of the second level(with 3 letters) have pointers to the nodes of the linked list. for example "bac" points to bacunin...
Thank u!
0
 
PaulCaswellCommented:
Hi xiromdim,


Essentially, you need to start with some code for an ordinary binary tree. Then, everywhere there is access to either 'left' or 'right', enhace it to handle an array of nodes.

Free source code for a binary tree implementation should be easy to find.

Are you allowed to use C++? It would be significantly easier to code in C++.

Paul
0
 
PaulCaswellCommented:
Hi xiromdim,

You are likely to 'eat' quite a lot of memory with this structure. What are your limitations in that area? Have you considered the idea of using a hash table? They are usually comparable in speed to extended trees such as this.

Paul
0
 
xiromdimAuthor Commented:
Thank you Paul! Well it's a homework! But I believe there will be a good solution anyhow. For example there will not be a node with aaa, since no name starts with aaa.
JIm..
0
 
PaulCaswellCommented:
Hi xiromdim,

Yes indeed but if you need to handle every combination of two letters at every node of the tree, each node will be at least 256k in size assuming a pointer is at least 4 * the size of a byte, which is conservative..

Paul
0
 
PaulCaswellCommented:
Hi PaulCaswell,

Oops! I just worked it out again it comes to about 2k but thats still a bit chunky. Were you specifically asked to use two characters per level? I should re-read the question.

Paul
0
 
jhshuklaCommented:
paul, i think this is allocate-on-demand. if no name starts with A then the root won't have an entry for A and so there can't be any children for A. an empty dictionary would use up 4x26 = 104bytes. add one name to get + 104 + 104 + space for linked list; and depending on variations in first three letters in the name, the space required could be HUGE or modestly large.
0
 
Infinity08Commented:
Any luck on starting, xiromdim ? Can you post what code you have at the moment ? If you don't know where or how to start, please let us know, and we'll be glad to help you get started.
0
 
xiromdimAuthor Commented:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct listnode{
    int id;
    char name[30];
};    
struct t_node{
    char letters[3];
    struct t_node *tree_ptr;
    struct listnode *names_ptr;
}treenode[26];    
int main(){
    int i;
    char c;
    char str[4];
    for(i=0;i<26;i++){//here I fill the root node
        c=97+i;//97 =ASCII for 'a'
        str[0]=c;
        str[1]='\0';
        strcpy(treenode[i].letters,str);
        treenode[i].tree_ptr=malloc(sizeof(t_node));
        treenode[i].names_ptr=NULL;
    }//end for
    system("pause");
    //with the same way i fill the root node I
    return 0;
}        
0
 
PaulCaswellCommented:
jhshukla,

>>paul, i think this is allocate-on-demand. ...
IMHO: Using linked lists for the array of pointers to subtrees would, in my opinion, be a mistake. The hit you would take to search the list for the letter you are looking for rather than just a straight table lookup would completely destroy the search optimality provided by a tree such as this. Its still doable with tables with current multimegabyte ram configurations.

Paul
0
 
cwwkieCommented:
struct t_node{
    char letters[3];
    struct t_node *tree_ptr;
    struct listnode *names_ptr;
}treenode[26];    

If this is one node (for example a), shouldn't you have 26 childnodes (for aa..az) instead of just one (tree_ptr)?
And look at the size of letters. 3 is probably not what you want.
0
 
fridomCommented:
very complicated structure with no good reason really. You want a fast string search for a whole name so what would three levels of trees give you?

Use a hash-table with a good hash code for strings and you lookup will be nearly instantaniously.

The other problem is you can have more then one johnson so you still would have to keep a list in the last leaf.

PaulCaswell has pointed it out very clearly. I just have seen it on second sight.

Regards
Friedrich
0
 
fridomCommented:
A small extra remark if you insist on you approache. What you are looking for is called n-ary trees. You can find about them e.g. here:
http://www.brpreiss.com/books/opus5/html/page257.html#SECTION0010200000000000000000

and an implementation free to use in C here:
http://developer.gnome.org/doc/API/2.0/glib/glib-N-ary-Trees.html

Regards
Friedrich


0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

  • 5
  • 4
  • 4
  • +4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now