Data Structure and Algorithm

//

C program to insert a node at front, at end, and at any position in a Single Linked List.

#include
#include

//Create a basic structure for NODE from which new nodes can be created.
struct node
{
 int data;
 struct node *link;
};

//Initialize 3 pointers as globals so that they do not need to be passed in functions.
struct node *header, *ptr, *temp;

//Prototypes for various user defined functions.
void insert_front();
void insert_end();
void insert_any();
void display();

void main()
{
 int choice;
 int cont = 1;

 //Allocate memory for header node.
 header = (struct node *) malloc(sizeof(struct node));

 clrscr();

 //Set the content of header node
 header->data = NULL;
 header->link = NULL;

 while(cont == 1)
 {
  //Display menu to the user
  printf("\n1. Insert at front\n");
  printf("\n2. Insert at end\n");
  printf("\n3. Insert at any position\n");
  printf("\n4. Display linked list\n");
  printf("\nEnter your choice: ");
  scanf("%d", &choice);

  switch(choice)
  {
   case 1:
    insert_front();
    break;
   case 2:
    insert_end();
    break;
   case 3:
    insert_any();
    break;
   case 4:
    display();
    break;
  }

  printf("\n\nDo you want to continue? (1 / 0): ");
  scanf("%d", &cont);
 }

 getch();
}

//Function to insert a node at the front of a single linked list.
void insert_front()
{
 int data_value;

 printf("\nEnter data of the node: ");
 scanf("%d", &data_value);

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

 temp->data = data_value;
 temp->link = header->link;
 header->link = temp;
}

//Function to insert a node at the end of a single linked list.
void insert_end()
{
 int data_value;

 printf("\nEnter data of the node: ");
 scanf("%d", &data_value);

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

 //Traverse to the end of the linked list.
 ptr = header;
 while(ptr->link != NULL)
 {
  ptr = ptr->link;
 }

 temp->data = data_value;
 temp->link = ptr->link;
 ptr->link = temp;
}

//Function to insert a node at any position after a particular node.
void insert_any()
{
 int data_value, key;

 printf("\nEnter data of the node: ");
 scanf("%d", &data_value);
 printf("\nEnter data of the node after which new node is to be inserted: ");
 scanf("%d", &key);

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

 //Traverse till key is found or end of the linked list is reached.
 ptr = header;
 while(ptr->link != NULL && ptr->data != key)
 {
  ptr = ptr->link;
 }
 if(ptr->data == key)
 {
  temp->data = data_value;
  temp->link = ptr->link;
  ptr->link = temp;
 }
 else
 {
  printf("\nValue %d not found\n",key);
 }
}

//Function to display the contents of the linked list.
void display()
{
 printf("\nContents of the linked list are: \n");
 //Print the contents of the linked list starting from header
 ptr = header;
 while(ptr->link != NULL)
 {
  ptr = ptr->link;
  printf("%d ", ptr->data);
 }
}

DATA STRUCTURE AND ALGORITHM




Infix to Postfix Conversion in C

#include<stdio.h>

char stack[20];

int top = -1;

void push(char x)

{

    stack[++top] = x;

}

char pop()

{

    if(top == -1)

        return -1;

    else

        return stack[top--];

}

int priority(char x)

{

    if(x == '(')

        return 0;

    if(x == '+' || x == '-')

        return 1;

    if(x == '*' || x == '/')

        return 2;

}

main()

{

    char exp[20];

    char *e, x;

    printf("Enter the expression :: ");

    scanf("%s",exp);

    e = exp;

    while(*e != '\0')

    {

        if(isalnum(*e))

            printf("%c",*e);

        else if(*e == '(')

            push(*e);

        else if(*e == ')')

        {

            while((x = pop()) != '(')

                printf("%c", x);

        }

        else

        {

            while(priority(stack[top]) >= priority(*e))

                printf("%c",pop());

            push(*e);

        }

        e++;

    }

    while(top != -1)

    {

        printf("%c",pop());

    }

}