4 Replies - 353 Views - Last Post: 06 March 2013 - 05:33 AM Rate Topic: -----

#1 HKCHaN92  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 85
  • Joined: 23-July 11

Linked List: implementing GetItem() with only one part of a node

Posted 03 March 2013 - 06:18 PM

I'm writing a program that places the key, author, and article title of a jornal articles from a file into a linked list. The program first reads all the article information for each article into a linked list then asks the user to choose an option from a menu. The menu choices are: Find an article, List all articles, Add a new article, Remove an existing article, or Exit the program. I have the list all articles option working and the add a new article working except for the add a new article option the program should search through the list to see if the key entered already exist in the list or not and then if it doesn't already exist the program prompts the user for the title and the author and then adds the article to the list. Also, for Find an article we are suppose to use the GetItem function to get an item from the list but the only thing entered by the user is the key, and like with the add a new article I don't know how to do this just using the key. And I'm having a similar issue with the remove an article from the list. Here is the code for the program: (Sorry about the scattered comments I started out commenting as I went but then I just got so focused on finsihing and fixing errors that I forgot to comment the rest).

LinkedList.h
#include <iostream>
#include <cstdlib>

using namespace std;


template<class T>
struct NodeType;

template<class T>
class LinkedList
{
	public:
		LinkedList();                       // Constructor 
		~LinkedList();                      // Destructor
		int GetLength() const;              // Gets length of list
		void PutItem(T item);               // Inserts item into list
		void DeleteItem(T item);            // Deletes item from list
		T GetItem(T& item, bool& found);    // Get item in list
		void display(ostream& disp);

	private:
		int length;
		NodeType<T>* listData;
		NodeType<T>* currentPos;
};

template<class T>
struct NodeType
{
	T info;
	NodeType<T>* next;
};
#include "LinkedList.cpp"



LinkedList.cpp
#include <iostream>
#include <cstdlib>

using namespace std;


template<class T>
LinkedList<T>::LinkedList()
// Pre: 
// Post:
// Function: 
{
	length = 0;
	listData = NULL;
}

template<class T>
int LinkedList<T>::GetLength() const
// Pre:
// Post:
// Function:
{
	return length;
}

template<class T>
void LinkedList<T>::PutItem(T item)
// Pre:
// Post:
// Function:
{
	NodeType<T>* newNode;              // Pointer to node being inserted
	NodeType<T>* predLoc;              // Pointer to previous node location
	NodeType<T>* location;             // Location of a node
	NodeType<T>* tempLoc;
	bool found = false;
	
	location = listData;                 // Set location to listData which points to top node in list
	predLoc = NULL;                      // Set predLoc to NULL since starting at top of list
	
	tempLoc = new NodeType<T>;
	tempLoc->info = item;
	
	
	while (location != NULL && !found)
	{
		if((tempLoc->info) > (location->info))
		{
			found = true;
		}
		else
		{
			predLoc = location;
			location = location->next;
		}
	}
	delete tempLoc;
	
	newNode = new NodeType<T>;
	newNode->info = item;
	
	if(predLoc == NULL)
	{
		newNode->next = listData;                     // Moves first node in list to next node in list
		listData = newNode;                           // Inserts new node as first node in list
	}
	else
	{
		newNode->next = location;                     // Sets current location to next node in list
		predLoc->next = newNode;                      // Sets newNode to previous node in list
	}
	length++;                                         // Increments length of list
}

template<class T>
void LinkedList<T>::DeleteItem(T item)
// Pre:
// Post:
// Function:
{
	NodeType<T>* itemNode;                              // Pointer to node being deleted
	NodeType<T>* predLoc;                               // Pointer to previous node location
	NodeType<T>* location;                              // Location of a node
	NodeType<T>* tempLocation;                          // Create a temporary location pointer
    bool found = false;
	
	location = listData;                             // Set location to the first node in list
	
	tempLocation = new NodeType<T>;
	tempLocation->info = item;
	
	if ((listData->info) == (tempLocation->info))
	{
		tempLocation = location;
		listData = listData->next;
	}
	else
	{
		while(((location->next)->info) != (tempLocation->info))
		{
			location = location->next;
		}
		tempLocation = location->next;
		location->next = (location->next)->next;
	}
	
	delete tempLocation;
	length--;
	
	
}
template<class T>
T LinkedList<T>::GetItem(T& item, bool& found)
// Pre:
// Post:
// Function:
{
	NodeType<T>* location;
	
	location = listData;
	found = false;
	
	while (location != NULL && !found)
	{
		if ((location->info) == item)
		{
			found = true;
			return item;
		}
		else
		{
			location = location->next;
			found = false;
		}
	}
	if (found == false && location == NULL)
	{
			return item;
	}

}

template<class T>
void LinkedList<T>::display(ostream& disp)
{
	NodeType<T>* location = listData;
	
	while (location != NULL)
	{
		disp << location->info << endl;
		location = location->next;
	}
}

template<class T>
LinkedList<T>::~LinkedList()
// Pre:
// Post:
// Function:
{
	NodeType<T>* tempPtr;
	
	while(listData != NULL)
	{
		tempPtr = listData;
		listData = listData->next;
		delete tempPtr;
	}
}



Article.h
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>

using namespace std;

class Article
{
	public:
		// Overload functions for operators > and ==
		friend bool operator> (const Article &a1, const Article &a2);
		friend bool operator== (const Article &a1, const Article &a2);
		friend ostream& operator<< (ostream &out, const Article &a);
		
		Article();                                        // Default constructor
		Article(string k, string a, string t);            // Constructor with arguments for key, author, and title
		string GetKey() const;                            // Returns key
		string GetAuthor() const;			  // Returns author
		string GetTitle() const;			  // Returns title
		void SetKey(string k);                            // Set key to k
		void SetAuthor(string a);                         // Set author to a
		void SetTitle(string t);                          // Set title to t
	
	private:
		string key;                      // Stores article's key
		string author;                   // Stores article's author
		string title;                    // Stores article's title
		
};



Article.cpp
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstring>

using namespace std;

#include "Article.h"


bool operator> (const Article &a1, const Article &a2)
// Pre:
// Post:
// Function:
{
	string key1 = a1.GetKey();
	string key2 = a2.GetKey();
	
	if (key1 > key2)
		return false;
	else if (key2 > key1)
		return true;
}

bool operator== (const Article &a1, const Article &a2)
// Pre:
// Post:
// Function:
{
	string key1 = a1.GetKey();
	string key2 = a2.GetKey();
	
	if (key1 == key2)
		return true;
	else 
		return false;
}

Article::Article()
// Pre:
// Post: 
// Function:
{
	key = "\0";
	author = "\0";
	title = "\0";
}

Article::Article(string k, string a, string t)
// Pre:
// Post:
// Function:
{
	key = k;
	author = a;
	title = t;
}
void Article::SetKey(string k)
{
	key = k;
}
void Article::SetAuthor(string a)
{
	author = a;
}
void Article::SetTitle(string t)
{
	title = t;
}
string Article::GetKey() const
// Pre:
// Post:
// Function:
{
	return key;
}

string Article::GetAuthor() const
// Pre:
// Post:
// Function:
{
	return author;
}

string Article::GetTitle() const
// Pre:
// Post:
// Function:
{
	return title;
}

ostream& operator<< (ostream &out, const Article &a)
{
	return out << "---------------------------------------------------------------------------" << endl
			<< "Key: " << a.GetKey() << endl 
			<< "Author: " << a.GetAuthor() << endl 
			<< "Title: " << a.GetTitle() << endl
			<< "---------------------------------------------------------------------------" << endl;
}



Driver.cpp
#include <iostream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <fstream>

using namespace std;

#include "Article.h"
#include "LinkedList.h"

int main()
{
	LinkedList<Article> cacmDB;
	ifstream inFile;
	string key, title, author;
	string uKey;
	Article a;
	char choice;
	bool found = false;
	
	inFile.open("cacmpubs5.txt");
	
	if (!inFile)
	{
		cout << "Error opening file" << endl;
	}
	else
		cout << "Loading library, please wait..." << endl;
	
	while (!inFile.eof())
	{
		getline(inFile, key);
		a.SetKey(key);
		
		getline(inFile, author);
		a.SetAuthor(author);
		
		getline(inFile, title);
		a.SetTitle(title);

		key = a.GetKey();
		author = a.GetAuthor();
		title = a.GetTitle();
		
		cacmDB.PutItem(a);

	}

	
	cout << endl;
	cout << "Welcome to the CACM Library!" << endl;
	
	do
	{
	cout << "What would you like to do?" << endl;
	
	cout << "(F)ind an article" << endl;
	cout << "(L)ist all articles" << endl;
	cout << "(A)dd a new article" << endl;
	cout << "(R)emove an existing article" << endl;
	cout << "(E)xit" << endl;
	
	cout << "Your choice>";
	cin >> choice;
	cin.ignore(1000, '\n');
	switch(choice)
	{
		case 'F':
			cout << "Please enter a search key: ";
			getline(cin, uKey);
			
			// Not sure how to use GetItem while only comparing keys and
			// print out the key user entered as well as the author and title 
			// that go with it. 
			
			break;
		
		case 'L':
			cacmDB.display(cout);
			cout << cacmDB.GetLength() << " records shown." << endl;
			break;
		
		case 'A':
			cout << "Please enter the key for your new article: ";
			getline(cin, key);
			cout << endl;
			
			// Again don't know how to only look at keys with just the list (not using the file)
			// to see if user entered key is already in the list or not.
			
			cout << "Enter the author's name: ";
			getline(cin, author);
			cout << endl;
			
			cout << "Enter the title of the article: "; 
			getline(cin, title);
			cout << endl;
			
			a.SetKey(key);
			a.SetAuthor(author);
			a.SetTitle(title);
			
			cacmDB.PutItem(a);
			
			cout << "The following record has been added: " << endl
				 << a << endl;
		
			break;
		
		case 'R':
			// Same problem as with case 'F'. Not sure how to find article just using the
			// key and then delete the author and title that go with that key.
			break;
		
		case 'E':
			exit(0);
			break;
	}
	
	}while(choice != 'E');
	
	inFile.close();
	return 0;
}



I posted all of it just in case. But again my main problem is using just the key to find an item to remove and to find a specific item the user has specified and making sure that the a user-entered key is not in the list so a new article can be added. I've been trying to figure this out most of the day and I just can't. Thanks for any and all help.

This post has been edited by HKCHaN92: 03 March 2013 - 07:11 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Linked List: implementing GetItem() with only one part of a node

#2 #define  Icon User is online

  • Duke of Err
  • member icon

Reputation: 1327
  • View blog
  • Posts: 4,553
  • Joined: 19-February 09

Re: Linked List: implementing GetItem() with only one part of a node

Posted 03 March 2013 - 07:09 PM

I don't see a GetLine function.

I would create a helper function that checks whether an item exists in the list (and returns a bool).

To find an Article you can create an Article variable and set the key. Then pass it to your find function. That way the list just has to compare two items.

If your Article class had a constructor with a string parameter, then the compiler could perform an implicit conversion.
Was This Post Helpful? 1
  • +
  • -

#3 HKCHaN92  Icon User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 85
  • Joined: 23-July 11

Re: Linked List: implementing GetItem() with only one part of a node

Posted 05 March 2013 - 07:32 PM

Ok so I figured out how to code the find, add, and remove options so now the only problem is the output. For this assignment we are suppose to overload the << operator to print out the object but for each option he wants us to print it out differently and he never showed us how to do that. I'm pretty sure we are suppose to use just one overload<< function but the output he has in the example shows it being different each time for example if I list all the articles in the list it just uses the function as it is now printing it out like this:

--------------------------------------------------------------------
Key: Example:Key
Author: John Smith
Title: Example Title
--------------------------------------------------------------------

But if the user chooses the Find an article option for example and enters a key that is in the list the output should be:

---------------------------------------------------------------------
Record FOUND:

Key: Example:Key
Author: John Smith
Title: Example Title
----------------------------------------------------------------------

here is the current overload function:
ostream& operator<< (ostream &out, const Article &a)
{
	return out << "---------------------------------------------------------------------------" << endl
		        << "Key: " << a.GetKey() << endl 
			    << "Author: " << a.GetAuthor() << endl 
			    << "Title: " << a.GetTitle() << endl
			    << "---------------------------------------------------------------------------" << endl;
}



So how do I change the output to do this? Is there even a way to do it while still using just one overload function? Thanks again for any and all help.
Was This Post Helpful? 0
  • +
  • -

#4 #define  Icon User is online

  • Duke of Err
  • member icon

Reputation: 1327
  • View blog
  • Posts: 4,553
  • Joined: 19-February 09

Re: Linked List: implementing GetItem() with only one part of a node

Posted 05 March 2013 - 09:38 PM

I would think that the overloaded function would just output the following (the data specific to Article), and the functions that call it would add their own adornments.

Key: Example:Key
Author: John Smith
Title: Example Title
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5796
  • View blog
  • Posts: 12,631
  • Joined: 16-October 07

Re: Linked List: implementing GetItem() with only one part of a node

Posted 06 March 2013 - 05:33 AM

You haven't provided yourself any way to iterate over your list! You have a GetLength, but no way to retrieve a value at a particular index. No wonder you can't do a search!

Ideally, your list would actually implement an iterator. Something like:
template<class T>
struct Iterator {
	virtual bool hasNext() const = 0;
	virtual T next() = 0;
};



Also, making your NodeType an inner struct and giving it a constructor would make your code much easier. You're killing way to many pointers in here.

e.g.
template<class T>
void LinkedList<T>::PutItem(T item) {
	if (listData==NULL || item < listData->info) {
		listData = new NodeType(item, listData);
	} else {
		NodeType *p = listData;
		while(p->next!=NULL && p->next->info < item) {
		//...



If I had to store with keys, I'd just do a simple binary tree can call it a day. It doesn't even matter if it has no balance at all and is almost worse case, it would still make for faster, easier, lookups.

Hope this helps.

This post has been edited by baavgai: 06 March 2013 - 05:34 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1