Solved

C++ problem

Posted on 2012-03-23
6
1,334 Views
Last Modified: 2012-03-25
add the following operation to the class orderedLinkedList:
void mergeLists(orderedLinkedList<Type> &list1,orderedLinkedList<Type> &list2)
{
     //this function creates a new list by merging the elements of list 1 and list2
     //Postcondition: first points to the merged list; list1 and list 2 are empty
}

orderedLinkedList<int> newList;
orderedLinkedList<int> list1;
orderedLinkedList<int> list2;
suppose list1 points to the list with elements 2 6 7 and list 2 points to the elements with 3 5 8. The statement
newList.mergeLists(list1, list2);
creates a new linked list with the elements in order 2 3 5 7 8 and the object newLists points to this list. Also, after the preceding statement executes, list 1 and list2 are empty.
Write the definition of the function template to implement the operation mergeLists. Also write a program to test the function.
The code for the header file for the class orderedLinkedList
#include <iostream>
#include "linkedListType.h"

using namespace std;

template <class Type>
class orderedLinkedList: public linkedListType<Type>
{
public:
    bool search(const Type& searchItem) const;
    //func to determine whether searchItem is in the list
    //postcondition: returns true if searchitem is in the list, otherwise false
    void insert(const Type& newItem);
    //func to insert newItem into list
    //postcondition: first points to the new list, newItem is inserted at the proper place
    //in the list, and count is incremented by 1
    void insertFirst(const Type& newItem);
    //func to insert newItem at the beginning of the list
    //postcondition: first points to the new list, newitem is inserted at the beginning of the list, last points to the last
    //node in the list, and count is incremented by 1
    void insertLast(const Type& newItem);
    //func to insert newItem at the end of the list
    //postcondition: first points to the new list, newitem is inserted at the end of the list, last points to the last
    //node in the list, and count is incremented by 1
    void deleteNode(const Type& deleteItem);
    //func to delete deleteItem from the list
    //postcondition: if found, the node containing deleteItem is deleted from the list, first points to the first node
    // of the new list, count is decremented by 1. If deleteItem is not in the list, a message is printed.
protected:
    int count; //valiable to store the number of list elements
    nodeType<Type> *first; //pointer to the first node of the list
    nodeType<Type> *last; //pointer to the last node of the list
       
};
0
Comment
Question by:Dmon443
  • 3
  • 2
6 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 37759952
So, do you have a question or was you just hoping we'd do this for you?
0
 

Author Comment

by:Dmon443
ID: 37760087
Ok so I need some help with the function mergeLists.
here are all the header files in the program:

template <class Type>
struct nodeType
{
    Type info;
    nodeType<Type> *link;    
};

template <class Type>
class linkedListIterator
{
public:
    linkedListIterator();
    //default constructor
    //postcondition: current = NULL
    linkedListIterator(nodeType<Type> *ptr);
    //constructor with a parameter
    //postcondition: current = ptr
    Type operator* ();
    //function to overload the dereferencing operator *
    //postcondition: returns the info contained in the node
    linkedListIterator<Type> operator++();
    //overload the preincrement operator
    //postcondition: the iterator is advanced to the next node
    bool operator==(const linkedListIterator<Type>& right) const;
    //overload the equality operator
    //postcondition: returns true if this iterator is equal to the iterator specified by right, otherwise false
    bool operator!=(const linkedListIterator<Type>& right) const;
    //overload the not equal to operator
    //postcondition: returns true if this iterator is not equal to the iterator specified by right, otherwise false

private:
    nodeType<Type> *current; //pointer to point to the current node in the linked list
       
};

#include "linkedListIterator.h"

using namespace std;


template <class Type>
class linkedListType
{
public:
    const linkedListType<Type>& operator =(const linkedListType<Type>&);
    //overload the assignment operator
    void initializeList();
    //initialize the list to an empty state.
    //postcondition: first = NULL, last = NULL, count =0
    bool isEmptyList() const;
    //function to determine whether the list is empty
    //true empty
    void print() const;
    //function to output the data contained in each node
    int length() const;
    //function to return the number of nodes in the list
    //returns value of count
    void destroyList();
    //function to delete all the nodes from the list
    //postcondition: first and last = NULL count =0
    Type front() const;
    //function to return the first element of the list
    //precondition: list must exist and must not be empty
    //post: if list is empty prog terminates, otherwise first element is returned
    Type back() const;
    //function to return the last element of the list
    //precondition: list must exist and must not be empty
    //post: if list is empty prog terminates, otherwise last element is returned
    virtual bool search(const Type& searchItem) const = 0;
    //function to determine whether searchItem is in the list
    //returns true if searchItem is in list otherwize false
    virtual void insertFirst(const Type& newItem) = 0;
    //function to insert newItem at the beginning of the list
    //postcondition: first points to the new list, newItem is inserted at the beggining of the list,
    //last points to the last node in the list, and count is incremented by 1
    virtual void insertLast(const Type& newItem) = 0;
    //function to insert newItem at the end of the list
    //postcondition: first points to the new list, newItem is inserted at the end of the list,
    //last points to the last node in the list, and count is incremented by 1
    virtual void deleteNode(const Type& deleteItem) = 0;
    //function to delete deleteItem from the list
    //postcondition: if found the node containing deleteItem is deleted from the list.
    //first points to the first node, last points to the last node of the updated list
    //and count is decremented by 1
    linkedListIterator<Type> begin();
    //function to return an iterator at the beginning of the linked list
    //postcondition: returns an iterator such that current is set to first
    linkedListIterator<Type> end();
    //function to return an iterator one element past the last element in the linked list
    //postcondition: returns an iterator such that current is set to NULL
    linkedListType();
    //default constructor
    //initialises the list to an empty state
    //postcondition: first = NULL, last = NULL, count = 0;
    linkedListType(const linkedListType<Type>& otherlist);
    //copy constructor
    ~linkedListType();
    //destructor deletes all nodes from the list
    //postcondition: the list object is destroyed

protected:
    int count; //valiable to store the number of list elements
    nodeType<Type> *first; //pointer to the first node of the list
    nodeType<Type> *last; //pointer to the last node of the list

private:
    void copyList(const linkedListType<Type>& otherlist);
    //function to make a copy of otherlist
    //postcondition: a copy of otherlist is created and assigned to this list        
};

and orderedLinkedList.h which I already posted.

Ok so for the function mergeLists I have :
void mergeLists(orderedLinkedList<Type> &list1, orderedLinkedList<Type> &list2)
{
    nodeType<Type> *newNode; //pointer to create a node
    nodeType<Type> *currentl1; //pointer to traverse list1
    nodeType<Type> *currentl2; //pointer to traverse list2
    currentl1 = list1.first; //currentl1 points to list1
    currentl2 = list2.first; //currentl2 points to list2
    first = new nodeType<Type>; //create the node
    first->info = currentl1->info; //copy the info
    //first->link = NULL; //set the link field of the node to NULL
    last = first; //make last point to the first node
    currentl1 = currentl1->link; //make currentl1 point to the next node
    currentl2 = currentl2->link; //make currentl2 point to the next node
    //copy the remaining list
    while (currentl1 != NULL)
    {
        newNode = new nodeType<Type>; //create a node
        newNode->info = currentl1->info; //copy the info
        newNode->link = NULL; //set the link of newNode to NULL
        last->link = newNode; //attach newNode after last
        last = newNode; //make last point to the actual last node
        currentl1 = currentl1->link; //make current point to the next node
    }//end while
    while (currentl2 != NULL)
    {
        newNode = new nodeType<Type>; //create a node
        newNode->info = currentl2->info; //copy the info
        newNode->link = NULL; //set the link of newNode to NULL
        last->link = newNode; //attach newNode after last
        last = newNode; //make last point to the actual last node
        currentl1 = currentl2->link; //make current point to the next node
    }//end while
   
       
}

So my questions are, will this put the two lists together I realise I must sort them after putting them together, also this seems like it is a very long and inefficient way to do it? Is there a better way to do this? If you would like me to put up the .cpp files for all those header files let me know.

Thanks
0
 

Author Comment

by:Dmon443
ID: 37760419
So I have been working on it some more and now it looks like this:
void mergeLists(orderedLinkedList<Type> &list1, orderedLinkedList<Type> &list2)
{
    nodeType<Type> *newNode; //pointer to create a node
    nodeType<Type> *currentl1; //pointer to traverse list1
    nodeType<Type> *currentl2; //pointer to traverse list2
    nodeType<Type> *trailCurrent; //pointer to trail current
    currentl1 = list1.first; //currentl1 points to list1
    currentl2 = list2.first; //currentl2 points to list2
    first = new nodeType<Type>; //create the node
    first->info = currentl1->info; //copy the info
    //first->link = NULL; //set the link field of the node to NULL
    last = first; //make last point to the first node
    currentl1 = currentl1->link; //make currentl1 point to the next node
    currentl2 = currentl2->link; //make currentl2 point to the next node
    //copy the remaining list
    while (currentl1 != NULL)
    {
        newNode = new nodeType<Type>; //create a node
        newNode->info = currentl1->info; //copy the info
        newNode->link = NULL; //set the link of newNode to NULL
        last->link = newNode; //attach newNode after last
        last = newNode; //make last point to the actual last node
        currentl1 = currentl1->link; //make current point to the next node
    }//end while
    while (currentl2 != NULL)
    {
        newNode = new nodeType<Type>; //create a node
        if (currentl2->info < first)
        {
                currentl1->link = currentl2->link;
                currentl2->link = first;
                first = currentl2;        
        }
        else
        {
                trailcurrent = first;
                currentl1 = currentl1->link;
                while (currentl1->info < currentl2->info)
                {
                                trailCurrent = currentl1;
                                currentl1 = current->link;
                }      
                if (currentl1 != currentl2)
                {
                                currentl2->link = currentl2->link;
                                currentl2->link = currentl1;
                                trailCurrent->link = currentl1;
                }
                else
                                currentl2 = currentl2->link;
        }
        newNode->info = currentl2->info; //copy the info
        newNode->link = NULL; //set the link of newNode to NULL
        last->link = newNode; //attach newNode after last
        last = newNode; //make last point to the actual last node
        currentl1 = currentl2->link; //make current point to the next node
    }//end while
       
}

That is my attempt at trying to sort it at the same time. Strange thing happens when I try to compile it, a compile progress window pops up but never finishes, I have never seen this happen before, usually my programs compile in about 1 second, not sure what I have done to put it in a never ending loop of compiling. Please help
0
 
LVL 40

Accepted Solution

by:
evilrix earned 500 total points
ID: 37761053
Ok, I am happy to assist you (and I'm sure jkr is too). Before we go anywhere I just want to make sure I understand the problem space so that I'm not giving you incorrect information.

Looking at the code that does the "merge" it looks like you are taking a copy of one list and appending it to the end of another. If I've understood the assignment criteria I don't think it's actually necessary to do this, although maybe I've misunderstood so let me share my take.

The assignment states, "suppose list1 points to the list with elements 2 6 7 and list 2 points to the elements with 3 5 8. The statement newList.mergeLists(list1, list2); creates a new linked list with the elements in order 2 3 5 7 8 and the object newLists points to this list. Also, after the preceding statement executes, list 1 and list2 are empty."

So, this suggests to me that there is no need to copy anything because it states that the original lists will be "emtpy". In fact the algorithm for doing this is almost trivial.

All you need do is walk both lists, find the value that is the lowest at each step and append it to the new list. You do this by having 2 pointers, one pointing to each list. Check the values at both positions (in this case position 0). The value that is the highest, move that node to the end of the new list. Then increment the pointer pointing to the list of the item you just moved. As you work your way through both lists you'll start to build a new list that is sorted (because the original two lists are sorted -- that is a prerequisite of this algorithm working).

Now perform the step again. At each step, you move the item with the lowest value to the new list and increment the pointer that was pointing to the item you moved. If both have the same value it doesn't matter which you move (in fact, you can move them both if you like). When you reach the end of one of the lists what remains in the other list just needs appending to the new list.

http://en.wikipedia.org/wiki/Merge_algorithm

This is the simplest method of merging two lists and it is done in linear 0(N) time, where N is the total number of items in both lists, and 0(1) space complexity (in other words, you require no additional space).

http://en.wikipedia.org/wiki/Time_complexity

Let's do a very quick example.

// our two old lists and the new one
list1 -> { 2, 6, 7 }
list2 -> { 3, 5, 8 }
newL => {}

// pointers to the head of each list (ie. the first items)
p1 = list1_head
p2 = list2_head
pN = newl_head = Null

// as long as both pointers are pointing to value list items
while (p1 && p2)
do
   if p1 > p2  // if p1 is greater move p2
     pN = p2
     p2 = p2->next
   else
   if p2 > p1 // if p2 is greater move p1
     pN = p1
     p1 = p1->next
   else // p1 and p2 have the same value so we can move both
      pN = p1
      pN = pN->next
      pN = p2
     p2 = p2->next
     p2 = p2->next
   endif

   // sure pN points to the tail of the new list
  pN = pN->next
end

// if we get here at least one pointer points to the end of a list, whichever it is append the other to the new list. If they both point to the end that's also find as it will just append a list terminator
pN = p1 if  p2==Null else p2

Open in new window


Note that this is an off the top of my head example of pseudo code. It's just to give you an idea, you'll still have to code it up and test it (I'm sure you realise code off the top of your head is unlikely to be error free so don't assume this isn't).

Let me know if anything is unclear.
0
 

Author Closing Comment

by:Dmon443
ID: 37762382
wow thanks that makes sense now, it's a lot simpler than it looked actually. Thanks again that really helped, I just need to practice a lot more so I can start to think more logically like that.
0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now