By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,131 Members | 1,728 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,131 IT Pros & Developers. It's quick & easy.

Need help in sorting a singly linked list...

P: 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
Share this Question
Share on Google+
3 Replies


Banfa
Expert Mod 5K+
P: 8,916
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

P: 4
Thankx Banfa, God Bless u.
Aug 6 '06 #3

P: 1
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.