0

In my cs2 class we are covering simple lists very quickly. I was assigned to add some functions to a basic list class, and after much thought I can not understand how to solve the problem.

Here is the assignment:

you will add the
following methods:

+ removeNode(val : int) : void This function receives an int as a
parameter and removes the node storing the value val if such node exist.

+ searchNode(val : int) : Node* This function receives an int as a
parameter and return a pointer pointing to the node storing the value val if
such node exist, else return NULL.

+ insertAfter(val : int, ptr : Node*): void This function receives an int
and a pointer to a node in the list as parameters and insert val in a new
node, and stores the new node in the list after the node to which ptr point.

Here is my code:

//******************************************************************************
//Programer: Kyle Willett
//Course:    CS-1513
//Program:   Assignment 7
//Purpose:   Functoins to remove a node, search for a node, and insert a node.
//Input:     Value to remove or value to search for or value for a new node.
//Calculate: Search or, manipulate ptr's for removal or insertion of nodes.
//Output:    Pointer to a node for two of the functions.
//******************************************************************************

#include<iostream>
#include<cstdlib>

using namespace std;

//******************************************************************************
class Node;

class Node
{
	private:
		int value;
		Node *next;
//************************************************		
	public:
	   //****CONSTRUCTORS****
    	Node()
		{
			value=0;
			next=NULL;	
		}
		Node(int val, Node *ptr)
		{
			value=val;
			next=ptr;
		}
//************************************************		
		int getValue()
		{
			return value;
		}
//************************************************
		void setValue(int val)
		{
			value=val;
		}
//************************************************
		Node* getNext()
		{
			return next;
		}
//************************************************
		void setNext(Node* ptr)
		{
			next=ptr;
		}
};
//******************************************************************************
class List
{
	private:
		int size;
		Node * head;
		Node * tail;
//************************************************
	public:
	   //****CONSTRUCTOR****
    	List()
		{
			size=0;
			head=NULL;
			tail=NULL;
		}
//************************************************
		int getsize()
		{
			return size;
		}
//************************************************
		Node* getHead()
		{
			return head;
		}
//************************************************
		Node* getTail()
		{
			return tail;
		}
//************************************************
		void setHead(Node *ptr)
		{
			head=ptr;
		}
//************************************************
		void setTail(Node* ptr)
		{
			tail=ptr;
		}
//************************************************
		void addFront(int val)
		{
			Node*  temp= new Node();
			(*temp).setValue(val);
			(*temp).setNext(head);
			
			head=temp;
			if(tail==NULL)
			{
				tail=temp;
			}
			
			size++;
		}
//************************************************
		void printValues()
		{
			Node* temp;
			temp=head;
			while(temp!=NULL)
			{
				cout << "Value in current Node is: ";
				cout <<(*temp).getValue() << endl;
				temp=(*temp).getNext();
			}
		}
//************************************************
		void addEnd(int val)
		{
			Node* temp= new Node(val, NULL);
			if(tail==NULL)
			{
				tail=temp;
				head=temp;
			}
			else
			{
				(*tail).setNext(temp);
				tail=temp;
			}                          
			size++;
		}
//************************************************
		void sortList1()
		{
			Node *temp1;
			Node *temp2;
			Node *temp3;

			temp1=temp2=head;
			
			int minVal;

			while(temp1!=NULL)
			{
				minVal=(*temp1).getValue();

				temp3=temp1;
				
				while(temp2!=NULL)
				{
					if((*temp2).getValue()< minVal)
					{
						minVal=(*temp2).getValue();
						temp3=temp2;
					}	
					temp2=(*temp2).getNext();
				}
				(*temp3).setValue((*temp1).getValue());
				(*temp1).setValue(minVal);
				temp1=(*temp1).getNext();
				temp2=temp1;
			}
		}
//************************************************
    void removeNode(int val)
    {
        
    }
//************************************************   
    Node* searchNode(int val)
    {
        Node* temp;
		temp=head;
			
        while(temp!=NULL)
        {
            if((*temp).getValue()==val)
            {
                return temp;
                //This statment returns the value in the node if it matches
                //the value searched for.
            }
            else if(temp!=NULL)
            {
                temp=(*temp).getNext();
            }
        //This statment goes to the next node if the search value wasn't found
        }
        if(temp==NULL)
        {
            return NULL;
        }
        //This return statment is used if the search value was not found.
    }
//************************************************
    void insertAfter(int val, Node* ptr)
    {
        Node *temp0;
        //used to hold a copy of the current list.
        Node *temp1;
        //used to know the value of the current element that must
        //be shifted down one.
        temp0=temp1=head;
        
        bool check=false;
        
        while(check==false)
        {
            
            if(temp0==ptr)
            {
                temp1=temp0;
                temp0= new Node(val, (*temp0).getNext());
                check=true;
                ptr=temp0;
            }
            temp0=(*temp0).getNext();
        }
    }	
};
//******************************************************************************
//******************************************************************************
int main()
{
	//create instance of class node.
	
	Node var1;
	var1.setValue(20);
	cout << var1.getValue() << endl;

	//create a list object.
	List var2;

	for(int n=0; n<10; n+=2)
	{
		var2.addFront(n);
		var2.addEnd(n+1);
	}

	cout << var2.getsize()<< endl;

	var2.printValues();
	
	var2.sortList1();
	
	cout << endl << endl << endl;	

	var2.printValues();

	cout << endl << endl << endl;	

    int value=0;
    Node *temp=NULL;
    cout << "Enter a value to search the list for: ";
    cin >> value;
    cout << endl;
    cout << "The value searched for is: ";
    temp=var2.searchNode(value);
    if(temp!=NULL)
    {
        cout << (*temp).getValue();
    }
    else if(temp==NULL)
    {
        cout << "NULL";
    }
    //The if statment is used because of errors if the value returned was
    //NULL, so the conditional statment doesnot let the computer attempt to 
    //dereference NULL.
    cout << endl << endl;

    int val;
    cout << "Input value for new Node: ";
    cin >> val;
    cout << endl;
    var2.insertAfter(88, var2.getHead());
    var2.printValues();
    cout << endl;
    
	return 0;
}
//******************************************************************************

if it helps here is an earlier version of the insertAfter function I was working on:

void insertAfter(int val, Node* ptr)
{
    Node *temp0;
    //used to hold a copy of the current list.
    Node *temp1;
    //used to know the value of the current element that must
    //be shifted down one.
    temp0=temp1=head;
    
    while(temp0!=NULL)
    {
        if(temp0==ptr)
        {
            temp1=temp0;
            temp0= new Node(val, temp1);
        }
    }
}

I need help with finishing the insertAfter function and I don't even know where to start with the removeNode function.

Since I spent so much time trying to understand everything the time I have to do this project has ran out, it is due tomorrow, so prompt help would be appreciated!

Thank You.

2
Contributors
4
Replies
5
Views
6 Years
Discussion Span
Last Post by Kyle Willett
0

There are two things that occur to me about insertAfter() ; first, that in the current version you aren't testing for the end of the list; second, that you want to insert the new node after the node pointed to by ptr , but right now, you have it replacing ptr , instead.

//************************************************
    void insertAfter(int val, Node* ptr)
    {
        Node *temp0;
        //used to hold a copy of the current list.
        Node *temp1;
        //used to know the value of the current element that must
        //be shifted down one.
        temp0 = temp1 = head;
        
        while(temp0 != NULL)
        {
            
            if(temp0 == ptr)
            {
                temp1 = new Node(val, ptr->getNext());
                ptr->setNext(temp1);
                return;
            }
        }

        // reached the end of the list
        temp->setNext(new Node(val, NULL));
    }

I can't promise that this will work, but it should. Note the use of the member indirection operator ( -> ), which is basically a shorthand for dereferencing the pointer and getting the member from the dereferenced value.

Edited by Schol-R-LEA: n/a

1

I just noticed two serious problems with the code I posted. Here's the corrected code (I hope):

//************************************************
    void insertAfter(int val, Node* ptr)
    {
        if (head == NULL)
        {
            head = new Node(val, NULL);
            return;
        }

        Node *current;
        //used to hold a copy of the current list.
        Node *previous;
        //used to know the value of the current element that must
        //be shifted down one.
        

        current = previous = head;
        
        while(current != NULL)
        {
            if (current == ptr)
            {
                ptr->setNext(new Node(val, ptr->getNext()));
                return;
            }
            previous = current;
            current = current->getNext();
        }

        // reached the end of the list
        previous->setNext(new Node(val, NULL));
    }

Edited by Schol-R-LEA: n/a

0

Ok thank you very much for the help with the insert function, do you have any advice on the remove function?

0

Well the time came for me to have to submit the program thanks you for helping me though.

I the code I wound up using for the remove function was:

void removeNode(int val)
    {
        Node *previous;
        Node* temp;
		temp=previous=head;
		
		if((*temp).getValue()==val)
		{
            delete temp;
            temp=(*temp).getNext();
        }
		

		while(temp!=NULL && (*temp).getValue()!=val)
		{
            previous=temp;
            temp=(*temp).getNext();
        }
        
        if((*temp).getValue()==val)
        {
            (*temp).setNext((*previous).getNext());
            delete temp;
            //In this step I am trying to preserve the linking of the list, 
            //but it does not seem to work correctly.
        }      
   }

I know this doesn't work but I think it is close.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.