Homework SourseDiscuss about Header Node And also write a program for unor
^^^
Discuss about Header Node? And also write a program for unordered single linked list and linked implementation of QUEUE?Solution
Header node:
Sometimes it is desire to keep an extra node at the front of a List. Such a node doesn’t represent an item in the List and is called a Header Node or a List Header. The Information field of such Header node might be unused but the Next field maintains the first node address. More often the information of such a node could be used to keep Global Information about the Entire List.
One of the applications of Header node is the information portion of the Header node contains the number of nodes (not including Header) in the List. In this Structure the Header must be adjusted the total number of nodes when we apply addition or deletion operation on the List. We can directly obtained the total number of nodes without traversing the entire List.
By using this application, we can develop Data Structure Stack easily. Since Header node information field maintains the number of elements that the Stack contains.
Another application is we can simply develop the Data Structure Queue. Until now, two external pointers, Front & Rear, were necessary for a List to represent a Queue. However, now only a single external pointer is sufficient to maintain a Queue that is Head node. Because the Header node next field behave like a Front and information field of Header node maintains last node address so that it is behave like a Rear .
Another possibility for the use of the information portion of a List Header is as a pointer to a Curr node in the List during a traversal process. This would be eliminate the node for an external pointer during traversal.
#include<stdio.h>
#include<stdlib.h>
#include<alloc.h>
#include<string.h>
struct node
{
char info;
struct node *next;
};
typedef struct node sl;
void display(sl *);
sl * create(sl *root)
{
sl *curr,*new;
char val;
printf(\"\ Enter $ to STOP --- Otherwise Continue : \");
fflush(stdin);
scanf(\"%c\",&val);
while(val != \'$\')
{
new=(sl *) malloc(sizeof(sl));
new->info = val;
new->next = NULL;
if(root == NULL)
root = new;
else
{
curr = root;
while( curr->next != NULL )
curr = curr->next;
curr->next = new;
}
printf(\" Enter $ to STOP --- Otherwise Continue : \");
fflush(stdin);
scanf(\"%c\",&val);
}
printf(\"\ The Created Linked List Is \ \");
display(root);
return root;
}
sl * delete(sl *root,char val)
{
sl *temp,*curr,*rear;
curr = root;
rear = NULL;
while( curr != NULL && val != curr->info )
{
rear = curr;
curr = curr->next;
}
if(curr == NULL)
{
if( rear == NULL)
{
printf(\"\ Linked List is Empty\");
printf(\"\ Deletion is not Possible \");
}
else
{
printf(\"\ deleted Node does not exist in List\");
printf(\"\ Deletion is not Possible \");
}
}
else
{
if( rear == NULL)
{
temp = root;
root = root->next;
}
else
{
temp = curr;
rear->next = curr->next;
}
printf(\"\ Node is deleted \");
printf(\"\ Deleted Node information is %c\",temp->info);
free(temp);
}
display(root);
return root;
}
sl * insert(sl *root,char val)
{
sl *curr,*new;
new=(sl *) malloc(sizeof(sl));
new->info = val;
new->next = NULL;
if(root == NULL)
root = new;
else
{
curr = root;
while( curr->next != NULL )
curr = curr->next;
curr->next = new;
}
return root;
}
void display(sl *start)
{
printf(\"\ ROOT-> \");
while(start != NULL )
{
printf(\"%c -> \",start->info);
start =start->next;
}
printf(\"NULL\ \ \");
getch();
}
char menu()
{
char ch;
clrscr();
gotoxy(33,2); printf(\"MAIN MENU\");
gotoxy(25,6); printf(\"Creation C\");
gotoxy(25,8); printf(\"Insertion I\");
gotoxy(25,10);printf(\"Removing R\");
gotoxy(25,12);printf(\"Display D\");
gotoxy(25,14);printf(\"Quit Q\");
gotoxy(10,30);printf(\"\ Enter Choice : \");
fflush(stdin);
scanf(\"%c\",&ch);
return(ch);
}
main()
{
sl *insert(sl *,char),*delete(sl *,char),*create(sl *);
sl *root=NULL;
char item;
char choice;
char menu();
while( ( choice=menu() ) != \'Q\' || ( choice != \'q\') )
{
switch(choice)
{
case \'c\':
case \'C\': root = NULL;
root = create(root);
break;
case \'i\':
case \'I\': printf(\"Enter Character Item to be Inserted : \");
fflush(stdin);
scanf(\"%c\",&item);
root = insert(root,item);
break;
case \'d\':
case \'D\': printf(\"The Current Linked List is : \");
display(root);
getch();
break;
case \'r\':
case \'R\': printf(\"Enter the Item wich you want to be Remove :\");
fflush(stdin);
scanf(\"%c\",&item);
root = delete(root,item);
break;
case \'q\':
case \'Q\': return;
}
}
}
