|
Project |
//prog05v7.cpp //CSLL Singly linked list class project |
|
Include files |
#include <iostream.h> #include <string.h> #include <stdlib.h> #include <time.h>
|
|
Constants |
const int MAX_LEN = 10; const int MAX_SIZE = 10;
const char *testData[] = {"Bob", "Tom", "Ann", "Ron", "Ben", "Ken", "Rob", "Sam", "Don", "Dan"};
const int MAX_DATA = sizeof(testData)/sizeof(testData[0]);
|
|
Node structure |
struct NodeType { char name[MAX_LEN+1]; NodeType *next; };
|
|
Class definition |
class CSLL { private: public: CSLL &operator = (const CSLL &list); void displayDistinct(void) const; void displayPhysical(void) const; void insertAtHead(const char s[]); void insertAtTail(const char s[]); };
|
|
Test function prototypes |
void testConstructorIntN(void); void testConstructorCharD(void); void testConstructorCharR(void); void testConstructorDefault(void); void testConstructorCopy(void); void testDisplayDistinct(void); void testDisplayPhysical(void); void testOperatorAssign(void);
|
|
Main function |
void main(void) { char ch; srand(time(NULL));
do { cout << "TEST CENTER\n"; cout << "===========\n"; cout << "1 constructorDefault\n"; cout << "2 constructorCharR\n"; cout << "3 constructorIntN\n"; cout << "4 constructorCopy\n"; cout << "5 constructorCharD\n"; cout << "6 destructor\n"; cout << "7 insertAtHead(name)\n"; cout << "8 insertAtTail(name)\n"; cout << "9 displayPhysical()\n"; cout << "a removeAll()\n"; cout << "b operator = \n"; cout << "c displayDistinct()\n"; cout << "d has(name)\n"; cout << "Enter your choice (0 to quit): "; cin >> ch; cout << ch << endl;
switch (ch) { case '1': testConstructorDefault(); break; case '2': testConstructorCharR(); break; case '3': testConstructorIntN(); break; case '4': testConstructorCopy(); break; case '5': testConstructorCharD(); break; case '6': testDestructor(); break; case '7': testInsertAtHead(); break; case '8': testInsertAtTail(); break; case '9': testDisplayPhysical(); break; case 'a': testRemoveAll(); break; case 'b': testOperatorAssign(); break; case 'c': testDisplayDistinct(); break; case 'd': testHas(); break; default:; } } while (ch != '0');
}
|
|
Sample run |
TEST CENTER =========== 1 constructorDefault 2 constructorCharR 3 constructorIntN 4 constructorCopy 5 constructorCharD 6 destructor 7 insertAtHead(name) 8 insertAtTail(name) 9 displayPhysical() a removeAll() b operator = c displayDistinct() d has(name) Enter your choice (0 to quit):
|
|
Member |
|
|
Description |
It is a private data member. It points to the first node (front) in the singly linked list. It is set to null when the list is empty.
|
|
Member |
|
|
Description |
It is a private data member. It holds the number of nodes in the singly linked list. It is set to 0 when the list is empty.
|
|
Member |
|
|
Description |
Constructs a singly linked list with n nodes in it. Nodes have values randomly selected from the testData array of names.
|
|
Diagram |
|
|
Algorithm |
Set head to null Set count to 0 While n > 0 do the following Insert a random name from testData to the linked list Decrease value of n by 1 End while
|
|
Function definition |
CSLL::CSLL(int n) { head = NULL; count = 0; while (n>0) { insertAtHead(testData[rand()%MAX_DATA]); n--; } }
|
|
Test function |
void testConstructorIntN(void) { cout << "Testing CSLL myList(n);\n"; cout << "-----------------------\n"; char ch; do { int n = rand()%(MAX_SIZE+1); CSLL myList(n); myList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing CSLL myList(n); ----------------------- List[5]: Bob Don Tom Sam Ben List[3]: Sam Ben Ron List[5]: Ben Tom Ann Bob Dan List[9]: Bob Tom Ron Don Don Don Ron Dan Bob
|
|
Member |
|
|
Description |
Constructs a singly linked list with random number of nodes in it. Nodes have values randomly selected from the testData array of names. If the value of the parameter is ‘r’ then the list created has random names in it. If the value for the parameter is ‘d’ then only the distinct names are inserted in the list. |
|
Diagram |
|
|
Algorithm |
Set head to null Set m to a random integer Set count to 0
If ch is ‘r’ then While m > 0 do the following Insert a random name from testData to the linked list Decrease value of m by 1 End while End if
If ch is ‘d’ then While m > 0 do the following Set tName to a random name from testData If tName is not in the list then Insert tName to the list End if Decrease value of m by 1 End while End if
|
|
Function definition |
CSLL::CSLL(char ch) { head = NULL; count = 0; if ('r' == ch) { int m = rand()%MAX_SIZE; while (m>0) { insertAtHead(testData[rand()%MAX_DATA]); m--; } }
if ('d' == ch) { char tName[MAX_LEN+1]; int m = rand()%MAX_SIZE; while (m>0) { strcpy(tName, testData[rand()%MAX_DATA]); if (!has(tName)) insertAtHead(tName); m--; } } }
|
|
Test function |
void testConstructorCharD(void) { cout << "Testing CSLL myList('d');\n"; cout << "-------------------------\n"; char ch; do { CSLL myList('d'); myList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing CSLL myList('d'); ------------------------- List[6]: Ann Sam Bob Rob Don Ken List[3]: Bob Ken Rob List[3]: Ron Ben Bob List[7]: Bob Don Ben Tom Dan Sam Ron
|
|
Test function |
void testConstructorCharR(void) { cout << "Testing CSLL myList('r');\n"; cout << "-------------------------\n"; char ch; do { CSLL myList('r'); myList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing CSLL myList('r'); ------------------------- List[8]: Rob Ann Bob Ron Ann Ron Rob Ron List[5]: Rob Ron Ben Rob Ron List[6]: Don Dan Ken Ben Dan Ken List[3]: Tom Sam Bob
|
|
Member |
|
|
Description |
Creates an empty singly linked list.
|
|
Diagram |
|
|
Algorithm |
Set head to null Set count to 0
|
|
Function definition |
CSLL::CSLL(void) { head = NULL; count = 0; }
|
|
Test function |
void testConstructorDefault(void) { cout << "Testing CSLL myList;\n"; cout << "--------------------\n"; char ch; do { CSLL myList; myList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing CSLL myList; -------------------- List[0]: List[0]: List[0]: List[0]:
|
|
Member |
|
|
Description |
Copy constructor creates a copy of the singly linked list. The resulting copy has a copy of all the nodes of the list.
|
|
Diagram |
|
|
Algorithm |
Set count to 0 Set head to null Set p to the head of the supplied list While p <> null do the following Insert value of node pointed to by p at tail of self list Advance p End while
|
|
Function definition |
CSLL::CSLL(const CSLL &list) { count = 0; head = NULL;
NodeType *p;
p = list.head;
while (p != NULL) { insertAtTail(p->name); p = p->next; } }
|
|
Test function |
void testConstructorCopy(void) { cout << "Testing CSLL myList(yourList);\n"; cout << "------------------------------\n"; char ch; do { CSLL myList('r'); myList.display(); CSLL yourList(myList); yourList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing CSLL myList(yourList); ------------------------------ List[9]: Ann Ann Ken Rob Tom Ron Tom Ann Bob List[9]: Ann Ann Ken Rob Tom Ron Tom Ann Bob List[5]: Ann Ron Sam Sam Tom List[5]: Ann Ron Sam Sam Tom List[4]: Don Ron Don Don List[4]: Don Ron Don Don List[9]: Dan Ron Bob Bob Dan Rob Ken Ann Ann List[9]: Dan Ron Bob Bob Dan Rob Ken Ann Ann
|
|
Member |
|
|
Function description |
Destructs the singly linked list by removing all the nodes from it.
|
|
Diagram |
|
|
Algorithm |
While head <> null do the following Set p to head Advance head Release memory pointed to by p End while Set count to 0
|
|
Function definition |
CSLL::~CSLL(void) { NodeType *p; while (head != NULL) { p = head; head = head->next; delete p; } count = 0; }
|
|
Test function |
{ cout << "Testing destructor\n"; cout << "------------------\n"; char ch; do { CSLL *myListP; myListP = new CSLL('r'); myListP->display(); delete myListP; cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing destructor ------------------ List[3]: Ron Don Ron List[1]: Ron List[8]: Ann Sam Ron Ken Ann Sam Bob Bob List[4]: Ann Ben Ron Ron
|
|
Member |
void CSLL::display(void) const;
|
|
Description |
Displays the contents of the singly linked list.
|
|
Diagram |
|
|
Algorithm |
Set ptr to head While ptr <> null do the following Display the value of the node pointed to by ptr Advance ptr End while
|
|
Function definition |
void CSLL::display(void) const { NodeType *ptr;
cout << "List[" << count << "]: ";
ptr = head; while (ptr != NULL) { cout << ptr->name << ' '; ptr = ptr->next; }
cout << endl; }
|
|
Member |
void CSLL::displayDistinct(void) const;
|
|
Description |
Displays only the distinct node values from the singly linked list.
|
|
Diagram |
|
|
Algorithm |
If the list is empty then exit function Set p to head Display the node value pointed to by p Advance p While p <> null do the following If node pointed to p has not been visited yet then Display the node value pointed to by p End if Advance p End while
|
|
Function definition |
void CSLL::displayDistinct(void) const { cout << "List distinct: ";
if (0 == count) { cout << endl; return; }
NodeType *p, *q; bool visited;
p = head; cout << p->name << ' '; p = p->next;
while (p != NULL) { q = head; visited = false; while (q != p) { if (strcmp(p->name, q->name) == 0) visited = true; q = q->next; }
if (!visited) cout << p->name << ' ';
p = p->next; }
cout << endl; }
|
|
Test function |
void testDisplayDistinct(void) { cout << "Testing displayDistinct()\n"; cout << "-------------------------\n"; char ch; do { int n = rand()%(MAX_SIZE+1); CSLL myList(n); myList.display(); myList.displayDistinct(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing displayDistinct() ------------------------- List[6]: Rob Ken Dan Rob Tom Ken List distinct: Rob Ken Dan Tom List[1]: Ann List distinct: Ann List[4]: Rob Bob Rob Bob List distinct: Rob Bob List[6]: Bob Ron Ken Bob Ron Bob List distinct: Bob Ron Ken
|
|
Member |
void CSLL::displayPhysical(void) const;
|
|
Description |
Displays the node values and their addresses in the singly linked list.
|
|
Diagram |
|
|
Algorithm |
Set ptr to head While ptr <> null do the following Display p and the node value pointed to by p Advance p End while
|
|
Function definition |
void CSLL::displayPhysical(void) const { NodeType *ptr;
cout << "List[" << count << "]:\n"; cout << "address name\n"; cout << "---------- ----\n";
ptr = head; while (ptr != NULL) { cout << ptr << ' ' << ptr->name << endl; ptr = ptr->next; } cout << endl; }
|
|
Test function |
void testDisplayPhysical(void) { cout << "Testing displayPhysical()\n"; cout << "-------------------------\n"; char ch; do { int n = rand()%(MAX_SIZE+1); CSLL myList(n); myList.display(); myList.displayPhysical(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing displayPhysical() ------------------------- List[1]: Sam List[1]: address name ---------- ---- 0x00791E20 Sam
List[4]: Dan Sam Ron Ann List[4]: address name ---------- ---- 0x00791D60 Dan 0x00791DA0 Sam 0x00791DE0 Ron 0x00791E20 Ann
List[4]: Ben Tom Ann Ben List[4]: address name ---------- ---- 0x00791D60 Ben 0x00791DA0 Tom 0x00791DE0 Ann 0x00791E20 Ben
List[6]: Ben Bob Bob Tom Tom Sam List[6]: address name ---------- ---- 0x00791CE0 Ben 0x00791D20 Bob 0x00791D60 Bob 0x00791DA0 Tom 0x00791DE0 Tom 0x00791E20 Sam
|
|
Member |
bool CSLL::has(const char s[]);
|
|
Description |
Checks if the singly linked list has a node whose value matches with the given value in s.
|
|
Diagram |
|
|
Algorithm |
Set p to head While p <> null do the following If s = value of the node pointed to by p then Return true End if Advance p End while
Return false
|
|
Function definition |
bool CSLL::has(const char s[]) { NodeType *p; p = head; while (p != NULL) { if (strcmp(p->name, s)==0) return true; p = p->next; }
return false; }
|
|
Test function |
{ cout << "Testing has(name)\n"; cout << "-----------------\n"; char ch; do { CSLL myList('r'); myList.display(); char tName[MAX_LEN+1]; strcpy(tName, testData[rand()%MAX_DATA]); if (myList.has(tName)) cout << tName << " is in the list\n"; else cout << tName << " is NOT in the list\n"; cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing has(name) ----------------- List[6]: Ron Dan Ann Ken Rob Don Sam is NOT in the list List[2]: Ken Bob Sam is NOT in the list List[1]: Tom Ken is NOT in the list List[1]: Dan Dan is in the list
|
|
Member |
void CSLL::insertAtHead(const char s[]);
|
|
Description |
For a given value creates a node and inserts it at the head (front) of the singly linked list.
|
|
Diagram |
|
|
Algorithm |
Set p to the address of a new node block Move s to the name field of the new node Set next field of the new node to head Set head to p Increase count by 1
|
|
Function definition |
void CSLL::insertAtHead(const char s[]) { NodeType *p; p = new NodeType; if (NULL == p) { cout << "Out of memory\n"; return; }
strcpy(p->name, s); p->next = head; head = p; count++; }
|
|
Test function |
{ cout << "Testing insertAtHead(name)\n"; cout << "--------------------------\n"; char ch; do { CSLL myList('r'); myList.display(); char tName[MAX_LEN+1]; strcpy(tName, testData[rand()%MAX_DATA]); myList.insertAtHead(tName); cout << "After inserting " << tName << " at head\n"; myList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing insertAtHead(name) -------------------------- List[4]: Ben Tom Ken Tom After inserting Ben at head List[5]: Ben Ben Tom Ken Tom List[3]: Sam Ron Ken After inserting Bob at head List[4]: Bob Sam Ron Ken List[1]: Dan After inserting Ann at head List[2]: Ann Dan List[3]: Rob Ron Dan After inserting Dan at head List[4]: Dan Rob Ron Dan
|
|
Member |
void CSLL::insertAtTail(const char s[]);
|
|
Description |
For a given value creates a node and inserts it at the tail (end) of the singly linked list.
|
|
Diagram |
|
|
Algorithm |
Set p to the address of a new node block Set last to the address of the last node in the list Move s to the name field of the new node Set next field of the new node to null Set next field of the last node to p Increase count by 1
|
|
Function definition |
void CSLL::insertAtTail(const char s[]) { NodeType *p; p = new NodeType; strcpy(p->name, s); p->next = NULL;
if (NULL == head) head = p; else { NodeType *last; last = head; while (last->next != NULL) { last = last->next; } last->next = p; } count++; }
|
|
Test function |
{ cout << "Testing insertAtTail(name)\n"; cout << "--------------------------\n"; char ch; do { CSLL *myListP; myListP = new CSLL('r'); myListP->display(); char tName[MAX_LEN+1]; strcpy(tName, testData[rand()%MAX_DATA]); myListP->insertAtTail(tName); cout << "After inserting " << tName << " at tail\n"; myListP->display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing insertAtTail(name) -------------------------- List[8]: Ann Rob Ron Don Bob Dan Ann Rob After inserting Don at tail List[9]: Ann Rob Ron Don Bob Dan Ann Rob Don List[1]: Bob After inserting Ron at tail List[2]: Bob Ron List[3]: Sam Dan Dan After inserting Ron at tail List[4]: Sam Dan Dan Ron List[8]: Tom Don Ben Ken Dan Ken Tom Ben After inserting Bob at tail List[9]: Tom Don Ben Ken Dan Ken Tom Ben Bob
|
|
Member |
CSLL &CSLL::operator = (const CSLL &list);
|
|
Description |
Overloads the assignment operator
|
|
Diagram |
|
|
Algorithm |
If the self list is not empty then remove all the nodes from it end if
set p to the head of the supplied list while p <> null do the following insert the node value pointed to by p to the self list advance p end while
return self list
|
|
Function definition |
CSLL &CSLL::operator = (const CSLL &list) { if (this->count > 0) removeAll();
NodeType *p; p = list.head;
while (p != NULL) { insertAtTail(p->name); p = p->next; }
return *this; }
|
|
Test function |
{ cout << "Testing operator =\n"; cout << "------------------\n"; char ch; do { int n = rand()%(MAX_SIZE+1); CSLL myList(n); myList.display(); CSLL yourList, hisList; hisList = yourList = myList; yourList.display(); hisList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing operator = ------------------ List[10]: Ann Don Dan Ann Don Rob Sam Bob Ken Bob List[10]: Ann Don Dan Ann Don Rob Sam Bob Ken Bob List[10]: Ann Don Dan Ann Don Rob Sam Bob Ken Bob List[5]: Bob Rob Ben Sam Ben List[5]: Bob Rob Ben Sam Ben List[5]: Bob Rob Ben Sam Ben List[10]: Ron Tom Bob Sam Dan Don Dan Ben Dan Ben List[10]: Ron Tom Bob Sam Dan Don Dan Ben Dan Ben List[10]: Ron Tom Bob Sam Dan Don Dan Ben Dan Ben List[8]: Don Bob Rob Ken Dan Ben Bob Tom List[8]: Don Bob Rob Ken Dan Ben Bob Tom List[8]: Don Bob Rob Ken Dan Ben Bob Tom
|
|
Member |
|
|
Description |
Removes all the nodes from the list.
|
|
Diagram |
|
|
Algorithm |
While head <> null do the following Set p to head Advance head Release the node pointed to by p End while
|
|
Function definition |
void CSLL::removeAll(void) { NodeType *p; while (head != NULL) { p = head; head = head->next; delete p; } count = 0; }
|
|
Test function |
{ cout << "Testing removeAll()\n"; cout << "-------------------\n"; char ch; do { int n = rand()%(MAX_SIZE+1); CSLL myList(n); myList.display(); myList.removeAll(); myList.display(); cin >> ch; } while (ch != '0'); }
|
|
Sample run |
Testing removeAll() ------------------- List[1]: Bob List[0]: List[7]: Ben Bob Ron Don Don Don Tom List[0]: List[5]: Ann Ann Ron Don Tom List[0]: List[4]: Bob Sam Sam Ben List[0]:
|
