代做CS 225 mp_lists代写留学生C/C++程序

CS 225|mp_lists

Goals

In this MP(machine problem)you will:

● learn to manipulate linked memory by writing functions to modify linked lists

● practice debugging more complex code

● practice using templates

● get familiar with iterators

Checking Out the Code

All assignments will be distributed via our release repo on github this semester.You will need to have set up your git directory to have our release as a remote repo as described in ourgit set up

You can merge the assignments as they are released into your personal repo with

git pull --no-edit --no-rebase release main --allow-unrelated-histories

git     push

The first git command will fetch and merge changes from the main branch on your remote repository named release  into  your  personal.The--no-edit  flag  automatically  generates  a commit message for you,and the--no-rebase flag will merge the upstream branch into the   current  branch.Generally,these  two  flags  shouldn't  be  used,but  are  included  for  ease  of merging assignments  into your  repo.

The second command will  push to origin(your  personal),which will allow  it to track the  new changes from release.

You willneed to run these commands for every assignment that is released. All the files for this lab are in the mp_lists directory.

Preparing Your Code

This semester for MPs we are using CMake rather than just make.This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment.This change does mean that for each assignment you need to use CMake to build your own custom makefiles.To do this you need to run the following in the base directory of the assignment.Which in this assignment is the mp_lists directory.

mkdir        build

cd      build

This first makes a new directory in your assignment directory called build.This is where you will actually build the assignment and then moves to that directory.This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake     ..

This runs CMake to initialize the current directory which is the build directory you just made as the  location to  build  the  assignment.The one argument to  CMake  here  is..which  referes  to    the parent of the current directory which in this case is top of the assignment.This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

You will need to do the above once for each assignment.You will need to run make every time you change source code and want to compile it again.

Background Information:Template Classes

ldentical to what you saw in lecture,template classes provide the ability to create generic container classes.In this MP,you will be writing a List class.

template    

class  List    {

//implementation

};

This simply says that our class List has a parametrized type that we willcall T.Similarly,the constructor will look like this:

template      

List::List(){

//implementation

}

We need the template or template above all of our functions—it becomes part of the function signature.The keywords class and typename can be interchanged.

Template classes need access to the implementation for compilation.Every time a different class is used as the template,the code must be compiled to support containing it.For

example,if you want to make a List,the compiler must take the generic List

implementation code and replace all the Ts with ints inside it,and compile the result(this process is called template  instantiation).Our solution to this  is to#include "List.hpp"at the bottom of our List.h file,and not includeList.h in our List.hpp file.This ensures that whenever a client includes our header file,he/she also gets the implementation as well for compilation  purposes(there are other solutions,but this is how we will solve it in this course).

Background Information:Linked Lists

The interface of this List class is slightly different from what you have seen in lecture.This List  has  no sentinel  nodes;the first  node'Sprev  pointer,and the  last  node'Snext  pointer,are  both NULL.In lieu of these sentinels,we keep a pointer head to the first node,and a pointer tail to the  last node in the List.(In an empty list,both head and tail are NULL.)The List class also has an integer member variable,length,which represents the number of nodes in the List;you will need to maintain this variable.

Background Information:Iterators

If you are not familiar with iterators,please read our notes here. We use iterators to figure out where we currently are in the list,what is the next/previous node,and to access the data.

Iterator class has one member variable,namely a pointer to the node in the list.Some of the core functionality includes moving the pointer,getting current location,and checking the location of the iterator.

Background Information:GDB

We have a reference guide for GDB here.You should read through it to get an idea of how to start gdb,what commands you have available,etc.

曰Guide:How to use GDB

To summarize a bit,you could run:

gdb    --args    ./test"[part=1]"

to debug the part one test cases with gdb,

gdb    --args    ./test"*insert*"

to  debug  all  the  tests  with“insert”in  their  name.

Once you start gdb to execute the tests you want to run,you can set breakpoints to help you debug.For example,we could set a breakpoint at the beginning of a test case we want to debug,or breakpoint(s)at the beginning or end of functions which are not behaving as we expect.For example,if we are failing the insertFront test,we could add a breakpoint at the end of the insertFront function and see if the list lookshow we expect.This will let us know whether to focus our debugging on exactly what the function is doing,or what the test case is doing after this call to insertFront.

For example,we can set a breakpoint in line 25 of our List class like so:

(gdb)b  List.hpp:25

or a breakpoint in line 50 of the part 1 test cases like so:

(gdb)b tests/tests_part1.cpp:50

We can also set breakpoints using function names:

(gdb)b     main

sets a breakpoint at the beginning of main,and

(gdb)b    List::sort()

sets a breakpoint at the beginning of the sort function.You can tab complete this,so for example after typing b List::ins you can press tab to see a list of possible functions starting with ins in the List class,templatized with int.

Remember that Catch will print not only the name of a failing test case,but also what file the  test was in and the line number of the failing assertion.You can use this to decide which tests to run and where you might want to set breakpoints.

OAll of the functions should be implemented iteratively outside of mergesort,which is recursive.If any functions are done recursively,you willencounter a stack overflow.

Part  1:Debugging  &Implementing  Linked  Lists

In your mp_lists folder,you will find that the List class is split into four.h or.hpp files:

●   List.h

●  List.hpp

●   List-ListIterator.hpp

● List-given.hpp

We have provided a partial implementation of a few List functions for this part of the MP.Some functions are written,and some are unwritten.Those functions which are already coded may   have a few bugs in them!This part of the MP is to help get you used to debugging certain kinds of logical and memory related bugs,as well as writing pointer manipulation code.All the

functions are specified in List.h,and their(potentially empty)implementations are in List.hpp orList-ListIterator.hpp for you to write.

You should use gdb,valgrind,and any other debugging tools or techniques you're

comfortable with to complete the first part of this MP(as well as general debugging in Part 2 and beyond).

See the [Doxygen][List]for details of the List class

1Notes on testing There are two ways to test this MP:

1.Using make to make list.cpp into./lists,which allows you to write your own lists to test.

2.Using make test to make./test,which allows you to run the automated tests.

3.You can add test to the automated tests in tests_student.cpp. You're free to run Valgrind (or other tools)on the executables:

val(val)grind(grind)  ./.t(/)est(lis)ts[part=1]

You can also select test cases to run by their names,and run those under valgrind or gdb as well:

./test"List::reverse" ./test"*insert*"

valgrind     ./test"*insert*"    gdb   --args   ./test"*insert*"

List()

This should default construct the list.Keep in mind everything mentioned in the background

for the Linked List class.

~List()and_destroy()

Since the List class has dynamic memory associated with it,we need to define all of the Rule of Three.We have provided you with the Copy Constructor and overloaded operator=.

● You will  need to  implement  the destroyO helper function called by operator=(the assignment   operator)and   the   destructor~List()

· The_destroy()function  should  free all  memory allocated forListNode objects. Insertion

The insertFront Function

(SeetheDoxygen for insertFront.)

● This function takes a data element and prepends it to the beginning of the list.

·If the  list  is empty  before  insertFront  is  called,the  list should  have one element with the same value as the parameter.

·You may allocate neW ListNodeS.

Example For example,ifinsertFront is called on the list of integers <547>

with the  parameter 6,then the  resultant  list should  be <6547>

The insertBack Function

(SeetheDoxygen for insertBack.)

● This function takes a data element and appends it to the end of the list.

·If the list is empty before insertBack is called,the list should have one element with the same value as the parameter.

·You may allocate neW ListNodeS.

Example For example,ifinsertBack is called on the list of integers <547>

with  the  parameter6,then  the  resultant  list  should  be <5476>

Testing Your insert Functions

Once you have completed insertFront and insertBack,you should compile and test them.These tests do not rely on your iterator

make       test

./test         "List::insertFront*"

./test"List::insertBack*" ./test"List::insert*"

Iterator

In order to provide the client code with the ability to read the data from the list in a uniform way,we need to have an iterator.We have provided a list iterator class List-ListIterator.hpp which has some functionality implemented.However,there are a few functions yet to be

written as wellas some functions with buggy implementations!You will need to worry about all   the    functions with a @TODO comment:

●  ListIterator&operator++()

●  ListIterator operator++(int)

●    ListIterator&operator--()

● ListIterator  operator--(int)

● bool operator!=(const ListIterator&rhs)

You will also need to implement the begin() and end()functions in List.hpp to have a way of obtaining an iterator from a List.

Many of the more advanced functionality will be tested by using your iterator.So,you should make sure to debug and implement these after you have finished your insert functions but    before you start working too much on the later functionality.

The split Helper Function (SeetheDoxygen for split.)

● This function takes in a pointer start and an integer splitPoint and splits the chain of  ListNodes into two completely distinct chains of ListNodes after splitPoint many nodes.

·The split happens after splitPoint number of nodes,making that the head of the new  sublist,which should be returned.In effect,there will be splitPoint number of nodes remaining in the current list.

·You      may NOT allocate     neW     ListNodeS

Example For example,if split is called on the list of integers listl=<12345>

then after calling list2   =list1.split(2)the  lists  will  look  like listl                  ==<12>

list2                    ==<345>

Testing Your split Function

Once you have completed split,you  should compile and test  it. make      test

./test"List::split*"

You should see images actual-split_*.png created in the working directory (these are generated by  repeatedly splitting split.png).Compare them against expected-split_*.png.

The waterfall Function (Seethe Doxygen for waterfall.)

● This function modifies the list in a cascading manner as follows.

·Every  other  node  (starting  from  the  second  one)is  removed  from  the  list,but  appended at  the  back,becoming  the  new  tail.

● This continues  until the  next thing to  be  removed  is  either the tail(not  necessarily the original tail!)or  NULL.

·You  may NOT  allocate neW ListNodeS.

·Note  that  since  the  tail  should  be  continuously  updated,some  nodes  will  be  moved more  than  once.

Example For example,if waterfall is called on the list of integers <12345678>

then the  call  to waterfall()should  result  in <13572648>

(Do you see the pattern here?)

Step-by-Step Example We will look again at the list <12345678>

When we call waterfal1,this  is how it should look step-by-step: <12345678>-Skip the 1

curr                           tail

<13456782>-Remove the 2 and move it at the end curr                tail

<13567824>-Skip  the  3,and  move  the  4  to  the  end curr                     tail

<13578246>-Skip  the  5  and  move  the  6  to  the  end curr       tail

<13572468>-Skip the 7 and move the 8 to the end

curr           tail

<13572684>-We         have          moved         past          the          original         tail          of         the          list.

This is okay!Skip the 2 and move the 4 to the end,

curr    tail        now      for      the      second      time!

<13572648>Skip  the   6   and  move  the   8   to  the   end,now   for  the   second   time!

curr   tail

We are done now because we skip over the 4 and get to the tail of the list.The s stays in place, and we have finished.If you were keeping track of moves,you would notice that a number

(they happen to be in order here for convenience)gets moved the same amount of times as it  is divisible by 2!Technically this might not be true for the s,but we could have moved it that    last time,it just would have stayed where it was(remove it from the tail and put it back to the tail).Kinda    neat,huh?

Testing Your waterfal1 Function

Once you have completed waterfall,you should compile and test it. make    test

./test"List::waterfall*"

Testing   Part   1

Compile your code using the following command: make      test

After compiling,you can run all of the part one tests at once with the following command: ./test    [part=1]

Notes

● These tests are deliberately insufficient. We strongly recommend augmenting these tests with your own.

● Be sure to think carefully about edge cases and reasonable behavior of each of the   functions when called on an empty list,or when given an empty list as a parameter.

·It        is highly     advised to    test   with    lists   of integers before     testing     with     lists     of     HSLAPixelS.

·Printing out a list both forward and backwards(eg,using an iterator or a custom print function)is one way to check whether you have the double-linking correct,not just

forward linking.Printing the size may also help debug other logical errors.

ODOUBLE CHECK that  you  can  confidently  answer“no”to  the  following  questions:

·Did I allocate new memory in functions that disallow it?

·Did     Imodify     the      data     entry     of     any      ListNode? ·Do  l  leak  memory?

Extra Credit Submission

For extra credit,you can submit the code you have implemented and tested for part one of mp_lists.Follow the submission   instructions section for handing in your code.

Part 2

The reverse Helper Function (SeetheDoxygen for reverse.)

In List.hpp you will see that a public reverse method is already defined and given to you.You are to write the  helper function that the  method  calls.

·This function will  reverse a  chain of linked  memory  beginning  at startPoint and ending at endPoint.

·The startPoint and endPoint pointers should point at the new start and end of the chain of linked   memory.

● The next member of the ListNode before the sequence should point at the new start,and the prev member of the ListNode after the sequence should point to the new end.

·You   may NOT allocate neW ListNodeS.

Example For example,if we have a list of integers <1234567>

(with head pointing at 1and tail pointing at 7)and call the public function reverse()

The resulting list should be <7654321>

(with head pointing at 7 and tail pointing at 1)

9 Your helper function should be as general as possible!In other words,do not assume  your reverse()helper function  is called only to  reverse the  entire  list-it may be called to reverse only parts of a given list.

Additionally,the pointers startPoint and endPoint that are parameters to this function should at its completion  point to the  beginning and end of the  new,reversed sublist.

The reverseNth Function

(SeetheDoxygen for reverseNth.)

·This function  accepts  as  a  parameter  an  integer,n,and  reverses  blocks  of  n  elements  in the  list.

·The  order  of the  blocks  should  not  be  changed.

·If  the  final  block(that is,the  one  containing  the  tail)is  not  long  enough  to  have  n

elements,then just  reverse  what  remains  in  the  list.In  particular,ifn  is  larger  than  the length of the list,this will do the same thing as reverse.

·You   may NOT allocate neW ListNodeS.

Example For example,if reverseNth is called on the list of integers

<123456789>

then the call to reverseNth(3)should result in <321654987>

For the list of integers <123456>

the call to reverseNth(4)should result in <432165>

1Hint You should try to use your reverse()helper function here. Testing Your reverse Functions

Once you have completed reverse and reverseNth,you should compile and test them.

make test

./test"List::reverse"

./test  "List::reverseNth  #1" ./test"List::reverseNth #2"

Sorting

You will be implementing the helper functions for one more member function of the List

template class:sort.This is designed to help you practice pointer manipulation and solve an interesting algorithm problem.In the process of solving this problem,you willimplement several helper functions along the way-we have provided public interfaces for these helper functions to help you test your code.

Themerge Helper Function

(SeetheDoxygen for merge.)

·This function takes in two pointers to heads of sublists and merges the two lists into one in sorted order(increasing).

● You can assume both lists are sorted,and the final list should remain sorted.

·You should use operator

·You may NOT allocate neW ListNodes!

Example For example,if we have the following lists

listl=<1346>

list2       =<257>

then after calling list1.mergeWith(list2)the lists will look like

listl                                           ==<1234567>

list2                 ==<>

Testing Your merge Function

Once you have completed merge,you should compile and test it. e(ak)s(e)t      test "List::merge"

You should see the image actual-merge.png created in the working directory if your program

terminates properly.This is generated by merging the images tests/mergel.png and tests/merge2.png.Compare   this   against    expected-merge.png.

The mergesort Helper Function (SeetheDoxygen for mergesort.)

● This function sorts the list using the merge sort algorithm,explained     below.

·You should use operatorobjects.This allows you to perform the comparisons  necessary for sorting.

·You should use the private helper functions you wrote above to help you solve this problem.

·You   may NOT allocate neW ListNodeS

·This   function's   runtime   willbe   graded   for   efficiency(correct   Big-Oh   runtime) Example For example,if sort is called on the list of integers

<615843729>

the resulting list should be <123456789>

Merge Sort-Algorithm Details

Merge Sort is a recursive sorting algorithm that behaves as follows:

● Base Case:A  list  of  size  1is  sorted.Return.

● Recursive Case:

o  Split  the  current  list  into  two  smaller,more  manageable  parts

o Sort the two halves(this should be a recursive call)

o Merge the two sorted halves back together into a single list

In other words,Merge Sort operates on the principle of breaking the problem into smaller and smaller pieces,and merging the sorted,smaller lists together to finally end up at a completely sorted  list.

Testing Part 2

Compile your code using the following command:

make test

After compiling,you can run the part two tests at once with the following command: ./test  [part=2]

Hint:Comparing similar images Occasionally diff may tell you that the 2 images differ,but you cannot easily tell the difference with the naked eye.In these scenarios,there is a great tool on ews machines called compare which can help you.

compare out.png out_01.png out_difference.png

This command will create a new image called out_difference.png where any differing pixels willbe  bright  red.

Notes

·These  tests  are  deliberately  insufficient.We  strongly  recommend  augmenting  these tests with your own.

·Be sure to think carefully about reasonable behavior of each of the functions when called on an empty list,or when given an empty list as a parameter.

·It is highly advised to test with lists of integers before testing with lists of HSLAPixelS.

·Printing out a list both forward and backwards is one way to check whether you have the double-linking correct,not just forward linking.Printing the size may also help debug

other logical errors.

9DOUBLE  CHECK that you  can  confidently  answer “no”to the following  questions:

·Did I allocate new memory in functions that disallow it? ·Did I modify the data entry of any ListNode?

·Do I  leak  memory?

Grading  Information

We will use the following files for grading:

●  List.h

●  List.hpp

●     List-ListIterator.hpp

All other files including any testing files you have added will not be used for grading.

To submit your assignment you upload these file to the mp_lists questions here for

PrairieLearn EC and PrairieLearn Final.