SORT a LINKED LIST containing STRINGS

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

typedef struct STR_DATA
{
    char *name;
    struct STR_DATA *next;
}NODE;

int count=0;
void add_names(NODE **head);
void sort_names(NODE *head);
void print_names(NODE *head);
char printmenu(NODE *head);

int main()
{
    NODE *head=NULL;
    char ch='y';
    int flag=1;

    while(flag)
    {
        ch = printmenu(head);
        switch(ch)
        {
            case '0':
                    printf("\n\nEXITING...");
                    flag = 0;
                    break;
            case '1':
                    while ((ch = getchar()) != '\n' && ch != EOF);
                    add_names(&head);
                    break;
            case '2':
                    while ((ch = getchar()) != '\n' && ch != EOF);
                    sort_names(head);
                    break;
            default:
                    printf("\n\nENTER VALID CHOICE...");
                    break;   
        }
       
    }

    printf("\n\n");
    system("wait");
    printf("\n");
    return 0;
}
char printmenu(NODE *head)
{
    char ch;

    printf("\nCurrent list: ");
    print_names(head);
    printf("\nWHAT TO DO: ");
    printf("\n[1] ADD a name\n[2] SORT names");
    printf("\n\nEnter choice: ");
    scanf("%c",&ch);

    return ch;
}
void add_names(NODE **head)
{
    NODE *new_node;
    int num_char=0;
    char *str1=NULL,ch='x';

    new_node =(NODE*)malloc(1*sizeof(NODE));
    count++;
    new_node->next=*head;
    *head=new_node;

    printf("\nEnter name : ");   
    while(ch!='\n' && ch != EOF)
    {
        ch=getchar();
        if(ch=='\n')
            break;
       
        num_char++;
        str1 = (char*)realloc( str1,(num_char+1)*sizeof(char));
        if(str1 == NULL)
        {
            printf("\nERROR: reallocating memory...\n\n");
            exit(1);
        }

        str1[num_char-1]=ch;
        str1[num_char]='\0';
    }
   
    new_node->name = (char*)malloc((num_char+1)*sizeof(char));
    strcpy(new_node->name,str1);
    free(str1);
}

void sort_names(NODE *head)
{
    int i,j;
    NODE *curr,*prev;
    char *temp1,*temp2;

    for(i=0;i<count-1;i++)
    {
        prev=head;
        curr=head->next;               
        for(j=0;j<count-1-i;j++)
        {
            if(strcmp(prev->name,curr->name) > 0)
            {
                temp1 = (char*)malloc(strlen(prev->name));
                temp2 = (char*)malloc(strlen(curr->name));
                strcpy(temp1,prev->name);
                strcpy(temp2,curr->name);

                curr->name = (char*)realloc(curr->name,strlen(temp1));
                prev->name = (char*)realloc(prev->name,strlen(temp2));
                strcpy(prev->name,temp2);
                strcpy(curr->name,temp1);
                free(temp1);
                free(temp2);
            }
            prev=curr;
            curr=curr->next;
        }
    }
}

void print_names(NODE *head)
{
    if(!head)
    {
        printf("EMPTY");
        return;
    }
    while(head)
    {
        printf("%s|",head->name);
        head=head->next;
    }
}

Modify STACK EXAMPLE to create A DYNAMIC QUEUE

DYNAMIC QUEUE using DYNAMIC STACK

//TITLE         DYNAMIC QUEUE by modifying DYNAMIC STACK

//AUTHOR        VINAY CHOUDHARY

//DATE          26 OCT 2009

//This is a C program for DYNAMIC queue using stack functions

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define NUM 5

/*

*pos  :    we will use "pos" to point to top element in array,            used in pop, value updates in push.

*arr  :    pointer to array which is allocated memory at run-time.Can be replaced by static array. Just comment out part where we are using malloc() for array in push().

num   :    "num" tells how much data is present.

*next :    "*next" is pointer to next stack element.

*/

typedef struct blk{

     int *pos;                 

     int *arr;                 

     int num;         

     struct blk *next;   

}stack;

/*

PUSH FUCTION : we pass head as pointer and data here. Head is stored in backup for returning new value when stack is created for first time, else it contains old head value.

In loop above we check if head exists and go to last stack,which has next == null. There we check if head(stack) exists or not or if array is full for current last stack. In both cases we create a new stack as temp. temp points to NULL, since it will be last stack and has no data at present so num = 0 for temp and make pos to point to base of arr.

Now if stack doesnt exist then assign temp as head of stack since we will add data to it. Also since this is new head, store it in backup for returning purpose, else if array has filled for current last stack attach newly created temp stack to stack by storing its address in next of curent stack and make head same as temp since we add data to newly created stack(temp) using head(head=temp).

Then add data and increment index and return backup

*/

stack* push(stack *head,int data)

{         

     stack* backup,*temp;                

     for(backup = head;head && head->next != NULL;head = head->next);               

     if(head == NULL || head->num == NUM)

     {              

           temp = (stack *)malloc(1*sizeof(stack));  

           temp->arr = (int*)malloc(NUM*sizeof(int));

           temp->next = NULL;                                  

           temp->num = 0;      

           temp->pos = temp->arr;                              

           if(backup == NULL)

                backup = head = temp;

           else if(head->num == NUM)

                head = head->next = temp;

     }                                        

     head->arr[head->num++] = data

    

     return backup;

}

//POP FUNCTION: we pass head as pointer and data as pointer here.

//save backup as head;

//Read data at pos. pos is where queue starts

//since data at pos is read, now we will read next element next time so //pos++

//and take data in pointer passed, which is collected in main

//here we check if array of current last stack has become empty, if so

//second last stack, use temp to make second last stack to point to NULL. //Hence stack

//pointed by temp is now the last stack. Free memory of stack to be deleted.

//NOTE THAT stack is deleted only when no data is left

//whether updated or not return backup which is collected as head in main //program

stack* pop(stack *head,int *data)

{        

stack* backup,*temp=NULL;

     backup = head;                                 

     *data = *head->pos;       

     head->pos++;              

     --head->num;                   

if(head->num == 0)

{                    

temp = head->next;

           free(head->arr);    

           free(head);               

           backup = temp;           

}         

     return backup; 

}

void display(stack *head)

{   

     int *p,i;                                 

    

     printf("\nCURRENT STACK: ");

    

     if(!head)

           printf("DOESN'T EXIST");

    

     while(head)

{

           for(i=0,p=head->pos;i<head->num;p++,i++)

                printf("%d ",*p);

           head = head->next;

     }

}

void main()

{

     stack *head=NULL;

     int data,run=1;

     char ch;

     while(run)

{

           display(head);

           printf("\n\nWHAT TO DO ?");

           printf("\n1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\nYOUR OPTION : ");

           scanf(“%c”,&ch);

           switch(ch)

{

                case '1':

{

                     printf("Enter number to push: ");

                     scanf(“%d”,&data);

                     head = push(head,data);        

                     break;

                }

    

                case '2':

{                                         

                     if( (head) )

{                              

                           head = pop(head,&data);   

                           printf("DATA POPPED: %d",data);

                          

                     }

                     else

                           printf("CAN'T POP: NO DATA IN STACK");

                     break;

                }

    

                case '3':

{

                     display(head);

                     break;

                }

                case '4':

{

                     run = 0;

                     break;

                }

               

                default:

{

                     printf("\nENTER VALID OPTION");

                     break;

                }

           }

     }

     printf("\n\n");

}

A STACK PROGRAM EXAMPLE.

PROBLEM : we must create a stack using linked list with following specifications:
1. USING LINKED LIST
2. DYNAMIC IN SIZE
3. EACH STACK NODE CONTAINS AN ARRAY OF N(=5 in code) SIZE.

SAMPLE DIAGRAM

The code is shown below:

//TITLE         DYNAMIC STACK

//AUTHOR        VINAY CHOUDHARY

//DATE          26 OCT 2009

//This is a C program for DYNAMIC STACK

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define NUM 5

//pointer to array which is allocated memory at run-time. Can be //replaced by static

//array. Just comment out part where we are using malloc() for array //in push(). "num"

//tells how much data is present. "*next" is pointer to next stack

typedef struct blk

{

     int *arr;                 

     int num;                  

     struct blk *next;         

}stack;

//PUSH FUCTION : we pass head as pointer and data here.

//head is stored in backup for returning new value when

//stack is created for first time, else it contains old head value.

//In for loop we check if head exists and go to last stack,which has //next == null

//here we check if head(stack) exists or not or if array is

//full for current last stack. In both cases we create a new stack

//as temp. temp points to NULL, since it will be last stack

//and has no data at present so num = 0 for temp.

//now if stack doesnt exist then assign temp as head of stack since //we will add data to it. Also since this is new head store it in //backup for returning purpose,else if array has filled for current //last stack attach newly created temp stack to stack by storing its //address in next of curent stack and make head same as temp since //we add data to newly created stack(temp) using head(head=temp)

//add data

//and increment index. THIS INDEX CAN BE USED AS STACK POINTER

stack* push(stack *head,int data)

{         

     stack* backup,*temp;                

                                                    

     for(backup = head;head && head->next != NULL;head = head->next);               

    

     if(head == NULL || head->num == NUM){          

           temp = (stack *)malloc(1*sizeof(stack));  

           temp->arr = (int*)malloc(NUM*sizeof(int));

           temp->next = NULL;                                  

           temp->num = 0; 

           if(backup == NULL)             

                backup = head = temp;

           else if(head->num == NUM)      

                head = head->next = temp; 

     }                                              

     head->arr[head->num] = data;   

     head->num = head->num + 1;     

     return backup;

}

//POP FUNCTION: we pass head as pointer and data as pointer here.

//temp will have first stack if there is only one stack else it //stores second last stack address

//in loop above we intialise temp = head and go to last stack //structure.

//decrement index. THIS INDEX CAN BE USED AS STACK POINTER

//and take data in pointer passed, which is collected in main.

//here we check if array of current last stack has become empty, if //so we need to delete it. But if there was only one stack (then //temp == head), make backup point to NULL and return it later, //since existing stack will //be removed.

//if there were more than one stacks, then delete last one. Since //temp has address of

//second last stack, use temp to make second last stack to point to //NULL. Hence stack pointed by temp is now the last stack. Free //memory of stack to be deleted.

stack* pop(stack *head,int *data)

{   

     stack* backup=NULL,*temp=NULL;

    

     for(backup = head,temp = head;head->next != NULL;temp = head,head = head->next);

    

     head->num = head->num - 1;     

     *data = head->arr[head->num];  

     if(head->num == 0)

{         

           if(temp == head)    

                backup = NULL; 

           temp->next=NULL;    

           free(head->arr);    

           free(head);               

     }

     return backup;

}

void display(stack *head)

{

     int i;

    

     printf("\nCURRENT STACK: ");

    

     if(!head)

           printf("DOESN'T EXIST");

    

     while(head)

{

           for(i=0;i<head->num;i++)

                printf("%d ",head->arr[i]);

           head = head->next;

     }

}

void main()

{

     stack *head=NULL;

     int data,run=1,cls=0;

     char ch;

     while(run)

{

           display(head);

           printf("\n\nWHAT TO DO ?");

           printf("\n1. PUSH\n2. POP\n3. DISPLAY\n4. EXIT\nYOUR OPTION : ");

           scanf(“%c”,&ch);

           switch(ch)

{

                case '1':{

                     printf("Enter number to push: ");

                     scanf(“%d”,&data);

                     head = push(head,data);        

                     break;

                }

    

                case '2':{                                

                     if( (head) )

{                              

                           head = pop(head,&data);   

                           printf("DATA POPPED: %d",data);

                     }

                     else

                           printf("CAN'T POP: NO DATA IN STACK");

                     break;

                }

    

                case '3':{

                     display(head);

                     break;

                }

                case '4':{

                     run = 0;

                     break;

                }

               

                default:{

                     system("cls");

                     printf("\nENTER VALID OPTION");

                     break;

                }

           }

     }

     printf("\n\n\);

}