本次北美CS代写主要内容是C++数据结构相关
CSE 332: Spring 2021 Exam Assignment (Pandemic Exam Replacement)
Assigned: 4/14/2021 Due: 4/21/2021 (11:59 PM) Percent of final grade: 14%
In place of an in-person exam, this assignment is designed to be a cumulative review of concepts covered so far this semester. Topics covered will be:
- Pointers and pointer arithmetic
- Dynamic memory management
- Copy control
- Design of the STL
Notes on Academic Integrity and getting help on the assignment: This is an individual assignment and academic integrity checks will be made.
Resources you may use to complete the exam include: the textbooks, slides, lecture videos, recitation videos, C++ reference pages, and other online C++ resources.
Resources you may not use to complete the exam include: any solutions found online, your peers or your peers solutions. All submitted work should be your own solution and all code should be designed and written by you.
Extensions and late policy for the exam: I will not give any extensions on the exam. You may submit the exam late up to 4 days. Any late submissions will be graded with an automatic 20% deduction. The way this will work is, any assignments submitted before the deadline will be graded without penalty. Any exams submitted after the deadline will be graded with an automatic 20% deduction. The deduction will be the same up until the final date to submit for a grade, which is Sunday, April 25th at 11:59 PM.
Help with technical issues, assignment specification clarifications: TAs will be instructed not to answer questions over the exam or help with exam code in office hours (you may ask about slides, general concepts we have covered, past assignments, etc.). If you have any technical difficulties, please make a private post to Piazza. If you have any questions regarding the tests or clarifications over the assignment specification, please make a private post in Piazza. We will make posts public if the answer should be shared with everyone.
Overview of the assignment:
In this assignment, you will implement your own doubly-linked list data structure as well as an iterator for your list implementation. Your implementation of a doubly-linked list will be based on std::list. To keep the assignment to a reasonable length, you will only be implementing a subset of the interface std::list supports. You will implement a slimmed down version of std::iterator as well (~300-500 lines of code for the list implementation, ~100-200 lines of code for the iterator). A doubly-linked list is a sequential container that stores elements of a specific type. Rather than storing elements in contiguous memory, like a vector or deque, a linked list stores elements throughout memory. Each “node” in the list contains a specific element, but also contains pointers to the next “node” and previous “node” in the list (singly-linked lists only store a pointer to the next “node”). Each “node” in the linked list is dynamically allocated in the heap and the list itself maintains a pointer to the first and last node in the list. This project will require interacting with pointers, understanding explicit memory management and copy control, and an understanding of the C++ standard template libraries.
Table of Contents:
Overview of the assignment: Table of Contents:
Grading breakdown: Getting started:
Part I: my_list implementation Overview of list implementation: Implementation details:
Question I: deep vs. shallow copy
Part II: my_list copy operations Implementation details:
Part III: my_list_iterator implementation Overview of my_list_iterator:
Implementation details:
Question II: iterator types and working with generic algorithms Part IV: applying my_list_iterator to my_list
Getting started:
Important: This assignment has a set of tests provided to help you test your work. Some tests are provided and you should make sure your implementation passes those tests. To ensure your code works well with the unit tests, it is important that you name classes and public member functions exactly as described in this document (anything highlighted in blue needs to be named exactly as it is typed in this document, for example: “my_list” or “void pop_back()”). As in studios 16-21, all files needed for this lab have already been created for you (my_list.h, my_list.cpp, my_list_iterator.h, my_list_iterator.cpp, ListNode.h, ListNode.ccp and files containing the tests), so you should not move the files around, rename files, or create new files.
- To create your repository, visit the link here and accept the assignment.
- Open a Windows machine (using the remote desktop or locally) and open Visual Studio. Clone your repository to your h: drive, or wherever you store your repos for this course if you are working locally. All you need to do is clone your repo, a Visual Studio Solution is
already set up for you.
- Within Visual Studio, open the “Team Explorer” tab. From the “manage connections”
screen, make sure your repository is listed under “Local Git Repositories”. If it is not, click “Add”, navigate to your cloned copy of the repository, and open it. You should see the repository appear under “Local Git Repositories”. Double-click it to make it your active repository. At the bottom of the ”Home” screen of the “Team Explorer” tab, you should see all .sln(visual studio solutions) stored in the repository (there should only be 1). Open “list_assignment.sln” by double-clicking on it and then switch to the “Solution Explorer” tab. You should see the “ ” project as well as “ ”. All of your code should be written within the “ ” project. “ ” contains a set
list_assignment
list_test
list_assignment
list_test
of tests provided so that you may test your codes’ functionality. We may use additional tests when grading, so be sure to test any cases you can think of not covered by the tests.
- Expand the “list_assignment” project. You should see the following header and source files. I’ve provided an overview of what code you will write in each file as well.
- ListNode.h – the nodes of your list (you should not change this file)
- ListNode.cpp
- my_list.h – declaration of the my_list class
- my_list.cpp – function definitions for my_list class
- my_list_iterator.h – declaration of my_list_iterator class
- my_list_iterator.cpp – definitions for my_list_iterator class
- list_assignment.cpp – contains main(), you can use this to test your code as you
work as well as implement solutions for questions I and II
You should write all of your code in these files. You should not rename or move these
files. As a reminder: Do not modify ListNode.h or ListNode.cpp in any way.
- Testing: Originally, nearly all of the tests will contain errors as you have not declared/defined the required classes yet. I would suggest commenting out all of the tests to begin with. Then as you implement required functionality, you can uncomment and run tests that only use functionality you have implemented so far. At the end of each part (1-4), you should be able to uncomment the entire corresponding section of tests. To run the unit tests to test your code perform the following steps:
- Make sure you have built your program.
- Select “Test >> Windows >> Test Explorer” from the top bar of your VS window.
This will open the Test Explorer Window.
- Click the green arrow to run ALL tests. Failed tests will show up red and passed
tests will show up green. Any tests that did not run will have a blue exclamation beside them. Only tests with a completely filled in red or green circle actually ran. Tests with results that are outlined, but not filled did not run for some reason.
- Go back and fix any code that did not pass the given tests! Look at the test for more details on what might have gone wrong. You can also debug the test by right-clicking a test in the “test explorer” window and selecting “debug”. Make sure to set breakpoints in the test or in your code.
Note: Rebuild after you make any changes to your solution before you rerun the tests!
Part I: my_list implementation
Overview of list implementation:
The doubly-linked list data structure has a few highlights:
- ● Each entry in the list is actually a “node”. A node contains a specific element of the type
stored in the list as well as a couple of pointers. One points to the next node in the list,
and one to the previous node in the list
- ● Elements can be added to the front or back of the list in constant time
- ● The first and last element in the list can be accessed in constant time, however a list
does not provide random access to its elements.
A typical list implementation would use generic programming (templates in C++) which we did not cover in this course. Templates would allow us to create a list class that can hold many different element types. Your list will be implemented to store integers only.
The implementation of a linked list typically consists of two distinct classes. The “list” class (my_list in your implementation) stores information about the list such as its size (how many elements it contains) as well as information about where to find its first and last elements. The “node” class/struct (ListNode in your implementation, this class is provided and should not be modified) stores the actual data/elements contained in the linked list. A node also stores the location of the next node in the list as well as the location of the previous node in the list. Nodes are allocated dynamically in the heap as new elements are added to the list.
