//PhoneBook10.cpp
// saved 10 on 12/06/2000
// deleteByAddress
// CPhoneBook(int n)
// overload assignment (=) operator
// copy constructor
// insertAtHead added 09 11/27/2000
// searchByName added
// void swap(p,q) added
// void swap(e1,e2) added
// bool isSortedByName() added 06 11/08/2000
// void sortByName(void); added 05
//Overload << for output added 04
//Constructor CPhoneBook(ch) added 03
////////////////////////////////////////////////////////////
// project #6 Date Assigned 11/8/2000, Date Due 11/17/2000
// describe ten shuffling methods (20)
// implement one of the ten methods (20)
// write the testShuffle (10)
// Five test runs (10)
////////////////////////////////////////////////////////////
//include files
////////////////////////////////////////////////////////////
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
////////////////////////////////////////////////////////////
//constants
////////////////////////////////////////////////////////////
int const MAX_LEN = 10;
int const MAX_COUNT = 10;
int const TEST_COUNT = 5;
////////////////////////////////////////////////////////////
//global variables
////////////////////////////////////////////////////////////
int masterKey = 1;
////////////////////////////////////////////////////////////
//test values
////////////////////////////////////////////////////////////
const char *testNames[] =
{"Bob", "Tom", "Ann", "Ron", "Ben", "Ken", "Rob",
"Sam", "Don", "Dan", "Tim"};
const int MAX_NAMES = sizeof(testNames)/sizeof(testNames[0]);
const char *testPhones[] =
{"111-1111", "222-2222", "333-3333", "444-4444"};
const int MAX_PHONES = sizeof(testPhones)/sizeof(testPhones[0]);
const char *testGroups[] =
{"Group1", "Group2", "Group3", "Group4"};
const int MAX_GROUPS = sizeof(testGroups)/sizeof(testGroups[0]);
////////////////////////////////////////////////////////////
//CPhoneEntry
////////////////////////////////////////////////////////////
struct CPhoneEntry
{
char name[MAX_LEN+1];
char phone[14+1];
char group[10+1];
int key;
CPhoneEntry *next;
};
////////////////////////////////////////////////////////////
//CPhoneBook
////////////////////////////////////////////////////////////
class CPhoneBook
{
private:
CPhoneEntry *first;
CPhoneEntry *last;
int count;
public:
CPhoneEntry * addressOfEntryAt(int pos);
public:
CPhoneBook(void);
bool insertAtEnd(char name[], char phone[], char group[], int key);
void display(void);
void deleteAll(void);
~CPhoneBook(void);
CPhoneBook(char ch);
void sortByName(void);
bool isSortedByName(void);
void displayReverse(void);
void displayReverse2(void);
friend ostream & operator << (ostream &os, const CPhoneBook &list);
CPhoneEntry * searchByName(char name[]);
bool insertAtHead(char name[], char phone[], char group[], int key);
CPhoneBook(const CPhoneBook &aBook);
CPhoneBook & operator = (const CPhoneBook &list);
void displayWithAddresses(void);
CPhoneBook(int n);
bool deleteByAddress(CPhoneEntry *p);
bool deleteByName(char name[]);
int deleteAllByName(char name[]);
bool deleteByPosition(int pos);
bool searchReplaceByName(char nameOld[], char nameNew[]);
int searchReplaceAllByName(char nameOld[], char nameNew[]);
int deleteDuplicates(void);
};
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
/*
bool DeleteByAddress(CPhoneEntry *p)
Possibility Action
------------- ----------
Empty List false
p is NULL false
p is not in list false
single item delete, true
first item delete, true
last item delete, true
between two delete, true
Empty List
----------
if first is null then
return false
end if
p is NULL
---------
if p is null then
return false
end if
p is not in list
----------------
found = false
q = first
while (q != null)
if p = q then then found = true, break
advance q
wend
if found is false then
return false
end if
single item
-----------
if first = last then
if p = first then
delete p
first = last = null
count = 0
return true
else
return false
end if
first item
----------
if p = first then
advance first
delete p
count--
return true
end if
last item
---------
if p = last then
make q point to node left of p
make q point to null
last = q
delete p
count--
return true
end if
between two
-----------
if p <> last p <> first then
make q point to node left of p
make q point to next of p
delete p
count--
return true
end if
*/
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
bool CPhoneBook::deleteByAddress(CPhoneEntry *p)
{
//empty list
if (NULL == first)
return false;
//p is NULL
if (NULL == p)
return false;
//first item or only item
if (p == first)
{
first = first->next;
delete p;
if (NULL == first)
last = NULL;
count--;
return true;
}
//search for node at p
CPhoneEntry *q;
q = first;
while (p != q->next)
{
q = q->next;
if (NULL == q) //node not in list
return false;
}
//node in the list
q->next = p->next;
if (p == last) //last node
last = q;
count--;
delete p;
return true;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testDeleteByAddress(void)
{
cout << "Testing deleteByAddress =\n";
cout << "-------------------------\n";
char ch;
do
{
switch (rand()%7)
{
case 0: //empty list
{
cout << "case 0:\n";
CPhoneBook myList;
CPhoneEntry *p = new CPhoneEntry;
myList.displayWithAddresses();
cout << "Node to be deleted at " << p << endl;
bool result = myList.deleteByAddress(p);
if (result)
cout << "delete successful\n";
else
cout << "delete not successful\n";
myList.displayWithAddresses();
delete p;
break;
}
case 1: //1 p is NULL
{
cout << "case 1:\n";
CPhoneBook myList('r');
CPhoneEntry *p = NULL;
myList.displayWithAddresses();
cout << "Node to be deleted at " << p << endl;
bool result = myList.deleteByAddress(p);
if (result)
cout << "delete successful\n";
else
cout << "delete not successful\n";
myList.displayWithAddresses();
break;
}
case 2: //2 p is not in list
{
cout << "case 2:\n";
CPhoneBook myList('r');
CPhoneEntry *p = new CPhoneEntry;
myList.displayWithAddresses();
cout << "Node to be deleted at " << p << endl;
bool result = myList.deleteByAddress(p);
if (result)
cout << "delete successful\n";
else
cout << "delete not successful\n";
myList.displayWithAddresses();
delete p;
break;
}
case 3: //3 single item
{
cout << "case 3:\n";
CPhoneBook myList(1);
CPhoneEntry *p;
p = myList.addressOfEntryAt(0);
myList.displayWithAddresses();
cout << "Node to be deleted at " << p << endl;
bool result = myList.deleteByAddress(p);
if (result)
cout << "delete successful\n";
else
cout << "delete not successful\n";
myList.displayWithAddresses();
break;
}
case 4: //4 first item
{
cout << "case 4:\n";
CPhoneBook myList(2+rand()%5);
CPhoneEntry *p;
p = myList.addressOfEntryAt(0);
myList.displayWithAddresses();
cout << "Node to be deleted at " << p << endl;
bool result = myList.deleteByAddress(p);
if (result)
cout << "delete successful\n";
else
cout << "delete not successful\n";
myList.displayWithAddresses();
break;
}
case 5: //5 last item
{
cout << "case 5:\n";
int n = 2+rand()%5;
CPhoneBook myList(n);
CPhoneEntry *p;
p = myList.addressOfEntryAt(n-1);
myList.displayWithAddresses();
cout << "Node to be deleted at " << p << endl;
bool result = myList.deleteByAddress(p);
if (result)
cout << "delete successful\n";
else
cout << "delete not successful\n";
myList.displayWithAddresses();
break;
}
case 6: //6 between two
{
cout << "case 6:\n";
int n = 5;
CPhoneBook myList(n);
CPhoneEntry *p;
p = myList.addressOfEntryAt(1 + rand()%3);
myList.displayWithAddresses();
cout << "Node to be deleted at " << p << endl;
bool result = myList.deleteByAddress(p);
if (result)
cout << "delete successful\n";
else
cout << "delete not successful\n";
myList.displayWithAddresses();
break;
}
default:;
}
cin >> ch;
}
while (ch != '0');
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
CPhoneBook & CPhoneBook::operator = (const CPhoneBook &list)
{
if (this->count > 0)
deleteAll();
CPhoneEntry *p;
p = list.first;
while (p != NULL)
{
insertAtEnd(p->name, p->phone, p->group, p->key);
p = p->next;
}
return *this;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testOperatorAssign(void)
{
cout << "Testing operator =\n";
cout << "------------------\n";
char ch;
do
{
CPhoneBook myList('r'), yourList, hisList;
cout << "myList\n" << myList;
hisList = yourList = myList;
cout << "yourList\n" << yourList;
cout << "hisList\n" << hisList;
cin >> ch;
}
while (ch != '0');
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
CPhoneBook::CPhoneBook(const CPhoneBook &aBook)
{
cout << "copy constructor called\n";
count = 0;
first = NULL;
CPhoneEntry *p;
p = aBook.first;
while (p != NULL)
{
insertAtEnd(p->name, p->phone, p->group, p->key);
p = p->next;
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testConstructorCopy(void)
{
cout << "Testing CPhoneBook myList(yourList);\n";
cout << "------------------------------\n";
char ch;
do
{
CPhoneBook myList('r');
cout << myList;
CPhoneBook yourList(myList);
cout << yourList;
cin >> ch;
}
while (ch != '0');
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testInsertAtHead(void)
{
{
CPhoneBook myBook;
myBook.display();
myBook.insertAtHead("John", "231-7000", "friend", 1);
myBook.display();
myBook.insertAtHead("Tom", "231-7001", "enemy", 1);
myBook.display();
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
bool CPhoneBook::insertAtHead(char name[], char phone[], char group[], int key)
{
CPhoneEntry *p;
p = new CPhoneEntry;
if (NULL == p)
return false;
strcpy(p->name, name);
strcpy(p->phone, phone);
strcpy(p->group, group);
p->key = key;
if (NULL == first)
{
first = p;
last = p;
p->next = NULL;
}
else
{
p->next = first;
first = p;
}
count++;
return true;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
// p=first
// if the found return p
// else advance p and go to prev statement
/*
p = first
while p <> NULL
if at p the name we are looking for then
return p
else
advance p
end while
return NULL
*/
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testSearchByName(void)
{
CPhoneBook b1('r');
char tName[MAX_LEN+1];
cout << b1;
for (int i=1; i<=TEST_COUNT; i++)
{
strcpy(tName, testNames[rand()%MAX_NAMES]);
cout << tName << " is at " << b1.searchByName(tName) << endl;
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
CPhoneEntry * CPhoneBook::searchByName(char name[])
{
CPhoneEntry *p;
p = first;
while (p != NULL)
{
if ((strcmp(p->name, name)==0))
return p;
else
p = p->next;
}
return NULL;
}
//CPhoneEntry * CPhoneBook::addressOfEntryAt(int pos)
//Returns the address of node at position [0 to count-1]
//Possibilities return
//------------- ------
//Empty list NULL
//Nonempty
// pos=0 address of first node
// pos [0,count-1] address of the node by advancing pos times
// pos >= count NULL
CPhoneEntry * CPhoneBook::addressOfEntryAt(int pos)
{
if (count <= 0)
return NULL;
if (pos < 0)
return NULL;
if (pos >= count)
return NULL;
CPhoneEntry *p;
p = first;
for (int steps=1; steps<=pos; steps++)
p = p->next;
return p;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
//void CPhoneBook::displayReverse(void)
void CPhoneBook::displayReverse2(void)
{
for (int pos=count-1; pos>=0; pos--)
{
CPhoneEntry *p; //better if put outside the loop
p = addressOfEntryAt(pos);
cout << p->name << ", ";
cout << p->phone << ", ";
cout << p->group << ", ";
cout << p->key << endl;
}
cout << endl;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testDisplayReverse2(void)
{
for (int i=1; i<=TEST_COUNT; i++)
{
cout << "Test #" << i << ": ";
CPhoneBook b1('r');
cout << "Original\n";
b1.display();
cout << "Reverse\n";
b1.displayReverse2();
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
//void CPhoneBook::displayReverse(void)
/* start from the first, display the last node
start from the first, display next to the last
for pos=count to 1 step -1 do the following
point to first
advance pointer pos-1 times
display the pointed node
*/
void CPhoneBook::displayReverse(void)
{
CPhoneEntry *p;
for (int pos=count; pos>0; pos--)
{
p = first;
for (int steps=1; steps<=pos-1; steps++)
p = p->next;
cout << p->name << ", ";
cout << p->phone << ", ";
cout << p->group << ", ";
cout << p->key << endl;
}
cout << endl;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testDisplayReverse(void)
{
for (int i=1; i<=TEST_COUNT; i++)
{
cout << "Test #" << i << ": ";
CPhoneBook b1('r');
cout << "Original\n";
b1.display();
cout << "Reverse\n";
b1.displayReverse();
}
}
////////////////////////////////////////////////////////////
//swap the records
////////////////////////////////////////////////////////////
void swap(CPhoneEntry &e1, CPhoneEntry &e2)
{
char tName[MAX_LEN+1];
char tPhone[14+1];
char tGroup[10+1];
int tKey;
//plug the e1 and e2 at the right places
strcpy(tName, e1.name);
strcpy(e1.name, e2.name);
strcpy(e2.name, tName);
strcpy(tPhone, e1.phone);
strcpy(e1.phone, e2.phone);
strcpy(e2.phone, tPhone);
strcpy(tGroup, e1.group);
strcpy(e1.group, e2.group);
strcpy(e2.group, tGroup);
tKey = e1.key;
e1.key = e2.key;
e2.key = tKey;
}
////////////////////////////////////////////////////////////
//swap the records through the pointers
////////////////////////////////////////////////////////////
void swap(CPhoneEntry *p, CPhoneEntry *q)
{
char tName[MAX_LEN+1];
char tPhone[14+1];
char tGroup[10+1];
int tKey;
strcpy(tName, p->name);
strcpy(p->name, q->name);
strcpy(q->name, tName);
strcpy(tPhone, p->phone);
strcpy(p->phone, q->phone);
strcpy(q->phone, tPhone);
strcpy(tGroup, p->group);
strcpy(p->group, q->group);
strcpy(q->group, tGroup);
tKey = p->key;
p->key = q->key;
q->key = tKey;
}
////////////////////////////////////////////////////////////
//bool CPhoneBook::isSortedByName(void)
////////////////////////////////////////////////////////////
//Go from left to right
//if a pair is found to be out of order
//then return false else return true
bool CPhoneBook::isSortedByName(void)
{
CPhoneEntry *p, *q;
if (first == last)
return true;
p = first;
q = p->next;
while (q != NULL)
{
if ((strcmp(p->name, q->name)>0))
return false;
p = q; // or p = p->next
q = q->next;
}
return true;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testIsSortedByName(void)
{
//for (int i=0; i<TEST_COUNT; i++)
// {
CPhoneBook b1('r');
cout << "Original: " << b1;
if (b1.isSortedByName())
cout << "The list is SORTED\n";
else
cout << "The list is NOT SORTED\n";
b1.sortByName();
cout << "Sorted: "<< b1;
if (b1.isSortedByName())
cout << "The list is SORTED\n";
else
cout << "The list is NOT SORTED\n";
// }
}
////////////////////////////////////////////////////////////
//void CPhoneBook::sortByName(void)
////////////////////////////////////////////////////////////
//Algorithm
/*
do the following
check pairs from left to right and put them in order
until no change in order of the list
if first = last then exit function
do the following
set sorted = true
p = first
q = p->next
while q <> null
if name at p > name at q then
swap records at p and q except the pointers
sorted = false
end if
p = q or p = p->next
q = q->next
end while
while not sorted
*/
void CPhoneBook::sortByName(void)
{
if (first == last) return;
bool sorted;
CPhoneEntry *p, *q;
do
{
sorted = true;
p = first;
q = p->next;
while (q != NULL)
{
if ((strcmp(p->name, q->name)>0))
{
//swap records at p and q except the pointers
//swap(p, q); //using pointers
swap(*p, *q); //using records
sorted = false;
}
p = q; // or p = p->next
q = q->next;
}
}
while (!sorted);
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testSortByName(void)
{
//for (int i=0; i<TEST_COUNT; i++)
// {
CPhoneBook b1('r');
cout << "Original: " << b1;
b1.sortByName();
cout << "Sorted: "<< b1;
// }
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
ostream & operator << (ostream &dan, const CPhoneBook &list)
{
CPhoneEntry *p;
dan << "Phonebook[" << list.count << "]\n";
p = list.first;
while (p != NULL)
{
dan << p->name << ", ";
dan << p->phone << ", ";
dan << p->group << ", ";
dan << p->key << endl;
p = p->next;
};
return dan;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testOperatorOutput(void)
{
//for (int i=0; i<TEST_COUNT; i++)
// {
CPhoneBook b1('r'), b2('r');
cout << b1 << b2;
// }
}
////////////////////////////////////////////////////////////
//Constructor for CPhoneBook
////////////////////////////////////////////////////////////
//'r' random elements
//'u' distinct random elements
//'s' sorted list
//'i' enter from the keyboard
CPhoneBook::CPhoneBook(char ch)
{
cout << "constructor(ch) called\n";
count = 0;
first = NULL;
last = NULL;
if ('r' == ch)
{
char rName[MAX_LEN+1];
char rPhone[14+1];
char rGroup[10+1];
int rKey;
for(int n = rand()%(MAX_COUNT+1); n>0; n--)
{
strcpy(rName, testNames[rand()%MAX_NAMES]);
strcpy(rPhone, testPhones[rand()%MAX_PHONES]);
strcpy(rGroup, testGroups[rand()%MAX_GROUPS]);
rKey = masterKey++;
insertAtEnd(rName, rPhone, rGroup, rKey);
}
}
}
////////////////////////////////////////////////////////////
//Constructor for CPhoneBook
////////////////////////////////////////////////////////////
//'r' random elements
//'u' distinct random elements
//'s' sorted list
//'i' enter from the keyboard
CPhoneBook::CPhoneBook(int n)
{
cout << "constructor(n) called\n";
count = 0;
first = NULL;
last = NULL;
char rName[MAX_LEN+1];
char rPhone[14+1];
char rGroup[10+1];
int rKey;
for( ; n>0; n--)
{
strcpy(rName, testNames[rand()%MAX_NAMES]);
strcpy(rPhone, testPhones[rand()%MAX_PHONES]);
strcpy(rGroup, testGroups[rand()%MAX_GROUPS]);
rKey = masterKey++;
insertAtEnd(rName, rPhone, rGroup, rKey);
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testCPhoneBookConstructor(void)
{
for (int i=0; i<TEST_COUNT; i++)
{
CPhoneBook b1('r');
b1.display();
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
CPhoneBook::~CPhoneBook(void)
{
cout << "destructor called\n";
deleteAll();
}
////////////////////////////////////////////////////////////
//void CPhoneBook::deleteAll(void)
////////////////////////////////////////////////////////////
//deletes all the nodes from the linked list
void CPhoneBook::deleteAll(void)
{
while (first != NULL)
{
last = first->next;
delete first;
first = last;
}
count = 0;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void CPhoneBook::display(void)
{
CPhoneEntry *p;
cout << "Phonebook[" << count << "]\n";
p = first;
while (p != NULL)
{
cout << p->name << ", ";
cout << p->phone << ", ";
cout << p->group << ", ";
cout << p->key << endl;
p = p->next;
};
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void CPhoneBook::displayWithAddresses(void)
{
CPhoneEntry *p;
cout << "Phonebook[" << count << "]\n";
p = first;
while (p != NULL)
{
cout << p->name << ", ";
cout << p->phone << ", ";
cout << p->group << ", ";
cout << p->key << ", ";
cout << "at " << p << endl;
p = p->next;
};
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
bool CPhoneBook::insertAtEnd(char name[], char phone[], char group[], int key)
{
CPhoneEntry *p;
p = new CPhoneEntry;
if (NULL == p)
return false;
strcpy(p->name, name);
strcpy(p->phone, phone);
strcpy(p->group, group);
p->key = key;
p->next = NULL;
if (NULL == first)
{
first = p;
last = p;
}
else
{
last->next = p;
last = p;
}
count++;
return true;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void testInsertAtEnd(void)
{
{
CPhoneBook myBook;
myBook.display();
myBook.insertAtEnd("John", "231-7000", "friend", 1);
myBook.display();
myBook.insertAtEnd("Tom", "231-7001", "enemy", 1);
myBook.display();
}
{
CPhoneBook yourBook;
yourBook.display();
}
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
CPhoneBook::CPhoneBook(void)
{
cout << "constructor called\n";
count = 0;
first = NULL;
last = NULL;
}
////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////
void main(void)
{
//testInsertAtEnd();
//testCPhoneBookConstructor();
//testOperatorOutput();
//testSortByName();
//testIsSortedByName();
//testDisplayReverse();
//testDisplayReverse2();
//testSearchByName();
//testInsertAtHead();
//testConstructorCopy();
//testOperatorAssign();
testDeleteByAddress();
}
|