How would you solve this problem? The text book I am using is Data Structures Us
ID: 3789528 • Letter: H
Question
How would you solve this problem? The text book I am using is Data Structures Using C++ Author: D.S. Malik Publisher: Course Technology. Please help I'm really confused on the assignment, I'm using this linked list below #include <iostream> #include <cstdlib> using namespace std; struct nodeType { int info; nodeType *link; }; void createList(nodeType*& first, nodeType*& last); void printList(nodeType*& first); void insertFront(nodeType*& first); void insertBack(nodeType*& last); void deleteFirst(nodeType*& first); void deleteLast(nodeType*& last, nodeType* first); int main() { nodeType *first, *last; int num; createList(first, last); int choice; while(true) { cout<<"1. Insert Front. 2. Insert Last. 3. Delete Front. 4. Delete Last. 5. Print List. 6. Exit. "; cout<<"Enter your choice: "; cin>>choice; switch(choice) { case 1: insertFront(first); break; case 2: insertBack(last); break; case 3: deleteFirst(first); break; case 4: deleteLast(last, first); break; case 5: printList(first); break; case 6: return 0; default: cout<<"Invalid menu option. Try again."<<endl; } } system("PAUSE"); return 0; } void createList(nodeType*& first, nodeType*& last) { int number; nodeType *newNode; first = NULL; last = NULL; cout<<"Enter an integer (-999 to stop): "; cin>>number; while (number != -999) { newNode = new nodeType; // create new node newNode->info = number; newNode->link = NULL; if (first == NULL) { first = newNode; last = newNode; } else { last->link = newNode; last = newNode; } cout<<"Enter an integer (-999 to stop): "; cin>>number; } // end of while-loop } // end of build list function void deleteFirst(nodeType*& first) { nodeType *temp; temp= first; first= temp->link; delete temp; return; } void deleteLast(nodeType*& last, nodeType* current) { nodeType *temp; while(current->link != NULL) { temp=current; current=current->link; } temp=last; current->link=NULL; delete temp; last = current; return; } void insertFront(nodeType*& front) { int num; cout<<" Enter the number to insert: "; cin>>num; nodeType *newNode = new nodeType; newNode->info=num; newNode->link= front; front= newNode; return; } void insertBack(nodeType*& last) { int num; cout<<" Enter the number to insert: "; cin>>num; nodeType *newNode = new nodeType; newNode->info=num; newNode->link= NULL; last->link= newNode; last = newNode; return; } void printList(nodeType*& first) { cout<<"Inside printList...printing linked list... "<<endl; nodeType *current; current = new nodeType; current = first; while (current != NULL) { cout << current->info << " "; current = current->link; } cout<<endl; } How would you solve this problem? The text book I am using is Data Structures Using C++ Author: D.S. Malik Publisher: Course Technology. Please help I'm really confused on the assignment, I'm using this linked list below #include <iostream> #include <cstdlib> using namespace std; struct nodeType { int info; nodeType *link; }; void createList(nodeType*& first, nodeType*& last); void printList(nodeType*& first); void insertFront(nodeType*& first); void insertBack(nodeType*& last); void deleteFirst(nodeType*& first); void deleteLast(nodeType*& last, nodeType* first); int main() { nodeType *first, *last; int num; createList(first, last); int choice; while(true) { cout<<"1. Insert Front. 2. Insert Last. 3. Delete Front. 4. Delete Last. 5. Print List. 6. Exit. "; cout<<"Enter your choice: "; cin>>choice; switch(choice) { case 1: insertFront(first); break; case 2: insertBack(last); break; case 3: deleteFirst(first); break; case 4: deleteLast(last, first); break; case 5: printList(first); break; case 6: return 0; default: cout<<"Invalid menu option. Try again."<<endl; } } system("PAUSE"); return 0; } void createList(nodeType*& first, nodeType*& last) { int number; nodeType *newNode; first = NULL; last = NULL; cout<<"Enter an integer (-999 to stop): "; cin>>number; while (number != -999) { newNode = new nodeType; // create new node newNode->info = number; newNode->link = NULL; if (first == NULL) { first = newNode; last = newNode; } else { last->link = newNode; last = newNode; } cout<<"Enter an integer (-999 to stop): "; cin>>number; } // end of while-loop } // end of build list function void deleteFirst(nodeType*& first) { nodeType *temp; temp= first; first= temp->link; delete temp; return; } void deleteLast(nodeType*& last, nodeType* current) { nodeType *temp; while(current->link != NULL) { temp=current; current=current->link; } temp=last; current->link=NULL; delete temp; last = current; return; } void insertFront(nodeType*& front) { int num; cout<<" Enter the number to insert: "; cin>>num; nodeType *newNode = new nodeType; newNode->info=num; newNode->link= front; front= newNode; return; } void insertBack(nodeType*& last) { int num; cout<<" Enter the number to insert: "; cin>>num; nodeType *newNode = new nodeType; newNode->info=num; newNode->link= NULL; last->link= newNode; last = newNode; return; } void printList(nodeType*& first) { cout<<"Inside printList...printing linked list... "<<endl; nodeType *current; current = new nodeType; current = first; while (current != NULL) { cout << current->info << " "; current = current->link; } cout<<endl; } Doubly Linked List (Page 310 ordered Doubly Linked List Note-Start with a new C program/project. Functions for Doubly Linked List Insert See page 316 o This section, in the book, shows class/object implementation o You are not required to implement as a class/object o You are not required to use the "count" (inked list counter) o Must implement the 4 cases (1, 2, 3 and 4) o Run the code to show it will insert in all four cases Display the list (first to last) Reverse print the list (ast to first Delete Page 318 o This section, in the book, shows class/object implementation o You are not required to implement as a class/object o You are not required to use the count" (linked list counter) o Must implement the 4 cases (1, 2, 3 and 4) o Run the code to show it will delete in all four cases OVER Please read Chapter 6 Recursion for Thursday's Class
Explanation / Answer
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct Node
{
int data;
Node *next;
};
Node *tail=NULL;
Node* Insert_atHead(Node *head, int data)
{
Node *temp=new Node;
temp->data=data;
temp->next=head;
head=temp;
return head;
}
Node* Insert_atTail(Node *head, int data)
{
Node *tail=head;
if(tail==NULL)
{
Node *temp = new Node;
temp->data=data;
temp->next=NULL;
head=temp;
return head;
}
while(tail!= NULL)
{
if(tail->next==NULL)
{
Node *temp=new Node;
temp->data=data;
temp->next=NULL;
tail->next=temp;
return tail;
}
else
{
tail=tail->next;
}
}
}
Node *Insert_atPosition(Node *head, int data, int position)
{
int i=0;
int j=position-1;
if(position==0)
{
Node *temp = new Node;
temp->data=data;
temp->next=head;
head=temp;
return head;
}
else
{
Node *temp=head;
while(i<j)
{
temp=temp->next;
i++;
}
Node *temp1 = new Node;
temp1->data=data;
temp1->next=temp->next;
temp->next=temp1;
return head;
}
return head;
}
Node* Delete(Node *head, int position)
{
Node *temp=head;
int i=1;
int j=position;
if(j==0)
{
head=head->next;
return head;
}
Node *temp1 = new Node;
while(j>0)
{
temp1=temp;
temp=temp->next;
j--;
}
temp1->next=temp->next;
delete temp;
return head;
}
int GetNode(Node *head,int positionFromTail)
{
Node *tail=head;
int l=0;
while(tail->next!=NULL)
{
tail=tail->next;
l++;
}
int i=(l-positionFromTail);
Node *temp=head;
while(i>0)
{
temp=temp->next;
i--;
}
return temp->data;
}
int Size_ofLinkedList(Node *head)
{
int S=0;
Node *temp = head;
while(temp!= NULL)
{
S++;
temp=temp->next;
}
return S;
}
Node *Reverse_LinkedList(Node *head)
{
Node *temp1 = head;
Node *tail = NULL;
Node *head1= new Node;
while(head!=NULL)
{
head1=head;
temp1=temp1->next;
head->next=tail;
tail=head;
head=temp1;
}
head=head1;
}
int CompareLists(Node *headA, Node* headB)
{
Node *tempA=headA;
Node *tempB=headB;
while(tempA!=NULL && tempB!=NULL)
{
if(tempA->data==tempB->data)
{
tempA=tempA->next;
tempB=tempB->next;
}
else
{
return 0;
}
}
if(tempA==NULL && tempB==NULL)
{
return 1;
}
else
{
return 0;
}
}
int FindMergeNode(Node *headA, Node *headB)
{
Node *tempA=headA;
Node *tempB=headB;
int m=0;
int n=0;;
while(tempA!=NULL)
{
tempA=tempA->next;
m++;
}
while(tempB!=NULL)
{
tempB=tempB->next;
n++;
}
tempA=headA;
tempB=headB;
int Data;
if(m>n)
{
int p=m-n;
while(p>0)
{
tempA=tempA->next;
p--;
}
while(tempA!=tempB)
{
tempA=tempA->next;
tempB=tempB->next;
}
Data=tempA->data;
}
else
{
int p = n-m;
while(p>0)
{
tempB=tempB->next;
p--;
}
while(tempA!=tempB)
{
tempA=tempA->next;
tempB=tempB->next;
}
Data=tempA->data;
}
return Data;
}
Node* RemoveDuplicates(Node *head)
{
Node *temp=head;
Node *temp1 = new Node;
while(temp->next!=NULL)
{
if(temp->data!=(temp->next)->data)
{
temp=temp->next;
}
else
{
temp1=temp->next;
temp->next=temp1->next;
delete temp1;
}
}
return head;
}
Node* MergeLists(Node *headA, Node* headB)
{
Node *temp = new Node;
Node *head = new Node;
if(headA==NULL || headB==NULL)
{
if(headA==NULL)
{
head=headB;
}
else
{
head=headA;
}
return head;
}
if(headA->data<=headB->data)
{
temp=headA;
headA=headA->next;
}
else
{
temp=headB;
headB=headB->next;
}
head=temp;
while(headA!=NULL && headB!=NULL)
{
if(headA->data<=headB->data)
{
temp->next=headA;
temp=temp->next;
headA=headA->next;
}
else
{
temp->next=headB;
temp=temp->next;
headB=headB->next;
}
}
if(headA==NULL && headB!=NULL)
{
temp->next=headB;
}
if(headA!=NULL && headB==NULL)
{
temp->next=headA;
}
return head;
}
int HasCycle(Node* head)
{
Node *temp1=head;
Node *temp2=head;
int X=0;
if(head==NULL || head->next==NULL)
{
X=0;
}
else
{
temp1=temp1->next;
temp2=(temp2->next)->next;
while(temp1!=temp2)
{
if(temp2->next==NULL || (temp2->next)->next==NULL)
{
X=0;
break;
}
temp1=temp1->next;
temp2=(temp2->next)->next;
X=1;
}
}
if(X==0)
{
return 0;
}
else
{
return 1;
}
}
void Print(Node *head)
{
Node *temp = head;
while(temp!= NULL)
{
cout<<temp->data<< " --> ";
temp=temp->next;
}
cout<< "NULL";
}
void ReversePrint(Node *head)
{
Node *temp1 = head;
Node *tail = NULL;
Node *head1= new Node;
if(head!=NULL)
{
while(head!=NULL)
{
head1=head;
temp1=temp1->next;
head->next=tail;
tail=head;
head=temp1;
}
Node *temp=head1;
while(temp!= NULL)
{
cout<<temp->data<< " ";
temp=temp->next;
}
}
}
int main() {
int data;
Node *head=NULL;
int H;
cout<< "No. of Node Insertion at Head: ";
cin>>H;
while(H>0)
{
cin>>data;
head=Insert_atHead(head, data);
H--;
}
int T;
cout<< "No. of Node Insertion at Tail: ";
cin>>T;
while(T>0)
{
cin>>data;
Insert_atTail(head,data);
T--;
}
int P;
cout<< " ";
cout<< "Add Node at Position: ";
cin>>P;
cout<< " ";
cout<< "data: ";
cin>>data;
Insert_atPosition(head,data,P);
cout<< " ";
cout<< "Delete Node at Position: ";
cin>>P;
Delete(head,P);
cout<< " ";
Print(head);
Reverse_LinkedList(head);
head=tail;
cout<< " ";
Print(head);
cout<< " ";
cout<< "Size of LinkedList: "<<Size_ofLinkedList(head);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.