Matt Johnson's reply to BinaryBoy #1867 @
//CSE 120
//Sorting.cpp
//This program will sort things
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int Partition( vector<string>& v, int start, int end )
{
int left = start + 1;
int right = end;
do
{
left = start + 1;
right = end;
while( left < end && v[left] < v[start] )
{
left ++;
}
while( right > start && v[right] >= v[start] )
{
right --;
}
if( left < right )
{
swap( v[left], v[right] );
}
}
while( left < right );
swap(v[start], v[right]);
return right;
}
void QuickSort( vector<string>& v, int start, int end)
{
if ( end - start > 0 )
{
int mid = Partition( v, start, end );
QuickSort( v, start, mid );
QuickSort( v, mid + 1, end);
}
}
void main()
{
string word;
vector<string> v;
cout << "Please enter something to be sorted: ";
do
{
cin >> word;
v.push_back( word );
}
while( cin.peek() != '\n' );
QuickSort( v, 0, v.size() - 1 );
/*for( int i = 0; i < v.size() ; i++ )
{
for( int j = i + 1; j < v.size() ; j++ )
{
if( v > v[j] )
{
swap( v, v[j] );
}
}
}
*/
cout << endl;
for( int m = 0; m < v.size(); m++ )
{
cout << v[m] << endl;
}
cout << endl;
}
#include <string>
#include <vector>
#include <iostream>
using namespace std;
void main()
{
string str;
vector<string> v;
do
{
cin>>str;
v.push_back(str);
}while (cin.peek() != '\n');
for (int i=1;i<str.length();i++)
for (int j=0;j<str.length();j++)
if (v<v[j])
swap(v, v[j]);
cout <<endl;
for (int i = 0; i<v.size(); i++)
cout<< v << endl;
return;
}
/*
Matthew McLure
DynamicString.cpp
String class cpp file
mdm5045
*/
#include <iostream>
#include "DynamicString.h"
#include "EmailTld.h"
#include "EmailLocalPart.h"
#include "EmailDomain.h"
#include "EmailSubDomain.h"
#include "Email.h"
using namespace std;
//The constructor here just sets stuff to null values
DynamicString::DynamicString()
{
String = NULL;
Length = 0;
}
//This constructor refers to the set function to copy the input array to the String pointer.
DynamicString::DynamicString(const char* inputString)
{
Set(inputString);
}
//the set function determines length from the input array and then declares the String pointer accordingly
void DynamicString::Set(const char* inputString)
{
Length = GetStringLength(inputString);
String = new char[Length + 1];
for ( int i = 0 ; i < Length ; i++ )
{
String = inputString;
}
String[Length] = '\0';
}
char* DynamicString::Get()
{
return String;
}
//The Get before function takes everything before a certain character and returns a char array out of it.
char* DynamicString::GetBefore(char symbol)
{
char* first_portion;
int pos = Find(symbol);
int i = 0;
first_portion = new char[pos];
for( i = 0 ; i < pos ; i++ )
{
first_portion = String;
}
first_portion = '\0';
return first_portion;
}
//Get after does same as Get before, except after the character
char* DynamicString::GetAfter(char symbol)
{
char* last_portion;
int pos = Find(symbol);
int i = 0;
int j = 0;
last_portion = new char[(Length - pos) + 1];
for( i = pos+1 ; i < Length ; i++ )
{
last_portion[j] = String;
j++;
}
last_portion[j] = '\0';
return last_portion;
}
//Get between return a char array from between 2 characters
char* DynamicString::GetBetween(char symbol1, char symbol2)
{
char* portion;
int pos1 = Find(symbol1);
int pos2 = Find(symbol2);
int i = 0;
int j = 0;
portion = new char[(pos2 - pos1) + 1];
for( i = pos1 + 1 ; i < pos2 ; i++ )
{
portion[j] = String;
j++;
}
portion[j] = '\0';
return portion;
}
//Contains checks if the String Contains a character and returns true or false
bool DynamicString::Contains(char symbol)
{
if ( Find ( symbol ) <= Length )
{
return true;
}
else
{
return false;
}
}
//begins with checks if a char array begins with a provided char, and returns true or false
bool DynamicString::BeginsWith(char symbol)
{
if ( Find ( symbol ) == 0 )
{
return true;
}
else
{
return false;
}
}
int DynamicString::GetLength()
{
return Length;
}
//Find returns the index of a provided character
int DynamicString::Find(char symbol)
{
int i;
for ( i = 0 ; i <= Length + 1 ; i++ )
{
if ( String == symbol )
{
return i;
}
}
return i;
}
// The destructor dynamically deletes the String pointer, and sets both String and length to their null values.
DynamicString::~DynamicString()
{
if ( String )
{
delete String;
String = NULL;
Length = 0;
}
}
//This function is used to find the length of an input array before copying it to the String pointer, so that String can be declared with an exact size.
int DynamicString::GetStringLength(const char* text)
{
int size = 0;
while ( text != '\0' )
{
size++;
}
return size + 1;
}
/*
Matthew McLure
DynamicString.h
String class header file
mdm5045
*/
#pragma once
using namespace std;
class DynamicString
{
public:
DynamicString();
DynamicString(const char* inputString);
public:
void Set(const char* inputString);
char* Get();
char* GetBefore(char symbol);
char* GetAfter(char symbol);
char* GetBetween(char symbol1, char symbol2);
bool Contains(char symbol);
bool BeginsWith(char symbol);
int GetLength();
int Find(char symbol);
public:
~DynamicString();
private:
int GetStringLength(const char* text);
private:
int Length;
char* String;
};
/*
Matthew McLure
mdm5045
BST_Main.cpp - Main implementation file
This program will take in a sentence, store the words in a binary search tree, and then prompt for a word to be removed.
*/
#include <iostream>
#include <string>
using namespace std;
template<typename T> struct TreeNode
{
TreeNode(const T& value, TreeNode<T>* left = NULL, TreeNode<T>* right = NULL)
{
Value = value;
Left = left;
Right = right;
}
T Value;
TreeNode<T>* Left;
TreeNode<T>* Right;
bool IsLeaf()
{
return Left == NULL && Right == NULL;
}
};
template<typename T> void Insert (T& value, TreeNode<T>* &treeRoot)
{
if (treeRoot == NULL)
{
treeRoot = new TreeNode<T>(value);
}
else if (treeRoot->Value == value)
return;
else if (treeRoot->Value < value)
{
Insert (value, treeRoot->Right);
}
else
{
Insert (value, treeRoot->Left);
}
}
template<typename T> void Remove (T& value, TreeNode<T>* &treeRoot, TreeNode<T>* &parent)
{
if (treeRoot == NULL)
{
return;
}
if (value < treeRoot->Value)
{
Remove (value, treeRoot->Left, treeRoot);
}
else if (value > treeRoot->Value)
{
Remove (value, treeRoot->Right, treeRoot);
}
else
{
if ( treeRoot->IsLeaf() )
{
if (parent->Left == treeRoot)
parent->Left = NULL;
else
parent->Right = NULL;
delete treeRoot;
}
else if (treeRoot->Left == NULL)
{
if (parent->Left == treeRoot)
parent->Left = treeRoot->Left;
else
parent->Right = treeRoot->Left;
delete treeRoot;
}
else if (treeRoot->Right == NULL)
{
if (parent->Left == treeRoot)
parent->Left = treeRoot->Left;
else
parent->Right = treeRoot->Left;
delete treeRoot;
}
else
{
TreeNode<T>* parent = NULL;
TreeNode<T>* node = treeRoot->Left;
while ( node->Right != NULL )
{
parent = node;
node = node->Right;
}
parent->Right = NULL;
treeRoot->Value = node->Value;
//parent->Left = node->Left;
delete node;
}
}
}
template<typename T> void Print (TreeNode<T>* &treeRoot)
{
if (treeRoot == NULL)
return;
Print (treeRoot->Left);
cout << endl << treeRoot->Value;
Print (treeRoot->Right);
}
int main()
{
cout << endl << "Please enter your sentence: ";
string word;
TreeNode<string> *treeRoot = NULL;
while (cin.peek() != '\n')
{
cin >> word;
Insert(word, treeRoot);
};
Print (treeRoot);
cout << endl << "Please enter a word to remove: ";
cin >> word;
Remove (word, treeRoot, treeRoot);
cout << endl;
Print (treeRoot);
cout << endl;
return 0;
}