Please Create a Separate Header file, Implementation file, and driver.... Also p
ID: 3531620 • Letter: P
Question
Please Create a Separate Header file, Implementation file, and driver.... Also please dont change code syntax and use current standard c++ syntax. 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 // 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 // Provides assert #include // 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
Singly Linked List:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct sll
{
int data;
struct sll *next;
}node;
int n;
node *head;
void create();
void insert();
void delete();
void display();
int main()
{
int choice;
do
{
printf(" ************* singly linked list ******************* ");
printf(" 1.create 2.insert 3.delete 4.display 0.exit");
printf(" enter u r choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
insert();
break;
case 3:
delete();
break;
case 4:
display();
break;
default:
exit(0);
}
}while(choice<=4); }
void create()
{
int i;
node *new,*temp;
printf(" enter the number of datas");
scanf("%d",&n);
head=(node*)malloc(sizeof(node));
temp=head;
printf(" enter the datas: ");
scanf("%d",&head->data);
for(i=2;i<=n;i++)
{
new=(node*)malloc(sizeof(node));
scanf("%d",&new->data);
temp->next=new;
temp=temp->next;
}
temp->next=NULL;
display();
}
void display()
{
node *temp;
temp=head;
do
{
printf("%d=> ",temp->data);
temp=temp->next;
}
while(temp!=NULL);
getch();
}
void insert()
{
node *temp,*new;
int loc,data,i;
printf(" enter the data: ");
scanf("%d",&data);
printf(" enter the location: ");
scanf("%d",&loc);
new=(node*)malloc(sizeof(node));
if(loc==1)
{
new->data=data;
new->next=head;
head=new;
}
else
{
temp=head;
for(i=2;(i<loc&&(temp->next!=NULL));i++)
temp=temp->next;
new->data=data;
new->next=temp->next;
temp->next=new;
}
n++;
printf(" After Insert ");
display();
}
void delete()
{
node *new,*temp,*prev;
int n;
printf(" enter the no: ");
scanf("%d",&n);
temp=head;
while(temp->data!=n)
{
prev=temp;
temp=temp->next;
}
prev->next=temp->next;
free(temp);
printf(" After delete ");
display();
}
Doubly Linked List
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct dll
{
int data;
struct dll *next,*prev;
}node;
int n;
node *head;
void create();
void insert();
void delete();
void display();
int main()
{
int choice;
do
{
printf(" >>>>>>DOUBLY LINKED LIST<<<<<< ");
printf(" 1.CREATE 2.INSERT 3.DELETE 4.DISPLAY 0.EXIT");
printf(" WHAT IS YOUR CHOICE?? ");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
insert();
break;
case 3:
delete();
break;
case 4:
display();
break;
default:
exit(0);
}
}while(choice<=4); }
void create()
{
int i;
node *new,*temp;
printf(" ENTER NUMBER OF NODES TO BE CREATED: ");
scanf("%d",&n);
head=(node*)malloc(sizeof(node));
head->prev=head;
head->next=NULL;
temp=head;
printf(" ENTER THE DATA IN THE NODES: ");
scanf("%d",&head->data);
for(i=2;i<=n;i++)
{
new=(node*)malloc(sizeof(node));
scanf("%d",&new->data);
temp->next=new;
new->prev=temp;
temp->prev=new;
temp=temp->next;
}
display();
}
void display()
{
node *temp;
temp=head;
do
{
printf("%d=> ",temp->data);
temp=temp->next;
}
while(temp!=NULL);
getch();
}
void insert()
{
node *temp,*new,*temp1;
int loc,data,i;
printf(" ENTER THE DATA IN THE NEW NODE: ");
scanf("%d",&data);
printf(" ENTER THE LOCATION OF THE NEW NODE: ");
scanf("%d",&loc);
new=(node*)malloc(sizeof(node));
if(loc==1)
{
new->data=data;
new->next=NULL;
new->prev=head->prev;
temp=head->prev;
temp->prev=new;
}
else
{
temp=head;
for(i=2;(i<loc&&(temp->next!=head));i++)
{temp=temp->next;}
temp1=temp->next;
new->data=data;
temp->next=new;
new->prev=temp;
temp1->prev=new;
new->next=temp1;
}
n++;
printf(" AFTER INSERTION: ");
display();
}
void delete()
{
node *new,*temp,*tempr,*templ;
int ne;
printf(" ENTER THE DATA TO BE DELETED: ");
scanf("%d",&ne);
temp=head;
while(temp->data!=ne)
{
temp=temp->next;
}
templ=temp->prev;
tempr=temp->next;
free(temp);
templ->next=tempr;
tempr->prev=templ;
printf(" AFTER DELETION ");
display();
}