Please comment each case number within the code so that I know where the case fu
ID: 3745798 • Letter: P
Question
Please comment each case number within the code so that I know where the case function is and what is happening.
CODE:
#include <iostream>
using namespace std;
struct node {
int number;
node* next;
};
bool isNull(node*& first);
int menu();
void insertFirst(node*& first, node*& last, int number);
void insert(node*& first, node*& last, int number);
void remove(node*& first, node*& last);
void printList(node* current);
bool isNull(node*& first)
{
// if the list is empty
if (first == NULL)
return true;
// if the list is not empty
else
return false;
}
int menu()
{
int selection;
cout << "Menu Selection ";
cout << "1. Add an item. ";
cout << "2. Remove an item. ";
cout << "3. Show list. ";
cout << "4. Exit system. ";
cin >> selection;
return selection;
}
int getLength(node* first)
{
node* trav = first;
int count = 0;
// loop untill list ends
while (trav)
{
count++;
// go to next node
trav = trav->next;
}
return count;
}
void insertFirst(node*& first, node*& last, int number)
{
// create a new node
node* temp = new node;
// The linked list current state is NULL (empty), A node with a new number should be the only one
// and be first in the list.
if (first == NULL)
temp->number = 1;
else
temp->number = number;
// make temp point to current first node of the list
temp->next = first;
// make temp as the new first node
first = temp;
// if the list was empty
if (last == NULL)
last = temp;
}
// check if x is the smaller than smallest number in list
bool ifSmallest(node* first, int x)
{
node* trav = first;
// loop untill list ends
while (trav)
{
// if x is not the smallest
if (trav->number < x)
return false;
// go to next node
trav = trav->next;
}
return true;
}
// check if x is the larger than largest number in list
bool ifLargest(node* first, int x)
{
node* trav = first;
// loop untill list ends
while (trav)
{
// if x is not the largest
if (trav->number > x)
return false;
// go to next node
trav = trav->next;
}
return true;
}
void insert(node*& first, node*& last, int number)
{
if (isNull(first))
insertFirst(first, last, number);
// if number is smaller than the smallest number in the list
else if (ifSmallest(first, number))
insertFirst(first, last, number);
// if number is larger than the largest number in the list
// node goes at the last of the list
else if (ifLargest(first, number))
{
node* temp = new node;
temp->number = number;
temp->next = NULL;
last->next = temp;
last = temp;
}
// The new number should be inserted inserted in the middle of the link list.
else {
// get the length of the list
int len = getLength(first);
node* trav = first;
int i;
// go to the node before the middle node
for (i = 0; i < len - 2; i++)
trav = trav->next;
// adjust the pointer
node* temp = new node;
temp->number = number;
temp->next = trav->next;
trav->next = temp;
}
}
void remove(node*& first, node*& last)
{
if (isNull(first))
cout << "The list is already empty. ";
else if (first == last)
{
delete first;
first == NULL;
last == NULL;
}
else {
node* temp = first;
first = first->next;
delete temp;
}
}
void printList(node* current)
{
if (isNull(current))
cout << "The list is empty ";
else {
cout << "The list contatins: ";
while (current != NULL)
{
cout << current->number << endl;
current = current->next;
}
}
}
int main()
{
node* first = NULL;
node* last = NULL;
int selection;
int number;
do {
selection = menu();
switch (selection)
{
case 1:
cout << "Please enter a selection number: ";
cin >> number;
insert(first, last, number);
break;
case 2:
remove(first, last);
break;
case 3:
printList(first);
break;
case 4:
exit(0);
default:
cout << "System exit ";
}
} while (selection != '4');
return 0;
}
Explanation / Answer
#include <iostream>
using namespace std;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
struct node *head = NULL;
struct node *last = NULL;
struct node *now = NULL;
//is list empty
bool isEmpty() {
return head == NULL;
}
int length() {
int length = 0;
struct node *now;
for(now = head; now != NULL; now = now->next){
length++;
}
return length;
}
//insert at the first position
void insert_At_First_Position(int key, int data) {
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
//make it the last
last = link;
} else {
//update first prev
head->prev = link;
}
link->next = head;
//point first to new first
head = link;
}
//insert at the last location
void insertLast(int key, int data) {
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()) {
last = link;
} else {
//make a new last
last->next = link;
//mark old last as previous to the new last
link->prev = last;
}
last = link;
}
//delete first item
struct node* delete_first_node() {
//save reference to first link
struct node *tempLink = head;
if(head->next == NULL){
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
return tempLink;
}
//delete link at the last location
struct node* delete_last_node() {
//save reference to last link
struct node *tempLink = last;
if(head->next == NULL) {
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
return tempLink;
}
//delete a link with given key
struct node* delete_avl(int key) {
struct node* now = head;
struct node* previous = NULL;
if(head == NULL) {
return NULL;
}
while(now->key != key) {
//if it is last node
if(now->next == NULL) {
return NULL;
} else {
//store reference to current link
previous = now;
now = now->next;
}
}
if(now == head) {
// point next to the previous head as the new head
head = head->next;
} else {
now->prev->next = now->next;
}
if(now == last) {
last = now->prev;
} else {
now->next->prev = now->prev;
}
return now;
}
bool insertAfter(int key, int newKey, int data) {
struct node *now = head;
if(head == NULL) {
return false;
}
while(now->key != key) {
if(now->next == NULL) {
return false;
} else {
now = now->next;
}
}
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = newKey;
newLink->data = data;
if(now == last) {
newLink->next = NULL;
last = newLink;
} else {
newLink->next = now->next;
now->next->prev = newLink;
}
newLink->prev = now;
now->next = newLink;
return true;
}
//display the list in from first to last
void display_list() {
//start from the beginning
struct node *ptr = head;
//navigate till the end of the list
printf(" [ ");
while(ptr != NULL) {
printf("(%dth position and data is %d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//reverse of the list
void reverse_doubly_linked_list() {
//start from the last
struct node *ptr = last;
printf(" [ ");
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
//move previous
ptr = ptr ->prev;
}
}
int main() {
insert_At_First_Position(1,100);
insert_At_First_Position(2,10);
insert_At_First_Position(3,35);
insert_At_First_Position(4,9);
insert_At_First_Position(5,50);
insert_At_First_Position(6,96);
printf(" List (First to Last): ");
display_list();
printf(" ");
printf(" List (reverse): ");
reverse_doubly_linked_list();
printf(" After deleting the first node the list will look like: ");
delete_first_node();
display_list();
printf(" After deleting the last node the list will look like: ");
delete_last_node();
display_list();
printf(" List , insert after 4th place : ");
insertAfter(4,9, 12);
display_list();
printf(" List , delete after 4th place : ");
delete_avl(8);
display_list();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.