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 mustsavenode1.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( ) );
deleteremove_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

#include #include struct node { struct node *prev; int info; struct node *next; }*start; main() { int choice,n,m,po,i; start=NULL; while(1) { printf("1.Create List "); printf("2.Add at begining "); printf("3.Add after "); printf("4.Delete "); printf("5.Display "); printf("6.Count "); printf("7.Reverse "); printf("8.exit "); printf("Enter your choice : "); scanf("%d",&choice); switch(choice) { case 1: printf("How many nodes you want : "); scanf("%d",&n); for(i=0;iinfo=num; tmp->next=NULL; if(start==NULL) { tmp->prev=NULL; start->prev=tmp; start=tmp; } else { q=start; while(q->next!=NULL) q=q->next; q->next=tmp; tmp->prev=q; } }/*End of create_list()*/ addatbeg(int num) { struct node *tmp; tmp=malloc(sizeof(struct node)); tmp->prev=NULL; tmp->info=num; tmp->next=start; start->prev=tmp; start=tmp; }/*End of addatbeg()*/ addafter(int num,int c) { struct node *tmp,*q; int i; q=start; for(i=0;inext; if(q==NULL) { printf("There are less than %d elements ",c); return; } } tmp=malloc(sizeof(struct node) ); tmp->info=num; q->next->prev=tmp; tmp->next=q->next; tmp->prev=q; q->next=tmp; }/*End of addafter() */ del(int num) { struct node *tmp,*q; if(start->info==num) { tmp=start; start=start->next; /*first element deleted*/ start->prev = NULL; free(tmp); return; } q=start; while(q->next->next!=NULL) { if(q->next->info==num) /*Element deleted in between*/ { tmp=q->next; q->next=tmp->next; tmp->next->prev=q; free(tmp); return; } q=q->next; } if(q->next->info==num) /*last element deleted*/ { tmp=q->next; free(tmp); q->next=NULL; return; } printf("Element %d not found ",num); }/*End of del()*/ display() { struct node *q; if(start==NULL) { printf("List is empty "); return; } q=start; printf("List is : "); while(q!=NULL) { printf("%d ", q->info); q=q->next; } printf(" "); }/*End of display() */ count() { struct node *q=start; int cnt=0; while(q!=NULL) { q=q->next; cnt++; } printf("Number of elements are %d ",cnt); }/*End of count()*/ rev() { struct node *p1,*p2; p1=start; p2=p1->next; p1->next=NULL; p1->prev=p2; while(p2!=NULL) { p2->prev=p2->next; p2->next=p1; p1=p2; p2=p2->prev; /*next of p2 changed to prev */ } start=p1; }/*End of rev()*/

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---