Description
Spring 2025
2. Recursive Linked List: Split (weight 0.5)
Overview Write a recursive function to split the elements of a sorted (in increasing order), singly-linked lists of integers into two sorted, singly-linked lists, where the first list contains all items with an odd value, and the second list contains all items with an even value. The original list should not be preserved (see below). Your function must be recursive – you will get NO credit if you use for, while, do while, or goto. If you use helper functions – which you may – then they all must also be recursive. ● You should use the following Node type: struct Node { int value; Node *next; }; ● Here is the function you should implement: void split (Node*& in, Node*& odds, Node*& evens); These are prototyped in split.h for you which you can #include to your split.cpp and test file. You MAY NOT change the definitions provided in this file. ● Empty lists are represented by NULL . You may assume that odds and evens are both NULL when split is called from the main function. ● When your split function terminates, in should be set to NULL (the original list is not preserved), odds should point to the head of a linked list containing all items where value is an odd integer, and evens should point to the head of a linked list containing all items where value is an even integer. Obviously, your solution must not leak memory. Use valgrind to verify correct memory handling and cleanup. Hint: by far the easiest way to make this work is to not delete or new nodes, but just to change the pointers. Testing You will need to test the coding questions yourself with your own test programs. This should cause you to a.) appreciate the importance of testing b.) consider the kinds of test cases you should write (i.e. if none of your test cases exercise a particular set of code in your implementation then you probably need to write more tests) Unset Unset c.) What common tasks related to testing would be useful to reuse and why there are testing frameworks like the one we will use in this class, gtest. (Don’t worry, we’ll cover gtest in lab soon!) While we will only test your split function, you will probably want to write some main code to actually test it. There is a file called test_split.cpp. That file also includes #include “split.h” to bring in the prototype and Node definition. Then you can write a main that instantiates and fills some linked list cases (up to you to do) and then calls split to test its behavior. You must commit this file to your GitHub repo, however it will not be graded. If you get an error NULL is not defined in this scope when compiling split.cpp or your test file, try adding #include to your .cpp file where you are using NULL. Your submission should be in a file called split.cpp, and it should only contain your implementation of the function and NO main(). Using Valgrind If you were to compile a program that takes two arguments: $ ./program input.txt output.txt The corresponding Valgrind command would be: $ valgrind –tool=memcheck –leak-check=yes ./program input.txt output.txt Unset Unset Unset Run the following commands in a terminal (the working directory should be hw1) Compiles without warnings: g++ -g -Wall -std=c++11 -c split.cpp g++ -g -Wall -std=c++11 test_split.cpp split.cpp -o test_split Ensure no Valgrind errors: valgrind –tool=memcheck –leak-check=yes ./test_split Testing with our tests We have provided a few files in the same directory that we will use to grade this code. These tests use the Gtest framework (more on that in lab), but it is fairly easy to use. To run the test code: bash ./grade_split.sh This will compile your split.cpp with our test code and run 12 tests. One time the test will be run normally, and a second time the test will be run with Unset Unset Unset valgrind. A lot of information will be output, but the last few lines will tell you how many tests failed for both the regular execution and with valgrind. If you want to compile and run the test code: g++ split.cpp grade_split.cpp -o grade_split `pkg-config –cflags –libs gtest` ./grade_split Doing it this way will output exactly which tests failed. You can look at the code in grade_split.cpp to see what each test is running. To run a single test you can do: ./grade_split –gtest_filter=Test.Name Test.Name is the name of the test found in grade_split.cpp. For example, there is a test named Split, AllOddsOneEven, you can run just that single test with: ./grade_split –gtest_filter=Split.AllOddsOneEven If you need to see if a single test is failing valgrind (substitute with a real test name): Unset valgrind –tool=memcheck –leak-check=yes ./grade_split –gtest_filter=Test.Name Once your code is working well, make sure to push it to Github: 1. Run git status to see which files have been modified. 2. Run git add on each modified file. Don’t add any object files or executables, just the code you’ve been working on. 3. Run git commit -m where you replace with a short comment like “all done with part 1” 4. Run git push origin main 5. 3. Data structure: unrolled linked list (weight 0.5) Understanding an Unrolled Linked List An unrolled linked list, is a normal linked list (doubly-linked in this case) but each node/item does not store a single data value but an array of values. The head and tail nodes of the linked list may have arrays that are not fully occupied so we keep first and last index to indicate where the first actual data item exists in the array (this index is inclusive) and the last data item exists (this index is exclusive and points to one beyond the last value). These arrays provide better underlying memory performance in most computers (due to caching effects that you’ll learn about in CS 356 or EE 457) and can be more space efficient. In the image above we see each Item struct has a next and prev pointer as would be typical in a doubly-linked list. Then, rather than a single value, it will contain an array of a fixed size where multiple items can be placed. To track which items are used a pair of indices is used of the form: [first, last) where first is inclusive and is the index of the first used item and last is the index 1 beyond the last used index. This approach allows more natural iteration and allows computing the number of items in the range through simple subtraction (i.e. last-first). As an example, first=last=0 indicates no items are used and first=0 and last=10 indicates the 10 elements are occupied (from indices 0..9). To track the head Item, tail Item, and size of the linked list (i.e. number of strings stored in the entire list), the head_, tail_ and size_ members of the ULListStr class are used, respectively. The unrolled list we implement will store strings. For the sake of this homework, we will only ask you to implement the ability to add or remove a value from the front or back of the list (and not in the middle of the list). Each of these operations should run in time O(1). Pushing to the front or back should NOT require moving any values. When pushing to the front, only allocate a new Item if the current head Item has no room before the first Item. When removing an item, only deallocate an Item when the number of used values in its array reaches 0. This means there should not be “empty” C/C++ nodes in the list…when no more array entries of an Item are used, deallocate the Item. 1. You need to examine the code provided in ulliststr.h and ulliststr.cpp and add the implementations for push_back, push_front, pop_back, pop_front, back, front and getValAtLoc in ulliststr.cpp. ○ Below is an example sequence of options: ○ ULListStr dat; dat.push_back(7); dat.push_front(8); dat.push_back(9); cout << dat.get(0) << ” ” << dat.get(1) << ” ” << dat.get(2) << endl; // prints: 8 7 9 cout << dat.size() << end; // prints 3 since there are 3 strings stored ○ ○ Here is a video explanation for some of the possible implementation approaches. ○ Do NOT change any of the public member function signatures or private data members, though you may add additional member functions or data members if you deem them useful. ○ getValAtLoc is a private helper function which will return a pointer to the i-th value in the entire list (not just in a single Item’s array) and is used in several other member functions. If a non-existent location provided to getValAtLoc should cause it to return NULL. ○ As you implement these member functions be sure to meet the RUNTIME requirements. Failure to do so may lead to minimal (less-than half) credit being awarded. Unset ○ To repeat, any comments provided in the skeleton file act as requirements that you must meet. 2. After completing the functions above, you should write a separate program name, test_ullist.cpp, to test your implementation. You should allocate one of your ULListStr items and make calls to push_back, push_front, pop_back, pop_front, back and front that will exercise the various cases you’ve coded in the functions. For example, if you have a case in push_back for when the list is empty and a separate case for when it has one or more items, then you should make a call to push_back when the list is empty and when it has one or more items. It is important that when you write code, you test it thoroughly, ensuring each line of code in the ULListStr class is triggered at some point. You need to think about how you can test whether it worked or failed as well. In this case, calls to get, size, and others can help give you visibility as to whether your code worked or failed. 3. Ensure your solution does not access memory incorrectly or leak memory. Use valgrind to verify correct memory handling and cleanup. 4. Ensure you do not change the filenames of the skeleton we give you and that your test file is named test_ulliststr.cpp and submit it with your other files. Do NOT place a main function in the class file: ulliststr.cpp (it should be in your test file: test_ulliststr.cpp). Obviously, your own ULListStr class should pass your own tests. To compile a program of multiple files you must list ALL the .cpp files in the g++ command line AND NEVER compile a .h file on the g++ command line. Thus, your compilation command would look like: g++ -g -Wall ulliststr.cpp test_ulliststr.cpp -o test_ulliststr Testing with our tests Unset Unset Unset Once your test_ulliststr.cpp is complete and you think your ulliststr.cpp code is ready to test, the instructions are similar to the split.cpp exercise. To run the test code: bash ./grade_ulliststr.sh This will compile your ulliststr.cpp with our test code and run 35 tests. One time the test will be run normally, and a second time the test will be run with valgrind. A lot of information will be output, but the last few lines will tell you how many tests failed for both the regular execution and with valgrind. If you want to compile and run the test code: g++ ulliststr.cpp grade_ulliststr.cpp -o grade_ulliststr `pkg-config –cflags –libs gtest` ./grade_ulliststr Doing it this way will output exactly which tests failed. You can look at the code in grade_ulliststr.cpp to see what each test is running. To run a single test you can do: ./grade_ulliststr –gtest_filter=Test.Name Test.Name is the name of the test found in grade_ulliststr.cpp. Unset If you need to see if a single test is failing valgrind (substitute with a real test name): valgrind –tool=memcheck –leak-check=yes ./grade_split –gtest_filter=Test.Name Once your code is working well, make sure to push it to Github: 1. Run git status to see which files have been modified. 2. Run git add on each modified file. Don’t add any object files or executables, just the code you’ve been working on. 3. Run git commit -m where you replace with a short comment like “all done with part 2” 4. Run git push origin main Next