Advanced Software Engineering (SOFT40051) - Data Structure C++ Program

This C++ program implements dynamic data structures, specifically linked lists and stacks, allowing users to select and manipulate them through a menu-driven interface. The program allocates memory dynamically based on user input and provides options to add objects, display contents, save data to files, and perform linear searches. It includes a class diagram illustrating object insertion in a linked list, along with detailed test cases to validate functionality. The program's strengths lie in its use of dynamic structures and user-selectable data types, while weaknesses include potential memory consumption and slower insertion/deletion operations. The code utilizes templates and friend classes for data structure creation and file I/O, enabling users to compare the performance of linear search on different data structures. The program's main functionality centers around template usage, class creation for linked lists, and file data dumping. The provided code snapshot includes the main menu and the complete source code listing.

Test Plan and Results:
As per the given requirement in the assignment, There will be 7 options available in the menu and user
will be asked to specify the data structure and based on the selection the memory is allocated and the
value is stored in it. The two data structure which are used are linked list and stack.
Class Diagram:
Below is the sequence diagram for insertion of object in the linked list. The flow will be the user is
prompted to enter the object type, if selected Linked list then memory is allocated, the user is prompted
to enter the value and if entered then value is stored in the memory. Once done then the object is
added.

Following are the test case for the program:
Test case 1: Stack object needs to be created and 5 is added into it.
Expected Result: User is prompted to select the type and then for values.
The value should be entered in the stack object.
Test case 2: Linked List object needs to be created and 5 is added into it.
Expected Result: User is prompted to select the type and then for values.
The value should be entered in the Linked list object.
Test case 3: Display the content of the Linked List
Expected Result: User is prompted to select the type and then all the values of Linked List will be
displayed and it should not display the content of Stack.
Test case 4: Display the content of the Stack
Expected Result: User is prompted to select the type and then all the values of Linked List will be
displayed and it should not display the content of Linked List.
Test case 5: Save file with the content of the Linked List
Expected Result: User is prompted to select the type and then all the values of Linked List will be saved
in the file and it should not save the content of Stack.
Test case 6: Save file with the content of the Stack
Expected Result: User is prompted to select the type and then all the values of Stack will be saved in the
file and it should not save the content of Linked List.
Test case 7: Quit the Program
Expected Result: It will exit the program
Test case 8: Linear Search option is selected then it will display the time for Linked List and Stack.
Expected Result: It will show the time.

Evaluation of the Program:
Strength Of the program:
The main strength of this program is that dynamic data structures vector and stack are used and it
provides user of the program to select anyone of it. This program does not allocate the memory until
unless the type of data structure is chosen. The strength of the program is that it provides option to user
of the program to enter manually the type of object and store in the data structure or insert from the
file (there is no restriction on the number of objects). Additionally user of the program can by himself
validate which data structure is better by comparing the execution of linear search on each of the data
structure. This program every time ask user to provide the name of the data structure on which the
action needs to be performed. In this way user can experiment on both the type of data structures.
Weakness of the program:
Both the stack and vector are objects and hence consuming more memory as compared to arrays.
Because of dynamic memory allocation nature if not all memory is used then it leads to complete
wastage of the memory. Insertion and deletions are slow. This program in every option ask again and
again the data structure on which the operation need to be performed.
Performance of data structure with linear search:
If we compare both the data structure then the performance of linear search is good in Stack as
compared to vector. The reason behind is that stack has first pop and push operation as compared to
vector which slow performance at tail. The snapshot is attached below.
Main Functionality in the program:
The important aspect in the program is the template usage, the class for Link and List are created and
which help to create the data structure for Linked List. The methods are defined inside the List class and
the list class is made friend class in Link class. Hence the object of Link class is created and made used of
this data structure. Below is the code snapshot.

The important functionality is to dump the data structure in the file:
Here the object of link is created and file is opened using Ofstream and then the linked list is traversed
and the X (value) is written in the file and then file is saved.

Main Menu:
To create a Main Menu the while statement is used which has case statements based on the input it
trigger the method.
Snapshots of the program:

Appendix: Full Source Code Listing:
#include <iostream>
#include <stack>
#include <fstream>
#include <string>
#include <ctime>
#include <vector>
using namespace std;
class Link
{
friend class List;
// Allows class List to access Link’s private data
private:
int X;
Link* Next;
public:
Link(int);
};
class List
{
private:
Link* head;
public:
List();
int add(int x);
void display();
void writeToFile(char filename[100]);

std::vector<int> getVector();
};
Link::Link(int px)
{
X = px;
Next = 0;
}
List::List()
{
// 'head' points to 0 initially and when the list is empty.
// Otherwise 'head' points to most recently
// added object head
head = 0;
}
void List::display()
{
Link* temp; // 'temp' used to iterate through the list
// 'head' points to last object added
// Iterate back through list until last pointer (which is 0)
for (temp = head; temp != 0; temp = temp->Next)
{
cout << "Value of object is " << temp->X << endl;
}
}
std::vector<int> List::getVector()
{

std::vector<int> vectorInt;
Link* temp; // 'temp' used to iterate through the list
// 'head' points to last object added
// Iterate back through list until last pointer (which is 0)
for (temp = head; temp != 0; temp = temp->Next)
{
vectorInt.push_back(temp->X);
}
return vectorInt;
}
void List::writeToFile(char filename[100])
{
Link* temp; // 'temp' used to iterate through the list
// 'head' points to last object added
// Iterate back through list until last pointer (which is 0)
ofstream myfile(filename);
if (myfile.is_open())
{
for (temp = head; temp != 0; temp = temp->Next)
{
myfile << "Value of object is " << temp->X << endl;
}
myfile.close();
}
else cout << "Unable to open file";

}
int List::add(int x)
{
// pointer 'temp' used to instantiate objects to add to list
Link* temp;
// memory allocated and the object is given a value
temp = new Link(x);
if (temp == 0) // check new succeeded
{
return 0; // shows error in memory allocation
}
// the pointer in the object is set to whatever 'head' is pointing to
temp->Next = head;
// 'head' is re-directed to point to the last created object
head = temp;
return 1;
}
int linearSearch(int searchElement, vector<int> data)
{
int low = 0, high = data.size() - 1;
int position = low;
int location = -1;
do
{