Bubble Sort on a Singly Linked List

Main:

Code:

---

#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>

#include "StudentRecordDataNode.h"
#include "Course.h"
#include "StudentSingleListedLink.h"

#define SIZE_BUF  15

using namespace std;

void sortNodes(StudentRecordDataNode * ptr);

void main()
{
        double marks[18];
        unsigned int Age;
    unsigned int ID;
    unsigned int CourseCount;
    char FirstName[10];
    char LastName[10];
        Course Courses[18];
        StudentRecordDataNode *node = 0;
        StudentSingleListedLink iList;
        StudentRecordDataNode *nd = 0;
        ifstream is;
        is.open ("OOP344_Assignment_3_2011_01.dat", ios::binary );
        do {
                //beginning of saving records from the file
                for(int i=0; i<18; i++)
                        marks[i] = 0;

                is.read(reinterpret_cast<char *>(&marks), sizeof(double)*18);

                is.read(reinterpret_cast<char *>(&Age), sizeof(Age));
                is.read(reinterpret_cast<char *>(&ID), sizeof(ID));
                is.read(reinterpret_cast<char *>(&CourseCount), sizeof(CourseCount));
                is.read(reinterpret_cast<char *>(&FirstName), sizeof(FirstName));
                is.read(reinterpret_cast<char *>(&LastName), sizeof(LastName));

                for (int i=0; i < 18; i++)
                {
                        is.read(reinterpret_cast<char *>(&Courses[i].Semester), sizeof(Courses[i].Semester));
                        is.read(reinterpret_cast<char *>(&Courses[i].Name), sizeof(Courses[i].Name));
                }
                //end of saving
       
                StudentRecordData *r;
                r = new StudentRecordData(marks,Age,ID,CourseCount,FirstName,LastName, Courses);
                node = new StudentRecordDataNode(r);
                iList.AddNode(node);
        } while (!is.eof());

        //nd=iList.getFirstNode();
        sortNodes(node);

        for(nd=iList.getFirstNode();nd;nd=iList.getNextNode(nd))
                        nd->getValue()->display();

        is.close();

        cin.get();
        return;
}

void sortNodes(StudentRecordDataNode * ptr) {
        StudentRecordData * temp=0;
        StudentRecordDataNode * curr;
        for(bool didSwap = true; didSwap; ) {
                didSwap = false;
                for(curr = ptr; curr->next != NULL; curr = curr->next) {
                        if(curr->getValue()->getAge() > curr->next->getValue()->getAge()) {
                                temp = curr->getValue();
                                *curr->getValue() = *curr->next->getValue();
                                *curr->next->getValue() = *temp;
                                didSwap = true;
                        }
                }
        }
}

---

StudentRecordDataNode.h

Code:

---

#ifndef STUDENTRECORDDATANODE_H
#define STUDENTRECORDDATANODE_H
#include "StudentRecordData.h"

class StudentRecordDataNode
{
        StudentRecordData *Value;
        friend class StudentSingleLinkedList;
public:
        StudentRecordDataNode *next;
        StudentRecordDataNode();
        StudentRecordDataNode(StudentRecordData *val)
        {
                Value = val;
                next = 0;
        }
        StudentRecordData *getValue()
        {
                return Value;
        }
};
#endif

---

StudentSingleListedLink.h

Code:

---

#ifndef StudentSingleListedLink_H
#define StudentSingleListedLink_H

#include "StudentRecordDataNode.h"

class StudentSingleListedLink
{
        StudentRecordDataNode *root;
public:
        StudentSingleListedLink();
        ~StudentSingleListedLink();
        void AddNode(StudentRecordDataNode *);
        StudentRecordDataNode *getFirstNode();
        StudentRecordDataNode *getNextNode(StudentRecordDataNode *nd);
};

#endif

---

StudentSingleListedLink.cpp

Code:

---

#include "StudentSingleListedLink.h"

StudentSingleListedLink::StudentSingleListedLink()
{
        root = 0;
}

StudentSingleListedLink::~StudentSingleListedLink()
{
        StudentRecordDataNode *curr=root;
        StudentRecordDataNode *next;
       
        while(curr)
        {
                next = curr->next;
                delete curr;
                curr = next;
        }
}

void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
{
        if(!root)
        {
                root = nd;
                return;
        }
        nd->next = root;
        root = nd;
}

StudentRecordDataNode *StudentSingleListedLink::getFirstNode()
{
        return root;
}

StudentRecordDataNode *StudentSingleListedLink::getNextNode(StudentRecordDataNode *nd)
{
        return nd->next;
}

---

StudentRecordData.h

Code:

---

#ifndef STUDENTRECORDDATE_H
#define STUDENTRECORDDATE_H

#include "Course.h"

#define MAX_COURSES      18
#define LEN_FN          10
#define LEN_LN          10

class StudentRecordData
{
  double Marks[MAX_COURSES];
  unsigned int Age;
  unsigned int ID;
  unsigned int CourseCount;
  char FirstName[LEN_FN];
  char LastName[LEN_FN];
  Course  Courses[MAX_COURSES];
public:
        StudentRecordData();
        StudentRecordData(double m[18], unsigned int age, unsigned int id, unsigned int cc, char fn[10], char ln[10], Course c[18]);
        unsigned int getID() {return ID;}
        unsigned int getAge() {return Age;}
        void display();
};

#endif

---

StudentRecordData.cpp

Code:

---

#include <iostream>
#include <fstream>
#include <string>

#include "StudentRecordData.h"
#include "Course.h"

using namespace std;

StudentRecordData::StudentRecordData(double m[18], unsigned int age, unsigned int id, unsigned int cc, char fn[10], char ln[10], Course c[18])
{
        for(int i=0;i<18;i++)
                Marks[i] = m[i];

        Age = age;
        ID = id;
        CourseCount = cc;
        strcpy(FirstName, fn);
        strcpy(LastName, ln);
        for(int i=0;i<18;i++)
        {
                strcpy(Courses[i].Name,c[i].Name);
                Courses[i].Semester = c[i].Semester;
        }
       
}

void StudentRecordData::display()
{
        for(int i=0; i<18; i++)
        {
                if (Marks[i] > -1)
                        cout << Marks[i] << " ";
        }
        cout << endl << "Age: " << Age << " ID: " << ID << " Course Count: " << CourseCount << " First Name: " << FirstName
                << " Last Name: " << LastName << endl;
        for(int i=0;i<CourseCount;i++)
        {
                cout << Courses[i].Name << " ";
        }
        cout << endl<<endl;
}

---

the file needed to be read:

Code:

---

    @Q@    €J@      O@    €L@    ÀX@    ÀS@    €Q@      O@    ÀQ@      N@      X@    €J@    ÀV@    @X@      M@      R@ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ  Ø�   Mitcha ÌÌÌAdru ÌÌÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ      J@    €W@      R@    €L@    @U@    ÀX@    €V@      Q@      O@    €K@    @S@    €T@    @T@    ÀU@      W@    @U@    ÀR@    €R@  º6   James ÌÌÌÌHarkley ÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444      ÀR@      P@    €W@    €Q@      L@    ÀP@      O@    €V@    @X@    ÀX@    €V@    €T@    ÀV@    @W@ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ"  âê          Jake ÌÌÌÌÌChoy ÌÌÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ    €T@    €Q@    @X@    @P@    @P@    €T@    @U@    @U@    €L@      U@    €R@      R@    €M@    ÀQ@    €S@      I@      R@      J@  }T   David ÌÌÌÌHansen ÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444      T@    €Q@      S@      V@      L@    @T@    @V@      W@    ÀR@    €S@    €P@    @S@      L@    €O@    €M@      W@      T@      O@  |˜   Matt ÌÌÌÌÌFaria ÌÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444      L@      V@    @T@    €M@    ÀS@    €V@      X@      P@      N@      S@    ÀX@      X@      N@    ÀX@    ÀT@      I@    €K@ÌÌÌÌÌÌÌÌ  îß   Maria ÌÌÌÌDallan ÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 ÌÌÌÌÌÌÌÌ    €N@    @X@      T@    €P@    @T@    ÀV@    €W@      T@    €Q@      R@      M@    €X@    @X@    €T@    €T@    @U@    €W@    @U@  é          Brandon ÌÌLay ÌÌÌÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444      €V@    €L@      J@    ÀX@    @P@    €U@    ÀV@    @Q@      J@      J@      P@    @P@    ÀR@    ÀS@    €I@ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ  Îù   Bruno ÌÌÌÌCondello Ì
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ    €J@      L@      M@    €U@    ÀX@    @T@    ÀS@    €V@    €S@    ÀT@      S@      V@    ÀR@    @P@      M@    ÀP@      S@    ÀQ@  ÇÑ
   Lui ÌÌÌÌÌÌDonghui ÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 JAC444      Q@    €I@    @Q@    @U@    @U@    ÀW@    @U@    ÀQ@    @R@    @R@    ÀS@    @S@      X@    ÀQ@      T@    €N@    €O@ÌÌÌÌÌÌÌÌ#  Ÿ8   Alex ÌÌÌÌÌChow ÌÌÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 ÌÌÌÌÌÌÌÌ    ÀV@    ÀR@      Q@    €K@      R@      V@      R@    @R@    @S@      V@    €T@    ÀR@    @X@ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ  i
  Phuong ÌÌÌLy ÌÌÌÌÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ    €U@    @W@    ÀS@    €M@    €Q@    @V@    ÀU@    ÀU@    ÀP@    €X@      Q@    €Q@    €W@    ÀV@    €M@    €M@    @W@ÌÌÌÌÌÌÌÌ  `â   Arthur ÌÌÌBradlow ÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 EAC397 ÌÌÌÌÌÌÌÌ    @Q@      W@      S@    ÀU@    ÀX@      O@    €P@    €W@      M@    ÀP@    €N@    @V@      J@      T@    €O@    €R@ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ  gl   Roya ÌÌÌÌÌSakedad ÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ    @S@    €N@    @V@      J@    €N@    €M@    ÀX@      M@      K@    @S@    €S@      N@    ÀW@    @W@    @U@    @X@ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ  ʽ   Charles ÌÌBrady ÌÌÌÌ
APC100
EAC150
ICA002
IOS110
IPC144 ULI101 DBS201 IBC233 INT222 OOP244 DBS301 INT322 SYS366 BAC344 OOP344 DCN455 ÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌÌ

---

The problem lies in the sort. It is duplicating a few of the nodes multiple times. While it is in sorted order. A good bunch of the nodes are gone because a few where duplicated. Any suggestions?

Quote:

---

Originally Posted by bigmac(rexdale)

Any suggestions?

---

Fix it! :D

Now seriously, ask yourself: Why some nodes get duplicated while others are gone?
Take a deep breath, dive into your code, and tell us what you found, ok? :)

Don't try using bubble sort on a linked list. Though it is very easy for an array, it is far harder to get right with a linked-list. There are way more things that make it very very hard to get right, that you haven't even thought of.

Implement Insertion Sort instead. It is the simplest linked-list sorting algorithm.

I checked up on insertion sort and got this so far:

Code:

---

void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
{
        if(!root)
        {
                root = nd;
                return;
        }
        else if (nd->getValue()->getAge() < root->getValue()->getAge())
        {
                nd->next = root;
                root = nd;
        }
}

---

is this correct? (well so far atleast?)

Code:

---

void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
{
        if(root==NULL)
        {
                root = nd;
                return;
        }
        else if (root->getValue()->getAge() <= nd->getValue()->getAge())
        {
                nd->next = root;
                root = nd;
        }
        else if(root->getValue()->getAge() == NULL)
        {
                root->next = nd;
        }
        else
        {
                StudentRecordDataNode * current = root;
                StudentRecordDataNode * going = current->next;
                while(going!=NULL)
                {
                        if(nd->getValue()->getAge() >= going->getValue()->getAge())
                        {
                                current->next = nd;
                                nd->next = going;
                        }
                        else
                        {
                                if(going->next == NULL)
                                {
                                        going->next = nd;
                                        going = going->next;
                                        current = going;
                                        going = current->next;
                                }
                                else
                                {
                                        current = going;
                                        going = current->next;
                                }
                        }
                }
        }
}

---

This is what i finished writing. Doesnt work though

#1. If you are going to use C-style strings (null terminated char arrays) then you should be including the <cstring> header and not the <string> header. The former holds the declarations of strcpy and the like, the later helps with using C++ std::string containers.


#2. It should always be int main, not void main.


#3

Code:

---

do {
    ...
} while (!is.eof());

---

Controlling loops with an end-of-file test usually is not the right way to do things 99.99999% of the time (link example is C but the lesson still applies to C++). Usually you want to directly test a read operation instead of EOF otherwise you sometimes may end up with a duplicate record being processed.


#4 These (in red) don't need the ampersands:

Code:

---

//beginning of saving records from the file
for(int i=0; i<18; i++)
    marks[i] = 0;

is.read(reinterpret_cast<char *>(&marks), sizeof(double)*18);

is.read(reinterpret_cast<char *>(&Age), sizeof(Age));
is.read(reinterpret_cast<char *>(&ID), sizeof(ID));
is.read(reinterpret_cast<char *>(&CourseCount), sizeof(CourseCount));
is.read(reinterpret_cast<char *>(&FirstName), sizeof(FirstName));
is.read(reinterpret_cast<char *>(&LastName), sizeof(LastName));

for (int i=0; i < 18; i++)
{
    is.read(reinterpret_cast<char *>(&Courses[i].Semester), sizeof(Courses[i].Semester));
    is.read(reinterpret_cast<char *>(&Courses[i].Name), sizeof(Courses[i].Name));
}
//end of saving

---

You really don't need the casts on those lines either since these name fields are already effectively char pointers when used by themselves in the above context.


#5 Would it be possible to attach the data file as well instead of a cut and past job?


Haven't looked at anything else, just a brief glance.

Fixed the following problems you stated and uploaded the .dat to sendspace:

Code:

---

http://www.sendspace.com/file/khr1rf

---

anyone get a chance to check this out?

Oh, it appears that rather than implement insertion sort, you're opting to insert each item into the correct place in the list immediately. I guess that's fine if you don't need to iterate over it in the unsorted order first, and this too is easier than doing bubble sort on a linked-list.

The first two cases are okay, but I don't know why you have this case:

Code:

---

        else if(root->getValue()->getAge() == NULL)

---

It doesn't make sense for getAge to return NULL.

It should be a little shorter than what you have. It can certainly be done with only two if-statements. Having said that, can you follow through your logic with the debugger and try out some of the cases? Try inserting one item by itself, then another item before that, then another item after that etc and follow it through with a pen and paper if necessary.

Code:

---

void StudentSingleListedLink::AddNode(StudentRecordDataNode *nd)
{
        StudentRecordDataNode * current = root;
        StudentRecordDataNode * temp = nd;
        if(!root)
        {
                root = nd;
        }
        else if(root->getValue()->getAge() > temp->getValue()->getAge())
        {
                temp->next = root;
                root = temp;
        }
        else
        {
                current = root;
                while(current->next && current->getValue()->getAge() < nd->getValue()->getAge())
                {
                        current = current->next;
                }
                nd->next = current->next;
                current->next = nd;
        }
}

---

I shortened it and it seems to work until age 22. Basically the first half is sorted but the remaining is unsorted. Ill try debugging it now but let me know if you find the problem.

any one can help me out?