School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!
Welcome to Dream.In.Code
Become an Expert!

Join 340,098 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 4,833 people online right now. Registration is fast and FREE... Join Now!



Double Linked List Question~ Need HeLp!

Double Linked List Question~ Need HeLp! Rate Topic: -----

#1 ickiepig  Icon User is offline

  • New D.I.C Head
  • Pip
  • Group: Members
  • Posts: 12
  • Joined: 24-October 07


Dream Kudos: 0

Posted 13 April 2008 - 10:21 PM

I got some problem with my Remove + Traverse + Overload Assignment Operator methods.
Remove - it works but looks weird.
Traverse - it does not work.
Overload Assignment Operator - I have no idea how to do it!
Need someone's help... Thanks!!!


// list.h
#include<iostream>
using namespace std;
#include<cstddef>
#include "node.h"

enum Error_code {success, fail, overflow, range_error};  // The possible error conditions

template <class List_entry>
class List {
public:
	List();	  // constructor
	/* Post: The List is initialized to be empty.*/
	
	int size() const;
	/* Post: Return the size of the List. */
	
	bool empty() const;
	/* Post: If the List is empty, true is returned. Otherwise false is returned. */
	
	void clear();
	/* Post: All List  entries have been removed; the List is empty*/
	
	void traverse(void (*visit)(List_entry &));
	/* Post: The action specified by function(*visit) has been performed on every entry of theList , 
			 beginning at position 0 and doing each in turn. */
	
	Error_code retrieve(int position, List_entry &x) const;
	/* Post: The entry at the indicated position has been retrieved to the 
			 output parameter x. If position is out of bounds an Error_code 
			 of range_error is returned. */

	Error_code replace(int position, const List_entry &x);
	/* Post: If 0 <= position < n, where n is the number of entries in the List, 
			 the function succeeds: The entry at position is replaced by x; 
			 all other entries remain unchanged.
			 Else: The function fails with a diagnostic error code.*/
			 
	Error_code remove(int position, List_entry &x);
	/* Post: If 0<= position < n, where n is the number of entries in the List, the function succeeds: 
			 The entry at position is removed from the List, and all later entries have their position numbers decreased by 1. 
			 The parameter x records a copy of the entry formerly at position.
			 Else: The function fails with a diagnostic error code.*/

	Error_code insert(int position, const List_entry &x);
	/* Post: If the List is not full and 0 <= position <= count the function succeeds.
			 Any entry formerly at position and all later entries have their position
			 increased by 1 and x is inserted at position of the List.
			 Else: the function fails with a diagnostic error code. */
			 				 
	~List();	 // destructor
	/* Post: The List has been destroyed and its memory freed. */
	
	const List<List_entry>& operator = (const List<List_entry> &original); // Overload assignment operator
	/* Stub */


	List(const List<List_entry> &original);	// copy constructor
	/* Post: The List is initialized as a copy of List original. */

protected:
	int count;
	mutable int current_position;
	mutable Node <List_entry> *current;
	Node<List_entry> *head;
	void set_position(int position) const;
	/* Pre:  Position is a valid position in the List: 0 <= position < count.
	   Post: The current Node pointer references the Node at position. */
};

template <class List_entry>
Error_code List<List_entry>::insert(int position, const List_entry &x)
/* Post: If the List is not full and 0 <= position <= count the function succeeds.
		 Any entry formerly at position and all later entries have their position
		 increased by 1 and x is inserted at position of the List.
		 Else: the function fails with a diagnostic error code. */
{
	Node<List_entry> *new_node, *following, *preceding;
	if (position < 0 || position > count) return range_error;
	if (position == 0) {
		if (count == 0) following = NULL;
		else {
			set_position(0);
			following = current;
		}
		preceding = NULL;
	}
	else {
		set_position(position - 1);
		preceding = current;
		following = preceding->next;
	}
	new_node = new(nothrow) Node<List_entry>(x, preceding, following);
	if (new_node == NULL) return overflow;
	if (preceding != NULL) preceding->next = new_node;
	if (following != NULL) following->back = new_node;
	current = new_node;
	current_position = position;
	count++;
	return success;
}

template <class List_entry>
Error_code List<List_entry>::remove(int position, List_entry &x)
/* Post: If 0<= position < n, where n is the number of entries in the List, the function succeeds: 
		 The entry at position is removed from the List, and all later entries have their position numbers decreased by 1. 
		 The parameter x records a copy of the entry formerly at position.
		 Else: The function fails with a diagnostic error code.*/
{	
	Node<List_entry> *previous, *following;
	if (position < 0 || position >= count) return range_error;
	if (position > 0) {
		set_position(position-1);
		previous = current;
		following = previous->next;
		previous->next = following->next;
		if(following->next) following->next->back = previous;
	}
	else{
		following = head;
		head = head->next;
		if(head)head->back = NULL;
	}
	delete following;
	count--;
	return success;
}
	
template <class List_entry>
Error_code List<List_entry>::retrieve(int position, List_entry &x) const
/* Post: The entry at the indicated position has been retrieved to the 
		 output parameter x. If position is out of bounds an Error_code 
		 of range_error is returned. */
{
	if (position < 0 || position >= count || empty()) return range_error;
	set_position(position);
	x = current->entry;
	return success;
}

template <class List_entry>
Error_code List<List_entry>::replace(int position, const List_entry &x)
/* Post: If 0 <= position < n, where n is the number of entries in the List, 
		 the function succeeds: The entry at position is replaced by x; 
		 all other entries remain unchanged.
		 Else: The function fails with a diagnostic error code.*/			 
{
	if (position < 0 || position >= count) return range_error;
	set_position(position);
	current->entry=x;
	return success;
}


template <class List_entry>
bool List<List_entry>::empty() const
/* Post: If the List is empty, true is returned. Otherwise false is returned. */
{
	return (count == 0);
}

template <class List_entry>
int List<List_entry>::size() const
/* Post: Return the size of the List. */
{
	return count;
}

template <class List_entry>
List<List_entry>::List()	// Constructor
/* Post: The List is initialized to be empty.*/
{
	count = 0;
}

template <class List_entry>
void List<List_entry>::clear()
/* Post: All List entries have been removed; the List is empty*/
{
	List_entry x;
	while(!empty())remove(0,x);
}

template <class List_entry>
void List<List_entry>::traverse(void (*visit)(List_entry &))
/* Post: The action specified by function(*visit) has been performed on every entry of the List, 
		 beginning at position 0 and doing each in turn. */
{
	Node<List_entry> *new_node = head;
	while(new_node){
		(*visit)(new_node->entry);
		new_node = new_node -> next;
	}
}

template <class List_entry>
List<List_entry>::~List()	 // Destructor
/* Post: The List has been destroyed and its memory freed. */
{
	clear();
}

template <class List_entry>
const List<List_entry>& List<List_entry>::operator = (const List<List_entry> &original) // Overload assignment operator
/* Stub */
{
}

template <class List_entry>
List<List_entry>::List(const List<List_entry> &original) // copy constructor
/* Post: The List is initialized as a copy of List original. */
{
	List_entry x;
	count = 0;
	for (int i = 0; i < original.count; i++){
		original.retrieve(i, x);
		insert(i, x);
	}
}

template <class List_entry>
void List<List_entry>::set_position(int position) const
/* Pre:  Position is a valid position in the List: 0 <= position < count.
   Post: The current Node pointer references the Node at position. */
{
	if (current_position <= position)
		for (; current_position != position; current_position++)
			current = current->next;
	else
		for(; current_position != position; current_position--)
			current = current->back;
}



 
// node.h
#include<cstddef>

template <class Node_entry>
struct Node{
// data members
	Node_entry entry;
	Node<Node_entry> *next;
	Node<Node_entry> *back;
// constructors
	Node();
	/* Post: an empty node is created that has no next or previous nodes. */
	
	Node(Node_entry item, Node<Node_entry> *link_back = NULL,
						  Node<Node_entry> *link_next = NULL);
	/* Post: a node is created that contains the entry item and has the node at link_back
			 as the back node and link_next as the next node. */
};

template <class Node_entry>
Node<Node_entry>::Node()
/* Post: an empty node is created that has no next node. */
{
	next = NULL;
	back = NULL;
}

template <class Node_entry>
Node<Node_entry>::Node(Node_entry item, Node<Node_entry> *link_back, Node<Node_entry> *link_next)
/* Post: a node is created that contains the entry item and has the node at link_back as the
		 back node and link_next as the next node. */
{
	entry = item;
	next = link_next;
	back = link_back;
}



// main.cpp
#include<iostream>
using namespace std;

#include "list.h"

typedef char List_entry;

void print(List_entry &x);
/* Post: Print a character. */

void help();
/* Post: A help screen for the program is printed, giving the meaning of each
		 command that the user may enter.*/

void introduction();
// An introduction of the program.

char get_command();
/* Post: The user enters a command (I, D, R, G, P, H, Q, i, d, r, g, p, h, or q). The function returns
		 the command entered. */
		 
bool do_command(char c, List<List_entry> &test_list);
/* Pre:  c represents a valid command.
   Post: Performs the given command c on the List test_List.
		 Returns false if c == 'q', otherwise returns true.
   Uses: The class List. */

int main()
/* Post: Accepts commands from user as a menu-driven demonstration program
		 for the class List.
   Uses: The class List and the funcitons introduction, get_command, and do_command. */
{
	List<List_entry> test_list;
	introduction();
	while (do_command(get_command(), test_list));	
}

void introduction()
// stub
{
	cout << "The Doubly Linked List." << endl;
}

void help()
/* Post: A help screen for the program is printed, giving the meaning of each
		 command that the user may enter.*/
{
	cout << endl
		 << "This program allows the user to enter one command" << endl
		 << "(but only one) on each input line." << endl
		 << "For example, if the command G is entered, then" << endl
		 << "the program will retreive an entry from the list." << endl
		 << endl
		 << "The valid commands are:" << endl
		 << "I - Insert a entry into the list" << endl
		 << "D - Delete an entry from the list" << endl
		 << "R - Replace an entry in the list" << endl
		 << "G - Get an entry from the list" << endl
		 << "P - Print the list" << endl
		 << "H - This help screen" << endl
		 << "Q - Quit" << endl
		 << "Press < Enter > to continue." << flush;
	
	char c;
	cin.get(c);   // flush out an extra newline
	do {
		 cin.get(c);
	} while (c != '\n');
}

char get_command()
/* Post: The user enters a command (I, D, R, G, P, H, Q, i, d, r, g, p, h, or q). The function returns
		 the command entered. */
{
	char command;
	bool waiting = true;
	cout << "Select command and press < Enter > :";
	while (waiting){
		cin >> command;
		command = tolower(command);
		if (command == 'i' || command == 'd' || command == 'r' ||
			command == 'g' || command == 'p' || command == 'h' || command == 'q') 
			waiting = false;
		else {
			cout << "Please enter a valid command:" << endl
				 << "[I]insert [D]delete [R]replace" << endl
				 << "[G]get [P]print [H]Help" << endl
				 << "[Q]uit." << endl;
		}
	}
	return command;
}

bool do_command(char c, List<List_entry> &test_list)
/* Pre:  c represents a valid command.
   Post: Performs the given command c on the List test_list.
		 Returns false if c == 'q', otherwise returns true.
   Uses: The class List. */
{
	bool continue_input = true;
	int position;
	List_entry x;
	Error_code err;
	switch (c) {
	case 'i':
		cout << "Please enter a position to insert the new entry: " << flush;
		cin >> position;
		cout << "Please enter a new character to insert into the List: " << flush;
		cin >> x;
		err = test_list.insert(position, x);
		if (err == overflow)
			cout << "List is full." << endl;
		if (err == range_error)
			cout << "Position is not valid." << endl;
		break;
	case 'd':
		cout << "Please enter a position to delete: " << flush;
		cin >> position;
		err = test_list.remove(position, x);
		if (err == range_error)
			cout << "Position is not valid." << endl;
		else
			cout << "The removed entry was " << x << "." << endl;
		break;
	case 'r':
		cout << "Please enter a position to replace: " << flush;
		cin >> position;
		cout << "Please enter a new character to put in this position: " << flush;
		cin >> x;
		err = test_list.replace(position, x);
		if (err == range_error)
			cout << "Position is not valid." << endl;
		break;
	case 'g':
		cout << "Please enter a position to get: " << flush;
		cin >> position;
		err = test_list.retrieve(position, x);
		if (err == range_error)
			cout << "Position is not valid." << endl;
		else
			cout << "The entry is " << x << "." << endl;
		break;
	case 'p':
		test_list.traverse(print);
		cout << endl;
		break;
	case 'h':
		help();
		break;
	case 'q':
		cout << "List demonstration finished." << endl;
		continue_input = false;
		break;
	}
	return continue_input;
}

void print(List_entry &x)
{
	cout << x << " ";
}
		 


This post has been edited by ickiepig: 13 April 2008 - 10:22 PM

Was This Post Helpful? 0
  • +
  • -



Fast Reply

  

1 User(s) are reading this topic
0 members, 1 guests, 0 anonymous users



Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month