Linked Lists

[HiTechRedneck3]

I'm working on a C++ program that is supposed to utilize a linked list to create a hypercard stack (whatever that is). The problem is, I have no idea what I'm doing. I've written some code, but it crashes, and honestly I have no idea if it even meets the specifications for what I need it to do if it did work as written. Here's the code I've come up with.

This is my .h file:

 //program6.h
#include <iostream>
#include <fstream>
using namespace std;

class Node {
public:
	Node();
	Node(char code, int num, string data);
	Node(Node & node);
	~Node();
	
	bool readFile();
	void setNext(Node* next);
	void print();
	
private:
	char Code;
	int Num;
	string Data;
	Node *Next;
};

My Implementation File:

//program6.cpp
#include "program6.h"
#include <iostream>
#include <string>

class List 
{
public:
class Node {
public:
	Node();
	Node(char code, int num, string data);
	Node(Node & node);
	~Node();
	
	bool readFile();
	void setNext(Node* next);
	void print();
	
private:
	char Code;
	int Num;
	string Data;
	Node *Next;
};

Node::Node() {
	Code = '\0';
	Num = 0;
	Data = "";
	Next = NULL;
}

Node::Node(char code, int num, string data) {
	char Code = code;
	int Num = num;
	string Data = data;
	Next = NULL;
}

Node::Node(Node & node) {
	Code = node.Code;
	Num = node.Num;
	Data = node.Data;
	Next = NULL;
}

Node::~Node() {
}

bool Node::readFile() {
	char code = '\0';
	int num = 0;
	string data = "";
	
	ifstream inputFile;
	inputFile.open("prog6.dat");
	
	if(!inputFile) {
		cerr << "Open Faiulre" << endl;
		exit(1);
		return false;
	}
	
	Node *head = NULL;
	while(!inputFile.eof()) {
		inputFile >> code >> num >> data;
		
		Node *temp = new Node(code, num, data);
		temp->setNext(head);
		head = temp;
	}
	
	inputFile.close();
	head->print();
	return true;
}

void Node::setNext(Node* next) {
	Next = next;
}

void Node::print() {
	cout << Code << " " << Num << " " << Data;
	if(Next != NULL) 
		Next->print();
}

And my main() file:

//program6test.cpp
#include "program6.h"
#include <iostream>
#include <fstream>
using namespace std;

int main() {
	Node list;
	if(list.readFile()) 
		cout << "Success" << endl;
	else
		cout << "Failure" << endl;
		
	return 0;
}

And here is the output I get when I run the program.

[cs331129@cs ~]$ g++ -o prog6 program6test.cpp
[cs331129@cs ~]$ prog6
terminate called after throwing an instance of 'St9bad_alloc'
  what():  St9bad_alloc
Aborted

And here are the "directions" I was given:

The hypercard “stack” concept is more general than a stack since “cards”
(elements) can be inserted anywhere and the entire “stack” can be traversed back
to the “home card”. Using circular lists, implement a hypercard stack.

Suppose we have a class or record structure (below) that contains a key code
(integer), a string of information (type Entry) 25 characters or fewer and a pointer

typedef struct elem_tag {
Key key;
Entry fact;
struct elem_tag * link;
} Node_type;

We can create a “hypercard stack”, read in information from a file, build a linked list of cards, and perform operations (insert(i), delete(d), traverse(t), home(h), forward(f), print(p)) on the list. For example, given a data file containing:

i 27 Mary had a little lamb
i 15 Today is a good day
i 35 Now is the time!
i 9 This lab is easy and fun
p

we produce a “hypercard stack” below.

1 2 3 4

v ---> 27 ---> 15 ---> 35 ---> 9 --- | Mary... Today... Now... This... | ----------------------------------------------------------------------------

Note that 27 is the “home card” (the home card is the next one after the one tail points to) and the card printed will be associate with “Current” (i.e., “This lab ...”). If we now process the following data file items:

d 35
t
i 37 Better now.

we will have the following list (note that traverse (t) should output each “fact” encountered for the entire list from the current pointer).

1 2 3 4

v v ---> 27 ---> 15 ---> 37 ---> 9 --- | Mary... Today... Better... This... | -------------------------------------------------------------------------------

If we process the data item

h

the list will be

1 2 3 4

v v ---> 27 ---> 15 ---> 37 ---> 9 --- } Mary... Today... Better... This... | -------------------------------------------------------------------------------

To delete 9 (i.e., d 9 appears in the data file) the card before must be found (“Current points to it”) and “Tail” adjusted.

Write a C++ program to do the following:

1. Read in the information and build a “hypercard” linked list
2. Process all codes and data. Check the code first before attempting to read
any additional data. Remember to check for special cases (i.e., list is empty, list has one element, etc.).

Input:
Each input data line in the file will consist of a character code and the appropriate data (no errors will be introduced) and will be in prog6.dat. Read and process each line separately to the end of the file.

Output:
Output will consist of facts (strings) from print (p) or traverse (t) commands and an active response for each command.

Hints:
Declare a list type, either as a class or a record (struct is a public class) - for example:

typedef struct list_tag{
Node_type * current;
Node_type * tail;
} List_type;

Build the initial linked list by inserting each data item in turn at the end of the list. Maintain “Tail” and “Current” pointers. You must check to see if the “
Tail” pointer is NULL before insertion, otherwise insertion is AFTER the “Current” position. Deletion will cause the “Current” pointer to be set to point at the card before the one being deleted (unless it is the last card in which case “Tail” and “Current” must become NULL). Forward (f) should move the “Current” pointer to the next card.

Write a separate function for each ADT list operation (i.e., init/create, insert, delete, print, traverse, home), developed first as stubs, then as full functions. Use the standard technique of placing the main, functions, and headers in separate files

Can anyone help me?

[Norm Gunderson]

I haven't studied this is detail, but I can see a couple of problems:

line 67: I think you need to read just the code first, then depending on whether the code is i, d, t, h, f, or p decide on a different action (e.g. if the code is i, then you want to try reading num & data and create a new Node, like you are at the moment. A case statement would be a good way to go). However (and more critically), you would be better off reading in a whole line at a time from your file. Have a look at this for an example of reading a line at a time: http://www.cplusplus.com/forum/general/17771/

Line 48: your destructor is empty. Depending on how you run your program, this is going to cause a memory leak. The reason being that all of the Nodes that you've been dynamically allocating on line 69 will never get de-allocated. It's unlikely to be giving you any issues at the moment, but I think you should put something like delete Next; in your destructor.

I would suggest printing out the values of code num & data after you've read them in - they probably won't be what you expect.