Please help me with this C++ homework. Write a class that implements an ordered
ID: 3668398 • Letter: P
Question
Please help me with this C++ homework.
Write a class that implements an ordered linked list based on the following UML diagram:
The { query } tag indicates the method is an accessor.
The class contains a single attribute, head. Head is a pointer to the first node in the linked list.
The class contains several required methods and one extra credit method.
The required methods are:
Constructor - initializes head to null.
Destructor - responsible for deallocating the list from memory
Insert - Accepts a character argument, inserts a node containing the character into the linked list. Insert preserves the order of the linked list. THe linked list orderes the nodes in ascending order. For example, Head -> A -> E -> O -> U -> NULL.
remove - Accepts a charater argument, then searches the linked list for the first matching node and removes it. Does nothing if a matching node is not found.
search -- Accepts a character argument, then searches for a matching node in the linked list. Returns true if found, false otherwise.
print -- displays the contents of the linked list to the screen.
size -- returns the number of nodes with in the linked list.
write -- writes the contents of the linked list to a file named "list.dat". Returns true if the file is successfully written, false othewise. Each nodes value should be written to the file without whitespace. For example, the linkedlistmentioned in the insert method would appear as AEOU within the file.
read -- read the "list.dat" file, and constructs a linked list using the data. Returns true if linked list is succesfully created, false otherwise.
destroy -- removes the linked list from memory. Could be called by the destructor.
The extra credit methods are:
reverse -- accepts no arguments, merely calls the overloaded reverse method.
reverse -- accepts a node pointer as an argument. Uses recursion to display the contents of the linked list in reverse order. For example, the list mentioned in the insert description would be displayed as : Head-> U -> O -> E -> A -> NULL
The extra credit is worth 1 point.
Demonstrate your class in a menu-driven program.
The program should prompt the user for a selection from the following choices:
(C)lear
when the user selects this option, the linked list is destroyed.
(D)elete
Selecting this option prompts the user for a character to remove from the linked list, and then attempts to remove it.
(G)et
Loads the linked list from disk
(I)nsert
Prompts the user for a character to insert into the linked list, then the insertion is performed.
(L)ength
Returns a count of the number of nodes currently in the linked list
(M)enu
Displays a menu of options
(P)rint
Displays the contents of the linked list
(Q)uit
Terminates the program.
(R)everse
Extra credit option: displays the linked list in reverse order.
(S)earch
Asks the user for a value to search for. Indicates whether the value has been found or not.
(W)rite;
Writes the linked list to disk.
The program should continue prompting the user for selections and processing them until the user select Quit. Use your object methods to process each request.
Some screenshots:
Compiled solutions to this problem are attached for Windows 64-bit systems.
The extra credit is worth 1 point.
Explanation / Answer
#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;
typedef struct node node;
struct node
{
char name;
node * next;
};
node *newNode(char new_data)
{
node* new_node =new node();
/* put in the data */
new_node->name = new_data;
new_node->next = NULL;
return new_node;
}
void printList(node *head)
{
node *temp=new node();
temp=head;
while(temp!=NULL)
{
cout<<" Name is "<<temp->name;
temp=temp->next;
}
}
void sortedInsert(node** head_ref,node* new_node)
{
node* current;
/* Special case for the head end */
if (*head_ref == NULL || (*head_ref)->name >= new_node->name)
{
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
current = *head_ref;
while (current->next!=NULL &&
current->next->name < new_node->name)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
}
}
void findLength(node *head)
{
int length=0;
node *temp=new node();
temp=head;
while(temp!=NULL)
{
temp=temp->next;
length++;
}
cout<<" Total Length is "<<length<<" ";
}
void GetNthElement(node *head,int val)
{
int count=0;
node *temp=head;
while(temp!=NULL)
{
count++;
temp=temp->next;
if(count==val)
cout<<" the data at given position is "<<temp->name;
}
}
int main()
{
int choice;
int position;
node* head = NULL;
node *new_node = newNode('A');
sortedInsert(&head, new_node);
new_node = newNode('X');
sortedInsert(&head, new_node);
new_node = newNode('T');
sortedInsert(&head, new_node);
new_node = newNode('P');
sortedInsert(&head, new_node);
new_node = newNode('M');
sortedInsert(&head, new_node);
new_node = newNode('B');
sortedInsert(&head, new_node);
for(;;)
{
cout<<" Enter your choice"<<" ";
cout<<"1.search"<<" ";
cout<<"2.print List"<<" ";
cout<<"3.size"<<" ";
cout<<"4.Exit"<<" ";
cout<<"Enter your choice"<<" ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the position whose element you want to find";
cin>>position;
GetNthElement(head,position);
break;
case 2:
printList(head);
break;
case 3:
findLength(head);
break;
case 4:
exit(0);
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.