Thread: Data structure implementation

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    147

    Data structure implementation

    I am doing a small test program by extracting data out of a notepad which consists of results or performance data of students throughout their duration at a particular institute, for example. After obtaining the data, I will use that data to display a graph. Nevermind the graph, i mainly need ideas on how i could implement some data structures.

    I just want to try out how a binary search tree could work, or how i could implement stacks and queues.

    Can anybody give me suggestions as to how I can implement these concepts?
    Only by the cross are you saved...

  2. #2
    thi_spcst
    Guest
    Well there's plenty of tutorials out there already. Or switch to C++'s STL? It has strings, lists, stacks, deques, vectors, maps, multimaps, sets, multisets, bitsets, etc. And they're templated, meaning you can use them with any data type you wish to use. You can even build little containers out of them, like this linked list of vectors of strings:

    #include <string>
    #include <list>
    #include <vector>
    Code:
    int main() {
    typedef vector<string> words;
    typedef list< words > lines;
    typedef words::iterator witerator;
    typedef lines::iterator literator;
    
    lines xData;
    literator it = xData.begin(), nd = xData.end();
    for( ; it != end; ++it)
     for(witerator wit = *it, wnd = (*it).end(); wit != wnd; ++wit)
      cout << *wit << endl;
    
    return 0;
    }

  3. #3
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    @thi_spcst: No point in posting C++ code on a C forum

    Some link list and tree info here
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Can anybody give me suggestions as to how I can implement these concepts?
    Your best bet would be to pick up a good book on data structures. But since you asked about some of the easier data structures....Stacks and queues are very easy using a linked list setup as the base:
    Code:
    /* Simple stack */
    typedef struct node *link;
    
    struct node
    {
        int  data;
        link next;
    };
    
    int empty ( link top )
    {
        return top == NULL;
    }
    
    link push ( link top, link item )
    {
        item->next = top;
        return item;
    }
    
    link pop ( link top, link *item )
    {
        *item = top;
        return top->next;
    }
    For queues the same basic principle applies. The only difference is that removing is slightly more complicated:
    Code:
    /* Simple queue */
    typedef struct node *link;
    
    struct node
    {
        int  data;
        link next;
    };
    
    int empty ( link top )
    {
        return top == NULL;
    }
    
    link enqueue ( link top, link item )
    {
        item->next = top;
        return item;
    }
    
    link dequeue ( link top, link *item )
    {
        if ( top->next == NULL ) {
            *item = top;
            top = NULL;
        }
        else {
            link it = top;
    
            while ( it->next != NULL && it->next->next != NULL )
                it = it->next;
            
            *item = it->next;
            it->next = NULL;
        }
    
        return top;
    }
    Binary search trees have far too many variations to describe all of them, but if you look in K&R2 Section 6.5, pp. 139 you'll find a basic binary search tree implementation. If you don't have K&R2...well, you should.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Bitmasking Problem
    By mike_g in forum C++ Programming
    Replies: 13
    Last Post: 11-08-2007, 12:24 AM
  2. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  3. Dynamic data members?
    By confusalot in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2005, 11:15 AM
  4. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM
  5. Dynamic Data Structure -- Which one is better?
    By Yin in forum C++ Programming
    Replies: 0
    Last Post: 04-10-2002, 11:38 PM