C++

Forum

 
Help With Linked List

reaper0grim (4)
So for my hw, I have to create a linked list of movie objects.

This is the code for a Node class that my prof supplied for the hw.

Node.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
template <typename T>
class Node {
    T data;
    Node<T> *nextLink, *previousLink;
public:
    Node (){}
    Node (T theData, Node<T>* previous, Node<T>* next)
            : data(theData), nextLink(next), previousLink(previous) {}
    Node<T>* getNextLink() const {return nextLink;}
    Node<T>* getPreviousLink() const {return previousLink;}
    T getData() const {return data;}
    void setData(T theData) {data = theData;}
    void setNextLink(Node<T>* pointer) {nextLink = pointer;}
    void setPreviousLink(Node<T>* pointer) {previousLink = pointer;}
	void headInsert(Node<T>*& head, T theData);
};


Node.cpp
1
2
3
4
5
6
7
8
9
 
#include "Node.h"
// Note that separate compilation of templates is supported in VC++
template <typename T>
void Node<T>::headInsert(Node<T>*& head, T theData) {
	Node<T>* newHead = new Node<T>(theData, NULL, head);
	head->setPreviousLink(newHead);
	head = newHead;
}


This is the code I currently have for a class called Movies which is a linked list of Movie objects (it was originally an array but we are modding it to be a LL)

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
 
// Movies.cpp
#include "Movie.h" // include Movie class definition
#include "Movies.h" // include Movies class definition
#include "Node.h"
#include <fstream>
using namespace std;

Movies::Movies(string fn){loadMovies(fn);}

int Movies::getMovieCount() const {return movieCnt;}

int Movies::getMovieHash(string mc) const {
	int hashVal = 0;
	for( int i = 0; i < mc.length(); i++ )
		hashVal = HASH_KEY * hashVal + mc[i];
	hashVal = abs(hashVal) % TABLE_SIZE;
	return hashVal;
}

const Movie * Movies::getMovie(string mc) const {
	if(mc.length()==0)
		return NULL; // not found
	else
		return &(movies[getMovieHash(mc)]);
}

Movies::~Movies() {delete[] movies; movies = NULL;}

void Movies::loadMovies(string fn) {
	ifstream iS(fn);  // technically should be c_str
	string s;
	getline(iS, s); // skip heading
	getline(iS, s);
	movieCnt = 0;
	movies = new Movie[TABLE_SIZE];
	Movie* n = new Movie(s);
	Node<Movie>* root = new Node<Movie>(n,NULL,NULL);
	//while(!iS.eof()) {
		//Movie* m = new Movie(s);
		//movies[getMovieHash(m->getTitle())] = *m;
		//movieCnt++;
		//getline(iS, s);
	//}
	iS.close();
}

My question is on line 37 of the code above, I'm getting an error that says: "No instance of constructor "Node<T>::Node[with T=Movie]" matches the argument list.
I don't really understand the error and how I could fix it.

Also, how would I go about creating the LL so that it is in ascending sequence by title ignoring cases. Here is the code for the Movie class:
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
 
// Movie.cpp
#include "Movie.h" // include Movie class definition
#include <sstream>
using namespace std;

Movie::Movie() {
	title = "";
	usBoxOffice = nonUSBoxOffice = worldBoxOffice = usRank = nonUSRank =
		worldRank = 0;
}

Movie::Movie(string temp) {
	istringstream iS(temp);
	getline(iS, title, '\t');
	iS >> worldBoxOffice >> usBoxOffice >> nonUSBoxOffice
		>> worldRank >> usRank >> nonUSRank;
}

string Movie::getTitle() const {return title;}
long long Movie::getUSBoxOffice() const {return usBoxOffice;}
long long Movie::getNonUSBoxOffice() const {return nonUSBoxOffice;}
long long Movie::getWorldBoxOffice() const {return worldBoxOffice;}
int Movie::getUSRank() const {return usRank;}
int Movie::getNonUSRank() const {return nonUSRank;}
int Movie::getWorldRank() const {return worldRank;}

ostream& operator <<(ostream& oS, const Movie& m) {
	oS << "\n\n====================== Movie Information\n"
	<< "\n             Movie Title:\t" << m.title
	<< "\n    US Rank & Box Office:\t" << m.usRank << "\t$" << m.usBoxOffice
	<< "\nNon-US Rank & Box Office:\t" << m.nonUSRank << "\t$" << m.nonUSBoxOffice
	<< "\n World Rank & Box Office:\t" << m.worldRank << "\t$" << m.worldBoxOffice
	<< "\n";
	return oS;
}

Movie::Movie(const Movie &mP) { // private copy constructor blocks invocation
	this->title = mP.title;
	this->usRank = mP.usRank;
	this->nonUSRank = mP.nonUSRank;
	this->worldRank = mP.worldRank;
	this->usBoxOffice = mP.usBoxOffice;
	this->nonUSBoxOffice = mP.nonUSBoxOffice;
	this->worldBoxOffice = mP.worldBoxOffice;
}


Thanks! I greatly appreciate any help!
hamsterman (4538)
The error is because you're passing a Movie* instead of Movie, as the first argument.

To get the sorted result, you could either sort the full list (1), or insert nodes in the right positions as you populate it (2). In both cases you'll have to write operator <. To ignore case when comparing two strings, convert both of them to lover(upper) case.

(1) You'll have to find yourself a sorting algorithm. Note that sorting a LL is not the same as sorting an array. Quick Sort is simple for lists. Remove the first element "pivot", then separate the rest of the list into two lists : "left" with elements that compare less than "pivot and "right with elements that don't. Then Sort "left" and "right" using recursion. Lastly concatenate left+pivot+right.

(2) This is similar to (1), but a bit simpler. You're given a sorted (possibly empty) "list" and an "element". To insert "element" at the right spot, again, divide "list" into "left" and "right" as in (1). This time it is easier, since "list" is already sorted, so "left" will be its first half and "right" will be the second half. You only need to find the breaking point. Finally concatenate left+element+right. No recursion this time.
Last edited on
reaper0grim (4)
Okay, I get that.

So I tried Movie n = new Movie(s); and it said cannot convert Movie* to Movie, how would I go about just creating a Movie object?
reaper0grim (4)
Got it, this seemed to work.

Node<Movie*>* root = new Node<Movie*>(n,NULL,NULL);
hamsterman (4538)
That's one way.

A simpler one is
1
2
 
Movie n(s);
Node<Movie>* root = new Node<Movie>(n, 0, 0);
Simpler because it removes an unnecessary heap allocation (new).

You could also do
1
2
3
 
Movie* n = new Movie(s);
Node<Movie>* root = new Node<Movie>(*n, 0, 0);
delete n;
Although it's silly in this case.
reaper0grim (4)
I tried doing something similar to that and it kept on giving me an error saying:
Error: Movie::Movie(const Movie &) is inaccessible

This is what I have as of now for the Movies.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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
// Movies.cpp
#include "Movie.h" // include Movie class definition
#include "Movies.h" // include Movies class definition
#include "Node.h"
#include <fstream>
using namespace std;

Movies::Movies(string fn){loadMovies(fn);}

int Movies::getMovieCount() const {return movieCnt;}

int Movies::getMovieHash(string mc) const {
	int hashVal = 0;
	for( int i = 0; i < mc.length(); i++ )
		hashVal = HASH_KEY * hashVal + mc[i];
	hashVal = abs(hashVal) % TABLE_SIZE;
	return hashVal;
}

const Movie * Movies::getMovie(string mc) const {
	Node<Movie*>* here = new Node<Movie*>();
	if(mc.length()==0)
		return NULL; // not found
	else{
		mc = myToLower(mc);
		while (here->getNextLink() != NULL){	  
			if (myToLower(here->getData()->getTitle()) == mc)	  
				return here->getData();
			else	  
				return NULL;
                here = here->getNextLink();
		}
	}
}

Movies::~Movies() {delete[] movies; movies = NULL;}

void Movies::loadMovies(string fn) {
	ifstream iS(fn);  // technically should be c_str
	string s;
	getline(iS, s); // skip heading
	getline(iS, s);
	movieCnt = 0;
	movies = new Movie[TABLE_SIZE];
	Movie* n = new Movie(s);
	Node<Movie*>* root = new Node<Movie*>(n,NULL,NULL);
	while(!iS.eof()) {
		Movie* m = new Movie(s);
		Node<Movie*>* node = new Node<Movie*>(m,root,NULL);
		node->getPreviousLink()->setNextLink(node);
		movieCnt++;
		getline(iS, s);
	}
	iS.close();
}

string Movies::myToLower(string s) const {
	int n = s.length();
	string t(s);
	for(int i=0;i<n;i++)
		t[i] = tolower(s[i]);
	return t;
}

void Movies::Sort(){
	Node<Movie*>* firsts = new Node<Movie*>();
	Node<Movie*>* seconds = new Node<Movie*>();
	Node<Movie*>* temp = new Node<Movie*>();
}


I finished the loadMovies method and I'm currently modded the getMovie method to traverse through the linked list and grab the movie they serach for for as well as working on the Sort method.

I guess my new question is regarding the getMovie method. So I created a dummy node called here, how do I get that to point to the head node?
Last edited on
hamsterman (4538)
Error: Movie::Movie(const Movie &) is inaccessible
I forgot your copy constructor was private. Why did you do that?

how do I get that to point to the head node?
Can't say without seeing declaration of Movies class. From implementation, I see that there's something weird with it. It should be
1
2
3
4
5
 
class Movies{
   ...
   Node<Movie*>* head, *tail;//only head would be enough,
   //but then there would be little point in having a doubly linked list
};
Last edited on
Topic archived. No new replies allowed.