Hello, please help! I need to solve this problem, but I\'m also very interested
ID: 3553757 • Letter: H
Question
Hello, please help! I need to solve this problem, but I'm also very interested in learning how to do it, not just getting the answer... So an explanation of the code would be perfect! Thank you in advance. (Using C++ and Visual Studio 2010).
Activity #1
Implement a binary search function using a template. Your function should search for a value of any type within an array. Test your search function by calling it from the main function using an array of integers and an array of strings.
Activity #2
Modify the linked list class implemented in the lectures so that it can store values of different types (because it is implemented as a template class). Test your class using integer data and string data.
Linked list:
Explanation / Answer
/* -- Binary search with template -- */
#include <iostream>
#include <cstring>
using namespace std;
template <typename T>
int B_search (T A[], T const& key, int low, int high)
{
int mid = (low+high)/2;
if(A[mid] == key) return mid;
else if(A[mid] < key) return B_search(A,key,mid+1,high);
else return B_search(A,key,low,mid-1);
}
int main() {
string A[3] = {"Dileep","Kumar","wizard"};
string key = "wizard";
cout<<B_search(A,key,0,2)<<endl;
int B[3] = {0,1,2};
int k = 2;
cout<<B_search(B,k,0,2)<<endl;
return 0;
}
/* -- Linked list with template -- */
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;
template<typename T>
struct Node {
T data;
Node *next;
};
template<class T>
class LinkedList {
public:
LinkedList();
~LinkedList();
void addFront(T d);
bool remove(T d);
void addBack(T d);
bool removeBack();
void displayList();
bool isEmpty();
private:
Node<T>* head;
};
template<class T>
LinkedList<T>::LinkedList() {
head = NULL;
}
template<class T>
LinkedList<T>::~LinkedList() {
while (!isEmpty()) {
T d = head->data;
remove(d);
}
//delete some stuff...do this later...
}
template<class T>
bool LinkedList<T>::isEmpty() {
return (head == NULL);
}
template<class T>
void LinkedList<T>::displayList() {
cout << "Linked List: " << endl;
cout << "-------------------" << endl;
Node<T>* temp = head;
//loop through all nodes to display them
while (temp != NULL) {
cout << "DATA: " << temp->data << endl;
temp = temp->next;
}
cout << "-------------------" << endl;
}
template<class T>
void LinkedList<T>::addFront(T d) {
Node<T> *temp = new Node<T>;
temp->data = d;
temp->next = head;
head = temp;
}
template<class T>
bool LinkedList<T>::remove(T d) {
if (isEmpty()) {
return false;
} else {
Node<T> *current = head;
//Node<T> *previous = NULL;
//case 1: head is node to delete
if (current->data == d) {
head = current->next;
delete current;
return true;
} else {
//case 2: head is not node
while (current->next != NULL) {
if (current->next->data == d) {
Node<T> *temp = current->next;
current->next = current->next->next;
delete temp;
return true;
}
current = current->next;
}
return false;
}
}
}
int main() {
//ordinary linked list
LinkedList<string> l;
//data in empty list
cout << "data in empty list removed? " << l.remove("Aaron") << endl;
l.displayList();
l.addFront("Jeremy");
l.addFront("Melissa");
l.addFront("Khalil");
l.addFront("Aaron");
l.displayList();
//data at head
cout << "data at head removed? " << l.remove("Aaron") << endl;
l.displayList();
//data at head
cout << "data not in list removed? " << l.remove("Mahalia") << endl;
l.displayList();
//data in middle
cout << "data in middle removed? " << l.remove("Melissa") << endl;
l.displayList();
//data at tail
cout << "data at tail removed? " << l.remove("Jeremy") << endl;
l.displayList();
//only one element in list
cout << "data removed when only one element in list? " << l.remove("Khalil") << endl;
l.displayList();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.