QUES 29 CONCATENATION OF LINKED LIST

C LANGUAGE BOOK

 Concatenate one linked list  at the end of other


Insertion operation of  linked list
Deletion operation of linked list

create first linked list.
create second linked list.

How to Concatenate second list at the end of first list.
create an empty third list.
if first list is empty
 assign second list to third list.
else

if second list is empty

 assign first list to third list.
else
if first list and second list are not empty.
assign first list to third list.
go to last node of third list.
assign next pointer of last node of third list to point to start node of second list


/* WAP a Program to concatenate one linked list  at the end of other.*/


#include<alloc.h>
#include<stdio.h>

struct me
{
int data;
struct me *link;
};

void main()
{

 struct me *p,*q,*w;
 int j;
 p=q=w=NULL;

 do
 {
 printf("\n\tLINKED LIST");
 printf("\n\t1.ENTER THE FIRST LIST");
 printf("\n\t2.ENTER THE SECOND LINKED LIST");
 printf("\n\t3.CREATE A THIRD LIST WHICH \n\tCONTAIN CONCATNATION OF THE SECOND LIST \n\tAT THE END OF FIRST LIST");
 printf("\n\t4.DISPLAY THE CONCTANATION LIST");
 printf("\n\t5.EXIT\n");
 printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
 scanf("%d", &j);
 printf("\n");

switch(j)
{
  case 1:   Menu(&p);
        printf("\n");
        break;

  case 2:   Menu(&q);
        printf("\n");
        break;

  case 3:   Concat(p, q, &w);
        printf("\n");
        break;

  case 4:   Display(w);
        printf("\n");
        break;

  case 5:   exit(1);
default :  err_msg(3);
}

}while(j>=1 && j<=5);
}

Menu(struct me **p)
{
int j;
do
{
 printf("\n\t1.INSERTION");
 printf("\n\t2.DELETION");
 printf("\n\t3.SORTING");
 printf("\n\t4.DISPLAY");
 printf("\n\t5.RETURN\n");
 printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 5): ");
 scanf("%d", &j);
 printf("\n");
 switch(j)
 {
  case 1:   Insertion(&(*p));
        break;
  case 2:   Deletion(&(*p));
        break;
  case 3:   Sorting(&(*p));
        printf("\n");
        break;
  case 4:   Display(*p);
        printf("\n");
        break;
  case 5:   return;
default :  err_msg(3);
 }

}while(j>=1 && j<=5);
}

Insertion(struct me **q)
{
 int i,m,n;
 char ch[15];
 do
  {
        printf("\n\tINSERTION");
        printf("\n\t1.INSERT AT BEGINNING");
        printf("\n\t2.INSERT AT POSITION");
        printf("\n\t3.INSERT AT END");
        printf("\n\t4.RETURN\n");
        printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
        scanf("%d", &i);
        printf("\n\n i=%d ",i);
        printf("\n");
        switch(i)
        {
        case 1: printf("ENTER THE NUMBER : ");
            scanf("%d", &m);
            AddAtBeg(&(*q),m);
            printf("\n");
            break;
        case 2: printf("ENTER THE NUMBER : ");
            scanf("%d", &m);
            printf("ENTER THE POSITION : ");
            scanf("%d", &n);
            AddAtPos(*q , m, n);
            printf("\n");
            break;
        case 3: printf("ENTER THE NUMBER : ");
            scanf("%d", &m);
            AddAtEnd(&(*q) , m);
            printf("\n");
            break;
        case 4: return;
      default : err_msg(3);
           }
     }while(i>=1 && i<=4);

}

Deletion(struct me **q)
{
 int i,m,n;
 do
 {
        printf("\n\tDELETION");
        printf("\n\t1.DELETION AT BEGINNING");
        printf("\n\t2.DELETION AT POSITION");
        printf("\n\t3.DELETION AT END");
        printf("\n\t4.RETURN\n");
        printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 4): ");
        scanf("%d", &i);
        printf("\n");
        switch(i)
        {
        case 1: DeleteAtBeg(&(*q));
            printf("\n");
            break;
        case 2: printf("ENTER THE POSITION : ");
            scanf("%d", &n);
            DeleteAtPos(*q ,n);
            printf("\n");
            break;
        case 3: DeleteAtEnd(&(*q));
            printf("\n");
            break;
        case 4: return;
      default : err_msg(3);

        }
       }while(i>=1 && i<=4);
}
Sorting(struct me **q)
{
   int i;

  do
  {
        printf("\n\tSORTING");
        printf("\n\t1.USING BUBBLE SORT");
        printf("\n\t2.RETURN");
        printf("\n\n\tWHAT DO YOU WANT TO DO (PRESS 1 TO 2): ");
        scanf("%d", &i);
        printf("\n");
        switch(i)
        {
         case 1: UsingBubbleSort(&(*q));
             printf("\n");
             break;
         case 2: return;
      default : err_msg(3);
        }
       }while(i>=1 && i<=2);
}

AddAtBeg(struct me **q,int x)
{
 struct me *p,*w;
 p = *q;
 if(p == NULL)
 {
  w = malloc(sizeof(struct me));
  w->data = x;
  w->link = NULL;
 *q = w;
  }
 else
 {
 w = malloc(sizeof(struct me));
 w->data = x;
 w->link = *q;
  *q = w;
  }
return;
}

AddAtPos(struct me *q,int x,int y)
{
 struct me *p,*w,*z;
 int i;
 w = q;
 z = q;
if(w == NULL)
{
  err_msg(5);
  return;
}
else
{
for(i = 0; i < y; i++)
{
 z = z->link;
if(z == NULL)
 {
   printf("THERE ARE LESS THAN %d ELEMENTS IN THE LIST", y);
   return;
  }
}
printf(" \n\n  heelloioyuo \n");
  p = malloc(sizeof(struct me));
  p->data = x;
  p->link = z->link;
  z->link  = p;
return;
}

}


AddAtEnd(struct me **q, int y)
{
struct me *p,*w;
p = *q;
if(p == NULL)
 {
 p = malloc(sizeof(struct me));
 p->data = y;
 p->link = NULL;
 *q = p;
 return;
 }
else
{
while(p->link != NULL)
{
 p = p->link;
}
w = malloc(sizeof(struct me));
w->data = y;
w->link = p->link;
p->link = w;
return;
}
}

DeleteAtBeg(struct me **q)
{
struct me *p,*w;
p = *q;
if(p == NULL)
{
  err_msg(1);
}
else
{
 if(p->link == NULL)
 {
  printf("THE LIST");
  *q = NULL;
  free(p);
 }
 else
 {
 w = p;
 *q = w->link;
 free(w);
 }

}
return;
}

DeleteAtPos(struct me *q,int x)
{
struct me *p,*w, *z;
int i;
p = q;
w = q;

if(p == NULL)
{
  err_msg(6);
}
else
{
for(i = 0; i < x; i++)
{
 w = w->link;
if(w == NULL)
{
printf("CANNOT DELETE THERE ARE LESS THAN %d \n ELEMENTS IN THE LIST", x);
return;
}
}
z = w->link;
w->link = z->link;
free(z);
return;
}
}

DeleteAtEnd(struct me **q)
{
struct me *p,*z;
p = *q;
if(p == NULL)
{
  err_msg(1);
  }
else
if(p->link == NULL)
{
  *q = NULL;
  free(p);
}
else
{
while(p->link->link != NULL)
{
p = p->link;
}

z = p->link;
p->link = p->link->link;
free(z);
}
return;
}

UsingBubbleSort(struct me **q)
{
int c = 0,x;
struct me *p, *w, *z,*v;
p = *q;
v = *q;

while( p != NULL)
{
c++;
p = p->link;
}

printf("\n\n\nNUMBER OF NODES IN LINKED LIST IS : %d\n\n",c);

if(v == NULL)
{
err_msg(1);
}
else if(v->link == NULL)
{
err_msg(4);
}
else
{
for(w = *q ; w != NULL; w = w->link)
{
for(z = *q ; z->link != NULL; z = z->link)
{
 if(z->data > z->link->data)
   {
     x = z->link->data;
     z->link->data = z->data;
     z->data = x;
   }
}
for(p = *q ; p != NULL; p = p->link)
 printf("\nLIST:  %d", p->data);

printf("\n");

}
}
return;
}

Display(struct me *q)
{

struct me *z;
z = q;

if(z == NULL)
{
err_msg(1);
return;
}
else
{
while(z != NULL)
{
 printf("%d", z->data);
  z = z->link;
 printf("\n");
 }

return;
}
}

Concat(struct me *p, struct me *q, struct me **w)
{
struct me *temp;

*w = temp = p;

if(p == NULL)
{
   if(q == NULL)
   {
     err_msg(1);
   }
   else
   if(q != NULL)
   {
      *w = q;
   }
return;
}
else
if(p != NULL)
{
   if(q == NULL)
   {
    *w = p;
   }
   else
   if(q != NULL)
   {
    while(temp->link != NULL)
    {
    temp = temp->link;
    }
    temp->link = q;
    }

return;
}
}

err_msg(int p)
{
if(p==1)
printf("THE LIST IS EMPTY");
if(p==2)
printf("HELLO");
if(p==3)
printf("WRONG CHOICE");
if(p==4)
printf("THE LIST IS ALREADY SORTED");
if(p==5)
printf("\nINSERTION AT POS REQUIRED ONE NODE");
if(p==6)
printf("\nDELETION AT POS REQUIRED TWO NODE");

}

C LANGUAGE BOOK