Computer Science Homework for COS2611: Data Structures

COS2611Assignment2.cpp

//COS2611 UNIQUE ASSIGNMENT 394025
//QUESTION 1:
#include <iostream>                            
#include "CustomLinkedList.h"                
 
using namespace std;

int main() {

    unorderedLinkedList<char> name;
    name.insertFirst('S');
    name.insertFirst('i');
    name.insertFirst('p');
    name.insertFirst('h');
    name.insertFirst('o');
    name.insertFirst(' ');    
    name.insertFirst('V');
    name.insertFirst('a');
    name.insertFirst('n');
    name.insertFirst(' ');
    name.insertFirst('A'); 
    name.insertFirst('s');   

    name.outputLinkedList();

    unorderedLinkedList<char> first_name,last_name;
    first_name.insertFirst('S');
    first_name.insertFirst('i');
    first_name.insertFirst('p');
    first_name.insertFirst('h');
    first_name.insertFirst('o');
  
    last_name.insertFirst('V');
    last_name.insertFirst('a');
    last_name.insertFirst('n');
    last_name.insertFirst(' ');
    last_name.insertFirst('A'); 
    last_name.insertFirst('s');   
    first_name.join(first_name,last_name);
    cout << endl;
    first_name.outputLinkedList();
}
//QUESTION 1 CUSTOM ADT CUSTOMLINKEDLIST.h:
template <class Type>
struct nodeType
{
	Type info;
	nodeType<Type> *link;
};
using namespace std; 

template <class Type>
class unorderedLinkedList{

public:
	nodeType<Type> *first ;
	nodeType<Type> *last ;

	unorderedLinkedList(){
		first = NULL;
		last = NULL;
	};

	void insertFirst(const Type& input){
		nodeType<Type> *newNode;
		newNode = new nodeType<Type>;
		newNode->info = input;
		newNode->link = NULL;
		if (first == NULL){
			first = newNode;
			last = newNode;
		} else
				{
					last->link = newNode;
					last = newNode;
				}
		}

	void outputLinkedList(){
		nodeType<Type> *current;
		current = new nodeType<Type>;
		current=first;
		while(current != NULL)
		{
		std::cout << current->info;
		current = current->link;
		}
	}

	void join(const unorderedLinkedList<Type>& firstList, const unorderedLinkedList<Type>& secondList)
	{
		//Join the two lists together.
		unorderedLinkedList<Type> tempList;
		const nodeType<Type> *current;
		nodeType<Type> *newNode;
		current = new nodeType<Type>;
		newNode = new nodeType<Type>;

		current=(firstList).first;
		while(current != NULL)
		{
		tempList.insertFirst(current->info);
		current = current->link;
		}	

		newNode->info = Type(' ');//TYPE CASTING FTW


		tempList.insertFirst(newNode->info);
		current=(secondList).first;
		while(current != NULL)
		{
		tempList.insertFirst(current->info);
		current = current->link;
		}	

		(*this) = tempList;//I like this.. lol.
	}

};
//QUESTION 1 OUTPUT:
Sipho Van As
Sipho Van As[Finished in 2.2s]
//QUESTION 2:
#include "myStack.h"
#include <iostream>

using namespace std;

template <class Type>
void stackType<Type>::update(Type t)
{

    stackType<Type> helperStack(maxStackSize);
    helperStack.initializeStack();
    bool isFound = false;
    while (top() != t && !isEmptyStack())
    {
        helperStack.push(top());
        pop();

    }
    if (top() != t)
    {
            helperStack.pop();  //pop the number //had to remove a dumb assert in myStack.h. 
                                //Took me too long to find it, agh. Smiley face, woosah!
    }else{pop();}

    while (!helperStack.isEmptyStack()) 
    {
        push(helperStack.top());
        helperStack.pop();

    }
    push(t);
    
}

int main(){
	stackType<int> stack(5),copyStack(5);
	stack.initializeStack();
    stack.push(1);
    stack.push(7);  
    stack.push(2);
    stack.push(8);
    stack.push(4);
    copyStack = stack;
    cout << "The elements of copyStack before update function: ";

    while (!copyStack.isEmptyStack())  //print copyStack
    {
        cout << copyStack.top() << " ";
        copyStack.pop();
    }
    cout << endl;
    stack.update(7);
    copyStack = stack;
    cout << "The elements of copyStack after update function: ";

    while (!copyStack.isEmptyStack())  //print copyStack
    {
        cout << copyStack.top() << " ";
        copyStack.pop();
    }
    cout << endl;

    stack.update(9);
    copyStack = stack;
    cout << "The elements of copyStack after update function with the value of 9(not in the stack): ";

    while (!copyStack.isEmptyStack())  //print copyStack
    {
        cout << copyStack.top() << " ";
        copyStack.pop();
    }
    cout << endl;
	return 0;
}

//QUESTION 2 OUTPUT:
The elements of copyStack before update function: 4 8 2 7 1 
The elements of copyStack after update function: 7 4 8 2 1 
The elements of copyStack after update function with the value of 9(not in the stack): 9 7 4 8 2 
[Finished in 1.4s]
//QUESTION 3:

//RECURSION: For fuck sakes, got to work on it. A bit of guidance wouldn't have hurt in this instance.

//QUESTION 4:
#include <iostream>
#include "linkedQueue.h"
 
using namespace std;

template <class Type>
void linkedQueueType<Type>::removeFirst(linkedQueueType<Type>& Q, const Type& x)
{
//the queue passed is the same queue as the queue in memory.
	
	linkedQueueType<Type> tempQ;
	tempQ.initializeQueue();
	bool isFound = false;
    while (!Q.isEmptyQueue() )
    {
    	if (isFound == false && Q.front() == x)
    	{
    		isFound = true;
    	}else
    	{
        tempQ.addQueue(Q.front());
        }
        Q.deleteQueue();

    }

    while(!tempQ.isEmptyQueue())
    {
    	Q.addQueue(tempQ.front());
    	tempQ.deleteQueue();
    }

}

int main()
{
    linkedQueueType<int> queue;

    queue.initializeQueue();
    queue.addQueue(1);
    queue.addQueue(2);
    queue.addQueue(3);
    queue.addQueue(4);
    queue.addQueue(5);
    queue.addQueue(4);
    queue.addQueue(4);
    queue.addQueue(1);
    cout << "Queue Elements: ";

    while (!queue.isEmptyQueue())
    {
        cout << queue.front() << " ";
        queue.deleteQueue();
    }
    cout << endl;
    queue.addQueue(1);
    queue.addQueue(2);
    queue.addQueue(3);
    queue.addQueue(4);
    queue.addQueue(5);
    queue.addQueue(4);
    queue.addQueue(4);
    queue.addQueue(1);    
    cout << "Remove 4" << endl;
    queue.removeFirst(queue,4);
	cout << "Queue Elements: ";

    while (!queue.isEmptyQueue())
    {
        cout << queue.front() << " ";
        queue.deleteQueue();
    }

    cout << endl;
    return 0;
}
//QUESTION 4 OUTPUT:
Queue Elements: 1 2 3 4 5 4 4 1 
Remove 4
Queue Elements: 1 2 3 5 4 4 1 
[Finished in 2.0s]

//QUESTION 5
Selection Sort
5 12 3 2 4 10 1 6 
1 12 3 2 4 10 5 6 
1 2 3 12 4 10 5 6 
1 2 3 12 4 10 5 6 
1 2 3 4 12 10 5 6 
1 2 3 4 5 10 12 6 
1 2 3 4 5 6 12 10 
1 2 3 4 5 6 10 12 
After Selection Sort
1 2 3 4 5 6 10 12 
--------------------
Insertion Sort
5 12 3 2 4 10 1 6 
5 12 3 2 4 10 1 6 
5 12 3 2 4 10 1 6 
3 5 12 2 4 10 1 6 
2 3 5 12 4 10 1 6 
2 3 4 5 12 10 1 6 
2 3 4 5 10 12 1 6 
1 2 3 4 5 10 12 6 
1 2 3 4 5 6 10 12 
After Insertion Sort
1 2 3 4 5 6 10 12 
--------------------
Quick Sort
5 12 3 2 4 10 1 6 
5 1 3 2 4 6 10 12 
2 1 3 4 5 6 10 12 
2 1 3 4 5 6 10 12 
1 2 3 4 5 6 10 12 
1 2 3 4 5 6 10 12 
After Quick Sort
1 2 3 4 5 6 10 12

//QUESTION 6:
preorder:    - * x + y z / - a b c
inorder:     x * y + z - a - b / c
postorder:   x y z + * a b - c / -

//QUESTION 7:

//Again, recursion, and submission time is 12pm, it is now 11:15pm, fuck that.. bed time, got golf tomorrow.

This helps me tons.. I didn't know how to interpret question 2 and now I get it.