Table of Contents

Corning Community College

CSCS2320 Data Structures

PROJECT: Singly-Linked List of Nodes (SLL2)

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.

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-sll2

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 sll2 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 sll2 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/sll2/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}

Then try building the project again.

BACKGROUND

In previous weeks we have been building our list library to include some tools to check our lists for various things. This week we will add functionality modify its contents with a bit more precision. Ever thought you might want to clear the contents and/or remove your list entirely; once you are done with it, of course… Maybe you want to sort your list by the values its nodes contain or simply remove a node and move some things around yourself? If so, cool. Make it do the thing.

SPECIFICATIONS

This week we will finish up the core functions by adding obtain to our list library. The three core functions are insert, append, and obtain.

This week you will find five new .c files, each containing their corresponding functions.

We have 5 tasks to do for full credit. These are:

  • clear() deallocates all nodes, returns an empty list
  • obtain() contains a double pointer (should use getpos() and setpos() from previous sllX)
  • rm() should be making use of the clear()
  • sort() could be supported with swap, but is not necessary
  • swap() changes positions between two nodes inside the list, assuming they are there.

You also have an extra task, for extra credit (26 points), inside app/list/ of your sll2 base directory. The extra credit task is to build a linked list based on input from the user. You will also determine whether or not this linked list is a palindrome linked list or not. In case you don't know what a palindrome list is, here is an example. A palindrome list is a list that would look the same if you reversed it. For example, if you have a list, 1 2 3 2 1, that would be a palindrome, because if you display it backwards or forwards, it would display the same thing.

The palindrome should accept values either from the CLI, stdin, or both. Be able to determine if the created list is a palindrome. Reverse the list(hint: use sortlist()). Finally, display the list.

*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

Recommended Order to make functions:

  1. obtain()
  2. clearlist()
  3. rmlist()
  4. swap()
  5. sort()

Details as to the behaviour of the functions can be found as comments inside the .c files of the programs themselves, located in src/list. If confusion arises in the make check process to verify then the .c code of the verify files can be found inside the unit/list directory. Do note that the verify code can rely upon some of the functions you are making to check the others, hence the recommended order.

The unit tests for sll2 make use of several of the functions made in previous projects as well. So if some of those other functions aren’t working as they should be, it could cause mismatches in the unit tests for sll2. It may be helpful to run the unit tests individually to check the output of specific functions.

Make sure to not overestimate what you are trying to do, especially in obtain(), do not try to optimize your program by removing the node, because the node will be held in the double pointer thatNode.

If you have difficulty debugging obtain(), ensure lead and last pointers are being set appropriately: if you are obtaining the first node in the list update the lead pointer, if you are obtaining the last node in the list update the last pointer. Not doing so may cause an endless loop in unit-obtain.

OUTPUT SPECIFICATIONS

UNIT TESTS

Basic GDB

GDB is a very useful tool, especially if you are running into segmentation faults on any unit test. GDB allows you to set breakpoints, find the line of a segfault, display values of variables at a particular point in the program, and step line by line. Below are some common examples:

To launch gdb (obtain used as example):

USER@lab46:DIR/sll2/unit/list$ gdb unit-obtain
Basic Operations

Placing a breakpoint at line #5:

(gdb) b 5

Placing a breakpoint at function main():

(gdb) b main

Run program until next breakpoint:

(gdb) r
**or**
(gdb) run

Continue after breakpoint is hit:

(gdb) c

Display variable state:

(gdb) print var

Execute one line (after breakpoint is hit):

(gdb) n

Step into function:

(gdb) s
 

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

Pertaining to the collaborative authoring of project documentation

Additionally