facebook like button

Showing posts with label reverse the list. Show all posts
Showing posts with label reverse the list. Show all posts

18 August, 2011

program 78: do everything with linked list

The need:
This is a program to show almost all basic operations on linked lists. This program is just a combination of various programs of linked lists written by me. This is written in a way that you can pick data and function definitions and can use as-it-is in other programs.
The code:
------------------------------------------------------------
#include<stdio.h> 
#include<stdlib.h> 

// defining data-type node 
struct linked_list 
{ 
    int num;
    struct linked_list *next;
}; 
typedef struct linked_list node ;   //defining datatype node 

//declaration of functions 

node *create_list(node *p); 
node *reverse(node *p); 
int count (node *p); 
void print(node *p); 
node *insert(node *p); 
node *find(node *p,int a); 
node *hatana(node *p); 
node *insert_sort(node *head,int n); 
void sort(node *p); 
node *rearrange(node *p); 

main() 
{ 
    int i;
    node *head=NULL ;
    printf("This is a program to do with linked list .\n\n");
    lebel:
    printf("Options :\n(1)Create linked list.\n(2)view list.\n(3)Insert element.\n(4)Delete Element.\n");
    printf("(5)To arrange list in increasing order.\n");
    printf("(6)To remove double entries .\n(7)to reverse the list\n(8)Exit program.\n");
    scanf("%d",&i);
    switch(i)
    {
        case 1 :
                printf("Enter element numbers .\n");
                printf("Type -999 to end :\n");
                head=create_list(head);
                printf("List created successfully .\nNumber of items in the list are %d.\n\n\n",count(head));
                goto lebel;
        case 2 :
                print(head);
                goto lebel ;
        case 3 :         
                head=insert(head);
                goto lebel ;
        case 4 :         
                head=hatana(head);
                goto lebel ;
        case 5 :
                sort(head);
                printf("\nsorted in increasing order\n\n");
                goto lebel;
        case 6 :
                rearrange(head);
                printf("\nduplicate entries deleted\n\n");
                goto lebel;
        case 7 :
                head=reverse(head);
                printf("\nList reversed\n\n");
                goto lebel;
        case 8 :
                exit (0);
                break;         
        default:     
                printf("Invalid Choice !!!.\n");
                goto lebel ;
                break;
    }
     
     
    return 0;
        
}                //main ends here 

node *create_list(node *list) 
{ 
    int i;
    list=NULL;
    scanf("%d",&i);
    if(i!=-999)
    {
        list=(node*)malloc(sizeof(node));
        list->num=i;
        list->next=create_list(list->next);
    }
    return list;
} 

node *reverse(node *p) 
{ 
    node *temp=NULL,*rev=NULL;
    while(p)
    {
        temp=p;
        p=p->next;
        temp->next=rev;
        rev=temp;
    }
    return(rev);
} 

int count (node *list) 
{ 
    if(list==NULL)
    return 0;
    else
    return (1+count(list->next));            //recursion 
} 


void print(node *list) 
{ 
    if(list==NULL)
    printf("The list is empty.\n\n");
    else
    {
        printf("%d-->",list->num);
        if(list->next==NULL)
        printf("END\n\n\n");
        else
        print(list->next);            //recursion 
    }
} 



node *find(node *list, int key)            //This function returns the node after which 
{     
    if(list->next)
    {                                    //the key is found .                             
        if(list->next->num == key)     /* key found */ 
            return(list);
        else if(list->next->next == NULL)    /* end */ 
            return(NULL);
        else
        find(list->next, key);
    }
    else
    return NULL;
} 



node *insert(node *head) 
{ 
    node *new_node;          /* pointer to new node */ 
    node *n1=head;        /* pointer to node preceding key node */ 
    int key;
    int x;            /* new item (number) to be inserted */ 
    if(!head)
    {
        printf("\nlist is not created yet.\n\n");
        return head;
    }
    printf("What value you want to insert?");
    scanf("%d", &x);
    printf("before which key item ? (type -999 if to be inserted last) ");
    scanf("%d", &key);

    if(key==-999)        /* insert new node at last*/ 
    {
        while(n1->next)
            n1=n1->next;    //navigate to last node 
            
        new_node = (node *)malloc(sizeof(node));
        new_node->num = x;
        new_node->next = n1->next;
        n1->next = new_node;
    }
    else if(head->num == key)        /* new node is first */ 
    {
        new_node = (node *)malloc(sizeof(node));
        new_node->num = x;
        new_node->next = head;
        head = new_node;
    }
    else        /* find key node and insert new node */ 
    {            /* before the key node */ 
        n1 = find(head, key);    /* find key node */

        if(n1 == NULL&&key!=-999)
           printf("\n key is not found !!!\n\n");
            
        else        /* insert new node */ 
        {
          new_node = (node *)malloc(sizeof(node));
          new_node->num = x;
          new_node->next = n1->next;
          n1->next = new_node;
        }
      }
      return head;
} 



node *hatana(node *list) 
{ 
    void delete_node(node *);
    node *n1,*n2;
    int key;
    if(!list)
    {
        printf("\nlist is not created yet.\n\n");
        return list;
    }
    printf("What value do you want to delete ?");
    scanf("%d",&key);
    if(key==list->num)                        //key is the first node 
    {
        n2=list->next;
        free(list);
        list=n2;
        printf("\n%d is deleted successfully .\n\n",key);
    }
    else
    {
         n1=find (list ,key);
         if(n1)
        {
            delete_node(n1);                        //This function deletes n1->next 
            printf("\n%d is deleted successfully .\n\n",key);
        }
         else
         printf("\nItem is not in the list !!! \n\n\n");
    }
return(list); 
} 


void delete_node(node *list)  //This function deletes list->next 
{ 
    node *n2;
    n2=list->next->next;
    free(list->next);
    list->next=n2;
} 



node *rearrange(node *list) 
{ 
    node *p1;
    sort(list);
    for(p1=list;p1->next!=NULL;p1=p1->next)
    {
        if(p1->num==p1->next->num)
        delete_node(p1);
    }
    return(list);
} 


void sort(node *list) 
{ 
    void exchange(int *s1,int *s2);
    node *p,*q;
    for(p=list;(p->next)!=NULL;p=p->next)
        for(q=list;(q->next)!=NULL;q=q->next)
        {
            if(q->num > q->next->num)            //simple bubble sort 
            exchange(&(q->num),&(q->next->num));
        }
} 

void exchange(int *s1,int *s2) 
{ 
    int temp;
    temp =*s1;
    *s1=*s2;
    *s2=temp;
}
------------------------------------------------------------
Remarks:
This program has a small bug try and find out.