Unit – 3
Linked Lists
Each node in singly linked list points to next node and it appears to move in one direction. Thus, SLL is unidirectional. Fig. 6.3 shows schematic diagram of singly linked list with 4 nodes.
Fig.: Singly Linked List
Implementation in C:
typedef struct node
{
int data;
struct node *next;
}
node;
A node is defined by structures in C. This structure is called as self-referential structure. This node stores integer value in data field of node. next stores address of next node and hence declared as a pointer variable.
Creation of First Node:
Step 1: node *P;
Step 2: P = (node*) malloc(sizeof(node));
Step 3: P->data = 10;
Step 4: P->next=NULL;
P1: Program to create a Linked List
#include <stdio.h>
#include<conio.h>
typedef struct node
{
int data;
struct node *next;
}node;
void main()
{
node *HEAD, *P ;
int n,i;
printf(“Enter no of nodes to be inserted ”)
scanf(“%d”, &n);
HEAD = (node*)malloc(sizeof(node));//get the first node
scanf(“%d”, &(HEAD->data));// get data in first node
HEAD->next= NULL;
P=HEAD;// currently HEAD and P points to same node
for(i=1;i<n;i++)// for n nodes
{
P->next= (node*)malloc(sizeof(node));
P=P->next;
P->next= NULL;
scanf(“%d”, &(P->data));
}
}
Explanation:
Declare node with self-referential structure.
Create HEAD node which is first node in Linked List.
HEAD = (node*) malloc(sizeof(node));
Store data in First node.
scanf (“%d”, &(HEAD->data)) ;//
Currently there is only one node in Linked List. So *next contains Null value and HEAD and P points to same node.
HEAD next=NULL;
P=HEAD;
Now create remaining nodes with the help of following code.
for (i=1; i<n; i++)// for n nodes
{
P->next= (node*) malloc(sizeof(node));
P=P->next;
P->next= NULL;
scanf (“%d”, &(P->data));
}
P2: Program to create and display the Linked List using function. This program also counts total number of nodes in Linked List
#include <stdio.h>
#include<conio.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *create(int);
void display(node*);
int count(node *);
void main()
{
node *HEAD;
int n, x;
printf(“Enter number of nodes”);
scanf(“%d”, &n);
HEAD = create(n) ;
display(HEAD);
x= count(HEAD);
printf(“Total number of nodes =”+x);
getch();
}
node *create(int n)
{
node *start, *P;
int i;
HEAD= (node*)malloc(sizeof(node));
start-> next = NULL;
scanf(“%d”, &(start->data));
P= start;
for(i=1;i<n;i++)
{
P->next = (node*)malloc(sizeof(node));
P=P->next;
scanf(“%d”, &(P->data));
P->next= NULL;
}
return(start);
}
void display(node *P)
{
printf(“Nodes are”)
while(P!=NULL)
{
printf(“ %d ”P->data);
P=P->next;
}
}
int count(node *P)
{
int i=0;
while(P!=NULL)
{
P=P->next;
i++;
}
return(i)
}
Output:
Enter number of nodes: 3
10 20 30
Nodes are
10 20 30
Total number of nodes: 3
Traversing is the most common operation that is performed in almost every scenario of singly linked list. Traversing means visiting each node of the list once in order to perform some operation on that. This will be done by using the following statements.
ptr = head;
while (ptr! =NULL)
{
ptr = ptr -> next;
}
Algorithm
STEP 1: SET PTR = HEAD
STEP 2: IF PTR = NULL
WRITE "EMPTY LIST"
GOTO STEP 7
END OF IF
STEP 4: REPEAT STEP 5 AND 6 UNTIL PTR! = NULL
STEP 5: PRINT PTR→ DATA
STEP 6: PTR = PTR → NEXT
[END OF LOOP]
STEP 7: EXIT
C function
#include<stdio.h>
#include<stdlib.h>
void create(int);
void traverse();
struct node
{
int data;
struct node *next;
};
struct node *head;
void main ()
{
int choice,item;
do
{
printf("\n1.Append List\n2.Traverse\n3.Exit\n4.Enter your choice?");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter the item\n");
scanf("%d",&item);
create(item);
break;
case 2:
traverse();
break;
case 3:
exit(0);
break;
default:
printf("\nPlease enter valid choice\n");
}
}while(choice != 3);
}
void create(int item)
{
struct node *ptr = (struct node *)malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted\n");
}
}
void traverse()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Empty list..");
}
else
{
printf("printing values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}
Output:
1.Append List
2.Traverse
3.Exit
4.Enter your choice?1
Enter the item
23
Node inserted
1.Append List
2.Traverse
3.Exit
4.Enter your choice?1
Enter the item
233
Node inserted
1.Append List
2.Traverse
3.Exit
4.Enter your choice?2
printing values . . . .
233
23
Searching an element (Iterative approach)
1) Initialize a node pointer, temp = head
2) Do following while temp is not NULL
temp->data is equal to the data being searched, return true.
temp = temp->next
3) Return false
Now, let us see a program to search element in a linked list using the iterative approach.
Iterative C Program to search for an element in the Linked List
#include <stdio.h>
#include <stdlib.h>
// Creating node with data and a pointer
struct node {
int data;
struct node *next;
}*head;
void createList(int n);
void search_element(int data);
void displayList();
int main()
{
int n, data, element;
printf("\nEnter the total number of nodes: ");
scanf("%d", &n);
createList(n);
printf("\nThe List is \n");
displayList();
printf("\nEnter the element to be searched in the list : "); // value of the element to be searched in the list
scanf("%d",&element);
search_element(element);
return 0;
}
void createList(int n)
{
struct node *newNode, *temp;
int data, i;
head = (struct node *)malloc(sizeof(struct node));
// When the list is empty
if(head == NULL)
{
printf("Unable to allocate memory.");
}
else
{
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data;
head->next = NULL;
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("Unable to allocate memory.");
break;
}
else
{
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}}}}
void search_element(int data)
{
int count = 0;
struct node* temp;
temp = head;
while(temp != NULL) // Start traversing from head node
{
if(temp -> data == data)
{
printf("\nElement found at position %d",count);
break;
}
else
{
count = count + 1;
temp = temp -> next;
}}
printf("\n Element %d is not found in the list\n",data);
}
void displayList()
{
struct node *temp;
if(head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
while(temp != NULL)
{
printf("%d\t", temp->data);
temp = temp->next;
}
printf("\n");
}}
OUTPUT
Insertion is a three- step process −
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc (sizeof (struct node));
link->key = key;
link->data = data;
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
Deletion is a two-step process −
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
A Double ended queue is a queue in which elements can be inserted or deleted from either front or rear. New elements can be added at either the front or the rear. Likewise, existing items can be removed from either end. This abstract data structures often abbreviated as deque and is also known as head-tail linked list. Deques are useful when we need both random access, and ability to delete/insert at both the ends. This hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.
add to front add to rear
A B C D E
remove from front Fig. Deque remove from rear
Dequeue can be categorized in two types
1) Input restricted Dequeue: It allows insertions at only one end
2) output restricted Dequeue: It allows deletions from only one end
A header node is a special node that is found at the beginning of the list. A list that contains this type of node, is called the header-linked list. This type of list is useful when information other than that found in each node is needed.
For example, suppose there is an application in which the number of items in a list is often calculated. Usually, a list is always traversed to find the length of the list. However, if the current length is maintained in an additional header node that information can be easily obtained.
Types of Headers Linked List
Grounded Header Linked List
It is a list whose last node contains the NULL pointer. In the header linked list the start pointer always points to the header node. start -> next = NULL indicates that the grounded header linked list is empty. The operations that are possible on this type of linked list are Insertion, Deletion, and Traversing.
Construction of doubly linked list:
B C A
NULL |
| N | 10 |
|
| 1000 | 20 | 3000 |
| 2000 | 30 |
|
| NULL |
1000 2000 3000
Fig.: Doubly Linked List
Fig. shows example of doubly linked list. Assume Our Doubly Linked List contains 3 nodes and let us denote it by A, B, and C.
Node A starts at memory address 1000.It does not have any predecessor node so left link points to NULL. Data field contains integer value ‘10’. Right Link of node in doubly linked list always stores memory address of its successor node. Hence right link of node A contains 2000 i.e., memory address of node B.
Left Link of node in doubly linked list contains memory address of predecessor node. A is predecessor node of B so left link of B contains 1000 i.e., memory address of A. Data field contains value’20’ and right link contains 3000 i.e., memory address of node C.
Same strategy is applied for all nodes in doubly linked list.
Node in doubly linked list is defined as
typedef struct node
{
int data;
struct node *next, *prev;
} node;
Node is defined as self-referential structure which contains one data field denoted as ‘data’ and two pointers ‘*next’, ‘*prev’. *next points to successor node and *prev points to predecessor node.
C Implementation of Doubly Linked List:
P6: Program to create and display doubly linked list
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next, *prev;
} node;
node *create();
void display(node*);
void main()
{
node *head;
head= NULL;
head=create();
printf(“Elements of Doubly Linked List”);
display(head);
}
node *create()
{
node *p, *q, *r;
int i,n,x;
p=NULL;
printf(“Enter number of elements”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“Enter data”);
scanf(“%d”,&x);
r= (node*)malloc(sizeof(node));
r->data=x;
r->prev=q->next=NULL;
if(p==NULL)
q=p=r;
else
q->next=r;
r->prev=q;
q=r;
}
return(p);
}
void display()
{
while(p!=NULL)
{
printf(“ %d ”, p->data);
p=p->next;
}
}
Operations On Doubly Linked List
1. Insertion of Node
2. Deletion of Node
3. Traversing
Insertion of Node
Node can be inserted in doubly linked list at 3 positions.
(A) At the beginning
(B) In the middle
(C) At the end
Algorithms:
Assume node to be inserted is pointed by P.
(A) Insertion of node at the beginning of Doubly Linked List
Suppose our DLL consists of 3 nodes.
Insertion can be done in following steps
1. Allocate memory to node pointed by P
P= (node*) malloc(sizeof(node))
2. Update the next pointer of the node P to the Head node and make prev pointer as
NULL
P->next=Head
P->prev= NULL
3. Now update Head node’s prev pointer to point to node P and make node P as head node.
Head->prev=P
P = Head
Insertion of node in the middle of Doubly Linked List
To insert a node in the middle of DLL we must know the data value of node after which node is to be inserted. Once we get the data value of node, traverse to that node.
Let us represent data value in a node by variable ‘data’ and value of node after which new node is to be inserted is ‘val’. Suppose we want to insert new node after 2nd node.
2. Initially Q points to first node.
Traverse to the node after which node is to be inserted.
while (Q! =NULL)
{
if(Q->data==val)
break;
Q=Q->next
}
Now Q points to 2nd node.
P
Make the next pointer of node P to point to node next to Q. Also make the prev point of node P to point to node 2nd node.
P->next=Q->next
P->prev=Q
Now point Q’s next to P
Q->next=P
Insertion of node at the last of Doubly Linked List
1. Traverse the list to end.
Q=Head
while(Q->next! =Null)
Q=Q->next
2. Update next pointer of Q to point to P.
Q->next=P
3. Make next pointer of P to point to NULL and prev pointer to point to Q
P->prev=Q
P->next=NULL
Deletion Of Node from Dll
Node can be deleted from doubly linked list at 3 positions
(A) At the beginning
(B) In the middle
(C) At the end
Algorithms:
(A) Deletion of node from the beginning of Doubly Linked List
Assume P points to node to be deleted.
1. P and Head points to the first node in DLL.
2. Now move the Head pointer to point to the next node. Also change the Head’s prev and P’s next to NULL. Then dispose the node pointed by P.
(B) Deletion of node from the middle of Doubly Linked List
To delete a node in the middle of DLL we must know the data value of node after which node is to be deleted. Once we get the data value of node, traverse to that node.
Let us represent data value in a node by variable ‘data’ and value of node after which new node is to be inserted is ‘val’. Suppose we want to delete 3rd node
1. Initially P and Head points to first node.
2. Traverse to the node after which node is to be deleted.
while (P! =NULL)
{
if(P->data==val)
break;
Q=P;
P=P->next
}
Now Q points to 2nd node and P points to 3rd node i.e., node to be deleted.
3. Set next of Q to next of P and prev of next of P to Q.
P->next=Q->next
P->next->prev=Q
Dispose P.
free(P)
(c) Deletion of node from the end of Doubly Linked List
1. Position pointer Q to the node previous to P. In order to find this position, list should be traversed first, beginning from the head.
Q=Head
while(Q->next->next! =NuLL)
Q=Q->next
P=Q->next
2. Set next link of the Q and prev link of P to NULL.
Q->next=NuLL
3. Dispose of the Last Node.
free(P)
P7: Program to perform following operations on doubly linked list
(A) Create a doubly linked list
(B) Insertion of a node
1. At the beginning of doubly Linked List
2. In the middle of doubly Linked List
3. At the end of doubly Linked List
(C) Deletion of a node
1. beginning of doubly Linked List
2. the middle of doubly Linked List
3. end of doubly Linked List
(D) Display doubly Linked List
#include <stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
char data;
struct node *next, *prev;
}node;
node *create();
node *insert_s(node *head, char x)
node *insert_b(node *head, char x)
node *insert_e(node *head, char x);
node *delete_s(node *head );
node *delete_b(node *head );
node *delete_e(node *head );
void display(node*);
void main()
{
int c,op;
char x;
node *head=NULL;
do
{
printf(“1.create\n2.insert\n3.delete\n4.display\n5.Quit”);
printf(“Enter your choice”);
scanf(“%d”, &c);
switch(c)
{
case 1:head=create();
break;
case 2:printf(“\n 1.Beginning\n2. Middle\n3.end”);
printf(“Enter your choice”);
scanf(“%d”,&op);
printf(“Enter data to be inserted”);
flushall();
x=getchar();
switch(op)
{
case 1:head=insert_s(head,x);
break;
case 2:head=insert_m(head,x);
break;
case 3:head=insert_e(head,x);
break;
}
break;
case 3:printf(“\n 1.Beginning\n2. Middle\n3.end”);
printf(“Enter your choice”);
scanf(“%d”,&op);
switch(op)
{
case 1:head=delete_s(head);
break;
case 2:head=delete_m(head);
break;
case 3:head=delete_e(head);
break;
}
break;
case 4:display(head);
break;
}
}while(op!=5);
}
node *create()
{
node *head,*p;
char x;
head=NULL;
printf(“Enter string”);
flushall();
while(x=getchar()!=’\n’)
{
if(head==NULL)
{
head=p=(node *)malloc(sizeof(node));
head->next=head->prev=NULL;
}
else
{
p->next=(node*)malloc(sizeof(node));
p->next->prev=p;
p=p->next;
p->next=NULL;
}
p->data=x;
}
return(head);
}
node *insert_s(node *head, char x)
{
node *p;
p= (node*)malloc(sizeof(node));
p->data=x;
if(head==NULL)
{
Head=p;
Head->next=head->prev=NULL;
}
else
{
p->next=head;
head->prev=p;
p->prev=NULL;
head=p;
}
return(head);
}
node *insert_m(node *head, char x)
{
node *p,*q;
char y;
p= (node*)malloc(sizeof(node));
p->data=x;
printf(“Insert after which character”);
flushall();
y=getchar();
for(q=head;q!=NULL && q->data!=y;q=q->next)
{
if(q->data==y)
{
p->next=q->next;
p->prev=q;
p->next->prev=p;
p->prev->next=p;
}
else
printf(“data not found”);
return(head);
}
}
node *insert_e(node *head, char x)
{
node *p,*q;
p= (node*)malloc(sizeof(node));
p->data=x;
if(head==NULL)
{
head=p;
head->next=head->prev=NULL;
}
else
{
for(q=head;q->next!=NULL;q=q->next)
{
q->next=p;
p->prev=q;
p->next=NULL;
}
return(head);
}
node *delete_s(node *head)
{
node *p,*q;
if(head==NULL)
{
printf(“Linked list is empty”);
return(head);
}
if(head->next==NULL)
{
p=head;
free(p);
head=NULL;
}
else
{
P=head;
head=head->next;
head->prev=NULL;
free(p);
}
return(head);
}
node *delete_m(node *head)
{
node *p,*q;
char x;
if(head==NULL)
{
printf(“List is empty”);
return(head);
}
printf(“Enter data to be deleted”);
flushall();
x=getchar();
for(p=head;p!=NULL && p->data!=x;p=p->next)
{
if(p->data!=x)
{
printf(“data not found”);
return(head);
}
if(p==head)
{
head=head->next;
if(head!=NULL)
head->prev=NULL;
free(p);
}
else
{
p->prev->next=p->next;
p->next->prev=p->prev;
free(p);
}
return(head);
}
}
void display(node *head)
{
node *p;
if(head!=NULL)
{
for(p=head;p!=NULL;p=p->next)
printf(“%c”, p->data);
}
}
Output:
create
Insert
Delete
Display
Quit
Enter choice: 1
Enter a string: abcde
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice: 2
Beginning
Middle
End
Enter choice: 2
Enter data to be inserted: f
Insert after which character: c
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice: 4
abcfde
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice:3
Beginning
Middle
End
Enter choice: 1
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice:4
bcfde
Reverse of Doubly Linked List:
C Function to reverse a doubly linked list:
void reverse(node *head)
{
node *p;
if(head!=NULL)
{
for(p=head;p->next!=NULL;p=p->next)
{
for(;p!=NULL;p=p->prev)
printf(“%c”, p->data);
}
}
}
Analysis is the theoretical way to study performance of computer program. Analysis of an algorithm is helpful to decide the complexity of an algorithm. There are three ways to analyze an algorithm which are stated as below.
1. Worst case: In worst case analysis of an algorithm, upper bound of an algorithm is calculated. This case considers the maximum number of operations on algorithm. For example, if user want to search a word in English dictionary which is not present in the dictionary. In this case user has to check all the words in dictionary for desired word.
2. Best case: In best case analysis of an algorithm, lower bound of an algorithm is calculated. This case considers the minimum number of operations on algorithm. For example, if user want to search a word in English dictionary which is found at the first attempt. In this case there is no need to check other words in dictionary.
3. Average case: In average case analysis of an algorithm, all possible inputs are considered and computing time is calculated for all inputs. Average case analysis is performed by summation of all calculated value which is divided by total number of inputs. In average case analysis user must be aware about the all types of input so average case analyses are very rarely used in practical cases.
Circular Linked List,
A circular linked list is a linked list in which last node points to first node i.e., next pointer of last node points to first node. Circular linked list does not contain NULL pointers.
Here A is the first node and C is the last node. C points to A and hence C stores address of A.
Operations On Circular Linked List
1. Insertion of a node
2. Deletion of a node
3. Traversing
Insertion of a node
Node can be inserted at 3 positions i.e., at the beginning, in the middle and at the end of circular linked list.
Insertion at the beginning:
Assume node to be inserted is pointed by P. Insertion can be done in following steps.
1. Position pointer Q to the last node of CLL. For this traverse the list to the end of list.
Q=Head
while(Q->next! =NULL)
Q=Q->next
2. Set next link of Q to P and next link of P to Head of CLL.
Q->next=P
P->next=Head
3. Make P as Head of CLL
Head=P
Insertion in the middle
Insertion of node in the middle of CLL is same as that of Singly linked List. Refer to section 2.2.
Insertion at the end
1. Position pointer Q to the last node of CLL. For this traverse the list to the end of list.
Q= Head
while(Q->next! =Head)
Q=Q->next
2. Set next link of Q to P and next link of P to Head.
P= Q->next
Head= P->next
Deletion Of Node from Cll
Node can be deleted at the beginning, from the middle and end of CLL.
Deletion at the beginning
Assume node to be deleted is pointed by P. Deletion can be done in following steps.
1. Position pointer P to point to Head Node and Q to the last node.
P=Q= Head
while(Q->next! =Head)
Q=Q->next
2. Position pointer Head to the next of P. Set next link of Q to point to new Head.
Head=Head->next
Head= Q->next
3. Dispose P.
free(P)
Deletion in the middle of CLL
Deletion of node in middle of CLL is same as that of Singly linked list. Refer to section…
Deletion at the end of CLL
1. Position pointer Q to last but one node of CLL.
Q=Head
while(Q->next->next! =Head)
Q=Q->next
2. Set next link of Q to Head and P to NULL. Dispose P.
Q->next=Head
free(P)
3. Set next link of Q to Head and P to NULL. Dispose P.
Q->next=Head
free(P)
P8: Program to create add remove & display element from circular linked list
#include<stdio.h>
#include<alloc.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
};
struct node *head=NULL;
struct node *tail=NULL;
void main()
{
void addrecord();
void deleterecord();
void disrecord();
int ch;
clrscr();
do
{
printf("\n 1. To add records\n");
printf("\n 2. To delete a records\n");
printf("\n 3. To view the records\n");
printf("\n 4. To exit\n");
printf("\n Enter your choice\n");
scanf("%d",&ch);
fflush(stdin);
switch(ch)
{
case 1:addrecord();
break;
case 2:deleterecord();
break;
case 3: disrecord();
break;
case 4:exit(0);
}
} while (ch!=4);
}
void addrecord()
{
int new_data;
char ans='y';
struct node *ptr,*prev,*temp;
clrscr();
while (ans=='y')
{
temp=(struct node*)malloc(sizeof(struct node));
printf("\n Enter the new element:\n");
scanf("%d",&new_data);
fflush(stdin);
temp->data=new_data;
temp->next=NULL;
if (head==NULL)
{
head=tail=temp;
temp->next=head;
}
else
{
tail->next=temp;
tail=temp;
}
printf("\n Would you like to enter another data(y\\n): \n");
ans = getchar();
fflush(stdin);
}
}
void deleterecord()
{
struct node *ptr,*prev,*delnode;
int elt;
printf("\n Enter the enrollment number to be deleted \n");
scanf("%d",&elt);
fflush(stdin);
if (head==NULL)
{
printf("\n No elements in the list \n");
return;
}
else
{
if (head->data==elt)
{
delnode=head;
if (head==tail)
head=tail=NULL;
else
{
head=head->next;
tail->next=head;
}
}
else if (tail->data==elt)
{
for(ptr=head;(ptr!=tail);prev=ptr,ptr=ptr->next);
delnode=tail;
tail=prev;
tail->next=head;
}
else
{
for(prev=ptr=head;(ptr->data!=elt)&&(ptr!=tail);
prev=ptr,ptr=ptr->next);
if(ptr->data==elt)
{
delnode=ptr;
prev->next=ptr->next;
printf("yes...");
}
else
{
printf("Given element not found in the list");
getch();
return;
}
}
}
free(delnode);
}
void disrecord()
{
struct node *ptr,*prev=NULL;
if (head==NULL)
{
printf("\n No records to view\n");
return;
}
printf("\n The elements in the circular list are\n");
for (ptr=head;prev!=tail;prev=ptr,ptr=ptr->next)
printf("\n\n %d",ptr->data);
printf(" NULL\n\n ");
getch();
}
Complexity of an algorithm is the function which gives the running time and space requirement of an algorithm in terms of size of input data. Frequency count refers to the number of times particular instructions executed in a block of code. Frequency count plays important role in the performance analysis of an algorithm. Each instruction in algorithm is incremented by one as its execution. Frequency count analysis is the form of priori analysis. Frequency count analysis produces output in terms of time complexity and space complexity.
Frequency count analysis for this code is as follows
Sr. No. | Instructions | Frequency count |
#include<stdio.h> |
| |
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int marks; |
|
5. | printf(“enter a marks”); | add 1 to the time count |
6. | scanf(“%d”,&marks); | add 1 to the space count |
7. | printf(“your marks is %d”,marks); | add 1 to the time count |
8. | getch(); } |
|
In the above example, for the first four instructions there is no frequency count. For data declaration and the inclusion of header file there is no frequency count. So, for this example has a frequency count for time is 2 and a frequency count for space is 1. So, total frequency count is 3.
Consider the following example
Sr. No. | Instructions | Frequency count |
#include<stdio.h> |
| |
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int sum=0; | 1 |
5. | for(i=0;i<5;i++) | 6 |
6. | sum=sum+i; | 5 |
7. | printf(“Addition is %d”,sum); | 1 |
8. | getch(); } |
|
Explanation: In the above example, one is added to frequency count for instruction four and seven after that in fifth instruction is check from zero to five so it will add value six to frequency count. ‘For’ loop executed for five times so for sixth instruction frequency count is five. Total frequency count for above program is 1+6+5+1 =13.
Consider the following example
Sr. No. | Instructions | Frequency count |
1. | #include<stdio.h> |
|
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int a[2][3],b[2][3],c[2][3]] |
|
5. | for(i=0;i<m;i++) | m+1 |
6. | { |
|
7. | for(j=0;j<n;j++) | m(n+1) |
8. | { |
|
9. | c[i][j]=a[i][j]*b[i][j]; | m.n |
10. | }} |
|
11. | getch(); } |
|
Explanation: In the above example, in instruction five value of ‘i’ is check from 0 to ‘m’ so frequency count is ‘m+1’ for fifth instruction. In instruction five value of ‘j’ is check from 0 to ‘n’ so frequency count is ‘n+1’ but this instruction is in the for loop which execute for ‘m’ times, so for seventh instruction is m*(n+1). Ninth instruction is in the two for loops, out of which first for loop execute for m times and second ‘for’ loop execute for ‘n’ times. So, for ninth instruction frequency count is m*n. The total frequency count for the above program is (m+1) +m(n+1) +mn=2m+2mn+1=2m(1+n) +1.
Consider the following example
Sr. No. | Instructions | Frequency count |
1. | #include<stdio.h> |
|
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int a[2][3],b[2][3],c[2][3]] |
|
5. | for(i=0;i<m;i++) | m+1 |
6. | { |
|
7. | for(j=0;j<n;j++) | m(n+1) |
8. | { |
|
9. | a[i][j]=n; | m.n |
10. | for(k=0;k<n;k++) | mn(n+1) |
11. | c[i][j]=a[i][j]*b[i][j]; | m.n.n |
12. | }} |
|
13. | getch(); } |
|
Explanation: For above program total frequency count
=(m+1) +m(n+1) +mn+mn(n+1) +mn
=m+1+mn+m+mn+mn2 +mn+mn2
=2 mn2+3mn+2m+1
=mn(2n+3) +2m+1
Consider the following example
Sr. No. | Instructions | Frequency count |
1. | #include<stdio.h> |
|
2. | #include<conio.h> |
|
3. | void main() { |
|
4. | int n=1,m; | 1 |
5. | Do |
|
6. | { |
|
7. | printf(“hi”); | 10 |
8. | if(n==10) | 10 |
9. | break; | 1 |
10. | n++; | 9 |
11. | } |
|
12. | while(n<15); | 10 |
13. | getch(); } |
|
Explanation: the above example, one is added to frequency count for instruction four. The loop will execute till value of n is incremented to 10 from 1, so for loop statements i.e., instructions seven and eight is execute for tam times. when the value of ‘n’ is ten then ‘break’ statement will execute for one time and it will skip the tenth execution of tenth instruction. Tenth instruction will add value nine to frequency count. Total frequency count for above program is 10+10+1+9+10 = 40.
References:
1. Algorithms, Data Structures, and Problem Solving with C++”, Illustrated Edition by Mark Allen Weiss, Addison-Wesley Publishing Company.
2. “How to Solve it by Computer”, 2nd Impression by R.G. Dromey, Pearson Education.
3. “Fundamentals of Data Structures”, Illustrated Edition by Ellis Horowitz, Sartaj Sahni, Computer Science Press.
