Table of Contents

Corning Community College

CSCS2320 Data Structures

PROJECT: Singly-Linked List of Nodes (SLL3)

OBJECTIVE

To continue to enhance our ability to explore various algorithmic and computing realms through the exploration and cultivation of debugging and troubleshooting skills, and collaboratively authoring and documenting the project and its specifications.

OVERVIEW

Now with our singly-linked list implementation complete, we will perform a baseline tweak for use with the group data structure in sll4 (a group of lists). That particular tweak is the incorporation of a quantity element, so each and every transaction upon the list needs to maintain the accuracy of the node count.

UPGRADING

To assist with consistency across all implementations, project files for use with this project, along with the integration of the work you did on the last project, is made possible via a special recipe in the Makefile.

Simply go into the project base directory, and run:

lab46:~/src/SEMESTER/DESIG/prevPROJECT$ make upgrade-sll3

EDIT

You will want to go here to edit and fill in the various sections of the document:

FIXES

If you are getting unexplainable build errors on your own system when you run 'make default' after already running 'make clean', it can be one of two things.

Firstly, it can be because your using the wrong version of gcc, the sll3 project files can only compile with version 9 of gcc. You can use the same version of gcc as lab46 by using the following commands (assuming you are using a Raspberry Pi with it's default OS) in this link: https://gist.github.com/sol-prog/95e4e7e3674ac819179acf33172de8a9

If that does not fix the problem then you need to edit one of the Makefiles in the sll3 project directory. The offending Makefile is in the /src/list/ directory. Run the following command to edit that file:

USER@SYSTEM:$ nano ~/src/SEMESTER/DESIG/sll3/src/list/Makefile

remove the following line of code (after the line that says lib:)

@date +'%Y%m%d%H%M%S' >> /var/public/$(SEMESTER)/$(DESIG)/$(PROJ)/.updates/.metrics/${USER}

You might have to change the semester to fall2022 instead of having it check for the semester by checking the directory. You can delete what SEMESTER is set to and insert fall2022 instead.

Note that if you are working on your pi there may be no semester file to begin with, so to create it simply use cd /usr/local/etc/ to go to the relevant location, use sudo su to gain root access, create a file named “semester”, and insert “fall2022” into it. Then use can exit root with the “exit” command to decrease the likelihood of doing something you shouldn't.

Then try building the project again.

BACKGROUND

There are no new files or functions to work on this week. Instead, we will be going back to some of the core list-processing functions we've developed in the previous weeks, and enhance their functionality to expand our linked-list data structure. Once you upgrade to SLL3, you will see a couple of new properties on the 'list' struct, contained in the list.h file.
These two new properties are:

  • qty: An 'unsigned long int,' that indicates the number of nodes contained within the 'list.'
  • next: A 'list' pointer that points to another 'list,' this way we will link one list to another.

Do not overthink these properties. To get a better understanding of what they are, think back to the functionality of our nodes. Our Node structs have 2 properties, 'info' and 'right.' The info variable holds data within the node. The 'right' pointer links the current node to another node. With that in mind, qty and next will work in a similar way.

Going up in a level of abstraction, lists are the new nodes! Linking lists does not mean merging nodes. A list pointing to another means that they are only linked together, each list will conserve its own nodes and pointers.

SPECIFICATIONS

Therefore, it is our task to modify our core node-list-processing functions to modify the qty value when necessary. When does the qty value change? When you add or remove nodes from the list! And to have a 'next' pointer ready to point to a linked list. For sll3, we will not focus much on 'next,' next will be part of sll4.

Depending on how you coded your functions, these are functions you might be looking to modify:

  • mk(): Implement the new functionality of 'qty' and the next 'list'
  • insert(): Add new functionality related to 'qty'
  • append(): Same as insert
  • obtain(): Opposite of insert() & append()
  • cp(): Make sure to copy the new properties of the struct 'list'
  • perhaps even clear().

Remember, these are list functions.

*Our task is to ask questions on Discord or in class and document our findings on this wiki page collaboratively, regarding the functionality of this project.

*For anybody interested in editing the wiki page, here is the dokuwiki user guide: https://www.dokuwiki.org/wiki:syntax#basic_text_formatting -Ash

PROGRAM

Inside list.h, the included header file given to you when you upgraded, and that you've had for the past few iterations of this project was updated with additional variables. Two new variables were added to the list struct.

Those are qty and next.

  • [next] is a pointer to the next list, we are now dealing with groups of linked lists. (myList → next)
  • [qty] contains the amount of nodes in the list. (myList → qty)

Other than that, nothing has changed inside the list.h file given to you. This project should take minimal time, don't be surprised if it seems too easy, that's why sll3 and sll4 are due both the week after break week. More detailed information about the types of qty and the next pointer are specified above in the specifications section.

Remember- with the new quantity property, you only want to change it's value if you are adding/removing nodes to the list (Only in insert, append, and obtain). Also, be sure you check that you are not incrementing the quantity if inserting NULL to the list, or else your quantity will be incorrect (qty 1 number off on insert unit test). This should be checked for each function that inserts/removes nodes from the list.

OUTPUT SPECIFICATIONS

Nothing has changed in terms of output from your original five functions. Only add functionality of the new variables to the previously made functions.

UNIT TESTS

Unit Tests are again located inside bin/ after you compile. To compile, from the base sll3 directory, make clean(should be done every time but first time is not necessary) then make. An errors file will be created after running make, this may be helpful if things aren't compiling correctly. Unit Tests will have more tests in each than previous, these tests are for your next and qty variables.

DEBUGGING

Useful tools for debugging issues are gdb and examining the test files themselves. to utilize gdb, run the test program with the gdb command (not make check), with a command that might look like “gdb ./bin/unit-lobtain”. Once in gdb the “run” command with start the program, and “break (line number)” will cause the program to stop at the specified line number. Once you have hit the breakpoint you can use “display (variable name)” to see the value of a variable at every step, “n” to step to the next line, and “continue” to continue running the program until the next breakpoint. Note that if you encounter a seg fault the program will tell the where the seg fault occurs, and you can use “run” again to restart the program.

 

SUBMISSION

To be successful in this project, the following criteria (or their equivalent) must be met:

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following (assuming you have a program called uom0.c):

lab46:~/src/SEMESTER/DESIG/PROJECT$ make submit

You should get some sort of confirmation indicating successful submission if all went according to plan. If not, check for typos and or locational mismatches.

RUBRIC

I'll be evaluating the project based on the following criteria:

78:sll3:final tally of results (78/78)
*:sll3:obtained project by the Sunday prior to duedate [13/13]
*:sll3:clean compile, no compiler messages [13/13]
*:sll3:implementation passes unit tests [13/13]
*:sll3:adequate modifications to code from template [13/13]
*:sll3:program operations conform to project specifications [13/13]
*:sll3:code tracked in lab46 semester repo [13/13]

Pertaining to the collaborative authoring of project documentation

Additionally