1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

if I want but value in the header in linked list

Discussion in 'C' started by fulla, Mar 10, 2011.

  1. fulla

    fulla New Member

    Joined:
    Mar 6, 2011
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    hi..

    I want ask if I want but in the header of linked list acounter to count the nods for exampel or any thing ..
    I just want know how can I add the value in teh header

    the code of linked list is:
    HTML:
    
    
    
    
    
    //    Node Declaration
    
        template <class  TYPE> 
        struct NODE 
          {
           TYPE    data;
           NODE   *link;
          }; //  End of Node Declaration
          
    
    
    //    List Class Declaration
    
        template <class  TYPE, class KTYPE> 
        class List  
           {
             private:
               NODE<TYPE> *head;
               NODE<TYPE> *pos;
               NODE<TYPE> *rear;
               int         count;
              
    
    //         Function Declarations
               bool  _insert  (NODE<TYPE>   *pPre,   
                               TYPE          dataIn);
               void  _delete  (NODE<TYPE>   *pPre,
                               NODE<TYPE>   *pLoc,
                               TYPE         *dataOutPtr);
               bool  _search  (NODE<TYPE>  **pPre,
                               NODE<TYPE>  **pLoc,
                              int       key);
    
             public:
            
               NODE<TYPE>  *arry;//?????
               List (void);
              ~List (void);
               int        addNode      (int  dataIn);
               bool       removeNode   (KTYPE  key, 
                                        TYPE  *dataOutPtr);
               bool       retrieveNode (KTYPE  Argu, 
                                        TYPE&  dataOut);
               bool       getNext      (int    fromWhere,  
                                        TYPE&  dataOut);
               int        listCount    (void);
               bool       emptyList    (void);
               bool       fullList     (void); 
           }; // class List 
    
    //     End of List Class Declaration
    
    /*     =============== List Constructor  ==============    
        Initialize the list.
          Pre    Class is being instantiated
          Post   Class instantiated and initialized
    */
    template <class TYPE, class KTYPE>
    List<TYPE, KTYPE> :: List (void)   
    {
    //    Statements 
        head     = NULL;
        pos      = NULL;
        rear     = NULL;
        count    = 0;
        
        
        
    } //  List Constructor 
    
    /*    ==================== addNode =================== 
        Inserts data into linked list.
           Pre     dataIn contains data to be inserted
           Post    Data inserted or error
           Return -1 if overflow, 
                   0 if successful,
                   1 if duplicate key
    */
    template <class TYPE, class KTYPE> 
    int List<TYPE, KTYPE> :: addNode (int dataIn)
    {
    //    Local Definitions 
        bool  found;
        bool  success;
    
        NODE<TYPE>  *pPre;
        NODE<TYPE>  *pLoc;
        
    //  Statements 
        found = _search (&pPre, &pLoc, dataIn);
        if (found)
           // Duplicate keys not allowed 
           return (+1);
        
        success = _insert (pPre,  dataIn);
        if (!success)
           // Overflow 
           return (-1);
        return (0);
    }    //  addNode 
    
    /*    ===================== _insert ==================== 
        Inserts data into a new node in the linked list.
           Pre     Insertion location identified by pPre
                   dataIn contains data to be inserted
           Post    data inserted in linked list or overflow
           Return  true  if successful, false if overflow
    */
    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE> :: _insert (NODE<TYPE> *pPre,  
                                       TYPE        dataIn)
    {
    //    Local Definitions 
        NODE <TYPE>  *pNew;
    
    //    Statements 
        if (! (pNew = new NODE<TYPE>))
           return false;
        
        pNew->data = dataIn; 
        pNew->link = NULL; 
             
        if (pPre == NULL)
           {
            //  Adding before first node or to empty list. 
            pNew->link = head;
            head = pNew;
           } // if pPre 
        else
            {
             // Adding in middle or at end 
             pNew->link  = pPre->link;
             pPre->link  = pNew;
            } // if else  
         
             // Now check for add at end of list 
             if (pNew->link == NULL)
                // Adding to empty list. Set rear  
                rear = pNew;
    
        count++;
    
        return true;
    }    // _insert 
    
    /*     ================== removeNode ================== 
        Removes data from linked list. 
           Pre    dltkey is identifier of node to be deleted
                  pDataOut is pointer to data variable to 
                  receive a copy of the deleted data
           Post   data copied to output variable and node
                  deleted or not found
           Return false if not found
                  true  if deleted
    */
    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE> ::  
              removeNode (KTYPE dltkey, TYPE *pDataOut)
    {
    //    Local Definitions 
        bool         found;
        NODE<TYPE>  *pPre;
        NODE<TYPE>  *pLoc;
        
    //    Statements 
        found = _search (&pPre, &pLoc, dltkey);
        if (found)
            _delete (pPre, pLoc, pDataOut);
        return found;
    } // removeNode
    
    /*    =================== _delete ================== 
        Deletes data from a linked list and returns 
        data to calling module.
           Pre  pPre is a pointer to predecessor node
                pLoc is a pointer to target node
                pDataOut is pointer to output data area
           Post Data have been deleted and returned 
                Data memory has been recycled
    */
    template <class TYPE, class KTYPE>
    void List<TYPE, KTYPE> :: _delete (NODE<TYPE>   *pPre,
                                       NODE<TYPE>   *pLoc, 
                                       TYPE         *pDataOut) 
    {
    //    Statements 
        *pDataOut = pLoc->data;
        if (pPre == NULL)
            // Deleting first node 
            head = pLoc->link;  
        else
            // Deleting any other node
            pPre->link = pLoc->link;
         
        // Test for deleting last node 
        if (pLoc->link == NULL)
           rear = pPre;
    
        count--;
        delete pLoc;
      
        return;
    }    //  _delete 
    
    /*    =================== retrieveNode ================== 
        Interface to search function. 
           Pre    key is the search argument
                  dataOut is variable to receive data
           Post   dataOut contains located data if found
                  if not found, contents are unchanged
           Return true if successful, false if not found
    */
    
    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE> 
             :: retrieveNode (KTYPE  key, TYPE&  dataOut)
    {
    //    Local Definitions 
        bool          found;
        NODE <TYPE>  *pPre;
        NODE <TYPE>  *pLoc;
    
    //    Statements 
        found = _search (&pPre, &pLoc, key);
        if (found)
           dataOut = pLoc->data;
        return found;
    }    // retrieveNode 
    
    /*    ==================== _search =================== 
        Searches list and passes back address of node 
        containing target and its logical predecessor.
           Pre    pPre is pointer variable for predecessor
                  pLoc is pointer variable for found node
                  key  is search argument
           Post   pLoc points to first node equal/greater key 
                  -or- null if target > key of last node
                  pPre points to largest node smaller than key
                  -or- null if target < key of first node
           Return true if successful, false if not found
    */
    template <class TYPE, class KTYPE> 
    bool List<TYPE, KTYPE> :: _search (NODE<TYPE> **pPre,  
                                       NODE<TYPE> **pLoc,
                                       int       key)
    {
    //    Statements 
        *pPre  = NULL;
        *pLoc  = head;
        if (count == 0)
            return false;
        
        // Test for argument > last node in list 
        if (key > rear->data) 
           {
            *pPre = rear;
            *pLoc = NULL;
            return false;
           } // if 
    
        while (key > (*pLoc)->data)
           {
            //  Have not found search argument location 
            *pPre = *pLoc;
            *pLoc = (*pLoc)->link;
           } // while 
        
        if (key == (*pLoc)->data)
            //   argument found--success 
            return true;
        else
            return false;
    }    //  _search 
    
    /*    =============== emptyList ============== 
        Returns Boolean indicating whether the
        list is empty.
           Pre    Nothing 
           Return true if empty, false if list has data 
    */
    template<class TYPE, class KTYPE> 
    bool List<TYPE, KTYPE> :: emptyList (void) 
    {
    //    Statements 
         return (count == 0);
    }    //  emptyList 
    
    /*    =================== fullList ================== 
        Returns Boolean indicating whether the list is full
        or has room for more data. 
           Pre    Nothing 
           Return true if full, false if room for another node
    */
    template <class TYPE, class KTYPE>
    bool List<TYPE, KTYPE> :: fullList (void) 
    {
    //    Local Definitions  
        NODE<TYPE>  *temp;
    
    //    Statements 
        if (temp = new NODE<TYPE>)
           {
            delete temp;
            return false;
           } // if
    
        // Dynamic memory full 
        return true;
    }    // fullList 
    
    /*    ==================== listCount ==================== 
        Returns integer representing number of nodes in list.
           Pre     Nothing
           Return  count for number of nodes in list
    */
    template <class TYPE, class KTYPE>
    int List<TYPE, KTYPE> :: listCount(void) 
    {
    //    Statements 
        return count;    
    }    // listCount
    
    /*    ====================== getNext ===================== 
        getNext traverses a linked list. Each call either starts 
        at the beginning of the list or returns the location of  
        the element in the list that was last returned.
           Pre   fromWhere is 0 to start at the first element
                 dataOut is reference to data variable 
           Post   if another element, address placed in output area
           Return true if another element located, 
                  false if end of list
    */
    template <class TYPE, class KTYPE> 
    bool List<TYPE, KTYPE> :: getNext (int    fromWhere,
                                       TYPE&  dataOut)
    {
    //    Local Definitions 
        bool success;
    
    //    Statements 
        if (fromWhere == 0)
           {
            // Start from first node 
            if (count == 0)
                success = false;
            else
               {
                pos      = head;
                dataOut  = pos->data;
                success  = true;
               } // if else 
           } // if fromwhere is zero
        else
           {
            // Continue from current position 
            if (pos->link == NULL)
                success = false;
            else
               {
                pos      = pos->link;
                dataOut  = pos->data;
                success  = true;
               } // if else 
           } // if fromWhere else 
        
        return success;
    }    // getNext
    
    /*    =============== Destructor ============== 
        Deletes all data in list and recycles memory
           Pre    List is being deleted 
           Post   Data and class structure have been deleted
    */
    template<class TYPE, class KTYPE> 
    List<TYPE, KTYPE > :: ~List (void) 
    {
    //    Local Definitions 
        NODE<TYPE>   *deletePtr;
    
    //    Statements 
        if (head)
           {
            while (count > 0) 
               {
                deletePtr = head;
                head      = head->link; 
                count--;
                delete  deletePtr; 
               } // while
           } //  if 
    }    // Destructor 
    
    
    
    
    
    
    
    and thanks :shy:
     
  2. fulla

    fulla New Member

    Joined:
    Mar 6, 2011
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    my secund qustion : if I want choos arandom node from the list how can I do it ??

    I bild a pointer then I saide :
    TYPE data;
    NODE<TYPE> *seek;
    data.key=abs(rand() % ??);
    seek->data.key;

    I gut loste !! becuse how can I know if the pointer dident go out of the rang?
     
  3. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Storing the size of a linked list is not a good idea as it is extra data that must be kept up to date with the list. Normally to determine the length of the list you would walk it from start to finish just counting each step. But there's nothing to stop you doing that if you want; just make sure that every function that adds or removes one or more nodes modifies the counter accordingly.

    If you know the size of the list then picking a random entry is easy. rand() % size will pick a random number in range, then you walk that many steps down the list. Lists are not arrays and do not use array semantics, so there is no "quick" way to the data.

    You can check if the pointer doesn't go out of range by checking for the NULL terminator. At the end of the list, link should be NULL, so if you're still walking when you encounter it you know your size variable has become out of step with the array (i.e. it doesn't represent the true length).
     
    fulla and shabbir like this.
  4. fulla

    fulla New Member

    Joined:
    Mar 6, 2011
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    ammmm... I use the function listcount like this:
    HTML:
    
    data.key=abs(rand()% A.listCount() );
    
    can I use function retrieveNode to do the jub to Ensures the existence within the list??
    EX:
    HTML:
    
    while(!A.retrieveNode (data.key, dataOut))
    
    
     
  5. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    I don't know. Does it work if you try it? (Why do you need to ask me this? It's your code; you know how it works.)
     
  6. fulla

    fulla New Member

    Joined:
    Mar 6, 2011
    Messages:
    8
    Likes Received:
    0
    Trophy Points:
    0
    becuse Iam relly bad in programming :(

    thanks alot for help ..
     

Share This Page