link list with copy and delete elements

Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved

Join Date: Oct 2008
Posts: 6
Reputation: Geard2 is an unknown quantity at this point 
Solved Threads: 1
Geard2 Geard2 is offline Offline
Newbie Poster

link list with copy and delete elements

 
0
  #1
Oct 5th, 2008
I am new to link list and I have this problem where you have two lists. One list pointed by HEAD has a list of numbers in it, and the second list pointed by LARGE that contains the highest element(s) in the list pointed by HEAD. Each element has three fields: name, value, and link (I think the problem assumes the link is the pointer to the next node). Say for example you have a list 31 28 25 31 29 29 30 31 so the program will copy the highest value(s), here been 31(and its associated variables: name and link) into the list pointed by LARGE. On top of that, you delete those highest value(s) (including the name and link) in the list pointed by HEAD. So list pointed by HEAD will now have: 28 25 29 29 30 and list pointed by LARGE will have: 31 31 31. This is what I have so far (pseudo-code):

I am having trouble as to how to send the other values to the new list (name and link), and how to delete the old nodes from the original list (do not know how I can tell the program that this value came from the first node of orginial use delete using this method, or this value was found some where in between so you this method, since deleting the first node, last node, anything in between are three different algorithms to do it).

Algorithm node (struct node *HEAD)
Input: List with name, value, and link
Output: The orginial list without the highest value(s), and a list pointed by LARGE that contains the highest value(s) found in the list pointed by HEAD


struct node *LARGE;

node *currentVal = HEAD;
node *currentLargeVal = LARGE;
node *temp1;
node * temp2;
node *next = link; 

int p, q, Max;

if(currentVal == NULL)
{
    cout<<"Empty list"<<endl;
}
else
{
     temp1 = currentVal;
  
     for(currentVal = HEAD; currentVal != NULL; currentVal->next)
     { 
           p = temp1->value;
           q = temp1->next->value;
           if( p >= q)
           {
                 Max = p;
           } 
           else
           {
                 Max = q; 
           }
      } 
}// End of traversing the list to find the Max value in list pointed by HEAD

temp1 = currentVal;
temp2 = currentLargeVal;
for(currentVal = HEAD; currentVal != NULL; currentVal->next)
{
       if(temp1->value == Max)
        {
                if(currentLargeVal != NULL)
                { while (temp2 -> next != NULL)
                    {
                        temp2= temp2->next;
                    }
                      
                      temp2->next = Max;
                 }
        }
}
Reply With Quote Quick reply to this message  
Join Date: Jan 2008
Posts: 119
Reputation: kux is on a distinguished road 
Solved Threads: 10
kux kux is offline Offline
Junior Poster

Re: link list with copy and delete elements

 
0
  #2
Oct 5th, 2008
Why bother implementig your own list when you can easly use std::list and a struct Data{ string name; int value; }; with it?
Last edited by kux; Oct 5th, 2008 at 8:19 pm.
Reply With Quote Quick reply to this message  
Join Date: Oct 2008
Posts: 6
Reputation: Geard2 is an unknown quantity at this point 
Solved Threads: 1
Geard2 Geard2 is offline Offline
Newbie Poster

Re: link list with copy and delete elements

 
0
  #3
Oct 5th, 2008
Thank you for the suggestion. Since I am new to c++ I googled for std and list and I get information on how to do it with doubly linked lists. The program that I need help with is singly link list (sorry forgot to add it to my 1st post).
Reply With Quote Quick reply to this message  
Join Date: Oct 2007
Posts: 305
Reputation: stilllearning has a spectacular aura about stilllearning has a spectacular aura about 
Solved Threads: 43
stilllearning stilllearning is offline Offline
Posting Whiz

Re: link list with copy and delete elements

 
0
  #4
Oct 6th, 2008
In order to delete an element from a singly linked list, you need to save the previous pointer, and set a current pointer.

You may do something like :
if (current->data== max){
   tmp = current;
  // is current the head, if so move the head. 
   prev->next = current->next;
   current       = current->next;
   tmp->next  = NULL;

   // we have tmp, add it to max list 

  .....
}
else{
  // update prev
  // update current 
}

Now you have tmp, which is one of your max nodes, and you can add that to your new list.
You can increment the pointers accordingly. You may have edge cases to check for where max is the first or last element in the list, or if you have consecutive max elements.
Last edited by stilllearning; Oct 6th, 2008 at 1:07 am.
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC