Objectives: • Implement a linked list • Use structures to create nodes for a lin

Question

Objectives: • Implement a linked list • Use structures to create nodes for a linked list • Use pointers to manipulate a linked list Problem: Doc Brown has configured the DeLorean to go back to the days of the Roman Empire. Unfortunately, the Roman Empire does not use Arabic numerals which is going to make it difficult for Doc to do the proper calculations he needs to get back home. Before he heads back in time, he wants you to create a Roman numeral converter for him.

• Roman numerals are as follows: o 1 = I o 5 = V o 10 = X o 50 = L o 100 = C o 500 = D o 1000 = M • Determine if the input given is Roman numeral or Arabic. • Convert from given type to the missing type. • All numbers will be in the range of 1 – 4999. • Store the file contents in a linked list. o Add the node to the beginning of the list • All manipulation of the data will happen in the linked list. o Convert each piece of data to its unlisted counterpart • Write the contents of the linked list back to the file at the end of the program. • The file may contain invalid data. o If invalid data is identified, ignore the entry in the file. • Invalid data: o Arabic numeral outside the given rage. o Invalid characters in Roman numeral. o Invalid characters in Arabic numeral. • User will be able to search and sort the data. • Use a linear search o Search can be for Arabic or Roman numeral o Do not ask user what type of numeral to search for (-5 points if user is asked) User can type in Arabic or Roman numeral You have to figure out what they typed • Implement sorting algorithm of your choice o Sorting algorithm will move nodes (-10 points) o Do not exchange node data o All sorts will sort in ascending order Arabic: smallest to largest number Roman: alphabetical • Comment your code generously. Refer to the grading rubric for more details. • Use as few variables as possible. Don’t waste memory holding a calculation just so you can print it out one time. User Interface and Input: Create a simple menu interface allowing the user to search and sort the data. The menu will consist of 3 options: 1. Search 2. Sort 3. Exit If the user selects the sort option, provide a sub menu: 1. Sort by Roman numeral 2. Sort by Arabic numeral All user input will be valid. Remember that the file input may not be valid. File Structure: • The file will contain an unknown quantity of numbers to convert. • Each number will be on a separate line. • The number will be either Arabic or Roman • Each line of the file will have the same format o Roman numeral field – 16 characters • Fixes the 4888 issue Arabic numeral field – 4 characters • The last line may or may not have a new line at the end • Only one of the fields will hold a value on each line o If a field does not hold a value, it will contain all spaces. o If the Roman numeral field contains a space as the first character, you know that the line contains an Arabic numeral Output: If the user enters the option to search, state whether the item was found or not found ( ) in the console window. If the user enters the option to sort, display the sorted values to the console window. Only display the values for the type of data sorted. For example, if Roman numerals are sorted, only display the Roman numerals in alphabetic order. At the end of the program, write the linked list back to the file used for input.

Explanation / Answer

Source code:-
=======================
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
int count();
void display(struct node *r);
struct node
{
int data;
struct node *next;
}*head;
void append(int num)
{
struct node *temp,*right;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=num;
right=(struct node *)head;
while(right->next != NULL)
right=right->next;
right->next =temp;
right=temp;
right->next=NULL;
}
void add( int num )
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
if(head== NULL)
{
head=temp;
head->next=NULL;
}
else
{
temp->next=head;
head=temp;
}
}
void addafter(int num, int loc)
{
int i;
struct node *temp,*left,*right;
right=head;
for(i=1;i<loc;i++)
{
left=right;
right=right->next;
}
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
left->next=temp;
left=temp;
left->next=right;
return;
}
void insert(int num)
{
int c=0;
struct node *temp;
temp=head;
if(temp==NULL)
{
add(num);
}
else
{
while(temp!=NULL)
{
if(temp->data<num)
c++;
temp=temp->next;
}
if(c==0)
add(num);
else if(c<count())
addafter(num,++c);
else
append(num);
}
}
int delete_n(int num)
{
struct node *temp, *prev;
temp=head;
while(temp!=NULL)
{
if(temp->data==num)
{
if(temp==head)
{
head=temp->next;
free(temp);
return 1;
}
else
{
prev->next=temp->next;
free(temp);
return 1;
}
}
else
{
prev=temp;
temp= temp->next;
}
}
return 0;
}
void display(struct node *r)
{
r=head;
if(r==NULL)
{
return;
}
while(r!=NULL)
{
printf("%d ",r->data);
r=r->next;
}
printf(" ");
}
int count()
{
struct node *n;
int c=0;
n=head;
while(n!=NULL)
{
n=n->next;
c++;
}
return c;
}
void sort()
{
struct node *ptr, *s;
int value;
if (head == NULL)
{
cout<<"The List is empty"<<endl;
return;
}
ptr = head;
while (ptr != NULL)
{
for (s = ptr->next;s !=NULL;s = s->next)
{
if (ptr->data < s->data)
{
value = ptr->data;
ptr->data = s->data;
s->data = value;
}
}
ptr = ptr->next;
}
}
void Linear_search()
{
int value, pos = 0;
bool flag = false;
if (head == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the value to be searched: ";
cin>>value;
struct node *s;
s = head;
while (s != NULL)
{
pos++;
if (s->data == value)
{
flag = true;
cout<<"Element "<<value<<" is found at position "<<pos<<endl;
}
s = s->next;
}
if (!flag)
cout<<"Element "<<value<<" not found in the list"<<endl;  
}
int main()
{
int i,num;
int last_item;
struct node *n;
head=NULL;
while(1)
{
cout<<" Linked List Operations "<<endl;
cout<<"========================= "<<endl;
cout<<"1.Insert"<<endl;
cout<<"2.Display"<<endl;
cout<<"3.Size"<<endl;
cout<<"4.delete_n"<<endl;
cout<<"5.search Element"<<endl;
cout<<"6.Sort the Elements:"<<endl;
cout<<"7.Exit "<<endl;
cout<<"Enter your choice:"<<endl;
if(scanf("%d",&i)<=0)
{
cout<<"Enter only an Integer"<<endl;
exit(0);
}
else
{
switch(i)
{
case 1:
cout<<"Enter the number to insert"<<endl;
scanf("%d",&num);
insert(num);
break;
case 2:
if(head==NULL)
{
cout<<"List is Empty"<<endl;
}
else
{
cout<<"Element(s) in the list are:"<<endl;
}
display(n);
break;
case 3:
cout<<"Size of the list is:"<<count()<<endl;
break;
case 4:
if(head==NULL)
cout<<"List is Empty "<<endl;
else
{
cout<<"Enter the number to delete_n"<<endl;
scanf("%d",&num);
if(delete_n(num))
cout<<num<<" deleted successfully"<<endl;
else
cout<<num<<"is not found in the list"<<endl;
}
break;
case 5:
Linear_search();
break;
case 6:
sort();
break;
case 7:
return 0;
default:
cout<<"Invalid option"<<endl;
}
}
}
return 0;
}


Sample Output:-
=========================
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
1
Enter the number to insert
40
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
1
Enter the number to insert
50
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
1
Enter the number to insert
20
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
2
Element(s) in the list are:
20 40 50
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
6
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
2
Element(s) in the list are:
50 40 20
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
5
Enter the value to be searched: 40
Element 40 is found at position 2
Linked List Operations
=========================
1.Insert
2.Display
3.Size
4.delete_n
5.search Element
6.Sort the Elements:
7.Exit
Enter your choice:
7
--------------------------------
Process exited after 58.35 seconds with return value 0
Press any key to continue . . .

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.