• May 15, 2020

题意:C++实现名为JaggedArray的自定义数据结构及其相关操作解析:  JaggedArray是大小为n的一维数组,代表n个箱子,每个箱子存储template型元素的集合T。JaggedArray具有两种显示模式:unpacked和packed。示意图如下:  Unpacked模式:
offsets和packed_values置空;counts记录每个箱子包含的元素个数,count[1]=3即第二个箱子存放3个元素;unpacked_values详细记录每个箱子包含的元素信息,unpacked_values[1]=abc即第二个箱子存放a、b、c。 Packed模式:
unpacked模式支持插入和删除元素,addElenent(3,’g’)表示在unpacked_values[3]中插入元素g,removeElement(1,1)表示从unpacked_values[1]中删除下标为1的元素(从0开始)。示意图如下:涉及知识点:C++ 指针,动态数组,template,内存分配与释放 更多可加微信讨论微信号:WHJ980416pdf

CSCI-1200 Data Structures | Fall 2019Homework 3 | Jagged ArrayIn this assignment you will build a custom data structure named JaggedArray. A JaggedArray is a 1D arrayof n bins, and each bin stores a collection of elements of templated type T. Building this data structure willgive you practice with pointers, dynamic array allocation and deallocation, and writing templated classes.The implementation of this data structure will involve writing one new class. You are not allowed to use anyof the STL container classes in your implementation or use any additional classes or structs. Please read theentire handout before beginning your implementation. Also, be sure to review the Lecture 6 notes.MotivationThe JaggedArray class is found in many real-world applications where a variable number of elements arestored in a collection of bins. This data structure is helpful to ensure high performance for applicationsneeding frequent read and write access to this organizational information.For example, let’s consider a physical simulation with hundreds of ping pong balls bouncing around insidea box. We will need to calculate the collisions of the balls with the sides of the box, but also the collisionsof the balls with each other. A naive, brute-force implementation will require consideration of all pairwisecollisions { for n balls, this is n2!A relatively straightforward optimization will instead consider the interactionof each ball with only its nearest k neighbors = k ∗n total potential collisions (agreat improvement for large n!). How do we efficiently find each ball’s nearestneighbors? If we divide space into a large grid of bins and sort all the balls intothe bins, we can find the nearest neighbors of a particular ball by collecting theballs in the same bin (and the adjacent bins). How many balls are in each bin?Some bins are empty. Some bins have several or many balls. As the simulationprogresses and the balls move around, balls move in and out of bins and thenumber of balls in each bin changes. A JaggedArray could be a great choicefor storing this data for efficient collision detection.The Data StructureThe JaggedArray class you will implement has two fundamental representation modes: unpacked and packed.In the unpacked representation, the JaggedArray stores an array of integers containing the counts of howmany elements are in each bin and an array of pointers to arrays that hold these elements. In the packedrepresentation, the JaggedArray stores an array of offsets for the start of each bin. These offsets refer toa single large array that stores all of the elements grouped by bin but all packed into the same large array.We can convert a JaggedArray from unpacked to packed mode by calling the pack member function andsimilarly convert from packed to unpacked by calling unpack. Below is an illustration of both representationsfor a small example with 7 bins storing 6 total elements (unpacked on the left, packed on the right):The JaggedArray stores elements of template type T. In the examples in this handout, T is type char.The representation consists of the six member variables presented in these diagrams and you should exactlyfollow this representation (variable names, types, and data). Depending on the mode (unpacked or packed)of the JaggedArray, two of the variables are set to NULL. The JaggedArray contains the expected accessorfunctions numElements, numBins, numElementsInBin, getElement, and isPacked and modifiers addElement,removeElement, and clear. See the provided main.cpp code for example usage and details on the argumentsand return values for these functions.In the packed version of the data structure, the first element in bin i is stored at the index stored inoffsets[i]. The number of elements in the bin is equal to offsets[i+1] – offsets[i]. Except the lastbin, which contains num_elements – offsets[i] elements.Modifying the Data StructureThe JaggedArray can only be edited while in unpacked mode. The left diagram illustrates the necessarychanges to the representation for the call addElement(3,’g’), which adds the element ’g’ to bin 3 (the binsare indexed starting with 0). And the diagram on the right illustrates the changes to the representation forthe subsequent call to removeElement(1,1) which removes the element in slot 1 (element ’b’) from bin 1.Note how the variables holding the total number of elements in the JaggedArray and the count of theelements for the specific bin are updated appropriately.For our implementation we will always size each of the arrays to exactly contain the required information.This will ensure you get plenty of practice with proper allocation and de-allocation. When the new array isallocated, the necessary data from the old array is copied and then the old array is de-allocated.Attempting to access the non-existent bins or elements (out-of-bounds indices) is an error. Similarly,attempting to edit a JaggedArray while the array is in packed mode is an error. Your program shouldcheck for these situations, and if a problem is detected, your program should print an appropriate warningmessage to std::cerr and call exit(1).Testing, Debugging, and PrintingWe provide a main.cpp file with a wide variety of tests of your data structure. Some of these tests areinitially commented out. We recommend you get your class working on the basic tests, and then uncommentthe additional tests as you implement and debug the key functionality of the JaggedArray class. Study theprovided test cases to understand what code triggers calls to your JaggedArray copy constructor, assignmentoperator, and destructor and verify that these functions are working correctly.It is your responsibility to add additional test cases, including examples where the template class type T issomething other than char. You must also implement a simple print function to help as you debug yourclass. Include examples of the use of this function in your new test cases. Your function should work forJaggedArrays containing char, int, and reasonably short strings. The print function does not need towork for more complex types. Please use the example output as a guide (we will grade this output by hand).2Performance AnalysisThe data structure for this assignment (intentionally) involves a lot of memory allocation & deallocation.Certainly it is possible to revise this design for improved performance and efficiency or adapt the datastructure to specific applications. However, for this assignment, please implement the data structure exactlyas described.In your README.txt file include the big O notation for each of the JaggedArray member functions describedabove: numElements, numBins, numElementsInBin, getElement, isPacked, clear, addElement, removeElement,pack, unpack, and print and don’t forget the constructors, destructor, and assignment operator. Foreach function determine the performance for each of the representation modes (packed and unpacked), asappropriate. You will be graded on the big O notation efficiency of your implementation, so carefullyconsider any significant implementation choices.You should assume that calling new [] or delete [] on an array will take time proportional to the numberof elements in the array. In your answers use the variables b = the number of bins, e = the number ofelements, and k = the number of elements in the largest bin.Debugging Memory Errors and Looking for Memory LeaksTo help verify that your data structure does not contain any memory errors or memory leaks and thatyour destructor is correctly deleting everything, we include a batch test function that repeatedly allocates aJaggedArray, performs many operations, and then deallocates the data structure. To run the batch test case,specify 2 command line arguments, a file name (small.txt, medium.txt, or large.txt) and the number oftimes to process that file. If you don’t have any bugs or memory leaks, this code can be repeated indefinitelywith no problems.On Unix/Linux/OSX, open another shell and run the top command. While your program is running, watchthe value of \RES” or \RPRVT” (resident memory) for your program. If your program is leaking memory,that number will continuously increase and your program will eventually crash. Alternately, on Windows,open the Task Manager (Ctrl-Shift-Esc). Select \View” ! \Select Columns” and check the box next to\Memory Usage”. View the \Processes” tab. Now when your program is running, watch the value of \MemUsage” for your program (it may help to sort the programs alphabetically by clicking on the \Image Name”column). If your program is leaking memory, that number will continuously increase.Memory DebuggersWe also strongly recommend using a memory debugging tool to find errors. Information on installationand use of the memory debuggers \Dr. Memory” (available for Linux/MacOSX/Windows) and \Valgrind”(available for Linux { and possibly MacOSX) is presented on the course webpage: homework submission server is configured to run your code with Dr. Memory to search for memoryproblems. Your program must be memory error and memory leak free to receive full credit.SubmissionDo all of your work in a new folder named hw3 inside of your Data Structures homeworks directory. Use goodcoding style when you design and implement your program. Be sure to make up new test cases and don’tforget to comment your code! Please use the provided template README.txt file for any notes you want thegrader to read. You must do this assignment on your own, as described in the \CollaborationPolicy & Academic Integrity” handout. If you did discuss the problem or error messages, etc.with anyone, please list their names in your README.txt file. When you’ve finished writing, testing,debugging, and commenting your code, prepare and submit your assignment as instructed on the coursewebpage.