Sorted Linked List

[massimo]

Hey,

I wrote this program which should take the numbers entered and sort them
out. It doesn¹t matter what order, if decreasing or increasing.

I guess I'm confused in the sorting part. Anyone has any advices??

#include <iostream>
using namespace std;

struct link
{
int data;
link *pNext;
link *pHead;
link *current;
};

class linkList
{
private:
link *pHead;
public:
linkList()
{ pHead = NULL;}
void add_Item(int d);
void display();
};

void linkList::add_Item(int d)
{
link *pPrev;
link *pSucc;

pPrev = pHead;
while(true)
{
pPrev = pSucc;
pSucc = pSucc -> pNext;

if(pSucc == NULL)
break;

if(d >= pSucc -> data)
break;
}

link *newLink = new link;
newLink -> data = d;
pPrev -> pNext = newLink;
newLink -> pNext = pSucc;
}

void linkList::display()
{
link *current = pHead;
while (current != NULL)
{
cout << current -> data << endl;
current = current -> pNext;
}
}

int main ()
{
int input;

linkList numbers;

cin >> input;
while(input >= 0)
{
cout << "Enter any numbers" << endl;
cin >> input;
numbers.add_Item(input);
}

numbers.display();

return 0;
}

 

[osmium]

I wrote this program which should take the numbers entered and sort them
out. It doesn¹t matter what order, if decreasing or increasing.

I guess I'm confused in the sorting part. Anyone has any advices??

#include <iostream>
using namespace std;

struct link
{
int data;
link *pNext;
link *pHead;
link *current;
};

class linkList
{
private:
link *pHead;
public:
linkList()
{ pHead = NULL;}
void add_Item(int d);
void display();
};

void linkList::add_Item(int d)
{
link *pPrev;
link *pSucc;

pPrev = pHead;
while(true)
{
pPrev = pSucc;
pSucc = pSucc -> pNext;

if(pSucc == NULL)
break;

if(d >= pSucc -> data)
break;
}

link *newLink = new link;
newLink -> data = d;
pPrev -> pNext = newLink;
newLink -> pNext = pSucc;
}

void linkList::display()
{
link *current = pHead;
while (current != NULL)
{
cout << current -> data << endl;
current = current -> pNext;
}
}

int main ()
{
int input;

linkList numbers;

cin >> input;
while(input >= 0)
{
cout << "Enter any numbers" << endl;
cin >> input;
numbers.add_Item(input);
}

numbers.display();

return 0;
}

The "right" way to do it is to write a merge sort. I am sure there are tons
of tutorials on the web, probably even Java applets to demonstrate the
process.

The quick and dirty way out is to traverse the list, put everything into an
array, use qsort to sort the array, and write a new list from the sorted
array. I doubt if an instructor would care for that approach.

Note also that there are sort aids in the STL.

 

[John Harrison]

Hey,

I wrote this program which should take the numbers entered and sort them
out. It doesn¹t matter what order, if decreasing or increasing.

I guess I'm confused in the sorting part. Anyone has any advices??

I would say to throw away the code and start again, but comments below.

#include <iostream>
using namespace std;

struct link
{
int data;
link *pNext;
link *pHead;
link *current;

Why do you need a pointer back to head? What is current?

};

class linkList
{
private:
link *pHead;
public:
linkList()
{ pHead = NULL;}
void add_Item(int d);
void display();
};

It's good that you have two seperate classes, one for the links and one for
the list.

void linkList::add_Item(int d)
{
link *pPrev;
link *pSucc;

pSucc is uninitialised.

pPrev = pHead;
while(true)
{
pPrev = pSucc;

pSucc is still uninitialised.

pSucc = pSucc -> pNext;

pSucc is still uninitialised, program crashes here.

OK, here how to do it properly. Here's some suitable classes

struct Link
{
int data;
Link* next;
};

class List
{
public:
List() { head = NULL; }
void add_item(int d);
void display();
private
Link* head;
};

Now the thing is to think carefully about the add_item algorithm. Lets say
we are going to add items in ascending order, smallest first, largest last.
Clearly you are going to have to loop though the list looking for the place
to add the new data. When will that loop end? One reason for the loop to end
is when we find data in the list that is larger than the one we are adding,
then we stop looping and add the item before the larger data. The other
reason the loop might end is that we hit the end of the list, then we add an
item at the end of the list. Now an important simplification is that both
these cases are actually the same. In both cases we add a new link after the
previous link. In the case when we hit the end of the list the previous link
is the last link in the list so adding after that link is adding to the end
of the list.

Now special case is adding to an empty list or adding a number that is
smaller than all the numbers in the list. In that case we add to the
beginning of the list.

Here's the code

void List::add_item(int d)
{
// test for empty list or data smaller than first item in list
if (head == NULL || d <= head->data)
{
// add to beginning of list
Link* temp = new Link;
temp->data = d;
temp->next = head;
head = temp;
}
else
{
// we don't need to add to beginning of list
// so loop though list looking for where to add
Link* prev = head;
Link* curr = head->next;
// keep looping while not end of list and data bigger than current
item
while (curr != NULL && d > curr->data)
{
prev = prev->next;
curr = curr->next;
}
// found place to add, add after previous item
Link* temp = new Link;
temp->data = d;
temp->next = curr;
prev->next = temp;
}
}

This is untested code so it might have bugs, but the main thing is you
understand the algorithm.

john

 

[massimo]

Hey john,

Thank you very much. I totally understand the checking/sorting algorithm.

I debugged the program and it compiles fine. I still believe I have some
problem with the display() and main(); I'm doing something wrong and I don't
see it!!
When it compiles it doesn't prompt me and if I enter the numbers, it just
return "Enter a number" for as many numbers I entered.
How do I space the number??
Let's say I want to enter:
12 34 56 23 45 33 and the on enter I want the program to spit out the sorted
list.

void List::display() // display links
{
Link *curr = head; // set pointer to first link
while (curr != NULL) // on last link stop
{
cout << curr -> data << endl; // print data
curr = curr -> next; // move to next
}
}

int main ()
{
int input;

List numbers; // make linked list

cin >> input;
while(input >= 0)
{
cout << "Enter any numbers" << endl;
cin >> input;
numbers.add_item(input);
}

numbers.display();

return 0;
}

Thanks,mass

 

[massimo]

Well,

I guess if I use space between numbers the compiler assumes that are
different numbers. Ok that¹s good.

Example_
if I enter these 4 numbers:
12 34 52 24 26

This is the cout:
Enter any numbers
Enter any numbers
Enter any numbers
Enter any numbers
Enter any numbers

Obviously if I enter:
1265
This is the cout:
Enter any numbers

So it's definitely something wrong with my prompt and the main();

Thanks,mass

 

[Thomas Matthews]

Hey john,

Thank you very much. I totally understand the checking/sorting algorithm.

I debugged the program and it compiles fine. I still believe I have some
problem with the display() and main(); I'm doing something wrong and I don't
see it!!
When it compiles it doesn't prompt me and if I enter the numbers, it just
return "Enter a number" for as many numbers I entered.
How do I space the number??
Let's say I want to enter:
12 34 56 23 45 33 and the on enter I want the program to spit out the sorted
list.

[snip]

My suggestion is to write a small main() function that reads in the
numbers then spits them out:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

typedef vector<int> Vector_Of_Ints;

int main(void)
{
// Create a container for the numbers.
Vector_Of_Ints numbers;

int users_number;

// Read in the numbers until EOF or error:
while (cin >> users_number)
{
numbers.push_back(users_number);
}

// Now to sort them:
sort(numbers.begin(), numbers.end());

// After sorting, spit them out.
for (unsigned int i = 0; i < numbers.size(); ++i)
{
cout << " " << numbers;
}
cout << endl;

return EXIT_SUCCESS;
}

The purpose of this program is to work out how you want to
enter the numbers. Once you have that working, add in calls
to your linked list system.

My understanding is that when you enter a lot of numbers on
one line:
12 34 56 23 45 33
They will be placed into a buffer until you press Enter.
At that point, whenever a "cin >> number" is performed,
the next number in the buffer is given to the program.

When I ran the program, I had to supply my operating
system with an EOF character (like CTRL-D). It read
every number on the line.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

 

[massimo]

[Fully functional]. Thanks


#include <iostream>
using namespace std;


struct Link
{
int data;
Link* next;
};

class List
{
public:
List() { head = NULL; }
void add_item(int d);
void display();
private:
Link* head;
};

void List::add_item(int d)
{
// test for empty list or data smaller than first item in list
if (head == NULL || d <= head->data)
{
// add to beginning of list
Link* temp = new Link;
temp->data = d;
temp->next = head;
head = temp;
}
else
{
// Don't need to add to beginning of list
// so loop though list looking for where to add
Link* prev = head;
Link* curr = head->next;
// keep looping while not end of list and data bigger than
currentitem
while (curr != NULL && d > curr->data)
{
prev = prev->next;
curr = curr->next;
}
// found place to add, add after previous item
Link* temp = new Link;
temp->data = d;
temp->next = curr;
prev->next = temp;
}
}

void List::display() // display links
{
Link* curr = head; // set pointer to first link
while (curr != NULL) // on last link stop
{
cout << curr -> data << endl; // print data
curr = curr -> next; // move to next
}
}

int main ()
{
int input = 1;

List numbers; // make linked list

cout << "Enter any numbers" << endl;
while(input != 0)
{
cin >> input;
numbers.add_item(input);
}

numbers.display();
return 0;
}

//=========================================================================