Sorting elements of a one-way linked list

[MatthiasBerger]

So the task is to sort numbers which are stored in a one-way linked list by changing the links in the list (just changing the numbers contained within is not allowed). What I have now compiles but the program crashes when it compares elements. Some text output is included to help myself understand what's going on and at the "Elements are" output it doesn't really display what it should (displays an address?) yet I'm missing why that is so.

#include <iostream>
using namespace std;


class Elem
{
public:
	int num;
	Elem *next;
	Elem (int n) { num = n; next = NULL; };
};

class List
{
protected:
    Elem *first, *last;
public:
    Elem *current;
public:
    List () { first = last = current = NULL; };
    void add_element (int n);
    void delete_element ();
    int is_empty () { return (first == NULL); };
    void start () { current = first; };
    int end () { return (current == NULL); };
   void next(){if (!end())current = current -> next;};
   void sortList();
};


int main()
{
  List l;
  int k;
  cout << "Input an element(0 to end input):\n";
  cin >> k;
  while (k!=0)
  {
    l.add_element (k);
    cout << "Input an element(0 to end input):\n";
    cin >> k;
  };
  for (l.start(); !l.end(); l.next())
  {
    cout << l.current->num << endl;
  }

l.sortList();

  for (l.start(); !l.end(); l.next())
  {
    cout << l.current->num << endl;
  }

  while (!l.is_empty())
  {
    l.delete_element ();
  };

};

void List::add_element (int n)
{
    Elem *p = new Elem (n);
    if (first == NULL) first = last = p;
    else last = last -> next = p;
    current =p;
};

void List::delete_element ()
{
    Elem *p = first;
    if(!is_empty())
    {   if (current == first) current = first-> next;
        first = first -> next;
    delete p;
    if(is_empty())last = NULL;
    }

};

void List::sortList()
{
int count=0;
for (start(); !end(); next())
count++;

cout<<"Element count: "<<count<<endl;

for(int i = 1; i < count; i++)
{
    Elem* p1 = first;
    Elem* p2 = first->next;
    Elem* p3 = p2->next;
cout<<"Elements are "<<p1->num<<p2->num<<p3->num;
    for(int j = 1; j <= (count - i); j++)
    {cout<<p1<<p2<<p3<<endl;
       if(p2->num > p3->num)
       {
           p2->next = p3->next; //3 lines of moving the links
           p3->next = p2;
           p1->next = p3;
           p1       = p3; // 2 lines with moving forward in the list
           p3       = p2->next;
       }
       else
       {
           p1 = p2;
           p2 = p3;
           p3 = p3->next;
       }
    }
}
};

[TheIdeasMan]

Hi MatthiasBerger,

Try stepping through with a debugger and watch variables to see what is going on.

hope this helps

TheIdeasMan

[MatthiasBerger]

Well debugger does show me that things go bad at line 98 as the program tries to compare two addresses (I think they are addresses, not sure) instead of the values inside elements but that just brings me back to the original post in which I said the same thing phrased a bit differently - the local variables in the compare function don't do what they should (p2->num should return a number contained within the element not an address) and I'm unable to understand why.

[TheIdeasMan]

So if you have a problem with

if(p2->num > p3->num)

then use the debugger to see how p2, p3, num are initialised.

Is this a problem in main?

List l;

you haven't used the new operator, do this instead:

List *pList = new List();

pList is a pointer to the List object, in just the same way you created the Elem obj in List::add_element

The new operator dynamically allocates memory - if you don't use it then you have to use something like malloc which isn't any near as easy as using new.

Also p isn't a good name for a pointer to an Elem object. Elem isn't a good name either - don't abbreviate name too much. It can sometimes be a real advantage if variable names make sense. The usual convention for naming variables says that pointer variables should start with p. So pCElement tells us that it a pointer to a class obj named Element.

So use the debugger to check the initialisation of all your variables. If that is OK then there is some other logical problem.

Let is know how you go.

TheIdeasMan

[ne555]

p2->num is a number.
The problem is that p3 becomes a null pointer. Instead of using the counter, stop at the end of the list.

¿why are you bypassing the first cell?


@TheIdeasMan: this ain't java. We've got objects in c++
List l; does creates an object.

pCElement is an even worse name, you only added type information.
_that may change, ¿will you change the name?
_¿why do you need that info in the name? ¿can't just look up two lines where it is declared?

[Lowest0ne]

As a side, if you happen to swap the first or last elements, be sure to update your first and last member variables. For example:

p2->next = p3->next; //3 lines of moving the links
p3->next = p2;
p1->next = p3

if (p3 == tail) tail = p2;  // might be a good time to break the loop too

p1       = p3; // 2 lines with moving forward in the list
p3       = p2->next;

[TheIdeasMan]

@ne555

pCElement is an even worse name, you only added type information.

Forgive me if I am wrong, but is pCElement a worse name than p?

I usually work from a C++ coding standard found here

http://www.possibility.com/Cpp/CppCodingStandard.html

Just wondering what you might suggest?

_that may change, ¿will you change the name?
_¿why do you need that info in the name? ¿can't just look up two lines where it is declared?

I think sensible naming is important in programming. Poor naming can be the cause of confusion. A good name reinforces the idea of what the variable is for and makes it easier to understand.

This could be especially important when the variable holds a pointer. Confusion over pointers is very often the reason that errors occur in code.

I never use a single character for a variable name - even for an array subscript or a loop counter. The characters 1 i j l are often hard to see. It is much better to use a word that means something like Row or Column or DegreeCounter or MinuteCounter or SecondCounter as examples.

Also I prepend my variable names with characters that indicate the basic types:
d double
f float
i int
u unsigned
sh short
us unsigned short
l long
ll long long
ul unsigned long
str string

This is called Hungarian notation, and I find it very handy as long as one doesn't get carried away.


TheIdeasMan

[ne555]

The 'p' in add_element(), I would not use it.
In delete_element(), 'to_die' if you please (but really don't care)

In sort Elem *before, *here, *after
You know, meaningful names.

About Hungarian, there were several threats about that. An interesting reading http://www.joelonsoftware.com/articles/Wrong.html

But the typed one doesn't pay.

[TheIdeasMan]

In sort Elem *before, *here, *after
You know, meaningful names.

I wasn't complaining about all the names, just ones like p.

I read the article. The convention they talked about were bad

My notation convention just sticks to basic data types only, and I think are pretty easy to understand when you look at a couple of declarations.

I guess it all depends on who is looking at the code. Commercial programming would involve conforming to the organisations coding standard. Whichever convention it is probably doesn't matter too much as long as it is reasonable.

Edit:

I wasn't trying to force anyone into my convention - just trying to suggest that there could be a better way.