# CS301 Data Structures Assignment 1 Solution Spring 2014

Question:

I am sending you a C++ program related to linked list along with your assignment file. In the given C++ program, I did not write some functions. Name of these functions are given below.

1)      main()

3)      void split(int c, List list, List largeList, List smallList)

4)      void differenceList(List listA, List listB)

Your assignment is to write the codes of these functions so that given program could be compiled and run to perform the required functionality/purpose.

Moreover required functionality/purpose of this C++ program is to perform the following tasks given below by using a linked list.

Splitting up an odd list:

2)      Create a linked list that will contain all the odd elements less than the number which you entered in first step. Also display this list.

3)      Now ask the user to enter any pivot element. Pivot element is a simple integer number. Use this pivot element to divide the list into two halves. First half will contain all the elements smaller than that pivot element. Save this first half into a list called smallList. Second half will contain all the elements larger than that pivot element. Save this second half into a list called largeList.

4)      Display smallList and LargeList that you formed in step 3.

Performing set difference operation on two odd lists:

1)      Your program should ask the user to input any two integer number for example 30 and 20.

2)      Create a linked list i.e. ‘list A’ that will contain all the odd elements less than the number 30 which you entered in first step. Also display this list.

3)      Create a linked list i.e. ‘list B’ that will contain all the odd elements less than the number 20 which you entered in first step. Also display this list.

4)      Perform the set difference operation on the two lists ‘list A’ and ‘list B’.

5)      Save the result of set difference operation in another list called setDifference and then display the list setDifference.

Note:

1)      Pivot element should be positive, greater than 0 and pivot element must also be from the list.

Sample Output

See the sample output demo file inorder to understand the desired output of your program.

Lectures Covered:  This assignment covers Lecture # 1 to 7.

Idea Solution:

#include <iostream.h>
#include <stdlib.h>

class Node
{
public:
int get() { return object; };
void set(int object) { this->object = object; };
Node * getNext() { return nextNode; };
void setNext(Node * nextNode) { this->nextNode = nextNode; };
private:
int object;
Node * nextNode;
};

class List
{
public:
List();
int get();
bool next();
friend void traverse(List list);
friend void split(int c, List list, List largeList, List smallList);
friend void differenceList(List listA, List listB);

private:
int size;
Node * currentNode;
Node * lastCurrentNode;
};
/* Constructor */
List::List()
{
currentNode = NULL;
lastCurrentNode = NULL;
size = 0;
}
{
Node * newNode = new Node();
if( currentNode != NULL )
{
newNode->setNext(currentNode->getNext());
currentNode->setNext( newNode );
lastCurrentNode = currentNode;
currentNode = newNode;
}
else
{
newNode->setNext(NULL);
currentNode = newNode;
}
size ++;
}
/* get() class method */
int List::get()
{
if (currentNode != NULL)
return currentNode->get();
}
/* next() class method */
bool List::next()
{
if (currentNode == NULL) return false;
lastCurrentNode = currentNode;
currentNode = currentNode->getNext();
if (currentNode == NULL || size == 0)
return false;
else
return true;
}
/* Friend function to traverse linked list */
void traverse(List list)
{
Node* savedCurrentNode = list.currentNode;
cout “\n\n Elements of list are given below “;
for(int i = 1; list.next(); i++)
{
cout “\n Element ” i ” ” list.get();
}
cout “\n List size = ” list.size ‘\n’;
list.currentNode = savedCurrentNode;
}

void split(int c, List list, List largeList, List smallList)
{

}

{

}

void differenceList(List listA, List listB){

}

main()
{

}