Create a Doubly Linked List Class. Start with the linked list class from Chapter

Question

Create a Doubly Linked List Class.

Start with the linked list class from Chapter #5. You must save node1.cpp as dnode.cpp and revise the functions in this file to implement a doubly linked. Create a driver program that tests all the functions in the implementation file. Your files should be named:
dnode.h
dnode.cpp
lastname3.cpp

Comment your driver program to show me what function you are testing.
Example: // Testing Constructor Function
// Testing List Search

You must add a traverse function to the linked list toolkit. This function will need to traverse the list both forwards and backwards in order to see that the links are correct.

// FILE: dnode.h
// PROVIDES: A class for a node in a doubly linked list, and list manipulation
// functions, all within the namespace main_savitch_5
//
// TYPEDEF for the dnode class:
// Each node of the list contains a piece of data and a pointers to the
// previous and next nodes. The type of the data is defined as
// dnode::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 dnode class:
// dnode(
// const value_type& init_data = 0,
// node* init_fore = NULL,
// node* init_back = NULL
// )
// Postcondition: The node contains the specified data and links.
// 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. Both links have 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 dnode*) and a const version (where the return value
// is const dnode*).
// EXAMPLES:
// const dnode *c;
// c->fore( ) activates the const version of fore
// dnode *p;
// p->fore( ) activates the non-const version of fore
//
// MEMBER FUNCTIONS for the dnode class:
// void set_data(const value_type& new_data)
// Postcondition: The node now contains the specified new data.
//
// void set_fore(dnode* new_fore)
// and
// void set_back(dnode* new_back)
// Postcondition: The node now contains the specified new link.
//
// value_type data( ) const
// Postcondition: The return value is the data from this dnode.
//
// const dnode* fore( ) const <----- const version
// dnode* fore( ) <----------------- non-const version
// const dnode* back( ) const <----- const version
// dnode* back( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is a link from this dnode.

// HEADER

#ifndef DNODE_H
#define DNODE_H
#include <cstdlib> // Provides size_t and NULL

// TYPEDEF
typedef double value_type;

class dnode
{
public:

// CONSTRUCTOR
dnode(const value_type& init_data = 0.0,
dnode* init_fore = NULL,
dnode* init_back = NULL)
{
data_field = init_data;
link_fore = init_fore;
link_back = init_back;
}

// Member functions to set the data and link fields:
void set_data(const value_type& new_data) { data_field = new_data; }
void set_fore(dnode* new_fore) { link_fore = new_fore; }
void set_back(dnode* new_back) { link_back = new_back; }

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

// Two slightly different member functions to retrieve each current link:
const dnode* fore( ) const { return link_fore; }
dnode* fore( ) { return link_fore; }
const dnode* back( ) const { return link_back; }
dnode* back( ) { return link_back; }

private:
value_type data_field;
dnode *link_fore;
dnode *link_back;
};

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

#endif

// IMPLEMENTATION

// FILE: node1.cpp
// 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 <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t
#include "node1.h"

size_t list_length(const node* head_ptr)
{
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 value_type& entry)
{
head_ptr = new node(entry, head_ptr);
}

void list_insert(node* previous_ptr, const 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 value_type& target)
{
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 value_type& target)
{
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)
{
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)
{
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)
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}



void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
{
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( );
}
}

Explanation / Answer

Hi, my friend this is a class i mad my self if u need more help message me PLEASE RATE #include using namespace std; struct nodeType { char info; nodeType *next; nodeType *back; }; class doublylinkedList { public: doublylinkedList() { head=new nodeType; head=0; } ~doublylinkedList() { destroyList(); } void insertFirst(char val) { nodeType *p; p=new nodeType; p->info=val; p->next=0; p->back=0; if(head==0) head=p; else { p->next=head->next; head=p; } } void insertLast(char val) { nodeType *p; p=new nodeType; p->info=val; p->next=0; p->back=0; if(head==0) head=p; else { nodeType *c; c=head; while(c->next!=0) c=c->next; c->next=p; p->back=c; } } void insertAfter(int loc,char val) { nodeType *p; p=new nodeType; p->info=val; p->back=0; p->next=0; if(head==0) head=p; else { nodeType *c; c=head; int count=0; while(countnext; count++; } p->next=c->next; p->back=c; c->next=p; } } void insertBefore(int loc,char val) { nodeType *p; int count=0; p=new nodeType; p->info=val; p->next=0; p->back=0; if(head==0) head=p; else { nodeType *c; c=head; while(countnext; count++; } p->next=c->next; p->back=c; c->next=p; c->next->next->back=c->next; } } void initializeList() { destroyList(); } void destroyList() { nodeType *q; while(head!=0) { q=head; head=head->next; delete q; } } bool isEmpty() { return (head->next == NULL); } void print() { nodeType *curent=head; while(curent != NULL) { coutinfo); return -1; } char back() { nodeType *curent=head; while(curent->next != NULL) curent = curent -> next; return (curent->info); } protected: nodeType *head; public: void copyList(const doublylinkedList &cf) { destroyList(); nodeType *c; if(cf.head!=0) c=cf.head; while(c!=0) { insertLast(c->info); c=c->next; } } void removeAfter(int loc) { nodeType *p; int counter=0; int len=length(); p=head; if(head!=0 && loc =0) { while(counter!=loc+1 && counternext; counter++; } if(loc+1==len-1) { p->back->next=0; delete p; } else { p->next->back=p->back; p->back->next=p->next; delete p; } } } void removeBefore(int loc) { int counter=0; int len=length(); nodeType *p; p=head; if(head!=0 && loc>0 && locnext; counter++; } if(loc-1==0) { p->next->back=0; head=p->next; delete p; } else { p->next->back=p->back; p->back->next=p->next; delete p; } } } void removeAt(int loc) { int count=0; nodeType *p; if(head!=0 && loc>=0) { if(loc>0) removeAfter(loc-1); else { p=head; head=head->next; head->next->back=0; delete p; } } } }; int main() { doublylinkedList obj1; obj1.insertFirst('x'); obj1.print(); cout

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---