468,496 Members | 1,798 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,496 developers. It's quick & easy.

Need help in sorting a singly linked list...

4
// Linked Lists in classes(excluding structures) without using tail pointer

# include<iostream.h>
# include<stdlib.h>

void Swap(int num1, int num2)
{
int a = num1;
num2 = num1;
num2 = a;
}

class node
{
private:
int data;
node* next;
node* headptr;
public:
node()
{headptr = NULL;}
void insert_at_head(int d)
void insert_at_tail(int d);

void display_all();

void sort_ascending_order(); // complicated
void sort_descending_order(); // complicated



};

///////////////////////////////////////////////////////////////////////////////

void node::insert_at_head(int d)
{
node* ptr = new node;
ptr->data = d;

ptr->next = headptr;
headptr = ptr;

}

void node::display_all()
{
node* tempptr = headptr;

if(headptr == NULL)
{cout<<"The list is empty"<<endl;}

while(tempptr->next != NULL)
{
cout<<tempptr->data<<" , ";
tempptr = tempptr->next;
}

if(tempptr->next == NULL)
{cout<<tempptr->data;}
}

void node::insert_at_tail(int d)
{
node* temptr = new node;
temptr->data = d;
temptr->next = NULL;

node* ptrCurrent = headptr;

while(ptrCurrent->next != NULL)
{
ptrCurrent = ptrCurrent->next;

}
ptrCurrent->next = temptr;
}





void node::sort_ascending_order()
{
node* realptr = headptr;
node* ptrCurrent = headptr;

while(ptrCurrent->next != NULL)
{
if(ptrCurrent->data > ptrCurrent->next->data)
{
realptr->data = ptrCurrent->data;
cout<<realptr->data<<endl;

Swap(ptrCurrent->data,ptrCurrent->next->data);
}
ptrCurrent = ptrCurrent->next;
realptr = realptr->next;


}

}




void main()
{
node n1;
n1.insert_at_head(1);
n1.insert_at_head(2);
n1.insert_at_head(3);
n1.insert_at_tail();
n1.insert_at_tail();
n1.display_all();
cout<<endl<<endl;

cout<<"Testing Sorting"<<endl<<endl;
n1.sort_ascending_order();

cout<<endl<<endl;
n1.display_all();

}

//void node::sort_ascending_order() this is not working

Please help me out using singly linked list and do keep the code less complicated. Thankx
Aug 5 '06 #1
3 7472
Banfa
9,055 Expert Mod 8TB
My computer just crashed at the end of me typing a long post, 'fraid I can be bother to type it all again but here are some pointers

Your Swap function doesn't work (go on try it with 2 ints)

You need to look up about static data members and static function members of classes

You should always check your pointers, where you have already checked them you need to act on it not just continue as if everything was OK insert_at_head and insert_at_tail among other places

In your print function your while loop has the wrong control expression and wont print the last list member, the final if statement is useless as the condition MUST be false for the while loop to exit.

You can not perform an array sort in a single pass of the array, it is not possible. The realptr variable is confusing and useless, it always points to the same place as ptrCurrent.

1 sort method is called a bubble sort, you scan down your list comparing adjacent pairs of entries. If the need swaping you swap them, when you get to the end of the list if you swapped any entries on this scan of the list then you scan the list again.

1 possible method is
Aug 5 '06 #2
malik
4
Thankx Banfa, God Bless u.
Aug 6 '06 #3
void LinkList::sort()
{
Node *q, *r;
for( q = p ; q->link != NULL ; q = q->link )
{
for( r = q->link ; r->link != NULL ; r = r->link )
{
if (r->data<q->data)
{
int temp;
temp = r->data;
r->data = q->data;
q->data = temp;
}
}
}
}
Dec 11 '06 #4

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

18 posts views Thread by Matthias Kaeppler | last post: by
19 posts views Thread by RAJASEKHAR KONDABALA | last post: by
4 posts views Thread by dssuresh6 | last post: by
7 posts views Thread by Shwetabh | last post: by
13 posts views Thread by XXXXXX.working.in.my.blood | last post: by
3 posts views Thread by jou00jou | last post: by
23 posts views Thread by Himanshu Chauhan | last post: by
4 posts views Thread by saki | last post: by
3 posts views Thread by gieforce | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.