这是一篇美国的数据结构C++代写

Introduction

In lecture, we discussed Skip Lists. In this project, we’re going to implement one. You will discover that there are some details you uncover as you work on this that aren’t apparent when you analyze the concept of a Skip List.

Getting Started

Before you begin work on this project, there are a couple of chores you’ll need to complete on your ICS 46 VM to get it set up to proceed.

Refreshing your ICS 46 VM environment

Even if you previously downloaded your ICS 46 VM, you will probably need to refresh its environment before proceeding with this project. Log into your VM and issue the command ics46 version to see what version of the ICS 46 environment you currently have stored on your Note, in particular, the timestamp; if you see a version with a timestamp older than the one listed below, you’ll want to refresh your environment by running the command ics46 refresh to download the latest one before you proceed with this project.

If you’re unable to get outgoing network access to work on the ICS 46 VM — something that afflicts a handful of students each quarter — then the ics46 refresh command won’t work, but an alternative approach is to download the latest environment from the link in a previous project description, then to upload the file on to your ICS 46 VM using SCP. (See the Project #0 write-up for more details on using SCP.) Once the file is on your VM, you can run the command

ics46 refresh_local NAME_OF_ENVIRONMENT_FILE, replacing

NAME_OF_ENVIRONMENT_FILE with the name of the file you uploaded; note that you’d need

to be in the same directory where the file is when you run the command.

Creating your project directory on your ICS 46 VM

A project template has been created specifically for this project, containing a similar structure to the basic template you saw in Projects #0 and #1.

Decide on a name for your project directory, then issue the command ics46 start YOUR_CHOSEN_PROJECT_NAME project2 to create your new project directory using the project1 template. (For example, if you wanted to call your project directory proj2, you would issue the command ics46 start proj2 project2 to create it.) Now you’re ready to proceed!

Requirements

• Fill in SkipList.hpp

○ Your implementation must be a linked structure.

○ Your implementation must fit the interface given.

○ Your implementation must be templated

■ An implementation of SkipList that does not properly template may cause

you to get a zero on this assignment. Do not assume that working for unsigned is sufficient, despite those being the only cases in the provided test cases.

■ Your project needs to be able to handle Key items of any type that have the < operator defined, a default constructor, an assignment operator, and for which the flipCoin() function is defined. For purposes of the assignment, unsigned integers and std::string are the only two such types.

■ No, really; pay attention to that warning. Students may end up with zeroes for this project if their code is not properly templated, regardless of other considerations.

○ When you insert a key/value pair into your Skip List and flip a coin to determine higher levels, use the function flipCoin. This is described at the top of SkipList.hpp This returns true if the coin flip returned heads (meaning add a layer).

○ If the insertion of an element would result in more than 3 * ceiling of (log n) layers, where n is the number of elements in the Skip List (including this one being inserted), stop the insertion procedure. The exception is for the first 16 elements being inserted, in which case, the maximum height allowed is fixed at 12.The library cmath has a function for logarithms and ceiling, and you may use this for the assignment.

○ Please note: the project will not build successfully until you have at least stubbed code for the public member functions.

• Your implementation does not have to be the most efficient thing ever, but it cannot be “too slow.” In general, any test case that takes over a minute on the grader’s computer may be deemed a wrong answer, even if it will later return a correct one.

You are prohibited from using any standard library container classes. Using a standard library container, including std::vector, in implementing your SkipList will be treated as a serious academic integrity violation. The only exception to this is in the function allKeysInOrder().However, in that function, you must create the vector during your implementation.

Deliverables

After using the gather script in your project directory to gather up your C++ source and header files into a single project2.tar.gz file (as you did in previous assignments), submit that file (and only that file) to Checkmate. Refer back to Project #0 if you need instructions on how to do that.

You will submit your project via Checkmate. Keep in mind that you’re responsible for submitting the version of the project that you want graded. We won’t regrade a project simply because you submitted the wrong version accidentally. (It’s not a bad idea to look at the contents of your tarball before submitting it; see Project #0 for instructions on how to do that.)

Can I submit after the deadline?

Yes, it is possible, subject to the late work policy for this course, which is described in the section titled Late work in the course reference and syllabus.

Grading

The grade that will be returned to you is based solely on correctness : we will run some number of test cases for your code and, based on how many and which ones you get correct, you will earn some number of points between 0 and 6 (inclusive, and might not be integer-valued).Each is worth some number of points and is graded based on whether or not your code correctly behaves according to the test case, and if so, what it is. If it is determined that your program does not make an attempt to solve the problem at hand, you will not get these points,regardless of the result from testing. The tests will look a lot like the tests in your Google Test starting directory for this assignment; if you pass those, you’re off to a good start, but it’s not a guarantee.

If we review your code and find your style to be sufficiently bad, we reserve the right to deduct points based on this, proportional to how bad the style is. If we do so, we will alert you to both the penalty and the reason. Review project 1’s style guidelines for an overview.

Academic Integrity

Please review the syllabus for academic integrity expectations for this class. These rules apply even for projects where I don’t give you an explicit reminder. As a reminder, the following are examples of behavior that is explicitly prohibited. This is not a complete list of prohibited behavior:

• Searching online for an implementation of a Skip List
• Looking online for help or “ideas” for writing a Skip List in any forum where a potential respondent might not be subject to UCI’s academic integrity policy. Of course, if you find help in an allowable resource (such as one of the textbooks for this class), you may use material from them, but you must cite this in comments.

• “Hiding” the fact that you are not implementing your own Skip List, such as by having a std::vector in your implementation code, other than one created in the function allKeysInOrder().