Linked Lists C++ Sorting Integers

[notfornothing21]

I am just learning linked lists and I need to start off my inputing integers and outputing them in a sorted list. I have written a code and pretty confident that the code make sense, but maybe it is out of sequence is why it is not working? I am able to input the integers, which means the loop is working, but then it stops. Code is below. Do I maybe need to put the Sorting information also into a function? And if so, I guess I am confused as to where in Int Main I would put it -- in the loop? Any help is appreciated.
I pasted the code below, but lost its format so I tried to reformat as best I could. THANKS!!

**********************************************************

#include <iostream>
#include <fstream>
using namespace std;


//Functions
void GetData (int& number);


const int nil=0;
class node_type


{
public:
int num; // Numbers that we are entering
node_type *next;
};


void main ()
{
node_type *first, *p, *q, *newnode;
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=2; i<=13; i++)


{
GetData (number);
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode;
p=newnode;
}


//Now Sort the List


if (first == nil)


{
first = newnode;
}
else
{


if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
}
else
q=first;
p=(*q).next;
if (p==nil)
(*first).next=newnode;
else
while ((*p).num < (*newnode).num  && ((*p).next!=nil))
q=p;
p=(*p).next;
//endwhile
//endif
if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
(*p).next=newnode;
//endif
}//endif
//endif



q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}
//endwhile


}


void GetData(int& number)


{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

[Lazaro Claiborn]

I am just learning linked lists and I need to start off my inputing integers and outputing them in a sorted list. I have written a code and pretty confident that the code make sense, but maybe it is out of sequence is why it is not working? I am able to input the integers, which means the loop is working, but then it stops. Code is below. Do I maybe need to put the Sorting information also into a function? And if so, I guess I am confused as to where in Int Main I would put it -- in the loop? Any help is appreciated.
I pasted the code below, but lost its format so I tried to reformat as best I could. THANKS!!

**********************************************************

#include <iostream>
#include <fstream>
usingnamespace std;

//Functions
void GetData (int& number);

constint nil=0;
class node_type

{
public:
int num; // Numbers that we are entering
node_type *next;
};

void main ()
{
node_type *first, *p, *q, *newnode;
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=2; i<=13; i++)

{
GetData (number);
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode;
p=newnode;
}

//Now Sort the List

if (first == nil)

{
first = newnode;
}
else
{

if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
}
else
q=first;
p=(*q).next;
if (p==nil)
(*first).next=newnode;
else
while ((*p).num < (*newnode).num && ((*p).next!=nil))
q=p;
p=(*p).next;
//endwhile
//endif
if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
(*p).next=newnode;
//endif
}//endif
//endif

q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}
//endwhile

}

void GetData(int& number)

{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

int main should to return an int.

Good luck, LamaBot

[Lazaro Claiborn]

void main ()
{
node_type *first, *p, *q, *newnode;
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=2; i<=13; i++)
{
GetData (number);
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode;
p=newnode;
}

//Now Sort the List
if (first == nil)
{
first = newnode;
}
else
{
if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
}
else
q=first;

Ok at this point in the program, p points to the first element in the list. Keep that in mind.

p=(*q).next;

So no matter what, p is assigned q. Keep that in mind.

if (p==nil)
(*first).next=newnode;
else
while ((*p).num < (*newnode).num && ((*p).next!=nil))
q=p;
p=(*p).next;
//endwhile
//endif

So the else is executed if the user entered a number for the last element that is less than or equal to the first. This is a problem because p at this point would equal q which isn't assigned anything!

if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
(*p).next=newnode;
//endif
}//endif
//endif

q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}
//endwhile

}

void GetData(int& number)

{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

You need to delete the allocated memory too. Mull over this a little and get back to me. Very good for a beginner might I say, kudo's. Although you could format the code a bit better, the code is dense nonetheless.

Good luck, LamaBot

[Infarction]

Lazaro, please do everyone else a favor and don't quote hugely long threads for a one line reply. Or, if you're quoting to that your reply has context, please trim the quoted part as much as possible. Thanks.

[Infarction]

Ok, a list of things.

First, as Lazaro pointed out, main should be type int, not void. A return 0; is then implied, but most people add it for clarity's sake.

Second, on a matter of style: your use of nil is good, but you might consider using NULL like everyone else does. You can usually get it from <cstdlib> but I think it's in <cstddef> if you're really worried about being precise.

Third, another note of style. Instead of the *(ptr).member syntax, you can use ptr->member. Example:

firs->num = number; // (*first).num = number;
first->next = NULL; // (*first).next = nil; and following note 2

Fourth, more style. Your for loop condition is whacky. Since you wrote it, it's probably obvious to you that you're creating nodes 2-13. Most people reading this would probabaly do a double-take at first. To make 12 more nodes, most people would just do for(int i = 0; i < 12; i++) .

Fifth, yet more style. Putting a blank line between for or if constructs is also confusing. The common styles are same line or next line. And, if the enclosed block only has a single statement, you can get away without braces. With respect to that last, having a blank line looks really weird, to me at least.

Now we get into solving problems (I've just been writing these as I read the code :o)

Sixth: Now that we've hit the real code, time for a breakdown.

if (first == nil)
  {
    first = newnode;
  }
  else
  { /* everything in the else block */ }

If first was somehow nil/NULL, you skip the sorting. Even though first hasn't had a chance to change since you assigned it a value, so this won't happen. But setting it to the last one probably isn't the best thing to do. Just pointing out the logical flaw.

Seventh, looking at your //endwhile and //endif , you seem to have forgotten that C++ uses curly braces to indicate blocks. Put them in whenever you have a for/while/if/else till you've got a bit more experience under your belt, just to get in the habit.

Eighth, this code is hard to understand. Put some comments.

Ninth, looking at the logic in the else block:

if ((*newnode).num <=(*first).num)
    {
      (*newnode).next = first;
      first = newnode;
    }
    else
...

So, if the last node (newnode) is less than the first, make it be the first. Makes sense. But now your list is a big circle. Ignoring the line first = newnode for a sec, we get this scenario: newnode points to first, which points to the second, which points to the third, which points... to the twelfth, which points to newnode, which points to first... ick.

Tenth is the problem with braces. I have no clue how your code is supposed to be. Just having my editor indent things automagically, I get this output:

if (first == nil)
  { 
    first = newnode;
  } 
  else 
  { 
    if ((*newnode).num <=(*first).num)
    {
      (*newnode).next = first;
      first = newnode;
    }
    else
      q=first;
    p=(*q).next;
    if (p==nil)
      (*first).next=newnode;
    else
      while ((*p).num < (*newnode).num && ((*p).next!=nil))
        q=p;
    p=(*p).next;
    //endwhile
    //endif
    if ((*p).num >= (*newnode).num)
    {
      (*q).next=newnode;
      (*newnode).next = p;
    }
    else
      (*p).next=newnode;
    //endif
  }//endif
  //endif


  q=first;
  cout<< "The list contains \n";
  while (q != nil)
  {
    cout<<" The numbers are: " << (*q).num << "\n";
    q = (*q).next;
  } //endwhile

I think you meant for it to be like this:

else 
  { 
    if ((*newnode).num <=(*first).num)
    {
      (*newnode).next = first;
      first = newnode;
    }
    else
    {
      q=first;
      p=(*q).next;
      if (p==nil)
      {
        (*first).next=newnode;
      }
      else
      {
        while ((*p).num < (*newnode).num && ((*p).next!=nil))
        {
          q=p;
          p=(*p).next;
        } //endwhile
      } //endif
      if ((*p).num >= (*newnode).num)
      {
        (*q).next=newnode;
        (*newnode).next = p;
      }
      else
      {
        (*p).next=newnode;
      } //endif
    } //endif
  } //endif


  q=first;
  cout<< "The list contains \n";
  while (q != nil)
  {
    cout<<" The numbers are: " << (*q).num << "\n";
    q = (*q).next;
  } //endwhile

I'll assume that my braces are correct from here on, based on your comments.

Eleventh on the list:

q=first;
      p=(*q).next;
      if (p==nil)
      {
        (*first).next=newnode;
      }

Same as part 6.

Twelfth is the only part which has a chance to do work (comments added):

while ((*p).num < (*newnode).num && ((*p).next!=nil))
     // while (p is less than the last node && p has a next)
        {
          q=p; // q is now p
          p=(*p).next; // p is the next one
        }

Since this is the only loop, you can't really sort a list elsewhere. And you don't do any reordering here, so it wont get sorted here either. Not much else to say, but this really doesn't do anything.

13th:

if ((*p).num >= (*newnode).num)
      {
        (*q).next=newnode;
        (*newnode).next = p;
      }
      else
      {
        (*p).next=newnode;
      } //endif

at this point there's two possibilities for the state of p: 1) p is nil (and it went through the code in 12) which can't happen without bad input (which would cause a crash earlier anyways), or 2) it went through the loop and either p->num >= newnode->num or p == newnode. The else in this quoted segment will never run. The if part of it will take q->next and change it from p to newnode. Then newnode will point to p. That's the extend of swappint the order of nodes in your code.

Then, finally, your output loop will die from things already mentioned (e.g. the linked list is messed up). I tried running it with ascending values (1 to 13) and it looped on 13. I tried descending order (13 to 1) and it printed a loop (as mentioned earlier).

[notfornothing21]

Wow -- thanks! Lots of information to take in so I am trying hard here... I appreciate the help.
Okay so I go tthe Int Main and the return no problem. I updated my brackets. I have to use "nil" for class purposes. I understand the logic behind that the the first should not equal Nil... maybe opposite and NOT equal nil?
The loop -- yes I understand the logic that it is going to go round and round, but not really sure how to make it not do that.

Here is my NEW CODE: I am a little closer... the loop now ends but the output is the last number. So I am thinking that maybe I should be outputing elsewhere in the program so that it outputs as it sorts?

#include <iostream>
#include <fstream>
using namespace std;
//Functions
void GetData (int& number);
const int nil=0;
class node_type // Declaration of Class
{
public:
int num; // Numbers that we are entering
node_type *next;
};
int main ()
{
node_type *first, *p, *q, *newnode; // Introducing the Nodes
int i;
int number;
float sum = 0;
first = new node_type;
p=first;
GetData(number);
(*first).num = number;
(*first).next = nil;
for (i=1; i<=12; i++)
{
GetData (number); // Input Numbers
newnode = new node_type;
(*newnode).num=number;
(*newnode).next=nil;
(*p).next = newnode; // Links previous Node to new Node //
p=newnode;
}
if (first != nil)
{
first = newnode;
}
else
{
if ((*newnode).num <=(*first).num)
{
(*newnode).next = first;
first = newnode;
p=(*p).next;
}
else
{
q=first;
p=(*q).next;
if (p==nil)
{
(*first).next=newnode;
}
else
{
while ((*p).num < (*newnode).num && ((*p).next!=nil))
{
q=p;
p=(*p).next;
}//endwhile
}//endif

if ((*p).num >= (*newnode).num)
{
(*q).next=newnode;
(*newnode).next = p;
}
else
{
(*p).next=newnode;
}//endif
}//endif
}//endif
q=first;
cout<< "The list contains \n";
while (q != nil)
{
cout<<" The numbers are: " << (*q).num << "\n";
q = (*q).next;
}//endwhile
return 0;
}

void GetData(int& number)
{
cout<< "Enter an integer \n";
cin>>number;
cout<< number << "\n";
}

[Infarction]

if (first != nil)
{
first = newnode; 
}

I'm just not seeing a reason for even having this part. You know first != nil because you set it above. And if you set first = newnode, you'll lose the first n-1 parts of your list. This is why you're only printing one thing at the end, btw.

Your sorting logic really has very little to do with sorting. You need to be reordering the list in the while loop without creating a circular list. You'll have to rewrite the loop to do that. After rewriting, you should probably run through a few example lists by hand to make sure it's doing what you want (i.e. not creating a circle and not losing nodes).

Two other small notes:
- post your code inside code tags.
- add spaces to usingnamespace and constint.

;)