Back to Top
Showing posts with label Data Structure Using C. Show all posts
Showing posts with label Data Structure Using C. Show all posts
  1. Home
  2. Posts filed underData Structure Using C

Single Link List using C program with algorithm

Algorithm 



InsertNodeAtBegining()

                    If (newNode == NULL) then
                        print ('Unable to allocate memory')
                    End if
                    Else then
                            read item
                            newNode.item ← item
                            newNode.next ← head
                            head ← newNode
                    End else

InsertNodeAtEnding()

                     If (newNode == NULL) then
                            print ('Unable to allocate memory')
                    End if
                    Else then
                            read item
                            newNode.item ← item
                            newNode.next ← NULL
                            temp ← End
                            While (temp.next != NULL) do
                            temp ← temp.next
                            End while
                            temp.next ← newNode
                    End else

InsertNodeAtMiddle()

                                 If (newNode == NULL) then
                                        write ('Unable to allocate memory.')
                                 End if
                                Else then
                                        read item
                                        newNode.item ← item
                                        temp ← head
                                            For i ← 2 to n-1
                                                temp ← temp.next
                                                    If (temp == NULL) then
                                                        break
                                                    End if
                                            End for
                                        If (temp != NULL) then
                                            newNode.next ← temp.next
                                            temp.next ← newNode
                                            End if
                                End else

deleteFirstNode()

                                  If (head==NULL)
                                                print “List Empty”
                                  end if
                                   else
                                         temp = head
                                         head = head.next
                                        delete temp
                                   End

deleteLastNode() 

                                     If (head == NULL) then
                                               print ('List is already empty')
                                     End if
                                     Else then
                                                temp ← head
                                                previousNode ← head
                                     While (temp.next != NULL) do
                                                previousNode ← temp
                                                temp ← temp.next
                                     End while
                                    If (temp == head) then
                                            head ← NULL
                                    End if
                                        Else then
                                                previousNode.next ← NULL
                                        End else
                                                free (temp)
                                    End

deleteMiddleNode()

                                    If (head == NULL) then
                                                print('List empty')
                                    End if
                                    Else then
                                                temp ← head
                                                 previousNode ← head
                                    For i←2 to n do
                                                previousNode ← temp
                                                temp ← temp.next
                                        If (temp == NULL) then
                                                break
                                        End if
                                    End for
                                    If (temp != NULL and temp == head) then
                                                   head ← head.next
                                    End if
                                    Else
                                                    previousNode.next ← temp.next
                                                    temp.next ← NULL
                                                    free (temp)
                                     End else
                                     End

Source Code of Single Link List operation

/*
Single Link List using C program
*/

#include <stdio.h>
#include <stdlib.h>

/* Structure of a node */
struct node
{
int item;
struct node *next;
} * head;

void createList(int n);
void displayList();
void insertNodeAtBeginning(int item);
void insertNodeAtEnd(int item);
void insertNodeAtMiddle(int item, int position);
void deleteFirstNode();
void deleteLastNode();
void deleteMiddleNode(int position);
int main()
{
int n, item, position;
int choice;
for (;;)
{
printf("\n===========::Single Link List Menu::=================\n\n ");
printf("\n1. Press 1 for Creating Lists\n");
printf("\n2. Press 2 for display Lists\n");
printf("\n3. Press 3 for insert item into fisrt Position of Lists\n");
printf("\n4. Press 4 for insert item into last Position of Lists\n");
printf("\n5. Press 5 for insert item into specified middle Position of Lists\n");
printf("\n6. Press 6 for delete item from fisrt Position of Lists\n");
printf("\n7. Press 7 for delete item from last Position of Lists\n");
printf("\n8. Press 8 for delete item from specified middle Position of Lists\n");
printf("\n===========::Single Link List Menu::=================\n ");
printf("\n\tEnter your choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
printf("Enter the total number of nodes: ");
scanf("%d", &n);
createList(n);
break;
case 2:
printf("\nitem in the list \n");
displayList();
break;
case 3:
printf("\nEnter item to insert at beginning of the list: ");
scanf("%d", &item);
insertNodeAtBeginning(item);
break;
case 4:
printf("\nEnter item to insert at end of the list: ");
scanf("%d", &item);
insertNodeAtEnd(item);
break;
case 5:
printf("nEnter item to insert at middle of the list: ");
scanf("%d", &item);
printf("Enter the position to insert new node: ");
scanf("%d", &position);
insertNodeAtMiddle(item, position);
break;
case 6:
deleteFirstNode();
break;
case 7:
deleteLastNode();
break;
case 8:
printf("\nEnter the node position you want to delete: ");
scanf("%d", &position);
deleteMiddleNode(position);
break;
case 9:
exit(1);
break;
default:
printf("Wrong selction");
}
}
return 0;
}

void createList(int n)
{
struct node *newNode, *temp;
int item, i;

head = (struct node *)malloc(sizeof(struct node));

if (head == NULL)
{
printf("Unable to allocate memory.");
exit(0);
}

printf("Enter the item of node 1: ");
scanf("%d", &item);

head->item = item;
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;
}

printf("Enter the item of node %d: ", i);
scanf("%d", &item);

newNode->item = item;
newNode->next = NULL;
temp->next = newNode;
temp = temp->next;
}
}
void displayList()
{
struct node *temp;

if (head == NULL)
{
printf("List is empty.");
}
else
{
temp = head;
while (temp != NULL)
{
printf("item = %d\n", temp->item);
temp = temp->next;
}
}
}
void insertNodeAtBeginning(int item)
{
struct node *newNode;

newNode = (struct node *)malloc(sizeof(struct node));

if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = head;

head = newNode;

printf("item INSERTED SUCCESSFULLY\n");
}
}
void insertNodeAtEnd(int item)
{
struct node *newNode, *temp;

newNode = (struct node *)malloc(sizeof(struct node));

if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = NULL;

temp = head;

while (temp != NULL && temp->next != NULL)
temp = temp->next;

temp->next = newNode;

printf("item INSERTED SUCCESSFULLY\n");
}
}
void insertNodeAtMiddle(int item, int position)
{
int i;
struct node *newNode, *temp;

newNode = (struct node *)malloc(sizeof(struct node));

if (newNode == NULL)
{
printf("Unable to allocate memory.");
}
else
{
newNode->item = item;
newNode->next = NULL;

temp = head;

for (i = 2; i <= position - 1; i++)
{
temp = temp->next;

if (temp == NULL)
break;
}

if (temp != NULL)
{

newNode->next = temp->next;

temp->next = newNode;

printf("item INSERTED SUCCESSFULLY\n");
}
else
{
printf("UNABLE TO INSERT item AT THE GIVEN POSITION\n");
}
}
}
void deleteFirstNode()
{
struct node *toDelete;

if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
head = head->next;

printf("\nData deleted = %d\n", toDelete->item);

free(toDelete);

printf("Successfully Delete First Node\n");
}
}
void deleteLastNode()
{
struct node *toDelete, *secondLastNode;

if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
secondLastNode = head;

while (toDelete->next != NULL)
{
secondLastNode = toDelete;
toDelete = toDelete->next;
}

if (toDelete == head)
{
head = NULL;
}
else
{
secondLastNode->next = NULL;
}

free(toDelete);

printf("Successfully Deleted Last Node\n");
}
}
void deleteMiddleNode(int position)
{
int i;
struct node *toDelete, *prevNode;

if (head == NULL)
{
printf("List is already empty.");
}
else
{
toDelete = head;
prevNode = head;

for (i = 2; i <= position; i++)
{
prevNode = toDelete;
toDelete = toDelete->next;

if (toDelete == NULL)
break;
}
if (toDelete != NULL)
{
if (toDelete == head)
head = head->next;

prevNode->next = toDelete->next;
toDelete->next = NULL;

free(toDelete);

printf("Successfully\n");
}
else
{
printf("Invalid position unable to delete.");
}
}
}


 
Stack implementation using C  ||  Queue implementation using C
| at | No comments |

Data Structure - Queue Implentation in C

Queue Algorithm

enqueue/insert element to the queue

                    procedure enqueue(data)      
                                  if  queue is full
                                      return overflow
                               endif
                                      rear ← rear + 1
                                   queue[rear] ← data
                                   return true
                   end procedure

 dequeue/delete element from the queue

                             procedure dequeue
                                              if queue is empty
                                                  return underflow
                                           end if
                                                   data = queue[front]
                                                   front ← front + 1
                                                   return true
                              end procedure

Source Code of Queue implementation in C using Array


#include <stdio.h>
#include <stdlib.h>
#define MAX 50
void enqueue();
void dequeue();
void display();
int queue_array[MAX];
int rear = -1;
int front = -1;
int main()
{
int choice;
while (1)
{
printf("\n1.Enqueue/Insert element to queue \n");
printf("\n2.Dequeue/Delete element from queue \n");
printf("\n3.Display all elements of queue \n");
printf("\n4.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("Wrong choice \n");
}
}
}
void enqueue()
{
int data;
if (rear == MAX - 1)
printf("Queue Overflow \n");
else
{
if (front == -1)
front = 0;
printf("Inset the element in queue : ");
scanf("%d", &data);
rear = rear + 1;
queue_array[rear] = data;
}
}
void dequeue()
{
if (front == -1 || front > rear)
{
printf("Queue Underflow \n");
return;
}
else
{
printf("Element dequeue from queue is : %d\n", queue_array[front]);
front = front + 1;
}
}
void display()
{
int i;
if (front == -1)
printf("Queue is empty \n");
else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
}

Source Code of Queue implementation in C using Link List

#include<stdio.h>
#include<stdlib.h>
struct Queue         //structure is declared
{ 
    struct Queue *next; //self referensing structure
    int item;            //initailizing item in the structure
};
    struct Queue *front;  //a pointer front is declared in structure
    struct Queue *rear;   //a pointer rear is declared in structure
    void addq(int);      //addq function is declared
    int delq();          //delq function id declared
void main()
{
    int ch, item, val; //variables are declared
    while(1)
    {
        printf("\nEnter 1 to add element in the Queue");
        printf("\nEnter 2 to delete element from the Queue");
        printf("\nEnter 3 to exit from program");
        printf("\nEnter your choice::");
        scanf("%d",&ch);
        switch(ch)
        {
            case 1: printf("\nEnter the item in the list::");
                scanf("%d", &item);
                addq(item);
                break;
            case 2: val=delq() ;
                printf("\nThe deleted element is %d=",val);
                break ;
            case 3: exit(1);
            default: printf("\nWrong Input") ;
         }
     }
        
}
void addq(int item)
{
 struct Queue *temp; //a pointer temp is declared within the structure
 temp=(struct Queue*)malloc(sizeof(struct Queue));
 if(temp==NULL)
    {
      printf("\nQueue Overflowed");
      return;
    }
 temp->item=item;//the value is entered in the List
 temp->next=NULL;
 if(rear==NULL)
  {
    front=temp;
    rear=temp;
  }
 else
  {
   rear->next=temp;
   rear=rear->next;     //rear is incremented
  }
}
int delq()
{
 struct Queue *temp;
 int item=0;
 if(front==NULL)       //checking unerflowed condition
  {
   printf("\nQueue Underflowed");
   return 0;
  }
  item=front->item;
  temp=front;
   if(front==NULL)   //checking whether front is null or not, if true
    { 
     front=NULL;    //front is assign with NULL
     rear=NULL;
    } 
  else
  {
    front=front->next;
    free(temp);
  }
  return item;
}


 Single Link List implementation using C
| at | No comments |

Data Structure - Stack Implementation in C

 ******Stack Algorithm******


      PUSH/INSERT()

                 1.      if top=MAX then
                                print "Stack is full";
                            exit;
                2. otherwise
                            top:=top+1;
                                stack(top)=item;
                3.  end of if
                4. exit

   POP/DELETE()

               1.      if top=0 then
                                print "Stack is empty";
                            exit;
                2. otherwise
                            item=stack(top);
                                    top:=top-1;
                3.  end of if
                4. exit

 isFull()

                 1.      if top=MAX then
                                status=true;
                2. otherwise
                          status=false;
                3.  end of if
                4. exit

 isEmpty()

                 1.      if top=0 then
                                  status=true;
                2.   otherwise
                          status=false;
                3.    end of if
                4.    exit

Stack Implementation Using Array[Static Memory allocation]


#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}



Stack Implementation using Link List

#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
} *top = NULL;

void push(int);
void pop();
void display();

void main()
{
int ch, data;
printf("\n:: Stack using Linked List ::\n");
while (1)
{
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Pop\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter the value to be insert: ");
scanf("%d", &data);
push(data);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)
{
struct Node *newNode;
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value;
if (top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if (top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if (top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
while (temp->next != NULL)
{
printf("%d--->", temp->data);
temp = temp->next;
}
printf("%d--->NULL", temp->data);
}
}

Queue implementation using  Single Link List in C 
| at | No comments |