We use Virtual Studio 2019 C++: All Assignments beginning from the fourth are just for help The on im doing is the first one. (Sorted Linked lists)

Sorted Linked Lists

Use the implementation of Sorted linked list we used in class (sortedList.h) and make the following changes.

We implemented the list as a template. Change the implementation for datatype string.

When we implemented, the items were being included in ascending order.Change the list to accommodate the items in descending order.

You can create Sorted Linked List for Strings and do not use a Template one. So you need to update putItem, findItem and deleteItem functions to reflect the fact that the ItemType (here the string) is included in descending order. (40 points)

The Link list should be a list of strings. Strings should be included in the list in descending order of the alphabet.

So for example if you are inserting the following strings "cart ", "mart ", "dart ", "part", "art"

The strings should be included in descending order of the alphabet which is the following order

part -> mart ->dart-> cart-> art

where the listData or header should point to 'part' which is the highest string in descending order.

Add the following functions besides the regular ones:

public stringfindWordEndIn(char endAlphabet)(15 points)

// Here the list applies only for strings. The function checks in the list for the first word in the list which ends with a particular alphabet and returns the string. For example if char 'w' is passed in it should return the first word if there is any word in the list which ends in w like saw or slaw etc. If there are more than one word you can stop with the first one and return that word. Don't need to search anymore. If no word is found it should return the string "Not Found".

public void displayListBackwards() ( 25 points) // prints the list in ascending order of alphabets

// displays the words in the reverse alphabetic order. So for example if the list is

part -> mart ->dart-> cart-> art

//it should print out the list in reverse order.

art cart dart mart part

You can add any other constructors or methods if needed to implement this. The solution has to be done non recursively. There is an easy recursive solution which we will look at when we do recursion later. But here you need to see how we can do using a non recursive solution.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Assignment 4:

In this assignment, we will create two variants of the classes from Assignment 3; SortedArrayBufferNoDups and SortedArrayBufferWithDups.As the name implies, the first class is a sorted array and does not allow the insertion of duplicate values, while the second one does.The SortedArrayBufferNoDups class should look like the ArrayBufferNoDups class in Assignment 2. Only the insert operation has to change. Insert has to insert in order.Here there is only one remove function which is stableRemove that has to be slightly altered so that you don't have to go until the end of the array to find the integer. You can stop when you have reached a value greater than the value being passed in. For example if your array contains integers [1,3,5,7,9] and you are asked to remove integer 4, you can stop once you reach 5 as you know 4 cannot be found now. Same applies to the find function.

The SortedArrayBufferWithDups class should also look like the class in SortedArrayBufferWithNoDups class in previous section.This time, change the insert function that allows duplicates but needed to be inserted in order.Now implement the findAll and stableRemoveAll.The findAll function should return an int with the number of elements that have the same value as the target value, while the stableRemoveAll function should remove all copies of the target value.Have the stableRemoveAll function return an int with the number of values that were actually removed.

Here findAll and stableRemoveAll become easier. For findAll once you find the first one you need to look at the next element. If it's the same keep going until you find an element which is a greater value and you stop searching. And Similarly for stableRemoveAll as you know the number of occurrences and now if you find the locationOf the first one you can stop looking and remove starting from that index to the number of occurrences. So for example if you have an integer array [1,3,5,5,5,7,9] and you are asked to remove 5, location of first 5 is 2 and number of occurrences for 5 is 3. So you need to remove from index 2 to 4(3 occurrences). For this assignment, like assignment 3 have the constructor take an integer argument for the BUFFER_SIZE and do not use a default.

-------------------------------------------------------------

Assignment 3:

Arrays Buffers with and Without Duplicates This assignment assumes you have a mastered assignment 1.If you remember, the BufferArray class in Assignment 2 had methods for insert, find, remove, stableRemove, and display, as well as a private "helper" function called locationOf.

In this assignment, we will create two variants of the BufferArray class; ArrayBufferNoDups and ArrayBufferWithDups.As the name implies, the first class does not allow the insertion of duplicate values, while the second one does.The ArrayBufferNoDups class should look like the BufferArray class in Assignment 2.

Only the insert operation has to change.

Both remove functions should assume that there is never more than one copy of a value.

For this assignment I would also like the distinction between the two remove functions to be more clear.So please rename the remove function to fastRemove and keep the other one with the same name stableRemove.

The ArrayBufferWithDups class should also look like the class in BufferArray class in Assignment 2.

This time, do not change the insert function, and implement both remove functions as for the NoDups case.

But, in addition, add three new methods, called findAll, fastRemoveAll, and stableRemoveAll.

oThe findAll function should return an int with the number of elements that have the same value as the target value,

owhile the two removeAll functions should remove all copies of the target value.Have both removeAll functions return an int with the number of values that were actually removed.

For this assignment, we will make two more changes.First, omit the BUFFER_SIZE constant, and instead have the constructor take an integer argument for the size.

-------------------------------------------------------------------------------------------------------------------

Assignment 2:

This assignment is really about strengthening your programming skills for the kinds of things we will be doing a lot in this class. A buffer is a place where you can put stuff. I key feature of a buffer is the space is reserved before anything is actually being stored. So there are two concepts of size. The first is how much space does the buffer have, and the second is how much of that space is actually being used to hold values that have been put into the buffer. You can think of it as a classroom with seats. Before any students come to class, the room has 25 seats, but they are all empty. When class starts, 14 students have entered the room and are sitting in seats. So there are 14 students, but 25 places for students. If I then say, I want to know the name of the student in each seat, will I hear 25 names, or 14 names. The same situation applies when I say, print the values in the buffer. I should see only as many numbers as were added to the buffer.

We had already started on this assignment in class. So based on the requirements given you can use the same functions, modify the existing functions or add new functions.

1. Create a C++ class called BufferArray. It will have an array to hold integers and a variable, called numberOfElements, that records how many values are being stored in the array.

2. Give the BufferArray an integer constant called BUFFER_SIZE and initialize it to 8.

3. Give the BufferArray an array of ints, called intArray, and initialize it to be an array that can hold BUFFER_SIZE ints.

4. Give the BufferArray a variable called numberOfElements and initialize it to 0.

5. Make BUFFER_SIZE, intArray, and numberOfElements private.

6. Give the BufferArray a public method called insert() that takes an integer argument, called value, and returns a Boolean. For starters, just have it return false.

7. Give the BufferArray a public method called remove() that takes an integer argument, called value, and returns a Boolean. For starters, just have it return false.

8. Give the BufferArray a public method called find() that takes an integer argument, called target, and returns a Boolean. For starters, just have it return false.

9. Give the BufferArray a public method called display() that takes no arguments and returns nothing.

10. Give the BufferArray a private method called locationOf() that takes an integer argument, called target, and returns an integer.

11. Write a test driver main for your BufferArray class that tests the insert, display, find, and remove methods. Make the tests fairly thorough.

12. Have the insert method add the value argument to the next available space at the end of the array and increment the numberOfElements variable. Then it should return true. If the intArray is already full, it should just return false without doing anything.

13. Have the display() method print all the value in the BufferArray to the console, one after the other, on a single line. The values should be separated by commas, but there should be no extra comma and the beginning or end. After printing the array, it should advance to the next line. If the BufferArray is empty it should print nothing, but still advance to the next line.

14. Have the locationOf method visit every value in the array. If it finds a value that matches the target argument, it should return it location in the array (its index). If no values in the array match the target, it should return -1.

15. Have the find method look for the value in the intArray. If a value that was put in the intArray matches the argument target, it should return the value true. If no values that were place in the intArray matches the target, it should return false. Use the locationOf method to implement this behavior.

16. Have the remove method remove the first array element that matches the target. To do this, it should replace it with the last value in the array, and decrement the numberOfElements count. Then it should return true. If no elements match the target value, it should just return false.

17. Give the BufferArray class one more method, called stableRemove. Have the stableRemove method remove the first array element that matches the target. To do this, it should shift every array value above that location down one position in the array, and decrement the numberOfElements count. Then it should return true. If no elements match the target value, it should just return false. (In data structures, "stable" means that the order is not changed.)