Splitting a linked list

[Erdrigard]

I imagine I'm going to have multiple questions with this one. Please bear with me.

I am to split a linked list. I'm required to use this base class function (classes unorderedLinkedList and orderedLinkedList inherit this class):

template <class Type>
void linkedListType<Type>::divideAt(linkedListType<Type> &otherList, const Type &item)

which divides a linked list at a set link in the linked list. For example, you input a series of characters for object unorderedLinkedlist<char> list1: j, a, r, c, w, t, q. Something similar to this, though a tad different, appears in main:
list1.divideAt(list2, w)
And list1 would be j, a, r, c and list2 would be w, t, q.

My first question is this. Here's main.

#include <cstdlib>
#include <iostream>

#include "unorderedlinkedlist.h"

using namespace std;

int main()
{
    int i;
    unorderedLinkedList<int> myList;
    unorderedLinkedList<int> otherList;
    Type j;  //Line 13
    
    cout << "Insert some integers.  End with -999." << endl;
    cin >> i;
    
    while (i != -999) {
       myList.insertLast(i);
       cin >> i;
       }
       
    cout << "Here is the list of integers in the order you had given them: \n";
    myList.print();
    
    cout << endl;
    
    cout << "We will now create a new list from the integers given.\nRe-enter " 
         << "an integer you had previously entered.  The new list will begin there.\n";

    cin >> j;
    myList.divideAt(otherList, j);
    
    cout << "Here is that second list:\n";
    
    otherList.print();
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

The problem is Line 13. divideAt takes a const Type&.

The first question is how do I declare a variable of template Type in main? I know main can't be a template, so is there a painless, or way of moderate pain, way solution?
Thanks for reading!

[hamsterman]

You could write another function..

template<typename T>
void do_stuff(){
    unorderedLinkedList<T> myList, otherList;
    T j;
    ...
}

int main(){
    do_stuff<int>();
    return 0;
}

[ne555]

There isn't a variable Type, and your function isn't asking for one.

template <class Type>
void linkedListType<Type>::divideAt(linkedListType<Type> &otherList, const Type &item)

When you want to call this function you need to specify the template parameter (or let the compiler figures out)

unorderedLinkedList<int> myList; //here you are telling that Type=int
 myList.divideAt(otherList, j);

And that function call now creates the correspondent function
void linkedListType<int>::divideAt(linkedListType<int> &otherList, const int &item)

[Erdrigard]

Hey hamsterman, that worked well, thanks. I don't know why that thought didn't come to me. Wager I overthought it.

As I predicted, more issues surfaced. Now I've an issue with the divideAt function. For a quick reference as to what it does, I'll paste its explanation from this topic's intro post. Apologies if anyone is annoyed by the repetition:

divideAt() divides a linked list at a set link in the linked list. For example, you input a series of characters for object unorderedLinkedlist<char> list1: j, a, r, c, w, t, q. And here it is:

template <class Type>
void linkedListType<Type>::divideAt(linkedListType<Type> &otherList, const Type &item)
{     
     nodeType<Type> *current;  //node to traverse the list
     
     copyList(otherList);   //copies list to otherList
     
     while (first.otherlist->info != item)  //while the first is not the one in question
     {
      current = first.otherList;  //assign current to first node in otherlist
      first.otherList = first.otherList->next;  //first is assigned to next node
      count--;  //number of items in the list are reduced
      delete current;  //purges item from list
      } 
}

I know this only accounts for the otherList, and not the original list (so the original list, using the example here would be still be j, a, r, c, w, t, q). But, using the above code, I get this error:
request for member `otherlist' in `((linkedListType<int>*)this)->linkedListType<int>::first', which is of non-class type `nodeType<int>*'
I've never seen this error before, and I don't quite know what to do. Do any of you? Thanks for reading!

[ne555]

What is first? And why it has a member otherList?

//current = first.otherList;
current = otherList.first;

[Erdrigard]

Whoops, I got dyslexic with the members. Thanks.

I have another problem. Now, program complied and ran until divideAt function was called.

template <typename Type>
void func();

int main()
{
    int i;
    unorderedLinkedList<int> myList;
    unorderedLinkedList<int> otherList;

    cout << "Insert some integers.  End with -999." << endl;
    cin >> i;
    
    while (i != -999) {
       myList.insertLast(i);
       cin >> i;
       }
       
    cout << "Here is the list of integers in the order you had given them: \n";
    myList.print();
    
    cout << endl;
    
    cout << "We will now create a new list from the integers given.\nRe-enter " 
         << "an integer you had previously entered.  The new list will begin there.\n";

    func<int>();   //problem seems to be here
    
    cout << "Here is that second list:\n";
    
    otherList.print();
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

template <typename Type>
void func()
{
     unorderedLinkedList<Type> myList, otherList;
     Type j;
     
     cin >> j;   
     myList.divideAt(otherList, j);  //the problem seems to be here
}

It works fine until it asks for the point to split the list. After the number is entered, the program encounters an error and needs to close. At first I thought it was an encapsulation problem. After all, there were separate unorderedLinkedLists in their own scope.

So I decided to put everything in func(). But I get the exact same result at the same spot in the program.

#include <cstdlib>
#include <iostream>

#include "unorderedlinkedlist.h"

using namespace std;

template <typename Type>
void func();


int main()
{
    func<int>();
        
    system("PAUSE");
    return EXIT_SUCCESS;
}

template <typename Type>
void func()
{
     unorderedLinkedList<Type> myList, otherList;
     Type j;
     int i;
     
     cout << "Insert some integers.  End with -999." << endl;
    cin >> i;
    
    while (i != -999) {
       myList.insertLast(i);
       cin >> i;
       }
       
    cout << "Here is the list of integers in the order you had given them: \n";
    myList.print();
    
    cout << endl;
    
    cout << "We will now create a new list from the integers given.\nRe-enter " 
         << "an integer you had previously entered.  The new list will begin there.\n";
         
    cin >> j;
     myList.divideAt(otherList, j);   //seems to be a problem
    
    cout << "Here is that second list:\n";
    
    otherList.print();
}

Anybody know why the program combusts at that point? (by the way, combusts isn't a recognized word here... sad face)

[Erdrigard]

I've dedicated to take another stab at this. This time, I moved divideAt() from the base to the derived class and made some code adjustments. Here's where its stands now (info is what the node points to at that moment and link is the next node):

template <class Type>
void unorderedLinkedList<Type>::divideAt(Type& div)
{   
    nodeType<Type>* middle;  //node to trail current
    nodeType<Type>* current; //node that traverses the list

    if (this->first == NULL)  //if the list is empty
        cout << "There is no list to divide.";
    else if (this->first->link == NULL)   //if it has one item
        current->link = NULL;   //then current points to NULL... should probably say ya can't divide a single item list
    else  //if it has more than one item
    {
        current = this->first;   //assign current to the first item in the list

        if (current->info != div)    //if current doesn't point to the item of interest
            { middle = current;  //assign middle to where current is
               current = current->link;  //then move current one item forward
               }
        else if (current->info == div) //if current traverses to the value of interest
           middle->link = NULL;   //the node that was initially just behind current now points to NULL, severing the list
    } 
} 

I haven't yet written the code to start a new list starting from current->info. My main looks virtually the same as before as the bottom post on Nov 22, 2010 at 7:37pm, and I'm having a very similar problem:

the program makes it to the same point (the divideAt(i) function call, and, while to doesn't outright crash, it can't seem to get past the function in this post (it sort of stops at that point, I don't get a message telling me it needs to shut down, but it doesn't progress).

Anybody know what can cause this? Thanks.

[Erdrigard]

Alright, so some progress has been made on this one. The program runs with nothing that causes it to shut down (at least not that I have seen). It runs fine with problem (that I know of): dividedAt doesn't... divide lists. The code:

template <class Type>
void linkedListType<Type>::dividedAt(Type& div, linkedListType<Type> &otherList)
{   
    nodeType<Type>* trailer;  //node that trails current
    nodeType<Type>* current;  //node that traverses lists

    if (first == NULL)  //if the list is empty
        cout << "There's nothing in this list.\n";
    else if (first->link == NULL)  //if there's just one element
        cout << "There's just that one item in this list and it's not for dividing.";
    else
    {
        trailer = first;       //assign trailer to the first element
        current = first->link;   //assign current to the second element
        
        if (trailer->info != div && current != div)//if it's not the first or second item
           { trailer = current;   //reassign trailer to the next node, current
            current = current->link;} //reassign current to the next item
        else if (current->info == div) //if current does happen upon the item
          {trailer->link = NULL;  //****list is severed between trailer and current****
          otherList.first = current;  } //new list starts with current
    } 
} 

A new list is actually formed here, but the old list isn't severed at the right spot. Here's an example of the program output:

Enter a series of integers.  End with -999: 1
2
3
-999

Now divide the list into two lists.  Select an integer from the
list.  The new list will start there: 2

Okay.  Here's what's left of the original list:
1 2 3
Now here's the new list beginning from the selected value:
2 3
And finally the original list:
1 2 3
Press any key to continue . . . 

The last line is supposed to simply say 1. Anybody know why the list isn't dividing? Thanks.