User Tools

Site Tools


Sidebar

projects

wcp1 (due 20220824)
ael0 (due 20220831)
ntr0 (due 20220831)
pct1 (bonus; due 20220831)
wcp2 (due 20220831)
pct2 (due 20220907)
pct3 (bonus; due 20220907)
sln0 (due 20220907)
wcp3 (due 20220907)
sln1 (due 20220914)
wcp4 (due 20220914)
pct4 (due 20220915)
sll0 (due 20220921)
wcp5 (due 20220921)
pct5 (bonus; due 20220922)
gfo0 (due 20220928)
sll1 (due 20220928)
wcp6 (due 20220928)
pct6 (due 20220929)
pct7 (bonus; due 20221005)
sll2 (due 20221005)
wcp7 (due 20221005)
bwp1 (bonus; due 20221019)
pct8 (due 20221019)
sll3 (due 20221019)
sll4 (due 20221019)
wcp8 (due 20221019)
pct9 (bonus; due 20221026)
wcp9 (due 20221026)
dll0 (due 20221027)
dln0 (due 20221027)
gfo1 (due 20221102)
pctA (due 20221102)
wcpA (due 20221102)
dll1 (due 20221103)
pctB (bonus; due 20221109)
wcpB (due 20221109)
dll2 (due 20221110)
dls0 (due 20221110)
pctC (due 20221116)
wcpC (due 20221116)
dlq0 (due 20221117)
bwp2 (bonus; due 20221201)
pctD (bonus; due 20221201)
wcpD (bonus; due 20221201)
pctE (bonus; due 20221207)
wcpE (bonus; due 20221207)
gfo2 (due 20221208)
EoCE (due 20221219)
haas:fall2022:data:projects:dls0

Corning Community College

CSCS2320 Data Structures

PROJECT: Lists - Doubly-Linked Stacks (DLS0)

OBJECTIVE

Onto Stacks! Another very commonly used data structure, we will be building it atop our list.

Don't forget to contribute to project documentation! That helps to ensure everyone is invested in the project.

OVERVIEW

Our stack will in many ways be a restricted-access list: access with the stack functions will only manipulate the list at certain points, creating a consistency we don't have with full-access lists.

Stacks are a First In, First Out structure (or Last In, Last Out), and understanding the value that provides is key to effectively leveraging this data structure.

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

EDIT

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

BACKGROUND

Stacks are linear data structures, that may be structured by linked lists. Linked lists are only accessed by one end and in the case of our project, this may be the lead or last node, (we will have to verify that with the unit tests scripts).

In the dls0/inc directory is a new file, stack.h , which defines the stack struct. The members of the stack struct for this project include Node *top (a pointer to the top of the stack), List *data (pointer to stack data), ulli size (size of the stack).

cd

SPECIFICATIONS

The top of the stack follows the list in reverse order. The top of the stack will be equal to the last node of the list.

myStack → top = myList → last

There will be approximately 7 functions, will have to confirm that once you upgrade. These new functions go as follows:

  • push() - Place a new node onto top of stack.
  • pop() - Remove a node from top of stack.
  • peek() - See node from top of stack.
  • isempty() - Return if stack is empty or not.
  • cpstack() - Copy stack to another.
  • mkstack() - Create and initialize a new stack.
  • rmstack() - Empty, deallocate, and nullify stack.

Do your best to not reinvent the wheel. This project contains a lot of work with node's and list's and thoughtful use of previously made functions relating to those data structures will lead to cleaner code. This is also a time to test your previously made functions in an actual use environment, where you can see if it actually works outside of specified unit tests.

Applying List functions in stack functions

Below are pairings of stack functions on the left, and list functions that could be very useful in accomplishing these stack functions on the right.
mk.c → mklist
push.c → append
pop.c → obtain
cpstack.c → mkstack, cplist
peek.c → cpnode
rmstack.c → rmlist

USE YOUR LIST FUNCTIONS TO HANDLE NODES WITHIN THE STACKS

KEY NOTE: Remember that the dereferenced version of the double pointers inside other functions you use should be NULL. Most of the functions previously made should have had an error if the dereferenced list/node was not NULL.

*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 the stack are 3 different objects, a node, a list, and the size of the stack. The node is the top of the stack, and follows the last node of the list. For the purpose of your push and pop functions, new nodes from push should go to the end of the list, and that should be the new top. For pop, it should take off the end of the list, and reassign the new top, which is the last node in the list. Also, you can make use of the make command -make use-test-reference. This uses a working implementation of object files from the previous dllX projects, and can very much help you if your previous projects did not pass all unit tests.

OUTPUT SPECIFICATIONS

No output should be visible outside of testing purposes inside unit tests. Functions will modify the corresponding list/node/stack according to what is asked of the function.

UNIT TESTS

 

SUBMISSION

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

  • Project must be submit on time, by the deadline.
    • Late submissions will lose 33% credit per day, with the submission window closing on the 3rd day following the deadline.
  • All code must compile cleanly (no warnings or errors)
    • Compile with the -Wall and –std=gnu18 compiler flags
    • all requested functionality must conform to stated requirements (either on this document or in a comment banner in source code files themselves).
  • Executed programs must display in a manner similar to provided output
    • output formatted, where applicable, must match that of project requirements
  • Processing must be correct based on input given and output requested
  • Output, if applicable, must be correct based on values input
  • Code must be nicely and consistently indented
  • Code must be consistently written, to strive for readability from having a consistent style throughout
  • Code must be commented
    • Any “to be implemented” comments MUST be removed
      • these “to be implemented” comments, if still present at evaluation time, will result in points being deducted.
      • Sufficient comments explaining the point of provided logic MUST be present
  • No global variables (without instructor approval), no goto statements, no calling of main()!
  • Track/version the source code in your lab46 semester repository
  • Submit a copy of your source code to me using the submit tool (make submit on lab46 will do this) by the deadline.

Submit Tool Usage

Let's say you have completed work on the project, and are ready to submit, you would do the following:

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:

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

Pertaining to the collaborative authoring of project documentation

  • each class member is to participate in the contribution of relevant information and formatting of the documentation
    • minimal member contributions consist of:
      • near the class average edits (a value of at least four productive edits)
      • near the average class content change average (a value of at least 256 bytes (absolute value of data content change))
      • near the class content contribution average (a value of at least 1kiB)
      • no adding in one commit then later removing in its entirety for the sake of satisfying edit requirements
    • adding and formatting data in an organized fashion, aiming to create an informative and readable document that anyone in the class can reference
    • content contributions will be factored into a documentation coefficient, a value multiplied against your actual project submission to influence the end result:
      • no contributions, co-efficient is 0.50
      • less than minimum contributions is 0.75
      • met minimum contribution threshold is 1.00

Additionally

  • Solutions not abiding by spirit of project will be subject to a 50% overall deduction
  • Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
  • Solutions not utilizing indentation to promote scope and clarity or otherwise maintaining consistency in code style and presentation will be subject to a 25% overall deduction
  • Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction
haas/fall2022/data/projects/dls0.txt · Last modified: 2022/11/12 15:24 by wedge