Include Stdafx.H
// Assignment4.cpp : //
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <string>
#define Driver pair<string,int>
using namespace std;
template<class ItemType> struct NodeType{
ItemType data;
NodeType<ItemType> *next;
};
/* Assumption: ItemType is a type for which the operators
"<" and "==" are defined-either an appropriate built-in type or a class that overloads these operators. */
template<class ItemType>
class UnsortedType
{
public:
// Class constructor, destructor, and copy constructor
UnsortedType();
~UnsortedType();
UnsortedType(const UnsortedType<ItemType&);
void operator=(UnsortedType<ItemType>);
bool IsFull() const;
// Determines whether list is full.
// Post: Function value = (list is full)
int GetLength() const;
// Determines the number of elements in list.
// Post: Function value = number of elements in list.
void RetrieveItem(ItemType& item, bool& found);
// Retrieves list element whose key matches item's key
// (if present).
// Pre: Key member of item is initialized.
// Post: If there is an element someItem whose key matches
// item's key, then found = true and item is a copy of
// someItem; otherwise found = false and item is
// unchanged.
// List is unchanged.
void InsertItem(ItemType item);
// Adds item to list.
// Pre: List is not full.
// item is not in list.
// Post: item is in list.
void DeleteItem(ItemType item);
// Deletes the element whose key matches item's key.
// Pre: Key member of item is initialized.
// One and only one element in list has a key matching
// item's key.
// Post: No element in list has a key matching item's key.
void ResetList();
// Initializes current position for an iteration through the
// list.
// Post: Current position is prior to list.
void GetNextItem(ItemType&);
// Gets the next element in list.
// Pre: Current position is defined.
// Element at current position is not last in list.
// Post: Current position is updated to next position.
// item is a copy of element at current position.
//private:
NodeType<ItemType>* listData;
int length;
NodeType<ItemType>* currentPos;
};
template<class ItemType>UnsortedType<ItemType>::UnsortedType(){
listData = NULL;
currentPos = NULL;
length = 0;
}
//The destructor deletes all nodes, freeing up the memory they used. The clear() function is called to do this operation.
template<class ItemType>UnsortedType<ItemType>::~UnsortedType(){
NodeType<ItemType> *tmp, *del;
tmp = listData;
for (int i=1; i <= length; i++){
del = tmp;
delete del;
tmp = tmp->next;
}
tmp = currentPos;
for (int i=1; i <= length; i++){
del = tmp;
delete del;
tmp = tmp->next;
}
length = 0;
}
template<class ItemType>UnsortedType<ItemType>::UnsortedType(const UnsortedType<ItemType& item){
*this = item;
}
template<class ItemType> void UnsortedType<ItemType>::operator=(UnsortedType<ItemType> item){
listData = item.listData;
length = item.length;
currentPos = item.currentPos;
}
/*The IsFull() function works exactly the same way as it did with other data structures.
A node is "created" using the new command, which is then checked.
If the new command had failed to set aside the necessary memory, its value is NULL, in which case the function returns true.
If the new node is created successfully, it is deleted and the function returns false.
*/
template<class ItemType>
bool UnsortedType<ItemType>::IsFull() const{
NodeType<ItemType> *tmp = new NodeType<ItemType>;
if(tmp == NULL)
return true;
else
{
delete tmp;
return false;
}
}
template<class ItemType>
int UnsortedType<ItemType>::GetLength() const{
return length;
}
template<class ItemType> void UnsortedType<ItemType>::RetrieveItem(ItemType &item, bool &found){
NodeType<ItemType> *tmp;
tmp = listData;
// consider each element of list and compare with item
for (int i=1; i <= length; i++){
if (tmp->data == item) {found = true; // found
return;
}
tmp = tmp->next; // consider next element
}
found = false; // not found
}
template<class ItemType> void UnsortedType<ItemType>::InsertItem(ItemType item){
NodeType<ItemType> *tmp = new NodeType<ItemType>;
NodeType<ItemType> *current;
ItemType newItem = item;
bool found;
RetrieveItem(newItem, found);
if (found) return; // item in List ====> exit
current = listData;
tmp->data = item;
if (listData == NULL){ // If list IS EMPTY, insert 1st node for the Circular list.
listData = tmp; // If list is EMPTY assign new tail insert to listData.
tmp->next = listData; // // Point tmp->next at listData: TMP NOW POINTS TO HEAD
} else{
while (current->next != listData) // Start with head and find the last node.
{
// As long as currrent->next is NOT equal to head, continue.
current = current->next; // Move to the next node, if any.
}
current->next = tmp; // Point current->next to tmp.
tmp->next = listData; // Point tmp->next at head: TMP NOW POINTS TO HEAD
}
currentPos = listData;
length++;
}
template<class ItemType> void UnsortedType<ItemType>::DeleteItem(ItemType item){
NodeType<ItemType> *tmp;
NodeType<ItemType> *current;
NodeType<ItemType> *garbage; // garbage FOLLOWS along behind the pointer current.
bool found;
if (length == 0) { cout<"List is empty"<endl;
return; // List is empty
}
RetrieveItem(item, found);
if (!found) { cout<"item need delete not in List"<endl;
return; // item not in List ===> exit
}
current = listData;
garbage = current;
if (listData == current->next) // ** If there is ONLY one element in list. **
if (current->data == item) // And it contains the id to be destroyed.
{
listData = NULL; // ** IMPORTANT to reset head to NULL if only element **
delete garbage; // delete node.
return;
}
//ELSE
for (int i=1; i <= length; i++)
if ((current->next)->data == item){
tmp = current->next;
current->next = (current->next)->next;
delete tmp; // delete node.
}
else
current = current->next;
length--;
}
template<class ItemType> void UnsortedType<ItemType>::ResetList(){
NodeType<ItemType> *tmp;
int post;
tmp = listData;
if (length <= 1) return;
post = rand()%length+1;
for (int i=1; i < post; i++) tmp = tmp->next;
currentPos = tmp;
}
template<class ItemType> void UnsortedType<ItemType>::GetNextItem(ItemType& item){
NodeType<ItemType> *tmp;
tmp = currentPos;
item = (tmp->next)->data;
}
//The class constructor initializes the private data members.
int _tmain(int argc, _TCHAR* argv[])
{
// name and age
string agn;
UnsortedType<Driver> *Test = new UnsortedType<Driver>();
cout<"Insert to circular linked list (name=Peter, age=23)"<endl;
Test->InsertItem(Driver("Peter",23));
cout<"Insert to circular linked list (name=Jack, age=29)"<endl;
Test->InsertItem(Driver("Jack",29));
cout<"Insert to circular linked list (name=Abeloa, age=26)"<endl;
Test->InsertItem(Driver("Abeloa",26));
cout<"Insert to circular linked list (name=Rikado, age=32)"<endl;
Test->InsertItem(Driver("Rikado",32));
cout<"Size of list is: "<Test->GetLength()<endl;
cout<"Delete from circular linked list (name=Jack, age=29)"<endl;
Test->DeleteItem(Driver("Jack",29));
cout<"Size of list is: "<Test->GetLength()<endl;
cout<"All element in list:"<endl;
NodeType<Driver> *tmp;
tmp = Test->listData;
for (int i=1; i <= Test->length; i++){
//strcpy((tmp->data).first, agn);
agn = (tmp->data).first;
for (int j=0; j < agn.size(); j++)
cout< agn[j];
cout<" "<(tmp->data).second<endl;
tmp = tmp->next;
}
cout<"Item current is:"<(Test->currentPos)->data.first<" "<(Test->currentPos)->data.second<endl;
cout<"\nResetList"<endl;
Test->ResetList();
Driver nextItem;
Test->GetNextItem(nextItem);
cout<"Item current is:"<(Test->currentPos)->data.first<" "<(Test->currentPos)->data.second<endl;
cout<"Get next item: "< nextItem.first<" "<nextItem.second<endl;
system("pause");
return 0;
}
//STDAFX.h
#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>