Help with sorting linked list by last name

[mysiarobin1987]

I'm trying to sort my linked list by last name. The program compiles and runs successfully, however, the linked list isn't sorted by last name. The function I need help with is sortLastName(). This is some code our professor and I came up with, so I think I'm on the right track.

PS: Here's the contents of the students.dat file incase you need it. Thanks for the help in advance!!
Smith Jefferey 891789 [e-mail] 3.75
Lee Jackson 3678902 [e-mail] 3.66
Gonzales Mariana, 168790 [e-mail] 4.0
Jones Mike 8973125 [e-mail] 3.1
Williams Anita 2985465 [e-mail] 3.64
Ronsinson Taylor 3278976 [e-mail] 3.55
Clark Allen 1094567 [e-mail] 3.48
Turner Tavon 318796 [e-mail] 3.2
Jenkins Nelson 289563 [e-mail] 3.0

using namespace std;

#include <iostream>
#include <fstream>
#include<string>
struct student;
typedef student * studentptr, * head, * tail;

struct student
{
string firstName;
string lastName;
unsigned int studentID;
string email;
float gpa;
studentptr next;
};

class studentsProc // Definition of class named studentsProc
{
public:
studentsProc();
void loadList(); // Function that loads data from a data file into a student list
void printList();
void retrieveStudent();
void insertStudent();
void deleteStudent();
void printStudent();
void sortLastName();
void sortGPA();
void insertOrder(studentptr s);
void printSortedList(studentptr sortedStudents);

private:
student * students; // Pointer to the list of students
void print() const; //Print the contents of the list
};

studentsProc::studentsProc()
{
students = NULL;
}

void studentsProc::loadList()
{
ifstream infile;
infile.open("students.dat");
students = NULL; //head pointer points no where
student temp;
studentptr temp_ptr;
while (!infile.eof())
{
temp_ptr = new student;
infile >> temp_ptr->lastName >> temp_ptr->firstName >> temp_ptr->studentID >> temp_ptr->email >> temp_ptr->gpa;//place data in the node
temp_ptr->next = students;
students = temp_ptr;
}
infile.close();

}

void studentsProc::retrieveStudent()
{
string lastName;
cout << endl;
print();
cout << endl;
cout << "Please Enter the Last Name of the Student's Information you Wish to Retrieve: " << endl;
cin >> lastName;
cout << endl << "Here is the Information You Requested: " << endl;
for (studentptr s = students; s != NULL; s = s->next)
if(lastName==s->lastName)
{
cout << "Student Name: " << s->lastName << ", " << s->firstName << endl << endl;
}
}

void studentsProc::insertStudent()
{
studentptr temp = new student;

cout << endl;
cout << "Please Enter the Following Information About The New Student: " << endl;
cout << "Last Name: "; cin >> temp->lastName;
cout << "First Name: "; cin >> temp->firstName;
cout << "Student ID: "; cin >> temp->studentID;
cout << "E-Mail: "; cin >> temp->email;
cout << "GPA: "; cin >> temp->gpa;
cout << endl;
temp->next = students;
students = temp;
cout << "The Student List Including the New Student's Information: " << endl;
printList();
}

void studentsProc::deleteStudent()
{
cout << endl;
studentptr prev, pos;
string lastName;
bool done = false;
pos = NULL;
prev = NULL;
print();
cout << endl;
cout << "Please Enter the Student's Last Name you Wish to Delete: " << endl;
cin >> lastName;
cout << endl;
for (studentptr s = students; (s != NULL) && (done == false); s = s->next)
{
if (s->lastName == lastName)
{
done = true;
pos = s;
}
else
{
prev = s;
}
}
if(prev != NULL)
{
prev->next = pos->next;
}
else
{
students = students->next;
}
cout << "The Student List Excluding the New Student's Information: " << endl;
printList();
}

void studentsProc::printList()
{
cout << endl;
for (studentptr s = students; s != NULL; s = s->next)
cout << "First Name: " << s->firstName << " * "
<< "Last Name: " << s->lastName << " * "
<< "Student ID: " << s->studentID << " * "
<< "E-Mail: " << s->email << " * "
<< "GPA: " << s->gpa << endl;
}

void studentsProc::sortLastName()
{
studentptr sortedStudents = NULL;

for (studentptr s = students; s!= NULL; s=s->next)
{
insertOrder(s);
}
}

void studentsProc::insertOrder(studentptr node)
{
studentptr prev1, pos1;
studentptr temp1 = new student;
studentptr sortedStudents = NULL;
bool done = false;
pos1 = NULL;
prev1 = NULL;
temp1->lastName = node->lastName;
temp1->firstName = node->firstName;
temp1->studentID = node->studentID;
temp1->email = node->email;
temp1->gpa = node->gpa;
temp1->next = NULL;
for (studentptr s = sortedStudents; (s!=NULL) && (done == false); s=s->next)
{
if (s->lastName > temp1->lastName)
{
done = true;
pos1 = s;
}
else
{
prev1 = s;
}
}

if (pos1 == NULL)
{
sortedStudents=temp1;
temp1->next = NULL;
}
else if (prev1 == NULL)
{
temp1->next = sortedStudents;
sortedStudents = temp1;
}
else
{
prev1->next = temp1;
temp1->next = pos1;
}
printSortedList(sortedStudents);
}

void studentsProc::printSortedList(studentptr sortedStudents)
{
cout << endl;
for (studentptr s = sortedStudents; s != NULL; s = s->next)
cout << "First Name: " << s->firstName << " * "
<< "Last Name: " << s->lastName << " * "
<< "Student ID: " << s->studentID << " * "
<< "E-Mail: " << s->email << " * "
<< "GPA: " << s->gpa << endl;
}

void studentsProc::sortGPA()
{

}

void studentsProc::printStudent()
{
string lastName;
cout << endl;
print();
cout << endl;
cout << "Please Enter the Last Name of the Student's Information you Wish to Retrieve: " << endl;
cin >> lastName;
cout << endl << "Here is the Information You Requested: " << endl;
for (studentptr s = students; s != NULL; s = s->next)
if(lastName==s->lastName)
{
cout << "Last Name: " << s->lastName << " * "
<< "First Name: " << s->firstName << " * "
<< "Student ID: " << s->studentID << " * "
<< "E-mail: " << s->email << " * "
<< "GPA: " << s->gpa << endl;
}
cout << endl;
}

void studentsProc::print() const
{
cout << "Student List of Names: " << endl;
for (studentptr s = students; s != NULL; s = s->next)
cout << "Last Name: " << s->lastName << " * "
<< "First Name: " << s->firstName << endl;
}
int main()
{
int choice;
studentsProc student;
student.loadList();
do
{
// Menu options to carry out specific operations for student list
cout << "Please Choose an Option from this Menu" << endl << endl;
cout << "1. Retrieve and Print a Student from the Student List " << endl;
cout << "2. Insert a Student into the Student List " << endl;
cout << "3. Delete a Student from the Student List " << endl;
cout << "4. Print the Contents of a Student Record " << endl;
cout << "5. Print the Contents for a List of Students " << endl;
cout << "6. View the Students List Sorted by Last Name " << endl;
cout << "7. View the Students List Sorted by GPA " << endl;
cout << "8. Exit the Program" << endl;
cin >> choice; // Asks user to input their choice

// Switch menu that carries out the specific operations for student list based on the user's input
switch (choice)
{
case 1: student.retrieveStudent(); // Function call to retrieve and print a student's information from the student list
break;
case 2: student.insertStudent(); // Function call to insert a student's information into the student list
break;
case 3: student.deleteStudent(); // Function call to delete a student's information from the student list
break;
case 4: student.printStudent(); // Function call to print the contents of a student's record
break;
case 5: student.printList(); // Function call to print the contents for a list of students
break;
case 6: student.sortLastName(); // Function call to sort the student list by students' last names
break;
case 7: student.sortGPA(); // Function call to sort the student list by students' GPAs
break;
case 8: exit(0);
default: cout << "Please enter a value 1-7" << endl; // Default case in which user does not enter a number between 1 and 7, asks user to reenter value
}//end switch
} while (choice != 9);

return 0;
}

[keskiverto]

First, please use the code tags. See http://www.cplusplus.com/articles/jEywvCM9/

What you have:

void studentsProc::sortLastName()
{
  studentptr sortedStudents = NULL; // unused local variable

  for ( studentptr s = students; s!= NULL; s=s->next )
  {
    insertOrder( s );
  }
}

This one seems to iterate over the students. Not quite the sort that I did expect.

Is this where the magic happens?

void studentsProc::insertOrder( studentptr node )
{
  studentptr prev1, pos1;
  studentptr temp1 = new student;
  studentptr sortedStudents = NULL; // <---
  bool done = false;
  pos1 = NULL;
  prev1 = NULL;
  temp1->lastName = node->lastName;
  temp1->firstName = node->firstName;
  temp1->studentID = node->studentID;
  temp1->email = node->email;
  temp1->gpa = node->gpa;
  temp1->next = NULL;
  for ( studentptr s = sortedStudents; (s!=NULL) && // <---
      (done == false); s=s->next)
  {
    // code
  }

  // code

  printSortedList(sortedStudents); // Why does this function print anything?
}

It seems that there is at least one clear showstopper.


Overall, the logic is not clear. One would expect that foo.sort() reorders the elements of foo.
You seem to create a temporary copy (and leak memory like a cheese crate).


Sorting is (usually) based on two operations:

1. pred(lhs, rhs) that returns true, if lhs and rhs are is proper order. The pred defines the order. Both std::sort and std::list::sort accept user-defined pred.

2. swap(lhs, rhs). When the elements are not in proper order, then they have to swap places to correct the situation.
On array-like containers one has to use copy/move of the values in the elements.
That is possible with linked list too, but it is also possible to swap by updating the links, which is cheaper if the values are expensive to copy/move.


There are three cases for list insertion:
1. Prepend. Add to front.

temp.next = head;
head = temp;

2. Append. Add after last node:

tail = ... last element ...
tail.next = temp;

3. Insert after node x:

temp.next = x.next;
x.next = temp;

Your insertion sort would:

original = ... the list ...
sorted = nullptr;
WHILE original has nodes
  x = node in original
  remove x from original
  seek position of x in sorted
  insert x to sorted at position
original = sorted

[Handy Andy]

Hello mysiarobin1987,

PLEASE ALWAYS USE CODE TAGS (the <> formatting button), to the right of this box, when posting code.

It makes it easier to read your code and also easier to respond to your post.

http://www.cplusplus.com/articles/jEywvCM9/
http://www.cplusplus.com/articles/z13hAqkS/

Hint: You can edit your post, highlight your code and press the <> formatting button.
You can use the preview button at the bottom to see how it looks.

I found the second link to be the most help.

To add to what keskiverto has said. Your first problem in the the "loadList" function.

The while condition based on "eof()" does not work the way that you think it does. What it is doing is prossing one extra record because the loop still thinks that end of file has not reached yet. So you end up reading nothing into the node variables.

Since your list is backwards from the file it is hard to see what has happened except that the first node in the list has nothing to print out.

This may not be the best way to code this, but it does help show what is wrong. Now when the while condition reads past end of file the file stream will fail and so will the while condition.

void studentsProc::loadList()
{
	std::ifstream infile;
	std::string tempName;  // <--- Added.
	infile.open("students.dat");
	students = NULL; //head pointer points no where
	student temp;
	studentptr temp_ptr{ NULL };

	while (infile >> tempName)  // <--- Changed.
	{
		temp_ptr = new student;
		temp_ptr->lastName = tempName;  // <--- Added.
		infile  >> temp_ptr->firstName >> temp_ptr->studentID >> temp_ptr->email >> temp_ptr->gpa;//place data in the node  // <--- Changed.
		temp_ptr->next = students;
		students = temp_ptr;
	}

	// <--- Used for testing.
	//for (studentptr s = students; s != NULL; s = s->next)
	//	std::cout << "Last Name: " << s->lastName << ", " << s->firstName << std::endl;

	infile.close();
}

After this I would work on what keskiverto has said.

Hope that helps,

Andy