Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   if I want but value in the header in linked list (http://www.go4expert.com/forums/i-value-header-linked-list-t25207/)

fulla 10Mar2011 12:46

if I want but value in the header in linked list
 
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 Code:






//    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:

fulla 10Mar2011 14:27

Re: if I want but value in the header in linked list
 
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?

xpi0t0s 11Mar2011 12:53

Re: if I want but value in the header in linked list
 
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 11Mar2011 17:08

Re: if I want but value in the header in linked list
 
ammmm... I use the function listcount like this:
HTML Code:


data.key=abs(rand()% A.listCount() );

can I use function retrieveNode to do the jub to Ensures the existence within the list??
EX:
HTML Code:


while(!A.retrieveNode (data.key, dataOut))


xpi0t0s 11Mar2011 17:55

Re: if I want but value in the header in linked list
 
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.)

fulla 11Mar2011 18:54

Re: if I want but value in the header in linked list
 
becuse Iam relly bad in programming :(

thanks alot for help ..


All times are GMT +5.5. The time now is 07:55.