Looking for a few examples..

This is a discussion on Looking for a few examples.. within the C++ Programming forums, part of the General Programming Boards category; Hello, I'm looking for easy-to-understand C++ codes with clear logic for : - Double Linked List - Queue - a ...

  1. #1
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472

    Looking for a few examples..

    Hello,

    I'm looking for easy-to-understand C++ codes with clear logic for :
    - Double Linked List
    - Queue
    - a program that validates expressions. for example :
    valid : ([(a+b)+c]) + x
    invalid : ([(a+b+c]) + x


    I already searched for it, but i wasn't lucky. No i'm not asking for someone to do it for me as i already can do it on my own, but i'm looking for simple and clear ones that are already available preferably with an explanation (like prelude's linked list).


    any help is much appreciated
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

  2. #2
    Magically delicious LuckY's Avatar
    Join Date
    Oct 2001
    Posts
    856
    Here's an old Doubly-Linked List class I wrote for a class nigh on 3 years back. I haven't really provided it the much needed "old once over" for which it desperately aches, for I leave that chore to act as your method of coherency allocation.
    Code:
    #ifndef _DOUBLYLINKEDLIST_H_
    #define _DOUBLYLINKEDLIST_H_
    
    #include <string>
    using namespace std;
    
    class ListException {
      string _msg;
    
    public:
      ListException(const char *msg=NULL) {
        _msg = (*msg == NULL) ? "Unknown list error" : msg;
      }
    
      const string& getMessage() const { return _msg; }
    };
    
    template <typename T>
    class DoublyLinkedList {
      template <typename T>
      struct DoubleNode {
        T     data;
        DoubleNode  *next;
        DoubleNode  *prev;
        DoubleNode() : next(NULL), prev(NULL), data() { }
      };
    
      typedef DoubleNode<T> Node;
    
      Node          *_head;
      Node          *_tail;
      Node          *_cur;
      int           _length;
      
      void*         locateItem(const T &item, int *counter);  
      
    public:
      DoublyLinkedList();
      virtual ~DoublyLinkedList();
      
      bool          isFull() const;
      bool          isEmpty() const;
      
      void          clear();
    
      void          insertItem(const T &item);
      bool          findItem(const T &item);
      void          deleteItem(const T &item);
      
      void          resetList();
      T             getNextItem();  
    };
    
    //////////////////////////////////////////////////////////
    // Implementation
    
    template <typename T>
    DoublyLinkedList<T>::DoublyLinkedList()
    : _head(NULL), _tail(NULL), _cur(NULL), _length(0)
    {
    }
    
    template <typename T>
    DoublyLinkedList<T>::~DoublyLinkedList() {
      clear();
    }
    
    ///////////////////////////////////////////////////////////////
    // name:    locateItem
    // params:  item - the item to locate
    //
    // desc:    searches list for item
    // returns: pointer to node where item was located or NULL
    //
    template <typename T>
    void* DoublyLinkedList<T>::locateItem(const T &item) {
      //work our way in from both sides
      Node *left = _head;
      Node *right = _tail;
    
      int leftIndex = 0;
      int rightIndex = _length - 1;
    
      while (leftIndex <= rightIndex) {
        if (left->data == item)
          return left;
        if (right->data == item)
          return right;
    
        ++leftIndex;
        --rightIndex;
        left = left->next;
        right = right->prev;    
      }
    
      return NULL;
    }
    
    /////////////////////////////////////////////
    // name:    isFull
    // params:  none
    //
    // desc:    checks if memory is available for
    //          dynamic allocation of an item
    // returns: true if full. false otherwise.
    //
    template <typename T>
    bool DoublyLinkedList<T>::isFull() const {
      try {//check if room exists for another node
        Node *node = new Node;
        delete node;
        return false;
      }
      catch (bad_alloc exc) {
        return true;
      }
    }
    
    ///////////////////////////////////////////
    // name:    isEmpty
    // params:  none
    //
    // desc:    checks if list is empty
    // returns: true if empty. false otherwise.
    //
    template <typename T>
    bool DoublyLinkedList<T>::isEmpty() const {
      return _head == NULL;
    }
    
    //////////////////////////////////////////
    // name:    clear
    // params:  none
    //
    // desc:    clears all items from the list
    // returns: nothing
    //
    template <typename T>
    void DoublyLinkedList<T>::clear() {
      //work our way in from both sides (faster)
      Node *left = _head;
      Node *right = _tail;
    
      int leftIndex = 0;
      int rightIndex = _length - 1;
    
      //only while left is < right
      while (leftIndex < rightIndex) {
        _length -= 2;
    
        Node *next = left->next;
        Node *prev = right->prev;
    
        delete left;
        delete right;
    
        ++leftIndex;
        --rightIndex;
        left = next;
        right = prev;    
      }
    
      //if left and right point at the same node (center)
      //make sure we only delete it once
      if (leftIndex == rightIndex) {
        --_length;
        delete left;
      }
    
      _head = _tail = _cur = NULL;    
    }
    
    //////////////////////////////////////////////////
    // name:    insertItem
    // params:  item - the item to insert
    //
    // desc:    inserts an item at the end of the list
    // returns: nothing
    //
    template <typename T>
    void DoublyLinkedList<T>::insertItem(const T &item) {
      if (isFull())
        throw ListException("Insert into full list");
    
      Node *newNode = new Node;
      newNode->data = item;
    
      if (_tail != NULL) {//if tail is pointing to a valid node
        _tail->next = newNode;//set it's next ptr to the new node
        newNode->prev = _tail;//set it's prev ptr to the previous tail
      }
    
      _tail = newNode;//now the new node IS the tail
    
      if (_head == NULL) {//if the list is empty
        _head = _tail;//point the head at the tail
        _cur = _head;
      }
    
      ++_length;
      ++_insCounter;//update stat counter
    }
    
    ///////////////////////////////////////////
    // name:    findItem
    // params:  item - the item to find
    //
    // desc:    searches list for item
    // returns: true if found. false otherwise.
    //
    template <typename T>
    bool DoublyLinkedList<T>::findItem(const T &item) {
      return locateItem(item, &_srcCounter) != NULL;
    }
    
    //////////////////////////////////////
    // name:    deleteItem
    // params:  item - item to delete
    //
    // desc:    deletes item from the list
    // returns: nothing
    //
    template <typename T>
    void DoublyLinkedList<T>::deleteItem(const T &item) {
      if (isEmpty())
        return; 
    
      //work our way in from both sides  
      Node *left = _head;
      Node *right = _tail;
    
      int leftIndex = 0;
      int rightIndex = _length - 1;
    
      while (leftIndex <= rightIndex) {
        ++_delCounter;//update stat counter
    
        //update our pointer indices
        ++leftIndex;
        --rightIndex;
        
        if (left->data == item) {
          --_length;
          
          if (left == _head) {//if at head, repoint it to our next node 
            _head = left->next;
            _head->prev = NULL;
          }
    
          if (left == _cur)//don't let _cur point at invalid memory
            _cur = _cur->next;
    
          if (left->prev != NULL)//point prev node's next to our node's next
            left->prev->next = left->next;
          
          if (left->next != NULL)//point next node's prev to our node's prev
            left->next->prev = left->prev;
    
          Node *next = left->next;//get next node before deleting
          delete left;//now dealloc
          left = next;//continue
        }
        else
          left = left->next;
    
        if (right->data == item) {
          --_length;
    
          if (right == _tail) {//if at tail, repoint at our prev node
            _tail = right->prev;
            _tail->next = NULL;
          }
    
          if (right == _cur)//don't let _cur point at invalid memory
            _cur = _cur->prev;
    
          if (right->next != NULL)//point next node's prev to our node's prev
            right->next->prev = right->prev;
    
          if (right->prev != NULL)//point prev node's next to our node's next
            right->prev->next = right->next;
    
          Node *prev = right->prev;//get prev node before deleting
          delete right;//now dealloc
          right = prev;//continue
        }
        else
          right = right->prev;
      }
    }
    
    /////////////////////////////////////////////
    // name:    resetList
    // params:  none
    //
    // desc:    resets internal pointer to head
    // returns: nothing
    //
    template <typename T>
    void DoublyLinkedList<T>::resetList() {
      _cur = _head;
    }
    
    /////////////////////////////////////////////
    // name:    getNextItem
    // params:  none
    //
    // desc:    gets item internal pointer refers
    //          to then increments to the next
    // returns: item internal pointer refers to
    //
    template <typename T>
    T DoublyLinkedList<T>::getNextItem() {
      if (_cur == NULL)//either empty list or resetList wasn't called
        throw ListException("Retrieve next without reset");
    
      T item = _cur->data;//get the data
      _cur = _cur->next;//move to the next node
      return item;
    }
      
    #endif //_DOUBLYLINKEDLIST_H_
    (If any of the implementation seems odd or generally unusual, recall that it was written as defined by the instructor's direction.)
    Last edited by LuckY; 12-27-2005 at 05:33 PM.

  3. #3
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472
    Thanks Lucky, but i'm afraid that this is a bit complicated than what i was looking for . I need those programs in their simplest form so i can read and understand them on the fly.

    I have a data structure exam coming very soon, and i'm already modifying and redoing more than a dozen programs that my teacher wrote. His logic, variable naming and style is incredibley hard to the point that he'd let a "hello world" program look extremley complicated.

    So i'm simplifying his program, but so far i couldn't do well with the three programs i've mentioned.
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Question, do you understand templates?

    This is a good one for queues...
    http://www.cprogramming.com/tutorial...ory/queue.html

  5. #5
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Code:
    //valid : ([(a+b)+c]) + x
    //invalid : ([(a+b+c]) + x
    
    #include <iostream>
    #include <stack>
    #include <string>
    
    using namespace std;
    
    //function declarations
    bool Is_Bracket_Open(char);
    bool Is_Bracket_Closed(char);
    bool Check_Match(char,char);
    bool Is_Valid(string);
    
    int main()
    {
        string A ="([(a+b)+c])+x";
        string B ="([(a+b+c)+x";
        
        if(Is_Valid(A)==true)
        {
            cout<<"Valid";
        }
        else
         cout<<"***ERR";
        
        
        cin.get();
        cin.get();
    }
    /*=============================================
      Given: my_string   a string 
      Task:  To determine if the brackets are valid 
      return: Nada
      ============================================*/ 
    bool Is_Valid(string my_string)
    {
        stack<char> my_stack;//create a stack of chars
        for(int i=0; i<my_string.length(); i++)//iterate through string
        {
           
            char Symbol;
            Symbol = my_string[i];
            
            if(Is_Bracket_Open(Symbol)==true)
            {
                //push open bracket onto stack
                my_stack.push(Symbol);
            }
            if(Is_Bracket_Closed(Symbol)==true)
            {
                char top;
                if (!my_stack.empty())
                {
                  top = my_stack.top(); 
                    
                  if(Check_Match(top,Symbol)==true)
                  {
                     //discard opening bracket
                   
                      my_stack.pop(); 
                    
                  }
                  else
                  {
                    
              
                    return false;
                    break;
                  }
                }  
                else
                { 
                    return false;
                    break;
                }      
            }
            
        }
        if(!my_stack.empty())
        {
          return false;
        } 
        else 
        {
          return true; 
        }      
        
    }       
      
    
    bool Is_Bracket_Open(char ch)
    {
        if ((ch == '(')||
            (ch == '[')||
            (ch == '{'))
            return true;
        else
            return false;
    } 
    
    bool Is_Bracket_Closed(char ch)
    {
        if ((ch == ')')||
            (ch == ']')||
            (ch == '}'))
            return true;
        else
            return false;
    } 
    
    bool Check_Match(char A,char B) 
    {
        if ((A=='(')&&(B==')') )
        {
            return true;
        } 
         else if ((A=='{')&&(B=='}') )
        {
            return true;
        } 
          else if ((A=='[')&&(B==']') )
        {
            return true;
        } 
    }
    That's an example using the stack... it may or maynot be helpful
    Last edited by treenef; 12-28-2005 at 08:24 AM.

  6. #6
    former member Brain Cell's Avatar
    Join Date
    Feb 2004
    Posts
    472
    Thanks alot guys, i really appreciate it.

    I still need the most important program though, the doubly linked list. I couldn't find an example anywhere.

    any ideas?
    My Tutorials :
    - Bad programming practices in : C
    - C\C++ Tips
    (constrcutive criticism is very welcome)


    - Brain Cell

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Windows - how to get started... examples don't help
    By nonoob in forum Windows Programming
    Replies: 6
    Last Post: 09-26-2008, 06:45 AM
  2. Thread Pool libraries or examples
    By Mastadex in forum Windows Programming
    Replies: 6
    Last Post: 08-24-2008, 09:58 PM
  3. C/C++ examples
    By msp in forum C++ Programming
    Replies: 19
    Last Post: 10-04-2007, 07:22 AM
  4. Resource ICONs
    By gbaker in forum Windows Programming
    Replies: 4
    Last Post: 12-15-2003, 07:18 AM
  5. Treeview examples.
    By Sebastiani in forum Windows Programming
    Replies: 0
    Last Post: 09-21-2003, 01:16 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21