Insertion sort on singly linked list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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 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;
}



StudentRecordDataNode.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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)
{
	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;
	}
}

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

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


StudentRecordData.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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;
}


When the list is displayed the first half is sorted but the remaining is unsorted. Function addnode is where all the sorting is taken placed

http://www.sendspace.com/file/khr1rf << .dat if you need it
Last edited on
Topic archived. No new replies allowed.