sorting linked list

[alamu]

please give the program for sorting a linked list without affecting the original value

[deceptikon]

Nobody is going to do your homework for you. But I'll give you a push in the right direction. You essentually have two options:

1. Build a new list in sorted order while traversing the old list.
2. Sort the old list into a new list.

It's a fairly subtle difference between the two, but the former assumes there's a sorted insertion function for the list while the latter assumes you'd modify something like the list insertion sort function here to build a new completely new list instead of splice nodes (a simple and minor change).

[alamu]

my question is sort a linked list without affecting the original value and without using a new list sir please guide me

[deceptikon]

Clearly you didn't read my post (probably because I didn't give you a full working program), because I explained exactly how to do it in two different ways.

[Sokurenko]

you need to modify only pointer "next", do you know what linked list is? If you know then you can draw something that you whant to do with it and then program this behaviour

[rubberman]

Basically, you cannot sort an unsorted list without modifying the list, unless you make a sorted copy of it without modifying the original. So, I think your original question is in question...

[raj527]

hi i can solve this problem

[raj527]

hey decepticon its me optimus prime user name- (rajgopal527)
i wonder how did u become administrator without having any basic knowlege of 
c language ?
now just get lost from daniweb and stop banning users form daniweb 
also open the thread of graphs using linked lists 
http://www.daniweb.com/software-development/c/threads/424743/graphs-using-linked-lists
here is the program 





#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
Position Find( int X, List L );
void Delete( int X, List L );
Position FindPrevious( int X, List L );
void Insert( int X, Position P );
void print(List L);


struct Node
    {
        int Element;
        Position    Next;
    };


void print(List L)
{

     if(L==NULL)
                 {
                 printf("\n list is empty \n");
                 return;
                 }
              do
              {
              if(L->Next==NULL)
              {
              printf("%d",L->Element);
               }
              else
               {
              printf("%d->",L->Element);
               }
              L=L->Next;
               }while(L!=NULL);
           }







 int IsLast( Position P, List L )
        {
            return P->Next == NULL;
        }


Position  Find( int X, List L )
      {
      Position P;
      P = L->Next;
      while( P != NULL && P->Element < X )
      P = P->Next;
      return P;
      }


 void Delete( int X, List L )
    {
        Position P, TmpCell;

        P = FindPrevious( X, L );


        if( !IsLast( P, L ) )
        {
        TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free( TmpCell );
        }
         else
         {
         printf("\n element not present in list\n");
         }
    }





Position FindPrevious( int X, List L )
    {
      Position P;
      P = L;
      while( P->Next != NULL && P->Next->Element < X )
      P = P->Next;
      return P;
    }
void  Insert( int X , Position P )
    {
     struct Node *r;
     r=FindPrevious(X,P);
     Position TmpCell;
     TmpCell = malloc( sizeof( struct Node ) );
     if( TmpCell == NULL )
     {
     printf("\n out of space!!!" );
     exit(1);
     }
TmpCell->Element = X;
TmpCell->Next = r->Next;
r->Next = TmpCell;
     }




main()
{

int i,key;
struct Node *head,*a,*s;
head=(struct Node*)malloc(sizeof(struct Node));
head->Next=NULL;
while(1)
{
printf("\n enter 1 to insert , 2 to print , 3 to delete , 4 to search 5 to return \n");
scanf("%d",&i);
    switch(i)
    {
         case 1:printf("\n enter the key value\n");
                scanf("%d",&key);
                Insert(key,head);
                break;

         case 2: a=head->Next;
                  print(a);
                  break;

         case 3: if(head->Next==NULL)
                 {
                 printf("\n list is empty");
                 break;
                 } 
                 printf("\n enter the key value to be deleted\n");
                 scanf("%d",&key);     
                 Delete(key,head);
                 break;
         case 4: printf("\n enter a value to be searched in list \n");
                 scanf("%d",&key);
                 s=Find(key,head);
                 if(s!=NULL)
                 {
                  printf("\n the key is present in linked list\n");                 
                 }
                  else
                 {
                  printf("\n the key is not present in linked list\n");      
                 }
                  break;
          case 5: return ;          

     }
     }
     }

     save this program as .c file and run in dev c++
     also ensure all the number entered are unique 

[deceptikon]

i wonder how did u become administrator without having any basic knowlege of c language ?

The two are unrelated. But if you want to discuss aspects the C language or standard library, I'll be happy to school you in a debate.

now just get lost from daniweb and stop banning users form daniweb

I only ban people who violate Daniweb's rules often enough to deserve it, and I can justify each and every one of them. I'm curious what your problem is, or who you really are since it's unusual for there to be such animosity given only 3 posts in this thread. Are you one of the rule breakers I've banned?

[alamu]

thank you mr.raj

[alamu]

sir i got error 112th line

[WaltP]

sir i got error 112th line

Sorry, but that's what you get for using someone else's code and not fixing your own code. You don't understand what he did and can't fix it.

[ra527]

alamu what error di u got ?
just download devc++ from this site
http://www.bloodshed.net/devcpp.html
and do just what i said

save this program as .c file and run in dev c++

save this program as .c file and run in dev c++

[WaltP]

If it only works in Dev-C++ then there's something terribly wrong. You should be able to compile C++ code in any C++ compiler.

[ra527]

moderator eyes have stopped completely working
so better observe before u talk that its a c program not c++
i am comfartable with devc++
if u find any other compiler that post the links here

[_avishek]

moderator eyes have stopped completely working

@ra527: Even after having been banned twice, why do you insist on posting such rude comments? You still have a lot to learn, not just about programming (your code is sloppy at best) but also on how to behave.

[WaltP]

Sorry. If it only works in Dev-C++ then there's something terribly wrong. You should be able to compile C code in any C compiler. It that better?

[deceptikon]

moderator eyes have stopped completely working
so better observe before u talk that its a c program not c++

It looks like a bastardized combination of C and C++ to me. I can only imagine that it compiles due to compiler extensions and quirks, but that means your code isn't portable (and for no reason at all). For example, in Insert() you mix declarations and statements:

r=FindPrevious(X,P);
Position TmpCell;

This is illegal prior to C99, but you're not using C99 because implicit int was completely removed and you use implicit int in your call to main():

main()
{
    ...
}

C++ also disallows implicit int, but not all compilers enforce this rule. However, something that all C++ compilers do enforce is the implicit conversion from void*, which you use here:

TmpCell = malloc( sizeof( struct Node ) );

This will only compile as C. So my guess is that mixing declarations and statements is coming from a gcc extension because you're not compiling as strict C and didn't realize it. If that's the case I'd recommend changing your build switches to include "-ansi", "-pendantic", and "-Wall". It also couldn't hurt to learn the different versions of C and what's allowed in each.

[milkshek]

[offensive remarks removed]
let alamu speak wheather his problem is solved ot not .....

[I_m_rude]

I seriuosly don't like when anybody talks rudely or bad with decpetikon. :'( please james sir, ban them. they don't have right to be part of this precious forumn. :'(

[alamu]

my problem not solved in my output the sorted values are displaying but i need to display the sorted values as well as the unsorted values (i.e)the original value given

[I_m_rude]

what exaclty do you want ? specify here only, may be I can help. thanks.

[alamu]

sorting the linked list without affecting the original value ,in output the sorted values are displaying but i need to display the sorted values as well as the unsorted values (i.e)the original value given

[deceptikon]

I see we've come full circle. You were given code that presumably works with only minor corrections to make it portable to your compiler. Have you even attempted to fix the code that raj so kindly gave you? Or are you expecting us to write the whole thing in its entirety for you so that all you need to do is turn it in for a grade?

[jameslowde]

i thank a lot to dani web

[optimus_prime_1]

new program which even reverses linked list
insert,sort,reverse,delete,search every thing now available

#include<stdio.h>
#include<stdlib.h>
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
Position Find( int X, List L );
void Delete( int X, List L );
Position FindPrevious( int X, List L );
void Insert( int X, Position P );
void print(List L);
Position reverse( List L );
struct Node
{
int Element;
Position Next;
};
void print(List L)
{
if(L==NULL)
{
printf("\n list is empty \n");
return;
}
do
{
if(L->Next==NULL)
{
printf("%d",L->Element);
}
else
{
printf("%d->",L->Element);
}
L=L->Next;
}while(L!=NULL);
}
int IsLast( Position P, List L )
{
return P->Next == NULL;
}
Position Find( int X, List L )
{
Position P;
P = L->Next;
while( P != NULL && P->Element < X )
P = P->Next;
return P;
}
void Delete( int X, List L )
{
Position P, TmpCell;
P = FindPrevious( X, L );
if( !IsLast( P, L ) )
{
TmpCell = P->Next;
P->Next = TmpCell->Next;
free( TmpCell );
}
else
{
printf("\n element not present in list\n");
}
}
Position FindPrevious( int X, List L )
{
Position P;
P = L;
while( P->Next != NULL && P->Next->Element < X )
P = P->Next;
return P;
}
void Insert( int X , Position P )
{
struct Node *r;
r=FindPrevious(X,P);
Position TmpCell;
TmpCell = malloc( sizeof( struct Node ) );
if( TmpCell == NULL )
{
printf("\n out of space!!!" );
exit(1);
}
TmpCell->Element = X;
TmpCell->Next = r->Next;
r->Next = TmpCell;
}
Position reverse(List L)
{
         struct Node *prev,*curr,*p;
         prev=NULL;
         p=curr=L->Next;
         free(L);

         while(curr != NULL)
         {
                          p=p->Next;
                          curr->Next=prev;
                          prev=curr;
                          curr=p;
                          }
           L=malloc(sizeof(struct Node));
           L->Next=prev;
           return(L);
           }               








main()
{
int i,key;
struct Node *head,*a,*s;
head=(struct Node*)malloc(sizeof(struct Node));
head->Next=NULL;
while(1)
{
printf("\n enter 1 to insert , 2 to print , 3 to delete , 4 to search 5 to reverse 6 to return \n");
scanf("%d",&i);
switch(i)
{
case 1:printf("\n enter the key value\n");
scanf("%d",&key);
Insert(key,head);
break;
case 2: a=head->Next;
print(a);
break;
case 3: if(head->Next==NULL)
{
printf("\n list is empty");
break;
}
printf("\n enter the key value to be deleted\n");
scanf("%d",&key);
Delete(key,head);
break;
case 4: printf("\n enter a value to be searched in list \n");
scanf("%d",&key);
s=Find(key,head);
if(s!=NULL)
{
printf("\n the key is present in linked list\n");
}
else
{
printf("\n the key is not present in linked list\n");
}
break;
case 5:head=reverse(head);
       print(head->Next);
       break;
case 6: return ;
}
}
}

[optimus_prime_1]

in findprevious function replace the statement P->Next->Element < X
by this new statement P->Next->Element != X
this will delete the elements in proper manner without sorting the linked list
also linked list can be reversed

[nndung179]

L1: original list
L2: Sorted list
1. Copy all value of L1 into L2.
2. Sort L2.

[gaandu_danibeb]

logic for sorting linked list
no need to copy L1 to L2 .. let L2 be empty initially
for each node in L1 find correct postion in
L2
for example let L1 contain keys 30 20 10 40
and L2 be empty then
then expand L2 in this way
->30
->20 30
->10 20 30
->10 20 30 40
sorted list created and stored in L2 without modifying L1

thanks to optimus prime

[satya_19]

Hey I got a better solution.
Here goes my code .

using namespace std;

/* Link list AnjelinaJolie */
class AnjelinaJolie {
public:
    int data;
    AnjelinaJolie* next;
};

/* function prototypes */
AnjelinaJolie* SortedMerge(AnjelinaJolie* a, AnjelinaJolie* b);
void FrontBackSplit(AnjelinaJolie* source,
                    AnjelinaJolie** frontRef, AnjelinaJolie** backRef);

/* sorts the linked list by changing next pointers (not data) */
void MergeSort(AnjelinaJolie** headRef)
{
    AnjelinaJolie* head = *headRef;
    AnjelinaJolie* a;
    AnjelinaJolie* b;

    /* Base case -- length 0 or 1 */
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    /* Split head into 'a' and 'b' sublists */
    FrontBackSplit(head, &a, &b);

    /* Recursively sort the sublists */
    MergeSort(&a);
    MergeSort(&b);

    /* answer = merge the two sorted lists together */
    *headRef = SortedMerge(a, b);
}

AnjelinaJolie* SortedMerge(AnjelinaJolie* a, AnjelinaJolie* b)
{
    AnjelinaJolie* result = NULL;

    /* Base cases */
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);

    /* Pick either a or b, and recur */
    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return (result);
}

/* UTILITY FUNCTIONS */
/* Split the AnjelinaJolies of the given list into front and back halves,
    and return the two lists using the reference parameters.
    If the length is odd, the extra AnjelinaJolie should go in the front list.
    Uses the fast/slow pointer strategy. */
void FrontBackSplit(AnjelinaJolie* source,
                    AnjelinaJolie** frontRef, AnjelinaJolie** backRef)
{
    AnjelinaJolie* fast;
    AnjelinaJolie* slow;
    slow = source;
    fast = source->next;

    /* Advance 'fast' two AnjelinaJolies, and advance 'slow' one AnjelinaJolie */
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }

    /* 'slow' is before the midpoint in the list, so split it in two
    at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}

/* Function to print AnjelinaJolies in a given linked list */
void printList(AnjelinaJolie* AnjelinaJolie)
{
    while (AnjelinaJolie != NULL) {
        cout << AnjelinaJolie->data << " ";
        AnjelinaJolie = AnjelinaJolie->next;
    }
}

/* Function to insert a AnjelinaJolie at the beginging of the linked list */
void push(AnjelinaJolie** head_ref, int new_data)
{
    /* allocate AnjelinaJolie */
    AnjelinaJolie* new_AnjelinaJolie = new AnjelinaJolie();

    /* put in the data */
    new_AnjelinaJolie->data = new_data;

    /* link the old list off the new AnjelinaJolie */
    new_AnjelinaJolie->next = (*head_ref);

    /* move the head to point to the new AnjelinaJolie */
    (*head_ref) = new_AnjelinaJolie;
}

/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    AnjelinaJolie* res = NULL;
    AnjelinaJolie* a = NULL;

    /* Let us create a unsorted linked lists to test the functions
Created lists shall be a: 2->3->20->5->10->15 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);
    push(&a, 20);
    push(&a, 3);
    push(&a, 2);

    /* Sort the above created Linked List */
    MergeSort(&a);

    cout << "Sorted Linked List is: \n";
    printList(a);

    return 0;
}