Implement the following specification of UnsortedType using a circular linked li
ID: 3562073 • Letter: I
Question
Implement the following specification of UnsortedType using a circular linked list as the implementation structure. template struct NodeType; /* Assumption: ItemType is a type for which the operators "<" and "==" are definedeither an appropriate built-in type or a class that overloads these operators. */ template class UnsortedType { public: // Class constructor, destructor, and copy constructor UnsortedType(); ~UnsortedType(); UnsortedType(const UnsortedType&); void operator=(UnsortedType); bool IsFull() const; // Determines whether list is full. // Post: Function value = (list is full) int GetLength() const; // Determines the number of elements in list. // Post: Function value = number of elements in list. void RetrieveItem(ItemType& item, bool& found); // Retrieves list element whose key matches item's key // (if present). // Pre: Key member of item is initialized. // Post: If there is an element someItem whose key matches // item's key, then found = true and item is a copy of // someItem; otherwise found = false and item is // unchanged. // List is unchanged. void InsertItem(ItemType item); // Adds item to list. // Pre: List is not full. // item is not in list. // Post: item is in list. void DeleteItem(ItemType item); // Deletes the element whose key matches item's key. // Pre: Key member of item is initialized. // One and only one element in list has a key matching // item's key. // Post: No element in list has a key matching item's key. void ResetList(); // Initializes current position for an iteration through the // list. // Post: Current position is prior to list. void GetNextItem(ItemType&); // Gets the next element in list. // Pre: Current position is defined. // Element at current position is not last in list. // Post: Current position is updated to next position. // item is a copy of element at current position. private: NodeType* listData; int length; NodeType* currentPos; };
Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
}node;
void insert(node *pointer, int data)
{
node *start = pointer;
/* Iterate through the list till we encounter the last node.*/
while(pointer->next!=start)
{
pointer = pointer -> next;
}
/* Allocate memory for the new node and put data in it.*/
pointer->next = (node *)malloc(sizeof(node));
pointer = pointer->next;
pointer->data = data;
pointer->next = start;
}
int find(node *pointer, int key)
{
node *start = pointer;
pointer = pointer -> next; //First node is dummy node.
/* Iterate through the entire linked list and search for the key. */
while(pointer!=start)
{
if(pointer->data == key) //key is found.
{
return 1;
}
pointer = pointer -> next;//Search in the next node.
}
/*Key is not found */
return 0;
}
void delete(node *pointer, int data)
{
node *start = pointer;
/* Go to the node for which the node next to it has to be deleted */
while(pointer->next!=start && (pointer->next)->data != data)
{
pointer = pointer -> next;
}
if(pointer->next==start)
{
printf("Element %d is not present in the list ",data);
return;
}
/* Now pointer points to a node and the node next to it has to be removed */
node *temp;
temp = pointer -> next;
/*temp points to the node which has to be removed*/
pointer->next = temp->next;
/*We removed the node which is next to the pointer (which is also temp) */
free(temp);
/* Beacuse we deleted the node, we no longer require the memory used for it .
free() will deallocate the memory.
*/
return;
}
void print(node *start,node *pointer)
{
if(pointer==start)
{
return;
}
printf("%d ",pointer->data);
print(start,pointer->next);
}
int main()
{
/* start always points to the first node of the linked list.
temp is used to point to the last node of the linked list.*/
node *start,*temp;
start = (node *)malloc(sizeof(node));
temp = start;
temp -> next = start;
/* Here in this code, we take the first node as a dummy node.
The first node does not contain data, but it used because to avoid handling special cases
in insert and delete functions.
*/
printf("1. Insert ");
printf("2. Delete ");
printf("3. Print ");
printf("4. Find ");
while(1)
{
int query;
scanf("%d",&query);
if(query==1)
{
int data;
scanf("%d",&data);
insert(start,data);
}
else if(query==2)
{
int data;
scanf("%d",&data);
delete(start,data);
}
else if(query==3)
{
printf("The list is ");
print(start,start->next);
printf(" ");
}
else if(query==4)
{
int data;
scanf("%d",&data);
int status = find(start,data);
if(status)
{
printf("Element Found ");
}
else
{
printf("Element Not Found ");
}
}
}
}