User Tools

Site Tools


Sidebar

projects

pct0 (bonus; due 20230823)
wcp1 (due 20230823)
abc0 (due 20230830)
btt0 (due 20230830)
pct1 (bonus; due 20230830)
pct2 (due 20230830)
wcp2 (due 20230830)
mpg0 (due 20230906)
pct3 (bonus; due 20230906)
wcp3 (due 20230906)
pct4 (due 20230913)
ttb0 (due 20230913)
wcp4 (due 20230913)
pct5 (bonus; due 20230920)
ttb1 (due 20230920)
wcp5 (due 20230920)
dap0 (due 20230927)
gfo0 (due 20230927)
pct6 (due 20230927)
wcp6 (due 20230927)
cgf0 (due 20231004)
pct7 (bonus; due 20231004)
wcp7 (due 20231004)
bwp1 (bonus; due 20231018)
cgf1 (due 20231018)
pct8 (due 20231018)
wcp8 (due 20231018)
cgf2 (due 20231025)
pct9 (bonus; due 20231025)
wcp9 (due 20231025)
cgf3 (due 20231101)
gfo1 (due 20231101)
pctA (due 20231101)
wcpA (due 20231101)
pctB (bonus; due 20231108)
waq0 (due 20231108)
wcpB (due 20231108)
pctC (due 20231115)
waq1 (due 20231115)
wcpC (due 20231115)
bwp2 (bonus; due 20231129)
pctD (bonus; due 20231129)
wcpD (bonus; due 20231129)
gfo2 (due 20231206)
pctE (bonus; due 20231206)
wcpE (bonus; due 20231206)
EoCE (due 20231214)
haas:fall2023:data:projects:dlq0

Corning Community College

CSCS2320 Data Structures

PROJECT: Lists - Doubly-Linked Queues (DLQ0)

OBJECTIVE

Onto Queues! 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 queue, like our stack, will in many ways be a restricted-access list: access with the queue functions will only manipulate the list at certain points, creating a consistency we don't have with full-access lists.

Queues are a First In, Last Out structure (or Last In, First 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-dlq0

EDIT

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

BACKGROUND

Queues, similar to stacks, are defined as linear data structures. However, opposite to a stack, a queue is open on both ends, data joins the list of data at the back of the queue, and leaves the list from the front of the queue. This principle is called FIFO, First In First Out.

Think of it as the line of the grocery market when you're ready to be cashed out. The person currently paying for their groceries with the cashier is at the front of the queue, and as soon as they're done paying they will be the first to leave the queue. You on the other hand, since you are the last will to join the queue at the back of the line, will therefore be last to leave the queue.

SPECIFICATIONS

You will find a new header file contained in the inc directory called queue.h.

The new queue struct has the following properties:

  • Node *front - Same as data→lead
  • Node *back - Same as data→last
  • List *data - Pointer to list holding actual queue data
  • ulli buffer - Maximum length of queue (0 = infinite)

For this project you will be working with 6 new functions related to the new queue struct.

  • mkqueue() - Allocates a new queue with an empty list.
  • purge() - Empties & removes the data list from a queue.
  • rm() - Empties, deallocates, and nullifies a queue.
  • cp() - Copies one queue to another.
  • dequeue() - Grabs a node off of the front of a queue.
  • enqueue() - Places a node on the back of a queue.

PROGRAM

Although not specified inside of the functions, the return codes should stack upon each other. So while they list a bunch of DLQ codes, the unit test will specify what return codes should be returned. The ones specified in the unit test include node return codes along with list return codes depending on what is happening.

Queues are composed of lists, so make sure to reuse functions you have previously made from the previous weeks. You can use your stack functions as a reference, and make some tweaking, by doing this not only will it make your life significantly easier, but it will also shorten the amount of time it takes for this project. There is absolutely no need to remake everything you need to do from scratch. 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

Output is strictly modifications to the queue, the associated list, and the front and back nodes. Nothing to stdout aside for testing purposes.

UNIT TESTS

Unit tests ran the same way, make clean, make, and make check to get a general view of all tests. Run each specific unit test inside of bin/ to see what is happening in each specific test. Run the verify-(corresponding test) to see a general view of the specific test, this one displays matches and mismatches without output.

 

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:dlq0:final tally of results (91/91)
*:dlq0:obtained project by the Sunday prior to duedate [6/6]
*:dlq0:clean compile, no compiler messages [13/13]
*:dlq0:implementation passes unit tests [13/13]
*:dlq0:adequate modifications to code from template [26/26]
*:dlq0:program operations conform to project specifications [26/26]
*:dlq0: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/fall2023/data/projects/dlq0.txt · Last modified: 2022/11/19 17:41 by 127.0.0.1