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?

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;
}

---

@thi_spcst: No point in posting C++ code on a C forum ;)

Some link list and tree info here

>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. :D