Member Avatar for ayk-retail

I have a major problem. I need to write a program using linked lists that will display...
A B C D E F
and then...
F E D C B A
without using a tail pointer. When I run the program, it displays the first set of letters but crashes immediately thereafter. Visual Studio does not display any errors within the program. I was given some functions to call for for the program. Here is the code...

Implementation Code:

#include <iostream>
#include "node1.h"
#include <cassert>
#include <cstdlib>
using namespace std;
using namespace main_savitch_5;


void print_list( node* head_ptr);
node* reverse_list(node* head_ptr);

void main()
{
	node* head_ptr;

	list_head_insert(head_ptr, 'F');
	list_head_insert(head_ptr, 'E');
	list_head_insert(head_ptr, 'D');
	list_head_insert(head_ptr, 'C');
	list_head_insert(head_ptr, 'B');
	list_head_insert(head_ptr, 'A');
	
	print_list(head_ptr);
	cout << endl;
	reverse_list(head_ptr);
	print_list(head_ptr);
	return;
}

void print_list(node* ptr)
{
	for (; ptr; ptr = ptr->link())
		cout << ptr->data() << " ";
	cout << endl;
	return;
}


node* reverse_list(node* head_ptr)
{
	cout << "Reversed..." << endl;
	node* result_ptr = NULL;
	node* curr_ptr = NULL;
	while (head_ptr)
	{
		curr_ptr = head_ptr;
		head_ptr = head_ptr->link( );
		curr_ptr->set_link(result_ptr);
		result_ptr = curr_ptr;
	}
	return result_ptr;
	//node* buffer1;
	//node* buffer2;
	//int i = 5;
	//buffer2 = ptr->info;
	//for (buffer1 = ptr->info; ptr; ptr = ptr->next)
	//{
	//	buffer2 = 

	//}
	//for (; ptr; ptr = ptr->next)
	//cout << ptr->info << " ";
}

Here is the driver code:

// FILE: node1.cxx
// IMPLEMENTS: The functions of the node class and the
// linked list toolkit (see node1.h for documentation).
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.

#include "node1.h"
#include <cassert>    // Provides assert
#include <cstdlib>    // Provides NULL and size_t
using namespace std;

namespace main_savitch_5
{
    size_t list_length(const node* head_ptr)
    // Library facilities used: cstdlib
    {
	const node *cursor;
	size_t answer;

	answer = 0;
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    ++answer;
	
	return answer;
    }
    
    void list_head_insert(node*& head_ptr, const node::value_type& entry)
    {
	head_ptr = new node(entry, head_ptr);
    }

    void list_insert(node* previous_ptr, const node::value_type& entry) 
    {
	node *insert_ptr;
    
	insert_ptr = new node(entry, previous_ptr->link( ));
	previous_ptr->set_link(insert_ptr);
    }

    node* list_search(node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
	node *cursor;
   
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    if (target == cursor->data( ))
		return cursor;
	return NULL;
    }

    const node* list_search(const node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
	const node *cursor;
   
	for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
	    if (target == cursor->data( ))
		return cursor;
	return NULL;
    }

    node* list_locate(node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
	node *cursor;
	size_t i;
    
	assert (0 < position);
	cursor = head_ptr;
	for (i = 1; (i < position) && (cursor != NULL); i++)
	    cursor = cursor->link( );
	return cursor;
    }

    const node* list_locate(const node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
	const node *cursor;
	size_t i;
    
	assert (0 < position);
	cursor = head_ptr;
	for (i = 1; (i < position) && (cursor != NULL); i++)
	    cursor = cursor->link( );
	return cursor;
    }

    void list_head_remove(node*& head_ptr)
    {
	node *remove_ptr;

	remove_ptr = head_ptr;
	head_ptr = head_ptr->link( );
	delete remove_ptr;
    }

    void list_remove(node* previous_ptr)
    {
	node *remove_ptr;

	remove_ptr = previous_ptr->link( );
	previous_ptr->set_link( remove_ptr->link( ) );
	delete remove_ptr;
    }

    void list_clear(node*& head_ptr)
    // Library facilities used: cstdlib
    {
	while (head_ptr != NULL)
	    list_head_remove(head_ptr);
    }

    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) 
    // Library facilities used: cstdlib
    {
	head_ptr = NULL;
	tail_ptr = NULL;

	// Handle the case of the empty list.
	if (source_ptr == NULL)
	    return;
    
	// Make the head node for the newly created list, and put data in it.
	list_head_insert(head_ptr, source_ptr->data( ));
	tail_ptr = head_ptr;
    
	// Copy the rest of the nodes one at a time, adding at the tail of new list.
	source_ptr = source_ptr->link( ); 
	while (source_ptr != NULL)
	{
	    list_insert(tail_ptr, source_ptr->data( ));
	    tail_ptr = tail_ptr->link( );
	    source_ptr = source_ptr->link( );
	}
    }

}

Here is the header code:

// FILE: node1.h
// PROVIDES: A class for a node in a linked list, and list manipulation
// functions, all within the namespace main_savitch_5
//
// TYPEDEF for the node class:
//     Each node of the list contains a piece of data and a pointer to the
//     next node. The type of the data is defined as node::value_type in a
//     typedef statement. The value_type may be any
//     of the built-in C++ classes (int, char, ...) or a class with a copy
//     constructor, an assignment operator, and a test for equality (x == y).
//
// CONSTRUCTOR for the node class:
//   node(
//     const value_type& init_data = value_type(),
//     node* init_link = NULL
//   )
//     Postcondition: The node contains the specified data and link.
//     NOTE: The default value for the init_data is obtained from the default
//     constructor of the value_type. In the ANSI/ISO standard, this notation
//     is also allowed for the built-in types, providing a default value of
//     zero. The init_link has a default value of NULL.
//
// NOTE:
//   Some of the functions have a return value which is a pointer to a node.
//   Each of these  functions comes in two versions: a non-const version (where
//   the return value is node*) and a const version (where the return value
//   is const node*). 
// EXAMPLES:
//    const node *c;
//    c->link( ) activates the const version of link
//    list_search(c,... calls the const version of list_search
//    node *p;
//    p->link( ) activates the non-const version of link
//    list_search(p,... calls the non-const version of list_search
//
// MEMBER FUNCTIONS for the node class:
//   void set_data(const value_type& new_data)
//     Postcondition: The node now contains the specified new data.
//   
//   void set_link(node* new_link)
//     Postcondition: The node now contains the specified new link.
//
//   value_type data( ) const
//     Postcondition: The return value is the data from this node.
//
//   const node* link( ) const <----- const version
//   node* link( ) <----------------- non-const version
//   See the note (above) about the const version and non-const versions:
//     Postcondition: The return value is the link from this node.
//   
// FUNCTIONS in the linked list toolkit:
//   size_t list_length(const node* head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The value returned is the number of nodes in the linked
//     list.
//
//   void list_head_insert(node*& head_ptr, const node::value_type& entry) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: A new node containing the given entry has been added at
//     the head of the linked list; head_ptr now points to the head of the new,
//     longer linked list.
//
//   void list_insert(node* previous_ptr, const node::value_type& entry) 
//     Precondition: previous_ptr points to a node in a linked list.
//     Postcondition: A new node containing the given entry has been added
//     after the node that previous_ptr points to.
//
//   const node* list_search(const node* head_ptr, const node::value_type& target) 
//   node* list_search(node* head_ptr, const node::value_type& target) 
//   See the note (above) about the const version and non-const versions:
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The pointer returned points to the first node containing
//     the specified target in its data member. If there is no such node, the
//     null pointer is returned.
//
//   const node* list_locate(const node* head_ptr, size_t position) 
//   node* list_locate(node* head_ptr, size_t position) 
//   See the note (above) about the const version and non-const versions:
//     Precondition: head_ptr is the head pointer of a linked list, and
//     position > 0.
//     Postcondition: The pointer returned points to the node at the specified
//     position in the list. (The head node is position 1, the next node is
//     position 2, and so on). If there is no such position, then the null
//     pointer is returned.
//
//   void list_head_remove(node*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list, with at
//     least one node.
//     Postcondition: The head node has been removed and returned to the heap;
//     head_ptr is now the head pointer of the new, shorter linked list.
//
//   void list_remove(node* previous_ptr) 
//     Precondition: previous_ptr points to a node in a linked list, and this
//     is not the tail node of the list.
//     Postcondition: The node after previous_ptr has been removed from the
//     linked list.
//
//   void list_clear(node*& head_ptr) 
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: All nodes of the list have been returned to the heap,
//     and the head_ptr is now NULL.
//
//   void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) 
//     Precondition: source_ptr is the head pointer of a linked list.
//     Postcondition: head_ptr and tail_ptr are the head and tail pointers for
//     a new list that contains the same items as the list pointed to by
//     source_ptr. The original list is unaltered.
//  void list_piece(
//    const node* start_ptr, const node* end_ptr, 
//    node*& head_ptr, node*& tail_ptr
//  )
//    Precondition: start_ptr and end_ptr are pointers to nodes on the same
//    linked list, with the start_ptr node at or before the end_ptr node
//    Postcondition: head_ptr and tail_ptr are the head and tail pointers for a
//    new list that contains the items from start_ptr up to but not including 
//    end_ptr.  The end_ptr may also be NULL, in which case the new list 
//    contains elements from start_ptr to the end of the list.
//
// DYNAMIC MEMORY usage by the toolkit: 
//   If there is insufficient dynamic memory, then the following functions throw
//   bad_alloc: the constructor, list_head_insert, list_insert, list_copy,
//   list_piece.
#include <iostream>
#ifndef MAIN_SAVITCH_NODE1_H  
#define MAIN_SAVITCH_NODE1_H
#include <cstdlib> // Provides size_t and NULL

namespace main_savitch_5
{
    class node
    {
    public:
	// TYPEDEF
	typedef char value_type;
    
	// CONSTRUCTOR
	node(
	    const value_type& init_data = value_type( ),
	    node* init_link = NULL
	)
	{ data_field = init_data; link_field = init_link; }

	// Member functions to set the data and link fields:
    	void set_data(const value_type& new_data) { data_field = new_data; }
    	void set_link(node* new_link)             { link_field = new_link; }

	// Constant member function to retrieve the current data:
	value_type data( ) const { return data_field; }

	// Two slightly different member functions to retreive
	// the current link:
	const node* link( ) const { return link_field; }
    	node* link( )             { return link_field; }
	
    private:
	value_type data_field;
	node* link_field;
    };

    // FUNCTIONS for the linked list toolkit
    size_t list_length(const node* head_ptr);
    void list_head_insert(node*& head_ptr, const node::value_type& entry); 
    void list_insert(node* previous_ptr, const node::value_type& entry);  
    node* list_search(node* head_ptr, const node::value_type& target);
    const node* list_search
	(const node* head_ptr, const node::value_type& target);
    node* list_locate(node* head_ptr, size_t position);
    const node* list_locate(const node* head_ptr, size_t position);
    void list_head_remove(node*& head_ptr);
    void list_remove(node* previous_ptr);
    void list_clear(node*& head_ptr);
    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr);
}

#endif

Thank you so much for your help!

  • 3 Contributors
  • 3 Replies
  • 386 Views
  • 18 Hours Discussion Span
  • Latest Post Latest Post by Laiq Ahmed
Member Avatar for ayk-retail

Thank you so much! It doesn't freeze anymore! However, it just displays the first...
A B C D E F
and then...
A
and then stops. I am not sure what to do about that. Also, can you recommend what I should initialize this to...
# node* head_ptr;

Thanks again!

Member Avatar for Laiq Ahmed

your link list implementation is stack based implementation,
to reverse it you first need to know how to reverse the list.

there are three ways of doing this.
1. Recursive.
2. using explicity stack.
3. using iterative approach. ( the one you are using).

your code says the following

node* reverse_list(node* head_ptr){	
               cout << "Reversed..." << endl;
 	node* result_ptr = NULL;
	node* curr_ptr = NULL;
	while (head_ptr)
	{
		curr_ptr = head_ptr;
		head_ptr = head_ptr->link( );
		curr_ptr->set_link(result_ptr);
		result_ptr = curr_ptr;
	}
	return result_ptr;
}

what it does.
statement 1. do nothing but printing.
you got two extra pointers.
traversing the list on the basis of headPtr.
holding the headPtr in currentPtr.
incrementing the headPtr.
setting NULL in the currentPtr link.
setting resultPtr = CurrentPtr ( which is same as headPtr ).

this was your first iteration. but where you reversed the list.

always remember to check the preconditions and postconditions.
in the reverse case the precondition is to check if the list is null, or it contains only one element. reversing that would be nothing ...

lets do the reverse.

void Reverse (Link* head)
{
	//checking preconditions.
	if (!head && !head->next)
	          return;
                //here we are sure that second node exists.
	Link* temp = head->next; // holding 2nd node reference.
                Link* iter = temp->next; // hold the reference of 3rd Node OR NULL.
	head->next = 0;  // setting the first Node next = 0; (why? think)
	while (temp)    // traversing from 2nd node to the end.
	{
		iter = temp->next;  // saving the 3rd Node.
		temp->next = head; // reversing the 2nd to point to first.
		head = temp;     // incrementing head.
		temp = iter;      // incrementing 2nd to 3rd saved abov.
	}
}

hope this help.
try the other two methods yourself.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.