Question
Part 1. In this project, you are asked to design and implement a class for double link list to hold integers:
– The class should be called DList, you also need a class called Node that contains an int as the data
Node needs the following data:
•int data; //the data held by the node
•Node* parent; //the parent of the Node
•Node* child; //the child of the Node
Node needs the following public functions:
•Node(int)// constructor to create a Node with the input int int
•GetData(); // return the int held by the Node
DList needs the following data:
•DList needs a head and tail, both should be pointers to Node, and initialized to NULL
•DList needs a default constructor (no parameter),
•a copy constructor (take const DList & as input)
DList needs the following public functions:
•void PushFront(int a); //create a Node containing a and add it to the front of the list
•void PushEnd(int a); //create a Node containing a and add it to the end of the list
•Node* PopFront(); //popping out the first Node of the list, if the list is empty, return NULL
•Node* PopEnd(); //popping out the last Node of the list, if the list is empty, return NULL DList & as input)
•void PrintListForward(); //print every element from start to end in one line separated by a space void
•PrintListReverse(); //print every element from end to start //in one line separated by a space
Specifications:
Files to turn in: You need to turn in four files in a tar.gz file: makefile, main.C, DList.C, DList.h. Among them, you need to use the main.C provided from the class web site which you cannot modify at all. DList.h declares the class DList and Node. You can make DList the friend of Node so it can access the private data of the Node.
THE GIVEN Main.C file:
#include "DList.h"
#include <iostream>
using namespace std;
int main() {
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
//return 0;
DList list;
int i;
//pust 10 numbers to the end
for (i = 0; i < 10; i++) list.PushEnd(i);
cout << "Print forward ";
list.PrintListForward();
cout << "Print reverse ";
list.PrintListReverse();
cout << "Pop front and print ";
//print the list from the beginning
Node* n = list.PopFront();
while ( n != NULL) {
cout << n->GetData() << endl;
n = list.PopFront();
}
//pust 10 numbers to the front
for (i = 0; i < 10; i++) list.PushFront(i);
//test copy constructor
DList* list2 = new DList(list);
cout << "Pop end and print ";
//print the list from the end
n = list2->PopEnd();
while ( n != NULL)
{
cout << n->GetData() << endl;
n = list2->PopEnd();
}
return 0;
}
Explanation / Answer
#include #include struct node { struct node *prev; int n; struct node *next; }*h,*temp,*temp1,*temp2,*temp4; void insert1(); void insert2(); void insert3(); void traversebeg(); void traverseend(int); void sort(); void search(); void update(); void delete(); int count = 0; void main() { int ch; h = NULL; temp = temp1 = NULL; printf(" 1 - Insert at beginning"); printf(" 2 - Insert at end"); printf(" 3 - Insert at position i"); printf(" 4 - Delete at i"); printf(" 5 - Display from beginning"); printf(" 6 - Display from end"); printf(" 7 - Search for element"); printf(" 8 - Sort the list"); printf(" 9 - Update an element"); printf(" 10 - Exit"); while (1) { printf(" Enter choice : "); scanf("%d", &ch); switch (ch) { case 1: insert1(); break; case 2: insert2(); break; case 3: insert3(); break; case 4: delete(); break; case 5: traversebeg(); break; case 6: temp2 = h; if (temp2 == NULL) printf(" Error : List empty to display "); else { printf(" Reverse order of linked list is : "); traverseend(temp2->n); } break; case 7: search(); break; case 8: sort(); break; case 9: update(); break; case 10: exit(0); default: printf(" Wrong choice menu"); } } } /* TO create an empty node */ void create() { int data; temp =(struct node *)malloc(1*sizeof(struct node)); temp->prev = NULL; temp->next = NULL; printf(" Enter value to node : "); scanf("%d", &data); temp->n = data; count++; } /* TO insert at beginning */ void insert1() { if (h == NULL) { create(); h = temp; temp1 = h; } else { create(); temp->next = h; h->prev = temp; h = temp; } } /* To insert at end */ void insert2() { if (h == NULL) { create(); h = temp; temp1 = h; } else { create(); temp1->next = temp; temp->prev = temp1; temp1 = temp; } } /* To insert at any position */ void insert3() { int pos, i = 2; printf(" Enter position to be inserted : "); scanf("%d", &pos); temp2 = h; if ((pos < 1) || (pos >= count + 1)) { printf(" Position out of range to insert"); return; } if ((h == NULL) && (pos != 1)) { printf(" Empty list cannot insert other than 1st position"); return; } if ((h == NULL) && (pos == 1)) { create(); h = temp; temp1 = h; return; } else { while (i next; i++; } create(); temp->prev = temp2; temp->next = temp2->next; temp2->next->prev = temp; temp2->next = temp; } } /* To delete an element */ void delete() { int i = 1, pos; printf(" Enter position to be deleted : "); scanf("%d", &pos); temp2 = h; if ((pos < 1) || (pos >= count + 1)) { printf(" Error : Position out of range to delete"); return; } if (h == NULL) { printf(" Error : Empty list no elements to delete"); return; } else { while (i next; i++; } if (i == 1) { if (temp2->next == NULL) { printf("Node deleted from list"); free(temp2); temp2 = h = NULL; return; } } if (temp2->next == NULL) { temp2->prev->next = NULL; free(temp2); printf("Node deleted from list"); return; } temp2->next->prev = temp2->prev; if (i != 1) temp2->prev->next = temp2->next; /* Might not need this statement if i == 1 check */ if (i == 1) h = temp2->next; printf(" Node deleted"); free(temp2); } count--; } /* Traverse from beginning */ void traversebeg() { temp2 = h; if (temp2 == NULL) { printf("List empty to display "); return; } printf(" Linked list elements from begining : "); while (temp2->next != NULL) { printf(" %d ", temp2->n); temp2 = temp2->next; } printf(" %d ", temp2->n); } /* To traverse from end recursively */ void traverseend(int i) { if (temp2 != NULL) { i = temp2->n; temp2 = temp2->next; traverseend(i); printf(" %d ", i); } } /* To search for an element in the list */ void search() { int data, count = 0; temp2 = h; if (temp2 == NULL) { printf(" Error : List empty to search for data"); return; } printf(" Enter value to search : "); scanf("%d", &data); while (temp2 != NULL) { if (temp2->n == data) { printf(" Data found in %d position",count + 1); return; } else temp2 = temp2->next; count++; } printf(" Error : %d not found in list", data); } /* To update a node value in the list */ void update() { int data, data1; printf(" Enter node data to be updated : "); scanf("%d", &data); printf(" Enter new data : "); scanf("%d", &data1); temp2 = h; if (temp2 == NULL) { printf(" Error : List empty no node to update"); return; } while (temp2 != NULL) { if (temp2->n == data) { temp2->n = data1; traversebeg(); return; } else temp2 = temp2->next; } printf(" Error : %d not found in list to update", data); } /* To sort the linked list */ void sort() { int i, j, x; temp2 = h; temp4 = h; if (temp2 == NULL) { printf(" List empty to sort"); return; } for (temp2 = h; temp2 != NULL; temp2 = temp2->next) { for (temp4 = temp2->next; temp4 != NULL; temp4 = temp4->next) { if (temp2->n > temp4->n) { x = temp2->n; temp2->n = temp4->n; temp4->n = x; } } } traversebeg(); }