C++ US?NG NODE A intList of elements of type integer is a finite sequence of ele

ID: 3740547 • Letter: C

Question

C++ US?NG NODE

A intList of elements of type integer is a finite sequence of elements of integer together with the following operations:

*Construct the list, leaving it empty.

*Determine whether the list is empty or not.

*Determine whether the list is full or not.

*Find the size of the list.

*Clear the list to make it empty.

*Insert an entry at a specified position of the list.

*Remove an entry from a specified position in the list.

*Retrieve the entry from a specified position in the list.

*Append

*insertToFront

*Merge two lists

*Intersection of two lists

Declaration of intList class:

class intList{

private:

Node *head;

int sz; //To keep track of how many items are in the list

public:

intList(); //The intList has been created and is initialized to be empty.

void clear();// All intList entries have been removed; the List is empty.

bool isEmpty() const; // The function returns true or false according to whether the List is empty or not.

bool isFull() const; //The function returns true or false according to whether the List is full or not.

int size() const; //The function returns the number of entries in the List.

bool retrieve(int position, int &x) const;

bool remove(int position, int &x);

bool remove(int val); //removes the node containing val as its data.

bool insert(int position, const int &x);

void print()const;

void insertLast(int val);

void insertFirst(int val);

int indexOf(int val)const;

intList interSection(const intList &)const;

intList union(const intList &)const;

};

A list is considered as having no fixed length: it can grow and shrink as additions or deletions are made anywhere on the list.

When an insertion is done the new value does not replace an existing value. When a new value is inserted at position i, the previous values all remain unchanged on the list but those which appeared at position i or later will now have new positions on the list.

Similarly, a deletion removes a value from the list but does not leave a gap: the remaining values assume new positions.

Operations that access entries of a list.

To find an entry in a list, we use an integer that gives its position within the list.

We shall number the positions in a list so that the first entry in the list has position 0, the second position 1, and so on. First, if we insert an entry at a particular position, then the position numbers of all later entries increase by 1. If we remove an entry, then the positions of all following entries decrease by 1.

bool insert(int position, int item);

If the List is not full and 0<= position <=n, where n is the number of entries in the List, the function succeeds: Any entry formerly at position and all later entries have their position numbers increased by 1, and x is inserted at position in the List. Returns: TRUE if insertion was successful or FALSE if the insertion failed.

Note that insert allows position ==n, since it is allowed to insert an entry after the last entry of the list.

bool remove(int position, int &x);

If 0<= position < n, where n is the number of entries in the List, the function succeeds: The entry at position is removed from the List, and all later entries have their position numbers decreased by 1. The parameter x records a copy of the entry formerly at position.

Returns: TRUE if deletion was successful or FALSE if the deletion failed.

bool retrieve(int position, int &x) const;

If 0_<=position < n, where n is the number of entries in the List, the function succeeds: The entry at position is copied to x; all List entries remain unchanged.

Returns: TRUE if retrieve was successful or FALSE if the search failed.

Given the methods for lists described above, implement the intList class, and make sure that following main function executes correctly.

void main()

{

intList myList; // Instantiate a list object

cout << "Simple List Demonstration ";

cout << "(List implemented as an Array";

cout << "Create a list and add a few tasks to the list";

myList.insert(0,12);//list is {12}

myList.insert(0, 4);//{4,12}

myList.insert(0, 7);//{7,4,12}

myList.insert(2, 34);//list becomes {7,4,34,12}

myList.insert(myList.size(), 85);//list becomes {7,4,34,12,85}

// Show what is in the list

myList.print()

// Test the list length function

cout << " List now contains " << myList.size() << "items. ";

// Test delete function

cout << "Testing delete of last item in list. ";

int val;

if (myList.remove(myList.size() - 1, val) == true)

cout << "delete operation was successfull:" << val << endl;

myList.print();

// Test delete function

cout << "Testing delete of first item in list. ";

if (myList.remove(0, val) == true)

cout << "delete operation was successfull:" << val << endl;

myList.print();

// Test delete function with a known failure argument

cout << "Testing failure in delete function. ";

if (myList.remove(10,val)==true)

cout <<" This was not expected. should not have been able to delete. ";

else

cout << "Unable to locate item to delete. ";

// Test retrieve ( failure)

cout << "Testing function. item at position 22 ";

if (myList.retrieve(22, val) == true)

cout << "retrieve result: val = " << val << " ";

else

cout << " result: Unable to locate item in list ";

// Test retrieve ( success)

cout << "Testing function. item at first position ";

if (myList.retrieve(0,val)==true)

cout << "retrieve result: val = " << val << " ";

else

cout << " result: Unable to locate item in list ";

}

Explanation / Answer

#include <iostream>

using namespace std;

struct node
{
int data;
node *next;
};

class intList{

private:

Node *head,*tail;

int sz=0; //To keep track of how many items are in the list
int max=10;

public:

intList(); //The intList has been created and is initialized to be empty.

void clear();// All intList entries have been removed; the List is empty.

bool isEmpty() const; // The function returns true or false according to whether the List is empty or not.

bool isFull() const; //The function returns true or false according to whether the List is full or not.

int size() const; //The function returns the number of entries in the List.

bool retrieve(int position, int &x) const;

bool remove(int position, int &x);

bool remove(int val); //removes the node containing val as its data.

bool insert(int position, const int &x);

void print(node*)const;

void insertLast(int val);

void insertFirst(int val);

int indexOf(int val)const;

node* create_node(int);

};

intList::intList()
{

head = NULL;
tail = NULL;
}

node *intList::create_node(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->info = value;
temp->next = NULL;
return temp;
}
}

void intList::clear()
{
head=NULL;
tail=NULL:
}

bool intList::isEmpty() const
{

if(head == NULL)
{
return true;
}

else
{
return false;
}

}

bool intList::isFull() const
{
sz=this->size();
if(sz==max)
return true;
else
return false;
}

int intList::size() const
{
count = 0;
iterator = head;
while(iterator != 0)
count++;
iterator = iterator.next;
return count;
}

bool intList::retrieve(int position, int &x) const
{

struct Node* current, head;
current = head;
int count = 0; /* the index of the node we're currently
looking at */
while (current != NULL)
{
if (count == position && count->data==x)
return(current->data);
count++;
current = current->next;
}

}

bool intList::remove(int position, int &x)
{
Node *head_ref;

if (*head_ref == NULL)
{
return;
}

//temp to store head
Node *temp = *head_ref;
//Delete head node
if (position == 0)
{
*head_ref = temp->next;
free(temp);
return;
}
//store previous of to be deleted node
for (int i=0; temp!=NULL && i<position-1; i++)
{
temp = temp->next;
}
if (temp == NULL || temp->next == NULL)
{
return;
}
//delete node at pos (next of pos-1)
struct LLNode *next = temp->next->next;
free(temp->next);
temp->next = next;
}

bool intList::remove(int val)
{
Node* current = head;
Node* next = current;
while(current != NULL) {
if(current->data == val) { // if match
break; // break out of while
}
else {
cout << "Value " << current->data << " does not match " << val << ". ";
next = current; // save in case
current = current->next; // go to next value
}
} // end while
if(current == NULL) { // if we reached end of list
cout << "Can't remove value: no match found. "; // no match, cant remove
} else { // found match
cout << "Deleting: " << current << " ";
delete current;
current = next->next; // current is updated
}
}

bool intList::insert(int position, const int &x)
{
struct node *temp, *s, *ptr;
temp = create_node(x);
int counter=0;
int i;

s = start;
while (s != NULL)
{
s = s->next;
counter++;
}
if (position == 1)
{
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
ptr = start;
start = temp;
start->next = ptr;
}
}
else if (position > 1 && position <= counter)
{
s = start;
for (i = 1; i < pos; i++)
{
ptr = s;
s = s->next;
}
ptr->next = temp;
temp->next = s;
}
else
{
cout<<"Positon out of range"<<endl;
}
}

void intList::print(node *head)const
{
while (head!=NULL){
cout<< head->data <<endl;
head=head->next;
}
}

void intList::insertLast(int val)
{

struct node *temp, *s;
temp = create_node(val);
s = start;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;

}

void intList:: insertFirst(int val)
{

struct node *temp, *p;
temp = create_node(val);
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
p = start;
start = temp;
start->next = p;
}
}

int intList::indexOf(int val)const
{

Node* tempNode = head;
int count = 0;
while(tempNode != NULL)
{
if (head->data==val)
{
break;
}

++count;
tempNode = tempNode->next;
}
return count;
}

void main()

{

intList myList; // Instantiate a list object

cout << "Simple List Demonstration ";

cout << "(List implemented as an Array";

cout << "Create a list and add a few tasks to the list";

myList.insert(0,12);//list is {12}

myList.insert(0, 4);//{4,12}

myList.insert(0, 7);//{7,4,12}

myList.insert(2, 34);//list becomes {7,4,34,12}

myList.insert(myList.size(), 85);//list becomes {7,4,34,12,85}

// Show what is in the list

myList.print()

// Test the list length function

cout << " List now contains " << myList.size() << "items. ";

// Test delete function

cout << "Testing delete of last item in list. ";

int val;

if (myList.remove(myList.size() - 1, val) == true)

cout << "delete operation was successfull:" << val << endl;

myList.print();

// Test delete function

cout << "Testing delete of first item in list. ";

if (myList.remove(0, val) == true)

cout << "delete operation was successfull:" << val << endl;

myList.print();

// Test delete function with a known failure argument

cout << "Testing failure in delete function. ";

if (myList.remove(10,val)==true)

cout <<" This was not expected. should not have been able to delete. ";

else

cout << "Unable to locate item to delete. ";

// Test retrieve ( failure)

cout << "Testing function. item at position 22 ";

if (myList.retrieve(22, val) == true)

cout << "retrieve result: val = " << val << " ";

else

cout << " result: Unable to locate item in list ";

// Test retrieve ( success)

cout << "Testing function. item at first position ";

if (myList.retrieve(0,val)==true)

cout << "retrieve result: val = " << val << " ";

else

cout << " result: Unable to locate item in list ";

}

Navigate

C++ UNSORTED LIST This a C++ program related to Unsorted list as a linked struct

C++ USE GETLINE. For this lab you are to use the STL stack which you can obtain

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

C++ US?NG NODE A intList of elements of type integer is a finite sequence of ele

Question

Explanation / Answer

Related Questions

Navigate