Corning Community College
CSCS2320 Data Structures
~~TOC~~
This section will document any updates applied to the project since original release:
This is a transitional project, making a few modifications to the list struct forcing some changes to a few functions so that we can better explore the next topic (in dls0).
As such, while this is a standalone project, it should be considered a small one, and one that is given out in combination with another (again: dls0), so be mindful of time management.
You will need to complete this project prior to upgrading to dls0.
For this project, we need to make a modification to the list struct (which you can also check out in inc/list.h):
struct list { Node *first; // pointer to start of list Node *last; // pointer to end of list ulli qty; // quantity of nodes in list };
Specifically, we now have a qty variable, which will keep track of the number of nodes in the list.
To implement qty, all list functions that perform manipulations to the list will need to see some updating (mklist(), insert(), append(), and obtain()). Functions like cplist() should be using the aforementioned functions to manipulate the list, so it does not need any changes (if your cplist() is redundant, it will need to see changes to ensure compatibility).
Again, in src/list/, you are to add support for qty so that, just as the list's first and last maintain an accurate positioning of their respective aspects of the list, qty maintains a count of the total number of nodes still in the list.
You are also to implement 4 additional modes to the display() function.
Be sure to adjust any mode error correction accordingly.
The modes are as follows:
////////////////////////////////////////////////////////////////////// // // Options for list display() and support catlist() functions // #define DISPLAY_FORWARD 000 #define DISPLAY_NOPOSVALS 000 #define DISPLAY_NOASCII 000 #define DISPLAY_SEPS 000 #define DISPLAY_POSVALS 001 #define DISPLAY_BACKWARD 002 #define DISPLAY_ASCII 004 #define DISPLAY_NOSEPS 010
What has changed? There are two additional toggles:
For example, if there was a numeric 65 stored in the node, with DISPLAY_ASCII set, an 'A' should be displayed instead of a 65.
Let's say we have a list with the following elements:
first -> 51 -> 49 -> 51 -> 51 -> 55 -> NULL
51 -> 49 -> 51 -> 51 -> 55 -> NULL
[0] 51 -> [1] 49 -> [2] 51 -> [3] 51 -> [4] 55 -> NULL
'3' -> '1' -> '3' -> '3' -> '7' -> NULL
[0] '3' -> [1] '1' -> [2] '3' -> [3] '3' -> [4] '7' -> NULL
31337
Please see the unit test for more information.
A problem that cropped up from time to time during the list implementation was the instance of a list cycle, where a node accidentally ended up pointing to itself (or a previous location, to the direction of traversal). This led to seemingly “infinite loops” as streams of identical values displayed on the screen, and hopefully pictures drawn to try and track down the source of the problem.
With the doubly-linked list functions (especially insert() and append()) we baked in additional resiliency by having them check the validity of their place pointers, to ensure that place was a legitimate node in the list.
But we've not done anything to address the presence of cycles. Here we will explore how to detect them, and even attempt to ascertain where they start (source) and at what point the list repeats (destination) over and over again.
To assist you in verifying a correct implementation, a fully working implementation of the node library, list library (with new modifications), and group library should resemble the following:
Here is what you should get for the specific functions relevant to dll3:
lab46:~/src/data/dll2$ make check ====================================================== = Verifying Doubly-Linked List Functionality = ====================================================== [mklist] Total: 18, Matches: 18, Mismatches: 0 [append] Total: 47, Matches: 47, Mismatches: 0 [insert] Total: 47, Matches: 47, Mismatches: 0 [obtain] Total: 71, Matches: 71, Mismatches: 0 [display] Total: 54, Matches: 54, Mismatches: 0 ====================================================== [RESULTS] Total: 237, Matches: 237, Mismatches: 0 ====================================================== lab46:~/src/data/dll2$
Here is what you should get for all the functions completed so far in the list library (dll0+dll1+dll2):
lab46:~/src/data/dll2$ bin/verify-list.sh ==================================================== = Verifying Doubly-Linked List Functionality = ==================================================== [mklist] Total: 18, Matches: 18, Mismatches: 0 [cplist] Total: 18, Matches: 18, Mismatches: 0 [rmlist] Total: 7, Matches: 7, Mismatches: 0 [empty] Total: 7, Matches: 7, Mismatches: 0 [append] Total: 47, Matches: 47, Mismatches: 0 [insert] Total: 47, Matches: 47, Mismatches: 0 [obtain] Total: 71, Matches: 71, Mismatches: 0 [display] Total: 54, Matches: 54, Mismatches: 0 [find] Total: 28, Matches: 28, Mismatches: 0 [compare] Total: 12, Matches: 12, Mismatches: 0 [swapnode] Total: 31, Matches: 31, Mismatches: 0 [sortlist] Total: 48, Matches: 48, Mismatches: 0 ==================================================== [RESULTS] Total: 388, Matches: 388, Mismatches: 0 ==================================================== lab46:~/src/data/dll2$
When you are done with the project and are ready to submit it, you simply run make submit:
lab46:~/src/data/PROJECT$ make submit ...
To be successful in this project, the following criteria must be met: